A simple and common example of the usefulness of lazy evaluation. 
Author Message
 A simple and common example of the usefulness of lazy evaluation.

I agree with the idea that a new concept in programming language
should help write some programs more easily.

I think that lazy evaluation does that in some simple and practical
cases. You don't need to mention infinite structure or infinite
stream for I/O to find some. Here is one example.

Suppose I want to compute f(x,y,z) where x, y, and z are some
values computed in some way, and where the time to compute
them might be large. So I write a program

               x = ...
               y = ...
               z = ...
           eval f(x,y,z)

Now, in this lazy form, the function f might compute x or y or z, or
it might not.

If you take a strict evaluation, x y and z gets evaluated before
the evaluation of f.

Now with this strict evaluation I have to worry about the cost
of computing x, y and z. For example, suppose that when x is negative
y will not be needed by f. I should now write

            x=...;
            z=...;
            If x<0 then f(x,anything,z)
                   else y=...;  f(x,y,z)

For strict evaluation the programmer has to worry about all non
needed computations at every point of the program. With lazy
evaluation that concerns disappear. ( Yes, a test on x is done in f.)

I think this is a common occurence in many computations. So,
lazy evaluation appears to be like automatic garbage collection.
It helps avoiding to worry about some details.

Now, the efficiency of implementing lazy evaluation is another story.

But, I think that strict evaluation remains more versatile. It is like
managing your own heap space, you do exactly what you want.

The interesting thing would be having the lazy mechanism, but also a
way to specify the order of evaluation when the programmer wants to
take care of it.

Mario Latendresse
Agent de recherche
Groupe CAO
Faculte d'amenagement
Universite de Montreal
Quebec
Canada



Mon, 02 Jan 1995 23:35:04 GMT  
 A simple and common example of the usefulness of lazy evaluation.

Quote:

>            x=...;
>            z=...;
>            If x<0 then f(x,anything,z)
>                   else y=...;  f(x,y,z)
>For strict evaluation the programmer has to worry about all non
>needed computations at every point of the program. With lazy
>evaluation that concerns disappear. ( Yes, a test on x is done in f.)

Notice your above arguement is simply one of efficiency.  Thus I can
turn a lazy arguement 'upside down' and solve this problem for strict
languages.    After all in just the same way that a compiler can
be made to find places where strict evaluation is equivalent and more
efficient, a compiler can be made to find places where lazy evaluation
is more efficient and use that.  

Thus the SEMANTICS of the language can be strict, but the programmer
need not worry about avoiding unnecessary computation because the
compiler does that for him.   (Of course in order to actually not
change the semantics, the compiler would have to guarentee that
skipped code does not diverge).

Actually in my own mind, I am not advocating strict or lazy evaluation
but only specifying very loose constraints on evaluation (since that
is all that is necessary for most programs).    Thus any program that
diverged on some legal order of evaluation but not on other order
would be undefined in the semantics.  (This way the compiler can
skip code whenever its value is not needed, or can evaluate eagerly
as possible if that is more efficient)

Vance



Tue, 03 Jan 1995 01:46:28 GMT  
 A simple and common example of the usefulness of lazy evaluation.

   I think that lazy evaluation does that in some simple and practical
   cases. You don't need to mention infinite structure or infinite
   stream for I/O to find some. Here is one example.

   Suppose I want to compute f(x,y,z) where x, y, and z are some
   values computed in some way, and where the time to compute
   them might be large. So I write a program [... argument in
   favor of lazy evaluation deleted...]

All true. However, it is not difficult to express lazy evaluation in a
mostly-eager language. You can either use LAMBDA directly, or your
language may provide syntactic sugar in the form of DELAY and FORCE.
Some eager languages even let you declare functions or individual
arguments to functions as being "lazy" and force the delayed values
automatically.

I find I need lazy evaluation relatively rarely. When I do, I usually
need it in the form of infinite streams (lazy lists). I would like to
see a language like SML support lazy lists syntactically, and maybe to
add some facilities for letting the user declare individual functions
as being lazy.

However, I don't like languages in which all evaluation is lazy. I
find it makes debugging and reasoning about programs much harder.
Apart from that, I have yet to see an efficient implementation of a
lazy language.

                                        Thomas.



Tue, 03 Jan 1995 08:39:10 GMT  
 A simple and common example of the usefulness of lazy evaluation.

[some sensible presentation of the interest of the concept of
lazyness, to manage complexity]

        At least, there is *one* honest attempt to demonstrate the
