sophisticated, they have moved closer to the semantic analysis
phase of the compiler. LISP systems achieved respect for target
language syntax by doing macro transformations on parse trees
rather than source text. Scheme’s system takes things a step
further by respecting lexical scoping and name bindings. In
addition, the standard high-level part of Scheme’s macro system
specifies syntactic rewrite rules in a pattern directed fashon
which includes error checks.
To contrast Scheme’s macro system with those of older LISPs, here
is a brief historical view of the LET macro. LET is a construct
for introducing new name bindings. It has the form:
(let ( ( ) … )
… )
The semantics of LET is to evaluate the expressions in an
environment extended by the names which have initial
values obtained by evaluating the expressions . An
example is: (let ( (a 1) (b 2) ) (+ a b) ), which binds the value 1 to
a, 2 to b and then evaluates the expression (+ a b). LET is
syntactic sugar for lambda binding:
( (lambda ( …) …) … )
So (let ( (a 1) (b 2) ) (+ a b) ) rewrites to
( (lambda (a b) (+ a b)) 1 2 )
Early LISP systems operated directly on the list structures of
the parsed source expression using low-level operations:
(macro LET
(lambda (form)
(cons (cons ‘lambda
(cons (map car (cadr form))
(cddr form)))
(map cadr (cadr form)))))
Later, arguments and “backquotes” were added, making things much
more readable, but without error checking. The backquote (`)
indicates an “almost constant” list expression, where comma (,)
or comma-splice (,@) are used to force evaluation of a
subexpression. The comma replaces the evaluated expression
directly, where comma-splice splices it into the list.
So `(lambda ,(cdr (cons ‘a ‘b)) ,@(cdr (cons ‘a ‘b)))
becomes (lambda (b) b) .
Here is LET with argument binding and backquote:
(define-syntax (LET def-list . expressions)
`((lambda ,(map car def-list) ,@expressions)
,@(map cadr def-list)))
And here is the Scheme version using pattern maching with error
checks:
(define-syntax LET
(syntax-rules ()
( (let ( ( ) …) …) ; before
; rewrites to
((lambda ( …) …) …) ; after
) )
)
This next example demonstrates both macro names shadowing local
variables and locals shadowing macros. The outer binding of CAR
is to a function which returns the first element of a list.
;; from “Macros That Work”
(let-syntax ( (first (syntax-rules () ((first ?x) (car ?x))))
(second (syntax-rules () ((second ?x) (car (cdr ?x)))))
)
(let ( (car “Packard”) )
(let-syntax ( (classic (syntax-rules () ((classic) car))) )
(let ( (car “Matchbox”) )
(let-syntax ( (affordable (syntax-rules () ((affordable) car))) )
(let ( (cars (list (classic) (affordable))) )
(list (second cars) (first cars)) ; result
) ) ) ) ) )
The above evaluates to: (”Matchbox” “Packard”)
PRACTICUM: extending core Scheme to standard scheme
Scheme can remain such a small language because one can extend
the syntax of the language without making the compiler more
complex. This allows the compiler to know a great deal about the
few (7) basic forms. Most compiler optimizations then fall out
as general rather than special cases.
The following syntax definitions from the current Scheme standard
are directly (and simply) implemented.
Form: (or …)
Example: (or (= divisor 0) (/ number divisor))
Semantics: OR evaluates the expressions from left to right. The
value of the first true (not #f) expression is returned. Any
remaining expressions are not evalusted.
(define-syntax OR
(syntax-rules ()
((or) ;=*
#f
)
((or ) ;=*
)
((or …) ;=*
(let ( (temp ) )
(if temp temp (or …))
) )
) )
Form: (and …)
Example: (and (input-port? p) (read p))
Semantics: AND evaluates the expressions from left to right.
The value of the first false expression is returned. Any
remaining expressions are not evalusted.
(define-syntax AND
(syntax-rules ()
((and) ;=*
#t
)
((and ) ;=*
)
((and …) ;=*
(if (and …) #f)
))
) )
Forms: (let ( ( ) …) …)
(let ( ( ) …) …)
Examples:
(define A 37)
(let ( (a 2) (b (+ a 5)) ) (* a b)) ;=* 84
(let loop ( (count N) (accum 0) )
(if (* n 2)
accum
(loop (- count 1) (* count accum))
Semantics: LET evaluates the s in the enclosing environment
in some unspecified order and then extends the environment by
binding the values to the s and evaluates the expressions
from left to right, returning the value of the last expression as
the value of the LET. LET can be thought of as a “parallel
assignment”. Note that the value of B in the first example
depends on the value of A in the outer environment.
The second form is known as NAMED LET and allows recursion within
the let form. For the example above, the call to LOOP acts as a
goto which rebinds the s to fresh values and “starts over
at the top of the loop”. Note that this is a functional
construct: there are no unbound variables introduced and no
assignment is used.
(define-syntax LET
(syntax-rules ()
((let ( ( ) …) …)
;=*
((lambda ( …) …) …)
)
((let ( ( ) …) …)
;=*
((letrec ( (
(lambda ( …) …))
)
)
…)
)
) )
Form: (LET* ( ( ) …) …)
Example:
(define A 37)
(let ( (a 2) (b (+ a 5)) ) (* a b)) ;=* 14
Semantics: Like un-named LET except that the expressions
are evaluated sequentially and each “sees” the value of the
previous name bindings.
(define-syntax LET*
(syntax-rules ()
((let* () …) ;=*
(let () …)
)
((let* ( (var1* ) ( ) … )
…)
;=*
(let ( ( ) )
(let* ( ( ) … )
…))
)
) )
Form: (LETREC ( ( ) …) …)
Example:
(letrec ( (EVEN?
(lambda (n)
(if (zero? n) #t (odd? (sub1 n)))))
(ODD?
(lambda (n)
(if (zero? n) #f (even? (sub1 n)))))
)
(even? 14)) ;;=* #t
Semantics: Mutually recursive form of let. All name bindings are
visible to all s. Because the order of evaluation of the
s is unspecified, it must be possible to evaluate each init
without refering to the *value* of any . Note that if the
values are all lambda expressions, this condition is always
satisfied.
(define-syntax LETREC
(syntax-rules ()
((letrec ( ( ) … )
…)
;=*
(let ( ( #f) … )
(set! ) …
…)
))
) )
Forms: (cond ( …) … )
(cond ( …) … (else …))
Examples: (cond ((* x 0) ‘negative)
((* x 0) ‘positive)
(else ‘neither))
(cond ((assq key alist) =* cdr)
(else search-failure-value))
Semantics: Each expression is evaluated in turn. The
first which evaluates to true causes the s to be
evaluated. The value of the last is returned in this
case, or the value of if there are no s. If no
is true, the s of the else clause are evaluated and
the value of the last is the value of the COND
expression. If not is true and there is no else clause,
the result is unspecified. If a is true and followed by
‘=* then the following must evaluate to a procedure of one
argument and the procedure is called with the value of the
expression as an argument.
(define-syntax COND
(syntax-rules ( else =* ) ;; ‘else and ‘=* must match exactly
((cond) ;=*
#f
)
((cond (else …))
(begin …)
)
((cond ( =* ) …)
;=*
(let ( (result ) )
(if result
( result)
(cond …))
))
((cond () …)
(or (cond …))
)
((cond ( …) …)
(if (begin …) (cond …))
)
) )
Form: (case (( …) …) …
(else …))
Example: (case (peak-char (current-input-port))
((# #\?) (print-help-text))
((#\space #\newline) (keep-looking))
(else (read-command)))
Semantics: The expression is evaluated and compared in turn
to each . If it is equivalent (eqv?), then the s of
the first clause containing the datum are evaluated and the value
of the last one is returned as the value of the CASE expression.
If no match is found, then the else expression(s) are evaluated
and the last value returned, otherwise the value of the CASE is
unspecified.
(define-syntax CASE
(syntax-rules ( else )
((case )
)
((case (else …))
(begin …)
)
((case (( …) …) …)
;=*
(let ( (key ) )
(if (memv key ‘( …))
(begin …)
(case key …))
))
) )
PROBLEMS WHICH REMAIN: