From: ยทยทยทยท@pobox.com
Subject: Lambda-calculi of four built-in CL/Scheme evaluators
Date:
Message-ID: <7mb63c$70h$1@nnrp1.deja.com>
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*)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
OK> A macro-expander is also an evaluator in a Scheme/Lisp system; it works at
OK> compile-time. Interestingly, it supports a different order of evaluation. A
OK> macro-application is in no hurry to expand its arguments. Rather, the
OK> first, the leftmost macro is expanded first; the result is re-scanned, and
OK> if it contains any applications they are evaluated in turn. This "second
OK> scan" behavior seems characteristic of normal evaluators (pun intended). A
OK> macro-expander is not eager to reduce everything to a value: when presented
OK> with a form (X Y) where X is not a known macro, the expander leaves it
OK> alone. Just as a (normal) lambda-evaluator will. The result of an
OK> application may therefore be another application -- that's why the second
OK> pass is necessary.
Actually, isn't rescanning required until stability is reached?
OK> Reader-constructors and Sharpsign-Dot are also evaluators, only during
OK> read-time. They both help a reader to make sense of a particular
OK> sequence of characters and compute the corresponding (internal)
OK> Lisp/Scheme object. Sharpsign-Dot syntax is a familiar Common Lisp
OK> feature. Reader-constructors are a bit restricted version of them:
OK> read-time applications, which I'm trying to introduce into Scheme:
You know my mind on this topic, I believe read-time application or
evaluation is a Good Thing. I first saw this in Oaklisp. C'mon Oleg,
let's see the SRFI!
Thanks for this interesting treatment on the levels of interpretation.
Hearty food for thought.
OK> Sent via Deja.com http://www.deja.com/
OK> Share what you know. Learn what you don't.
This is problematic if learning is an eager evaluator, since the more you
learn, the more you realize how much you don't know. They gotta be talking
about applicative-order lambda learning. We shouldn't try to evaluate what we
don't know.
Regards, Andy