▼Racket School 2019:  
The “How to Design Languages” Track
►2 Macro Expansion
On this page:
2.1 
2.2 A Model of (plain old) Lisp Parsing and Macro Expanding
2.3 What Does This Look Like in Real Racket?
2.3.1 Scope
2.3.2 The Core is Flexible
7.4.0.4
    ← prev  up  next → 

2 Macro Expansion

Matthias Felleisen

Goals

— reading streams of characters into trees

— traversing and expanding trees

— core syntax

To understand Racket’s approach to language extension and construction, we need to have a model of the front-end of a language implementation.

Here is a small snippet of Racket’s core:

  ;; A LAM is one of:                         Its Interpretation is:

  ;; -- VAR                                   -- a variable ref

  ;; -- NUM                                   -- a literal constant

  ;; -- (lambda (VAR) LAM)                    -- a 1-argument function

  ;; -- (+ LAM LAM)                           -- an addition expression

  ;; -- (LAM LAM)                             -- a function application

  ;;

  ;; NUM is a (Racket) number

  ;;

  ;; VAR is a sequence of keyboard characters (not a Racket number)

These first five lines represent the core language of LAM, as in, "understood by the compiler, which assigns meaning."

The next two lines make the language extensible:

  ;; -- (let-syntax (VAR META) LAM)           -- a macro definition

  ;; -- (VAR LAM ...)                         -- a macro use IF VAR is declared

  ;;

  ;; META is a language for writing down functions that construct LAMs

Let’s study lexing, parsing, and macro expansion in this context.

2.1 

macro.rkt: provides functions to state and run simple macros

table.rkt: provides functions for adding VAR0keyed information to, and retrieving it from, a table

2.2 A Model of (plain old) Lisp Parsing and Macro Expanding

Let’s start with examples in the plain language state as strings:

(define program-as-text "((lambda (x) (+ x 10)) 42)")
 
(define macro-as-text
  (string-append
    "((lambda (y)"
    "   (let-syntax (plus10"
    "               (lambda (stx)"
    "                 (match stx"
    "                   [`(plus10 ,x) `(+ ,x 10)])))"
    "     (plus10 y)))"
    " 42)"))
 
 
(define another-example
  (string-append
  "((lambda (fun)"
  "   (fun "
  "    (let-syntax (syn (lambda (stx)"
  "                         23))"
  "      (syn (fun 1) 20))))"
  " (lambda (x) (+ x 1)))"))

First we need to turn those strings into trees of concrete syntax, and for that we need a data representation:

