- This plaintext file was created by OCR from the original PDF file.
- Source: https://3e8.org/pub/scheme/doc/Quasiquotation%20in%20Lisp%20(Bawden).pdf
- Note from "1. Introduction": The backquote character (`) introduces a
quasiquotation, just as the ordinary quote character (
') introduces an ordinary quotation.
This appendix contains a correct S-expression quasiquotation expansion algorithm.
Assume that some more primitive Lisp parser has already read in the quasiquotation to be expanded, and has somehow tagged all the quasiquotation markup. This primitive parser has also supplied the following four functions:
tag-backquote? This predicate will be true of the result of reading a
backquote (') followed by an S-expression.
tag-comma? This predicate will be true of the result of reading a comma (,)
followed by an S-expression.
tag-comma-atsign? This predicate will be true of the result of reading a
comma-atsign (,@) followed by an S-expression.
tag-data This function should be applied to an object that satisfies one of
the previous three predicates. It will return the S-expression that followed
the quasiquotation markup.
The main entry point is the function qq-expand, which should be applied to an
expression that immediately followed a backquote character. (I.e., the
outermost backquote tag should be stripped off before qq-expand is called.)
(define (qq-expand x)
(cond ((tag-comma? x)
(tag-data x))
((tag-comma-atsign? x)
(error "Illegal"))
((tag-backquote? x)
(qq-expand (qq-expand (tag-data x))))
((pair? x)
`(append ,(qq-expand-list (car x))
,(qq-expand (cdr x))))
(else `',x)))Note that any embedded quasiquotations encountered by qq-expand are
recursively expanded, and the expansion is then processed as if it had been
encountered instead.
qq-expand-list is called to expand those parts of the quasiquotation that
occur inside a list, where it is legal to use splicing. It is very similar to
qq-expand, except that where qq-expand constructs code that returns a value,
qq-expand-list constructs code that returns a list containing that value.
(define (qq-expand-list x)
(cond ((tag-comma? x)
`(list ,(tag-data x)))
((tag-comma-atsign? x)
(tag-data x))
((tag-backquote? x)
(qq-expand-list (qq-expand (tag-data x))))
((pair? x)
`(list (append ,(qq-expand-list (car x))
,(qq-expand (cdr x)))))
(else `'(,x))))Code created by qq-expand and qq-expand-list performs all list construction
by using either append or list. It must never use cons. As explained in section
3.3, this is important in order to make nested quasiquotations containing
splicing work properly.
The code generated here is correct but inefficient. In a real Lisp implementation, some optimization would need to be done. A properly optimizing quasiquotation expander for Common Lisp can be found in [18, Appendix C].