[Prev][Next][Index][Thread]

Call-by-value (eager) vs. Call-by-name (lazy)

As John hints in his message, there are great values to call-by-name in 
functional languages if you wish to support lazy evaluation (e.g. Miranda
and Haskell).  As I recall (someone correct me if memory fails me here), 
the semantics of functional programs are the "same" for call-by-value and
call-by-name except that call-by-name is "a little more defined".  That is,
there are programs that terminate in call-by-name that would not terminate
in call-by-value.  As a result, anyone who has experienced programming in a 
lazy-evaluation functional language will be loathe to give up the extra 
expressibility gained therein.  (It can make it much easier to write efficient 
recursive programs.  A trivial example is the following from Miranda:
	fib n = (f 1 1)!n
			where f a b = a : f b (a+b)
Here "!n" means take the nth element of the list and a:l represents  
the list with head a and tail l.  Thus f 1 1 generates the infinite 
list of all fibonacci numbers and fib pulls off the nth element of
that list and returns it as the answer.  This has complexity O(n) compared to
the usual recursive definition whose complexity is O(fib n).  Clearly this
definition would not converge in an eager language.  A similar program
could be written in an eager language, it would just be a bit uglier.)
	Also on the practical side, the reduction machine architectures 
(see Turner's implementation of Miranda, described in Software - 
Practice and Experience, December '79, pp. 31-49) explicitly (and with no
extra effort) supports lazy evaluation (call-by-name).  While this currently 
seems to be slower than other techniques on single-processor architectures, 
there is some hope that it will be better on highly-parallel architectures.  
	There are of course more problems with imperative languages since
the semantics really does change in those circumstances (and I personally
find Jensen's trick just that - a trick!).  Surely John Reynolds has something
to say about all of this (he being a call-by-name fan).
	Kim Bruce


----- End Included Message -----