1CMSC 330: Organization of Programming LanguagesFunctional Programming with OCamlCMSC 330 2Reminders• Homework 2 will be posted soon2CMSC 330 3Review• Recursion is how all looping is done• OCaml can easily pass and return functionsCMSC 330 4The Call Stack in C/Java/etc.void f(void) {int x;x = g(3);}x<junk>int g(int x) {int y;y = h(x);return y;}int h (int z) {return z + 1;}x3y<junk>z344int main(){f();return 0;}fgh3CMSC 330 5Nested Functions• In OCaml, you can define functions anywhere– Even inside of other functionslet pick_one n =if n > 0 then (fun x -> x + 1)else (fun x -> x - 1)(pick_one -5) 6 (* returns 5 *)let sum l =fold ((fun (a, x) -> a + x), 0, l)CMSC 330 6Nested Functions (cont’d)• You can also use let to define functions inside of other functionslet sum l =let add (a, x) = a + x infold (add, 0, l)let pick_one n =let add_one x = x + 1 inlet sub_one x = x - 1 inif n > 0 then add_one else sub_one4CMSC 330 7How About This?– (Equivalent to...)let addN (n, l) =letaddx=n+xinmap (add, l)Accessing variablefrom outer scopelet addN (n, l) =map ((fun x -> n + x), l)takes a number n and list l and adds n to every element in lCMSC 330 8Consider the Call Stack Again• Uh oh...how does add know the value of n?–The wrong answer for OCaml: it reads it off the stack• The language could do this, but can be confusing (see above)– OCaml uses static scoping like C, C++, Java, and Rubylet addN (n, l) =map (add, l)let map (f, n) = match n with[] -> []| (h::t) -> (f h)::(map (f, t))addN (3, [1; 2; 3])let add x = n + x inn3l <list>f <add>nx15CMSC 330 9Static Scoping•In static or lexical scoping, (nonlocal) names refer to their nearest binding in the program text– Going from inner to outer scope– C example:– In our example, add accesses addN’s nint x;void f() { x = 3; }void g() { char *x = "hello"; f(); }Refers to the x at file scope – that’s the nearest x going from inner scope to outer scope in the source codeCMSC 330 10Returned Functions• As we saw, in OCaml a function can return another function as a result– So consider the following example– When the anonymous function is called, n isn’t even on the stack any more!• We need some way to keep n around after addN returnslet addN n = (fun x -> x + n)(addN 3) 4 (* returns 7 *)6CMSC 330 11Environments and Closures•An environment is a mapping from variable names to values– Just like a stack frame•A closure is a pair (f, e) consisting of function code f and an environment e• When you invoke a closure, f is evaluated using e to look up variable bindingsCMSC 330 12Examplelet add x = (fun y -> x + y)(add 3) 4 <closure> 4 3+4 77CMSC 330 13Another Examplelet mult_sum (x, y) =letz=x+yinfunw->w*z(mult_sum (3, 4)) 5 <closure> 5 5*7 35CMSC 330 14Yet Another Examplelet twice (n, y) =letfx=x+ninf(fy)twice (3, 4) <closure> (<closure> 4) <closure> 7 108CMSC 330 15Still Another Examplelet add x = (fun y -> (fun z -> x + y + z))(((add 1) 2) 3) ((<closure> 2) 3) (<closure> 3) 1+2+3CMSC 330 16Currying• We just saw another way for a function to take multiple arguments– The function consumes one argument at a time, creating closures until all the arguments are available• This is called currying the function– Named after the logician Haskell B. Curry– But Schönfinkel and Frege discovered it• So it should probably be called Schönfinkelizing or Fregging9CMSC 330 17Curried Functions in OCaml• OCaml has a really simple syntax for currying– This is identical to all of the following:• Thus:– add has type int -> (int -> int)– add 3has type int -> int• The return of add x evaluated with x = 3• add 3is a function that adds 3 to its argument– (add 3)4=7• This works for any number of argumentslet add x y = x + ylet add = (fun x -> (fun y -> x + y))letadd=(funxy->x+y)let add x = (fun y -> x+y)CMSC 330 18Curried Functions in OCaml (cont’d)• Because currying is so common, OCaml uses the following conventions:– -> associates to the right• Thus int -> int -> int is the same as• int -> (int -> int)– function application associates to the left• Thus add 3 4 is the same as• (add 3) 410CMSC 330 19Another Example of Currying• A curried add function with three arguments:–The same as• Then...– add_th has type int -> (int -> (int -> int))– add_th 4has type int -> (int -> int)– add_th 4 5has type int -> int– add_th456is 15let add_th x y z = x + y + zlet add_th x = (fun y -> (fun z -> x+y+z))CMSC 330 20Currying and the map Function•Exampleslet negatex=-xmap negate [1; 2; 3] (* returns [-1; -2; -3 ] *)let negate_list = map negatenegate_list [-1; -2; -3]let sum_pairs_list = map (fun (a, b) ->a+b)sum_pairs_list [(1, 2); (3, 4)] (* [3; 7] *)• What's the type of this form of map?let rec map f l = match l with[] -> []| (h::t) -> (f h)::(map f t)map : ('a -> 'b) -> 'a list -> 'b list11CMSC 330 21Currying and the fold Functionlet rec fold f a l = match l with[] -> a| (h::t) -> fold f (f a h) tletaddxy=x+yfold add 0 [1; 2; 3]let sum = fold add 0sum [1; 2; 3]letnextn_=n+1let length = fold next 0 (* warning: not polymorphic *)length [4; 5; 6; 7]• What's the type of this form of fold?fold : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'aCMSC 330 22Another Convention• Since functions are curried, function can often be used instead of match– function declares an anonymous function of one argument– Instead of– It could be writtenlet rec sum l = match l with[] -> 0| (h::t) -> h + (sum t)let rec sum = function[] -> 0| (h::t) -> h + (sum t)12CMSC 330 23Another Convention (cont’d)Instead ofIt could be writtenlet rec map f l = match l with[] -> []| (h::t) -> (f h)::(map f t)let rec map f = function[] -> []| (h::t) -> (f h)::(map f t)CMSC 330 24Currying is Standard in OCaml• Pretty much all functions are curried– Like the standard library map, fold, etc.• OCaml plays a lot of tricks to avoid creating closures and to avoid allocating on the heap– It's unnecessary much of the time, since functions are usually called with all arguments13CMSC 330 25Higher-Order Functions in C• C has function pointers but no closures– (gcc has closures)typedef int (*int_func)(int);void app(int_func f, int *a, int n) {int i;for(i=0;i<n;i++)a[i] = f(a[i]);}int add_one(int x) { return x + 1; }int main() {int a[] = {1, 2, 3, 4};app(add_one, a,
View Full Document
Unlocking...