CSE 130 Lecture Notes, April 17, 2002

CSE130 LECTURE NOTES

April 17, 2002

ADMINISTRATION

The second project ideadline is extended to Wednesday May 8, because the project is not easy. It is quite doable if:

You understand the concepts in this week's lectures well.
You understand the problem to be solved and the iterative deepening algorithm well.
You design your implementation using lists and recursion.
Design top-down and code bottom-up:

Figure out your code organization top-down.
Implement each piece of code as a separate ML function building on previously implemented functions.
Put together your functions into the final solution.

Implement the ML version first, then implement the C version by analogy.

Most important of all: do not try to do this project just by hacking, or by trial and error. You can only succeed by thinking, understanding, and planning.

You will find the book Elements of ML Programming (ML97 Edition) useful. This book will beon reserve at the S&E Library, and important sections will also be available online as UCSD e-reserves. It is easy to buy on the web.

LISTS ARE RECURSIVE

Think about the type of lists. There are two fundamental differences between lists and tuples:

a tuple has a fixed length, but a list can be of any (finite) length
all the items in a list are of the same type, but the items of a tuple can have different types.

Informally, a list of integers consists of an integer, possibly followed by another list of integers.

Rather more precisely, we can say that a list is either the empty list, or a pair consisting of a "first" element which is an integer and a "second" element which is itself a list of integers. Formally let's write

integerlist = nil + (integer * integerlist)

Here + means tagged union and * means tuple as before. Here are some examples of values of the type integerlist:

nil
<13, nil>
<13, <14, nil>>
<13, <4, <8, <16, nil>>>>

The last three examples are all special cases of the fact that <13,x>is an integerlist for any x such that x is an integerlist.

DEFINING A LIST TYPE IN ML

In ML recursion is allowed with the datatype notation for tagged unions. So we can write

datatype intlist = nil | cons of int * intlist;

Remember that you have to choose a tag value for each type being unioned: we choose nil and cons which is short for "construct". So in ML we could write for example

val doubles = cons (2, cons (4, cons (8, cons (16, nil))));

THE STANDARD LIST TYPE IN ML

Instead of nil, the builtin notation for the empty list is[]. The built-in notation for the cons operator is the double colon :: which is infix.

For examples of ML functions using lists see the sections from the book Elements of ML Programming (ML97 Edition) that are available online as
UCSD e-reserves.

A RECURSIVE TYPE TO REPRESENT EXPRESSIONS IN ML

Suppose we want to manipulate arithmetic expressions in a symbolic way. The easiest notations to use are tree diagrams, and fully parenthesized expressions.

Consider for example typical arithmetic expressions, including constants. We can represent the set of all these expressions as a recursive type, and therefore as an ML datatype:

datatype expression =
    Constant of int |
    Plus of expression * expression |
    Minus of expression * expression |
    Times of expression * expression;

With the data structure defined above, it is easy to write a recursive function that evaluates expressions:

fun eval (Constant n) = n
| eval (Plus (exp1,exp2) ) = (eval exp1) + (eval exp2)
| eval (Minus (exp1,exp2) ) = (eval exp1) - (eval exp2)
| eval (Times (exp1,exp2) ) = (eval exp1) * (eval exp2)

Notice how this function follows the structure of the expression datatype exactly.

Exercise: Write a pointer-based type in C with exactly the same conceptual organization as the ML type above to represent expressions.

LOOKING UP VALES ASSOCIATED WITH NAMES

Let's make our expressions more complicated. Suppose an expression can include names, so the ML datatype is

datatype expression =
    Constant of int |
    Name of string |
    Plus of expression * expression |
    Minus of expression * expression |
    Times of expression * expression;

Separately, we have a list of the value associated with each names. Here is an ML function that searches for the value that a name is bound to in a list of bindings. If no binding exists, the value zero is returned.

fun lookup name [] = 0
| lookup name ((n, v) :: r) = if name = n then v else lookup name r

The syntax ((n, v) :: r) is ML pattern-matching for a list whose head is the ordered pair (i.e. tuple)(n, v) and whose tail is r.

The next function evaluates an arithmetic expression according to an environment:

fun eval (Constant n) env = n
| eval (Name s) env = lookup s env
| eval (Plus (exp1,exp2) ) env = (eval exp1 env) + (eval exp2 env)
| eval (Times (exp1,exp2) ) env = (eval exp1 env) * (eval exp2 env)
- val b1 = ("x", 2);
- val b2 = ("y", 3);
- eval (Times((Var "x"), (Var "y"))) [b1,b2];
The ML response is val it = 6 : int

Be sure that you understand the ML code above completely before you start writing code for the second project.