In this section, we set out to conquer the basics of ML syntax. Our exegetical strategy will be to make a bottom-up pass through the grammar. In other words, we will start with simple things (constants, variables) and proceed to consider how more complex expressions are constructed from simpler ones. By the end we will have covered most of the ways in which an ML program can be built. We will follow the close association between the form of a program and its type. ML programming emphasizes the consideration of types, as we shall see.
The read-eval-print loop allows one to interact with the ML interpreter, entering ML expressions (including programs), and getting answers back. This mode is commonly used in program development. Our examples will primarily be presented by using the interactive system.
The batch compiler is like that for many compiled languages, generating object code files which can be linked together to obtain stand-alone executables.
Whether it resides in a file, or is cut-and-pasted into an interactive session, a program is processed as follows:
Note. Since ML is an expression-based language, the distinction between expressions and programs is blurred. Therefore even very simple expressions, like the expression 42 for example, count as programs and are dealt with as just described.
Each type provided by the ML implementation tends to have an associated structure of the same name, wherein various useful functions on that type are collected.
Sample
Type Constants Structure
-------------------------------------------------
bool true, false Bool
int ... ~1, 0,1,0xF, ... Int
real 1.0, 0.1, 3.32E5, ... Real
char #"a", #"b", #"c", ... Char
string "", "foo\n", "\127", ... String
word8 0w255, 0wxFF, ... Word8
unit ()
instream stdIn TextIO
outstream stdOut, stdErr TextIO
time zeroTime Time
The types bool, int,
real, char, and string
are just the same as those found in a typical programming language. The
type word8 represents 8 bit bytes. There is also
another type word found in structure Word
which represents the type of n bit words, where n
depends on the word size of the machine.
The unit type has just one element: (). It is useful when programming with imperative constructs.
For performing input and output, there are types of input streams instream and outstream, along with the usual pre-defined streams. These are found in the structure TextIO. Binary versions of these may be found in BinIO, at least in MoscowML.
For measurements, there is a time type, with a constant representing a starting time.
val pat = exp
where a pattern pat is an expression built out of variables and
constants. If the structure of pat matches that of
exp, i.e., can be made identical by substituting for the
variables of pat, then the equalizing substitutions get added
to the current environment. In the following, x can obviously
be made identical to 2:
- val x = 2
> val x = 2 : int
- val y = x
> val y = 2 : int
After the second binding, y and x have the same value,
but they do not point to the same storage location. The next bindings
show further pattern matching behaviour.
- val 2 = x;
-
- val 3 = x
! Uncaught exception:
! Bind
The last binding attempt fails because 3 is not equal
to 2.
Another kind of pattern is wildcards, which are represented by an underscore. No binding is made to a wildcard position in a pattern. One can think of a wildcard as a variable guaranteed not to occur anywhere else in the program.
- val _ = 2;
Variables and wildcards are basic patterns.We will see more
complex patterns in due course.
let val x = 1
val y = 2
in
x + y
end
local val x = 1
val y = 2
in
val z = x + y
end
- val t = ("Dave", 1, true);
> val t = ("Dave", 1, true) : string * int * bool
- val r = {name="Dave", rank = 1, inClub=true};
> val r = {inClub = true, name = "Dave", rank = 1}
: {inClub : bool, name : string, rank : int}
Elements are accessed via indices (tuples) or field names (records)
#1 t = "Dave" : string
#2 t = 1 : int
#3 t = true : bool
#name r = "Dave"
#rank r = 1 : int
#inClub r = true : bool
The syntax of patterns has tuple and record patterns. These allow
simultaneous binding.
- val (a,_,c) = t;
> val a = "Dave" : string
val c = true : bool
- val {name, inClub, ...} = r;
> val name = "Dave" : string
val inClub = true : bool
A function application (M N) is an expression that applies function M to argument N. For example, the expression Char.chr 50 is the application of the function Char.chr, which has type int -> char, to the number 50.
- Char.chr 50; > val it = #"2" : charIn general terms, if M has type ty1->ty2, and N has type ty1, then (M N) is well-typed and has type ty2.
The evaluation order of ML is call-by-value. This means that a function appliction (M N) is evaluated by evaluating M to yield a function f and evaluating N to a value x. Then f is run on x.
Replicated application associates to the left: (M N O P) is understood as (((M N) O) P). For this to be well-typed, M must have the type ty1->ty2->ty3->ty4, where ty1,ty2,ty3 are the types of N,O,P, respectively. If M has a type of such a shape, it is said to be a Curried function (after Haskell Curry).
An uncurried function has a single argument, which is a tuple or a record. If M above were uncurried, its application would be M (N,O,P).
Type Functions Structure ------------------------------------------------------ bool andalso, orelse, not Bool int ~,+,-,*,div,mod,<,<=,>,>= Int real (same as int) Real char chr, ord Char string explode, implode, sub, ^ String word andb, orb, xorb Word instream openIn, closeIn, input TextIO outstream openOut, closeOut, output TextIO time now, toSeconds, toMilliseconds Time
fun fib 0 = 1 | fib 1 = 1 | fib n = fib(n-1) + fib(n-2)
fn (1::t) => 0 | (x::_) => x | [] => 13
fun ([] @ l) = l | ((h::t) @ l) = h::(t@l)
fun map f [] = [] | map f (h::t) = f h :: map f t
fun filter P [] = []
| filter P (h::t) = if P h then h::filter P t
else filter P t
fun rev_itlist f [] e = e | rev_itlist f (h::t) e = rev_itlist f t (f h e)
fun zip (h1::t1) (h2::t2) = (h1,h2) :: zip t1 t2 | zip l1 l2 = []
fun valOf (SOME x) d = x | valOf NONE d = d
datatype (tyv1, ..., tyvn)name
= C1 of ty_1,1 * ... * ty_1,k1
|
.
.
.
| Cm of ty_m,1 * ... * ty_m,km
datatype 'a tree = LEAF
| NODE of 'a tree * 'a * 'a tree
LEAF : 'a tree
NODE : 'a tree * 'a * 'a tree $->$ 'a tree
fun isin test LEAF = false
| isin test (NODE (t1,y,t2)) =
if test y
then true
else isin test t1 orelse isin test t2
fun preorder LEAF = []
| preorder (NODE(l,v,r)) = preorder l@[v]@preorder r;
fun inorder LEAF = []
| inorder (NODE(l,v,r)) = v::(inorder l@inorder r);
fun postorder LEAF = []
| postorder (NODE(l,v,r)) = postorder r@[v]@postorder l;
fun flat [] = []
| flat (h::t) = h @ flat t
fun flat [] = []
| flat ([]::rst) = flat rst
| flat ((h::t)::rst) = h :: flat (t::rst)
fun lmod5 (a::b::c::d::e::rst) = [a,b,c,d,e]::lmod5 rst
| lmod5 l = [l]
- zip (map inc [1,2,3])
(map (tackon "ly") ["slow","quiet","swift"])
> val it = [(2,"slowly"), (3,"quietly"), (4,"swiftly")]
: (int * string) list
fun qsort [] = []
| qsort (h::t) =
let val l1 = List.filter (curry (op >) h) t
val l2 = List.filter (curry (op Int.<) h) t
in qsort l1 @ [h] @ qsort l2
end
fun Qsort ord [] = []
| Qsort ord(h::t) =
let val l1 = List.filter(not o (ord h)) t
val l2 = List.filter(ord h}) t
in Qsort ord l1 @ [h] @ Qsort ord l2
end
abstype 'a tree =with end
- val x = ref 1; > val x = ref 1 : int ref - val () = x := 2; - !x; > val it = 2 : int
- val r = ref 1; > val r = ref 1 : int ref - fun cv() = !r; > val cv = fn : unit -> int - cv(); > val it = 1 : int - r := 2; > val it = () : unit - cv(); > val it = 2
- val x = 1; > val x = 1 : int - fun cv() = x; > val cv = fn : unit -> int - cv(); > val it = 1 : int - val x = 2; > val x = 2 : int - cv(); > val it = 1
let val fref = ref (fn x => x)
in
fref := fn x => x + 1
;
!fref true
end
- fun K x y = x;
- fun I x = x;
- (I,K);
> val ('a, 'b, 'c) it = (fn, fn) : ('a -> 'a) * ('b -> 'c -> 'b)
- val x = K I;
! Warning: Value polymorphism:
! Free type variable(s) at top level in value identifier x
> val x = fn : 'a -> 'b -> 'b
- fun mem eq x [] = false
| mem eq x (h::t) = eq x h orelse mem eq x t
> val ('a,'b) mem = fn:('a->'b->bool) -> 'a -> 'b list -> bool
- fun mem x [] = false
| mem x (h::t) = x=h orelse mem x t
> val ''a mem = fn : ''a -> ''a list -> bool
exception ERROR of string; (* declare our exception *)
fun open_file st =
if st = "" orelse FileSys.access(st,[])
then raise ERROR ("Unable to open file: " ^ st)
else TextIO.openOut st
val ostrm = open_file "foo"
handle ERROR s => take some appropriate action
fun mapfilter f [] = []
| mapfilter f (h::t) =
let val t' = mapfilter f t
in
f h :: t' handle _ => t'
end
(* repeat : ('a -> 'a) -> 'a -> 'a *)
fun repeat f =
let exception LAST of 'a
fun loop x =
let val y = (f x handle
Interrupt => raise Interrupt
| otherwise => raise (LAST x))
in loop y
end
in fn x => loop x handle (LAST y) => y
end
In the following example, we use repeat to find the maximum
element of the int type.
- Mosml.time (repeat inc) 0;
> User: 144.730 System: 0.010 GC: 0.000 Real: 144.886
> val it = 1073741823 : int
Caution. The above example will not terminate on
implementations of ML that implement int with bignums.
Konrad Slind, slind@cs.utah.edu