Where is ML? Put this in your path, type "sml" to get the interpreter:
/afs/cs.unc.edu/project/courses/comp145/sml <--- directory /afs/cs.unc.edu/project/courses/comp145/sml/sml <--- the interpreter this is an older version of SML and there will be some difference
How does one "feed" the interpreter?
Overview of basic ML features/semantics
basic types: int, real, string, char, boolean type constructors: list, tuple, function list * -> (syntax in type expressions) logical ops: orelse, andalso, not numeric negation in ~ (not - as in most languages) orthogonality... all types in ML are first class
tuples: like records, heterogeneous element types finite, fixed length #2(10,11,12) gives 11 #3(#"a","xyz",25.3) gives 25.3 #"a" is the syntax for the single char "a" as opposed to a string in newer versions of SML (PC version) lists [1,2,3] sortof like a tuple, but homogeneous (all elements of the same type) length can change as you add elements :: cons operator... combine element and list 1::[2,3] @ concat operator... combine two lists [1,2]@[3,4,5] hd, tl head, tail for lists (old LISP "car", "cdr") explode("abcde") --> ["a", "b", "c", "d", "e"] implode(["1", "2", "3"]) --> "123"
Typing ML is strongly typed... no type conversions or coercions done for you ML does type inference... programmer rarely has to give type information or type declarations identifiers are not bound to specific types... you are free to rebind identifiers to values that have different types scope... there is a top level environment containing the types, functions, etc. of the "standard basis" environment is a set of bindings... name bound to value you can think of this as a Perl hash, or a Python dictionary however, order of binding creations is important a new binding to a name hides older ones to the same name but it does not destroy them bindings are added to the environment as computations progresses computation is nothing more than evaluating expressions some expressions produce functions as their values (i.e., function definition, or declaration) some expressions have side effects that we really want and we don't care about the value produced by evlauation (i.e., print, output)
fun sq(x) = x*x ; <-- error... type system cannot tell if * is int or real fun sq1(x:real) = x*x ; fun sq2(x) = (x:real)*x ; - sq1 = sq2 ; !!!
try this val x = 5; fun wow z = z + x; wow 9; val x = 10; wow 9; this shows something of how bindings work...
fun rev L = (* note use of list operators *) (* note comments in ML *) if L = nil then nil else rev( tl(L)) @ [hd(L)] ; >> val rev = fn : ''a list -> ''a list this introduces equality types some ML types can be compared for equality, some cannot full "polymorphism" is a function that allows ANY type as argument >> val rev = fn : ''a list -> ''a list here the ''a is a type variable, but the '' means it is restricted to being an equality type functions, for example, are not equality types... try - rev = rev ; !!! reals are not equality types in the new versions of SML (but this works... 2.3 <= 2.3 andalso 2.3 >= 2.3 this works... x <= y andalso y <= x ) int, string, boolean are equality types list, tuple are equality types if their elements are equality types try (2,14) = (2,14) try (2,14.3) = (2,14.3) try [2.4, 4.5, 6.0] = [2.4, 4.5, 6.0] try [2.4, 4.5, 6.0] = [2.4, 4.5, 6.1] fun rev L = (* note use of list operators *) (* note comments in ML *) if null(L) then nil else rev( tl(L)) @ [hd(L)] ; >> val rev = fn : 'a list -> 'a list and there is still another way... with patterns... to follow
By the way... let's look at this if/then/else expression all expressions have types... the type of the value produced when the expression is evaluated if (someBool) then 5 else 14.7 what is the type? What is the type of the value produced? In ML the "then" expression and the "else" expression must have the same type, and the type of the entire "if" is that type. There must always be an "else" if (someBool) then 5 ; What type would this produce? Not legal...
mutual recursion (forward declarations) fun take(L) = (* picks off every other list elt, starting with first *) if L=nil then nil else hd(L)::skip(tl(L)) and skip(L) = (* picks off every other list elt, skips first *) if L=nil then nil else take(tl(L)) ;
pattern matching an alternative to the "if...then...else" style of fun def we have seen so far we can define a function based on patterns its parameters might have this is essentially defining a function as a sequence of partial functions x::xs is common pattern... matches any non-empty list (has a hd) cannot use one var twice in one pattern: x::x::xs to say first two elts are the same... NO x::y::zs must be used and x=y enforced in code fun rev(nil) = nil | rev(x::xs) = rev(xs) @ [x] ; >> val rev = fn : 'a list -> 'a list here, the alternatives ("|") are checked in order defined until one is found where the parameter pattern matches the arguments during evaluation
Note this form of definition does not require equality types!! since there is no "L = nil" comparison in the code. Note the types... earlier form is >> val rev = fn : ''a list -> ''a list whereas this form with patterns in the definition is >> val rev = fn : 'a list -> 'a list Try creating a list containing functions (not an eq type) and then apply each form of fun "rev" to the list... one works, one doesn't.
Pattern example polynomial arithmetic (* add poly P to poly Q *) fun pa (P,nil) = P | pa (nil,Q) = Q | pa ((p:real)::ps, q::qs) = (p+q)::pa(ps,qs); (* mult poly P by scalar q *) fun sm (nil,q) = nil | sm ((p:real)::ps,q) = (p*q)::sm(ps,q); (* mult poly P by poly Q *) fun pm (P,nil) = nil | pm (P,q::qs) = pa(sm(P,q), 0.0::pm(P,qs)); Here the input data format is this: x^2 + 5x - 7.2 --> [~7.2, 5.0, 1.0]
"as" giving names to patterns (* merges two sorted lists, sorted smallest first *) fun merge(nil,M) = M | merge(L,nil) = L | merge(L as x::xs, M as y::ys) = if (x:int) < y then x::merge(xs,M) else y::merge(L,ys) ;
Use of "_" as don't-care wildcard Each occurrance means a different variable consider computing "n choose m" fun comb(_,0) = 1 | comb(n,m) = if m=n then 1 else comb(n-1,m) + comb(n-1,m-1);
What can be a pattern? x::xs tuples and lists also (* sums all integers found in list of pairs *) fun sumPairs (nil) = 0 | sumPairs ((x,y)::zs) = x + y + sumPairs(zs) ; (* takes list of int lists, sums all integers *) fun sumLists (nil) = 0 | sumLists (nil::YS) = sumLists(YS) | sumLists ((x::xs)::YS) = x + sumLists(xs::YS) ;
Subtle pattern bug fun reverse(niil) = nil | reverse(x::xs) = reverse(xs) @ [x] ; Here, the misspelling leads to a pattern that matches anything... this is ok, you get overlapping patterns... ML trys to match arguments to patterns in the order they are declared.
SURPRISE ... up to now we have only seen function definitions with ONE parameter. fun rev (L) = if L = nil then nil else rev( tl(L)) @ [hd(L)] ; >> here, the ONE parameter is a tuple with one elt, the list L fun plus (a:int, b) = a + b ; >> here, the ONE argument is a tuple (a,b) and you are using patterns to locally bind names to parts of the pattern try this for clarity: fun plus (T as (a:int,b)) = #1 T + #2 T ; or fun plus (T as (_:int,_)) = #1 T + #2 T ;
Curried functions fun add(x,y) = x+y : int; >> val add = fn : int * int -> int see, the domain of the ONE argument is int * int, a tuple fun add x y = x + y : int ; >> val add = fn : int -> int -> int think fn: int -> (int -> int) here, it says add is a "partial function" of one argument, that produces another function of one argument. add 2 3; >> val it = 5 : int add 2; >> val it = fn : int -> int it 3; >> val it = 5 : int
Coming next... user defined types (beyond tuples and lists)
higher level functions
modules, signatures, functors