Homework 4 (Due Monday
...
9/
...
29/
...
2022 at 11:59pm)
To submit this assignment, simply upload the files in your GitHub repository to you GitHub Classroom repository for this assignment (as you have done for earlier assignments). In contrast to Assignments 1 and 2 where you could put the programs for all problems in a single file (HW01.rkt for Assignment 1 and HW02.rkt for Assignment 2), you must store the solution to each problem in a separate .rkt
file: , namely HW04-1.rkt
, HW04-2.rkt
, HW04-3.rkt
, and HW04-4.rkt
(if you do the extra credit problem) for problems 1, 2, 3, and 4 (extra credit). Unfortunately, none of the languages supported by DrRacket will allow these files to be combined. The Pretty Big Racket language allows top-level indentifiers (functions and variablesidentifiers (variable names) to be redefined, but it does not support check-expect
. All of the student languages—which are the only ones that support check-expect—
prohibit redefinition of identifiers.
Embed answers any answer text that are is not program text executable in a DrRacket block comment or block commenting brackets (#| and |#).
...
- a number
n
, - a sum
(make-sum ae1 ae2)
, - a product
(make-prod ae1 ae2)
, - a difference
(make-diff ae1 ae2)
, or - a quotient
(make-quot ae1 ae2)
where n
is a number (as defined in Racket number), and ae1
and ae2
are ArithE
xpr
s.
The following 4 exercises involve the data type ArithE
xpr
. If you are asked to write a function(s), follow the design recipe: contract, purpose, examples/tests, template instantiation, code, testing (which happens automatically when the examples are given in presented using (check-expect ...)
form ). Follow the same recipe for any help function that you introduce. You may use any of the library functions shown in class lectures including append
.
- (40 pts.) Write an evaluator for arithmetic expressions as follows:
- Write the (function) template for A
rithExpr
Write a function
to-list
that maps an ArithExpr
to the corresponding "list" representation in Racket. Numbers are unchanged. Some other examples include:
Note: youCode Block (to-list 12) => 12 (to-list (make-sum (make-prod 4 7) 25)) => '(+ (* 4 7) 25) (to-list (make-quot (make-diff 4 7) 25)) => '(/ (- 4 7) 25)
Notes:
The notation
'(+ (* 4 7) 25)
abbreviates(list '+ (list '* 4 7) 25)
.You need to define the output type (named RacketE
xpr
) for this function, but you can omit the template because this assignment does not include any functions that process this type. There are several mathematically distinct definitions that are correct. Some are more restrictive (narrower) than others but all our correct.The notation
'(+ (* 4 7) 25)
abbreviates(list '+ (list '* 4 7) 25)
.
- Write a function
eval: ArithExpr -> number
that evaluates an ArithExpr
. Your evaluator should produce exactly the same result for an ArithExpr E
that Racket evaluation would produce for the list representation representation(to-list E)
.
- Write the (function) template for A
- (40 pts.) Extend the definition of A
rithExpr
as follows:- Add a clause for variables represented as Racket symbols.
- Write the (function) template for this extended definition; it should similar to your template for
ArithExpr
from Problem 1. - Modify your definition of
to-list
to support the new expanded definition ofArithExpr
. Given the Racket structure definition:
Code Block (define-structure binding (var val))
a
binding
is(make-binding s n)
wheres
is a symbol andn
is a number and an . Anenvironment
is abinding-list
(list-of binding)
. Write a (function) template for processing anenvironment
.- Define a top-level variable (constant) variable
empty-env
that is bound to the empty environment containing no bindings (i.e., the empty list). Note thatempty-env
is really a constant since variables cannot be rebound in our functional subset of Racket. Write a function
extend
that takes environmentenv
, a symbols
, and a numbern
, and returns an extended environment identical toenv
except that it adds the additional binding ofs
ton
.
The definition ofextend
is trivial; it requires no recursion. As a result,extend
satisfies the invariantCode Block (check-expect (extend empty-env s n) (list (make-binding s n)))
where
s
is any symbol andn
is any number. Hence,Code Block (extend empty-env 'a 4) => (list (make-binding 'a 4))
In the remainder of the problem, use
empty-env
andextend
to define example environments for test cases.- Write a function
lookup
that takes a symbols
and an environmentenv
and returns the firstbinding
inenv
with avar
component that equalss
. If no match is found,lookup
returns empty. Note that the return type oflookup
is not simplybinding
because it can returnempty
. Define the a new union type calledoption-binding
for the the return type. You do not need to write a template for this type since it is trivial. Write a new
eval
function for the new expanded definition of ArithExpr
. The neweval
takes two arguments: an ArithExpr E
to evaluate and anenvironment env
specifying the values of free variables inE
. For example,Code Block (eval 'x (extend empty-env 'x 17)) => 17 (eval (make-prod 4 7) (extend empty-env 'x 17)) = 28 (eval 'y (extend empty-env 'x 17)) => some form of run-time error
If an A
rithExpr E
contains a free variable that is not bound in theenvironment env
, then(eval E env)
will naturally produce some form of run-time error if you have correctly codedeval
. Do not explicitly test for this form of error.
- (20 pts.) An
environment
is really a finite function (a finite set of ordered pairs). It is finite in the sense that it can be completely defined by a finite table, which is not true of nearly all the primitive and library functions in Racket (and other programming languages). Even the identity function is not finite. For the purpose of this exercise, we redefine the typeenvironment
as(symbol -> option-binding)
.- Rewrite
eval
to useenvironment
defined as a finite function in(symbol -> option-binding)
instead of as a(list-of option-binding)
. If you cleanly coded your definition ofeval
in the preceding problem usinglookup
,make-binding
, andextend
, all that you have to do to your solution to the previous problem is redefine the bindings oflookup
,empty-env
, andextend
, and revise your test cases forextend
. You can literally copy the entire text of your solution to problem 2; change the definitions oflookup
,empty-env
, andextend
; update your documentation (annotations) concerning theenvironment
type; and revise your tests forextend
. Note thatextend
cannot be tested (since the result is a function!) without usinglookup
to examine it. (If Note: if you wrote a correct solution to problem 2, you can do this problem is less than 15 minutes!)
Hint: you can uselambda
-notation in Racket to define a constant function forempty-env
, andextend
can be defined as a functional that takes a function (representing an environment) and adds a new pair to the function--using aif
embedded inside alambda
-abstraction.
- Rewrite
- Extra Credit (50 pts.) Add support for
lambda
-expressions in your evaluator from Problem 2 as follows:- Extend the definition of A
rithExpr
by adding a clause for unarylambda
-abstractions and a clause for unary applications of an ArithExpr
to an ArithExpr
. Use the namelam
for the structure representing alambda
-expression abstraction and the namesvar
andbody
for the accessors of this structure. Use the nameapp
for the structure representing an a unary application and the namesrator
andrand
for the argument of this structure. Note that therator
of anapp
is an ArithExpr
not alam
(which is a proper subtype ofArithExpr
). - Write a (function) template for this additional expansion of the newest definition of A
rithExpr
. - Extend the definition of
to-list
to support this expansion of the newest definition of ArithExpr
. You print the corresponding "concrete" syntax that would be fed as input to a compiler. Hence,
(to-list (make-lam 'x (make-plus 'x 'y))) => (list 'lambda (list 'x) '(+ x y)) = '(lambda (x) (+ x y))
- Extend the definition of
eval
to support the newest definition this expansion of ArithExpr
. Note thateval
can now return functions as well as numbers. Your biggest challenge is determining a good representation for function values. What doeseval
return for as the value of alam
input? That input may contain free variables. In principle, you could represent the value of thelam
input by a revisedlam
(with no free variables) obtained by substituting the values for free variables from the environment input (just like we do in hand-evaluation). But this approach is tedious and computationally expensive. A better strategy is to define a structure type (called a closure) to represent a function value. The structure type must contain the originallam
and a description of what substitution (of values for identifiers) would have been made, deferring the actual substitution just aseval
defers substitutions by maintaining an environment.
- Extend the definition of A