Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterOCAML• Compiler is on the EWS-linux systems at/usr/local/bin/ocaml• A (possibly better, non-PowerPoint) textversion of this lecture can be found athttp://www.cs.uiuc.edu/class/fa06/cs421/lectures/ocaml-intro-shell.txt• For the OCAML code for today’s lecture seehttp://www.cs.uiuc.edu/class/fa06/cs421/lectures/ocaml-intro.mlElsa L. GunterWWW Addresses for OCAML• Main CAML home:http://caml.inria.fr/index.en.html• To install OCAML on your computer see:http://caml.inria.fr/ocaml/release.en.htmlElsa L. GunterReferences for CAMLSupplemental texts (not required):• The Objective Caml system release 3.08,by Xavier Leroy, online manual• Developing Applications With ObjectiveCaml, by Emmanuel Chailloux, PascalManoury, and Bruno Pagano, on O’Reilly– Available online from course resourcesElsa L. GunterOCAML• CAML is European descendant of original ML– American/British version is SML– O is for object-oriented extension• ML stands for Meta-Language• ML family designed for implementing theoremprovers– It was the meta-language for programmingthe “object” language of the theorem prover– Despite obscure original application area,OCAML is a full general-purposeprogramming languageElsa L. GunterFeatures of OCAML• Higher order applicative language• Call-by-value parameter passing• Modern syntax• Parametric polymorphism– Aka structural polymorphism• Automatic garbage collection• User-defined algebraic data types• It’s fast - winners of the 1999 and 2000 ICFPProgramming Contests used OCAMLElsa L. GunterWhy learn OCAML?• Many features not clearly in languagesyou have already learned• Assumed basis for much research inprogramming language research• OCAML is particularly efficient forprogramming tasks involving languages(eg parsing, compilers, user interfaces)• Used at Microsoft for writing SLAM, aformal methods tool for C programsElsa L. GunterSession in OCAML% ocamlObjective Caml version 3.08.3# (* Read-eval-print loop; expressions anddeclarations *)# 2 + 3;; (* Expression *)- : int = 5# let test = 3 < 2;; (* Declaration *)val test : bool = falseElsa L. GunterEnvironments• Environments record what value isassociated with a given variable• Central to the semantics and implementationof a language• Notation: ρ = {name1→value1, name2→value2, …}Using set notation, but describes a partialfunction• Often stored as list, or stack• To find value start from left and take firstmatchElsa L. GunterSequencing# "Hi there";; (* has type string *)- : string = "Hi there"# print_string "Hello world\n";; (* has type unit *)Hello world- : unit = ()# (print_string "Bye\n"; 25);; (* Sequence of exp *)Bye- : int = 25# let a = 3 let b = a + 2;; (* Sequence of dec *)val a : int = 3val b : int = 5Elsa L. GunterGlobal Variable Creation# 2 + 3;; (* Expression *)// doesn’t effect the environment# let test = 3 < 2;; (* Declaration *)val test : bool = false// ρ = {test → false}# let a = 3 let b = a + 2;; (* Sequence ofdec *)// ρ = {b → 5, a → 3, test → false}Elsa L. GunterLocal let binding# let c = let b = a + a in b * b;; val c : int = 36# b;;- : int = 5Elsa L. GunterLocal Variable Creation# let c = let b = a + a// ρ1 = {b → 6, a → 3, test → false} in b * b;; val c : int = 36// ρ = {c → 36, b → 5, a → 3, test → false}# b;;- : int = 5Elsa L. GunterTerminology• Output refers both to the result returnedfrom a function application– As in + outputs integers, whereas +.outputs floats• Also refers to text printed as a side-effect of a computation– As in print_string “\n” outputs a carriagereturn– In terms of values, it outputs “unit”• We will standardly use “output” to referto the value returnedElsa L. GunterNo Overloading for BasicArithmetic Operations# let x = 5 + 7;;val x : int = 12# let y = x * 2;;val y : int = 24# let z = 1.35 + 0.23;; (* Wrong type of addition *)Characters 8-12: let z = 1.35 + 0.23;; (* Wrong type of addition *) ^^^^This expression has type float but is here used withtype int# let z = 1.35 +. 0.23;;val z : float = 1.58Elsa L. GunterNo Implicit Coercion# let u = 1.0 + 2;;Characters 8-11: let u = 1.0 + 2;; ^^^This expression has type float but is here usedwith type int# let w = y + z;;Characters 12-13: let w = y + z;; ^This expression has type float but is here usedwith type intElsa L. GunterBooleans (aka Truth Values)# true;;- : bool = true# false;;- : bool = false# if y > x then 25 else 0;;- : int = 25Elsa L. GunterBooleans# 3 > 1 & 4 > 6;;- : bool = false# 3 > 1 or 4 > 6;;- : bool = true# (print_string "Hi\n"; 3 > 1) or 4 > 6;;Hi- : bool = true# 3 > 1 or (print_string "Bye\n"; 4 > 6);;- : bool = true# not (4 > 6);;- : bool = trueElsa L. GunterFunctions# let plus_two n = n + 2;;val plus_two : int -> int = <fun># plus_two 17;;- : int = 19# let plus_two = fun n -> n + 2;;val plus_two : int -> int = <fun># plus_two 14;;- : int = 16First definition syntactic sugar for secondElsa L. GunterUsing a nameless function# (fun x -> x * 3) 5;; (* An application *)- : int = 15# ((fun y -> y +. 2.0), (fun z -> z * 3));; (* Asdata *)- : (float -> float) * (int -> int) = (<fun>, <fun>)Note: in fun v -> exp(v), scope of variable isonly the body exp(v)Elsa L. GunterValues fixed at declarationtime# let x = 12;;val x : int = 12# let plus_x y = y + x;;val plus_x : int -> int = <fun># plus_x 3;;What is the result?Elsa L. GunterValues fixed at declarationtime# let x = 12;;val x : int = 12# let plus_x y = y + x;;val plus_x : int -> int = <fun># plus_x 3;;- : int = 15Elsa L. GunterValues fixed at declarationtime# let x = 7;; (* New declaration, not anupdate *)val x : int = 7# plus_x 3;;What is the result this time?Elsa L. GunterValues fixed at declarationtime# let x = 7;; (* New declaration, not anupdate *)val x : int = 7# plus_x 3;;- : int = 15Elsa L. GunterFunctions with more than oneargument# let add_three x y z = x + y + z;;val add_three : int -> int -> int -> int =<fun># let t = add_three 6 3 2;;val t : int = 11Elsa L. GunterPartial application of functionslet add_three x y z = x + y + z;;# let h = add_three 5 4;;val h : int -> int = <fun># h 3;;- : int = 12# h 7;;- : int = 16Elsa L. GunterFunctions as arguments# let thrice f x = f
View Full Document