It seems that lisp could get by with less need of macros, and maybe
only one special form (you need something for conditional evaluation,
but I can't think of anything else), if you use lazy evaluation. My
understanding is that the lambda calculus is lazy evaluative, too.
Why then is lisp strict evaluative? Strict is by definition a special
case of lazy, so it would seem that to go strict is to pass up on some
power. Is it implemenation? Just history? Or something else
entirely?
On Thu, Aug 05, 2004 at 04:15:04PM -0700, matt knox wrote:
> It seems that lisp could get by with less need of macros, and maybe
> only one special form (you need something for conditional evaluation,
> but I can't think of anything else), if you use lazy evaluation. My
> understanding is that the lambda calculus is lazy evaluative, too.
> Why then is lisp strict evaluative? Strict is by definition a special
> case of lazy, so it would seem that to go strict is to pass up on some
> power. Is it implemenation? Just history? Or something else
> entirely?
You seem to be confused on a number of issues. First, you don't need a
special form for conditional evaluation; the pure lambda-calculus has no
such thing. Secondly, you are confusing Lisp with a functional
language.
Lisp is not a functional language (only) [1].
Normal-order reduction in the presence of side-effects is...interesting,
to say the least. For an imperative language (which Lisp is also),
applicative-order reduction seems to be the easiest to understand.
Consider the following expressions:
(defvar *a* 1)
(defun foo (a b) a)
(foo 1 (setf *a* 2))
*a* ; ==> ?
In Common Lisp, the last expression will evaluate to 2, because it
follows a strict left-to-right call-by-value model. If somehow the
model was changed to a lazy one, then the value would remain 1, because
the second argument to the function FOO is never used.
Third, how can you say that applicative-order is a special case of
normal-order reduction? Perhaps if you look at it theoretically. If
you look at the implementation, you'll find that call-by-need is more
difficult because it requires the creation of `thunks' to delay
evaluation and memoization, or graph reduction. (I am, of course,
assuming a compiler).
[1] Some of Lisp was indeed originally inspired by Church's paper on the
lambda calculus, but the original implementation got it wrong. Most
Lisp code, especially early code, looks nothing like code in a
functional language. It wasn't until Scheme that the lambda-calculus
was properly implemented, and Common Lisp derives lexical closures from
Scheme, mainly.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
> Consider the following expressions:
>
> (defvar *a* 1)
> (defun foo (a b) a)
> (foo 1 (setf *a* 2))
> *a* ; ==> ?
>
> In Common Lisp, the last expression will evaluate to 2, because it
> follows a strict left-to-right call-by-value model. If somehow the
> model was changed to a lazy one, then the value would remain 1, because
> the second argument to the function FOO is never used.
I think you can apply lazy evaluation to Common Lisp; it just becomes
complex to track all dependencies. In this case, for example, the
evaluation of *a* would notice that a thunk affecting the value of *a*
has been queued up and therefore should be executed first.
> Common Lisp derives lexical closures from Scheme, mainly.
Lexical closures came out as discussion of the FUNARG problem around
1968-1970, cf. [1]. You cannot attribute them to Scheme, which came
into existence only years later, in 1977.
Bruno
[1] Joel Moses, The Function of FUNCTION in LISP, or Why the FUNARG Problem
Should be Called the Environment Problem, Massachusetts Institute of
Technology, Cambridge, MA, 1970
> You seem to be confused on a number of issues. First, you don't need a
> special form for conditional evaluation; the pure lambda-calculus has no
> such thing. Secondly, you are confusing Lisp with a functional
> language.
My understanding is that "special forms" are things that have to be
implemented as distinct cases in eval. Quote, let, if, etc. cannot be
defined in terms of normal lisp functions because they need to get
their arguments in a different way than usual. Everything else can
just be a general application of function to arguments, right? With
lazy eval, you could, it would seem, evaluate the arguments or not, at
your discretion. I cannot think of a way to not have something like
'if' as a special case, because you need some way to express "do
this, or maybe not, depending on ...", but once you have that,
everything else can be expressed in terms of normal functions and if.
> Lisp is not a functional language (only) [1].
>
> Normal-order reduction in the presence of side-effects is...interesting,
> to say the least. For an imperative language (which Lisp is also),
> applicative-order reduction seems to be the easiest to understand.
> Consider the following expressions:
>
> (defvar *a* 1)
> (defun foo (a b) a)
> (foo 1 (setf *a* 2))
> *a* ; ==> ?
>
> In Common Lisp, the last expression will evaluate to 2, because it
> follows a strict left-to-right call-by-value model. If somehow the
> model was changed to a lazy one, then the value would remain 1, because
> the second argument to the function FOO is never used.
OK, I am happy to grant that you can construct a case in which having
lazy evaluation leads to counterintuitive results, but couldn't the
same argument be applied to continuations, lexical closures, or
macros? It would seem that a clever implementor would provide some
syntax for guaranteeing that things get evaluated, or maybe even say
that they got strictly evaluated by default, but could be made lazy
somehow.
> Third, how can you say that applicative-order is a special case of
> normal-order reduction? Perhaps if you look at it theoretically. If
> you look at the implementation, you'll find that call-by-need is more
> difficult because it requires the creation of `thunks' to delay
> evaluation and memoization, or graph reduction. (I am, of course,
> assuming a compiler).
Assume for a moment that you have lazy eval and a syntax for saying
'evaluate this strictly anyway' then strict eval is indeed a
degenerate case of lazy eval. Even if you don't have the syntax, you
can fake it by using variables whenever you want them evaluated, but
that is clearly burdensome and dumb.
> [1] Some of Lisp was indeed originally inspired by Church's paper on the
> lambda calculus, but the original implementation got it wrong. Most
> Lisp code, especially early code, looks nothing like code in a
> functional language. It wasn't until Scheme that the lambda-calculus
> was properly implemented, and Common Lisp derives lexical closures from
> Scheme, mainly.
I read somewhere that scheme does optional lazy eval, too. Is that correct?
matt knox wrote:
> It seems that lisp could get by with less need of macros, and maybe
> only one special form (you need something for conditional evaluation,
> but I can't think of anything else), if you use lazy evaluation. My
> understanding is that the lambda calculus is lazy evaluative, too.
> Why then is lisp strict evaluative? Strict is by definition a special
> case of lazy, so it would seem that to go strict is to pass up on some
> power. Is it implemenation? Just history? Or something else
> entirely?
Re conditional evaluation, you don't even need a special form for that
if you have lazy evaluation. In pure LC (using Lisp syntax here), you
can define true and false as functions:
(defun true (x y) x)
(defun false (x y) y)
And then define if as a function:
(defun if (condition x y)
(funcall condition x y))
Even in a hypothetical lazy Lisp, macros would still be useful for the
automatic generation of code, although they wouldn't be needed to
control evaluation time and side effects.
Alex