Re: [Haskell-cafe] memoization
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
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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On 07/22/2013 03:41 PM, David Thomas wrote:
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...
The reason it is a big deal to me is it sometimes the more natural-looking (read, declarative) way of writing a function is only reasonably efficient if certain parts are memoized. Otherwise I end up having to pass around extra arguments or data structures representing the data I don't want to be recalculated.
On Mon, Jul 22, 2013 at 04:04:33PM -0700, wren ng thornton wrote:
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.
Indeed.
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.
This is called the full laziness transformation http://foldoc.org/full+laziness and indeed with optimization on GHC (sometimes) does it, even when not appropriate http://www.haskell.org/pipermail/haskell-cafe/2013-February/105201.html Tom
participants (4)
-
Christopher Howard -
David Thomas -
Tom Ellis -
wren ng thornton