interest of the concept, and what it buys you. I appreciate the
comparison with garbage collection, and I think I now understand
better the interest of lazyness in the kind of situations you
describe, as a way to overcome complexity. Quite happy to learn that
there is at least *something* in it.

I'm still not really convinced however of the interest of lazy
languages as universal languages. Among the problems pointed out by
others are:

        1- It seems that in some situations the lack of control on the
effective order of evaluation may be a hindrance [because the order of
evaluation is not directly expressed in the text, and must be deduced
by a mental pre-evaluation of the program, which in a sense defeats
the purpose of a programming language].

        2- Another issues that has been raised is that of efficiency.
Despite the belief expressed by some that "Laziness is theoretically
more efficient even." (J. Farrel), I don't see how you can avoid
running "at the speed of the continental drift" as will from now on be
remembered as "Turner's confession", unless he denies vigorously
having said so.

Also, as I like discussions to be rooted in reality, I'd simply
restate the questions I've raised previously. There are computing
devices everywhere, doing lots of kinds of computations: numerical,
symbolic, decimal, logic, what-else... Since there seem to some vague
claims that Miranda (say) or Haskell could "become popular" as well as
Pascal or other languages, I suspect it should be possible to point
out *one* example taken from the real world where the use of such a
language would have been beneficial in *some* way (up to doing it
entirely differently, etc). Can some smart and fun person take the
challenge ?

        V. Delacour



Tue, 03 Jan 1995 02:02:19 GMT  
 A simple and common example of the usefulness of lazy evaluation.

Quote:
>    ....   (J. Farrel), I don't see how you can avoid
>running "at the speed of the continental drift" as will from now on be
>remembered as "Turner's confession", unless he denies vigorously
>having said so.

Before this story spreads any further, I  VIGOROUSLY  DENY  having  said
that Miranda (or any other recent) lazy functional language runs at "the
speed of continental drift".

It is a remark that I made twelve years ago about the THEN state of lazy
functional  language  implementation  (in relation to a language of mine
called KRC).  Matters have greatly improved in the  intervening  decade.
Miranda  today  runs three (decimal) orders of magnitude faster than KRC
did in 1980.

The  current  release  of  Miranda(tm)  is  interpreted,  and  primarily
designed  for  ease  of use - with a rapid edit/recompile cycle - rather
than efficient execution.  It is however perfectly  usable  (and  widely
used) for both teaching and software prototyping.

David Turner



Wed, 04 Jan 1995 21:41:52 GMT  
 A simple and common example of the usefulness of lazy evaluation.

Quote:
>       2- Another issues that has been raised is that of efficiency.
>   Despite the belief expressed by some that "Laziness is theoretically
>   more efficient even." (J. Farrel), I don't see how you can avoid
>   running "at the speed of the continental drift" as will from now on be
>   remembered as "Turner's confession", unless he denies vigorously
>   having said so.

It should be noted that the Miranda implementation is notoriously slow
and based on interpretive techniques. Indeed, even back in 1987, the
Chalmers LML implementation ran 100 times faster than Miranda on a
number of benchmarks (quicksort, 8 queens, that kind of thing)
[Augustsson's thesis]. So perhaps Miranda shouldn't be taken as a
representative example of such implementations. I would guess
that lazy languages are perhaps 10 times slower than imperative
ones on the average (feel free to correct me), with a smaller
factor on some benchmarks. (E.g., procedures that use
arithmetic are usually compiled well today, as I understand it.)
I would expect this factor to decrease with time, as the issues of
compilation are better understood (the basis of much of the work in
the area was laid in the mid-80:s, which isn't all that far-off).

As has been mentioned previously by Peyton Jones, there are good books
out on the subject of outrunning the continental drift.

Quote:
>       V. Delacour

                        Thomas

--
--------------------------------------------------------------------------



        "I can call procedures in the vasty kernel."
        "Why so can I, or so can any program. But will you
         return when you do call them?"
-----------------------------\\\\-----------------------------------------



Mon, 09 Jan 1995 23:54:34 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Lazy Evaluation... a simple example

2. Lazy evaluation in Common Lisp

3. Lazy evaluation in Common Lisp

4. lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

5. Lazy evaluation?

6. Monads and Lazy Evaluation

7. lazy evaluation, minimax, and alpha-beta pruning

8. eager/lazy evaluation

9. Lazy Evaluation and Parallel actions

10. Cycles in Lazy evaluation (was: Reference counting GC)

11. Benefits of lazy evaluation

12. a complexity result about lazy evaluation being better than eager

 

 
Powered by phpBB® Forum Software