CS 421 – Spring 2007Lecture Notes Set 7:Higher Order FunctionsElsa L. Gunter1Transcribed by: Pooja MathurCorresponding to Slides: 04-05-hof (slides 13-)Made available: January 31, 2007Revision 1.01 Change Log1.0 Initial Release.2 Some notes on the previous lecture...2.1 The type ’ a’ a is a outside the scope of this course, but the main idea is there is a clash of two types when it comes to thetype system. So you are writing code and there is a requirement that every value that you create must either gainits polymorphism from a <fun> bound variable or must be a polymorphic constant, like unit. It cannot gain itspolymorpism from the application of a polymorphic function to a polymorphic value. So, if you take a function likemap and you to apply polymorphic function then you have something left over that is polymorphic, for example a list,but now that list’s type is not being determined by some fun x it’s being determined by the application you just used.So we are left with this variable, or like in the example, a list, where we don’t know what it is, but it’s not allowed tobe entirely polymorphic, that is, it can’t take on any possible type, but there still may be some freedom. This is calledmonomorphic type. Then the first time you use it, it gets assigned a type and has to stay that way.For example, you have a function that applies an operation to some values. And the first time around you useintegers, then every time after, you have to use integers. You can’t apply the function on strings or floats because its’ a has been bound to an actual type. If you lambda lifted the function, then you have your complete polymorphicfunction and you won’t have to worry about this.What is key here is that when you see that a function is using something of type ’ a, the first time you apply thatfunction, your function will be bound to that type forever and ever.Here is a more clear example. Let’s say we write a function:# let f x = x;;val f : ’a → ’aSo we wrote the identity function, it will give back what ever we sent in and therefore will have the same type.And now we write another function.# let g = map f;;val g : ’ a list → ’ a listThen we apply g on a list of one element of type integer. So we are applying g to the list [1]. We end up with adifferent type for g now.val g : int list → int listIf you tried to then use g on a list of strings OCaml will get mad because there is a conflict in types. However, ifyou rewrote g to look like:1c 2007, Share and Enjoy1# let g l = map f l;;Then you would get the type:val g : ’a list → ’a listAnd now g is fully polymorphic and there is no binding of the function g to the type int.3 Lambda LiftingWhen evaluating a term, you evaluate until you get to a value. If that value is a closure, you stop there. You don’tevaluate the body of the closure. Doing this give you the ability to control the flow of operations because you canprevent something from occuring for a while by hiding it underneath a ”fun x →...”, also known as a lambda, or anabstraction.3.1 An introductory example (slides 13-14)So, we write a function add two.# let add two = (+) (print string ”test\ n”; 2);;Note that the (+) was described in the last lecture. It is simply an abstract way of referring to the addition operation.testval add two : int → int = <fun>So here, what is happening is you are trying to evaluate the function add two. Along that path is the primativefunction of print string. So you see that test is printed out. Then the rest of the evaluation continues. We see the 2becomes part of a partial application of the + operation, and that becomes a function. It is one that is waiting for aninteger argument to finish the evaluation of 2 + something. So we have an input of an integer that returns an integer.But, what if...what if you wanted the printing of the word ”test” to not happen until you get the second argumentfor the addtion operation. We can do this, we can stop the evaluation of the body of the function by hiding it. To hideit, we add the lambda.# let add2 = (* lambda lifted *)fun x → (+) (print string ”test\ n”; 2) x;;val add2 : int → int = <fun>Now, when we compile, we see that add2 is being bound to a function that takes an argument x and we think thatwe cannot evaluate any of it without that argument x. So even though we know it could be possible to evaluate theprint string, we don’t because it immediately goes to a closure that is waiting for x.Note that for add two, we will never again see the word ”test” print out, because it is not part of the closure ofadd two. The second function, add2, on the other hand, every time you give it an argument for x, you will see ”test”printed out.To see this, look at the following examples.# thrice add two 5;;- : int = 11We apply thrice to add two and supply add two with the value 5, and we get our final value of 11. That’s it, it wasas simple as that.# thrice add2 5;;testtesttest- : int = 11Now noice the difference after applying thrice to add2 and supplying the same value of 5. For every time thefunction add2 is evaluated, we see the word ”test” print to the screen. Then after the iterations and we have our result,we output that result.There is the issue of which one is better...well that depends on what you are doing. If you will have numerousiterations of a function and want to watch as the iterations happen, then lambda lifting is the way to go. If you just2want your final result, most likely, you should choose the original format. So, now you can see that you can controlhow often things are done by how you write your code.4 Lambda Lifting with Unknown Types (slides 15-17)In the previous lecture we discussed the function compose. Here is the function with one of its arguments supplied.# let f1 = compose plus two;;val f1 : (’ a → int) → ’ a → int = <fun>Notice now that the function has gone from polymorphic to a monomorphic one. This means that the next timeyou use f1, you have bound ’ a to a type.# let f2 = fun g → compose plus two g;;val f2 : (’a → int) → ’a → int = <fun>In function f2, we add the lambda lifting and by that we don’t even look at the compose plus two. That way, theargument g can be anything we want it to be, without restrictions.Note that there is a way to keep polymorphism and still have the side effects, like printing the word ”test”, onlyhappen at declaration time. This involves using the
View Full Document
Unlocking...