▼Programming Languages
•2 A Simple Model
7.8.0.8
    ← prev  up  next → 

2 A Simple Model

Goals

— reading streams of characters into trees

— traversing syntax trees

— macro expansion

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.

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.

Resources

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

    ← prev  up  next →