P505: Programming Languages Lecture 1: Intro; Caml ...

P505: Programming Languages Lecture 1: Intro; Caml ...

CSEP505: Programming Languages Lecture 1: Intro; Caml; Functional Programming Dan Grossman Winter 2009 Welcome! 10 weeks for key programming-language concepts Focus on the universal foundations Today: 1. Staff introduction; course mechanics 2. Why and how to study programming languages 3. Caml and functional-programming tutorial 8 January 2009 CSE P505 Winter 2009 Dan Grossman 2

Hello, my name is Dan Grossman, [email protected] Faculty member researching programming languages Sometimes theory (math) Sometimes implementation (graphs) Sometimes design (important but hand-waving) Particularly, safe low-level languages, easier-to-use concurrency, better type-checkers, other Approximately 0 years professional experience... but Ive done a lot of compiler hacking You can get the rest from Facebook 8 January 2009 CSE P505 Winter 2009 Dan Grossman 3

Course facts (overview) www.cs.washington.edu/education/courses/csep505/09wi/ TAs: Trinh, Laura, Ben Homework 0 Distance learning No textbook 5 homeworks Caml Final exam: Thursday March 19, 6:30-8:20PM Then onto actual course motivation and content

8 January 2009 CSE P505 Winter 2009 Dan Grossman 4 Course web page Read syllabus includes some advice Read advice for approaching homework Homework code is not industry code Functional programming is not imperative/OO programming Course web page will have slides, code, homework, programming resources, etc. Link to page with audio/video archives 8 January 2009

CSE P505 Winter 2009 Dan Grossman 5 TAs Trinh, Laura, and Ben All have taken a more theoretical version of this course from me (and presumably liked it ) And theyll be at most of the lectures Can reach all 4 of us at [email protected] And discussion board from course website Trinh will do a majority of the homework grading, but all will answer homework questions 8 January 2009 CSE P505 Winter 2009 Dan Grossman 6

Homework 0 An optional, brief and extremely useful survey On the web page; just email me Things like what you do and what your concerns are (Also helps me learn your names) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 7 Wide background Homework 0 will almost surely demonstrate a wide range of background So some material will be simultaneously too remedial and too advanced Still let me know (politely)

Challenge problems help some Affect your grade, but only a little Speaking of background, no need for PMP/5th-year mutual fear 8 January 2009 CSE P505 Winter 2009 Dan Grossman 8 Distance learning Ive done this once before The technology will rarely get in the way The two-way A/V is great (either location fine) Im okay with writing on the Tablet PC Please, please come to class!!! Archive/streaming useful when absolutely necessary I cannot teach to a brick wall And low attendance makes me cranky

You cannot learn as well without asking questions and feeling like youre part of a live interaction 8 January 2009 CSE P505 Winter 2009 Dan Grossman 9 Segue to a sermon Im here to teach the essential beauty of the foundations of programming languages If youre here because Its distance so you dont have to attend You can get out of the house on Thursday nights A Masters degree will get you a raise then you risk taking longcuts and being miserable Advice: If you must be <100% engaged, try to wait as long as possible the material builds more than it seems catching up is hard

8 January 2009 CSE P505 Winter 2009 Dan Grossman 10 No textbook There just isnt a book that covers this stuff well And the classic research papers are too old to be readable Pierce book: Very good, with about 30% overlap with the course Turbak/Gifford book: New, looks good but huge and more formal and about 20% overlap with the course Many undergraduate-level books, none of which Ive used OReilly book on OCaml is free (in English) Will post relevant recent papers as interesting optional reading (rarely good for learning material) 8 January 2009

CSE P505 Winter 2009 Dan Grossman 11 Homework 5 assignments Mostly Caml programming (some written answers) Expect to learn as you do them Probably all < 200 lines + thinking Again, challenge problems are optional There are 9 weekends before last lecture Do your own work, but feel free to discuss Do not look at others solutions But learning from each other is great Homework 1 due in two weeks Probably the hardest if youre new to Caml / functional programming 8 January 2009

CSE P505 Winter 2009 Dan Grossman 12 Final exam Please do not panic about taking an exam Worth 2/7 of the course grade (2x 1 homework) Why an exam? Helps you learn material as the course goes on Helps you learn material as you study for it Ill post a sample later 8 January 2009 CSE P505 Winter 2009 Dan Grossman 13 Caml

