CSE230  TUESDAY FEBRUARY 17, 1998



EVALUATION ORDER SUMMARY

How to remember the distinction:
	standard = leftmost innermost
	eager = standard but no optimization
	normal = leftmost outermost
	lazy = normal + caching
	
"leftmost" means the redex that starts furthest to the left
"outermost" means not inside any other redex
"innermost" means not containing any other redex



TYPES AND ABSTRACTION

Definition: A type system is a classification of values
	according to what operations make sense on them.

Abstraction means leaving out irrelevant details.

A type system is a tool for abstraction: aspects of the
implementation (especially the representation) of the values
of a type are abstracted away.

An ML datatype introduces a new type directly (concretely):
	- all legal values of the type are described inductively
	- the basic operators are constructor functions
	- these can be used to create values and to decompose
	  	values by pattern-matching.

New types in most languages are like ML datatypes in this respect.

For datatypes, the details left out are lexical: the representation
of values as integers or structures with pointers.



ABSTRACT DATA TYPES

An abstract data type introduces a new type indirectly, by giving
a set of operations that can produce and operate on a new set of values.

The new set of values is characterized by specifying the relationships
between the operations introduced.

Example: consider a data type to represent monetary amounts.
No concrete datatype is really adequate:
	- datatype money = real;
	- datatype money = Amount of real;
	- datatype money = Amount of int * int;
	- datatype money = Amount of string;

The problem is that for all conceivable concrete representations,
the constructor function Amount must do some checking and normalizing.



THE DEFINITION OF AN ADT

An ADT has two parts:
	a specification part and an implementation part.
A specification has two parts:
	a signature and a semantic part.
An implementation has two parts:
	a concrete datatype and a signature implementation.

Informally:
	- the signature specifies constructor/destructor function types
	- the semantics part specifies relationships between these
	- the concrete datatype specifies the actual representation of values
	- the implementation satisfies the signature and semantics part.



AN EXAMPLE ADT FOR ORDERED LISTS OF INTEGERS

First here's a signature:

	signature ordintlistsig = 
	   sig
		type ordintlist
		val onil:	ordintlist
		val ohd: 	ordintlist -> int
		val otl: 	ordintlist -> ordintlist
		val null: 	ordintlist -> bool
		val insert:	int -> ordintlist -> ordintlist
		val sort: 	int list -> ordintlist
	   end;

Next here is a sketch of a semantic part

	null nil = true;
	forall i:int x:ordintlist null (insert i x) = false
	forall i,j:int x:ordintlist
		insert(i,insert(j,x)) = insert(j,insert(i,x))
	...

The semantic part is conceptually important but real-world programming
languages do not require it.  There are two reasons for this
	- verification is not practically feasible
	- the semantics of specification languages is an open question

Finally, here's an appropriate (incomplete) implementation:

	structure ordintliststruct : ordintlistsig = 
	   struct
		datatype ordintlist = Ordered of int list

		fun doinsert (n: int) [] = [n]
		  | doinsert n (a::x) = if n <= a then n::(a::x)
						 else a::(doinsert n x)
		val onil = (Ordered [])
		fun ohd (Ordered (a::x)) = ...
		fun otl (Ordered (a::x)) = ...
		fun null (Ordered []) = true
		  | null (Ordered (a::x)) = false
		fun insert n (Ordered x) = Ordered (doinsert n x)
		fun sort x = (Ordered x)
	   end

Notice that the "sort" function is implemented as a "no-op".  This
implies that the "ohd" and "otl" functions must have non-trivial
implementations.



PUBLIC VERSUS PRIVATE

The specification part of an ADT is "public": it is what a user
of the ADT needs to know, and should be able to know.

The implementation part of an ADT is "private": only the implementer
needs to know the details of exactly how values are represented,
and how the basic operations on values are accomplished.

Languages have various mechanisms for making ADT function names visible.
For example in ML:
	- ordintliststruct.onil;
	val it = Ordered [] : ordintliststruct.ordintlist
	- open ordintliststruct;
	- onil;
	val it = Ordered [] : ordintlist

Implementation parts typically contain completely private auxiliary
functions that are not declared in the ppublic signature.

ADTs provide "representation independence" (better called implementation
independence) to their consumers.  Hiding the concrete implementation
of the type is crucial for this.

The same signature can have multiple implementations.  
These may differ, for example, on efficiency.  
Remember all the data structures you know for sets.