Mathematics for Computer Science

Chapter 6 Recursive Data Types184

• [ef] 2 Aexp. The expression[ef] is called aproduct. The
  Aexp’seandf are called thecomponentsof the product; they’re also
  called themultiplierandmultiplicand.


• -[e] 2 Aexp. The expression-[e]is called anegative.

Notice that Aexp’s are fully bracketed, and exponents aren’t allowed. So the
Aexp version of the polynomial expression3x^2 C2xC 1 would officially be written
as

These brackets and’s clutter up examples, so we’ll often use simpler expressions
like “3x^2 C2xC 1 ” instead of (6.8). But it’s important to recognize that3x^2 C2xC 1
is not an Aexp; it’s anabbreviationfor an Aexp.

6.4.1 Evaluation and Substitution with Aexp’s

Evaluating Aexp’s

Since the only variable in an Aexp isx, the value of an Aexp is determined by the
value ofx. For example, if the value ofxis 3, then the value of3x^2 C2xC 1
is 34. In general, given any Aexp,e, and an integer value,n, for the variable,x,
we can evaluateeto finds its value, eval.e;n/. It’s easy, and useful, to specify this
evaluation process with a recursive definition.

Definition 6.4.2.Theevaluation function, evalWAexpZ!Z, is defined recur-
sively on expressions,e 2 Aexp, as follows. Letnbe any integer.

 Base cases:

eval.x;n/WWDn; (value of variablexisn.) (6.9)

eval.k;n/WWDk; (value of numeralkisk, regardless ofx.) (6.10)

 Constructor cases:

eval.[e 1 +e 2 ];n/WWDeval.e 1 ;n/Ceval.e 2 ;n/; (6.11)

eval.[e 1 e 2 ];n/WWDeval.e 1 ;n/
eval.e 2 ;n/; (6.12)

eval.-[e 1 ];n/WWDeval.e 1 ;n/: (6.13)