Caml is an awesome, high-level language Well use a small core subset that is well-suited to manipulating recursive data structures (like programs) Tutorial will demonstrate its mostly functional nature Most data immutable Recursion instead of loops Lots of passing/returning functions Thought about using F# (core subset 95% identical), but wanted one platform that was free, easy-to-install, etc. It really doesnt matter for purpose of the course F# books Ive seen are a bit F#-specific (still useful?) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 14 Welcome! 10 weeks for key programming-language concepts

Focus on the universal foundations Today: 1. Staff introduction; course mechanics 2. Why and how to study programming languages 3. Caml and functional-programming tutorial 8 January 2009 CSE P505 Winter 2009 Dan Grossman 15 A question Whats the best kind of car?

Whats the best kind of shoes? 8 January 2009 CSE P505 Winter 2009 Dan Grossman 16 An answer Of course it depends on what you are doing Programming languages have many goals, including making it easy in your domain to: Write correct code Write fast code Write code fast Write large projects Interoperate

8 January 2009 CSE P505 Winter 2009 Dan Grossman 17 Another question Arent all cars the same? 4 wheels, a steering wheel, a brake the rest is unimportant details Standards help easy to build roads and rent a car But legacy issues dominate why are cars the width they are? 8 January 2009 CSE P505 Winter 2009 Dan Grossman

18 Arent all PLs the same? Almost every language is the same You can write any function from bit-string to bit-string (including non-termination) All it takes is one loop and two infinitely-large integers Called the Turing tarpit Yes: Certain fundamentals appear almost everywhere (variables, abstraction, records, recursive definitions) Travel to learn more about where youre from Caml lets these essentials shine Like the DEC Alpha in computer architecture No: Real differences at formal and informal levels 8 January 2009 CSE P505 Winter 2009 Dan Grossman

19 Picking a language Admittedly, semantics can be far down the priority list: What libraries are available? What do management, clients want? What is the de facto industry standard? What does my team already know? But: Nice thing about class: we get to ignore all that Technology leaders affect the answers Sound reasoning about programs requires semantics Mission-critical code doesnt seem to be right Blame: the compiler vendor or you? 8 January 2009 CSE P505 Winter 2009 Dan Grossman

20 And some stuff is just cool We certainly should connect the theory in this course to realworld programming issues Though maybe more later in the course after the basics But even if we dont, some truths are so beautiful and perspective-altering they are worth learning anyway Watching Hamlet should affect you Maybe very indirectly Maybe much later And maybe you need to re-watch it 8 January 2009 CSE P505 Winter 2009 Dan Grossman 21 Academic languages

Arent academic languages worthless? Yes: not many jobs, less tool support, etc. But see http://cufp.galois.com No: Knowing them makes you a better programmer Java did not exist in 1993; what doesnt exist now Eventual vindication (on the leading edge): garbage-collection, generics, function closures, iterators, universal data format, (whats next?) We dont conquer; we assimilate And get no credit (fine by me) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 22 A recent functional surge F#

Interoperable core with Caml, for .NET C# 3.0 First-class functions, some type inference, etc. Multicore (no mutation means easier to parallelize) MapReduce / Hadoop (first published 2004) Erlang for distributed computing 8 January 2009 CSE P505 Winter 2009 Dan Grossman 23 But I dont do languages Arent languages somebody elses problem? If you design an extensible software system or a non-trivial API, you'll end up designing a (small?) programming language! Examples: VBScript, JavaScript, PHP, ASP, QuakeC, Renderman, bash, AppleScript, emacs, Eclipse, AutoCAD, ...

Another view: A language is an API with few functions but sophisticated data. Conversely, an interface is just a stupid programming language. 8 January 2009 CSE P505 Winter 2009 Dan Grossman 24 Our API type source_prog type object_prog type answer val evaluate : source_prog -> answer val typecheck : source_prog -> bool val translate : source_prog -> object_prog

90+% of the course is defining this interface It is difficult but really elegant (core computer science) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 25 Summary so far We will study the definition of programming languages very precisely, because it matters There is no best language, but lots of similarities among languages Academic languages make this study easier and more forward-looking A good language is not always the right language but we will pretend it is APIs evolve into programming languages

