[erlang-questions] currying and lazy evaluation questions

John Hughes <>
Wed Sep 24 07:05:09 CEST 2008


There's another problem with this approach: it involves copying a function 
between processes (in the spawn_link in delay below). As has been pointed 
out several times recently, this copying losing all sharing in the 
representation. Function closures can contain a LOT of sharing in their 
representations, and this can really blow up memory use--you can send a 
function from a process with a heap of a few kilobytes, and find you're 
failing to allocate half a gigabyte or so in the receiver. If one tried to 
model lazy evaluation this way, and made much use of it, then I would expect 
this to happen quickly. (It certainly happened quickly to me!)

John

>
> One aspect of many lazy functional implementations is that delayed
> computations are memoized when forced - the evaluated result is stored,
> so that in
>
>    Promise = ?DELAY(expensive_computation(X, Y, Z)),
>    Value1 = ?FORCE(Promise),
>    Value2 = ?FORCE(Promise)
>
> the expensive computation is only evaluated once.  This can have a
> dramatic effect on the efficiency of lazy functional data structures,
> as shown in Okasaki.
>
> Sadly, there's no trick for getting this behavior in purely functional
> code, since it involves a side effect.  However, one can throw processes
> at the problem:
>
>    delay(Thunk) ->
>        spawn_link(fun() -> lazy_wait(Thunk) end).
>
>    force(Lazy) ->
>        Lazy ! {self(), force},
>        receive
>            {Lazy, Result} -> Result
>        end.
>
>    lazy_wait(Thunk) ->
>        receive
>            {Proc, force} ->
>                Result = Thunk(),
>                Proc ! {self(), Result},
>                memo_loop(Result)
>        end.
>
>    memo_loop(Result) ->
>        receive
>            {Proc, force} ->
>                Proc ! {self(), Result},
>                memo_loop(Result)
>        end.
>
> I don't think that processes get garbage collected, so there's a
> nontrivial problem of reclaiming resources.  This trick still might
> be useful in some limitied settings, through.
>
> Jim
>
> 




More information about the erlang-questions mailing list