Programming Languages

FWAE : Concrete syntax

<FWAE> ::= <num>

         | {+ <FWAE> <FWAE>}

         | {- <FWAE> <FWAE>}

         | {with {<id> <FWAE>} <FWAE>}

         | <id>

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

         | {<FWAE> <FWAE>}

FWAE : Abstract syntax

其中的“function definition”和“function call”在language structure内以lambda函数形式包含在其中，所以不需要像F1WAE那样的FunDef。

(define-type FWAE

  [num (n number?)]

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

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

  [with (name symbol?) (named-expr FWAE?) (body FWAE?)]

  [id (name symbol?)]

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

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

(fun x (add 1 x))等lambda函数形态本身就是with-namd-expr的FWAE∼ae类型，那么在with-body中，与with-name一致的相应id被调换到fun，并进入app的ftn之中。

parse : sexp -> FWAE

(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)]

    [(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 : FWAE -> FWAE

因为最终的结果是FWAE，所以add和sub的结果会使num重新加入。

(define (num+ x y)

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

(define (num- x y)

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

(define (interp fwae)

  (type-case FWAE fwae

    [num (n) fwae]

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

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

    [with (x i b) (interp (subst b x (interp i)))]

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

    [fun (x b) fwae]

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

                  (interp (subst (fun-body ftn)

                                 (fun-param ftn)

                                 (interp a))))]))

app中将ftn作为local define，如果f是未定义的函数，那么将出现free variable error，如果f是已经定义的函数，那么就是fun的形态，所以ftn具有fun的structure。

subst : FWAE symbol FWAE -> FWAE

(define (subst exp sub-id val)

  (type-case FWAE 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))]

    [with (x i b) (with x

                        (subst i sub-id val)

                        (if (symbol=? sub-id x)

                            b

                            (subst b 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)))]))

Examples

F1WAE : first-order functions

{deffun {f x} {+ 1 x}}

{f 10}

FWAE : first-class functions

{with {f {fun {x} {+ 1 x}}} {f 10}}

巴特西

Programming Languages_05 FWAE

FWAE : Concrete syntax

FWAE : Abstract syntax

其中的“function definition”和“function call”在language structure内以lambda函数形式包含在其中，所以不需要像F1WAE那样的FunDef。

(fun x (add 1 x))等lambda函数形态本身就是with-namd-expr的FWAE∼ae类型，那么在with-body中，与with-name一致的相应id被调换到fun，并进入app的ftn之中。

parse : sexp -> FWAE

interp : FWAE -> FWAE

因为最终的结果是FWAE，所以add和sub的结果会使num重新加入。

app中将ftn作为local define，如果f是未定义的函数，那么将出现free variable error，如果f是已经定义的函数，那么就是fun的形态，所以ftn具有fun的structure。

subst : FWAE symbol FWAE -> FWAE

Examples

最新文章

热门文章