(page 5) PART 2. Exception Handling, Curried Functions, User-defined Types. Exception Handling. ------------------- * The imperative notion of "control flow" has an implicit counterpart in functional languages -- given an expression like (F (Exp1,Exp2)) we evaluate Exp1, then Exp2, then F. To cope with "error" conditions imperative languages provide several mechanisms for interrupting normal flow of control -- "go to", "break", "exit", "on error do" (PL/1) etc. ML's exception-handling mechanism -- similar to LISP's catch/throw -- is the counterpart of these mechanisms. Example: a function to determine if two lists have the same head. exception empty_list; (* declares "empty_list" to be an exception *) fun HEAD [] = raise empty_list (* interrupt normal flow of control. NO value is returned by HEAD in this case. *) | HEAD (head::tail) = head; (* return a value, as usual *) fun same_head1 (L1,L2) = (HEAD L1) = (HEAD L2); (* if HEAD raises empty_list the evaluation of same_head1 is interrupted and the exception is "repeated" to the function that called same_head1 *) fun same_head2 (L1,L2) = (HEAD L1) = (HEAD L2) handle empty_list => false; (* if HEAD raises empty_list the evaluation of same_head2 is interrupted. The handle catches the exception and returns a normal value which is used in the ordinary evaluation of the function that called same_head1. *) * An exception can have a value associated with it (ML treats exception names as constructors). exception negative_arg of real; (* a value of type real is associated with the exception "negative_arg" *) fun SQRT x = if x >= 0.0 then sqrt x else raise negative_arg x (* Given a negative argument, SQRT raises an exception which carries the argument back to the exception-handler. Note that the type of value carried by the exception needn't be the same as the value ordinarily returned by the function. *) (* the exception-handle can use the value carried back with an exception. For example, the following function takes the coefficients of a quadratic polynomial and returns a list of its distinct roots and the value of the discriminant. *) fun quad_roots (a,b,c) = let val discriminant = (b*b - 4.0*a*c) val d = SQRT discriminant val a2 = 2.0*a in if d = 0.0 then ([~b/a2],discriminant) else ([(~b + d)/a2,(~b - d)/a2],discriminant) end handle negative_arg y => ([],y); * There are two main uses of exceptions. First, to implement partial functions, as the preceding examples illustrate. More complex examples of this are nondeterministic parsing and depth-first search -- on the web at http://www.site.uottawa.ca/~holte/ML/Programs.2 The second use is trapping the exceptions raised by ML that represent run-time errors. For example, arithmetic functions (div,sqrt,ln,...) raise exceptions when given an invalid argument (the exceptions have the same name as the function but with the first letter capitalized). As a second example, control-stack-overflow is an exception that a user can handle. (page 6) Curried Functions. ------------------ * So far, all functions have had just one argument. Using higher-order functions we can get around this to some extent, and create functions whose arguments can be supplied one at a time (e.g. FIRST_ARG). The general idea of changing a function whose argument is an N-tuple into one that takes N separate arguments is called Currying (after Haskell Curry, not the Indian spice, or horse grooming procedure). Compare the following definitions: val ADDa = fn (X,Y) => X+Y:int; (* single argument consisting of a pair *) val ADDb = fn X => (fn Y => X+Y:int); (* two separate arguments. (ADDb 1) is a legal, meaningful expression. *) * Recall that ML provides a convenient shorthand for val ADDa = fn (X,Y) => X+Y:int; namely, fun ADDa (X,Y) = X+Y:int; Likewise there is a shorthand for the definition of ADDb, namely, fun ADDb X Y = X+Y:int; What is the type of ADDb ? * In general, curried functions are more convenient than uncurried ones. We'll use curried functions heavily from now on. User-Defined Types ------------------ * ML permits user-defined types of three kinds: abbreviations, datatypes, and abstract types. * Type abbreviations are not very interesting: the user simply gives a name to an ML type. For example, in a student record you might use the following abbreviations: type Course = string; type Score = int; type Grade = Course * Score; type Student = {Name:string,Age:int,Year:int,Grades:Grade list}; When ML prints out the type of a function, or constant, it uses abbreviations only when forced to by the user. Example: fun pass x = x > 49; has type int-> bool, not Score->bool. * The simplest form of datatype somewhat resembles the Pascal enumerated type. For example datatype Course = cs101 | cs999 | cs242K ; datatype Score = A | Aplus | B | Bplus | C | Fail | Pass | Continue; The elements of these datatypes are constructors, and therefore can appear in patterns. Indeed, functions that take datatypes as arguments almost always are defined by cases: fun credit_hours cs101 = 3 | credit_hours cs999 = 9 | credit_hours cs242k = 6; Different datatypes should not have constructors in common (in some ML's it is a compile-time error). For example, because the following datatypes have the constructor Pass in common: datatype Score = A | Aplus | B | Bplus | C | Fail | Pass | Continue; datatype football_play = Pass | Run | Kick; In ML these can appear in the same program but Pass can only be used in one sense at a time, so Pass, after the second datatype definition, is unambiguously type football_play. (page 7) * More interesting datatypes are ones in which there is a value associated with some (or all) of the constructors. datatype Number = Infinity | R of real | I of int; fun divide (R r1,R r2) = if r2=0.0 then Infinity else (R (r1/r2)) | divide (I i1,I i2) = if i2=0 then Infinity else if (i1 mod i2) = 0 then (I (i1 div i2)) else (R ((real i1)/(real i2))) etc. (there are 9 cases in all) This function is of type Number*Number->Number. * Datatypes can be recursive. The classic definition of a binary tree is datatype 'a btree = LEAF of 'a | NODE of ('a btree*'a btree); fun leaf_list (LEAF x) = [x] | leaf_list (NODE (left,right)) = (leaf_list left) @ (leaf_list right); val tree1 = NODE (NODE (NODE (LEAF 1,LEAF 2), LEAF 3), LEAF 4); They can also be mutually recursive. Here's a definition of slot and frame -- a frame is a collection of slots, and a slot's value may involve a function on frames. datatype 'a Slot = CONSTANT of 'a | FUNCTION of (Frame ->'a) and Frame= FRAME of {id:string Slot, genls:(Frame list) Slot, volume:real Slot, weight:real Slot, density:real Slot}; val f1 = FRAME {id=CONSTANT "everything", genls=CONSTANT [], volume=CONSTANT 24.0, density=FUNCTION ( fn (FRAME { weight=(CONSTANT (w:real)), volume=(CONSTANT (v:real)), ...}) => w/v), weight=CONSTANT 6.0}; * Finally, the user can define abstract types. The type declaration and function definitions are very similar to datatypes. The big difference is that with abstract types the constructors are hidden from the user, so he can manipulate abstract types only by using the initially-provided functions. At the very least, then, an abstract type must provide ways of translating to and from the abstract type. abstype Number = Infinity | R of real | I of int with fun int_to_Number i = I i fun real_to_Number r = R r fun extract_reals [] = [] | extract_reals ((R r)::Tail) = r::(extract_reals Tail) | extract_reals (_::Tail) = (extract_reals Tail) end; - extract_reals [int_to_Number 3,real_to_Number 3.2]; val it = [3.2] : real list