[Dynamite] July (attn Ewan)

[Ian Holmes]

I actually found something at

http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html

It has general DP code, with applications for matrix multiplication and 
other things, but not string comparison.

I'm going to get this book, it looks cool..

I hosted Lloyd Allison when he came to speak at the Sanger Centre once.

-- 
Ian Holmes  ....  Howard Hughes Medical Institute  ....  ihh@fruitfly.org

On Fri, 19 May 2000, Guy Slater wrote:

> On Thu, 18 May 2000, Ian Holmes wrote:
> 
> > On Thu, 18 May 2000, Guy Slater wrote:
> > 
> > > > I am also keen on introducing a new buzzword of our own ;)
> > > > "object functional"
> > > > 
> > > > The idea is it's analogous to "object relational" (which is an object
> > > > model that mirrors a relational database). "Object functional" is an
> > > > object model that mirrors the properties of a mathematical function -- in
> > > > our case, a likelihood function: Pr { sequence(s) | model, params }
> > > > 
> > > > i may end up submitting something about this to BOSC.. 
> > > 
> > > Yes!  I like "Object Functional" a lot.
> > > 
> > > DP can be implemented most elegantly in functional languages,
> > > and if our object model behaves like that, we're laughing.
> > 
> > Guy, do you have an example of DP in a functional language.
> 
> Unfortunately, the example that really impressed me was in a book(shop),
> Looking around on the web, I had to go a long way to find any examples:
> 
>    ftp://ftp.csse.monash.edu.au/pub/lloyd/FP/edit.fast.m
> 
> ... which is an implementation of O(nk) edit distance calculation,
> by Lloyd Allison (who spoke at ISMB98).  This isn't really what
> we are looking for.
> 
> The code that had impressed me was more like this LCS implemenatation:
> 
>     http://www.csse.monash.edu.au/~lloyd/tildeFP/LML/Examples/lcs.slow.m
> 
> ... which looks pretty much like recurrence relations.
> These examples are both in Lazy ML, which I don't understand.
> 
> > You mentioned Haskell the other day...
> 
> I looked at functional languages a while back, and reckoned haskell
> would be the best to go for, not least because it is the nearest to
> a standard fp language, is most widely used, and hence has the best
> (free) compilers.
> 
> I'll see if I can find that book again at the weekend.
> 
> Guy.
> --
>  
> > So far I have the following general ideas (consider this a sketch for the
> > poster abstract, I guess). PLEASE READ THIS
> > 
> > I want to have a Function.pm container class, with the following methods
> > (or something like):
> > 
> > 	Score evaluate();
> > 	Score evaluate_first_derivative (Param deriv_param);
> > 	Param[] dependent_params();
> > 
> > Each Param has an associated Type saying whether it's a substitution
> > matrix or a scalar or whatever (i've rambled about this before).
> > 
> > Concrete subclasses of Function will include SumOfTerms, ProductOfTerms,
> > SumOfFunctions and ProductOfFunctions -- these will be implemented
> > using Composite.
> > 
> > Composite pattern:
> > http://www.math.luc.edu/~laufer/courses/CSPP521/handouts/Composite-1.htm
> > 
> > These classes will be managed by an Interpreter that parses expression
> > strings, like (stupid example that doesn't make sense but never mind):
> > 
> >     "gap_open * gap_extend^2 * (exon_begin + exon_end) * match(tca,S) / null(tca) / null(S)"
> > 
> > or whatever. The "*", "+" and "/" operators work in probability space.
> > This could confuse people who think in score space. Maybe we could replace
> > them with "AND", "OR" and "GIVEN" to emphasise that the true analogues of
> > probabilistic operators are boolean operators (finally bringing true an
> > ancient prophecy of Guy's, that real Bayesians should #define "TRUE",
> > "FALSE" *and* "MAYBE" at the top of their code).
> > 
> > I would suggest "&" and "|" instead of "AND" and "OR", but the problem is
> > that "|" is also the traditional probabilistic symbol for "conditioned on"
> > (for which I used "GIVEN" in the above notation).
> > 
> > Interpreter pattern:
> > http://csg.uwaterloo.ca/dptool/patterns/behavior/interpre.htm
> > 
> > Then I guess we want an abstract DPTask class, with methods
> > 
> > 	set_query
> > 	set_target
> > 	set_model
> > 	set_param_values
> > 
> > 	time_estimate   (returns something like number of cells * number of transitions)
> > 	memory_estimate (returns number of bytes)
> > 	strategy        (returns purely descriptive text string describing strategy e.g. "divide and conquer")
> >         run             (synchronous, for now)
> > 	state           (returns READY_TO_RUN or FINISHED)
> > 
> > 	save/restore    (private subclass-implemented methods using
> >                          Momentos; called by cache mechanism)
> > 
> > Then, we have abstract algorithm subclasses, like
> > 
> > ViterbiScoreOnly -- has a score() method, raises an exception if state != DONE
> > ViterbiWithTraceback -- has a score() and a traceback() method
> > ForwardScoreOnly -- etc, etc
> > 
> > Wrap all of these up with an abstract AlgorithmFactory. Have concrete
> > subclasses of AlgorithmFactory, such as
> > 
> > IncrediblySlowPerlAlgorithmFactory
> > CWrapperAlgorithmFactory
> > MicrocodeWrapperAlgorithmFactory...
> > 
> > These factories instantiate concrete subclasses, like
> > 
> > ViterbiScoreOnlyLinearSpace
> > ViterbiScoreOnlyLinearSpaceIncrediblySlowInPerl
> > ViterbiWithTracebackQuadraticSpace
> > ViterbiWithTracebackDivideAndConquer
> > ViterbiWithTracebackQuadraticIfPossibleElseDivideAndConquer
> > ...etc etc etc
> > 
> > I spent most of fucking today trying to get too clever with this whole
> > object functional thing, constructing a complicated functional database
> > query language using predicates and bindings and stuff, before realising
> > that the reason it was so dark was that I was up my own arse. It is not
> > worth it. We need to stick to the design goals...
> > 
> > Mind you, I still want to use the phrase "Object Functional" in the poster
> > abstract and pontificate about Haskell. which i reckon is fair enough
> > 
> > ian
> > 
> 
> --
> %!PS % <------ Guy St.C. Slater ------> http://www.ebi.ac.uk/~guy/  <------
> 210 297/a{def}def/b{translate}a b 36/c{rotate}a c 0 1 0 1 12/d{exch moveto}
> a/e{closepath stroke}a/f{index}a/g{0 0 0 0 4 f}a/h{setlinewidth newpath dup
> g}a{pop exch 1 f add 0 h neg d lineto 72 c lineto e 2 h d 3 f 0 108 arc d e
> 18 c 0 2 f neg b 18 c}for 72 c newpath add g 0 7 arc d e pop showpage
> 
> 
> 
> 
>