CSE 341 -- ML Basics

What is ML?

ML means "Meta Language." It is a "purely" functional/applicative language (this is actually a white lie, but we'll focus primarily on the functional part).

Application areas:

Education
Systems programming

Important attributes/features that are similar to those in Scheme/Lisp:

Functional programming style.
Interpreter based.
Heavy use of recursion and higher order functions.
High level data structures well supported (eg. lists)
Garbage collection

New attributes/features:

Statically/Strongly typed.
Type inference
Pattern matching.
Polymorphism
Compilation is well supported.

ML was developed by Robin Milner and friends in the mid-70s. In 1983, the language was redesigned, extended and standardized as Standard ML (SML). The language was initially used by the formal methods community, but has since gained popularity as a teaching language as well as a systems programming language. (Blurb from Pratt and Zelkowitz, 1996.)

Primitive ML data types

numbers
- integers (examples: 1, 4, ~3, 0) [Note the ~, not a -.]
- reals (examples: 0.0, 3.5, 1.23E~10) [Note the ~.]
booleans (true and false only)
strings (eg. "foo" "bar\n")

Case is significant (true, not TRUE).

Primitive ML operators

Arithmetic (+, -, *, / (reals), div (integers), mod (integers), ~ (unary minus))
String concatenation ("house" ^ "cat")
Relational (=, <, >, <=, >=, <>) are defined over numbers and strings
Logical (andalso and orelse): short circuit logical operators.
Conditional (if ... then ... else ...). This is an expression, not a control flow statement. There is no if-then construct in ML. The then expression is only evaluated if the conditional evaluates to true. The else expression is only evaluated if the conditional evaluates to false. The if expression and the then expression must be of the same type.
Type coercion. ML is strongly and statically typed. There are no mixed mode (3+3.0) expressions allowed. Use coercion operators: real (int->real), floor (real->int), ceiling (real->int), truncate (real->int) [drop digits to the right of decimal point], ord (char->int), chr (int->char).

Variables and Environments

Like pure Scheme (as in MiniScheme), and unlike languages like C, Pascal and ADA, pure ML doesn't have the notion of variables with state. The right way to think about variables in ML is as bindings between names and values in an environment. These bindings exist as long as the environment exists. Names can be rebound, in some sense, but a function can never rebind a name in an environment outside of its own. Because of this restriction, it is impossible to write an ML function that has a side effect on a non-local variable. Here is how we make new bindings in the top level of the interpreter:

- val someNumber = 16;          (* this is what we type *)
> val someNumber = 16 : int  (* this is what the interpreter spits back *)

- val x = true;
> val x = true : bool

- val y = (13 + 5) div 2;
> val y = 9 : int

- y;
> val it = 9 : int

Notice in the above examples, that ML infers the type of the variable for us. Also, when we evaluate an arbitrary expression, the interpreter names the returned value "it."

Aggregate Data Structures

Because ML has strong/static typing, aggregate data structures can be either extensible (lists) or heterogeneous (tuples), but not both. Contrast to Scheme. Generally, pattern matching is used for accessors. We'll learn more about pattern matching later.

Tuples

- val t = (44.0, true, "foo");     (* comment:  build a tuple *)
> val t = (44.0, true, "foo") : real * bool * string

- #3t;   (* access the third element of t *)
> val it = "foo" : string

Notice that the * used in the type value of the above tuple has a different meaning than * for numbers. Above, it should be read as "cross-product." For example, the tuple (1, 10.0) has the type int * real, or the set of integers crossed with the set of real numbers. Lists

- val mylist = [44.0, 34.0, 24.0]      (* makes a list of type real list. *)
- val mylist = 44.0::34.0::24.0::nil   (* ditto *)
- val mylist = [44.0]@[34.0]@[24.0]    (* ditto *)

- mylist;
> val it = [44.0, 34.0, 24.0] : real list

hd(mylist) corresponds to (first mylist)in Scheme. tl(mylist) corresponds to (rest mylist)in Scheme. The :: (cons operator) is right-associative. @ is the append operator for lists.

Functions

Syntax

fun function-name (arg1, arg2, ...) = expression; (* general form *)

- fun addtwo (x) = x+2.0;                         (* define a simple function *)
> val addtwo = fn : real -> real

Notice that ML deduced the type of the function. How? Why might ML complain about the following function?

- fun myadd (x, y) = x+y;

ML uses sophisticated type inference mechanisms that allow us to avoid explicitly declaring most types. However, in the above declaration, it could not determine the types of the arguments or result type. Here's a fix:

- fun myadd (x:real, y) = x+y;
> val myadd = fn: real * real -> real

Notice that the type of myadd is actually a function that maps tuples of two reals to reals. In fact, functions in ML can only take one argument. We can write functions which take multiple arguments by having them take tuples of arguments. Here is an example of a recursive function. As with Scheme, IF together with recursion provide our main control construct.

- fun append (x,y) = if x=nil then y else hd(x)::append(tl(x), y);
> val append = fn : ''a list * ''a list -> ''a list

Type expressions

The ML syntax for type expressions is probably pretty strange at first sight. The type expressions can consist of type names, combined by the "operators" ->, *, and list. Let's look at some examples:

int list                   list of integers [int]
int * int list	           a tuple (int, [int])
(int * int) list           a list of tuples [(int, int)]
int * int list -> real     a fun mapping tuples (ints, [int]) to reals

Here is the order of precidence from high to low:
     list
     *
     ->

Pattern Matching

To obtain cond-like functionality, we can rely on pattern matching:

;; Scheme version of adding one to every element of a list:

(define (add1-to-list lst)
  (cond ((null? lst) lst)
	(#t (cons (+ 1 (car lst)) (add1-to-list (cdr list))))))

(* ML version of adding one to every element of list: *)

- fun add1_to_list (nil) = nil
    | add1_to_list (x::xs) = (1+x) :: add1_to_list(xs);

> val add1_to_list = fn: int list -> int list

(* General pattern matching function form *)

fun functionName (pattern1) = expression1
  | functionName (pattern2) = expression2
  ...
  | functionName (patternN) = expressionN;

How does pattern matching work?

Patterns are checked from top to bottom, first matching expression is returned.
Cases don't have to be exhaustive, although ML should warn you.
Patterns should only be in terms of variables, constants, and constructors (the :: list constructor and the (,) tuple-constructor are most common) for data structures.
The same variable cannot represent two different parts of a pattern.

How do we find a matching expression? Here's the pattern matching algorithm to check if a pattern P matches an expression E.

Construct parse trees T1 and T2 which correspond to P and E.
Compare the corresponding nodes of T1 to those of T2.
If an operator or constant corresponds to a node element of a different value, declare a mismatch.
Otherwise, if all of T1s nodes are matched, declare a match.

Here is a somewhat more formal description of the pattern matching algorithm: Assume we are given nodes pNode and eNode, which are the roots of the trees patternTree and expressionTree respectively.

1.  If eNode or pNode are variables then the trees match.
2.  If eNode and pNode are constants and eNode == pNode then the trees match.
3.  If eNode and pNode are operators AND eNode == pNode AND
    the children of eNode match the children of pNode then the trees match.
4.  Otherwise declare a mismatch.

Which of the following are matches?

x::(a,b,c)::z with [(1,2,3), (4,5,6), (7,8,9)]

x::y::qs with [1,2]

x::y::qs with [1]

x@y with [1,2,3]

x+2 with 2

_ is a special wildcard symbol which can appear in a pattern. It differs from a normal identifier in that it can appear multiple times in a pattern and cannot be referenced in the associated expression. The special keyword "as" allows us to reuse whole patterns. Examples:

fun foo (x, _, _) = x*x*x;

fun append (nil, y) = y
  | append (x, nil) = x
  | append (x::xs, y) = x::append(xs,y);

fun merge (nil, L2) = L2
  | merge (L1, nil) = L1
  | merge (L1 as x::xs, L2 as y::ys) =
        if (x < y) then x::merge(xs, L2) else y::merge(L1, ys);
     
(* common compile time error: *)

fun sumList (nil) = 0;
  | sumList (a::as) = a + sumList(as);

Local Environments

Just as in Scheme, we can declare temporary variables by using a LET expression.

(* general form: *)

let
  val <var1> = <expr1>;
  val <var2> = <expr2>;
    ...
  val <varN> = <exprN>
in
  <expression>
end

(* an example of a fast exponentiator *)

fun fastexp(x, 0) = 1 
  | fastexp(x, n) =
      let 
         val temp = fastexp(x,n div 2)  
      in
         if (n mod 2 = 0) then temp * temp else temp * temp * x 
      end;

(* you can also declare temporary functions *)
(* here is a fast version of reverse.  *)

fun reverse(x) =
    let 
      fun help(nil, result) = result
        | help(x::xs, result) = help(xs, x::result)
    in
      help(x, nil)
    end;

(* here is a slow version of reverse, why is it slower? *)

fun reverse (nil) = nil
    | reverse (x::xs) = reverse(xs)@[x];

dugan@cs.washington.edu (Last Update: )