8 January 2009 CSE P505 Winter 2009 Dan Grossman 26 Welcome! 10 weeks for key programming-language concepts Focus on the universal foundations Today: 1. Staff introduction; course mechanics 2. Why and how to study programming languages 3. Caml and functional-programming tutorial 8 January 2009 CSE P505 Winter 2009 Dan Grossman 27

And now Caml Hello, World, compiling, running, note on SEMINAL Demo (not on Powerpoint) Tutorial on the language On slides but code-file available and useful Then use our new language to learn Functional programming Idioms using higher-order functions Benefits of not mutating variables Then use Caml to define other (made-up) languages 8 January 2009 CSE P505 Winter 2009 Dan Grossman 28 Advice

Listen to how I describe the language Let go of what you know: do not try to relate everything back to YFL (Well have plenty of time for that later) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 29 Hello, World! (* our first program *) let x = print_string Hello, World!\n

A program is a sequence of bindings One kind of binding is a variable binding Evaluation evaluates bindings in order To evaluate a variable binding: Evaluate the expression (right of =) in the environment created by the previous bindings This produces a value Extend the (top-level) environment, binding the variable to the value 8 January 2009 CSE P505 Winter 2009 Dan Grossman 30 Some variations let x = print_string Hello, World!\n (*same as previous with nothing bound to ()*)

let _ = print_string Hello, World!\n (*same w/ variables and infix concat function*) let h = Hello, let w = World!\n let _ = print_string (h ^ w) (*function f: ignores its argument & prints*) let f x = print_string (h ^ w) (*so these both print (call is juxtapose)*) let y1 = f 37 let y2 = f f (* pass function itself *) (*but this does not - y1 bound to () *) let y3 = y1 8 January 2009 CSE P505 Winter 2009 Dan Grossman 31 DEMO

8 January 2009 CSE P505 Winter 2009 Dan Grossman 32 Compiling/running ocamlc file.ml compile to bytecodes (put in executable) ocamlopt file.ml compile to native (1-5x faster, no need in class) ocamlc i file.ml

print types of all top-level bindings (an interface) ocaml read-eval-print loop (see manual for directives) ocamlprof, ocamldebug, see the manual (probably unnecessary) Later today(?): multiple files

8 January 2009 CSE P505 Winter 2009 Dan Grossman 33 Installing, learning Links from the web page: www.ocaml.org The on-line manual (fine reference) An on-line book (less of a reference) Local install/use instructions, including SEMINAL Contact us with install problems soon! Ask questions (we know the language, want to share) But 100 rapid-fire questions not the way to learn 8 January 2009 CSE P505 Winter 2009 Dan Grossman

34 Seminal No difference unless your code does not type-check And you compile with seminal or -seminal -no-triage Suggests ways to change such that it type-checks A complementary form of error message Sometimes much better (and sometimes not) A research prototype by Ben Lerner Feedback welcome, especially cool anecdotes 8 January 2009 CSE P505 Winter 2009 Dan Grossman 35

Types Every expression has a type. So far: int string unit t1->t2 a (* print_string : string->unit, : string *) let x = print_string Hello, World!\n (* x: unit *) (* ^ : string->string->string *) let f x = print_string (h ^ w)(* f : a -> unit *) let y1 = f 37 (* y1 : unit *)

let y2 = f f (* y2 : unit *) let y3 = y1 (* y3 : unit *) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 36 Explicit types You (almost) never need to write down types But can help debug or document Can also constrain callers, e.g.: let f x = print_string (h ^ w) let g (x:int) = f x let _ = g 37 let _ = g hi (*no typecheck, but f hi does*)

8 January 2009 CSE P505 Winter 2009 Dan Grossman 37 Theory break Some terminology and pedantry to serve us well: Expressions are evaluated in an environment An environment maps variables to values Expressions are type-checked in a context A context maps variables to types Values are integers, strings, function-closures, things already evaluated Constructs have evaluation rules (except values) and typechecking rules 8 January 2009 CSE P505 Winter 2009 Dan Grossman

38 Recursion A let binding is not in scope for its expression, so: let rec (*smallest infinite loop*) let rec forever x = forever x (*factorial (if x>=0, parens necessary)*) let rec fact x = if x==0 then 1 else x * (fact(x-1)) (*everything an expression, eg, if-then-else*) let fact2 x = (if x==0 then 1 else x * (fact(x-1))) * 2 / 2 8 January 2009 CSE P505 Winter 2009 Dan Grossman

