|
Jupyter at Bryn Mawr College |
|
|
| Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Assignments | |||
Principles of Programming Languages¶
Blank, Fall 2012¶
Assignment #4: Calculator Language with If-exp and User-defined Functions¶
Due: Thursday, October 9, 2014¶
This assignment is designed to:
- Understand our language as it is so far
- Explore Scheme procedures and variables
- Add if-exp to our language
- Add procedure-exp to our language
Solution to Assignment #3¶
(define list-of
"
list-of takes a function f and returns a function.
The returned function takes a list of items and applies
f to each. If (f item) is true for all items, then the
function returns #t, otherwise #f.
"
(lambda (f)
(lambda (ls)
(let loop ((ls ls))
(cond
((null? ls) #t)
((f (car ls)) (loop (cdr ls)))
(else #f))))))
We add the 3 different ways to call functions, and the variable-exp to the calc-exp:
(define-datatype
calc-exp calc-exp?
(literal-exp
(value number?))
(var-exp
(name symbol?))
(app-exp
(operator symbol?)
(arg1 calc-exp?)
(arg2 calc-exp?))
(func-call-exp
(function symbol?)
(arg1 calc-exp?)
(arg2 calc-exp?))
(func-call-var-exp
(function symbol?)
(args (list-of calc-exp?))))
We add these to the parser, hard-coding the 2-argument functions min and max, and the variable number of argument functions, avg and sum. Otherwise, if the list is of length 3, we assume that it is an application-exp:
(define parser
"Takes an s-expression representing our concrete syntax; returns AST"
(lambda (exp)
(cond
((symbol? exp) (var-exp exp))
((number? exp) (literal-exp exp))
((list? exp)
(cond
((eq? (car exp) 'min) (func-call-exp 'min
(parser (cadr exp))
(parser (caddr exp))))
((eq? (car exp) 'max) (func-call-exp 'max
(parser (cadr exp))
(parser (caddr exp))))
((eq? (car exp) 'avg) (func-call-var-exp 'avg
(map parser (cdr exp))))
((eq? (car exp) 'sum) (func-call-var-exp 'sum
(map parser (cdr exp))))
((= (length exp) 3) (app-exp (cadr exp)
(parser (car exp))
(parser (caddr exp))))
(else (error 'parser "Invalid concrete syntax: ~a" exp))))
(else (error 'parser "Invalid concrete syntax: ~a" exp)))))
We define some helper functions that we will need in the evaluator: avg and lookup:
(define avg
(lambda (args)
(/ (sum args) (length args))))
(define lookup
(lambda (name env)
(let ((binding (assq name env)))
(if binding
(cadr binding)
(error 'lookup "No such varibale: ~a" name)))))
Finally, in the evaluator, we eval the AST:
(define evaluator
(lambda (ast env)
(record-case ast
(literal-exp (value) value)
(var-exp (name) (lookup name env))
(app-exp (operator arg1 arg2)
(cond
((eq? operator '+) (+ (evaluator arg1 env)
(evaluator arg2 env)))
((eq? operator '-) (- (evaluator arg1 env)
(evaluator arg2 env)))
((eq? operator '*) (* (evaluator arg1 env)
(evaluator arg2 env)))
((eq? operator '/) (/ (evaluator arg1 env)
(evaluator arg2 env)))))
(func-call-exp (function arg1 arg2)
(cond
((eq? function 'min) (min (evaluator arg1 env)
(evaluator arg2 env)))
((eq? function 'max) (max (evaluator arg1 env)
(evaluator arg2 env)))))
(func-call-var-exp (function args)
(cond
((eq? function 'avg) (avg (map (lambda (e) (evaluator e env))
args)))
((eq? function 'sum) (sum (map (lambda (e) (evaluator e env))
args))))))))
Now, we define an environment and a utility function to make testing easy:
(import "math")
(define env (list (list 'pi math.pi)
(list 'e math.e)))
(define calc
(lambda (exp)
(evaluator (parser exp) env)))
(define test
(lambda (exp)
(printf "~a -> ~a~%" exp (calc exp))))
Now, test it out:
(test 1)
(test '(1 + 2))
(test '(min 56 12))
(test '(avg 4 5 6 7 8))
(test '(avg 4 5 6 7 8 9))
(test 'e)
(test 'pi)
(test '(avg pi e (1 + (8 * 7)) (sum 5 6 3) (min 6 2) (max 9 6)))
Summary and Next steps¶
The beginning of our calculator language looks very good! It can do at least as much as a good calculator, maybe more: it has in-fix operators, some specific functions, and variables.
But the implementation of the different functions and operators was pretty messy. The way that we had to write the parser was a bit limiting. For example, we might have some ambiguity in the future:
In [A]: (new-function + 34)
In [B]: (min + 23)
In [C]: (34 f 56)In A, our parser may find that to be addition, when we really meant it to be an application of the new-function.
In B, we can't have a variable named min or it would through off our parser.
In C, we can't have a variable f bound to +, because our parser wouldn't know that that is a plus-exp.
Perhaps we should consider an concrete syntax like Scheme's. Then all of the functions would appear in the initial position.
Let's leave that for the moment. In fact, let's remove all of the applications of functions, and think about what it would take for the user to be able to write their own functions.
As a warm up, let's add if-exp to a stripped-down parser/evaluator.
Adding an if-exp¶
We know that an if-exp in Scheme is a "special form"... it short-circuits evaluation of the elements, not evaluating the branch that it doesn't need to.
Let's define what the parser and evaluator should give us:
;; (parser '(if 1 2 3))
;; (if-exp (lit-exp 1) (lit-exp 2) (lit-exp 3))
;; (calc '(if 1 2 3))
;; 2
;; (calc '(if 0 2 3))
;; 3
Let us pare-down the datatype to the bare minimum to focus on new forms:
(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?)))
The parser is simply:
(define parser
(lambda (exp)
(cond
((symbol? exp) (var-exp exp))
((number? exp) (lit-exp exp))
((eq? (car exp) 'if) (if-exp (parser (cadr exp))
(parser (caddr exp))
(parser (cadddr exp)))))))
(parser '(if 1 2 3))
Test out the parser to make sure it is recursively well-defined.
To use our new if-exp, we need to have the ability to test whether an expression is true. We could introduce a boolean type. However, for the moment let's just use numbers to represent booleans. We define false to be 0; anything else will be true:
(define true?
(lambda (v)
(not (= v 0))))
(true? 0)
(true? 1)
(true? 42)
Our evaluator handling if-exp:
(define evaluator
(lambda (ast env)
(record-case ast
(lit-exp (value) value)
(if-exp (test-exp then-exp else-exp)
(if (true? (evaluator test-exp env))
(evaluator then-exp env)
(evaluator else-exp env))))))
(calc '(if 1 2 3))
(calc '(if 0 2 3))
Extensively test if-exp with recursive expressions.
Procedures and Closures¶
Now, let's think about procedures. Let's examine Scheme's procedures, and how they handle variables that are defined and undefined.
We can define procedures without worrying if everything is defined:
(lambda () x)
Oh, but we can't use that unless we have a way of later calling it. Note that in Scheme, you can define a function in one place (in one "environment") but use it in another.
(define f (lambda () x))
(f)
But, we can later put an x in the "global environment" and it will work:
(define x 3)
(f)
(define x 5)
(f)
Let's see what happens if we evaluate f with a "local" variable x:
(let ((x 7))
(f))
Interesting! x was still found in the global environment... it didn't even look in the local variables, but went straight to the globals.
Now let's try the opposite: what happens if we define a local variable, then return a function that references a variable from that local environment:
(define f (let ((x 42))
(lambda () x)))
What happens if we call it:
(f)
Interesting! Scheme remembered that x was 42. Let's see if we can change the value of x:
(define x 7)
(f)
Very interesting! When a lambda expression is evaluated, it "captures" the bindings of all of the defined variables. For those that aren't defined, those variables are unbound (aka "free"), and Scheme will look for their values in the "toplevel" environment dynamically at runtime.
So, a free variable:
(define f (lambda () q))
Is not bound to anything:
(f)
And can't be found in a local environment:
(let ((q 4))
(f))
But can, in the toplevel environment:
(define q 5)
(f)
Let's now see if we can add such behavior to our Calc language. We start by defining our concrete syntax, and the AST that it will parse into:
;; (parser '(func (n) n))
;; (procedure-exp (n) (var-exp n))
So, func is lambda.
;; (parser '((func (n) n) 42))
;; (app-exp (procedure-exp (n) (var-exp n)))
Great! But when we evaluate a procedure-exp, we need somehow to be able to "capture" all of those defined variables. We can do that by simply sticking the environment as it exists at that time into a new form called a "closure". A closure is nothing more than a procedure-exp with the current environment stuck in there as well:
;; (calc '(func (n) n))
;; (closure-exp env (n) (var-exp n))
Finally, we want to evaluate a function: we call it, and pass in arguments to be bound to variables:
;; (calc '((func (n) n) 42))
;; 42
We need a few helper functions:
(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)))
We define these new special forms:
(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?))
(app-exp
(procedure procedure-or-var?)
(args (list-of calc-exp?))))
The parser is pretty straightforward:
(define parser
(lambda (exp)
(cond
((symbol? exp) (var-exp exp))
((number? exp) (lit-exp exp))
((eq? (car exp) 'func) (procedure-exp
(cadr exp)
(parser (caddr exp))))
((eq? (car exp) 'if) (if-exp (parser (cadr exp))
(parser (caddr exp))
(parser (cadddr exp))))
(else (app-exp (parser (car exp))
(map parser (cdr exp)))))))
(parser '((func (n) 1) 4))
The evaluator is also fairly easy, although we introduce a new function applier that will apply whatever function we give it to a list of evaluated args. Notice that a procedure-exp evaluates to a closure-exp, which is just a procedure-exp with the current environment injected into it:
(define evaluator
(lambda (ast env)
(record-case ast
(lit-exp (value) value)
(var-exp (name) (lookup name env))
(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)))
(app-exp (procedure args)
(applier (evaluator procedure env) (map (lambda (e) (evaluator e env)) args) env)))))
When we evaluate an expression like ((func (n) n) 5) we need to be able to extend the environment with n bound to 5. To do that, all we need to do is cons (n 5) onto the environment, and use the extended environment:
(define extend-env
(lambda (vars vals env)
(cond
((null? vars) env)
(else (extend-env (cdr vars) (cdr vals)
(cons (list (car vars) (car vals)) env))))))
(extend-env '(a) '(1) env)
(extend-env '(a b c) '(1 2 3) env)
Notice that the environment doesn't change forever... it is still the same:
env
Finally, we are ready to apply our functions. We need a couple of helper functions to extract the parts of the closure datatype. (These should be defined when we execute define-datatype. An oversight!)
(define closure-exp->body
(lambda (closure)
(cadddr closure)))
(define closure-exp->parameters
(lambda (closure)
(caddr closure)))
Applier will then take a closure, extend the environment with the parameters bound to the arguments, and then evaluate the body of the closure:
(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)))))
(calc '((func (n) n) 4))
Yes, it works! Applier had actually two cases: one the closure that we have just defined, and the "else". We allow Calc functions to also be Scheme functions. Cheat! Well, yes. But that means that we can put Scheme functions in the environment, and they will work in our language:
;; First, we define those things that can't be defined in terms of others:
(define env (list (list 'pi math.pi)
(list 'e math.e)
(list '+ +)
(list '- -)
(list '* *)
(list 'list list)
(list '= (lambda (a b) (if (= a b) 1 0)))
(list '< (lambda (a b) (if (< a b) 1 0)))
(list '> (lambda (a b) (if (> a b) 1 0)))
))
;; Next, we extend-env with those things that can use the previous things:
(set! env (extend-env '(min max) (list
(evaluator (parser '(func (a b) (if (< a b) a b))) env)
(evaluator (parser '(func (a b) (if (> a b) a b))) env)
) env))
env
The above defines our env as before, first defining everything that we need as primitives. But we can define min and max in terms of less-than and greater-than, which are already defined. Note that less-than and greater-than can't be the Scheme versions directly, because they must return 0 and 1---our "booleans". They can't return #t and #f, because those don't exist in Calc language.
We set! the env to be the extended env, with min and max now defined.
Test away!
(calc '((func (a b) (list a b)) 1 2))
(calc '((func (n) (max 5 (max 6 (if n 100 4)))) 0))
(calc '((func (n) (max 5 (max 6 (if n 100 4)))) 1))
(calc '((func (n m) (if (< n m) n m)) 6 5))
This language should behavior very similarly to Scheme. You can write lot's of different kinds of functions.
Can you write factorial? Try!
Here is a version, except what go in the position of ???:
;; (calc '((func (n) (if (= n 1) 1 (* n (??? (- n 1))))) 5)
The problem is that the only way of naming things (currently) is through func. We don't have a "define".
But wait! What if we passed in factorial as another parameter:
;; (calc '((func (n factorial) (if (= n 1) 1 (* n (factorial (- n 1))))) 5 factorial))
But we don't have factorial... that is what we are defining. Wait! We just defined it. The problem is that we don't have a name for it. But we do have code for it... exactly what we just wrote. So, we can't pass it in by name, but we can pass it in by code... just copy it!
(calc '((func (n factorial) (if (= n 1) 1 (* n (factorial (- n 1) factorial))))
5
(func (n factorial) (if (= n 1) 1 (* n (factorial (- n 1) factorial))))))
Woot! We even have recursion, even though we can't name our recursive function.
Next steps¶
- Add
avgandsumback to the language, but do it by extending the environment rather than changing the language. - Define a Scheme procedure named
operator?(given a symbol, return #t if that symbol is an in-fix operator) and use it in the parser to allow in-fix operators (even with the caveats above). But, only the parser/concreate-syntax needs to change, not the evaluator/AST. That is, even though these operators will be in-fix, they are still just functions. - Add the in-fix operators from Assignment #3: +, -, *, /, and other operators you may have added.
- Study how we extended the environment with
(func (x y z) body). - Add local variables to Calc, using syntax similar to
(let ((x 1)) x). That is:(let ((VAR VALUE)...) BODY). It will use extend-env, and be somewhat similar toapplier. - Add an assignment-exp to Calc to allow you to change values of a variable, like
(set! x (+ x 1)). - We can't add
(define variable value)yet because we don't have the idea of a "toplevel" environment. We'll add that in class next Tuesday. How will that affect writing recursive functions?