Background: A "type" has been defined as a set or class of values, together with operations defined on members of that set. Machine and Assembly language programming has no concept of type -- all values manipulated by such programs are simply strings of bits, and any operation can be applied to any value, no matter what that value represents. This uniformity simplifies the hardware (since it avoids providing special operations to, say, copy characters from place to place, as opposed to integers), but at the expense of difficulty in debugging programs.

Even machine language programs distinguish between "addresses" and "numbers" -- the distinction is critical, since it seldom makes sense to reference memory at a location specified by a non-address. However, the hardware provides limited support for detecting such potential errors. These errors are usually painfully discovered during run-time.

The notion of "type" can be used to detect some programming errors at compile time. One can regard a programming error as a situation in which the wrong result is calculated. This might occur because the wrong operation was applied to the correct operands, or because the operands were selected incorrectly. Without running the program, and matching its actions against those the programmer expects, there is no hope of detecting all such errors. However, the use of "types" can detect a subset of them that occur commonly -- errors in which an operation not appropriate for some operand is applies to it. Programmer-defined types can refine what is meant by "not appropriate", and can ensure that the result of one operation (possibly a complicated subprogram) is passed only to subprograms that interpret that result correctly. (After this correct interpretation, nothing ensures that the subprograms perform the correct arithmetic an logical operations on their data, however.)

Machines provide operations which are intended to apply to objects with particular internal structure. Thus, a floating-point addition assumes that its operand bit-strings are subdivided into "mantissa" and "exponent" fields, and operates under that assumption. The early notion of "type" associated a "tag" with each computed value, and extended the hardware to check that instruction operands had the correct tag. This caught errors when they occurred, rather than when the result of an incorrect computation was used. However, machines with this hardware extension could only distinguish among elementary, built-in types.

Compilers (starting with FORTRAN) began associating "type" with individual program variables and functions. Eventually, through improvements in languages, it proved possible to design compilers for some languages that could ensure that correct source programs never "violated" the type rules -- that every variable declared to be of some specific type would always hold a value of that type. Such languages, which allow complete compile-time checking of all type constraints, are termed "strongly typed".

Most strongly-typed languages either rely heavily on "declarations", or deal only with built-in types, or both. C (which has deliberately included means of violating the type system), PASCAL, and JAVA all rely on declarations. In contrast, a language like SCHEME is not "strongly-typed", because its type-checking system operates mostly at run-time.

ML is an experiment in designing a language that is strongly-typed, allows user-defined types, allows some forms of "polymorphism" (in which a function can be applied to values from several "types"), and yet uses few, if any declarations. ML deduces types, by generating (from program expressions) equations which use "type variable symbols". It then uses these equations as constraints, and solves for the types for each type variable which satisfy all constraints.

The lack of required declarations in ML has two benefits: it requires fewer typed characters to express a given program, and is thus more convenient to use as a prototyping language. In addition, the lack of declarations allows radical changes to be made in the choice of data structures, without requiring changes in the programs that accept those structures as parameters.

Most of the syntax given in the text is in fact correct -- the exception is the syntax for function definition. In SML, a function is defined using a form like:

fun name parameter = expression;

The parameter is usually a tuple -- that is, a parenthesized list -- of names.

SML builds in the usual elementary data types, along with operators on them:

Numbers may be integers (int) or reals (real) (using ~ as the unary minus sign), Boolean (bool) constants true and false, and string (string) constants (as in C) exist; the operators that apply to numbers are like those of C, while "^" is used as the string concatenation operator. The comparison operators, which apply to two reals, two integers, or two strings are: <, >, =, <=, >=, and <>. The shortcut && and || operators of C become "andalso" and "orelse" in SML. There is conditional operator "if E then A else B" in SML, which has value A if the Boolean expression E is "true", and has value B otherwise. One caveat -- integers and reals are not arithmetically compatible types.

There are no "statements as such in SML. ML programs consist of a series of definitions, either "val" declarations (which bind names to values) and "fun" (which bind names to function definitions). An expression typed outside of such binding constructs is evaluated, and its value is printed. val-declarations associate values with names; a second val-declaration for the same name can be given, in which case the name's apparent value changes. Thus val-bound names act something like variables.

