🚀 go-pugleaf

In article <BJORNL.90May29165842@pike.tds.kth.se>, bjornl@tds.kth.se
(Bj|rn Lisper) writes:
> In article <4289@castle.ed.ac.uk> aipdc@castle.ed.ac.uk (Paul D. Crowley)
> writes:
> %WARNING: Uninformed opinions ahead!
> 
> %I was under the impression that in a truly "pure" functional language
> %the problem doesn't arise because nothing has more than one argument. 
> %Things that look as if they should have more than one argument are dealt
> %with lambda-calculus style:
> 
> %2+3:  ((plus 2) 3)
> %(plus 2) means plus applied to two, and equals a function which adds two
> %to its argument.
> 
> %so ((plus 2) 3) = (plus2 3) = 5
> 
> %Under these circumstances you _expect_ order of arguments to be
> %significant, so it doesn't surprise you that you get different results
> %if you change it.
> 
> 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. So, there's a
> problem with the very theoretical foundations of functional programming!
> 
> My last comment is deliberately provocative. It would be interesting to hear
> any comments on it from people more involved in the field than me.
> 
> Bjorn Lisper

I think there is a misunderstanding here.
There is no need to *evaluate* the argument of a curried function before
you need its value. 

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.

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. (Actually, if you do
strictness analysis, it may be possible to determine at compile time
that a particular argument is always evaluated, and so, to improve
efficiency, it can safely be evaluated before being passed to the function.)

In plus x y, plus is strict in both its arguments, and they will both be
evaluated. The order in which this happens is unimportant. Real
implementations do not implement plus as taking one argument and
producing a new function, they implement it by using ordinary machine
arithmetic, where addition is an operation that adds two values. 

In f (complex expression), I can still pass this as a functional
argument to something without evaluating (complex expression) first.
With call-by-need, when (complex expression) is eventually evaluated, it
will be replaced by its value, and will not need to be evaluated again.

None of this invalidates the semantics of a non-strict language.

The issue of the order in which cases and arguments are checked in
pattern matching is different. If you are primarily interested in
reasoning about programs, you will want all equations in a function
definition to be disjoint, so at most one equation can match the actual
arguments. In practice this is inconvenient, as you often need a case
that matches "everything else" after some special values have been dealt
with. If you are interested in writing programs, you want semantics that
are easy to understand, and if you can't have a situation where equation
sequence and argument order make no difference, at least you will want
something obvious like top-to-bottom, left-to-right.

Even if this is not totally pure, lazy evaluation with these
restrictions is still very useful, and should not be rejected. 

--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