Assignment 0: Warm-up with Racket
Your task on Assignment 0 is to start learning the Racket programming language. You will demonstrate this by submitting a module that provides four simple functions. First, start by installing (or updating your system to) Racket 6.10 and checking that it works:
$ racket Welcome to Racket v6.10. > (+ 1 2) 3 > '(1 2 3) '(1 2 3) > ((lambda (x) (* 4 x)) 3) 12 >
You can also try using the DrRacket IDE which provides syntax highlighting and debugging facilities with a built-in REPL.
Racket Resources
I recommend you get started by learning Racket broadly, on your own terms. One you’ve started, try entering into a free-form
dialogue with the Racket REPL!
See what works and what doesn’t—
Here are some good resources you might want to use:
Your Assignment
Your assignment is to submit a Racket module that provides four functions: my-reverse, my-append, interp, and free. On all your assignments, I ask that you include your full name in a comment near the top, and sign the bottom with a comment (also providing your name) as per UMD’s Academic Integrity policy.
A stubbed-out version of the assignment looks like:
#lang racket ; by Firstname Lastname (provide my-reverse my-append interp free) (define (my-reverse lst) '()) (define (my-append lst0 lst1) '()) (define (interp exp) '()) (define (free exp) '()) ; I, Firstname Lastname, pledge on my honor that I have not given or ; received any unauthorized assistance on this assignment.
The first two functions may assume their argument(s) satisfy the list? predicate and should use basic list manipulation functions such as cons, car, cdr, null? to reverse a list or append two lists, respectively. In case it doesn’t go without saying, these functions should match the behavior of their standard Racket counterparts, but may not be defined in terms of them, e.g.,
(define (my-reverse lst) (reverse lst)) (define my-append append)
Code like this will earn a zero. Do not use the reverse, append, or eval library functions in your solution. This is not to say you shouldn’t leverage other standard functions however; for example, can either of these be written in terms of foldl/foldr?
The second pair of functions operate over Racket lists that follow the grammar for the 3-form untyped λ-calculus:
exp ::= (lambda (x) exp) ; lambda abstraction | (exp exp) ; lambda application | x ; variable reference
For example, an identity function applied to itself can be written as a quoted list:
'((lambda (x) x) (lambda (y) y)) ; which is the same as: (list (list 'lambda (list 'x) 'x) (list 'lambda (list 'y) 'y))
The function interp should implement a meta-circular interpreter for the input language, the pure lambda-calculus. This means values in the input language (i.e., lambdas) should be modeled using that same feature in the host language (lambdas). The code above would thus return an identity function that works in Racket when interpreted:
$ racket Welcome to Racket v6.10. > (require "solution.rkt") > (define id (interp '((lambda (x) x) (lambda (y) y)))) > (id 5) 5 > ((id (lambda (z) z)) #t) #t
Your function will likely use a match form to case-split on the three kinds of expressions: lambda abstractions, applications, and variables. In a meta-circular interpreter, variables return a value in scope for variables, lambda abstractions return a racket lambda that may be applied on a value to evaluate its body with a new binding, and an application evaluates its function and argument, applying the former to the latter. If you get stuck, try refreshing your memory on the lambda calculus first. As this language is a proper subset of racket, you can use racket to experiment with terms and see what they yield.
The function free should accept an expression in this same language and return a list of symbols reporting its free variables. These are the symbols in the expression that, if reached during an evaluation of interp, will not have a value and are not in scope. These are the variables x that are not contained in the scope of any (lambda (x) ...). For example:
$ racket Welcome to Racket v6.10. > (require "solution.rkt") > (free '(lambda (f) (f a))) '(a)
At a high level, this function should pattern match on each form in the grammer and recur on subexpressions to find free variables. Consider employing Racket’s list and list-searching functions (cons, member, etc) or hash-set functions (set, set-add, set->list, etc) for tracking the symbols in scope at each point in your traversal.
You may download a stubbed out version of this code with a testing aparatus and some public tests. To run all tests, provide the testing script the argument all, to ask it for a list of open tests you can run, provide no arguments, and to run a specific test, provide its name as an argument.
A correct solution where your solution is located at ./solution.rkt would then look like:
$ racket tests.rkt Avaliable tests: reverse-0, append-0, append-1, interp-lambda-I, interp-app-0, free-0 $ racket tests.rkt append-0 Test passed! $ racket tests.rkt all Score on available tests (may not include release tests or private tests): 100.0% $
Six out of eleven tests are open source and included in the archive linked. No tests on the submit server will be private (the remaining five tests are marked as ’release’ tests and may be attempted before the deadline) so you will be able to find out what your final grade on the assignment will be and can resubmit as many times as you need to.