39 Locals Local variables and functions much like top-level ones with in keyword let quadruple x = let double y = y + y in let ans = double x + double x in ans let _ = print_string((string_of_int(quadruple 7)) ^ \n) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 40 Anonymous functions

Functions need not be bound to names In fact we can desugar what we have been doing Anonymous functions cannot be recursive let quadruple2 x = (fun x -> x + x) x + (fun x -> x + x) x let quadruple3 x = let double = fun x -> x + x in double x + double x 8 January 2009 CSE P505 Winter 2009 Dan Grossman 41 Passing functions (* without sharing (shame) *) print_string((string_of_int(quadruple 7)) ^ \n); print_string((string_of_int(quadruple2 7)) ^ \n);

print_string((string_of_int(quadruple3 7)) ^ \n) (* with boring sharing (fine here) *) let print_i_nl i = print_string ((string_of_int i) ^ \n) let _ = print_i_nl (quadruple 7); print_i_nl (quadruple2 7); print_i_nl (quadruple3 7) (* passing functions instead *) (*note 2-args and useful but unused polymorphism*) let print_i_nl2 i f = print_i_nl (f i) let _ = print_i_nl2 7 quadruple ; print_i_nl2 7 quadruple2; print_i_nl2 7 quadruple3 8 January 2009 CSE P505 Winter 2009 Dan Grossman 42

Multiple args, currying let print_i_nl2 i f = print_i_nl (f i) Inferior style (fine, but Caml novice): let print_on_seven f = print_i_nl2 7 f Partial application (elegant and addictive): let print_on_seven = print_i_nl2 7 Makes no difference to callers: let _ = print_on_seven quadruple ; print_on_seven quadruple2; print_on_seven quadruple3 8 January 2009 CSE P505 Winter 2009 Dan Grossman

43 Currying exposed (* 2 ways to write the same thing *) let print_i_nl2 i f = print_i_nl (f i) let print_i_nl2 = fun i -> (fun f -> print_i_nl (f i)) (*print_i_nl2 : (int -> ((int -> int) -> unit)) i.e., (int -> (int -> int) -> unit) *) (* 2 ways to write the same thing *) print_i_nl2 7 quadruple (print_i_nl2 7) quadruple 8 January 2009 CSE P505 Winter 2009 Dan Grossman

44 Elegant generalization Partial application is just an idiom Every function takes exactly one argument Call (application) associates to the left Function types associate to the right Using functions to simulate multiple arguments is called currying (somebodys name) Caml implementation plays cool tricks so full application is efficient (merges n calls into 1) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 45

Closures Static (a.k.a. lexical) scope; a really big idea let y = 5 let return11 = (* unit -> int *) let x = 6 in fun () -> x + y let y = 7 let x = 8 let _ = print_i_nl (return11 ()) (*prints 11!*) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 46 The semantics A function call e1 e2: 1. evaluates e1, e2 to values v1, v2 (order undefined) where v1

is a function with argument x, body e3 2. Evaluates e3 in the environment where v1 was defined, extended to map x to v2 Equivalent description: A function fun x -> e evaluates to a triple of x, e, and the current environment Triple called a closure Call evaluates closures body in closures environment extended to map x to v2 8 January 2009 CSE P505 Winter 2009 Dan Grossman 47 Closures are closed let y = 5 let return11 = (* unit -> int *)

let x = 6 in fun () -> x + y return11 is bound to a value v All you can do with this value is call it (with ()) It will always return 11 Which environment is not determined by caller The environment contents are immutable let return11 () = 11 guaranteed not to change the program 8 January 2009 CSE P505 Winter 2009 Dan Grossman 48 Another example let let

let let let x f x g _ = 9 () = x+1 = x+1 () = x+1 = print_i_nl (f() + g()) 8 January 2009 CSE P505 Winter 2009 Dan Grossman

49 Mutation exists There is a built-in type for mutable locations that can be read and assigned to: let let let let let x f _ g _ = ref 9

() = (!x)+1 = x := (!x)+1 () = (!x)+1 = print_i_nl (f() + g()) While sometimes awkward to avoid, need it much less often than you think (and it leads to sadness) On homework, do not use mutation unless we say 8 January 2009 CSE P505 Winter 2009 Dan Grossman 50 Summary so far Bindings (top-level and local) Functions Recursion Currying

