| |||||||
sml command starts the
compiler, and some simple operations (loading from files, setting
printDepth etc) were pointed out. The details are available at the
SML-NJ homepage
, along with tutorials and extensive documentation.
If you would like to download the ML compiler, follow the links from our programming page.
A typical ML programming example was considered to familiarise with the syntax and user-defined types. For this purpose, a list datatype was developed and a simple function was designed to act on that datatype.
The ourlist datatype was defined as:
datatype 'a ourlist = nil | LIST of 'a * 'a ourlist;
The meaning of a recursive datatype was discussed, and also the idea of a
type parameter as represented by 'a. The usage of LIST (and other such
tags) in disjoint union types was particularly confusing to students. It was
easier for some students to understand it in terms of a constructor of the
ourlist datatype, just like the cons used in Lisp.
To illustrate the ideas of pattern matching, we developed a simple
function that works on the ourlist type just defined. The
example taken was to define a count function that takes in a
value and a list, and counts the number of occurences of that value in the
list. Thus the intended semantics of the count function
should allow a call such as the following to work:
- count (1, LIST(2,LIST(1, LIST(1, nil))));
val it = 2 : int
In essence, the above count function call should count the
number of occurences of 1 in the list containing the members 2, 1, 1.
Since we expect to compare the first argument with the members of the
list, the expected type of the count function is:
val count = fn : ''a * ''a ourlist -> int
Then we went ahead and developed the ML code for the count
function, using the obvious recursive idea of breaking a list into a head
and an attached list. The ML pattern matching system was displayed here,
and the required exhaustive nature of the patterns was pointed out. The
final code for the count function designed is given below.
fun count (x,nil) = 0 |
count (x,LIST(y,z)) = if (x=y) then (1+(count (x,z))) else count
(x,z);
We went over the basic type inference system in ML, both at an intuitive level and at an algorithmic level using parse graphs.
To start, the construction of parse graphs was shown by parsing the given ML function as a lambda expression. It was shown that constructing the parse graph bottom upwards seemed to be more intuitive, especially when the final graph was large and deep.
The procedure of type inference was sketched out. The idea of overloaded
functions and the difference between overloading and true parametric
polymorphism was demonstrated using the + operator as an
example. Overloaded functions have different code for different argument types, and
the compiler must be able to figure out the code version to use at compile time.
The examples used to illustrate type inference were mainly from the book, and it would not be worth the effort to repeat the graphical solutions here. The interested student is referred to the examples given in the course text.
October 21, 2002