binds name x to the real value 3.0.

ML has special type constructor operators which form new types out of combinations of old types: tuples, lists, and datatypes.

The tuple:

binds a new object to name x, a tuple (here a record with 3 components). This tuple has type

The components of x can be accessed, using access operators which include integer constants (not expressions) in their names:

The list:

forms a list of items, each of which must have the same type. Lists can be operated on using hd() and tl() to access their components:

also built in are operators :: to "cons" another item to the beginning of a list, and @ to append two lists together:

Functions can be defined, and act much like Scheme functions, but with a much more pleasant syntax, and with full static type checking. Note that lists must be HOMOGENOUS. This seeming restriction will be softened when we introduce datatypes. Note that comments are surrounded by (* and *) sequences.

Here, I tack the type constraint :int onto hd(L), to force ML to deduce that L must be an int list.

reduce is defined as a series of cases, selected among based on the form of its argument. The cases are not exhaustive, for I haven't supplied a rule to use if L = nil. I'll get a warning message when I use this definition.

Mutually recursive functions can be defined "simultaneously", by separating their definitions with "and", instead of ";".

A list of statements can be "executed" sequentially, by surrounding them with "(" and ")", and separating them with ";". The main use of this sort of thing is in executing I/O statements, which do not fit into the functional model of ML, because these statements are used BECAUSE of their side-effects, not because of the values they return.

ML provides a way to abbreviate the values of complex expressions, by temporarily binding values to names in a let block:

The values bound to y are used in computing the value bound to z; the value thus bound to z is used in evaluating the final expression. On exit, the values bound to x, y, and z are all lost. Only the final expression's value is returned.

Programmer-defined types are allowed, using the form below:

A <constructor expression> has the form <name> of <type expression>.

An example:

This allows an "element" to be either a singleton of type 'a, or a pair of type 'b. The advantage is that "elements" can now be placed in a list, even though some are pairs, and others are singletons.

Since the list must contain only elements of one type, here an ('a, 'b) element, the argument of S must be of string type, as must the first argument of P.

We can use functions defined by patterns to operate on such a list. Suppose the second parameter of P represents the number of times its first parameter appears in some body of text, while S represents a word which occurs only once. Function ltxt(L) computes the total number of words:

A datatype definition can use its own name in the ttype signatures of its constructor expressions; if mutually recursive datatypes must be defined, their definitions are separated by "and", as for mutually-recursive function definitions.

So this defines a labeled binary tree, which may either be Empty, or may be a node label, with two child labeled binary trees.

ML uses patterns heavily. Function calls are defined as performing a match between the argument's value, and the parameter pattern. In:

is a perfectly valid function call. It takes the value of s, which could be a function call instead of a name evaluation, and matches that value, here (1,3), against (a,b); it matches 1 with a, and 3 with b, performing the corresponding bindings as the match proceeds. These bindings will then be evaluated within the body of f.

Patterns and matches are usable in ML's case expression, and in val-declarations. A match is a sequence of rules, each of which is of the form pattern => expression. The rules are separated by "|". This general form appears in an alternate form for defining functions:

For example:

The match applies to the single argument (all functions are assumed to have just one argument, although that argument may be a tuple). Operators and constants in the pattern must match corresponding parts in the argument; names in the pattern may match any sub-expression in the argument, and take on the value of that sub-expression in the expression. Here, the notion of "sub-expression" does not apply to arithmetic expressions, which are automatically reduced to numeric values, rather than retaining the symbolic form that represents their construction. However, if the value is a compound type, such as a tuple, or a user-defined type, the sub-expressions of that value are "visible" to the match mechanism, and can be separated out by using it. A match can be used in a case statement, as well as in function definitions:

Form is: case expression of match

For example:

The _ represents a "wildcard" pattern, which can match anything. Here it matches anything not already tested for by an earlier rule.

Patterns can be very useful in val-declarations:

The val (w,z) = split(xs) retains the pair of values returned by the recursive call on split and allows their value to be incorporated into the final answer.

In fact, the if E then A else B expression can be regarded as a shorthand for a case: