Re: [boost] Re: Memoization library

From: Joel de Guzman (joel_at_[hidden])
Date: 2003-12-12 20:21:01

David Abrahams wrote:
> "Thorsten Ottosen" <nesotto_at_[hidden]> writes:
> 
> 
>>"David Abrahams" <dave_at_[hidden]> wrote in message
>>news:uwu929r3l.fsf_at_boost-consulting.com...
>>
>>>Jim Apple <japple_at_[hidden]> writes:
>>>
>>>
>>>>Is there any interest in a memoization library?  I've begun writting
>>>>one for the following reasons:
>>>
>>>It might help some of us more ignorant folk if you'd post a definition
>>>of "memoization".
>>
>>and of dynamic programming too and how it differs from memoization :-)
> 
> 
> Especially if by "dynamic programming" you mean something other than an
> optimization technique for finding the least cost path through a
> search space.  That's the only meaning I know for the term.

Dave, you once gave me a link on Packrat Parsing. The paper describes
how to implement linear-time backtracking parsers in lazy functional
languages using memoization. I since lost the link but a quick google
gives:

http://citeseer.ist.psu.edu/534158.html

I wonder how Jim's library can be applied to Spirit... I'd like
to know Jim's comments on this.

-- 
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net