Re: Memoization as alternative to mutation

["Peter van Rooijen" <address@hidden>]

From: "Mark Alexander Wotton" <mwotton@cse.unsw.edu.au>
> On Thu, 12 Feb 2004, Michael St. Hippolyte wrote:
>
> > Hi all,
> >
> > I'm curious as to what is the language community's general feeling
towards
> > memoization and caching as a substitute for mutation.  I'm less
concerned with
> > labels (i.e. whether or not memoization counts as "pure" FP) than with
> > usefulness.  Has memoization proven to be a useful way to implement
things like
> > sorting algorithms, parsers, design patterns, etc?
> >
>
> Packrat parsing is an interesting application of memoization in parsing -
> at an increased storage cost (linear in the size of the program), you get
> a linear time cost and stronger parsing ability than CFGs.
>
> http://www.pdos.lcs.mit.edu/~baford/packrat/thesis/

>From Bryan Ford's thesis:

"Averaged across the test suite, the fully monadic parser uses 646 bytes of
live heap per byte of input, while the hybrid parser uses only 297 bytes of
heap per input byte, and the Pappy-generated parser falls in the middle at
441 bytes of heap per input byte. In general, these results are encouraging:
although packrat parsing can consume a substantial amount of space, a
typical modern machine with 128KB or more of RAM should have no trouble
parsing source files up to 100-200KB."

Who said that packrat parsing used a lot of memory ;-).

> cheers,
> mrak
>
> -- 
> i daren't use punctuation
> when arguing with legalists
> -- demmy
>
>