🚀 go-pugleaf

Article: 120 of comp.lang.functional
Path: edcastle!ukc!mcsun!sunic!sics.se!sics!bjornl
From: 
Newsgroups: comp.lang.functional
Message-ID: 
Date: 28 Jul 90 08:08:43 GMT
References: <BJORNL.90May29165842@pike.tds.kth.se> <14531@dime.cs.umass.edu> <2535@skye.ed.ac.uk> <8691@cs.utexas.edu> <4170@castle.ed.ac.uk> <3738@moondance.cs.uq.oz.au> <4289@castle.ed.ac.uk> <1990May29.234840.29162@comp.vuw.ac.nz>
Sender: news@sics.se
Organization: The Royal Inst. of Technology (KTH), Stockholm, Sweden.
Lines: 81
In-Reply-To: brian@comp.vuw.ac.nz's message of 29 May 90 23:48:40 GMT

bjornl@tds.kth.se (Bj|rn Lisper) sez in <BJORNL.90Jul28100843@tarpon.tds.kth.se>
/In article <1990May29.234840.29162@comp.vuw.ac.nz> brian@comp.vuw.ac.nz
\(Brian Boutel) writes:
/%> (Bjorn Lisper) wrote:
\%> Yes, this is exactly the "problem" with lazy functional languages as I see
/%> it: they rely on a serial evaluation order of arguments obtained from the
\%> currying of functions in order to get unary functions only, as in lambda
/%> calculus.  HOWEVER, this ordering is an imposed, arbitrary one. As I
\%> understand it this is inherent in the lambda calculus itself.
/
\%I think there is a misunderstanding here.
/%There is no need to *evaluate* the argument of a curried function before
\%you need its value. 
/
\Oops, I never claimed this. 

As far as I can see, the only kind of laziness that lambda-calculus is
open to is a curried function which says "Ignore the argument: the
answer is ...".  If such a function is produced the argument need not be
evaluated.

/%If I define f x y = E, I may be defining f to be a function which takes
\%an argument x and produces a function which takes an argument y etc.,
/%but all this implies is that I can use f 3, for example, as a function.
\%It says nothing about the order of evaluation of x and y.
/
\Doesn't it? Unless you know that f is strict, I'd say that whenever the
/value of f x y is needed, f x must be evaluated first and then, if needed,
\(f x) y. All this assuming that we want to follow the semantics given by
/lambda calculus (which imposes this order).
\
/(Please correct me if I'm wrong. I'm not a lambda calculus expert.)
\
/%In lazy evaluation, evaluation only occurs when a value is needed.
\%Ultimately, this is because it has to be output, but within a program,
/%evaluation is driven by pattern matching (a need to know which case
\%applies), or by a conditional ( a need to know which branch to take) or
/%by a strict primitive function like plus (needs the values of its
\%arguments before it can be applied). In all other cases, arguments are
/%passed to functions without prior evaluation.
/
\But in some sense, a conditional is a function.  To call some functions
/conditionals is a way to hide the basic "problem".  For instance, if(b,x,y)
\defined by
/
\b => if(b,x,y) = x
/not b => if(b,x,y) = y
\
/is a (non-strict) function in three arguments. Left-to-right lazy evaulation
\will give the ordinary "conditional" semantics. As I pointed out, there are
/cases where other evaluation orders terminate whereas this doesn't.

The kind of laziness I was talking about above applies particularly well
to if - you can use it to produce a version of if which only evaluates
the appropriate half.  

I can't see any way of implementing breadth-first evaluation of the kind
that would cope with

(((if forever) x) x)

using lambda-calculus notions.

Of course, what would solve all this would be a program that tests
whether an expression halts... :-)


-- 
\/ o\ Paul Crowley aipdc@uk.ac.ed.castle
/\__/ "Trust me, I know what I'm doing" - Sledge Hammer