Closures (compelling uses next time) Types base types (unit, int, string, bool, ) Function types Type variables Now: compound data 8 January 2009 CSE P505 Winter 2009 Dan Grossman 51 Record types type int_pair = {first : int; second : int} let sum_int_pr x = x.first + x.second let pr1 = {first = 3; second = 4} let _ = sum_int_pr pr1 + sum_int_pr {first=5;second=6}

A type constructor for polymorphic data/code: type a pair = {a_first : a; a_second : a} let sum_pr f x = f x.a_first + f x.a_second let pr2 = {a_first = 3; a_second = 4}(*int pair*) let _ = sum_int_pr pr1 + sum_pr (fun x->x) {a_first=5;a_second=6} 8 January 2009 CSE P505 Winter 2009 Dan Grossman 52 More polymorphic code type a pair = {a_first : a; a_second : a} let sum_pr f x = f x.a_first + f x.a_second let pr2 = {a_first = 3; a_second = 4} let pr3 = {a_first = hi; a_second = mom} let pr4 = {a_first = pr2; a_second = pr2}

let sum_int = sum_pr (fun x -> x) let sum_str = sum_pr String.length let sum_int_pair = sum_pr sum_int let _ = print_i_nl (sum_int pr2) let _ = print_i_nl (sum_str pr3) let _ = print_i_nl (sum_int_pair pr4) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 53 Each-of vs. one-of Records build new types via each of existing types Also need new types via one of existing types Subclasses in OOP

Enums or unions (with tags) in C Caml does this directly; the tags are constructors Type is called a datatype 8 January 2009 CSE P505 Winter 2009 Dan Grossman 54 Datatypes type food = Foo of int | Bar of int_pair | Baz of int * int | Quux let let let let foo3

bar12 baz1_120 quux = = = = let is_a_foo x match x with Foo i -> | Bar pr -> | Baz(i,j) -> | Quux ->

8 January 2009 Foo (1 + 2) Bar pr1 Baz(1,fact 5) Quux (* not much point in this *) = (* better than downcasts *) true false false false CSE P505 Winter 2009 Dan Grossman 55 Datatypes Syntax note: Constructors capitalized, variables not

Use constructor to make a value of the type Use pattern-matching to use a value of the type Only way to do it Pattern-matching actually much more powerful 8 January 2009 CSE P505 Winter 2009 Dan Grossman 56 Booleans revealed Predefined datatype (violating capitalization rules ): type bool = true | false if is just sugar for match (but better style): if e1 then e2 else e3 match e1 with true -> e2

| false -> e3 8 January 2009 CSE P505 Winter 2009 Dan Grossman 57 Recursive types A datatype can be recursive, allowing data structures of unbounded size And it can be polymorphic, just like records type int_tree = Leaf | Node of int * int_tree * int_tree type a lst = Null | Cons of a * a lst let lst1 = Cons(3,Null) let lst2 = Cons(1,Cons(2,lst1)) (* let lst_bad = Cons("hi",lst2) *)

let lst3 = Cons("hi",Cons("mom",Null)) let lst4 = Cons (Cons (3,Null), Cons (Cons (4,Null), Null)) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 58 Recursive functions type a lst = Null | Cons of a * a lst let rec len lst = (* a lst -> int *) match lst with Null -> 0 | Cons(x,rest) -> 1 + len rest 8 January 2009

CSE P505 Winter 2009 Dan Grossman 59 Recursive functions type a lst = Null | Cons of a * a lst let rec sum lst = (* int lst -> int *) match lst with Null -> 0 | Cons(x,rest) -> x + sum rest 8 January 2009 CSE P505 Winter 2009 Dan Grossman 60 Recursive functions

type a lst = Null | Cons of a * a lst let rec append lst1 lst2 = (* a lst -> a lst -> a lst *) match lst1 with Null -> lst2 | Cons(x,rest) -> Cons(x, append rest lst2) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 61 Another built-in Actually the type a list is built-in: Null is written [] Cons(x,y) is written x::y Sugar for list literals [5; 6; 7]

