FHH DEFINITIONS

3.1 Function Definitions
3.2 Operation Definitions
3.3 Name Definitions
3.4 Definition Rules
3.5 Recursive Definitions
3.6 Type Propagation
3.7 Summary
3.8 References

The main purpose of this chapter is to give a general introduction into one of the most important area's of the language. It explains what definitions are and how they are used to define new notions in terms of already existing notions. In following chapters the concept of definitions will be extended in several ways.

There are three kinds of definitions: function definitions, operation definitions, and name definitions. We will start with function definitions.

3.1 Function Definitions

Suppose we want to write a function for squaring integers. We may simply write:

square (integer) -> integer;
square (x) = x * x;

This example consists of two parts: the first part is the signature of the definition, the second part is a definition rule.

A signature specifies the name, the types of the parameters, and the result of a definition. In this example, the name of the definition is square, it has one parameter, which must be of integer type and the result is an integer value. ( The -> sign may be read as "has as result", or "returns").

The definition rule of square has as input parameter the value x and it returns the value of x * x. In general, definition rules are making use of other definitions. In our example, the definition rule uses a predefined integer operation. Predefined types and associated operations are specified in Appendix A.

We now may use the definition in expressions, as in:

square (7)?
49

square (square (9 - 6))?
81

Our square example has only one parameter. In general, we may use as many parameters as we want. Let's see how the sum of two integers can be defined:

sum (integer, integer) -> integer;
sum (x, y) = x + y;

Suppose, we also want to define the sum of three integers, thereby using the definition of the sum of two integers:

sum (integer, integer, integer) -> integer;
sum (x, y, z) = sum (sum (x, y), z);

We may now use both functions in expressions:

sum (3, 6)?
9

sum (3, 2 + 3, 3 * 4 - 5)?
15

sum (3, 6) + sum (3, 5, 7)?
24

In the last example both functions are called in one expression. How is the sum function with two parameters distinguished from the sum function with three parameters? By using a selection method which not only depends on the name of the function but also on the number of the parameters and on the types of the parameters.

In general, a reference to a function definition in an expression is called a function call. A function call is an expression which consists of the name of a function, followed by a number of arguments which are enclosed in parentheses and separated by comma's. The arguments are expressions, representing values of certain types. To select the corresponding definition, the translator first determines the name of the function, the number of arguments, and the types of the arguments, and then uses this information to find the definition which signature matches the calling information. The translator is that part of the Elisa system which translates the external program representation into an internal representation. In our example sum (3, 6) refers to the sum function with two integer parameters, and sum (3, 5, 7) refers to the sum function with three integer parameters.

By using different parameter types in a signature, different functions are defined. For example, we are able to define a similar set of functions for real values. The sum function for two reals may be defined as:

sum (real, real) -> real;
sum (x, y) = x + y;

If we compare this with the sum function for two integers, we see that, in this example, the signatures of both sum functions are different but that the definition rules are of the same appearance. However, in this definition rule use is made of a predefined real operation.

We may now use this function in an expression:

sum (7.0, 2.0 + 3.6)? 
12.6

Note that the sum function for two integers and the sum function for two reals are both valid within the same program. They may be even used in one expression:

sum (9.3 - 2.3, 2.0 + 3.5) + real (sum (15 / 5, 9 - 3))?
21.5

The real function is a predefined function which converts integers to reals. In our example its use is necessary because the integer sum function returns an integer result and the real sum function returns a real result.

Definitions may also be defined for other types. For instance, here are two functions for determining whether a character is a digit, or an upper-case letter:

isDigit (character) -> boolean;
isDigit (C) = '0'<= C & C <='9';

isUppercase (character) -> boolean;
isUppercase (C) = 'A'<= C & C <='Z';

Sometimes it is convenient to give a meaningful name to a parameter type, as in:

Area (Height = real, Width = real ) -> real;
Area (H, W ) = H * W;

In this example, both parameters of the Area definition are of type real. For documentary purposes, the type of the first parameter is associated with the name Height, the type of the second parameter is associated with the name Width. Neither Height nor Width have any other meaning than clarification for the human reader.

The Area definition may be called in the following way:

Area (3.0, 4.0)?
12.0

In some situations there are no parameters required for a function definition. In that case an empty parentheses list is written. For example, if we want to read the next character from a keyboard, we may write:

NextCharacter( ) -> character;
NextCharacter( ) = read (keyboard);

In this definition we assumed that somewhere else a read function from keyboard has been defined.

