Abstract Syntax.ppt

1、cs784 (Prasad),L6AST,1,Abstract Syntax,cs784 (Prasad),L6AST,2,Language of l-expressions, := | (lambda ( ) | ( ) E.g., concrete syntax Scheme S-expressions ( lambda (x) ( f ( f x ) ) ),cs784 (Prasad),L6AST,3,Abstract Syntax (vs Concrete Syntax),lambda-exp,app-exp,var-exp,var-exp,var-exp,id,id,id,id,b

2、ody,rand,rand,app-exp,rator,rator,cs784 (Prasad),L6AST,4,Overview,Parse-expression,Unparse-expression,Interpreter,Concrete Syntax,Abstract Syntax,Results,cs784 (Prasad),L6AST,5,Representing Abstract Syntax with Records,(define-datatype expression expression? (var-exp(id symbol?)(lambda-exp(id symbol

3、?)(body expression?)(app-exp(rator expression?)(rand expression?),cs784 (Prasad),L6AST,6,(define parse-expression(lambda (datum)(cond(symbol? datum) (var-exp datum)(pair? datum)(if (eqv? (car datum) lambda)(lambda-exp (caadr datum)(parse-expression (caddr datum)(app-exp(parse-expression (car datum)(

4、parse-expression (cadr datum)(else (eopl:error parse-expression“Invalid concrete syntax s“ datum) ),Parse: Concrete to Abstract Syntax,cs784 (Prasad),L6AST,7, (current-directory “I:tkprasadcs784EOPL-CODEinterps“) (load “chez-init.scm“) (load “2-2-2.scm“) (parse-expression x) (var-exp x) (parse-expre

5、ssion (lambda (x) (f x) (lambda-exp x (app-exp (var-exp f) (var-exp x) (parse-expression 45) Error reported by parse-expression: Invalid concrete syntax 45 debuge (unparse-expression (lambda-exp x (app-exp (var-exp f) (var-exp x) (lambda (x) (f x),Example (Petite Scheme),cs784 (Prasad),L6AST,8,Examp

6、le (PLT Scheme),cs784 (Prasad),L6AST,9,Unparse: Abstract to Concrete Syntax,(define unparse-expression(lambda (exp)(cases expression exp(var-exp (id) id)(lambda-exp (id body) (list lambda (list id)(unparse-expression body) )(app-exp (rator rand)(list (unparse-expression rator)(unparse-expression ran

7、d) ) ),cs784 (Prasad),L6AST,10,Role of Induction and Recursion,Define data structures (infinite values) by induction. Seed elements. Closure operations. Define functions (operations) by recursion. Boundary/Basis case. Composite/Recursive case. Prove properties using structural induction. Basis case.

8、 Inductive step.,cs784 (Prasad),L6AST,11,Representing Environment,cs784 (Prasad),L6AST,12,Alternative 1,(define empty-env(lambda () ()(define extend-env(lambda (syms vals env)(cons (list syms vals) env) )(define apply-env(lambda (env sym)(if (null? env)(eopl:error apply-env “No binding for s“ sym)(l

9、et (syms (car (car env)(vals (cadr (car env)(env (cdr env)(let (pos (rib-find-position sym syms)(if (number? pos)(list-ref vals pos)(apply-env env sym) ),cs784 (Prasad),L6AST,13,Alternative 2,(define empty-env(lambda ()(lambda (sym) (eopl:error apply-env “No binding for s“ sym) ) )(define extend-env

10、(lambda (syms vals env)(lambda (sym)(let (pos (list-find-position sym syms)(if (number? pos)(list-ref vals pos)(apply-env env sym) ) )(define apply-env(lambda (env sym) (env sym) ) ),cs784 (Prasad),L6AST,14,Alternative 3,(define-datatype environment environment? (empty-env-record) (extended-env-reco

11、rd(syms (list-of symbol?)(vals (list-of scheme-value?)(env environment?)(define scheme-value? (lambda (v) #t),cs784 (Prasad),L6AST,15,(contd),(define empty-env(lambda ()(empty-env-record) )(define extend-env(lambda (syms vals env)(extended-env-record syms vals env)(define apply-env(lambda (env sym)(

12、cases environment env(empty-env-record ()(eopl:error apply-env “No binding for s“ sym)(extended-env-record (syms vals env)(let (pos (list-find-position sym syms)(if (number? pos)(list-ref vals pos)(apply-env env sym) ) ),cs784 (Prasad),L6AST,16,Queue,(define reset (lambda (q) (vector-ref q 0) (defin

13、e empty? (lambda (q) (vector-ref q 1) (define enqueue (lambda (q) (vector-ref q 2) (define dequeue (lambda (q) (vector-ref q 3)(define Q (create-queue) (enqueue Q) 55) (empty? Q) (dequeue Q) (empty? Q) (reset Q) (dequeue Q),cs784 (Prasad),L6AST,17,(define create-queue(lambda ()(let (q-in () (q-out (

14、)(letrec (reset-queue(lambda ()(set! q-in () (set! q-out () )(empty-queue?(lambda ()(and (null? q-in) (null? q-out) )(enqueue(lambda (x)(set! q-in (cons x q-in) )(dequeue(lambda ()(if (empty-queue?)(eopl:error dequeue “Not on an empty queue“)(begin(if (null? q-out)(begin(set! q-out (reverse q-in) (set! q-in ()(let (ans (car q-out)(set! q-out (cdr q-out)ans) )(vector reset-queue empty-queue? enqueue dequeue) ),