CSE 130 Lecture Notes, April 10, 2002

CSE130 LECTURE NOTES

April 10, 2002

ADMINISTRATION

Here are the submission instructions for the first assignment, due before class next Monday.

HIGHER-ORDER FUNCTIONS

A function or procedure is called "higher-order" if it takes another function as a parameter. For example, here is one way to compute the dot product of two vectors:

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;

The word "signature" means the same as "type". The signature of f here is int -> real and the signature of sum is int * int * (int -> real) -> real. Remember that the symbol * inside a signature means Cartesian product, i.e. a record type.

PURE VERSUS IMPURE FUNCTIONS

In mathematics, a function in A -> 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.

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: giving different results depending on something random.
Side-effects: any effect apart from returning a value, e.g. changing a global variable or outputting something.
Hidden arguments: any value that a function depends on that is not an explicit parameter, e.g. the value of a global variable.

Having a hidden argument can make a function seem non-deterministic to the user. This can happen even if the function has no side-effects, i.e. it never changes the value of this or any other global variable.

One major difference between PLs is exactly what kinds of impure functions are allowed.

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.

INTRODUCTION TO ML

Functional programming involves giving declarations and evaluating expressions interactively.

pindar% sml
Standard ML of New Jersey, Version 75, November 11, 1991
- val two = 2;
val two = 2 : int
- fun double x = 2 * x;
val double = fn : int -> int
- double two;
val it = 4 : int

The ML type system is quite elegant. The principal builtin primitive types are int, real, string, and bool.
There are operators that create new types from old types:

-> creates a function type
* creates a tuple type

ML infers types automatically:

- fun d2 x = 2.0*x;
val d2 = fn : real -> real

Deduction: 2.0 is a real, so * must be the function of type real * real -> real, so x must be a real, so d2 must be of type real -> real.

HIGHER-ORDER FUNCTIONS IN ML

We saw how the set (A -> B) -> C is essentiallt the same as (A x B) -> Cand how this explains the signature of ML functions with two arguments.