CSE130 LECTURE NOTES

ADMINISTRATION

If you do not have exactly two team-mates for the first project, you need to find a third person or a team to join immediately.

On Thursday I'll talk about why the ability to write high-quality reports is so important for computer scientists and software engineers.  For today, here are some concrete guidelines.
 
 

REPORT GUIDELINES

Reports should be as long as necessary to be complete and easy to read, but they should be concise.  The maximum length permitted is ten pages, single-spaced.

Reports should be organized well:

• Have  sections, subsections, and paragraphs, each of which has a single main topic or idea.
• Sections and subsections should have informative titles.
• Use diagrams, charts, and tables when useful.  Always provide labels and legends.
• Cite your sources at each location where a source is relevant. Give full bibliographic information in a "List of References" at the end of the report.
• Printouts of code or sample executions should only appear in appendices.

• Follow all the rules of correct English explained by Strunk and White.
• Each section of your report should be edited carefully by a team-member who is not the author of the section.
• Call the UCSD Office of Academic Support and Instructional Services (OASIS) for help with writing at 534-3760.

 AN ARRAY IS A MAPPING

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.

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 awk language.

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 similar to numbers and records. They just happen to be usually infinite. However, functions are typically not first-class values.

Definition: A first-class value is one that can be assigned to a variable, passed as a parameter, returned as the result of a function, and included in a larger composite value, just like other values.

In typical PLs, being "first-class" is not all-or-nothing.  Some values are "more first-class" and some values are "less first-class."  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.
 
 

HIGHER-ORDER FUNCTIONS

function f(j:int): real;
begin
    return a[j]*b[j];
end;

function sum (lo,hi:int; f: int->real): real;
    var s: real := 0;
begin
    for k := lo to hi do s := s + f(k);
    return s;
end;

ANOTHER EXAMPLE OF A HIGHER-ORDER FUNCTION

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.

Two functions with different implementations can have the same semantics, i.e. specification.  The specification of a function is a mathematical mapping. Its implementation may be something different and more complicated that involves computation.
 
 

PURE VERSUS IMPURE FUNCTIONS

(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.

In programming, a function that satisfies this definition is called pure.  Programming functions can be impure for any or all of several reasons:

• Non-determinism
• Side-effects
• Hidden arguments.

Note that the implementation of a function may use one or more of the sources of impurity just mentioned, but this impurity may be encapsulated (i.e. hidden from users of the function) and therefore the function remains pure from a mathematical perspective.