Homework 5 (Due Monday 2/16/2009 at 11:00am)
Submit via Owl-Space
Submit each problem in a separate .ss
files: 1.ss
,
2.ss
, 3.ss
, and 4.ss
(if you do the extra credit problem). Unfortunately, none of the languages supported by DrScheme will allow these files to be combined. The Pretty Big Scheme language allows
top-level indentifiers (functions and variables) to be redefined, but
it does not support check-expect
. All of the student languages--the only ones that support check-expect
--prohibit redefinition.
Embed answers that are not program text in block 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:
- 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)
;
wheren
is a Scheme number, andae1
andae2
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: contract, purpose, examples/tests, template
instantiation, code, testing (which happens automatically if the examples are given in
(check-expect ...)
form). Follow the same recipe for any help
function that you introduce.
-
-
Write the (function) template for
arith-expr
-
Write a function
to-list
that maps anarith-expr
to the corresponding "list"
representation in Scheme. Numbers are unchanged. Some other examples include:(to-list (make-sum (make-prod 4 7) 25)) => '(+ (* 4 7) 25) (to-list (make-quot (make-diff 4 7) 25)) => '(/ (- 4 7) 25)
Note: you need to define the output type (which I call gen-expr)
for this function, but you can omit the template because this
assignment does not include any functions that process this type. -
Write a function
eval
that evaluates anarith-expr
. Your evaluator should produce
exactly the same result for anarith-expr E
that Scheme evaluation would produce for
the list representation(to-list E)
.
-
-
-
Extend the definition of
by adding a clause for variables (represented as Scheme
symbols). Write the (function) template for this definition.Modify your definition
ofto-list
to support the new definition of arith-expr.Given the Scheme structure defintion:
(define-structure binding (var val))
a
binding
is(make-binding s n)
wheres
is a symbol andn
is a number and
anenvironment
is a(listOf binding)
.Write a (function) template for processing
anenvironment
.Define a top-level variable (constant)
empty-env
that is bound
to the empty environment.Write a function
extend
that takes environmentenv
, a symbols
, and a numbern
,
and returns an extended environment identical
toenv
except that it includes the additional binding ofs
to
n
.The definition of
extend
trivial; it requires no recursion. As a result,extend
can be tested using a single test case, namely(check-expect (extend empty-env 'a 1) (list (make-binding 'a 1)))
In the remainder of the problem, use
empty-env
and
extend
to define example environments for test cases.Write a function
lookup
that takes a symbols
and an environmentenv
and returns the first
binding inenv
with avar
component that equalss
. If no match is found,lookup
returns empty. Note that the return type oflookup
is not simplybinding
. Define the
a new union type calledoption-binding
for the the return type.Write a new
eval
function for the new definition ofarith-expr
. The neweval
takes two arguments: anarith-expr E
to evaluate and anenvironment env
specifying the
values
of free variables inE
. For example,(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
arith-expr 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 codded
eval
. Do NOT explicitly test for this form of error.
-
-
-
Rewrite
eval
to useenvironment
defined as a finite function in
(symbol -> option-binding)
instead of as a(listOf 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 you wrote a correct
solution to problem 2, you can do this problem is less than 15 minutes!)
An
environment
is really a finite function. 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 Scheme (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)
. -
-
-
Extend the definition of
by adding a clause for unary
lambda
-expressions and a clause for unary applications of anarith-expr
to anarith-expr
.
Use the namelam
for the structure representing alambda
-expression and the names
var
andbody
for the accessors of this structure. Use the
nameapp
for the structure representing an application and the
nameshead
andarg
for the accessors of this structure. Note
that the head of anapp
is anarith-expr
not alam
.Write a (function) template
for the newest definition ofarith-expr
.Extend the definition of
to-list
to support
the newest definition ofarith-expr
.Extend the definition of
eval
to support the newest definition of
arith-expr
. 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 a
lam
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 strucure type (called a closure) to represent a function value. The structure type must contain the originallam
and a description of what substitution would have been made, deferring the actual substitution just aseval
defers substitutions by maintaining an environment.
Extra Credit (50%)
-