let rec append lst1 lst2 = (* built-in infix @ *) match lst1 with [] -> lst2 | x::rest -> x :: (append rest lst2) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 62 Summary Now we really have it all Recursive higher-order functions Records Recursive datatypes Some important odds and ends Standard-library Common higher-order function idioms

Tuples Nested patterns Exceptions Then (simple) modules 8 January 2009 CSE P505 Winter 2009 Dan Grossman 63 Standard library Values (e.g., functions) bound to foo in module M are accessed via M.foo Standard library organized into modules For homework 1, will use List, String, and Char Mostly List, for example, List.fold_left And we point you to the useful functions Standard library a mix of primitives (e.g., String.length)

and useful helpers written in Caml (e.g., List.fold_left) Pervasives is a module implicitly opened 8 January 2009 CSE P505 Winter 2009 Dan Grossman 64 Higher-order functions Will discuss map and fold idioms more next time, but to help get through early parts of homework 1: let rec mymap f lst = match lst with [] -> [] | hd::tl -> (f hd)::(mymap f tl) let lst234 = mymap (fun x -> x+1) [1;2;3] let lst345 = List.map (fun x -> x+1) [1;2;3] let incr_list = mymap (fun x -> x+1)

8 January 2009 CSE P505 Winter 2009 Dan Grossman 65 Tuples Defining record types all the time is unnecessary: Types: t1 * t2 * * tn Construct tuples e1,e2,,en Get elements with pattern-matching x1,x2,,xn Advice: use parentheses! let x = (3,"hi",(fun x -> x), fun x -> x ^ "ism") let z = match x with (i,s,f1,f2) -> f1 i (*poor style *) let z = (let (i,s,f1,f2) = x in f1 i) 8 January 2009

CSE P505 Winter 2009 Dan Grossman 66 Pattern-matching revealed You can pattern-match anything Only way to access datatypes and tuples A variable or _ matches anything Patterns can nest Patterns can include constants (3, hi, ) Patterns are not expressions, though syntactically a subset Plus some bells/whistles (as-patterns, or-patterns) Exhaustiveness and redundancy checking at compile-time! let can have patterns, just sugar for one-branch match! 8 January 2009 CSE P505 Winter 2009 Dan Grossman

67 Fancy patterns example type sign = P | N | Z let multsign x1 x2 = let sign x = if x>0 then (if x=0 then Z else P) else N in match (sign x1,sign x2) with (P,P) -> P | (N,N) -> N | (Z,_) -> Z | (_,Z) -> Z | _ -> N (* many say bad style! *) To avoid overlap, two more cases (more robust if type changes) 8 January 2009

CSE P505 Winter 2009 Dan Grossman 68 Fancy patterns example (and exns) exception ZipLengthMismatch let rec zip3 lst1 lst2 lst3 = match (lst1,lst2,lst3) with ([],[],[]) -> [] | (hd1::tl1,hd2::tl2,hd3::tl3) -> (hd1,hd2,hd3)::(zip3 tl1 tl2 tl3) | _ -> raise ZipLengthMismatch a list -> b list -> c list -> (a*b*c) list 8 January 2009 CSE P505 Winter 2009 Dan Grossman

69 Pattern-matching in general Full definition of matching is recursive Over a value and a pattern Produce a binding list or fail You implement a simple version in homework 1 Example: (p1,p2,p3) matches (v1,v2,v3) if pi matches vi for 1<=i<=3 Binding list is 3 subresults appended together 8 January 2009 CSE P505 Winter 2009 Dan Grossman 70 Quiz

What is let f x y = x + y let f pr = (match pr with (x,y) -> x+y) let f (x,y) = x + y let f (x1,y1) (x2,y2) = x1 + y2 8 January 2009 CSE P505 Winter 2009 Dan Grossman 71 Exceptions See the manual for: Exceptions that carry values Much like datatypes but extends exn Catching exceptions try e1 with Much like pattern-matching but cannot be exhaustive

