CS440 Programming Languages - Machine Problems 1: Recursion, Higher Order Functions and Meta-Circular Evaluator
CS 440 MP1
Overview
In this first machine problem you will be implementing a number of different Racket functions to get a feel for the language and a taste of language implementation.
All the code you write for this machine problem will go into the "mp1.rkt" file, found in the private source repository created when you accepted my GitHub invitation. In that file you will find stubs for each of the programming exercises described below.
Exercises
Part 1: Recursion and Lists (16 points)
First, let's get warmed up by writing a handful of functions, all of which will use recursion and operate on lists. rotate: takes an integer n ≥ 0 and a list and "rotates" n elements off the front of the list onto the end. E.g.,
lookup: treats a list of pairs as a lookup structure (aka "associative list"); when given a key and a list, it finds the pair whose car matches the key (using equal?) and returns the associated cdr. If no match exists, returns #f. E.g.,
> (rotate 3 '(1 2 3 4 5 6 7 8 9)) '(4 5 6 7 8 9 1 2 3)
> (rotate 2 '((a) (b (c)) (d e))) '((d e) (a) (b (c)))
> (lookup 'a '((a . apple) (b . bee) (c . cat))) 'apple
> (lookup 2 '((1 . "one") (2 "two" "three") (4 "four" "five"))) '("two" "three")
> (lookup 'foo '((a . apple) (2 . "two"))) #f
update: updates or inserts a new pair into a lookup list (as used by lookup) reflecting a provided key/value mapping. (The location of a newly inserted pair doesn't matter.) E.g.,
> (update 'a 'apple '((b . bee) (c . cat))) '((b . bee) (c . cat) (a . apple))
> (update 'a "auto" '((a . apple) (b . bee) (c . cat))) '((a . "auto") (b . bee) (c . cat))
> (update 1 (list 100 200 300) '()) '((1 100 200 300))
equal-shape?: returns #t if two pairs have the same "shape", i.e., if their structure consisting of zero or more nested pairs is identical; returns #f otherwise. E.g.,
> (equal-shape? '(1 2 3) '(2 3 4)) #t
Part 2: Higher Order Functions (16 points)
my-curry: implement your own version of curry. Your version should behave identically to curry, but need only work on procedures with fixed arity. E.g.,
Implement tail recursive versions of map and filter (found in "mp1.rkt" as my-map and my-filter).
make-object: creates and returns a rudimentary "object" as a closure over an associative list containing attributes. The returned closure
(i.e., function) responds to three "messages": get, set, and update.
get takes an attribute key, whose value is returned (if it exists).
set takes an attribute key and value, which are used to update the associative list
update takes an attribute key and a function which is used to update the associative list by applying it to the current value
make-object takes one argument, the initial name of the object (associated with the attribute key 'name). E.g.,
> ((my-curry even?) 2)
#t
> (((my-curry cons) 1) 2)
'(1 . 2)
> ((my-curry cons 1) 2)
'(1 . 2)
> (define obj (make-object "foo"))
> (obj 'get 'name)
"foo"
> (obj 'set 'name 'bar)
> (obj 'get 'name)
'bar
> (obj 'set 'x 42)
> (obj 'update 'x (lambda (n) (* n 100)))
> (obj 'get 'x)
4200
Part 3: Meta-circular Evaluator (10 points)
In this part you will implement your own limited version of eval. Your version will only understand a very limited subset of Racket, with expressions of the following kind:
Note that a lambda may only have one parameter.
Your evaluation function will be passed s-expressions of the above form (the base form will always be a lambda), and should return corresponding Racket values. Because your evaluator will use Racket features to represent and implement this subset of the Racket language, it
expr ::= (lambda (var) expr) | (expr expr)
| var
; lambda (function) definition
; function application
; variable reference
> (equal-shape? '(1 2 3) '(2 3 4 5))
#f
> (equal-shape? '(1 (a b) ((#f)) "d" e)
'(2 ("a" "b") ((100)) f g))
#t
> (equal-shape? '(a (b . c) d) '(a (b c) d))
#f
is a so-called meta-circular evaluator.
To implement this, you will need to take apart the input to your evaluator and determine which form it is before building the corresponding Racket form. In order to implement variables (which are just symbols in the input), you will also need to keep track of their bindings in an environment -- we recommend using the associative list which you implemented above.
Here's the evaluator in action:
We've stubbed out portions of the evaluator for you as a guide. Feel free to delete/keep what you wish.
Part 4: Free Variables (8 points)
Lastly, you will implement a function free, which will take the same types of expressions understood by your evaluator, but will instead return a list of all the free variables found in those expressions (order doesn't matter).
You will likely be able to reuse much of your code from part 3! Some sample results:
> ((my-eval '(lambda (x) x)) 10) 10
> (((my-eval '(lambda (f) (lambda (x) (f (f x))))) sqr) 5) 625
> (free 'a)
'(a)
> (free '(x y))
'(x y)
> (free '(lambda (x) x))
'()
> (free '(lambda (x) (x y)))
'(y)
> (free '(lambda (x) (w (lambda (w) (x y)))))
'(w y)
Testing
We've provided you with test suites for most of the exercises in the "mp1-tests.rkt" source file. If you open the file you'll find that there are a bunch of definitions that looks like this:
(test-case "test-make-object"
(define obj (make-object 'foo))
(obj 'set 'name 'bar)
(obj 'set 'x 42)
(obj 'update 'x (lambda (x) (* x 100)))
(obj 'set 'y 100)
(check-equal? (obj 'get 'name) 'bar)
(check-equal? (obj 'get 'x) 4200)
(check-equal? (obj 'get 'y) 100))
This defines a test case (here, for the make-object function). The check-equal? calls at the end of the test case are assertions. If they fail, they will produce out errors that looks like this:
--------------------
test-make-object FAILURE
You can run the tests by loading the file in DrRacket and evaluating it. Note that while passing all the tests is a good indication that your solutions are on the right track, we don't guarantee exhaustive test coverage, nor that passing all tests will results in 100% on the assignment!
Submission
When you are done with your work, simply commit your changes and push them to our shared private GitHub repository. Please note that your submission date will be based on your most recent push (unless you let us know to grade an earlier version).
name: check-equal?
location: mps/mp1/mp1-test.rkt:14:2
actual: 'foo
expected: 'bar
--------------------
