Programming Languages and Compilers (CS 421)FunctionsUsing a nameless functionValues fixed at declaration timeSlide 22Slide 23Slide 24Functions with more than one argumentPartial application of functions let add_three x y z = x + y + z;;Functions as argumentsQuestionSave the Environment!Closure for plus_xEvaluation of ApplicationEvaluation of application of plus_x;;Scoping QuestionRecursive FunctionsTuples and PatternsTuplesSlide 64Curried vs UncurriedSlide 66Match ExpressionsListsSlide 69Slide 70Lists are HomogenousSlide 72AnswerFunctions Over ListsSlide 75Slide 76Iterating over listsSlide 78Programming Languages and Compilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul AghaElsa L. Gunter Functions# 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. Gunter Using a nameless function# (fun x -> x * 3) 5;; (* An application *)- : int = 15# ((fun y -> y +. 2.0), (fun z -> z * 3));; (* As data *)- : (float -> float) * (int -> int) = (<fun>, <fun>)Note: in fun v -> exp(v), scope of variable is only the body exp(v)Elsa L. Gunter Values fixed at declaration time# 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. Gunter Values fixed at declaration time# 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. Gunter Values fixed at declaration time# let x = 7;; (* New declaration, not an update *)val x : int = 7# plus_x 3;;What is the result this time?Elsa L. Gunter Values fixed at declaration time# let x = 7;; (* New declaration, not an update *)val x : int = 7# plus_x 3;;- : int = 15Elsa L. Gunter Functions with more than one argument# 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. Gunter Partial application of functions let 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. Gunter Functions as arguments# let thrice f x = f (f (f x));;val thrice : ('a -> 'a) -> 'a -> 'a = <fun># let g = thrice plus_two;;val g : int -> int = <fun># g 4;;- : int = 10# thrice (fun s -> "Hi! " ^ s) "Good-bye!";;- : string = "Hi! Hi! Hi! Good-bye!"Elsa L. Gunter Question•Observation: Functions are first-class values in this language•Question: What value does the environment record for a function variable?•Answer: a closureElsa L. Gunter Save the Environment!•A closure is a pair of an environment and an association of a sequence of variables (the input variables) with an expression (the function body), written:f < (v1,…,vn) exp, f >•Where f is the environment in effect when f is defined (if f is a simple function)Elsa L. Gunter Closure for plus_x•When plus_x was defined, had environmentplus_x = {x 12, …, y 24, …}•Closure for plus_x: < y y + x, plus_x >Elsa L. Gunter Evaluation of Application•First evaluate the left term to a function (ie starts with fun )•Evaluate the right term (argument) to a value–Things starting with f un are values•Substitute the argument for the formal parameter in the body of the function•Evaluate resulting term•(Need to use environments)Elsa L. Gunter Evaluation of application of plus_x;;Have environment ={plus_x < y y + x, plus_x > , …, y 3, …}where plus_x = {x 12, …, y 24, …}Eval (plus_x y) in rewrites toEval (app < y y + x, plus_x > 3) rewrites toEval (y + x) in (y 3) + plus_x rewrites toEval (3 + 12) = 15Elsa L. Gunter Scoping QuestionConsider this code: let x = 27;;let f x = let x = 5 in (fun x -> print_int x) 10;;f 12;;What value is printed?a) 5b) 10c) 12d) 27Elsa L. Gunter Recursive Functions# let rec factorial n = if n = 0 then 1 else n * factorial (n - 1);; val factorial : int -> int = <fun># factorial 5;;- : int = 120# (* rec is needed for recursive function declarations *) (* More on this later *)Elsa L. Gunter Tuples and Patterns# let s = (5,"hi",3.2);;val s : int * string * float = (5, "hi", 3.2)# let (a,b,c) = s;;val a : int = 5val b : string = "hi"val c : float = 3.2# let x = 2, 9.3;; (* tuples don't require parens*)val x : int * float = (2, 9.3)Elsa L. Gunter Tuples# let d = ((1,4,62),("bye",15),73.95);;val d : (int * int * int) * (string * int) * float = ((1, 4, 62), ("bye", 15), 73.95)# let (p,(st,_),_) = d;;val p : int * int * int = (1, 4, 62)val st : string = "bye"Elsa L. Gunter Tuples# let fst_of_3 (x,_,_) = x;;val fst_of_3 : 'a * 'b * 'c -> 'a = <fun># s;;- : int * string * float = (5, "hi", 3.2)# fst_of_3 s;;- : int = 5# fst_of_3 d;;-: int * int * int = (1, 4, 62)Notice the type of fst_of_3Elsa L. Gunter Curried vs UncurriedRecall val add_three : int -> int -> int -> int = <fun>How does it differ from# let add_triple (u,v,w) = u + v + w;;val add_triple : int * int * int -> int = <fun>add_three is curried;add_triple is uncurriedElsa L. Gunter Curried vs Uncurried# add_triple (6,3,2);;- : int = 11# add_triple 5 4;;Characters 0-10: add_triple 5 4;; ^^^^^^^^^^This function is applied to too many arguments,maybe you forgot a `;'# fun x -> add_triple (5,4,x);;-: int -> int = <fun>Elsa L. Gunter Match Expressions# let triple_to_pair triple = match triple with (0, x, y) -> (x, y) | (x, 0, y) -> (x, y) | (x, y, 0) -> (x, y) | (x, y, _) -> (x, y);;val triple_to_pair : int * int * int -> int * int = <fun>•Each clause: pattern on left, expression on right•Each x, y has scope of only its clause•Use first matching clauseElsa L. Gunter Lists•First example of a recursive datatype (aka algebraic datatype)•Unlike tuples, lists are homogenous in type (all elements same type)Elsa L. Gunter Lists•List can take one of two forms:–Empty list, written [ ]–Non-empty list, written x :: xs•x is head element, xs is tail list, :: called “cons”–Syntactic sugar: [x] == x :: [ ][ x1; x2; …; xn] == x1 :: x2 :: … :: xn :: [ ]Elsa L. Gunter Lists# let fib5 = [8;5;3;2;1;1];;val fib5 : int list = [8; 5; 3; 2; 1; 1]# let fib6 = 13 :: fib5;;val fib6 : int list = [13; 8; 5; 3; 2; 1; 1]# (8::5::3::2::1::1::[ ]) = fib5;;- …
View Full Document
Unlocking...