6.4. Arithmetic Expressions 183
but with a slow growing coefficient nearly equal to the inverse Ackermann func-
tion. This means that pragmatically,Union-Findis linear, since the theoretically
growing coefficient is less than 5 for any input that could conceivably come up.
The Ackermann function can be defined recursively as the function,A, given by
the following rules:
A.m;n/D2n; ifmD 0 orn1; (6.6)
A.m;n/DA.m 1;A.m;n 1//; otherwise: (6.7)
Now these rules are unusual because the definition ofA.m;n/involves an eval-
uation ofAat arguments that may be a lot bigger thanmandn. The definitions
off 2 above showed how definitions of function values at small argument values in
terms of larger one can easily lead to nonterminating evaluations. The definition of
the Ackermann function is actually ok, but proving this takes some ingenuity (see
Problem 6.17).
6.4 Arithmetic Expressions
Expression evaluation is a key feature of programming languages, and recognition
of expressions as a recursive data type is a key to understanding how they can be
processed.
To illustrate this approach we’ll work with a toy example: arithmetic expressions
like3x^2 C2xC 1 involving only one variable, “x.” We’ll refer to the data type of
such expressions as Aexp. Here is its definition:
Definition 6.4.1.
Base cases:
- The variable,x, is in Aexp.
- The arabic numeral,k, for any nonnegative integer,k, is in Aexp.
Constructor cases: Ife;f 2 Aexp, then
- [e+f] 2 Aexp. The expression[e+f]is called asum. The Aexp’s
eandf are called thecomponentsof the sum; they’re also called the
summands.