Exceptions are not hierarchical (unlike Java/C# subtyping) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 72 Modules So far, only way to hide things is local let Not good for large programs Caml has a fancy module system, but we need only the basics Modules and signatures give Namespace management Hiding of values and types Abstraction of types Separate type-checking and compilation By default, Caml builds on the filesystem

8 January 2009 CSE P505 Winter 2009 Dan Grossman 73 Module pragmatics foo.ml defines module Foo Bar uses variable x, type t, constructor C in Foo via Foo.x, Foo.t, Foo.C Can open a module, use sparingly foo.mli defines signature for module Foo Or everything public if no foo.mli Order matters (command-line) No forward references (long story) Program-evaluation order See manual for .cm[i,o] files, -c flag, etc. 8 January 2009

CSE P505 Winter 2009 Dan Grossman 74 Module example foo.ml: foo.mli: type t1 = X1 of int | X2 of int (* choose to show *) type t1 = X1 of int | X2 of int let get_int t = match t with X1 i -> i

| X2 i -> i val get_int : t1->int (* choose to hide *) type even type even = int let makeEven i = i*2 let isEven1 i = true (* isEven2 is private *) let isEven2 i = (i mod 2)=0 8 January 2009 val makeEven : int->even val isEven1 : even->bool CSE P505 Winter 2009 Dan Grossman 75

Module example bar.ml: foo.mli: type t1 = X1 of int | X2 of int let conv1 t = match t with X1 i -> Foo.X1 | X2 i -> Foo.X2 let conv2 t = match t with Foo.X1 i -> X1 | Foo.X2 i -> X2 (* choose to show *) type t1 = X1 of int

| X2 of int i i i i val get_int : t1->int (* choose to hide *) type even val makeEven : int->even val isEven1 : even->bool let _ = Foo.get_int(conv1(X1 17)); Foo.isEven1(Foo.makeEven 17) (* Foo.isEven1 34 *) 8 January 2009

CSE P505 Winter 2009 Dan Grossman 76 Not the whole language Objects Loop forms (bleach) Fancy module stuff (e.g., functors) Polymorphic variants Mutable fields

Just dont need much of this for class (nor do I use it much) Will use floating-point, etc. (easy to pick up) 8 January 2009 CSE P505 Winter 2009 Dan Grossman 77 Summary Done with Caml tutorial Focus on up to speed while being precise Much of class will be more precise Next: functional-programming idioms Uses of higher-order functions (cf. objects) Tail recursion Life without mutation or loops Will use Caml but ideas are more general

8 January 2009 CSE P505 Winter 2009 Dan Grossman 78

Recently Viewed Presentations

  • Long-Term Correlates of Family Foster Care

    Long-Term Correlates of Family Foster Care

    Change that occurs when a client's measured functioning on a standardized scale is: In the dysfunctional range before intervention (e.g., greater than 5 on the QIDS-SR) In the functional range after intervention (e.g., 5 or below on the QIDS-SR) Change...
  • SASD PreschoolLevels of Excellence

    SASD PreschoolLevels of Excellence

    Parent Knowledge of Quality Early Childhood Education ... South Dakota Early Childhood Care & Education Network. ... Program staff connect with and use their community's urban, surburban, rural or tribal cultural resources.
  • FARL-LARC Field Day 2016

    FARL-LARC Field Day 2016

    A review from last year:2016 vs 2015 Contacts. 2016 Contacts. 17 more contacts (<1%) in 2016 than 2015, in spite of less operating time in 2015 due to the storms.
  • Annotation-based analysis of protein sets

    Annotation-based analysis of protein sets

    A brief on: Domain Families & Classification
  • Causes of WWI - MANIA!

    Causes of WWI - MANIA!

    Causes of WWI - MANIA! Militarism - policy of building up a strong military to prepare for war Alliances - agreements between nations to provide aid and protect one another Assassination - of Austrian Archduke Francis Ferdinand Imperialism - when...
  • Race Homophones - Yola

    Race Homophones - Yola

    with Mrs Ford Ford Complete a Qualifying Lap and Two Races to Win the Cup 1. Qualifying Lap 2. A1 Motor Speedway 3. Burnham School 500 Qualifying Lap Choose the right tool box.
  • Folds, Faults and Other Records of Rock Deformation

    Folds, Faults and Other Records of Rock Deformation

    The minerals recrystallize, and grow into new shapes. Joints are also fractures, but which do not show clear movement of blocks across them. ( Remember: Faults are also fractures but WITH movement across the fractures)
  • Generating Educator Effectiveness: A Blueprint For Creating ...

    Generating Educator Effectiveness: A Blueprint For Creating ...

    Objectives for the Day. Examine each step of the process through guided practice. Reflect on current practices in your building/s. Determine strengths & areas of need in your current data team process