[boost] Re: Memoization library

From: David Abrahams (dave_at_[hidden])
Date: 2003-12-12 20:33:48

Joel de Guzman <joel_at_[hidden]> writes:

> 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. 

Sure, my NLP system I told you about used dynamic programming,
definitely bottom-up.  I can see how top-down evaluation could
generate big efficiency gains, given first/follow sets.  If that's
all "memoization" means, I'm all for it. 

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com