Date: Fri, 29 Mar 2024 05:44:26 -0500 (CDT) Message-ID: <945842731.1157.1711709066781@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1156_1845964899.1711709066780" ------=_Part_1156_1845964899.1711709066780 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
Submit this assignment via Owl-Space In contrast to the previous assignm=
ents, submit each problem in a separate .ss
file: 1.ss=
code>,
2.ss
, 3.ss
, and 4.ss
(if you =
do the extra credit problem). Unfortunately, none of the languages supporte=
d by DrScheme will allow these files to be combined. The Pretty Big Scheme language allows top-level indentifiers (functions and variables) t=
o be redefined, but it does not support check-expect
.=
All of the student languages--the only ones that support check-expec=
t
--prohibit redefinition.
Embed answers that are not program text in a Scheme block comment or blo= ck commenting brackets (#| and |#).
Use the Intermediate Student with lambda
language.
Given the Scheme structure definitions:
(define= -struct sum (left right)) (define-struct prod (left right)) (define-struct diff (left right)) (define-struct quot (left right))
an arith-expr
is either:
n
,(make-sum ae1 ae2)
,(make-prod ae1 ae2)
,(make-diff ae1 ae2)
, or(make-quot ae1 ae2)
where n
is a Scheme number, and ae1
and =
ae2
are arith-exprs
.
The following 4 exercises involve the data type arith-expr
.=
If you are asked to write a function(s), follow the design recipe: contrac=
t, purpose, examples/tests, template instantiation, code, testing (which ha=
ppens automatically when the examples are given in (check-expect ...)=
form). Follow the same recipe for any help function that you introd=
uce.
arith-expr
to-list
that maps an arith-expr to the corresponding "list" representation in Scheme. Numbers are uncha=
nged. Some other examples include:=20
(to-lis=
t (make-sum (make-prod 4 7) 25)) =3D> '(+ (* 4 7) 25)
(to-list (make-quot (make-diff 4 7) 25)) =3D> '(/ (- 4 7) 25)
Note: you need to define the output type (named scheme-expr) for this function, but you can omit the template because this assignm=
ent does not include any functions that process this type.
eval: arith-expr -> number
that evalua=
tes an arith-expr
. Your evaluator should produce exactly the s=
ame result for an arith-expr E
that Scheme evaluation would pr=
oduce for the list representation (to-list E)
. <arith-expr>
} as follows:=20
to-list
to support the new defin=
ition of arith-expr.(define= -structure binding (var val))
binding
is (make-binding s n)
where n
is a number and an environm=
ent
is a (list-of binding)
. Write a (function) template=
for processing an environment
.empty-env
that is b=
ound to the empty environment.extend
that takes environment env=
code>, a symbol s
, and a number n
,
and returns an extended environment identical to env
except t=
hat it adds the additional binding of s
to n
.
The definition of extend
trivial; it requires no recursion. A=
s a result, extend
satisfies the invariant=20
(check-=
expect (extend empty-env s env n) (list (make-binding s n)))
In the remainder of the problem, use empty-env
and extend
to define example environments for test cases.lookup
that takes a symbol s
=
and an environment env
and returns the first binding in env
with a var
component that equals s
. I=
f no match is found, lookup
returns empty. Note that the retur=
n type of lookup
is not simply binding
. Define th=
e a new union type called option-binding
for the the return ty=
pe.eval
function for the new definition of =
arith-expr
. The new eval
takes two arguments: =
an arith-expr E
to evaluate and an environment env
specifying the values of free variables in E
. For example,=
=20
(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
arith-expr E
contains a free variable that is not=
bound in the environment env
, then (eval E env)
=
will naturally produce some form of run-time error if you have correctly c=
oded eval
. Do not explicitly test for this form of er=
ror. 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 Scheme (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)
.=20
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 islookup
, empty-env
, and =
extend
, and revise your test cases for extend
. Yo=
u can literally copy the entire text of your solution to problem 2; change =
the definitions of lookup
, empty-env
, and e=
xtend
; update your documentation (annotations) concerning the environment
type; and revise your tests for extend
. No=
te that extend
cannot be tested (since the result is a functio=
n!) without using lookup
to examine it. (If you wrote a correc=
t solution to problem 2, you can do this problem is less than 15 minutes!)<=
br>Hint: you can use lambda
-notation to defin=
e a constant function for empty-env
and extend
ca=
n be defined as a functional that takes a function (representing an environ=
ment) and adds a new pair to the function--using a if
embedded=
inside a lambda
-expression. lambda
-=
expressions in your evaluator as follows:=20
<arith-expr>
by adding a cl=
ause for unary lambda
-expressions and a clause for unary appli=
cations of an arith-expr
to an arith-expr
. Use th=
e name lam
for the structure representing a lambda
-expression and the names var
and body
for the a=
ccessors of this structure. Use the name app
for the structure=
representing an application and the names head
and arg<=
/code> for the accessors of this structure. Note that the head of an =
app
is an arith-expr
not a lam
.
arith-ex=
pr
.to-list
to support the newest def=
inition of arith-expr
.eval
to support the newest defini=
tion of arith-expr
. Note that eval
can now return=
functions as well as numbers. Your biggest challenge is determining a good=
representation for function values. What does eval
return for=
a lam
input? That input may contain free variables. In princi=
ple, you could represent the value of the lam
input by a revis=
ed lam
(with no free variables) obtained by substituting the v=
alues for free variables from the environment input (just like we do in han=
d-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 origina=
l lam
and a description of what substitution would have been m=
ade, deferring the actual substitution just as eval
defers sub=
stitutions by maintaining an environment.