This assignment is to be completed with the same partner as PS8.
Assignment goals:
DrScheme is itself a program that consists of several parts. One function checks whether the definitions and expressions we wrote down are grammatical Scheme expressions. Another one evaluates Scheme expressions. With what we have learned thus far, we can now develop simple versions of these functions.
Our first task is to agree on a data representation for Scheme programs.
In other words, we must figure out how to represent a Scheme expression
as a piece of Scheme data. This sounds unusual, but it is not difficult.
Suppose we just want to represent numbers, variables, subtractions, and
multiplications for a start. Clearly, Number
s can stand for
numbers and String
s for variables. Subtractions and
multiplications, however, call for a class of compound data because they
consist of an operator and two subexpressions.
A straightforward way to represent subtractions and multiplications is to use two structures: one for subtractions and another one for multiplications. Here are the structure definitions:
(define-struct sub (left right)) (define-struct mul (left right))
Each structure has two components. One represents the left expression and the other one the right expression of the operation.
Let’s look at some examples:
Scheme expression | representation of Scheme expression |
3 |
3 |
x |
"x" |
(* 3 10) |
(make-mul 3 10) |
(- (* 3 3) (* 4 4)) |
(make-sub (make-mul 3 3) (make-mul 4 4)) |
(- (* x x) (* y y)) |
(make-sub (make-mul "x" "x") (make-mul "y" "y")) |
(* 1/2 (* 3 n)) |
(make-mul 1/2 (make-mul 3 "n")) |
These examples cover all cases: numbers, variables, simple expressions, and nested expressions.
Provide a data definition for the representation of Scheme expressions. Then translate the following expressions into representations:
(- 10 -10)
(- (* 20 3) 33)
(* 3.14 (* r r))
(- (* 9/5 c) 32)
(- (* 3.14 (* o o)) (* 3.14 (* i i)))
A Scheme evaluator is a function that consumes a representation of a
Scheme expression and produces its value. For example, the expression
3
has the value 3
, (- 3 5)
has
the value -2
, (- (* 5 5) (* 3 3))
has the value
16
, etc. Since we are ignoring definitions for now, an
expression that contains a variable, for example, (- 3 x)
,
does not have a value; after all, we do not know what the variable
stands for. In other words, our Scheme evaluator should be applied only
to representations of expressions that do not contain variables. We say
such expressions are numeric.
Develop the function numeric?
, which consumes (the
representation of) a Scheme expression and determines whether it is
a numeric expression.
Provide a data definition for numeric expressions.
Develop the function evaluate-expression
.
The function consumes (the
representation of) a numeric Scheme expression and computes its value.
Once the function is tested, modify it so that it consumes all kinds of
Scheme expressions; the revised version raises an error when it
encounters a variable.
Hint: If you follow the template religiously,
evaluate-expression
will be short and straightforward; if
you don’t, it will be nearly impossible.
When people evaluate an application (f a)
they
substitute a
for f
’s parameter in
f
’s body. (This is the plugging rule that we
are familiar with from stepping.)
More generally, when people
evaluate expressions with variables, they substitute the variables with
values.
Develop the function subst
. The function consumes (the
representation
of) a variable (v
), a number (n
),
and (the representation of) a Scheme expression.
It produces a structurally equivalent expression in which
all occurrences of v
are replaced by n
.
A real Scheme implementation can do a few more operations than multiplication and subtraction. We won’t ask you to implement all of Scheme today, but we might like to be able to compute square roots.
Extend your data definition for expressions to allow you to represent square root expressions as well. Then translate the following Scheme expressions to your representation.
(sqrt 36)
(sqrt (- 25 (* 4 4)))
(* 2 (sqrt 2))
(sqrt (sqrt 625))
Extend evaluate-expression
to evaluate square root
expressions.
Design a function n-squares
that takes a
Natural
number n
and returns the
list of naturals, squared, from
n
^{2} down to
1
^{2}.
For example, (n-squares 5)
returns the list
(list 25 16 9 4 1)
Design a function n-circles
that takes a
Natural
number n
and returns a
list of Image
s containing solid, blue circles
with radii from (* 10 n)
down to (* 10 1)
.
For example, (n-circles 4)
returns the list
(list )
Abstract functions n-squares
and
n-circles
, and redefine them in terms of the abstract
function. Follow the design recipe for abstraction.
Please follow the electronic homework submissions instructions.
Last updated 11 March 2010.