11 Grift: binary operations
If you have to eat two frogs, eat the ugliest one first.
You may have noticed that up until this point, evaluating compound expressions in our language always depend upon the result of a single subexpression. For example, (add1 e) depends upon the result of e, (zero? e) depends upon e, and so on. Even expressions that involve multiple subexpressions such as (if e0 e1 e2) really only depends on e0 to determine which of e1 or e2 to evaluate.
Let’s now consider what happens when we have multiple subexpressions whose results must be combined in order to evaluate an expression. As an example, consider (+ e0 e1). We must evaluate both e0 and e1 and sum their results.
We’ll call this language Grift.
What’s new are the following binary operations:
(+ e0 e1) (- e0 e1)
This leads to the following grammar for Grift:
We can model it as a datatype as usual:
#lang racket (provide (all-defined-out)) ;; type Expr = ;; | Integer ;; | Boolean ;; | Variable ;; | Prim1 Expr ;; | Prim2 Expr Expr ;; | If Expr Expr Expr ;; | Let (Binding list) Expr ;; type Prim1 = 'add1 | 'sub1 | 'zero? ;; type Prim2 = '+ | '- ;; type Binding = Variable Expr ;; type Variable = Symbol (except 'add1 'sub1 'if, etc.) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;; The AST data structure ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; The AST can be viewed as having 'kinds' of nodes. ;; ;; * The nodes that represnt an expression themselves ;; ;; * The nodes that are part of an expression, but no an expression themselves ;; The below are the former: (struct int-e (i) #:transparent) (struct bool-e (b) #:transparent) (struct var-e (v) #:transparent) (struct prim-e (p es) #:transparent) (struct if-e (e t f) #:transparent) (struct let-e (bs b) #:transparent) ;; The next is the latter: ;; A binding holds a symbol representing the bound variable and ;; Expr that represents the value that will be bound to that variable (struct binding (v e) #:transparent) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;; AST utility functions (predicates) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define unops '(add1 sub1 zero?)) (define biops '(+ -)) ;; Any -> Boolean (define (prim? x) (and (symbol? x) (memq x (append unops biops)))) ;; Any -> Boolean (define (biop? x) (and (symbol? x) (memq x biops))) ;; Any -> Boolean (define (unop? x) (and (symbol? x) (memq x unops))) (define (value? v) (or (int-e? v) (bool-e? v))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;; AST utility functions (getters) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; It will sometimes be useful to get the list of all the variables that are ;; introduced by a `let` ;; [Binding] -> [Symbol] (define (get-vars bs) (match bs ['() '()] [(cons (binding v _) bs) (cons v (get-vars bs))])) ;; Get all of the _definitions_ from a list of bindings ;; [Binding] -> [Expr] (define (get-defs bs) (match bs ['() '()] [(cons (binding _ def) bs) (cons def (get-defs bs))])) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;; AST utility functions (printers) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; We have switched to using `#:transparent` above, so this should only be ;; necessary if you're desperate when debugging :'( ;; Given an AST, construct an sexpr that has the same shape (define (ast->sexpr a) (match a [(int-e i) `(int-e ,i)] [(bool-e b) `(bool-e ,b)] [(var-e v) `(var-e ,v)] [(prim-e p es) `(prim-e ,p ,@(map ast->sexpr es))] [(if-e e t f) `(if-e ,(ast->sexpr e) ,(ast->sexpr t) ,(ast->sexpr f))] [(let-e bs b) `(let-e ,(binding->sexpr bs) ,(ast->sexpr b))])) (define (binding->sexpr bnds) (match bnds ['() '()] [(cons (binding v e) bnds) `((,v ,(ast->sexpr e)) ,@(binding->sexpr bnds))]))
11.1 Meaning of Grift programs
The meaning of Grift programs is pretty straightforward. For (+ e0 e1), the meaning is the sum of the meanings of e0 and e1, when they mean integers, otherwise the meaning is an error.
The handling of primitives occurs in the following rule:
It makes use of an auxiliary judgment for interpreting primitives:
The interpreter is likewise straightforward:
#lang racket (provide (all-defined-out)) (require "ast.rkt") ;; type Answer = Value | 'err ;; type Value = ;; | Integer ;; | Boolean ;; type REnv = (Listof (List Variable Value)) ;; Expr -> Answer (define (interp e) (interp-env e '())) ;; Expr REnv -> Integer (define (interp-env e r) (match e [(var-e v) (lookup r v)] [(int-e i) i] [(bool-e b) b] [(prim-e (? prim? p) es) (let ((as (interp-env* es r))) (interp-prim p as))] [(if-e p e1 e2) (match (interp-env p r) ['err 'err] [v (if v (interp-env e1 r) (interp-env e2 r))])] [(? symbol? x) (lookup r x)] [(let-e (list (binding x def)) body) (match (interp-env def r) ['err 'err] [v (interp-env body (ext r x v))])])) (define (interp-env* es r) (match es ['() '()] [(cons e es) (cons (interp-env e r) (interp-env* es r))])) (define (interp-prim p as) (match (cons p as) [(list 'add1 (? integer? i)) (+ i 1)] [(list 'sub1 (? integer? i)) (- i 1)] [(list 'zero? (? integer? i)) (zero? i)] [(list '+ (? integer? i) (? integer? j)) (+ i j)] [(list '- (? integer? i) (? integer? j)) (- i j)] [_ 'err])) ;; Env Variable -> Answer (define (lookup env x) (match env ['() 'err] [(cons (list y i) env) (match (symbol=? x y) [#t i] [#f (lookup env x)])])) ;; Env Variable Value -> Value (define (ext r x i) (cons (list x i) r))
We can see that it works as expected:
Examples
> (interp (sexpr->ast '(+ 3 4))) 7
> (interp (sexpr->ast '(+ 3 (+ 2 2)))) 7
> (interp (sexpr->ast '(+ #f 8))) 'err
11.2 A Compile for Grift
Binary expressions are easy to deal with at the level of the semantics and interpreter. However things are more complicated at the level of the compiler.
To see the problem consider blindly following the pattern we used (and ignoring type errors for the moment):
; Expr Expr CEnv -> Asm (define (compile-+ e0 e1 c) (let ((c0 (compile-e e0 c)) (c1 (compile-e e1 c))) `(,@c0 ; result in rax ,@c1 ; result in rax (add rax ???))))
The problem here is that executing c0 places its result in register 'rax, but then executing c1 places its result in 'rax, overwriting the value of e0.
It may be tempting to use another register to stash away the result of the first subexpression:
; Expr Expr CEnv -> Asm (define (compile-+ e0 e1 c) (let ((c0 (compile-e e0 c)) (c1 (compile-e e1 c))) `(,@c0 ; result in rax (mov rbx rax) ,@c1 ; result in rax (add rax rbx))))
Can you think of how this could go wrong?
To come up with a general solution to this problem, we need to save the result of e0 and then retrieve it after computing e1 and it’s time to sum.
Note that this issue only comes up when e0 is a serious expression, i.e. an expression that must do some computation. If e0 were a literal integer or a variable, we could emit working code. For example:
; Integer Expr CEnv -> Asm ; A special case for compiling (+ i0 e1) (define (compile-+-int i0 e1 c) (let ((c1 (compile-e e1 c))) `(,@c1 ; result in rax (add rax ,(arithmetic-shift i0 imm-shift))))) ; Variable Expr CEnv -> Asm ; A special case for compiling (+ x0 e1) (define (compile-+-var x0 e1) (let ((c1 (compile-e e1 c)) (i (lookup x0 c))) `(,@c1 (add rax (offset rsp ,(- (add1 i)))))))
The latter suggests a general solution could be to transform binary primitive applications into a let form that binds the first subexpression to a variable and then uses the compile-+-var function above. The idea is that every time the compiler encounters (+ e0 e1), we transform it to (let ((x e0)) (+ x e1)). For this to work out, x needs to be some variable that doesn’t appear free in e1. This transformation is what’s called ANF (administrative normal form) and is a widely used intermediate representation for compilers.
But, we can also solve the problem more directly by considering the code that is generated for the ANF style expression above.
Consider the lexical address of x in the transformed code above. It is always 0 because the transformation puts the let immediately around the occurrence of x. So if we’re compiling (+ e0 e1) in environment c using this approach, we know the value of e0 will live at `(offset rsp ,(- (add1 (length c)))). There’s no need for a let binding or a fresh variable name. And this observation enables us to write a general purpose compiler for binary primitives that doesn’t require any program transformation: we simply push the value of e0 on the top of the stack and retrieve it later.
Here is a first cut:
; Expr Expr CEnv -> Asm (define (compile-+ e0 e1 c) (let ((x (gensym))) ; generate a fresh variable (let ((c0 (compile-e e0 c)) (c1 (compile-e e1 (cons x c)))) `(,@c0 (mov (offset rsp ,(add1 (- (length c)))) rax) ,@c1 (add rax (offset rsp ,(- (add1 (lookup x (cons x c))))))))))
There are a couple things to notice. First: the (lookup x (cons x c)) just produces (length c). Second, when compiling e1 in environment (cons x c), we know that no variable in e1 resolves to x because x is a freshly gensym’d symbol. Putting (an unreferenced) x in the environment serves only to “bump up” by one the offset of any variable bound after x so as to not override the spot where e0’s values lives. We can accomplish the same thing by sticking in something that no variable is equal to: #f:
; Expr Expr CEnv -> Asm (define (compile-+ e0 e1 c) (let ((c0 (compile-e e0 c)) (c1 (compile-e e1 (cons #f c)))) `(,@c0 (mov (offset rsp ,(add1 (- (length c)))) rax) ,@c1 (add rax (offset rsp ,(- (add1 (length c))))))))
The complete code for the compiler is:
#lang racket (provide (all-defined-out)) (require "ast.rkt") (define imm-shift 1) (define imm-type-mask (sub1 (arithmetic-shift 1 imm-shift))) (define imm-type-int #b0) (define imm-val-true #b11) (define imm-val-false #b01) ;; Expr -> Asm (define (compile e) `(entry ,@(compile-e e '()) ret err (push rbp) (call error) ret)) ;; Expr CEnv -> Asm (define (compile-e e c) (match e [(int-e i) (compile-integer i)] [(bool-e b) (compile-boolean b)] [(var-e v) (compile-variable v c)] [(prim-e (? prim? p) es) (compile-prim p es c)] [(if-e p t f) (compile-if p t f c)] [(let-e (list b) body) (compile-let b body c)])) ;; Integer -> Asm (define (compile-integer i) `((mov rax ,(arithmetic-shift i imm-shift)))) ;; Boolean -> Asm (define (compile-boolean b) `((mov rax ,(if b imm-val-true imm-val-false)))) (define (compile-prim p es c) (match (cons p es) [`(add1 ,e0) (compile-add1 e0 c)] [`(sub1 ,e0) (compile-sub1 e0 c)] [`(zero? ,e0) (compile-zero? e0 c)] [`(+ ,e0 ,e1) (compile-+ e0 e1 c)] [`(- ,e0 ,e1) (compile-- e0 e1 c)] [_ (error (format "prim applied to wrong number of args: ~a ~a" p es))])) ;; Expr CEnv -> Asm (define (compile-add1 e0 c) (let ((c0 (compile-e e0 c))) `(,@c0 ,@assert-integer (add rax ,(arithmetic-shift 1 imm-shift))))) ;; Expr CEnv -> Asm (define (compile-sub1 e0 c) (let ((c0 (compile-e e0 c))) `(,@c0 ,@assert-integer (sub rax ,(arithmetic-shift 1 imm-shift))))) ;; Expr CEnv -> Asm (define (compile-zero? e0 c) (let ((c0 (compile-e e0 c)) (l0 (gensym)) (l1 (gensym))) `(,@c0 ,@assert-integer (cmp rax 0) (mov rax ,imm-val-false) (jne ,l0) (mov rax ,imm-val-true) ,l0))) (define (compile-+ e0 e1 c) (let ((c1 (compile-e e1 c)) (c0 (compile-e e0 (cons #f c)))) `(,@c1 ,@assert-integer (mov (offset rsp ,(- (add1 (length c)))) rax) ,@c0 ,@assert-integer (add rax (offset rsp ,(- (add1 (length c)))))))) (define (compile-- e0 e1 c) (let ((c1 (compile-e e1 c)) (c0 (compile-e e0 (cons #f c)))) `(,@c1 ,@assert-integer (mov (offset rsp ,(- (add1 (length c)))) rax) ,@c0 ,@assert-integer (sub rax (offset rsp ,(- (add1 (length c)))))))) ;; Expr Expr Expr CEnv -> Asm (define (compile-if e0 e1 e2 c) (let ((c0 (compile-e e0 c)) (c1 (compile-e e1 c)) (c2 (compile-e e2 c)) (l0 (gensym)) (l1 (gensym))) `(,@c0 (cmp rax ,imm-val-false) (je ,l0) ; jump to c2 if #f ,@c1 (jmp ,l1) ; jump past c2 ,l0 ,@c2 ,l1))) ;; Variable CEnv -> Asm (define (compile-variable x c) (let ((i (lookup x c))) `((mov rax (offset rsp ,(- (add1 i))))))) ;; Variable Expr Expr CEnv -> Asm (define (compile-let b e1 c) (match b [(binding x e0) (let ((c0 (compile-e e0 c)) (c1 (compile-e e1 (cons x c)))) `(,@c0 (mov (offset rsp ,(- (add1 (length c)))) rax) ,@c1))])) ;; Variable CEnv -> Natural (define (lookup x cenv) (match cenv ['() (error "undefined variable:" x)] [(cons y cenv) (match (eq? x y) [#t (length cenv)] [#f (lookup x cenv)])])) (define assert-integer `((mov rbx rax) (and rbx ,imm-type-mask) (cmp rbx ,imm-type-int) (jne err)))