PLAI那些事

没有了with表达，with，exp，body的id换成exp的lambda函数，从而可以没有with来进行实现。即，{with {id exp} body}换成了{{fun {id} body} exp}。

FAE : Concrete syntax

<FWAE> ::= <num>

         | {+ <FWAE> <FWAE>}

         | {- <FWAE> <FWAE>}

         | <id>

         | {fun {<id>} <FWAE>}

         | {<FWAE> <FWAE>}

FAE : Abstrac syntax

(define-type FAE

  [num (n number?)]

  [add (lhs FAE?) (rhs FAE?)]

  [sub (lhs FAE?) (rhs FAE?)]

  [id (name symbol?)]

  [fun (param symbol?) (body FAE?)]

  [app (ftn FAE?) (arg FAE?)])

parse : sexp -> FAE

(define (parse sexp)

  (match sexp

    [(? number?) (num sexp)]

    [(list '+ l r) (add (parse l) (parse r))]

    [(list '- l r) (sub (parse l) (parse r))]

    [(? symbol?) (id sexp)]

    [(list 'fun (list x) b) (fun x (parse b))]

    [(list f a) (app (parse f) (parse a))]

    [else (error 'parse "bad syntax: ~a" sexp)]))

interp : FAE -> 'FAE'

(define (num+ x y)

  (num (+ (num-n x) (num-n y))))

(define (num- x y)

  (num (- (num-n x) (num-n y))))

(define (interp fae)

  (type-case FAE fae

    [num (n) fae]

    [add (l r) (num+ (interp l) (interp r))]

    [sub (l r) (num- (interp l) (interp r))]

    [id (s) (error 'interp "free variable")]

    [fun (x b) fae]

    [app (f a) (local [(define ftn (interp f))]

                  (interp (subst (fun-body ftn)

                                 (fun-param ftn)

                                 (interp a))))]))

subst : 'FAE' 'symbol' 'FAE' -> 'FAE'

(define (subst exp sub-id val)

  (type-case FAE exp

    [num (n) exp]

    [add (l r) (add (subst l sub-id val) (subst r sub-id val))]

    [sub (l r) (sub (subst l sub-id val) (subst r sub-id val))]

    [id (name) (cond [(equal? name sub-id) val]

                     [else exp])]

    [app (f arg) (app (subst f sub-id val)

                      (subst arg sub-id val))]

    [fun (id body) (if (equal? sub-id id)

                       exp

                       (fun id (subst body sub-id val)))]))

巴特西

PLAI那些事_06 FAE

没有了with表达，with，exp，body的id换成exp的lambda函数，从而可以没有with来进行实现。即，{with {id exp} body}换成了{{fun {id} body} exp}。

FAE : Concrete syntax

FAE : Abstrac syntax

parse : sexp -> FAE

interp : FAE -> 'FAE'

subst : 'FAE' 'symbol' 'FAE' -> 'FAE'

最新文章

热门文章