ISBN 0-321-33025-0Lecture 3Lecture 3Lecture 3Lecture 3Introduction to MLCopyright © 2006 Addison-Wesley. All rights reserved. 1-2Imperative Programming vs Functional ProgrammingExample: factorial functionJava version ML version int fact(int n) {if(n<=0)return 1;return n*fact(n-1);}fun fact x =if x <= 0 then 1 else x * fact(x-1);Copyright © 2006 Addison-Wesley. All rights reserved. 1-3Imperative Programming• Revolves around the assignment statement and the concept of an updateable memory. • Programs are aimed at modifying memory in a certain wayCopyright © 2006 Addison-Wesley. All rights reserved. 1-4Functional Programming• Computation based on functions as described by mathematicians• No variables• No assignments• No loops• Functions are first-class valuesCopyright © 2006 Addison-Wesley. All rights reserved. 1-5ML ("MetaLanguage")• Mostly functional • Safe• All definitions and expressions are type checked prior to execution.Major dialects:• Standard ML (SML)• Objective CAML (OCaml)Copyright © 2006 Addison-Wesley. All rights reserved. 1-6How to run ML?• The command is “sml”• Two ways of running ML code:– Type it in directly into ML system– Write code in ML using a text editor, save it in to a .sml file, and then type inuse ““““yourfilename.sml";Copyright © 2006 Addison-Wesley. All rights reserved. 1-7ML Expressions• They include variables, arithmetic expressions, boolean expressions, conditional expressions, function calls and more. • Expressions are charactized by two properties: their typeand their value.• Their value is computed by the system when they are evaluated.Copyright © 2006 Addison-Wesley. All rights reserved. 1-8ML expressions and typesbooltruetrue andalso falsefalse orelse (not false)if true then 5 else 6int4~45 + 67 * 9999 div 7typesexpressionsCopyright © 2006 Addison-Wesley. All rights reserved. 1-9ML expressions and typesunit()string“hello”“the” ^ “ “ ^ “bomb\n”char#”c”#”\n”typesexpressionsCopyright © 2006 Addison-Wesley. All rights reserved. 1-10ML operators• The usual operators, +, *, -, <, >, <=, >=, != can be applied to a pair of int's or to a pair of real's, but not to mixed types - int * real or real * int. • The function real converts its int argument to a real return value. • 3 + 5 has type int;• 3.0 + real(5) has type real;• 3.0 + 5 is a type mismatch (type clash) errorCopyright © 2006 Addison-Wesley. All rights reserved. 1-11ML declarations • Declarations are used to – define functions (function declarations)– give a name to the value of an expression (variable declarations)Copyright © 2006 Addison-Wesley. All rights reserved. 1-12Variable declarationsValue declarations use the keyword valand have the general formval id = expwhere idis any identifier and expis any expression. The effect of the declaration is to bind the identifier to the value of the expression.Copyright © 2006 Addison-Wesley. All rights reserved. 1-13Type Declaration• A type constraint such as ":int" or ":real" can be used after an expression and is sometimes necessary to clarify which operator is intended.Copyright © 2006 Addison-Wesley. All rights reserved. 1-14Examples of variable declarationsval x:int = 5;x + x;let val x:int = 7val y:int = 8in x * y end;(* ML will infer types: *)val x = 5;x + x;let val x=7 val y = 8 in x * y end;Copyright © 2006 Addison-Wesley. All rights reserved. 1-15Function declarations• Function declarations use the keyword funand have the general formfun id (x,y,z) = exp– where idis the function name, (x,y,z)is the parameter list, and expis the body of the function.Copyright © 2006 Addison-Wesley. All rights reserved. 1-16Examples of function declarationsfun add1 (x) = x + 1;fun add1 x = x + 1;fun add1 (x:int):int = x + 1;Copyright © 2006 Addison-Wesley. All rights reserved. 1-17Examples of function callsadd1 (5);add1 5;add1 (add1 5);Copyright © 2006 Addison-Wesley. All rights reserved. 1-18Using existing functionssize;size “hello”;val f: string->int = size;Int.toString;Int.toString 50;print;print “hello\n”;print (Int.toString 50);print (Int.toString (size “hello”));Copyright © 2006 Addison-Wesley. All rights reserved. 1-19Multiple argumentsfun add1both (x:int, y:int): int * int= (x + 1, y + 1);add1both (2, 3);Copyright © 2006 Addison-Wesley. All rights reserved. 1-20Multiple argumentsfun add1both (x, y) = (x + 1, y + 1);add1both (2, 3);Copyright © 2006 Addison-Wesley. All rights reserved. 1-21Functions and type inference• Example:fun fact n = if n=0 then 1 else n * fact(n-1)Copyright © 2006 Addison-Wesley. All rights reserved. 1-22Recursive functionsfun fact (n:int):int =if n = 0 then 1else n * fact (n - 1);fact 5;Copyright © 2006 Addison-Wesley. All rights reserved. 1-23Mutual recursionfun f (x:int):int = g (x + 1)and g x = f (x + 1);Copyright © 2006 Addison-Wesley. All rights reserved. 1-24Tuples(5, “hello”, true);val x = (5, “hello”, true);val (y1, y2, y3) = x;val (_,z2,_) = x;Tuples are expressions of the form (e1, ..., en). Its type is the Cartesian product of the types of its component expressions, (t1 * ... * tn)Its value is the tuple of the values of the component expressions, (v1, ..., vn).Copyright © 2006 Addison-Wesley. All rights reserved. 1-25Tuples as argumentsfun add1both (x, y) = (x + 1, y + 1);add1both (2, 3);Copyright © 2006 Addison-Wesley. All rights reserved. 1-26Nested tuplesExample:(1, (2, 3), 4)What is its type?Copyright © 2006 Addison-Wesley. All rights reserved. 1-27Lists• Lists provide a data structure for a list of an unbounded number of expressions all of the same type. • Examples:[1, 2, 3, 4, 5];Head: 1Tail: [2, 3, 4, 5]Copyright © 2006 Addison-Wesley. All rights reserved. 1-28Lists5::nil;5::6::nil;5::6::7::nil;[5];[5, 6];[5, 6, 7];val x: int list = [5, 6, 7];length x;rev x;Copyright © 2006 Addison-Wesley. All rights reserved. 1-29Lists• :: operator (right-associative)2::[3, 4]1::2::3::4::nil• nil empty listCopyright © 2006 Addison-Wesley. All rights reserved. 1-30Head and tailhd;hd [1,2,3,4];tl;tl [1,2,3,4];Copyright © 2006 Addison-Wesley. All rights reserved. 1-31Sample ML Code> fun fact n =if n = 0 then 1 else n * fact(n-1);val fact = fn: int -> int> val Pi = 3.14159;val Pi = 3.14159 : real> 2 :: [3,4];val it = [2,3,4] : int list> (1,2,3.1);val it = (1,2,3.1) : int * int * real> fun append([],L) = L| append(h::t,L) =
View Full Document