The NextCharacter function must be called as NextCharacter( ).

Exercises:

3.1 Define functions to compute the products of two and three reals.

3.2 Define a function to determine if a character is a lowercase letter.

3.3 Define a function to determine if a character is a letter.

3.4 Define a function to compute the volume of a box.

3.2 Operation Definitions

Operation definitions have the same characteristics as function definitions. The only difference is that the syntax is in accordance with the prefix and infix operator-operand notation. We will start with some examples.

Let us assume that we want to define mixed-type arithmetic for integers and reals. If we restrict the exercise to the + and * operations, the four corresponding definitions are:

integer + real -> real;
i + r = real (i) + r;

real + integer -> real;
r + i = r + real (i);

integer * real -> real;
i * r = real (i) * r;

real * integer -> real;
r * i = r * real (i);

Each operation definition starts with a signature of the operation and the types of the inputs and output. The corresponding definition rules are performing the necessary conversions. Each definition rule has a left-hand side which gives the operator symbol and the parameters, and a right-hand side which is an expression.

With these operation definitions we are now able to use mixed type arithmetic as in:

2 + 3.6?
5.6

5 * 6.2 + 3 * 6
49.0

sum (2 * 3.0, 1.2 * 5)?
12.0

The same selection method as defined for function calls is also used for operation calls. The operation-symbol, the number of operands and the types of the operands are identifying the operation definition. ( For historic reasons we are talking here about operands rather than about arguments; in technical sense they are identical).

The difference between an operation definition and a corresponding operation definition is mainly a question of notation. The similarities are clear if we compare a functional notation with the infix operator notation. With a functional notation the first definition of our mixed type examples could have been written as:

plus (integer, real) -> real;
plus (i, r) = real (i) + r;

The difference is, that, we have to write plus (2, 3.6) in a functional notation instead of 2 + 3.6.

Exercise:

3.4 Define the - and / operations for mixed type arithmetic.

3.3 Name Definitions

Name definitions are used to define names for expression results. For instance, it is possible to give a name to a constant or to the result of a computation. Examples are:

pi = 3.14159;
radius = 5.0;
circumference = 2.0 * pi * radius;

The name represents the value and the type of the expression. So, in our example, the name pi stands for the value 3.14159 which is of type real, and circumference is the name of the value represented by the expression 2.0 * pi * radius, which is also of type real.

3.4 Definition Rules

In the examples we used so far, a definition rule consisted of a left-hand side and a right-hand side, separated by the = symbol. For function definitions, the left-hand side consisted of the name of the function, followed by a number of parameter names which are enclosed in parentheses and separated by comma's. The right-hand side of a definition was an expression. For operation definitions we had a slightly different syntax for the left-hand side.

However, a definition with one definition rule is only a particular case of a more general scheme. As a rule, a definition may consists of a number of definition rules. Each definition rule is defined for one or more specific input values.

Multiple definition rules are often used to distinguish a number of cases, depending on parameter values. As a example of such a case analysis, we will write a definition which determines the number of days in a month of a non-leap year:

days (integer) -> integer;
days (2) 	= 28;
days (4) 	= 30;
days (6) 	= 30;
days (9) 	= 30;
days (11)	= 30;
days (X) 	= 31;

This definition consists of a signature and 6 definition rules. The definition has an integer as input, representing the month ( January = 1, February = 2, etc.). The output is also an integer, representing the number of days in a given month. In this example five months are explicitly mentioned. The remaining months are defined by the last definition rule.

We may now use the definition in expressions such as:

days(2)? 	<< February >>
28

days(9)? 	<< September >>
30

days(3)? 	<< March >>
31

We see that this definition is properly returning the numbers of days in a given month. How are these answers obtained by the system? By means of pattern matching. After the definition has been called, the system starts with the first definition rule and compares the argument value with the corresponding parameter.

If the parameter represents a value and the argument value and the parameter value are equal, the value of the right-hand side of the definition rule will be returned. For example, if the argument is 6, representing June, then the right-hand side of the corresponding definition rule is evaluated and the resulting value, in this case 30, is returned.

If the parameter is a name, as is the case in the last definition rule, then any argument value will match. So, all months not covered by the preceding definition rules are covered by this one.

As a general rule, if a definition should be defined for all cases then the last definition rule of a definition should cover the remaining cases not covered by previous definition rules. Later on, we will see examples where definitions are not handling all cases but only a selection of possible values.

