CIS 500Software FoundationsFall 2006September 11AdministriviaRecitationsRecitations start this week.Thursday, 10:30-12:00 Loc ation TBA ReviewFriday, 10:30-12:00 Loc ation TBA AdvancedStudy GroupsAnybody still want help forming a group?Homework 2Homework 1 was due at noon today.Homework 2 will be available by this evening and will be due nextMonday at noon.IRead Chapter 6 of Jason Hickey’s “Introduction to theObjective Caml Programming Language” before startingClass mailing listIf you have not been receiving messages for the class, please sendme an email and I will add you.Questions from last time...Are there any?On With OCaml...Basic Pattern MatchingRecursive functions on lists tend to have a standard shape: we testwhether the list is empty, and if it is not we do something involvingthe head element and the tail.# let rec listSum (l:int list) =if l = [] then 0else List.hd l + listSum (List.tl l);;OCaml provides a convenient pattern-matching construct thatbundles the emptiness test and the extraction of the head and tailinto a single syntactic form:# let rec listSum (l: int list) =match l with[] -> 0| x::y -> x + listSum y;;Pattern matching can be used with types other than lists. Forexample, here it is used on integers:# let rec fact (n:int) =match n with0 -> 1| _ -> n * fact(n-1);;The _ pattern here is a wildcard that matches any value.Complex PatternsThe basic elements (constants, variable binders, wildcards, [], ::,etc.) may be combined in arbitrarily complex ways in matchexpressions:# let silly l =match l with[_;_;_] -> "three elements long"| _::x::y::_::_::rest ->if x>y then "foo" else "bar"| _ -> "dunno";;val silly : int list -> string = <fun># silly [1;2;3];;- : string = "three elements long"# silly [1;2;3;4];;- : string = "dunno"# silly [1;2;3;4;5];;- : string = "bar"Type InferenceOne pleasant feature of OCaml is a powerful type inferencemechanism that allows the compiler to calculate the types ofvariables from the way in which they are used.# let rec fact n =match n with0 -> 1| _ -> n * fact(n-1);;val fact : int -> int = <fun>The compiler can tell that fact takes an integer argument becausen is used as an argument to the integer * and - functions.Similarly:# let rec listSum l =match l with[] -> 0| x::y -> x + listSum y;;val listSum : int list -> int = <fun>Polymorphism (first taste)# let rec length l =match l with[] -> 0| _::y -> 1 + length y;;val length : ’a list -> int = <fun>The ’a in the type of length, pronounced “alpha,” is a typevariable standing for an arbitrary type.The inferred type tells us that the function can take a list withelements of any type (i.e., a list with elements of type alpha, forany choice of alpha).We’ll come back to polymorphism in more detail a bit later.TuplesItems connected by commas are “tuples.” (The enclosing parensare optional.)# "age", 44;;- : string * int = "age", 44# "professor","age", 33;;- : string * string * int = "professor", "age", 33# ("children", ["bob";"ted";"alice"]);;- : string * string list ="children", ["bob"; "ted"; "alice"]# let g (x,y) = x*y;;val g : int * int -> int = <fun>How many arguments does g take?Tuples are not listsPlease do not confuse them!# let tuple = "cow", "dog", "sheep";;val tuple : string * string * string ="cow", "dog", "sheep"# List.hd tuple;;This expression has type string * string * stringbut is here used with type ’a list# let tup2 = 1, "cow";;val tup2 : int * string = 1, "cow"# let l2 = [1; "cow"];;This expression has type string but is hereused with type intTuples and pattern matchingTuples can be “deconstructed” by pattern matching:# let lastName name =match name with(n,_,_) -> n;;# lastName ("Pierce", "Benjamin", "Penn");;- : string = "Pierce"Example: Finding wordsSuppose we want to take a list of characters and return a list oflists of characters, where each element of the final list is a “word”from the original list.# split [’t’;’h’;’e’;’ ’;’b’;’r’;’o’;’w’;’n’;’ ’;’d’;’o’;’g’];;- : char list list =[[’t’; ’h’; ’e’]; [’b’; ’r’; ’o’; ’w’; ’n’];[’d’; ’o’; ’g’]](Character constants are written with single quotes.)An implementation of split# let rec loop w l =match l with[] -> [w]| (’ ’::ls) -> w :: (loop [] ls)| (c::ls) -> loop (w @ [c]) ls;;val loop : char list-> char list-> char list list= <fun># let split l = loop [] l;;val split : char list -> char list list = <fun>Note the use of both tuple patterns and nested patterns. The @ope rator is shorthand for List.append.Aside: Local function definitionsThe loop function is completely local to split: there is no reasonfor anybody else to use it — or even for anybody else to be able tosee it! It is good style in OCaml to write such definitions as localbindings:# let split l =let rec loop w l =match l with[] -> [w]| (’ ’::ls) -> w :: (loop [] ls)| (c::ls) -> loop (w @ [c]) ls inloop [] l;;In general, any le t definition that can appear at the top level# let ...;;# e;;;can also appear in a let...in... form.# let ... in e;;;A Better SplitOur split function worked fine for the example we tried it on.But here are some other tests:# split [’a’;’ ’;’ ’;’b’];;- : char list list = [[’a’]; []; [’b’]]# split [’a’;’ ’];;- : char list list = [[’a’]; []]Could we refine split so that it would leave out these spuriousempty lists in the result?Sure. First rewrite the pattern match a little (without changing itsbe havior):# let split l =let rec loop w l =match w,l with_, [] -> [w]| _, (’ ’::ls) -> w :: (loop [] ls)| _, (c::ls) -> loop (w @ [c]) ls inloop [] l;;Then add a couple of clauses:# let better_split l =let rec loop w l =match w,l with[],[] -> []| _,[] -> [w]| [], (’ ’::ls) -> loop [] ls| _, (’ ’::ls) -> w :: (loop [] ls)| _, (c::ls) -> loop (w @ [c]) ls inloop [] l;;# better_split [’a’;’b’;’ ’;’ ’;’c’;’ ’;’d’;’ ’];;- : char list list = [[’a’; ’b’]; [’c’]; [’d’]]# better_split [’a’;’ ’];;- : char list list = [[’a’]]# better_split [’ ’;’ ’];;- : char list list = []Basic ExceptionsOCaml’s exception mechanism is roughly similar to that found in,for example, Java.We begin by defining an exception:# exception Bad;;Now, encountering raise Bad will immediately terminateevaluation and re turn control to the top level:# let rec fact n =if n<0 then raise Badelse if n=0 then 1else n * fact(n-1);;# fact (-3);;Exception: