[Haskell-cafe] memoization

[David Thomas]

I, for one, would love to have a compiler do (a) based on (b), my
specification of (c), and the ability to pin particular things...


On Mon, Jul 22, 2013 at 4:04 PM, wren ng thornton <wren at freegeek.org> wrote:

> On 7/22/13 9:06 AM, Tom Ellis wrote:
> > On Mon, Jul 22, 2013 at 07:52:06PM +1200, Chris Wong wrote:
> >> A binding is memoized if, ignoring everything after the equals sign,
> >> it looks like a constant.
> >>
> >> In other words, these are memoized:
> > [...]
> >>      f = \x -> x + 1
> > [...]
> >> and these are not:
> >>
> >>      f x = x + 1
> >
> > In what sense is the former memoised?  I'm not aware of any difference
> > between these two definitions.
>
> Consider rather,
>
>     f1 = let y = blah blah in \x -> x + y
>
>     f2  x = let y = blah blah in x + y
>
> The former will memoize y and share it across all invocations of f1;
> whereas f2 will recompute y for each invocation.
>
> In principle, we could translate between these two forms (the f2 ==> f1
> direction requires detecting that y does not depend on x). However, in
> practice, the compiler has no way to decide which one is better since it
> involves a space/time tradeoff which: (a) requires the language to keep
> track of space and time costs, (b) would require whole-program analysis to
> determine the total space/time costs, and (c) requires the user's
> objective function to know how to weight the tradeoff ratio.
>
> --
> Live well,
> ~wren
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130722/4256e29d/attachment.htm>