Many real-world programs make very extensive use of records. After writing out a few sets of definitions to implement record types, however, Scheme programmers generally make an important discovery: Typing out these definitions is boring. They have a completely predictable form -- only the name of the type and the number, names, and mutabilities of the fields change from one kind of record to another -- and yet one has to sit down and type out a dozen or so procedures each time one wants to use a new kind of record. The process soon becomes tedious and error-prone.
The solution to this problem is metaprogramming: the creation of
programs that construct other programs. Metaprogramming automates some of
the tedious and error-prone parts of the programmer's job. Scheme is
particularly well suited to metaprogramming because of the fact that
definitions and commands in Scheme have the same form as data: They are
nothing but trees in which the leaves include such symbols as
lambda, if, and cons, together with
literal constants of various sorts.
For instance, if we wanted to build a datum that would look just like the Scheme definition
(define square
(lambda (n)
(* n n)))
we could do it simply by using the list procedure to collect
the right symbols in the right ways:
(list 'define 'square
(list 'lambda (list 'n)
(list '* 'n 'n)))
Evaluate the preceding expression to confirm that its value is a datum
that looks just like the definition of square.
Write a similar Scheme expression that, when evaluated, yields a datum that
looks just like the definition of the make-list-of-one
procedure on page 34 of the textbook.
It's not much more difficult to metaprogram a procedure that will take as arguments a symbol that tells the name of a record type and a list of symbols that tell the names of its fields, and returns a datum that looks just like a constructor procedure:
(define constructor-maker
(lambda (record-name field-names)
(let ((constructor-name
(string->symbol (string-append "make-"
(symbol->string record-name)))))
(list 'define constructor-name
(list 'lambda field-names
(cons 'vector
(cons (list 'quote record-name) field-names)))))))
Here's what happens when you invoke it:
> (constructor-maker 'star '(name right-ascension declination
visual-magnitude spectral-type))
(define make-star
(lambda (name right-ascension declination visual-magnitude spectral-type)
(vector 'star name right-ascension declination visual-magnitude
spectral-type)))
If we write this datum-that-looks-like-a-definition to a file and subsequently load that file as if it contained a Scheme program, neither Chez Scheme nor any human reader can tell that it is ``only a datum''! It is, in fact, indistinguishable from a definition that a human programmer might have written and placed in that same file.
We can similarly metaprogram all the other components of the implementation
of a record type. We can even collect them into a procedure -- let's call
it generate-record-definition-file -- that takes the
record and field names as arguments and writes the entire collection of
procedure definitions (the constructor, the selectors, the mutators, and
the type predicate) into an appropriately named file. If we can write this
metaprogram once, we won't have to write our own definitions
for record types ever again. Instead, we'll just do something like this:
> (generate-record-definition-file 'star 'name 'right-ascension
'declination 'visual-magnitude
'spectral-type)
> (load "star-definition.ss")
> (define Stella
(make-star "Alpha Centauri 1" '(14 39 26) '(-60 49 25) -0.01 'G2))
Scheme provides another kind of construction that makes metaprogramming
easier: the quasiquotation. Ordinary quotation converts a symbol,
a list, or a vector into a Scheme datum by setting up a barrier to
evaluation -- the single quotation mark tells the Scheme expression
evaluator not to go to work on the subexpression to which it is prefixed.
The quasiquotation mark (a backquote, ` -- you'll find this
character in the upper left-hand corner of the keyboard) also converts a
symbol, a list, or a vector into a datum, but its message to the Scheme
expression evaluator is more subtle: It prohibits the evaluation of any
subexpression except one that is immediately preceded by a comma
or by the two-character prefix ,@ (``comma-at''). For a
subexpression that is preceded by a comma or comma-at, evaluation
is switched back on again, and the result of the evaluation is inserted
into the datum at the point at which the subexpression occurs.
Here are some simple examples of quasiquotations:
> `(The sum of 7 and 5 is ,(+ 7 5)) (the sum of 7 and 5 is 12)
The quasiquote marks the list that it is attached to as a datum, turning
off evaluation; the comma turns evaluation back on again for the
subexpression (+ 7 5).
> (let ((sum (+ 7 5)))
`(The sum of 7 and 5 is ,sum))
(the sum of 7 and 5 is 12)
> (let ((name (string #\B #\o #\b)))
`(My name is ,name))
(my name is "Bob")
> (reverse `(a b ,(reverse '(c d)) e))
(e (d c) b a)
If you change the quasiquote in the last example to a quote, you naturally
get no evaluation within the argument to reverse:
> (reverse '(a b ,(reverse '(c d)) e)) (e ,(reverse '(c d)) b a)
The difference between a comma that switches evaluation back on and the comma-at switch is that the value that results from a comma-at evaluation, which must be a list, is spliced into the context in which it occurs, instead of just being inserted as a list element:
> (define full-name '(Robert Calvin Makkai)) > `(My full name is ,full-name and I like it) (my full name is (robert calvin makkai) and i like it) > `(My full name is ,@full-name and I like it) (my full name is robert calvin makkai and i like it)
As a more realistic example, here is how to write the
constructor-maker procedure with the help of quasiquotation:
(define constructor-maker
(lambda (record-name field-names)
(let ((constructor-name
(string->symbol (string-append "make-"
(symbol->string record-name)))))
`(define ,constructor-name
(lambda ,field-names
(vector ',record-name ,@field-names))))))
The quasiquotation acts as a template; one fills in the template with the
symbols and lists that are passed to constructor-maker as
parameters or computed in the binding specifications of the
let-expression. A comma marks a position in the template that
is to be filled in with the value of one of these identifiers; a comma-at
marks a position at which a list that is associated with one of those
identifiers is to be spliced in.
Write a similar procedure type-tester-maker that takes two
arguments -- a symbol giving the name of the record type and a list of
symbols giving the name of the fields -- and returns a datum that looks
just like a type predicate for that record type.
The file /home/stone/courses/scheme/html/record-builder.ss
contains a definition of the generate-record-definition-file
procedure.
Load this file into Chez Scheme and call the
generate-record-definition-file procedure with appropriate
arguments to construct a catalog-card record type, with five
fields: author, title, imprint,
call-number, and checked-out?.
Inspect the file that generate-record-definition-file created
in the preceding exercise; it will be called
catalog-card-definition.ss. Edit this file to remove the
mutators for all of the fields except checked-out?.
Load the catalog-card-definition.ss file and use the constructor procedure defined in it to create a catalog card for our textbook. (In Burling Library, its call number is "QA76.6.S686 1989" and it is currently checked out.)
A projection function is a procedure that returns one of its arguments and ignores all of the others. Here, for instance, is the definition of a projection function that returns the next-to-last of its seven arguments:
(define position-5-of-7
(lambda (p0 p1 p2 p3 p4 p5 p6)
p5))
Write a metaprocedure projection-function-maker that takes two
arguments -- a positive integer argument-count and a natural
number position that must be less than
argument-count -- and returns a datum that looks just like the
definition of a projection function that has argument-count
arguments and returns the one in the specified (zero-based) position.
> (projection-function 7 5)
(define position-5-of-7
(lambda (p0 p1 p2 p3 p4 p5 p6)
p5))
Puzzle (for entertainment only): Write a Scheme procedure call that,
when evaluated, yields a datum that looks just like itself. Hint:
Use a lambda-expression to identify the procedure that will be
invoked.
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1998/metaprogramming.html
created April 29, 1997
last revised June 21, 1998