Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/sp07/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterQuestion• Observation: Functions are first-classvalues in this language• Question: What value does theenvironment record for a functionvariable?• Answer: a closureElsa L. GunterSave the Environment!• A closure is a pair of an environmentand an association of a sequence ofvariables (the input variables) with anexpression (the function body), written:f → < (v1,…,vn) → exp, ρf >• Where ρf is the environment in effectwhen f is defined (if f is a simplefunction)Elsa L. GunterClosure for plus_x• When plus_x was defined, hadenvironmentρplus_x = {x → 12, …, y → 24, …}• Closure for plus_x: < y → y + x, ρplus_x >Elsa L. GunterEvaluation of Application• First evaluate the left term to a function (iestarts with fun )• Evaluate the right term (argument) to avalue– Things starting with fun are values• Substitute the argument for the formalparameter in the body of the function• Evaluate resulting term• (Need to use environments)Elsa L. GunterEvaluation of application ofplus_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. GunterScoping 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. GunterRecursive 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 recursivefunction declarations *) (* More on this later *)Elsa L. GunterTuples 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. GunterTuples# 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. GunterTuples# 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. GunterCurried vs UncurriedRecallval 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. GunterCurried 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. GunterMatch 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 onleft, expression on right•Each x, y has scope ofonly its clause•Use first matching clauseElsa L. GunterLists• First example of a recursivedatatype (aka algebraic datatype)• Unlike tuples, lists are homogenousin type (all elements same type)Elsa L. GunterLists• 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. GunterLists# 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;;- : bool = true# fib5 @ fib6;;- : int list = [8; 5; 3; 2; 1; 1; 13; 8; 5; 3; 2; 1; 1]Elsa L. GunterLists are Homogenous# let bad_list = [1; 3.2; 7];;Characters 19-22: let bad_list = [1; 3.2; 7];; ^^^This expression has type float but is hereused with type intElsa L. GunterQuestionWhich one of these lists is invalid?1. [2; 3; 4; 6]2. [2,3; 4,5; 6,7]3. [(2.3,4); (3.2,5); (6,7.2)]4. [[“hi”; “there”]; [“wahcha”]; [ ]; [“doin”]]Elsa L. GunterAnswerWhich one of these lists is invalid?1. [2; 3; 4; 6]2. [2,3; 4,5; 6,7]3. [(2.3,4); (3.2,5); (6,7.2)]4. [[“hi”; “there”]; [“wahcha”]; [ ]; [“doin”]]3 is invalid because of last pairElsa L. GunterFunctions Over Lists# let rec double_up list = match list with [ ] -> [ ] (* pattern before ->,expression after *) | (x :: xs) -> (x :: x :: double_up xs);;val double_up : 'a list -> 'a list = <fun># let fib5_2 = double_up fib5;;val fib5_2 : int list = [8; 8; 5; 5; 3; 3; 2; 2;1; 1; 1; 1]Elsa L. GunterFunctions Over Lists# let silly = double_up ["hi"; "there"];;val silly : string list = ["hi"; "hi"; "there"; "there"]# let rec poor_rev list = match list with [] -> [] | (x::xs) -> poor_rev xs @ [x];;val poor_rev : 'a list -> 'a list = <fun># poor_rev silly;;- : string list = ["there"; "there"; "hi"; "hi"]Elsa L. GunterFunctions Over Lists# let rec map f list = match list with [] -> [] | (h::t) -> (f h) :: (map f t);;val map : ('a -> 'b) -> 'a list -> 'b list = <fun># map plus_two fib5;;- : int list = [10; 7; 5; 4; 3; 3]# map (fun x -> x - 1) fib6;;- : int list = [12; 7; 4; 2; 1; 0; 0]Elsa L. GunterIterating over lists# let rec fold_left f a list = match list with [] -> a | (x :: xs) -> fold_left f (f a x) xs;;val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun># fold_left (fun () -> print_string) () ["hi"; "there"];;hithere- : unit = ()Elsa L. GunterIterating over lists# let rec fold_right f list b = match list with [] -> b | (x :: xs) -> f x (fold_right f xs b);;val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun># fold_right (fun s -> fun () -> print_string s) ["hi"; "there"] ();;therehi- : unit = ()Elsa L. GunterRecursion Example• Compute n2 recursively using:n2 = (2 * n - 1) + (n - 1)2# let rec nthsq n = (* rec for recursion *) match n (* pattern matching for cases *) with 0 -> 0
View Full Document
Unlocking...