|
Jupyter at Bryn Mawr College |
|
|
| Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Notes | |||
Calc without Closures¶
Consider the final version of Calc, as given in Exam #2:
In [1]:
(define list-of
(lambda (f)
(lambda (ls)
(let loop ((ls ls))
(cond
((null? ls) #t)
((f (car ls)) (loop (cdr ls)))
(else #f))))))
(define procedure-or-var?
(lambda (exp)
(or (var-exp? exp)
(procedure-exp? exp))))
(define var-exp?
(lambda (exp)
(eq? (car exp) 'var-exp)))
(define procedure-exp?
(lambda (exp)
(eq? (car exp) 'procedure-exp)))
(define closure-exp?
(lambda (exp)
(eq? (car exp) 'closure-exp)))
(define operator?
(lambda (item)
(member item '(+ - * /))))
(define true?
(lambda (v)
(and (number? v)
(not (= v 0)))))
In [2]:
(define closure-exp->body
(lambda (closure)
(cadddr closure)))
(define closure-exp->parameters
(lambda (closure)
(caddr closure)))
(define closure-exp->env
(lambda (closure)
(cadr closure)))
In [3]:
(define-datatype
calc-exp calc-exp?
(lit-exp
(value number?))
(var-exp
(name symbol?))
(if-exp
(test-exp calc-exp?)
(then-exp calc-exp?)
(else-exp calc-exp?))
(procedure-exp
(parameters (list-of symbol?))
(body calc-exp?))
(closure-exp
(env list?)
(parameters (list-of symbol?))
(body calc-exp?))
(let-exp
(variables (list-of symbol?))
(values (list-of calc-exp?))
(body calc-exp?))
(assignment-exp
(variable symbol?)
(value calc-exp?))
(define-exp
(variable symbol?)
(value calc-exp?))
(app-exp
(procedure procedure-or-var?)
(args (list-of calc-exp?))))
In [4]:
(define parser
(lambda (exp)
(cond
((symbol? exp) (var-exp exp)) ;; apple
((number? exp) (lit-exp exp)) ;; 1.2
((eq? (car exp) 'lambda) ;; (lambda (a b c) a)
(procedure-exp
(cadr exp) (parser (caddr exp))))
((eq? (car exp) 'let) ;; (let ((x 1)) x)
(let-exp
(map car (cadr exp))
(map parser (map cadr (cadr exp)))
(parser (caddr exp))))
((eq? (car exp) 'if) ;; (if test then else)
(if-exp (parser (cadr exp))
(parser (caddr exp))
(parser (cadddr exp))))
((eq? (car exp) 'set!) ;; (set! x 1)
(assignment-exp
(cadr exp)
(parser (caddr exp))))
((and (= (length exp) 3) (operator? (cadr exp))) ;; infix
(app-exp (parser (cadr exp))
(list (parser (car exp))
(parser (caddr exp)))))
((eq? (car exp) 'define) ;; (define x 1)
(define-exp (cadr exp) (parser (caddr exp))))
(else (app-exp (parser (car exp)) ;; (+ 3 4)
(map parser (cdr exp)))))))
In [5]:
(import "math")
(define toplevel-env
(list (list (list 'pi math.pi)
(list 'e math.e)
(list '+ +)
(list '- -)
(list '* *)
(list '/ /)
(list 'list list)
(list '= (lambda (a b)
(if (and (number? a)
(number? b)
(= a b))
1 0)))
(list '< (lambda (a b) (if (< a b) 1 0)))
(list '> (lambda (a b) (if (> a b) 1 0)))
)))
(define extend-env!
(lambda (vars vals env)
(cond
((null? vars) env)
(else
(begin
(set-car! env (cons (list (car vars)
(car vals))
(car env)))
(extend-env! (cdr vars) (cdr vals) env))))))
(define extend-env
(lambda (vars vals env)
(cons (map (lambda items items) vars vals) env)))
In [6]:
(define lookup-binding
(lambda (name env search-first-only)
(cond
((null? env) #f)
(else (let ((frame (car env)))
(let ((binding (assq name frame)))
(if binding
binding
(if search-first-only
#f
(lookup-binding name (cdr env) #f)))))))))
In [7]:
(define evaluator
(lambda (ast env)
(record-case ast
(lit-exp (value) value)
(var-exp (name) (let ((binding (lookup-binding name env #f)))
(if binding
(cadr binding)
(error 'evaluator "no such variable: ~a" name))))
(procedure-exp (parameters body)
(closure-exp env parameters body))
(if-exp (test-exp then-exp else-exp)
(if (true? (evaluator test-exp env))
(evaluator then-exp env)
(evaluator else-exp env)))
(let-exp (variables values body)
(evaluator body
(cons (map list variables (map (lambda (e) (evaluator e env)) values))
env)))
(assignment-exp (variable value)
(begin
(set-car! (cdr (lookup-binding variable env #f))
(evaluator value env))
(cadr (lookup-binding variable env #f))))
(define-exp (variable value)
(let ((binding (lookup-binding variable env #t))
(v (evaluator value env)))
(if binding
(set-car! (cdr binding) v)
(begin
(extend-env! (list variable)
(list v)
env)
(void)))))
(app-exp (procedure args)
(applier (evaluator procedure env)
(map (lambda (e) (evaluator e env)) args)
env)))))
In [8]:
(define applier
(lambda (f values env)
(cond
((closure-exp? f)
(evaluator (closure-exp->body f)
(extend-env (closure-exp->parameters f)
values (closure-exp->env f))))
(else (apply f values)))))
In [9]:
(define calc
(lambda (exp)
(evaluator (parser exp) toplevel-env)))
In [ ]:
(calc '(define f (let ((x 42)) (lambda () x))))
In [11]:
(calc '(f))
Out[11]:
In [12]:
(calc '(define x 100))
In [13]:
(calc '(f))
Out[13]:
Let's take a look at where a closure is applied:
(define applier
(lambda (f values env)
(cond
((closure-exp? f)
(evaluator (closure-exp->body f)
(extend-env (closure-exp->parameters f)
values (closure-exp->env f))))
(else (apply f values)))))
In [14]:
(define applier
(lambda (f values env)
(cond
((closure-exp? f)
(evaluator (closure-exp->body f)
(extend-env (closure-exp->parameters f)
values env)))
(else (apply f values)))))
In [15]:
(calc '(define f (let ((x 42)) (lambda () x))))
In [16]:
(calc '(f))
Out[16]:
The x in the let is still a local variable, its just that it only exists dynamically, not statically.
lexical or static scope: used with closures; variables statically bound at compile/parse time ("early binding")
dynamic scope: variables dynamically bound at lookup/runtime ("late binding")
https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scope_vs._dynamic_scope
This means that lexically-bound variables don't need a lookup at all at runtime... variables could be directly connected to the association that they are bound with.
lexical address - instead of just marking a variable as a var-exp when parsed, it could be replaced with an address (in environment) of the value.
In [17]:
(parse '(let ((x 1)) x))
Out[17]:
In [25]:
(parse '(let ((x 1) (y 2)) y))
Out[25]:
In [26]:
(use-lexical-address)
Out[26]:
In [27]:
(use-lexical-address #f)
In [28]:
(parse '(let ((x 1)) x))
Out[28]:
In [29]:
(parse '(let ((x 1) (y 2)) y))
Out[29]: