Lecture notes on ML * Some material taken from lecture slides by John Harrison, Univesrity of Cambridge, 1997. * ``ML originally developed in about 1973 at Edinbourgh University...as part ofa theorem proving package called LCF (The Logic of Computable Functions)'' -- http://www.bath.ac.uk/~cs1cb/ML/history.htm * Two main branches of ML are most popular: + Standard ML of New Jersey (SML/NJ) http://www.smlnj.org - Originally developed at Bell Labs and Princeton - Now split off; most active pieces at Yale, AT&T Research, U Chicago + O'Caml http://www.ocaml.org - Developed in France at INRIA - O = ``Objective,'' but we won't use objects in this course - Seems to be most popular dialect, currently - We will use O'Caml for several programming projects * Interesting things about ML: + Has higher-order functions - functions can be parameters and return values + ``Mostly functional'' - Use of side effects (writes to memory) less common + Type inference - Compiler/interpreter will figure out types without declarations - Supports parametric polymorphism (more on this later) + Data types and pattern matching (more later) + Exceptions + Garbage collection * Using O'Caml at Maryland + Installed on junkfood machines in /usr/local/bin + Can download from http://www.ocaml.org --------------------------------------------------------------------------- The Basics of O'Caml * The simplest way to use O'Caml is in interactive mode + Has a ``read-eval-print'' loop + Enter expressions + Terminate with ``;;'' # 5*2;; - : int = 10 - ``-'' is ``the expression last enetered'' - ``:'' means ``has type'' - Notice that the type int has been inferred - And the value, 10, has been displayed + ML will complain when types don't make sense # 1+true;; * Often we'll want to compute intermediate values for later use # let pi = 3.14 in pi *. 3.0 *. 3.0;; + Here *. is multiplication on floating point numbers. + And we need to write 3.0 to get a float + The syntax ``let x = e1 in e2'' means evaluate e1, and bind e1 to x during evaluation of e2 + Compare to C/Java: { T x = e1; e2;} + The binding only holds within evaluation of e2: # pi;; + When we're at the ``top-level,'' as in interactive mode, can omit ``in'' to mean ``from now on:'' # let pi = 3.14;; # pi;; * We can also define functions using let: # let next x = x + 1;; # next 3;; * For functions with multiple arguments, list one next to another # let plus x y = x + y;; # plus 1 2;; * ML allows functions to take other functions as arguments and return functions as results + Consequently, can play a trick called ``currying'' to (pretend) that all functions take one argument + So plus is actually a function that takes an integer as an argument and returns another function. # let foo = plus 3;; # foo 4;; + Example of function that takes another function as an argument # let bar f = 2*(f 2);; # bar incr;; # bar (plus 3);; * Since functions are ``first class,'' it's sometimes convenient to create a function without giving it a name # bar (fun x -> -x);; + The syntax is ``fun arg1 ... argn -> body'' So that means that let f arg1 ... argn = e is just shorthand for let f = fun arg1 ... argn -> e Compare: let next x = x + 1;; let next = fun x -> x + 1;; let plus x y = x + y;; let plus = fun x -> (fun y -> x + y);; + or, can omit the parentheses let plus = fun x -> fun y -> x + y;; * Functions can also be recursive; use letrec: # let rec fact n = if n = 0 then 1 else n * fact (n-1);; # fact 6;; + Remember, this is shorthand for let rec fact = fun n -> if n = 0 then 1 else n * fact (n-1);; + So here's the difference between let and letrec: let x = e1 in e2 x in scope within e2 let rec x = e1 in e2 x in scope within e2 *and* e1 ==> let rec only makes sense for recursive functions (in ML) * Finally, functions in ML can be ``polymorphic'' + These are functions that can take *any* type # let id x = x;; # id 1;; # id true;; # id ();; # id "foobar";; # (id id) 1;; The type ``unit'' is a type with only one member, ``()''. Think of this as the equivalent of ``void.'' The type 'a -> 'a means: For any 'a, this function has type 'a -> 'a. + More on polymorphism later on --------------------------------------------------------------------------- Interacting with O'Caml * Can use read-eval-print loop * Can use ``#use "filename.ml"'' to load files in + Just as if you typed them example.ml: let pythag x y z = x*x + y*y + z*z;; pythag 3 4 5;; pythag 5 12 13;; pythag 1 2 3;; -- # #use "example.ml" + Terminates reading with first error example2.ml: let foo a b = a + b;; 1 + false;; let bar a b = a + b;; -- # use "example2.ml";; * Comments with (* *) # (* this is a comment *) let x = 3;; + Can be properly nested (unlike C /* */) # (* this (* is *) a comment *) let x = 3;; * Compiling with ocamlc % ocamlc example.ml % ./a.out * Printing with print_ # print_string "hello";; example3.ml: let pythag x y z = x*x + y*y + z*z;; print_int (pythag 3 4 5);; pythag 5 12 13;; pythag 1 2 3;; print_string "hello\n";; -- % ocamlc example3.ml % ./a.out * Compile with -g to build a file with debugging information * Debug with ``ocamldebug'' % ocamlc -g example3.ml % ocamldebug a.out --------------------------------------------------------------------------- Pattern Matching * ML allows you to define new types # type t = int;; + Can declare types using ``:'' syntax # let foo (x:t) = x + 1;; # let foo x:t = x + 1;; * ML also lets you define types for data structures + ``Disjoint sums'' or ``tagged unions'' # type mylist = Nil | Cons of int * mylist;; # Nil;; # Cons (3, Nil);; + Nil and Cons are called ``constructors'' * We write functions on mylist using ``pattern matching'' # let rec sum = function Nil -> 0 | Cons (x, xs) -> x + (sum xs);; # sum Nil;; # sum (Cons(3,Cons(4,Nil)));; # let rec sum l = match l with Nil -> 0 | Cons (x, xs) -> x + (sum xs);; * Use _ in pattern matches when you don't care about an element # let rec len = function Nil -> 0 | Cons (_, xs) -> 1 + (sum xs);; * Warnings issued when pattern matching not exhaustive # let hd = function Cons (x, xs) -> x;; # hd (Cons (3, Cons (4, Nil)));; # hd Nil;; * Lists of integers are rather restrictive; we'd like to build lists of ``anything'' + Use polymorphism # type 'a mylist2 = Nil | Cons of 'a * ('a mylist2);; # Nil;; # Cons (3, Nil);; # Cons (3, Cons (true, Nil));; # let rec len = function Nil -> 0 | Cons (_, xs) -> 1 + (len xs);; # len (Cons (3, Nil));; # len (Cons (true, Nil));; * Of course, lists are built in to O'Caml, with much better syntax # [1; 2; 3; 4];; # [];; # 1 :: [2;3;4];; # let rec len = function [] -> 0 | (x::xs) -> 1 + (len xs);; # len [1;2;3];; * The combination of polymorphism and higher-order functions is a powerful combination with lists # let rec map f = function [] -> [] | (x::xs) -> (f x)::(map f xs);; # map (fun x -> x + 1) [1;2;3];; # let rec fold f z = function [] -> z | (x::xs) -> (fold f (f z x) xs);; # fold (fun a x -> a + x) 0 [1;2;3];; # fold (fun a _ -> a + 1) 0 [1;2;3;4];; --------------------------------------------------------------------------- Side Effects * O'Caml is *mostly* functional, but it does include support for side-effects + Writing to memory * Unlike C, you can't change the type of a variable # let x = 3;; # x := 4;; + This doesn't make any sense * To get memory that can be updated, use ref # let x = ref 0;; + Use ! to dereference a pointer # 3 + !x;; + Use := to update through a pointer # x := !x + 1;; * Putting these together, we can get a counter # let count = let c = ref 0 in fun () -> c := !c + 1; !c;; # count();; # count();; * ML also includes exceptions # exception My_exn;; # raise My_exn;; # let foo () = raise My_exn;; # try (foo (); print_string "hello") with My_exn -> print_string "goodbye";; --------------------------------------------------------------------------- Modules and the O'Caml Library * ML includes a fairly sophisticated module system for breaking large programs into smaller components. * Simple example: A stack module. stack.ml: module Stack = struct type 'a t = 'a list ref let create () = ref [] let push x s = s := x::!s let hd (x::_) = x let tl (_::xs) = xs let pop s = let t = hd !s in s := tl !s; t end;; -- # #use "stack.ml";; * Notice that ML has come up with a signature for Stack + More on this in a bit * Things in the module are accessed with ``.'' # let s = Stack.create();; # Stack.push s 3;; # Stack.push s 4;; # Stack.pop s;; # Stack.pop s;; # Stack.pop s;; * Notice that type t is exposed + Clients know what the internal represenation of stacks is * Notice that hd, tl functions are exposed + Even though they're purely internal to the module * Solution: Explicitly assign stacks a more restrictive signature stack2.ml: module HiddenStack : sig type 'a t val create : unit -> 'a t val push : 'a t -> 'a -> unit val pop : 'a t -> 'a end = Stack;; -- # use "stack2.ml";; # Stack.hd [1;2;3];; # HiddenStack.hd [1;2;3];; # let s = Stack.create ();; # let hs = HiddenStack.create ();; * ML includes a standard library containing many useful modules % cd /usr/local/ocaml/lib/ocaml * Each module is split into two files: + module.mli -- the signature + module.ml -- the code + With no sig or struct declarations + The O'Caml compiler knows what to do with these specially + (See project 2 for another example) % less list.mli % less list.ml * ML also includes ``functors,'' which allow you to create modules from other modules functor.ml: module type OrderedType = sig type t val compare : t -> t -> int end module Set(Ord : OrderedType) = struct let create () = [] let rec insert elt = function [] -> [elt] | (x::xs) -> if Ord.compare x elt < 0 then x::(insert elt xs) else elt::(x::xs) end module Int = struct type t = int let compare x y = x - y end module IntSet = Set(Int) -- # #use "functor.ml";; # let s1 = IntSet.create ();; # let s2 = IntSet.insert 2 s1;; # let s3 = IntSet.insert 3 s2;; # let s4 = IntSet.insert 1 s3;; + Warning: Types get a little complicated with functors - Sometimes You need to use ``with'' to tell O'Caml when two types are equal - See O'Caml documentation for more information