CSE130 LECTURE NOTES

ADMINISTRATION

CARTESIAN PRODUCTS

type person = string * string * int * real;

MAPPINGS

type direction = (n, e, s, w);
     field = array [direction] of real;

Mathematically, a mapping from set A to set B is a set of ordered pairs where

(1) the first item in each pair is from A and the second item is from B
(2) for each item x in A, there is a unique y in B such that the pair <x,y> is in the mapping.

The mathematical notation for an ordered pair is <x,y> using "angle brackets" or (x,y) using parentheses.  The mathematical notation for the set of all mappings from one set to another is ->. For example, cosine is a member of R -> R where R is the set of real numbers.

The cardinality of A -> B is |B| to the power |A|.  Intuitively, to specify a single mapping we must make |B| choices, |A| times.

Mappings are often called functions. The set on the left of the arrow (the "from" set) is called the domain and the set on the right is called the range.  Note that the domain of a mapping need not be a primitive type. For arrays the domain type is called the index type and is often a tuple.

Be sure to understand the difference between a single mapping, such as cosine, and the set of all mappings of the same type, such as R -> R.
 
 

AN ARRAY IS A MAPPING

(1) the first item in each pair is from A and the second item is from B
(2) for each item x in A, there is a unique y in B such that the pair <x,y> is in the mapping.

Note that an array satisfies exactly these two properties:

• Type-checking at compile-time verifies the first property.
• If an array is uninitialized, and the programming language has runtime error-checking, then one gets an error message if the second condition is violated.

Often the restriction is even more extreme: an index type must be a Cartesian product of discrete finite types.  For example, the following type might be used to store a screen image with 24-bit color:

        type screen = array [0..1023, 0..767] of array[1..3] of byte;

Remember that an array is a composite value.  We could have

        var blank : screen;
 
 

INFINITE MAPPINGS

Note that A -> (B -> C) is equivalent to (A x B) -> C but different from (A -> B) -> C.

Consider the mapping type string -> integer.  A variable of this type might be convenient for storing student scores on a quiz, for example.  No standard language allows this type. However some languages that are biased towards ease-of-use rather than efficiency do, for example the Perl, PHP, and awk scripting languages.

Data structures question: How is a variable of type string -> integer implemented?  Answer: maybe a labeled binary tree sorted in "in-order", or by hashing.
 
 

PL FUNCTIONS ARE VALUES OF A MAPPING TYPE ALSO

odd[-1] = true
odd[0] = false
odd[1] = true

odd(-1) = true
odd(0) = false
odd(1) = true

Notice that the function odd could have two different implementations.  One implementation might use mod, while the other might subtract or add two until 0 or 1 is reached.
 
 

OBSERVATIONS ABOUT FUNCTION VALUES

type boolean = {false, true};

const not1: array [boolean] of boolean := [true, false];

function not2 (x: boolean): boolean;
begin
    if x then return false else return true;
end;

Functions really are values, just like arrays and records are values.  Functions just happen to be usually infinite.
 
 

FUNCTIONS SHOULD BE FIRST-CLASS VALUES

• assigned to a variable,
• passed in to a routine (i.e. a function or a procedure) as a parameter,
• returned as the result of a function, and
• included in a larger composite value.

The property that the fewest values usually possess is the ability to be returned as the result of a function.  For example, in Pascal functions cannot return records.  In other words, the result type of a function cannot be a Cartesian product type.

Functions really are values similar, and they should be first-class in a powerful PL.  However in standard PLs such as C functions are not first-class.  In higher-level, more modern PLs such as ML, functions are first-class.
 
 

HIGHER-ORDER FUNCTIONS

For example, here are two alternative cosine functions:

function cosine (x: real): real;
begin
    return sine(x + pi/2.0);
end;

function cosine (x: real): real;
    const epsilon = 1e-9;
begin
    return integrate(sine,0,x,epsilon);
end;

The signature of integrate is (real -> real) * real * real * real -> real.