<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
To be precise, this is call-by-name, and not call-by-need (perhaps that
is what Tony meant by WARNING?) In call-by-name, a shared delay() value
is evaluated every time its value is needed. <br>
In call-by-need, the same shared value is evaluated at most once: the
first time its value is needed, the shared delay() is updated with the
value so that all other usages benefit from that first evaluation.<br>
Would be nice to have some basic mechanism in Erlang so that
call-by-need could be implemented. It would have to be light weight,
updateable, and GC-able. Would probably a disaster to let loose on the
unsuspecting Erlang programming community, though (:-)<br>
<br>
The sieve example works nicely because it needs only call-by-name. In
other cases, complexity can easily become exponential when you'd
otherwise expect linear time, canonical example here is a tabulated
fibonacci:<br>
<br>
fiblist = [ fib(I) || I <- [0..] ] .<br>
fibt(N) -> nth(fiblist,N).<br>
fib(0) -> 1<br>
fib(1) -> 1<br>
fib(N) -> fibt(N-1)+fibt(N-2).<br>
<br>
-- Thomas<br>
<br>
<br>
Tony Rogvall wrote:
<blockquote cite="midD5746AEC-8B9A-4F75-B7EE-46E2520C562B@rogvall.com"
type="cite"><br>
<div>
<div>25 maj 2005 kl. 15.50 skrev Vlad Dumitrescu:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite"><span class="Apple-style-span"
style="border-collapse: separate; -x-border-x-spacing: 0px; -x-border-y-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-indent: 0px; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px;">
<div><font face="Arial" size="2"><span class="Apple-style-span"
style="font-family: Arial; font-size: 10px;">Hi all,</span></font></div>
<div> </div>
<div><font face="Arial" size="2"><span class="Apple-style-span"
style="font-family: Arial; font-size: 10px;">I just hit a problem
where I clearly see how simple it would be with lazy evaluation. But
since we don't have that, I wonder if anyone could point me to some
non-lazy algorithms.</span></font></div>
<div> </div>
</span></blockquote>
<div><br class="khtml-block-placeholder">
</div>
<div>By working a bit, lazy evaluation can be done... (WARNING do not
use in real apps ;-)</div>
<div><br class="khtml-block-placeholder">
</div>
<div>For example using the macros:</div>
<div><br class="khtml-block-placeholder">
</div>
<div>-define(delay(X), fun() -> (X) end).</div>
<div><br class="khtml-block-placeholder">
</div>
<div>-define(force(X), force((X))).</div>
<div><br class="khtml-block-placeholder">
</div>
<div>force(F) when function(F) -> F();</div>
<div>force(V) -> V.</div>
<div><br class="khtml-block-placeholder">
</div>
<div><br class="khtml-block-placeholder">
</div>
<div>You can define a lazy algorithms (can of course only be used in
this context)</div>
<div><br class="khtml-block-placeholder">
</div>
<div>zeros() -></div>
<div> [0 | ?delay(zeros())].</div>
<div><br class="khtml-block-placeholder">
</div>
<div>ones() -></div>
<div> [1 | ?delay(ones())].</div>
<div><br class="khtml-block-placeholder">
</div>
<div>twos() -></div>
<div> [2 | ?delay(ones())].</div>
<div><br class="khtml-block-placeholder">
</div>
<div>seq(Start) -></div>
<div> [Start | ?delay(seq(Start+1))].</div>
<div><br class="khtml-block-placeholder">
</div>
<div><br class="khtml-block-placeholder">
</div>
<div>sieve1(L, P) -></div>
<div> [N | T1] = ?force(L),</div>
<div> case N rem P of</div>
<div> 0 -> sieve1(T1,P);</div>
<div> _ -> sieve([N | ?delay(sieve1(T1,P))])</div>
<div> end.</div>
<div><br class="khtml-block-placeholder">
</div>
<div>sieve(L) -></div>
<div> [P | X] = ?force(L),</div>
<div> [P | ?delay(sieve1(X, P))].</div>
<div><br class="khtml-block-placeholder">
</div>
<div>primes() -></div>
<div> sieve(seq(2)).</div>
<div><br class="khtml-block-placeholder">
</div>
<div>Regards</div>
<div><br class="khtml-block-placeholder">
</div>
<div>/Tony</div>
<div><br class="khtml-block-placeholder">
</div>
<div><br class="khtml-block-placeholder">
</div>
</div>
<br>
</blockquote>
<br>
</body>
</html>