Subprograms can be viewed as abstract operations on a predefined data set.
A subprogram represents a mathematical function that maps each particular set of arguments
into a particular set of results.

Specification of a subprogram (same as that for a primitive operation):

• the name of the subprogram
• the signature of the subprogram - gives the number of arguments, their order,
  and the data type of each, as well as the number of results, their order,
  and the data type of each
• the action performed by the subprogram

Some problems in attempting to describe precisely the function computed by a subprogram:

1. Implicit arguments in the form of nonlocal variables.
2. Implicit results (side effects) returned as changes to nonlocal variables or as changes in the subprogram's arguments.
3. Using exception handlers in case the arguments are not of the required type.
4. History sensitiveness - the results may depend on previous executions.

Implementation of a subprogram:

• Uses the data structures and operations provided by the language
• Defined by the subprogram body
Local data declarations
Statements defining the actions over the data.

The body is encapsulated, its components cannot be accessed separately by the user of the subprogram. The interface with the user (the calling program) is accomplished by means of
arguments and returned results.

Type checking: similar to type checking for primitive operations.
Difference: types of operands and results are explicitly stated in the program

2. 1. Subprogram definitions and subprogram activations

Subprogram definition: the set of statements constituting the body of the subprogram.
It is a static property of the program, and it is the only information available during translation.

A simple (but not efficient) approach:

A better approach:

Below is Figure 6.3 from the textbook.

On the left is the subprogram definition. On the right is the activation record created during
execution. It contains the types and number of variables used by the subprogram,
and the assigned memory locations at each execution of the subprogram.

The definition serves as a template to create the activation record (the use of the word template
is different from the keyword template in class definitions in C++, though its generic meaning
is the same - a pattern, a frame to be filled in with particular values.
In class definitions the binding refers to the data types and it is performed at compilation time,
while here the binding refers to memory locations and data values,
and it is performed at execution time.)

Generic subprograms: have a single name but several different definitions – overloaded.

Type definitions are used to define new data types.
Note, that they do not define a complete abstract data type,
because the definitions of the operations are not included.

Format: typedef definiion name

Actually we have a substitution of name for the definition.

Examples:

typedef int key_type;
key_type key1, key2;

These statements will be processed at translation time and the type of key1 and key2
will be set to integer.

struct rational_number
     {int numerator, denominator;};
     
typedef rational_number rational;
rational r1, r2;

Here r1 and r2 will be of type rational_number

• Name equivalence: two data types are considered equivalent
  only if they have the same name.

Issues
Every object must have an assigned type, there can be no anonymous types.
A singe type definition must serve all or large parts of a program.

• Structural equivalence: two data types are considered equivalent
  if they define data objects that have the same internal components.

Issues

Do components need to be exact duplicates? Can field order be different in records?
Can field sizes vary?

• Data object equality

We can consider two objects to be equal if each member in one object is identical
to the corresponding member of the other object. However there still may be a problem.
Consider for example the rational numbers 1/2 and 3/6.
Are they equal according to the above definition?

In general, the compiler has no way to know how to compare data values of user-defined type.
It is the task of the programmer that has defined that particular data type to define also
the operations with the objects of that type.