CSE230  THURSDAY JANUARY 8, 1998


See the New York Times article by James Gleick for a case study of an
expensive error (the failure of the Ariane 5 satellite launch rocket)
that could have been prevented by using a high-level programming
language.



THE SUBLANGUAGE OF EXPRESSIONS

Where do we find a higher degree of abstraction already?
Where do we already find freedom from administering time and space?

Answer: in the world of arithmetic expressions.

                               n!
Consider the expression     --------
                            m!(n-m)!

Notice the absence of many details:
	- where are intermediate results stored
	- in what order are intermediate results computed

Another major simplification:
	- m and n are invariant values throughout the expression.
Evaluating one subpart of the expression involving m doesn't change the
meaning of m in another subexpression.

Functional programming languages use expressions to do all the
work done by commands in imperative languages.
This makes them more abstract and higher-level.

         FEATURE      IMPERATIVE   FUNCTIONAL
	               MECHANISM    MECHANISM

	scheduling     sequence   function call
	conditional    if-then       if-then
	repetition     looping      recursion



A FIRST LOOK AT ML

What a programmer does is to define values, and associate them with names.
ML is interactive.  The programmer types code after the minus sign prompt.

	pindar% sml
	Standard ML of New Jersey, Version 75, November 11, 1991
	
	- val two = 2;
	val two = 2 : int
	
	- val four = two + two;
	val four = 4 : int

ML automatically infers that "two" and "four" have type "int".  
You can call "two" and "four" variables, but they are NOT updatable,
imperative variables.  They are names for fixed values.



FUNCTIONS ARE VALUES ALSO

In ML functions are values in the same way integers are values.

	- fun double x = 2 * x;
	val double = fn : int -> int

What is the value named double?
It's the mathematical function  { ... <-1,-2>, <0,0>, <1,2> ... }

This value has been defined intensionally, by giving a rule for computing it:
			x |-> 2*x
This rule says "double x reduces to 2*x" for any x of type integer.



PATTERN-MATCHING

A function can be defined by several rules:

	- fun f(0) = "zero"
	=   | f(1) = "one"
	=   | f(_) = "many";
	val f = fn : int -> string

This is pattern-matching: there are three patterns.
The last pattern contains a "wild card".
This is similar to Prolog pattern-matching by unification,
	but there are various restrictions
	motivated by efficient implementability

Notes on ML-specific syntax and semantics:
	- function arguments are not written inside parentheses
	- cases should be mutually exclusive



THE ML TYPE SYSTEM (FIRST PASS)

The ML type system is quite elegant.
There are base types
	int	real	string		and some more

There are operators that create new types from old types
	->	creates a function type
	*	creates a tuple type

A tuple is like a record, but fields are identified by position, not by name.

Mathematically (extensionally), double is a subset of R x R.
Computationally (intensionally), it's different, so ML has -> as well as *



AUTOMATIC TYPE INFERENCE

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.



POLYMORPHISM

In general list functions are "polymorphic": the type of their arguments
is not fixed.  We can say that the "type pattern" is fixed: it must
be "list of something."

This systematic polymorphism is called "parametric polymorphism".
Parametric polymorphism can be useful in any programming language.
Consider in Pascal:

        procedure swap (var x, y: alpha);
           var z: alpha;
        begin
           z := x;  x := y;  y := z;
        end;



BUILT-IN LISTS IN ML

List types are the most common polymorphic, recursive types. 

The type "list of something" is written "alpha list" where alpha
is a Greek letter indicating an arbitrary type.  ML implementations
write 'a for alpha, 'b for beta, etc.

The basic constructor functions for lists:
	1) create a new empty list	[]		type 'a list
	2) create a new non-empty list	:: infix
		type 'a -> 'a list -> 'a list

The basic destructor functions for lists:
	1) first = car		hd	type 'a list -> 'a
	2) rest = cdr		tl	type 'a list -> 'a list

Note again that [] and :: are constructors.  They are not
defined in terms of other functions, and they don't reduce.



ML PROGRAMMING STYLE

The most helpful documentation is declarative: a specification of
        the input and output type of each function, and of
        the relationship between input and output values.

Make cases in function definitions
        (1) exhaustive (2) disjoint (3) as uninstantiated as possible.
This helps in writing correct software and in verifying it.
Of course these objectives are not always attainable.



OVERLOADING

Overloading means having a few fixed alternative argument types.  This
is also called "ad hoc polymorphism".  For example:

Unlike for parametric polymorphism, ML type inference cannot deal 
with overloading, except for a few builtin functions.  For example:

        - fun d3 x = x + x;
        std_in:4.14 Error: overloaded variable "+" cannot be resolved

The difficulty is that there are two plus functions, one of type
        real * real -> real, and one int * int -> int.

In the latest version of ML, called ML97, the default type of + is int,
and = is not available for real numbers.