Extended Exercise: Evaluating Scheme

Next: Mutually Referential Data Definitions Up: More Self-referential Data Definitions Previous: Lists in Lists

Extended Exercise: Evaluating Scheme

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 in this section, 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, additions, and multiplications for a start. Clearly, numbers can stand for numbers and symbols for variables. Additions and multiplications, however, call for a class of compound data because they consist of an operator and two subexpressions.

A straightforward way to represent additions and multiplications is to use two structures: one for additions and another one for multiplications. Here are the structure definitions:

(define-struct add (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.

Scheme expression representation of Scheme expression

3 3

x 'x

(* 3 10) (make-mul 3 10)

(+ (* 3 3) (* 4 4)) (make-add (make-mul 3 3) (make-mul 4 4))

(+ (* x x) (* y y)) (make-add (make-mul 'x 'x) (make-mul 'y 'y))

(* 1/2 (* 3 3)) (make-mul 1/2 (make-mul 3 3))

Scheme expression	representation of Scheme expression
`3`	`3`
`x`	`'x`
`(* 3 10)`	`(make-mul 3 10)`
`(+ (* 3 3) (* 4 4))`	`(make-add (make-mul 3 3) (make-mul 4 4))`
`(+ (* x x) (* y y))`	`(make-add (make-mul 'x 'x) (make-mul 'y 'y))`
`(* 1/2 (* 3 3))`	`(make-mul 1/2 (make-mul 3 3))`

Let's look at some examples:

These examples cover all cases: numbers, variables, simple expressions, and nested expressions.

Exercises

Exercise 14.4.1

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))) Solution

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 8, (+ (* 3 3) (* 4 4)) has the value 25, 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.

Exercise 14.4.2

Develop the function numeric?, which consumes (the representation of) a Scheme expression and determines whether it is numeric. Solution

Exercise 14.4.3

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. When the function is tested, modify it so it consumes all kinds of Scheme expressions; the revised version raises an error when it encounters a variable. Solution

Exercise 14.4.4

When people evaluate an application (f a) they substitute a for f's parameter in f's body. 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 substituted by N. Solution

Next: Mutually Referential Data Definitions Up: More Self-referential Data Definitions Previous: Lists in Lists

PLT