(struct Syntax (e {stuff #:auto}) #:transparent #:auto-value 'stuff)

The Syntax structure encapsulates the S-expressions from the olden days and information about the original character string relative to these S-expressions. The model represents this information with 'stuff; you may imagine data such as the source file, line numbers, character numbers, and more.

Here is how we use this structure concretely:
; A SyntaxTree is one of:
; – (Syntax Number)
; – (Syntax Symbol)
; – (Syntax (list SyntaxTree ... SyntaxTree))
And here is a function that map an S-expression into this data representation.:
; S-expression -> SyntaxTree
(define (to-Syntax stx)
  (cond
    [(cons? stx) (Syntax (map to-Syntax stx))]
    [else (Syntax stx)]))

Second, we need a lex that reads a sequence of characters and produces a SyntaxTree:
; String -> S-exp
; read string (of characters) and transform into an S-expression
(define (lex str) ; also known as READER
  ... read ... to-Syntax ...)

Third, we need a function that gets rid of the language extensions. The function must traverse the SyntaxTree and, when it discovers a “core” form, it must “bless” it, possibly by some more processing.
(define (parse s table) ; also known as EXPANDER
  (match (Syntax-e s)
    [(? symbol?) s]
 
    [(? number?) s]
 
    [`(,(Syntax lambda _) ,(Syntax `(,(Syntax (? symbol? parameter) _)) _) ,body)
     (Syntax (list 'lambda parameter (parse body table)))]
 
    [`(,(Syntax '+ _) ,lop ,rop)
     (Syntax (list '+ (parse lop table) (parse rop table)))]
 
    ... *** ...
 
    [`(,fun ,arg) (Syntax (list 'app (parse fun table) (parse arg table)))]
 
    [_ (error 'parse "~s is not grammatical" s)]))
The function consumes a table in addition to the SyntaxTree because Technically, even core forms have transformers stored in the first table, and they map the SyntaxTree to true core forms. it needs to keep track of macros. Here is how it deals with them:
[`(,(Syntax 'let-syntax _) ,(Syntax `(,(Syntax (? symbol? name) _) ,rhs) _) ,body)
 (define transformer (make-transformer (from-Syntax rhs)))
 (parse body (extend-table name transformer table))]
 
[`(,(Syntax (? (compose (in? table)) m) _) ,more ...)
 (define transformer (retrieve m table))
 (parse (transformer s) table)]

The make-tranformer function turns the rhs META expression into a function on SyntaxTree.

With extend-table, parse remembers the association between name and this function for just the body of let-syntax. The last match clause of parse shows how the macro is used when a particular macro shape is discovered.

And yes, you can test this on the above strings.

2.3 What Does This Look Like in Real Racket?

The model is pretty close for simple Racket macros. Here is a simplification of the above example with correct syntax:
#lang racket
((lambda (fun)
   (fun
    (let-syntax ([syn (lambda (stx)     ; fix 1: add [...]
                        #'23)])   ; fix 2: add syntax
      (syn (fun 1) 20))))
 (lambda (x) (+ x 1)))
Unlike in our model, these syntax functions must construct syntax explicitly. There are simple versions of “macros” that inject their output into syntax automatically.

When you expand this expression in the model, the inner application of fun goes away, because the syn function is a constant function. When you expand this expression in Racket with expand the result is almost the same—and the differences can easily be explained.

Let’s experiment some more with this, and let’s use let instead of the cumbersome left-left-lambda:
#lang racket
 
(let ([fun (lambda (x) 65)])
  (list (fun 0)
        (let-syntax ((syn (lambda (stx)
                            #'23)))
          (list
           (syn)
           (syn 10)
           (syn 10 20)))
        (fun 1)))
No matter how many arguments we hand over to syn, it just works fine. Why? Remember that a syntax macro really gets the entire syn-labeled tree.

Add (displayln stx) to the syn function to see what is handed over as the argument. Then play with syntax-e to extract some of the tree’s pieces and look at them.

The point of the first two days is to explain the vast machinery of tools we have to define functions such as syn with notational economy.

But what is let-syntax then? It hooks a name (syn) to a function ((lambda (stx) #'23)), and this being Racket we can separate these notions:
#lang racket
 
(begin-for-syntax
  (define fun-defined-at-compile-time
    (lambda (stx)
      #'23)))
 
(let ([fun (lambda (x) 65)])
  (list (fun 0)
        (let-syntax ((syn fun-defined-at-compile-time))
          (list
           (syn)
           (syn 10)
           (syn 10 20)))
        (fun 1)))
And yes, we could have written (define (f stx) #'23).

With define-syntax, you can designate a compile-time function as applying to an entire module:
#lang racket
 
(begin-for-syntax
  (define fun-defined-at-compile-time
    (lambda (stx)
      #'23)))
 
(define-syntax syn fun-defined-at-compile-time)
 
(let ([fun (lambda (x) 65)])
  (list (fun 0)
          (list
           (syn)
           (syn 10)
           (syn 10 20))
        (fun 1)))

2.3.1 Scope

What the model does not show is that an expander also copes with lexical scope properly. It is perfectly acceptable to use the same name for compile-time and run-time functions:
#lang racket
(let ([fun (lambda (x) 65)])
  (list (fun 0)
        (let-syntax ((fun (lambda (stx)
                            #'23)))
          (list
           (fun)
           (fun 10)
           (fun 10 20)))
        (fun 1)))
A compile time function can also generated code that refers to a run-time function of the same name:
#lang racket
(let ([fun (lambda (x) 65)])
  (list (fun 0)
        (let-syntax ((fun (lambda (stx)
                            #'(fun 23))))
 
          (list
           (fun)
           (fun 10)
           (fun 10 20)))))

2.3.2 The Core is Flexible

Finally, here is a glance of what Racketeers, can do too. You don’t like lambda, well, re-define it for your purposes:
#lang racket
(let ([fun (lambda (x) x)])
  (fun
   (let-ntax ((lambda (lambda (stx) #'23)))
     (let ([fun (lambda (x) (+ 99 x))])
       fun))))

    ← prev  up  next →