Homework 5 (Due
...
Friday 2/
...
19/2009 at
...
10:00am)
Submit this assignment via Owl-Space Submit In contrast to the previous assignments, submit each problem in a separate .ss
files file: 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 a Scheme block comment or block commenting brackets (#| and |#).
...
Given the Scheme structure definitions:
Code Block |
---|
(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)
;
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: contract, purpose, examples/tests, template
instantiation, code, testing (which happens automatically if when the examples are given in
(check-expect ...)
form). Follow the same recipe for any help
function that you introduce.
HTML |
---|
<ol> |
HTML |
---|
<li> |
HTML |
---|
<ul> |
HTML |
---|
<li> |
- (40 pts.) Write an evaluator for arithmetic expressions as follows:
- Write the (function) template for
arith-expr
- Write the (function) template for
...
HTML |
---|
</li> |
...
...
<li>
Write a function
to-list
that maps anarith-expr
to the corresponding "list"
...
representation in Scheme. Numbers are unchanged. Some other examples include:
Code Block
...
(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 (
...
named
scheme-expr
)
...
for this function, but you can omit the template because this
...
assignment does not include any functions that process this type.
HTML |
---|
</li> |
HTML |
---|
<li> |
- Write a function
eval: arith-expr -> number
that evaluates anarith-expr
. Your evaluator should produce
- Write a function
...
- exactly the same result for an
arith-expr E
that Scheme evaluation would produce for
- exactly the same result for an
...
- the list representation
(to-list E)
.
- the list representation
HTML |
---|
</li> |
HTML |
---|
</ul> |
HTML |
---|
<li> |
HTML |
---|
<ul> |
HTML |
---|
<li> |
...
- (40 pts.) Extend the definition of
...
<arith-expr>
...
- } as follows:
- Add a clause for variables
...
- represented as Scheme
...
- symbols
...
- .
- Write the (function) template for this definition.
...
...
<li>
- Modify your definition
...
- of
to-list
to support the new definition of arith-expr.
- of
...
HTML |
---|
</li> |
...
Given the Scheme structure defintion:
Code Block
...
(define-structure binding (var val))
a
binding
is(make-binding s n)
wheres
is a symbol andn
is a number and
...
an
environment
is a(
...
list-of binding)
.
...
Write a (function) template for processing
...
an
environment
.
...
- Define a top-level variable (constant)
empty-env
that is bound
...
- to the empty environment.
HTML |
---|
<li> |
Write a function
extend
that takes environmentenv
, a symbols
, and a numbern
,
and returns an extended environment identical
...
to
env
except that it
...
adds the additional binding of
s
to
...
n
.
The definition ofextend
trivial; it requires no recursion. As a result,extend
...
satisfies the invariant
Code Block
...
(check-expect (extend empty-env
...
s
...
n) (list (make-binding
...
s
...
n)))
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 in
env
with avar
component that equalss
. If no match is found,lookup
returns empty. Note that the return type oflookup
is not simplybinding
. Define the
- binding in
...
- a new union type called
option-binding
for the the return type.
- a new union type called
HTML |
---|
<li> |
Write a new
eval
function for the new definition ofarith-expr
. The neweval
...
takes two arguments: an
arith-expr E
to evaluate and anenvironment env
specifying the
...
values
...
of free variables in
E
. 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
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
...
coded
eval
. Do
...
not explicitly test for this form of error.
HTML |
---|
</ul> |
HTML |
---|
<li> |
HTML |
---|
<ul> |
- (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 Scheme (and other programming languages). Even the identity function
...
- is not finite. For the purpose of this exercise, we redefine the type
environment
...
- as
(symbol -> option-binding)
.
...
- Rewrite
eval
to useenvironment
defined as a finite function in
- Rewrite
...
(symbol -> option-binding)
...
- instead of as a
(
- instead of as a
...
list-of option-binding)
. If you cleanly coded your definition ofeval
in the
...
- preceding problem using
lookup
,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
- preceding problem using
...
- revise your test cases for
extend
. 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
- revise your test cases for
...
- the
environment
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
- the
...
- solution to problem 2, you can do this problem is less than 15 minutes!)
- solution to problem 2, you can do this problem is less than 15 minutes!)
HTML |
---|
</ul> |
HTML |
---|
<li> |
HTML |
---|
<ul> |
Extra Credit (50%)
HTML |
---|
<li> |
Extend the definition of
HTML |
---|
<arith-expr> |
- Hint: you can use
lambda
-notation 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
-expression.
- Hint: you can use
- Extra Credit (50 pts.) Add support for
lambda
-expressions in your evaluator as follows:- Extend the definition of
<arith-expr>
by adding a clause for unarylambda
-expressions and a clause for unary applications of anarith-expr
to anarith-expr
.
- Extend the definition of
...
- Use the name
lam
for the structure representing alambda
-expression and the names
- Use the name
...
-
var
andbody
for the accessors of this structure. Use the
-
...
- name
app
for the structure representing an application and the
- name
...
- names
head
andarg
for the accessors of this structure. Note
- names
...
- that the head of an
app
is anarith-expr
not alam
.
- that the head of an
HTML |
---|
<li> |
- Write a (function) template
...
- for the newest definition of
arith-expr
.
- for the newest definition of
...
- Extend the definition of
to-list
to support
- Extend the definition of
...
- the newest definition of
arith-expr
.
- the newest definition of
HTML |
---|
<li> |
- Extend the definition of
eval
to support the newest definition of
- Extend the 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 does
eval
return for a
- as numbers. Your biggest challenge is determining a good representation for function values. What does
...
-
lam
input? That input may contain free variables.
-
...
- In principle, you could represent the value of the
lam
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
- In principle, you could represent the value of the
...
- 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 original
lam
and a description of what substitution would have been made, deferring the actual substitution just aseval
defers substitutions by maintaining an environment.
- structure type (called a closure) to represent a function value. The structure type must contain the original
...
HTML |
---|
</li> |
...