20 Mountebank: quote and compound static data
20.1 Quote
One of the distinguishing features of the Lisp family of languages is the quote form, abbreviated ’, which is a notation for writing down literal s-expressions.
Recall that an S-Expression is:
; type S-Expr = ; | Boolean ; | Number ; | Character ; | String ; | Symbol ; | Empty ; | (Boxof S-Expr) ; | (Pairof S-Expr S-Expr) ; | (Vectorof S-Expr)
Using quotes, we can write down a literal s-expression such as:
Examples
> '#t #t
> '#f #f
> '9 9
> '#\f #\f
> 'f 'f
> '() '()
> '#&7 '#&7
> '(1 . 2) '(1 . 2)
> '#(1 2 3) '#(1 2 3)
> '(a b ((c) #(d))) '(a b ((c) #(d)))
The grammar of things that can be written down inside of a quote are:
; Datum d ::= #t ; | #f ; | n where n is a Number literal ; | c where c is a Character literal ; | s where s is a String literal ; | s where s is a Symbol literal ; | () ; | #&d ; | (d . d) ; | #(d ...)
At a first level of understanding, it’s possible to understand quote by rewriting to “push” the quote in as far as possible.
Some things are “self-quoting,” e.g. booleans, characters, strings, numbers, boxes, and vectors; thus #t and '#t are the same. When we have a quote around a self-quoting datum, we can delete it.
Other datums like symbols and the empty list cannot push the quote in further, so we have '() and 'fred as literals for the empty list and the symbol fred, respectively.
Pairs, boxes, and vectors are compound datums. We can understand #&d as (box 'd) and '(d1 . d2) as (cons 'd1 'd2) and #(d ...) as (vector 'd ...).
We’ve been using the quote-notation from the beginning of the course so it should be familiar by now.
One of the key things about quote is that we can go from the concrete syntax of an expression as a piece of code, e.g. (if (zero? x) 0 (+ x (tri (sub1 x)))), to a representation of that expression as a piece of data by prepending a single character; ’, e.g. '(if (zero? x) 0 (+ x (tri (sub1 x)))).
We’ve relied on this in the front-end of our compiler and interpreter to parse programs by first calling read, which reads a single datum:
Examples
> (with-input-from-string "(if (zero? x) 0 (+ x (tri (sub1 x))))" read) '(if (zero? x) 0 (+ x (tri (sub1 x))))
Let us now add fully support for quote to our language. Let’s call it Mountebank.
We will change the AST definition for Mountebank to add a Quote constructor, which contains a datum. Since (Str s) and (Quote s) where s is a string are redundant, we remove all of the literal constructors.
Here is the new AST definition:
#lang racket (provide Lit Prim0 Prim1 Prim2 Prim3 If Eof Begin Let Var Prog Defn App Match Box Cons Conj Lam) ;; type Prog = (Prog (Listof Defn) Expr) (struct Prog (ds e) #:prefab) ;; type Defn = (Defn Id (Listof Id) Expr) (struct Defn (f xs e) #:prefab) ;; type Expr = (Lit Datum) ;; | (Eof) ;; | (Prim0 Op0) ;; | (Prim1 Op1 Expr) ;; | (Prim2 Op2 Expr Expr) ;; | (Prim3 Op3 Expr Expr Expr) ;; | (If Expr Expr Expr) ;; | (Begin Expr Expr) ;; | (Let Id Expr Expr) ;; | (Var Id) ;; | (App Expr (Listof Expr)) ;; | (Match Expr (Listof Pat) (Listof Expr)) ;; | (Lam Id (Listof Id) Expr) ;; type ClosedExpr = { e ∈ Expr | e contains no free variables } ;; type Id = Symbol ;; type Datum = Integer ;; | Boolean ;; | Character ;; | '() ;; | String ;; | Symbol ;; type Op0 = 'read-byte | 'peek-byte | 'void ;; type Op1 = 'add1 | 'sub1 ;; | 'zero? ;; | 'char? | 'integer->char | 'char->integer ;; | 'write-byte | 'eof-object? ;; | 'car | 'cdr | 'unbox ;; | 'empty? | 'cons? | 'box? ;; | 'box ;; | 'vector? | 'vector-length ;; | 'string? | 'string-length ;; | 'symbol? | 'symbol->string | 'string->symbol | 'string->uninterned-symbol ;; type Op2 = '+ | '- | '< | '= ;; | 'eq? | 'cons ;; | 'make-vector | 'vector-ref ;; | 'make-string | 'string-ref ;; type Op3 = 'vector-set! ;; type Pat = (Var Id) ;; | (Lit Datum) ;; | (Box Pat) ;; | (Cons Pat Pat) ;; | (Conj Pat Pat) (struct Eof () #:prefab) (struct Lit (d) #:prefab) (struct Prim0 (p) #:prefab) (struct Prim1 (p e) #:prefab) (struct Prim2 (p e1 e2) #:prefab) (struct Prim3 (p e1 e2 e3) #:prefab) (struct If (e1 e2 e3) #:prefab) (struct Begin (e1 e2) #:prefab) (struct Let (x e1 e2) #:prefab) (struct Var (x) #:prefab) (struct App (f es) #:prefab) (struct Lam (f xs e) #:prefab) (struct Match (e ps es) #:prefab) (struct Box (p) #:prefab) (struct Cons (p1 p2) #:prefab) (struct Conj (p1 p2) #:prefab)
The parser is updated to parse things like booleans, numbers, etc. as Quote nodes now and also to support the ability to write arbitrary datum value under a quote:
#lang racket (provide parse parse-closed parse-e parse-define parse-pattern) (require "ast.rkt") ;; [Listof S-Expr] -> Prog (define (parse . ss) (match (parse-prog ss (parse-defn-names ss) '()) [(list _ p) p])) ;; [Listof S-Expr] -> ClosedProg (define (parse-closed . ss) (match (parse-prog ss (parse-defn-names ss) '()) [(list '() p) p] [(list ys p) (error "undefined identifiers" ys)])) ;; S-Expr -> Expr ;; Parse a (potentially open) expression (define (parse-e s) (match (parse-e/acc s '() '()) [(list _ e) e])) ;; S-Expr -> Expr ;; Parse a (potentially open) definition (define (parse-define s) (match (parse-define/acc s '() '()) [(list _ d) d])) ;; S-Expr -> Pat ;; Parse a (potentially open) pattern (define (parse-pattern s) (match (parse-match-pattern/acc s '() '()) [(list _ _ p) p])) ;; S-Expr -> r:[Listof Id] ;; where: (distinct? r) ;; Extracts defined function names from given program-like s-expr ;; Does not fully parse definition ;; Example: ;; (parse-defn-names '((define (f x) x) (define (g y) y) 1) -> '(f g) (define (parse-defn-names ss) (define (rec ss fs) (match ss [(list s) fs] [(cons (cons (? (not-in fs) 'define) sd) sr) (match (parse-defn-name sd) [f (if (memq f fs) (error "duplicate definition" f) (rec sr (cons f fs)))])] [_ (error "parse error")])) (rec ss '())) (define (parse-defn-name s) (match s [(cons (cons (? symbol? f) _) _) f] [_ (error "parse error")])) ;; S-Expr [Listof Id] [Listof Id] -> (list [Listof Id] Prog) ;; s: program shaped s-expr to be parsed ;; xs: bound variables ;; ys: free variables ;; returns list of free variables and parse of program (define (parse-prog s xs ys) (match s [(list s) (match (parse-e/acc s xs ys) [(list ys e) (list ys (Prog '() e))])] [(cons s ss) (match (parse-define/acc s xs ys) [(list ys (and d (Defn f _ _))) (match (parse-prog ss xs ys) [(list ys (Prog ds e)) (list ys (Prog (cons d ds) e))])])])) ;; S-Expr [Listof Id] [Listof Id] [Listof Id] [Listof Id] -> (list [Listof Id] Defn) ;; s: definition shaped s-expr to be parsed ;; xs: bound variables ;; ys: free variables ;; returns list of free variables and parse of definition (define (parse-define/acc s xs ys) (match s [(cons 'define sr) (match sr [(list (cons (? symbol? g) (and (list (? symbol? zs) ...) (? distinct?))) s) (match (parse-e/acc s (cons g (append zs xs)) ys) [(list ys e) (list ys (Defn g zs e))])] [_ (error "parse error")])] [_ (error "parse error")])) ;; S-Expr [Listof Id] [Listof Id] [Listof Id] [Listof Id] -> (list [Listof Id] Expr) ;; s: expression shaped s-expr to be parsed ;; xs: bound variables ;; ys: free variables ;; returns list of free variables and parse of expression (define (parse-e/acc s xs ys) (define (rec s xs ys) (define ns xs) (match s [(and 'eof (? (not-in ns))) (list ys (Eof))] [(? self-quoting-datum?) (list ys (Lit s))] [(list (and 'quote (? (not-in ns))) (list)) (list ys (Lit '()))] [(list (and 'quote (? (not-in ns))) (? datum? d)) (list ys (Lit d))] [(? symbol? f) (if (memq s xs) (list ys (Var s)) (list (cons s ys) (Var s)))] [(list-rest (? symbol? (? (not-in ns) k)) sr) (match k ['let (match sr [(list (list (list (? symbol? x) s1)) s2) (match (rec s1 xs ys) [(list ys e1) (match (rec s2 (cons x xs) ys) [(list ys e2) (list ys (Let x e1 e2))])])] [_ (error "let: bad syntax" s)])] ['match (match sr [(cons s sr) (match (rec s xs ys) [(list ys e) (match (parse-match-clauses/acc sr xs ys) [(list ys ps es) (list ys (Match e ps es))])])] [_ (error "match: bad syntax" s)])] [(or 'λ 'lambda) (match sr [(list (and (list (? symbol? zs) ...) (? distinct?)) s) (match (rec s (append zs xs) ys) [(list ys e) (list ys (Lam (gensym 'lambda) zs e))])] [_ (error "lambda: bad syntax" s)])] [_ (match (parse-es/acc sr xs ys) [(list ys es) (match (cons k es) [(list (? op0? o)) (list ys (Prim0 o))] [(list (? op1? o) e1) (list ys (Prim1 o e1))] [(list (? op2? o) e1 e2) (list ys (Prim2 o e1 e2))] [(list (? op3? o) e1 e2 e3) (list ys (Prim3 o e1 e2 e3))] [(list 'begin e1 e2) (list ys (Begin e1 e2))] [(list 'if e1 e2 e3) (list ys (If e1 e2 e3))] [(list-rest g es) (list (cons g ys) (App (Var g) es))])])])] [(cons s sr) (match (parse-e/acc s xs ys) [(list ys e) (match (parse-es/acc sr xs ys) [(list ys es) (list ys (App e es))])])] [_ (error "parse error" s)])) (rec s xs ys)) ;; S-Expr [Listof Id] [Listof Id] [Listof Id] [Listof Id] -> (list [Listof Id] [Listof Expr]) ;; s: list of expressions shaped s-expr to be parsed ;; xs: bound variables ;; ys: free variables ;; returns list of free variables and parse of expressions (define (parse-es/acc s xs ys) (match s ['() (list ys '())] [(cons s ss) (match (parse-e/acc s xs ys) [(list ys e) (match (parse-es/acc ss xs ys) [(list ys es) (list ys (cons e es))])])] [_ (error "parse error")])) ;; S-Expr [Listof Id] [Listof Id] [Listof Id] [Listof Id] -> (list [Listof Id] [Listof Expr]) ;; s: list of match clauses shaped s-expr to be parsed ;; xs: bound variables ;; ys: free variables ;; returns list of free variables and list of parsed clause patterns and clause expressions (define (parse-match-clauses/acc sr xs ys) (match sr ['() (list ys '() '())] [(cons (list sp se) sr) (match (parse-match-pattern/acc sp xs ys) [(list ys xs p) (match (parse-e/acc se xs ys) [(list ys e) (match (parse-match-clauses/acc sr xs ys) [(list ys ps es) (list ys (cons p ps) (cons e es))])])])])) ;; S-Expr [Listof Id] [Listof Id] [Listof Id] [Listof Id] -> (list [Listof Id] [Listof Id] Pat) ;; s: list of patterns shaped s-expr to be parsed ;; xs: bound variables ;; ys: free variables ;; returns list of free variables, bound variables, and parse of pattern (define (parse-match-pattern/acc s xs ys) (define (rec p xs ys) (match p [(? self-quoting-datum?) (list ys xs (Lit p))] ['_ (list ys xs (Var '_))] [(? symbol?) (list ys (cons p xs) (Var p))] [(list 'quote (? datum? d)) (list ys xs (Lit d))] [(list 'box s) (match (rec s xs ys) [(list ys xs p) (list ys xs (Box p))])] [(list 'cons s1 s2) (match (rec s1 xs ys) [(list ys xs p1) (match (rec s2 xs ys) [(list ys xs p2) (list ys xs (Cons p1 p2))])])] [(list 'and s1 s2) (match (rec s1 xs ys) [(list ys xs p1) (match (rec s2 xs ys) [(list ys xs p2) (list ys xs (Conj p1 p2))])])] [_ (error "parse pattern error")])) (rec s xs ys)) ;; [Listof Any] -> Boolean (define (distinct? xs) (not (check-duplicates xs))) ;; xs:[Listof Any] -> p:(x:Any -> Boolean) ;; Produce a predicate p for things not in xs (define (not-in xs) (λ (x) (not (memq x xs)))) (define (in m) (λ (x) (memq x m))) ;; Any -> Boolean (define (self-quoting-datum? x) (or (exact-integer? x) (boolean? x) (char? x) (string? x) (and (box? x) (datum? (unbox x))) (and (vector? x) (andmap datum? (vector->list x))))) ;; Any -> Boolean (define (datum? x) (or (self-quoting-datum? x) (empty? x) (symbol? x) (and (pair? x) (datum? (car x)) (datum? (cdr x))))) ;; Any -> Boolean (define (op0? x) (memq x '(read-byte peek-byte void))) (define (op1? x) (memq x '(add1 sub1 zero? char? integer->char char->integer write-byte eof-object? box unbox empty? cons? box? car cdr vector? vector-length string? string-length symbol? symbol->string string->symbol string->uninterned-symbol))) (define (op2? x) (memq x '(+ - < = eq? cons make-vector vector-ref make-string string-ref))) (define (op3? x) (memq x '(vector-set!)))
20.2 Quotes are constants
One thing that the “pushing quote” in understanding of quote misses is that a quote expression produces a constant, unlike the use of operations to construct an equivalent value.
Using eq? we can observe the difference. Recall that '(1 . 2) produces a value equivalent to (cons 1 2); however '(1 . 2) is a constant, whereas (cons 1 2) dynamically allocates memory to represent the pair.
We can see difference here:
Examples
> (define (f) '(1 . 2)) > (define (g) (cons 1 2)) > (eq? (f) (f)) #t
> (eq? (g) (g)) #f
Note, this does not mean that all quotes are interned (although some members of the Lisp and Scheme family do this):
Examples
> (define (f) '(1 . 2)) > (define (g) '(1 . 2)) > (eq? (f) (g)) #f
On the other hand, it’s important to note that strings and symbols that appear in quoted datums are interned as usual:
Examples
> (define (f) '("first" . second)) > (define (g) '("first" . second)) > (eq? (car (f)) (car (g))) #t
> (eq? (cdr (f)) (cdr (g))) #t
> (eq? (f) (g)) #f
20.3 Interpreting quote
Interpreting a quoted datum is trivial—
#lang racket (provide interp interp-e) (provide interp-match-pat) (require "../syntax/ast.rkt") (require "interp-prim.rkt") (require "env.rkt") ;; type Value = ;; | Integer ;; | Boolean ;; | Character ;; | Eof ;; | Void ;; | '() ;; | (cons Value Value) ;; | (box Value) ;; | (string Character ...) ;; | (vector Value ...) ;; | (Value ... -> Answer) ;; type Answer = Value | 'err ;; type Env = (Listof (List Id Value)) (define (err? x) (eq? x 'err)) ;; ClosedExpr -> Answer ;; Prog -> Answer (define (interp p) (with-handlers ([err? identity]) (match p [(Prog ds e) (interp-e e '() ds)]))) ;l Expr Env Defns -> Value { raises 'err } (define (interp-e e r ds) ;; where r closes e (match e [(Var x) (interp-var x r ds)] [(Lit d) d] [(Eof) eof] [(Prim0 p) (interp-prim0 p)] [(Prim1 p e) (interp-prim1 p (interp-e e r ds))] [(Prim2 p e1 e2) (interp-prim2 p (interp-e e1 r ds) (interp-e e2 r ds))] [(Prim3 p e1 e2 e3) (interp-prim3 p (interp-e e1 r ds) (interp-e e2 r ds) (interp-e e3 r ds))] [(If e1 e2 e3) (if (interp-e e1 r ds) (interp-e e2 r ds) (interp-e e3 r ds))] [(Begin e1 e2) (begin (interp-e e1 r ds) (interp-e e2 r ds))] [(Let x e1 e2) (let ((v (interp-e e1 r ds))) (interp-e e2 (ext r x v) ds))] [(App e es) (let ((f (interp-e e r ds)) (vs (interp-e* es r ds))) (if (procedure? f) (apply f vs) (raise 'err)))] [(Match e ps es) (let ((v (interp-e e r ds))) (interp-match v ps es r ds))] [(Lam f xs e) (λ vs ; check arity matches (if (= (length xs) (length vs)) (interp-e e (append (zip xs vs) r) ds) (raise 'err)))])) ;; (Listof Expr) REnv Defns -> (Listof Value) { raises 'err } (define (interp-e* es r ds) (match es ['() '()] [(cons e es) (cons (interp-e e r ds) (interp-e* es r ds))])) ;; Id Env [Listof Defn] -> Answer (define (interp-var x r ds) (match (lookup r x) ['err (match (defns-lookup ds x) [(Defn f xs e) (interp-e (Lam f xs e) '() ds)] [#f 'err])] [v v])) ;; Value [Listof Pat] [Listof Expr] Env Defns -> Answer (define (interp-match v ps es r ds) (match* (ps es) [('() '()) 'err] [((cons p ps) (cons e es)) (match (interp-match-pat p v r) [#f (interp-match v ps es r ds)] [r (interp-e e r ds)])])) ;; Pat Value Env -> [Maybe Env] (define (interp-match-pat p v r) (match p [(Var '_) r] [(Var x) (ext r x v)] [(Lit l) (and (eqv? l v) r)] [(Box p) (match v [(box v) (interp-match-pat p v r)] [_ #f])] [(Cons p1 p2) (match v [(cons v1 v2) (match (interp-match-pat p1 v1 r) [#f #f] [r1 (interp-match-pat p2 v2 r1)])] [_ #f])] [(Conj p1 p2) (match (interp-match-pat p1 v r) [#f #f] [r1 (interp-match-pat p2 v r1)])])) ;; Defns Symbol -> Defn (define (defns-lookup ds f) (findf (match-lambda [(Defn g _ _) (eq? f g)]) ds)) (define (zip xs ys) (match* (xs ys) [('() '()) '()] [((cons x xs) (cons y ys)) (cons (list x y) (zip xs ys))]))
The proper treatment of datums as constants is inherited from Racket, so our interpreter does the right thing on these examples:
Examples
> (define (run . p) (interp (parse p)))
> (run '(define (f) (cons 1 2)) '(eq? (f) (f))) 'err
> (run '(define (f) '(1 . 2)) '(eq? (f) (f))) 'err
20.4 Compiling quote
Compiling quote is not difficult. We’ve seen all the necessary pieces already. The key things to observe are:
a compound quoted datum should be statically allocated,
strings and symbols that appear in datums should be interned.
The latter is achieved by extending the literals function from Mug to traverse the datum in a quote to extract any string or symbol occurrences.
#lang racket (provide compile-literals init-symbol-table compile-string-chars symbol->data-label) (require "../syntax/ast.rkt") (require "../syntax/literals.rkt") (require "../runtime/types.rkt") (require a86/ast a86/registers) ;; Prog -> Asm (define (compile-literals p) (append-map compile-literal (literals p))) ;; Symbol -> Asm (define (compile-literal s) (let ((str (symbol->string s))) (seq (Label (symbol->data-label s)) (Dq (value->bits (string-length str))) (compile-string-chars (string->list str)) (if (odd? (string-length str)) (seq (Dd 0)) (seq))))) ;; Prog -> Asm ;; Call intern_symbol on every symbol in the program (define (init-symbol-table p) (match (symbols p) ['() (seq)] [ss (seq (Sub 'rsp 8) (append-map init-symbol ss) (Add 'rsp 8))])) ;; Symbol -> Asm (define (init-symbol s) (seq (Lea rdi (symbol->data-label s)) (Extern 'intern_symbol) (Call 'intern_symbol))) ;; [Listof Char] -> Asm (define (compile-string-chars cs) (match cs ['() (seq)] [(cons c cs) (seq (Dd (char->integer c)) (compile-string-chars cs))])) (define (symbol->data-label s) (symbol->label (string->symbol (string-append "data_" (symbol->string s)))))
The static allocation of compound datums is achieved use the same static memory allocation mechanism we saw when allocating the string data of strings and symbols.
Here’s how datums are compiled:
strings are compiled to the tagged address of their string data,
symbols are compiled to the tagged address of their string data,
atoms are compiled to their bit represetation, and
compound datums are compiled to a static chunk of memory to contain its data and a tagged address of that memory.
Let’s see some examples:
(compile-datum 0) (compile-datum #f) (compile-datum 'fred) (compile-datum "fred") (compile-datum '(1 . 2))
In the last example, you’ll notice we get a (Data) section that includes 2 words of memory; the first contains the bit representation of 2, i.e. the cdr of the pair, and the second contains the bit representation of 1, i.e. the car of the pair. After the (Data) section, we switch back to (Text) mode with an instruction to load the address of the statically allocated pair, appropriately tagged.
Datums can be built up arbitrarily large, so in order to compound datums, we need to recursive traverse their structure to emit the static data section of their construction. Here’s a larger example:
(compile-datum '((3) fred #(x y z) (("wilma"))))
Notice that every compound datum has its own label and when they are contained within other compound datums, we get references, appropriately tagged, to those labels.
Here is a simple example of a nested datum: a box containing a box containing zero.
(compile-datum '#&#&0)
The data section starts with a label and word for the outer box. The word contains a tagged reference to the inner box, which is defined immediately below as a label and word. That word contains 0. In the text section there is a single instruction to load the tagged address of the outer box into 'rax.
Here is the complete code for compile-datum:
#lang racket (provide compile-datum) (require "../runtime/types.rkt") (require "compile-literals.rkt") (require a86/ast a86/registers) ;; Datum -> Asm (define (compile-datum d) (cond [(string? d) (seq (Lea rax (load-string d)))] [(symbol? d) (seq (Lea rax (load-symbol d)))] [(compound? d) (compile-compound-datum d)] [else (compile-atom d)])) (define (load-symbol s) (Mem (symbol->data-label s) type-symb)) (define (load-string s) (Mem (symbol->data-label (string->symbol s)) type-str)) ;; Value -> Asm (define (compile-atom v) (seq (Mov rax (value->bits v)))) ;; Datum -> Boolean (define (compound? d) (or (box? d) (cons? d) (vector? d))) ;; Datum -> Asm (define (compile-compound-datum d) (match (compile-quoted d) [(cons l is) (seq (Data) is (Text) (Lea rax l))])) ;; Datum -> (cons AsmExpr Asm) (define (compile-quoted c) (cond [(vector? c) (compile-datum-vector (vector->list c))] [(box? c) (compile-datum-box (unbox c))] [(cons? c) (compile-datum-cons (car c) (cdr c))] [(symbol? c) (cons (load-symbol c) '())] [(string? c) (cons (load-string c) '())] [else (cons (value->bits c) '())])) ;; Datum -> (cons AsmExpr Asm) (define (compile-datum-box c) (match (compile-quoted c) [(cons l1 is1) (let ((l (gensym 'box))) (cons (Mem l type-box) (seq (Label l) (Dq l1) is1)))])) ;; Datum Datum -> (cons AsmExpr Asm) (define (compile-datum-cons c1 c2) (match (compile-quoted c1) [(cons l1 is1) (match (compile-quoted c2) [(cons l2 is2) (let ((l (gensym 'cons))) (cons (Mem l type-cons) (seq (Label l) (Dq l1) (Dq l2) is1 is2)))])])) ;; [Listof Datum] -> (cons AsmExpr Asm) (define (compile-datum-vector ds) (match ds ['() (cons (Mem 'empty type-vect) '())] [_ (let ((l (gensym 'vector)) (cds (map compile-quoted ds))) (cons (Mem l type-vect) (seq (Label l) (Dq (value->bits (length ds))) (map (λ (cd) (Dq (car cd))) cds) (append-map cdr cds))))]))
Now we’ve succsefully implemented quote and can confirm are examples behave as expected:
(current-objects '("runtime/runtime.o")) (define (run . p) (bits->value (asm-interp (compile (parse p))))) (run '#t) (run ''#t) (run ''(1 . 2)) (run ''(1 fred #("wilma"))) (run '(define (f) '(1 . 2)) '(eq? (f) (f))) (run '(define (f) '("fred" . wilma)) '(define (g) '("fred" . wilma)) '(eq? (car (f)) (car (g)))) (run '(define (f) '("fred" . wilma)) '(define (g) '("fred" . wilma)) '(eq? (cdr (f)) (cdr (g))))
20.5 Getting Meta
It’s worth taking stock of the kind of programs we can now write. Since quote let’s us write down data that looks an awful lot like programs, we can start to write programs that operate over this kind of data in a way that may seem familiar.
For example, here’s a program that interprets a little language that has elements of the ones we’ve been building:
#lang racket ;; type Expr = Number ;; | Boolean ;; | (list Op1 Expr) ;; | (list Op2 Expr) ;; | (list 'if Expr Expr Expr) ;; | (list Expr Expr) ;; | (list 'λ (list Id) Expr) ;; | Id ;; type Id = Symbol ;; type Op1 = 'sub1 | 'zero? ;; type Op2 = '+ ;; type Value = Number ;; | Boolean ;; | (Value -> Value) ;; Expr Env -> Value (define (interp e r) (match e [(list '+ e1 e2) (+ (interp e1 r) (interp e2 r))] [(list 'sub1 e1) (sub1 (interp e1 r))] [(list 'zero? e1) (zero? (interp e1 r))] [(list 'if e1 e2 e3) (if (interp e1 r) (interp e2 r) (interp e3 r))] [(list 'λ (list x) e1) (λ (v) (interp e1 (cons (cons x v) r)))] [(list e1 e2) ((interp e1 r) (interp e2 r))] [_ (if (symbol? e) (lookup e r) e)])) ;; Id Env -> Value (define (lookup x r) (match r [(cons (cons y v) r) (if (eq? x y) v (lookup x r))])) (interp '(((λ (t) ((λ (f) (t (λ (z) ((f f) z)))) (λ (f) (t (λ (z) ((f f) z)))))) (λ (tri) (λ (n) (if (zero? n) 0 (+ n (tri (sub1 n))))))) 36) '())
Now of course this is a Racket program, which we can run. Running it will run the interpreter we defined on the input program, computing the 36th triangular number:
shell
racket simple-interp.rkt 666
But of course, this is also a Mountebank program! So we can interpret it with our Mountenank interpreter:
shell
racket -t interp-file.rkt -m simple-interp.rkt 666
And since it’s a Mountebank program, we can also compile it and then running the resulting executable:
shell
make simple-interp.run ./simple-interp.run 666
We are moving ever closer to the point where our compiler can compile the source code of itself.