Let us now see what happens if we are using in our example as input a number which does not represent an existing month, such as:

days (17)? 	<< Unknown Month >>
31 

days(- 5)? 	<< Illegal Month >>
31

We may conclude that any integer number is accepted by our definition. And that was certainly not our intention! To avoid this kind of problem and, in addition, to make our definition more readable, we will introduce an enumerated type specifying the names of the months and an adapted definition for the days in a month. (Enumeration types are discussed in Chapter 15, Section 3):

type Month = ( January, February, March, April, May, June, July,
	       August, September, October, November, December);

Days (Month) -> integer;
Days (=February)  = 28;
Days (=April)     = 30;
Days (=June)      = 30;
Days (=September) = 30;
Days (=November)  = 30;
Days (X)          = 31;

Compared to our previous definition, this definition can be used in a more readable form, such as:

Days (February)?
28

Days (September)?
30

Days (March)?
31

With this approach, we will not be tempted to ask for the days of non-existing months.

There is another aspect of our new example definition which should be explained: In the first five definition rules the name of the month is preceded by a = sign. We learned that if a parameter is a name it will match all argument values. However, we also want sometimes, as in our example, that names are representing values. To distinguish parameter names and parameter values we use the = sign. The = sign is a prefix operator which says that the following name, or, sometimes the following expression, represents a value which should be used for matching and which is not a parameter name such as the X of the last definition rule.

Let us now use another example. Assume a gambling game is played with a pair of dice. The result of a throw is the sum of the values of the two dice, unless both values are equal. In that case the result is zero. We may define that in the following way:

Throw (integer, integer) -> integer;
Throw (x, x) = 0;
Throw (x, y) = x + y;

This definition specifies the result of a throw. It has two parameters, representing the values of the two dice. The first definition rule states that if both values are equal then the result is zero. The second definition rule handles all remaining cases.

The first definition rule illustrates the convention that if a parameter list of an definition rule contains equal parameter names then the corresponding argument values must also be the same in order to match.

Exercise:

• 3.5 Define a function with has as input two reals and as output a boolean. The function returns the true value if both reals are equal, otherwise the false value is returned. There are two ways to define this function: one based on two definition rules as discussed before, the other with only one definition rule. Define both versions.

3.5 Recursive Definitions

A definition which calls upon itself, directly or indirectly, is a recursive definition.

We begin by considering an interesting example, the factorial function, defined by:

n! = n * (n - 1) * (n - 2) ... 3 * 2 * 1

There are many ways to compute factorials. One way is to make use of the observation that n! is equal to n * (n - 1)! for any positive n:

n! = n * ((n - 1) * (n - 2) ... 3 * 2 * 1) = n * (n - 1)!

Thus, we can compute n! by computing (n - 1)! and multiplying the result by n. If we add the boundary condition that 1! is equal to 1, this observation translates directly into a definition:

factorial(integer) -> integer;
factorial(1) = 1;
factorial(n) = n * factorial(n - 1);

By using substitution repeatedly we can watch this definition in action computing 7!, as shown in the following:

    factorial(7)= 7 * factorial(6) 
	    	= 7 * (6 * factorial(5))
	  	= 7 * (6 * ( 5 * factorial(4))) 
		= 7 * (6 * ( 5 * (4 * factorial(3)))) 
		= 7 * (6 * ( 5 * (4 * (3 * factorial(2)))))
		= 7 * (6 * ( 5 * (4 * (3 * (2 * factorial(1)))))) 
		= 7 * (6 * ( 5 * (4 * (3 * (2 * 1)))))
		= 7 * (6 * ( 5 * (4 * (3 * 2))))
		= 7 * (6 * ( 5 * (4 * 6)))
		= 7 * (6 * ( 5 * 24))
		= 7 * (6 * 120)
		= 7 * 720 
		= 5040

Notice that the recursive computation of a factorial needs many preparatory steps before the boundary condition is encountered and the actual computation can start. This is rather typical for many recursive definitions as we will see.

Let us now use another example of a recursive definition. We take as a case the definition of the sequence of Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... of which the first two terms are 1 and 1 and each succeeding term is the sum of the immediately preceding two. This sequence was developed by Leonardo Fibonacci around the year 1202 when he tried to estimate the rate of reproduction of rabbits. He made some simplifying assumptions:

• The reproduction rate of rabbits only depends on the number of mature female rabbits. Male rabbits are not included in the numbers.

• There are fixed time intervals. Each time interval may contain rabbits of distinct generations.

