CSSE 304 Day 13
Your questions on Exam 1? Lexical Address examples Computation in the lambda Calculus \reverse and reverse! Syntactic extensions
1
Interlude
lexical address solution
(lexical-address ‘((lambda (x y)
(((lambda (z) (lambda (w y)
(+ x z w y))) (list w x y z))
(+ x y z)))
(y z)))
((lambda (x y) (((lambda (z)
(lambda (w y)
((: free +) (: 2 0) (: 1 0) (: 0 0) (: 0 1))))
((: free list) (: free w) (: 0 0) (: 0 1) (: free z))) ((: free +) (: 0 0) (: 0 1) (: free z))))
((: free y) (: free z)))
2
lexical address solution 2
(lexical-address ‘(let ([a 3] [b 4])
(let ([a (+ b 2)] [c a]) (+abc))))
(let ((a 3) (b 4))
(let ((a ((: free +) (: 0 1) 2))
(c (: 0 0)))
((: free +) (: 0 0) (: 1 1) (: 0 1))))
Introduction to define‐syntax
GROWING THE SCHEME LANGUAGE
3
Syntactic extension
• A mechanism for adding new syntax to a programming language.
The “macro” of “macro-assembler”
• A “macro” is a “super-instruction”, a.k.a pseudo-instruction.
• An instruction that the assembler translates into a sequence of machine instructions.
• macros are an example of syntactic extension.
Vax-MACRO
Example in MIPS: la $t1
lui $t1, ori $t1, $t1,
4
Syntactic extension in C
#define square(x) ((x) * (x))
#define max(x, y) (((x)>(y)) ? (x) : (y))
#include
int n = 5, m = 7; double y = 6.17;
printf(“%d\n”, square(m + 7*n/3)); printf(“%lf %d\n”, max(n,y), max(m,n));
}
Note that #define does not define procedures; it defines syntactic substitutions (macros). This can be seen by running the C pre-processor:
output from CPP
#define square(x) ((x) * (x))
#define max(x, y) (((x)>(y)) ? (x) : (y))
printf(“%d\n”, square(m + 7*n/3)); printf(“%lf %d\n”, max(n,y), max(m,n));
gets replaced by
(without the extra line breaks that I added for readability)
printf(“%d\n”, (( m + 7*n/3 ) *
( m + 7*n/3 )) );
printf(“%lf %d\n”, ((( n ) > ( y )) ? (n):( y)),
((( m ) > ( n )) ? ( m ) : ( n )) );
5
Syntactic extension in Scheme
• lambda is a core syntactic form; let is not.
– Expressions involving let may be syntactically transformed into applications of lambda- expressions (as you did in the let->application HW procedure).
• There are many syntactic forms in Scheme
– most are not core forms, but are transformed into core forms before execution.
• Not everyone
agrees on which forms are core forms.
• Here is Kent
Dybvig’s list (TSPL section 3.1):
Scheme core forms
6
The syntactic expansion process
• expansion happens before interpretation.
• The syntax expander is called on each top- level form.
– If the form is a syntactic extension, it is expanded, and the expander is called again on the new form.
– If it is a core form, the expander is called on any subforms (e.g. the body of a lambda form).
– This continues until the form consists only of core forms. Then the form is interpreted.
define-syntax and syntax-rules
General form:
(define-syntax
{ [pattern template] }+ ))
What gets expanded
How to expand it
7
define-syntax and syntax-rules
my-let is equivalent to (unnamed) let
pattern (define-syntax my-let (syntax-rules () keyword list is empty
[(_ ((x v) …) e1 e2 …) ((lambda (x …) e1 e2 …)
assumed to be the name of the form, no matter what you put here
template
v …)]))
replace my-let expression with an application of a lambda expression
Live coding time
• my-let
• my-if
• ++
• ++-post
• my-and
• for loop (a couple of versions)
8