Quasiquotation

QUASIQUOTE is an extension of the QUOTE special form which is convenient for writing macros.

For symbols and other simple data, QUASIQUOTE behaves like QUOTE, returning the datum unevaluated. Lists are also return without being evaluated, with two exceptions. If an element of the list (or a sub-list) is of the form (UNQUOTE expr), then expr is evaluated and the result inserted into the list in place. (UNQUOTE-SPLICING expr) is similar, but the result of evaluating expr must be a list, the items of which are spliced into the parent list.

Example

(QUASIQUOTE (+ 1 (UNQUOTE (+ 2 3))))

evaluates to

(+ 1 5)

If we define L to be the list (3 4 5) then

(QUASIQUOTE (1 2 (UNQUOTE-SPLICING L)))

evaluates to

(1 2 3 4 5)

Shorthand syntax

Just like QUOTE, we will define the following abbreviations.

Rewriting the examples above with this syntax gives

`(+ 1 ,(+ 2 3))

and

`(1 2 ,@L)

Implementation

We extend the lexer to understand the additional special tokens.

// lex extracts the next token from the input after skipping
// comments and leading whitespace. on end of input, it
// returns nil for both the token and the remainder.
func lex(input []byte) (token []byte, remainder []byte) {
    // skip whitespace
    input = skipws(input)

    // check for end of input
    if len(input) == 0 {
        return nil, nil
    }

    // check for prefix characters
    if bytes.IndexByte(prefix, input[0]) >= 0 {
        token, remainder = input[:1], input[1:]
        return token, remainder
    } else if input[0] == ',' {
        if len(input) > 1 && input[1] == '@' {
            token, remainder = input[:2], input[2:]
        } else {
            token, remainder = input[:1], input[1:]
        }
        return token, remainder
    }

    // if we get here, the token is a symbol.
    // collect and return all the characters up to the first delimiter.
    token, remainder = runto(input, delimiters)
    return token, remainder
}

read_expr must expand the abbreviations in the same way as QUOTE

// read_expr reads the next expression from the input. an expression is
// either an atom or a list of expressions. returns the expression along
// with the remainder of the input and any errors.
// returns NIL and Error_EndOfInput on end of input. the caller must
// decide how to handle it.
// todo: result is not always updated by read. does that lead to bugs later?
func read_expr(input []byte, result *Atom) (remainder []byte, err error) {
    .
    .
    .
    switch token[0] {
    .
    .
    .
    case '`':
        sym := []byte("QUASIQUOTE")
        *result = cons(make_sym(sym), cons(_nil, _nil))
        // set car(cdr(result))
        return read_expr(rest, &result.value.pair.cdr.value.pair.car)
    case ',':
        sym := []byte("UNQUOTE")
        if len(token) > 1 && token[1] == '@' {
            sym = []byte("UNQUOTE-SPLICING")
        }
        *result = cons(make_sym(sym), cons(_nil, _nil))
        // set car(cdr(result))
        return read_expr(rest, &result.value.pair.cdr.value.pair.car)
    }
    err = read_atom(token, result)
    return rest, err
}

The QUASIQUOTE operator itself may be defined as a macro. First we need a few helper functions.

(define (append a b) (foldr cons b a))

(define (caar x) (car (car x)))

(define (cadr x) (car (cdr x)))

(append a b) concatenates the lists a and b.

And now the macro itself:

(defmacro (quasiquote x)
  (if (pair? x)
      (if (eq? (car x) 'unquote)
          (cadr x)
          (if (eq? (if (pair? (car x)) (caar x) nil) 'unquote-splicing)
              (list 'append
                    (cadr (car x))
                    (list 'quasiquote (cdr x)))
              (list 'cons
                    (list 'quasiquote (car x))
                    (list 'quasiquote (cdr x)))))
      (list 'quote x)))

(Note: the definition above includes a fix from [building-lisp-zig](https://github.com/jpaquim/building-lisp-zig).

The definition above is a little hard to follow, since the resulting expression must be built up using LIST and may include additional calls to QUASIQUOTE.

Quasiquotation allows us to make the body of a macro look like the expression it returns; for example the IGNORE macro in chapter 11

(DEFMACRO (IGNORE X)
  (CONS 'QUOTE (CONS X NIL)))

can now be written

(DEFMACRO (IGNORE X)
  `(QUOTE ,X))

and the operation is made clear.

Testing

> `(+ 1 ,(+ 2 3))
(+ 1 5)
> (define l '(3 4 5))
L
> `(1 2 ,@l)
(1 2 3 4 5)

let

We will now use QUASIQUOTE to define a new special form:

(LET ((sym1 expr1)
      (sym2 expr2)
      ...)
  body...)

LET causes the expressions expr to be evaluated with the symbols sym1, sym2... bound to the result of evaluating expr1, expr2 and so on. The result of the last expression body to be evaluated is returned.

The definition is simple.

(defmacro (let defs . body)
  `((lambda ,(map car defs) ,@body)
    ,@(map cadr defs)))

Example

When we evaluate the form

(LET ((X 3) (Y 5)) (+ X Y))

it is transformed by the LET macro into

((LAMBDA (X Y) (+ X Y)) 3 5)

Testing

> (let ((x 3) (y 5)) (+ x y))
8
> x
Symbol not bound

The LET expression clarifies the programmer's intent to make temporary definitions.

A trick

We can use LET to extend the built-in binary operator + to accept any number of arguments.

(define +
  (let ((old+ +))
    (lambda xs (foldl old+ 0 xs))))

Compare this with the definition of ADD add the end of chapter 10.

Testing

> (+ 1 2 3 4)
10

We didn't have to touch builtin_add or even recompile the interpreter.

func TestChapter13(t *testing.T) {
    env := env_create_default()
    if err := load_file(env, "library.lisp"); err != nil {
        t.Errorf("error: want nil: got %v\n", err)
    }

    for _, tc := range []struct {
        id     int
        input  string
        expect string
        err    error
    }{
        {id: 1, input: "`(+ 1 ,(+ 2 3))", expect: "(+ 1 5)"},
        {id: 2, input: "(define l '(3 4 5))", expect: "L"},
        {id: 3, input: "`(1 2 ,@l)", expect: "(1 2 3 4 5)"},
        {id: 4, input: "(let ((x 3) (y 5)) (+ x y))", expect: "8"},
        {id: 5, input: "x", expect: "NIL", err: Error_Unbound},
        {id: 6, input: "(+ 1 2 3 4)", expect: "10"},
    } {
        var expr Atom
        _, err := read_expr([]byte(tc.input), &expr)
        if err != nil {
            t.Errorf("%d: read error: want nil: got %v\n", tc.id, err)
            continue
        }

        var result Atom
        err = eval_expr(expr, env, &result)

        if tc.err == nil && err == nil {
            // yay
        } else if tc.err == nil && err != nil {
            t.Errorf("%d: error: want nil: got %v\n", tc.id, err)
        } else if !errors.Is(err, tc.err) {
            t.Errorf("%d: error: want %v: got %v\n", tc.id, tc.err, err)
        }
        if got := result.String(); tc.expect != got {
            t.Errorf("%d: eval: want %q: got %q\n", tc.id, tc.expect, got)
        }
    }
}