• All immature rabbits of a time interval are mature in the following time interval.

• Each mature female rabbit produces exactly one female offspring during each time interval.

• Female rabbits never die.

• The first time interval starts with one immature rabbit.

Thus the number of female rabbits added during a particular time interval equals the number of mature female rabbits, which is the total number of rabbits, mature or immature, at the previous interval.

Fibonacci numbers can be defined recursively by the following definition:

fib (integer) -> integer;
fib (1) = 1;
fib (2) = 1;
fib (n) = fib (n - 1) + fib (n - 2);

The first line in this example is the specification of the Fibonacci function. Its input is an interval number, its output is the total number of rabbits at the beginning of that interval.

There are three definition rules: the first rule defines the first immature rabbit, the second rule says that at the beginning of the second time interval the first rabbit is mature and the last rule states that the total number of rabbits at the beginning of a new time interval is the sum of the number of rabbits, mature or immature, of the previous time interval, and the new offspring, which is equal to the number of mature rabbits of the previous time interval. This number of mature rabbits is equal to the number of rabbits, two time intervals ago.

Because new Fibonacci numbers are defined in terms of previous Fibonacci numbers we can use a recursive definition. As an example, computation of the fifth Fibonacci number proceeds as follows:

	 fib(5) = fib(4) + fib(3)
		= (fib(3) + fib(2)) + (fib(2) + fib(1))
		= (((fib(2) + fib(1)) + 1) + (1 + 1)
		= ((( 1 + 1) + 1) + 2
		= 5

This exercise is instructive as another example of a recursive definition. However, it is a very inefficient way to compute Fibonacci numbers because it does so much redundant computation. Notice that for the computation of fib (n - 1) the computation of fib (n - 2) is required, which is also independently done by the second branch of fib(n). Later on, we will discuss more efficient solutions for these types of problems.

3.6 Type Propagation

Type propagation is a method, used at translation time, to assign to each name and expression associated type information, even if explicit type declarations are missing. The type information can be obtained by inspecting the static program text. How type propagation works will be explained in this section.

We discussed earlier how definitions are selected based on name, number of arguments, and types of arguments. Here we will describe how the result specification, after the -> sign, is used for type propagation.

Let us consider the following definitions:

F (integer) -> real;
F (i) = real (i);

G (integer, real) -> real;
G (I, R) = F (I) * R;

A = G (2, 3.0);

We start with the definition of G. Its parameter I is of type integer, because the specification of G states that the first parameter is an integer and the second is a real. So, I is integer and R is real.

The right-hand side of the definition rule of G contains the function call F(I). Because I is an integer, the translator will try to find the corresponding specification of F(integer). The specification of F, being the first definition in our example, matches with F(integer). The result specification of F states that the result of F is a real. This type information can be used in the * operation of G.

The following step is to determine the result of the * operation in G. Both operands are real, because the type of the result of F(I) is real and the type of R is real. So, we are looking for a specification of real * real. Because this operation is not (re-)defined in our example program, we will look for the standard operations of the basic data types as defined in Chapter 2. There, the real type specification states that "real * real -> real". So, the result of our multiplication is a real.

Because this is the final step in the type propagation process for G, the only remaining task is to verify if this result is in accordance with the result-specification of G, which is the case. It is an error if the type of the right-hand side of an definition rule is not matching with the result-specification.

Another example of type propagation is illustrated by the last definition of our example. In "A = G (2, 3.0);", the G (2, 3.0) refers to the preceding definition. Its result-specification is a real. So, the type of A will also be a real.

In general, this method of type propagation is used by the translator to assign to each name the associated type information.

3.7 Summary

· There are three kinds of definitions: function definitions, operation definitions, and name definitions.

· Function definitions and operation definitions consist of a signature and one or more definition rules.

· Signatures are specifying the name, number and types of the parameters and the type of the result.

· Parameters of a definition rule may be names, literals, or names of values.

· The unary = operation is used to distinguish parameter names from parameter values.

· The rules we used so far for successful pattern matching are:

1. If a parameter is a literal, the argument must have the same value.

2. If a parameter is a unary = sign followed by an expression, the argument must have the same value as the expression.

3. If a parameter has the same name as another parameter of the same definition rule, both argument values must be the same.

· Type propagation is used to determine the types of names and expressions.

3.8 References

Some of the examples in the text are adapted from Abelson and Sussman (1985), and Winston and Horn (1984).

Part 1: Language Description

Chapter 3: Definitions