Recursion II
Midterm on Friday
- We introduced
letrecexpressions to define recursive or mutually recursive functions in our defined language. BNF for the character syntax is:Potentially mutually recursive functions[expression] ::= letrec {[letrec-decl]}* in [expression] [letrec-decl] ::= [symbol]() = [expression] | [symbol]([symbol] {, [symbol]}*) = [expression]f1,...with parameter lists(x1,...),...and bodiesE1,...are defined inE1,...andEbyFree occurrences ofletrec f1(x1,...) = E1 ... in Ef1,...inE1,...and inEare bound toproc (x1,...) E1,....The application
is evaluated by evaluating(f1 a1...)E1in the environment of theletrecextended byf1,..., with free occurrences ofx1,...bound to the values ofa1,....The grammar for the concrete syntax is:and the(expression ("letrec" (arbno id "(" (separated-list id ",") ")" "=" expression) "in" expression) letrec-exp)define-datatypeforexpressioncontains the clause(letrec-exp (proc-names (list-of symbol?)) (idss (list-of (list-of symbol?))) (bodies (list-of expression?)) (letrec-body expression?))- For example, a recursive definition and application of times4 could be expressed
Andletrec times4(x) = if zero?(x) then 0 else +(4, (times4 sub1(x))) in (times4 3)defines recursive functionsletrec f(x) = if zero?(x) then 1 else *(2, (f sub1(x))) g(x, y) = if zero?(x) then y else (g sub1(x) *(2, y)) h(x) = (g x 1) in list((f 5), (g 5 1), (h 5))fandg, andhis terms ofg, and uses them in the body of theletrec.What do these functions compute?
What is the value of the expression?
Compare the concrete, list and abstract syntax for these functions:letrec f(x) = if zero?(x) then 1 else *(2, (f sub1(x))) g(x, y) = if zero?(x) then y else (g sub1(x) *(2, y)) h(x) = (g x 1) in list((f 5), (g 5 1), (h 5)) or (letrec ([f (lambda (x) (if (zero? x) 1 (* 2 (f (sub1 x)))))] [g (lambda (x y) (if (zero? x) y (g (sub1 x) (* 2 y))))] [h (lambda (x) (g x 1))]) (list (f 5) (g 5 1) (h 5))) or (a-program (letrec-exp (f g h) ((x) (x y) (x)) ((if-exp (primapp-exp (zero-prim) ((var-exp x))) (lit-exp 1) (primapp-exp (mult-prim) ((lit-exp 2) (app-exp (var-exp f) ((primapp-exp (decr-prim) ((var-exp x)))))))) (if-exp (primapp-exp (zero-prim) ((var-exp x))) (var-exp y) (app-exp (var-exp g) ((primapp-exp (decr-prim) ((var-exp x))) (primapp-exp (mult-prim) ((lit-exp 2) (var-exp y)))))) (app-exp (var-exp g) ((var-exp x) (lit-exp 1)))) (primapp-exp (list-prim) ((app-exp (var-exp f) ((lit-exp 5))) (app-exp (var-exp g) ((lit-exp 5) (lit-exp 1))) (app-exp (var-exp h) ((lit-exp 5))))))) => (32 32 32)- It is instructive to evaluate
with tracing ofletrec f(x) = if zero?(x) then 1 else *(2, (f sub1(x))) g(x, y) = if zero?(x) then y else (g sub1(x) *(2, y)) h(x) = (g x 1) in (g 0 1)eval-randsturned on.
eval-randsis called to evaluate the operands ofThere is no recursive call -- the value of y is returned.
- (g 0 1) in the init env extended by the recursive env, and of
- zero?(x) in the recursive env extended by [x = 0, y = 1]
Here is the trace:We have used an|(eval-rands ((lit-exp 0) (lit-exp 1)) (extended-env-recursively-record (f g h) #3((x) (x y) (x)) #3((if-exp (primapp-exp (zero-prim) ((var-exp x))) (lit-exp 1) (primapp-exp (mult-prim) ((lit-exp 2) (app-exp (var-exp f) ((primapp-exp (decr-prim) ((var-exp x)))))))) (if-exp (primapp-exp (zero-prim) ((var-exp x))) (var-exp y) (app-exp (var-exp g) ((primapp-exp (decr-prim) ((var-exp x))) (primapp-exp (mult-prim) ((lit-exp 2) (var-exp y)))))) (app-exp (var-exp g) ((var-exp x) (lit-exp 1)))) (extended-env-record (i v x emptylist) #4(1 5 10 ()) (empty-env-record)))) |(0 1) |(eval-rands ((var-exp x)) (extended-env-record (x y) #2(0 1) (extended-env-recursively-record (f g h) #3((x) (x y) (x)) #3((if-exp (primapp-exp (zero-prim) ((var-exp x))) (lit-exp 1) (primapp-exp (mult-prim) ((lit-exp 2) (app-exp (var-exp f) ((primapp-exp (decr-prim) ((var-exp x)))))))) (if-exp (primapp-exp (zero-prim) ((var-exp x))) (var-exp y) (app-exp (var-exp g) ((primapp-exp (decr-prim) ((var-exp x))) (primapp-exp (mult-prim) ((lit-exp 2) (var-exp y)))))) (app-exp (var-exp g) ((var-exp x) (lit-exp 1)))) (extended-env-record (i v x emptylist) #4(1 5 10 ()) (empty-env-record))))) |(0) 1extended-env-recursively-recordto represent a recursive environment.
- How is a
letrec-expevaluated?
- The clause in
eval-expressioncan be justThe magic is in the definition of(letrec-exp (proc-names idss bodies letrec-body) (eval-expression letrec-body (extend-env-recursively proc-names idss bodies env)))extend-env-recursively.
- We choose to extend the
environmentdata type.(define-datatype environment environment? (empty-env-record) (extended-env-record (syms (list-of symbol?)) (vec vector?) (env environment?)) (extended-env-recursively-record (proc-names (list-of symbol?)) (ids-vec vector?) (body-vec vector?) (env environment?)))extend-env-recursivelycreates anextended-env-recursively-record.The value of a recursively defined procedure will be a
closure, but we choose to create the closure when the value of the function is requested inapply-exp.(define extend-env-recursively (lambda (proc-names idss bodies env) (extended-env-recursively-record proc-names (list->vector idss) (list->vector bodies) env)))- The semantics is encapsulated in
apply-env.A recursive function is evaluated by creating a
closurewhose environment is its environment of definition extended by the recursive environment containing the function.A variable which is not one of the recursively defined functions is looked up in the environment of the
letrec.(define apply-env (lambda (env sym) (cases environment env (empty-env-record () (error 'empty-env "no association for symbol ~s" sym)) (extended-env-record (syms vec env) (let ((position (list-find-position sym syms))) (if (number? position) (vector-ref vec position) (apply-env env sym)))) (extended-env-recursively-record (proc-names ids-vec body-vec env0) (let ((position (list-find-position sym proc-names))) (if (number? position) (closure (vector-ref ids-vec position) (vector-ref body-vec position) env) (apply-env env0 sym)))))))- interp3-6sol.scm