Path: utzoo!attcan!uunet!comp.vuw.ac.nz!brian
From: brian@comp.vuw.ac.nz (Brian Boutel)
Newsgroups: comp.lang.functional
Subject: Re: Purity and Laziness
Message-ID: <1990May28.020325.18011@comp.vuw.ac.nz>
Date: 28 May 90 02:03:25 GMT
References: <1535@sys.uea.ac.uk> <4170@castle.ed.ac.uk> <14531@dime.cs.umass.edu> <2535@skye.ed.ac.uk> <8691@cs.utexas.edu> <1990May25.024023.10616@comp.vuw.ac.nz>
Sender: news@comp.vuw.ac.nz (News Admin)
Reply-To: brian@comp.vuw.ac.nz (Brian Boutel)
Organization: Dept. of Comp. Sci., Victoria Uni. of Wellington, New Zealand.
Lines: 102

In article <1535@sys.uea.ac.uk>, jrk@sys.uea.ac.uk (Richard Kennaway) writes:
> In article <1990May25.024023.10616@comp.vuw.ac.nz>
brian@comp.vuw.ac.nz (Brian Boutel) writes:
> >In article <4170@castle.ed.ac.uk>, nick@lfcs.ed.ac.uk (Nick Rothwell)
writes:
[...]

> 
> It's not lazy evaluation which has this evaluation order, but the
> so-called lazy languages.  I regard this as a defect, precisely because
> it fails to be lazy.  An eager language, in contrast, is uniformly bad
> in this respect.  I find the absence of laziness in a functional
> language as irksome as the absence of recursion would be in imperative
> languages.
> 
> >Lazy evaluation *will* allow your reverse_cons example. All the
> >arguments of functions and constructors are passed unevaluated.
> ...
> > --brian
> 
> 
> > || It's not quite as simple as that.
> 
> (This is jrk speaking, from here on the ">" doesnt indicate quoting.
> The reason will eventually become clear.)
> 
> Although the reverse_cons example doesnt cause problems, other examples do.
> Consider the following definitions:
> 
> >    list  ::=  Nil  |  Cons num list
> 
> >    f Nil Nil           =   1 
> >    f Nil (Cons x y)    =   2
> >    f (Cons x y) z      =   3
> 
> >    g Nil Nil           =   1
> >    g (Cons x y) Nil    =   2
> >    g z (Cons x y)      =   3
> 
> >    loop                =   loop
> 
> [....]
> Notice that f and g are nearly the same function, but they take their
> arguments in the opposite order.  Now consider the two expressions
> 
> >   test1   =   f (Cons 1 Nil) loop
> 
> and
> 
> >   test2   =   g loop (Cons 1 Nil)
> 
> test1 evaluates to 3.  Therefore so should test2, right?  But it gives a
> non-terminating computation instead.
> [....]
> 
> The reason for this behaviour is that Miranda adopts a specific evaluation
> strategy for any program, which may be summed up as "left to right, top to
> bottom".
> 


 I think jrk has done a large issue switch here, but, taking up his point:

Every language of this class has to specify the semantics of
pattern/equation  matching, and do do in a way that will permit
efficient implementation. Otherwise, we will all continue to play with
functional languages and do our real work in C.

It would be highly desirable for Miranda and Haskell to be sufficiently
lazy to guarantee that they would never loop/die/bottom while matching
equations if there is just one equation which matches the actual
arguments. Unfortunately,  examples like

f x     false true  = 1
f true  x     false = 2
f false true  x     = 3

show that there is no sequential algorithm which will always work. For
example, 

f bot false true

 matches the first equation and no other, but if, in matching, the first
argument is matched first, this will bottom. Similarly for f true bot
false if the second argument is matched first, etc. Whatever you try to
match first, there is an argument value that will cause non-termination.

The only ways to avoid this are
a) to outlaw programs like the example, which seem to be otherwise
reasonable, or
b) to go to parallel evaluation, which is expensive to simulate on a
sequential machine.

So, if the goal is to define a useful language for real computation, and
to have lazy evaluation, it seems that some compromise is necessary.
--brian

Internet: brian@comp.vuw.ac.nz
Postal: Brian Boutel, Computer Science Dept, Victoria University of Wellington,
        PO Box 600, Wellington, New Zealand
Phone: +64 4 721000
Fax:   +64 4 712070