Date: Fri, 29 Mar 2024 07:09:16 -0500 (CDT) Message-ID: <86744593.1167.1711714156005@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1166_98190443.1711714156003" ------=_Part_1166_98190443.1711714156003 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
To submit this assignment, simply upload the files in your GitHub reposi=
tory to you GitHub Classroom repository for this assignment (as you have do=
ne for earlier assignments). In contrast to Assignments 1 and 2=
where you could put the programs for all problems in a single file (HW01.r=
kt for Assignment 1 and HW02.rkt for Assignment 2), you must store the solu=
tion to each problem in a separate .rkt
file, namely HW0=
4-1.rkt
, HW04-2.rkt
, HW04-3.rkt
, and HW04-4.rkt
(if you do t=
he extra credit problem) for problems 1, 2, 3, and 4 (extra credit). Unfort=
unately, none of the languages supported by DrRacket allow these files to b=
e combined. The Pretty Big Racket language allows top-level identi=
fiers (variable names) to be redefined, but it does not support check-expect=E2=80=94
prohibit redefini=
tion of identifiers.
Embed any answer text that is not executable in a DrRacket block comment= or block commenting brackets (#| and |#).
Use the Intermediate Student with lambda language.
Given the Racket structure definitions:
(define= -struct sum (left right)) (define-struct prod (left right)) (define-struct diff (left right)) (define-struct quot (left right))
an ArithExpr
is either:
n
,(make-sum ae1 ae2)
,(make-prod ae1 ae2)
,(make-diff ae1 ae2)
, or(make-quot ae1 ae2)
where n
is a number (as defined in Racket), and ae1=
code> 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 rec=
ipe: contract, purpose, examples/tests, template instantiation, code, testi=
ng (which happens automatically when the examples are presented using (check-expect ...)
). 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
.
rithExpr
Write a function to-list
that maps an ArithExpr=
code> to the corresponding "list" representation in Racket. Numbers are unc=
hanged. Some other examples include:
(to-lis= t 12) =3D> 12 (to-list (make-sum (make-prod 4 7) 25)) =3D> '(+ (* 4 7) 25) (to-list (make-quot (make-diff 4 7) 25)) =3D> '(/ (- 4 7) 25)
Notes:
The notation '(+ (* 4 7) 25)
abbreviates
You need to define the output type (named RacketExpr
) f=
or this function, but you can omit the template because this assignment doe=
s 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
eval: ArithExpr -> number
that evaluat=
es an ArithExpr
. Your evaluator should produce exactly the sam=
e result for an ArithExpr E
that Racket evaluation would produ=
ce for the list representation &nb=
sp; (to-list E)
.rithExpr
as=
follows:
ArithExpr
from Problem 1.to-list
to support the expanded =
definition of ArithExpr
.Given the Racket structure definition:
(define= -structure binding (var val))
a binding
is (make-binding s n)
where n
is a number. An env=
ironment
is a (list-of binding)
. Write a (functio=
n) template for processing an environment
.
empty-env
that is bound =
to the empty environment containing no bindings (i.e., the empty l=
ist). Note that empty-env
is really a constant since var=
iables cannot be rebound in our functional subset of Racket.Write a function extend
that takes environment en=
v
, a symbol s
, and a number n
, and return=
s an extended environment identical to env
except that it adds=
the additional binding of s
to n
.
The definition of extend
is trivial; it requires no recursion=
. As a result, extend
satisfies the invariant
(check-= expect (extend empty-env s n) (list (make-binding s n)))
where s
is any symbol and n
is any numbe=
r. Hence,
(extend= empty-env 'a 4) =3D> (list (make-binding 'a 4))
In the remainder of the problem, use empty-env
and
lookup
that takes a symbol s
=
and an environment env
and returns the first binding in env
with a var
component that equals s
. If no match is found, lookup
returns empty. Note t=
hat the return type of lookup
is not simply binding because it can return empty
. Define the a new union type ca=
lled option-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 expanded definition o=
f ArithExpr
. The new eval
takes two argu=
ments: an ArithExpr E
to evaluate and an environment env=
specifying the values of free variables in E
. For exam=
ple,
(eval '= x (extend empty-env 'x 17)) =3D> 17 (eval (make-prod 4 7) (extend empty-env 'x 17)) =3D 28 (eval 'y (extend empty-env 'x 17)) =3D> some form of run-time error
If an ArithExpr E
contains a free variable that is no=
t bound in the environment env
, then (eval E env)
will naturally produce some form of run-time error if you have correctly =
coded eval
. Do not explicitly test for this form of e=
rror.
environment
is really a finite function=
(a finite set of ordered pairs). It is finite in the sense that i=
t 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 la=
nguages). Even the identity function is not finite. For the purpos=
e of this exercise, we redefine the type environment
as =
(symbol -> option-binding)
.
eval
to use environment
defined as a =
finite function in (symbol -> option-binding)
instead of as=
a (list-of option-binding)
. If you cleanly coded your definit=
ion of eval
in the preceding problem using lookup
=
, make-binding
, and extend
, all that you have to =
do to your solution to the previous problem is redefine the bindings of empty-env
, and extend
, and revi=
se your test cases for extend
. You can literally copy the enti=
re text of your solution to problem 2; change the definitions of look=
up
, empty-env
, and extend
; update your do=
cumentation (annotations) concerning the environment
type; and=
revise your tests for extend
. Note that extend
c=
annot be tested (since the result is a function!) without using looku=
p
to examine it. (Note: if you wrote a correct solution to problem 2=
, you can do this problem is less than 15 minutes!)lambda
-notation in Racket to define a constant =
function for empty-env
, and extend
can be defined=
as a functional that takes a function (representing an environment) and ad=
ds a new pair to the function--using a if
embedded inside a lambda
-=
expressions in your evaluator from Problem 2 as follows:
rithExpr
by adding a clause=
for unary lambda
-abstractions and a clause f=
or unary applications of an ArithExpr
to an A=
rithExpr
. Use the name lam
for the structure repr=
esenting a lambda
-abstraction and the names <=
code>var and body
for the accessors of this structure. =
Use the name app
for the structure representing a unar=
y application and the names rator
and rand for the argument of this structure. Note that the rator
of =
an app
is an ArithExpr
not a lam
(wh=
ich is a proper subtype of ArithExpr
).
rithExpr
.to-list
to support this expansion=
of the 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))) =3D>=
(list 'lambda (list 'x) '(+ x y)) =3D '(lambda (x) (+ x y))
eval
to support this expansion of=
ArithExpr
. Note that eval
can now return functio=
ns as well as numbers. Your biggest challenge is determining a good represe=
ntation for function values. What does eval
return as the valu=
e of a lam
input? That input may contain free variables. In pr=
inciple, you could represent the value of the lam
input by a r=
evised lam
(with no free variables) obtained by substituting t=
he values for free variables from the environment input (just like we do in=
hand-evaluation). But this approach is tedious and computationally expensi=
ve. A better strategy is to define a structure type (called a closure=
em>) to represent a function value. The structure type must contain the ori=
ginal lam
and a description of what substitution (of values fo=
r identifiers) would have been made, deferring the actual substitution just=
as eval
defers substitutions by maintaining an environment.=
li>