PLAI那些事02 WAE

WAE : Concrete syntax

<WAE> ::= <num>
        | {+ <WAE> <WAE>}
        | {- <WAE> <WAE>}
        | {with {<id> <WAE>} <WAE>}
        | <id>

WAE : Abstract syntax

(define-type WAE
  [num (n number?)]
  [add (lhs WAE?) (rhs WAE?)]
  [sub (lhs WAE?) (rhs WAE?)]
  [with (name symbol?) (named-expr WAE?) (body WAE?)]
  [id (name symbol?)])

parse : sexp -> WAE

(define (parse sexp)
  (match sexp
    [(? number?)                (num sexp)]
    [(list '+ l r)              (add (parse l) (parse r))]
    [(list '- l r)              (sub (parse l) (parse r))]
    [(list ’with (list x i) b)  (with x (parse i) (parse b))] 
    [(? symbol?)                (id sexp)]
    [else (error 'parse "bad syntax: ~a" sexp)]))

subst : WAE symbol number -> WAE

(define (subst wae x val)
  (type-case WAE wae
    [num (n)       wae]
    [add (l r)    (add (subst l x val) (subst r x val))]
    [sub (l r)    (sub (subst l x val) (subst r x val))]
    [with (y i b) (with y
                        (subst i x val)
                        (if (symbol=? y x) b (subst b x val)))]
    [id (s)       (if (symbol=? s x) (num val) wae)])))

interp : WAE -> number

(define (interp wae)
  (type-case WAE wae
    [num (n)       n]
    [add (l r)     (+ (interp l) (interp r))]
    [sub (l r)     (- (interp l) (interp r))]
    [with (x i b)  (interp (subst b x (interp i)))]
    [id (s)        (error 'interp "free variable")]))