From www@deja.com Sun Jul 11 15:30:03 1999
Message-ID: <7mb63c$70h$1@nnrp1.deja.com>
From: oleg@pobox.com
Subject: Lambda-calculi of four built-in CL/Scheme evaluators
Date: Sun, 11 Jul 1999 22:33:16 GMT
Reply-To: oleg@pobox.com
Keywords: Lambda calculus, call-by-value, normal-order evaluation, macro-expansion, reader-macro, Lisp, Scheme
Newsgroups: comp.lang.functional,comp.lang.lisp,comp.lang.scheme
Organization: Deja.com - Share what you know. Learn what you don't.
Summary: Lambda-calculi of run-time, macro-, reader-parser and reader-lexer evaluators in a CL/Scheme system
X-Article-Creation-Date: Sun Jul 11 22:33:16 1999 GMT
X-Http-User-Agent: Mozilla/4.08 (Macintosh; I; PPC, Nav)
Sender: www@deja.com
Content-Length: 6109
Status: OR

This is a simple observation that run-time, macro-, reader-parser and
reader-lexer evaluators in a CL/Scheme system implement two different
versions of lambda-calculus, in an interesting alternating pattern.

At one end of the hierarchy is the regular, run-time
evaluator/interpreter. When presented with a function application, it
evaluates the arguments first and only then executes the body of the
function. That is, given a term with several applications, the
innermost one is evaluated first. This call-by-value lambda-calculus
is too eager, and thus can fail where the normal lambda-calculator
succeeds:

(define (bottom) (bottom))
(define (first . args) (and (pair? args) (car args)))
(let ((x (first 1 (bottom)))) x)  ==> fails to terminate

or, in e-lisp

(defun bottom () (bottom))
(defun first (&rest args) (and (consp args) (car args)))
(let ((x (first 1 (bottom)))) x) ==> Lisp nesting exceeds
max-lisp-eval-depth

Although the function 'first' actually uses the value of only first of
its arguments, the run-time interpreter evaluates the other
application's arguments anyway; one of them, (bottom) fails to yield
any result.

What distinguishes a Lisp/Scheme interpreter from an applicative-order
lambda evaluator is that the former always tries to reduce a term to a
value -- to anything but another application. Presented with an
application (X Y) where X is not a known abstraction (function), a
Lisp/Scheme interpreter fails.

A macro-expander is also an evaluator in a Scheme/Lisp system; it
works at compile-time. Interestingly, it supports a different order of
evaluation. A macro-application is in no hurry to expand its
arguments. Rather, the first, the leftmost macro is expanded first;
the result is re-scanned, and if it contains any applications they are
evaluated in turn. This "second scan" behavior seems characteristic of
normal evaluators (pun intended). A macro-expander is not eager to
reduce everything to a value: when presented with a form (X Y) where X
is not a known macro, the expander leaves it alone. Just as a (normal)
lambda-evaluator will. The result of an application may therefore be
another application -- that's why the second pass is necessary.

(define-macro (bottom) '(bottom))
(define-macro (one) 1)
(define-macro (first . args) (and (pair? args) (car args)))
(define (y) (let ((x (first (one) (bottom)))) x))
(pp y) ==> (lambda () (let ((x 1)) x))

This shows that the normal lambda-evaluator is able to reduce the form
that the call-by-value interpreter above has tripped upon.

Of course, if you write in your source code
        (define (z) (let ((x (first (bottom) (one)))) x))
your compilation will never finish.

Reader-constructors and Sharpsign-Dot are also evaluators, only during
read-time. They both help a reader to make sense of a particular
sequence of characters and compute the corresponding (internal)
Lisp/Scheme object. Sharpsign-Dot syntax is a familiar Common Lisp
feature. Reader-constructors are a bit restricted version of them:
read-time applications, which I'm trying to introduce into Scheme:
        http://pobox.com/~oleg/ftp/Scheme/read-time-apply.txt

Both of these evaluators implement the applicative-order,
call-by-value lambda-calculus. Both can suffer from their eagerness.

; Reader-ctors and the corresponding sharp-comma syntax
; see the link above for details
(include "read-apply.scm")
(define-reader-ctor 'bottom (letrec ((x (lambda () (x)))) x))
(define-reader-ctor 'one (lambda () 1))
(define-reader-ctor 'first (lambda args (and (pair? args) (car
args))))
(with-input-from-string "#,(first #,(one) 2)" read)
==> 1
(with-input-from-string "#,(first #,(one) #,(bottom))" read)
==> fails to terminate

Thus even reading of your code may never finish.

Again, just like run-time interpreters, read-time evaluators are
over-anxious: they will reduce every (read-time) application to a
value -- or die trying.

Finally, the Reader itself implements the normal lambda-calculus
again. Reading and interpretation of input stream may be considered as
evaluation of the following Lambda-calculus term (application):
        \c.(p c) #\1 #\2 #\{ #\3 ...
where the input stream is "12{3..." and p is a parser abstraction. The
first reduction of this term leads to an application (p #\1), which
will yield another abstraction, \c.(p1 c). Here p1 is a function with
knowledge that the parser p has just ate #\1 and wants more. The
original term becomes:
        \c.(p1 c) #\2 #\{ #\3 ...
or, after one more reduction,
        \c.(p12 c) #\{ #\3 ...
Function p12 applied to #\{ notices that this delimiting character
can't possibly be a part of the number representation, and yields:
        (consume 12 ((p #\{ ) #\3 ... ))
This term contains two applications: that of consume and the other of
p. A normal-order calculator will start with the former. If 'consume'
decided not to read more from the input stream, parsing of #\{
character will not be attempted. On the other hand, a call-by-value
(applicative-order) evaluator will try to completely parse the rest of
the stream first. If the character #\{ is invalid  -- or worse, if #\{
is a _bottom_ character, a bummer ensues. Fortunately, Lisp/Scheme
reader is a normal calculator, as the following examples show. This
evaluator also has a symptomatic 'second-scan' trait mentioned above
for normal evaluators, as a reader-macro function is allowed to
recursively call the Lisp reader as well as backtrack the current
reader stream.

; A bottom-character in CL
(set-macro-character #\{
  #'(lambda (stream char)
      (unread-char char)
      (values)))
(read-from-string "12{3") ==> (12 . 2)

; Make a #\{ a bottom character in Gambit

(##readtable-char-handler-set!
        (##current-readtable) #\{
                (lambda (re c)
                        (display "damn!\n")
                        (##read-datum re)))
(with-input-from-string "12{3" read) ==> 12

Please don't try to explicitly read the bottom character, as in
        (with-input-from-string "{3" read)

The examples above run within emacs, albeit in different buffers
(Inferior Gambit or *scratch*)