INF 212 ANALYSIS OF PROG. LANGS FUNKTIONAL PROGRAMMING Instructors: Crista Lopes Copyright Instructors. Outline Closures Continuations Iterators, generators

Lazy evaluation Monads Closures Function with free variables that are bound to values in the enclosing environment (lambda (x) (lambda (y) x+y)) closure Note to self: illustrate closures in Python and C# (my examples) What are closures good for?

For changing your mind later! Replaces constants and variables with functions Replaces conditionals ... Declares imperatives! Outline

Closures Continuations Iterators, generators Lazy evaluation Monads Continuations Representation of the control state of a program

Data structure available to the programmer instead of hidden Contains the current stack and point in the computation Can be later used to return to that point Remember Goto A: blah blah if something GOTO A else GOTO B B: ... Flow control via textual labels mixes computation (beta-reductions)

and representation (the text of the program) Continuations continued Elegant concept for arbitrary flow control Computation in the past Av aila ble t ot he pro gra m

Current Continuation = current point + bound variables Computation in the future Note to self: illustrate continuations in Scheme (Wikipedia) me r What are continuations good for? Everything control flow!

Co-routines (as seen) Exceptions Preserving flow in non-blocking I/O (rhymes!) The continuation nature of exceptions function fact (n) { if (n < 0) throw "n < 0" ; else if (n == 0) return 1 ;

else return n * fact(n-1) ; } function total_fact (n) { try { return fact(n) ; } catch (ex) { return false ; } } document.write("total_fact(10): " + total_fact(10)) ; document.write("total_fact(-1): " + total_fact(-1)) ; The continuation nature of exceptions desugaring the previous slide function fact (n,ret,thro) { if (n < 0)

thro("n < 0") else if (n == 0) ret(1) else fact(n-1, function (t0) { ret(n*t0) ; }, thro) } function total_fact (n,ret) { fact (n,ret, function (ex) { ret(false) ; }) ; } total_fact(10, function (res) {

document.write("total_fact(10): " + res) }) ; total_fact(-1, function (res) { document.write("total_fact(-1): " + res) }) ; I/O and continuations Blocking (I/O in most systems) contents = fs.ReadFile(path); with contents do blah Blocks here until we have the result Non-blocking contents = fs.ReadFileAsync(path); with contents do

blah How to solve this? Uh-oh, we still dont have it I/O and continuations Non-blocking fs.ReadFileAsync(path, lambda(contents) { with contents do blah }); Its a callback! Its the current continuation of the blocking form JavaScript is FULL of this, so are jquery and node.js

Outline Closures Continuations Iterators, generators Lazy evaluation Monads Iterators what is the problem? Problem: accidental large intermediary

lists Example, we want to printout: a stream of positive random numbers n < 1 where abs(ni+1 ni) > 0.4 stream stops when n < 0.1 How would you do this? Iterators 1st attempt

import random def randomwalk_list(): last, rand = 1, random.random() nums = [] while rand > 0.1: if abs(last-rand) >= 0.4: last = rand nums.append(rand) else: print '*', rand = random.random() nums.append(rand) return nums for num in randomwalk_list(): print num, #

# # # init candidate elements empty list threshold terminator accept the number # add latest candidate to nums # display the rejection # new candidate # add the final small element We need to generate the entire list before printing any number out! Iterators 2nd attempt

static function-local variable import random def randomwalk_static(last=[1]): rand = random.random() if last[0] < 0.1: return None while abs(last[0]-rand) < 0.4: print '*', rand = random.random() last[0] = rand return rand num = randomwalk_static() while num is not None: print num, num = randomwalk_static() #

# # # # # # # init the "static" var(s) init a candidate value threshhold terminator end-of-stream flag look for usable candidate display the rejection new candidate update the "static" var Better, but clumsy

Iterators import random class randomwalk_iter: def __init__(self): self.last = 1 # init the prior value self.rand = random.random() # init a candidate value def __iter__(self): return self # simplest iterator creation def next(self): if self.rand < 0.1: # threshhold terminator raise StopIteration # end of iteration else: # look for usable candidate

while abs(self.last-self.rand) < 0.4: print '*', # display the rejection self.rand = random.random() # new candidate self.last = self.rand # update prior value return self.rand for num in randomwalk_iter(): print num, Problem solved! What are iterators, really?

Objects that keep state for traversing an abstract collection Closures that get passed around in every next() btw, objects and closures are related... Outline Closures Continuations Iterators, generators Lazy evaluation

Monads Generators Generators yield values every time they are called http://www.ibm.com/developerworks/ library/l-pycon/index.html Note to self: show this in python interpreter Generators the magic yield

http://matt.might.net/articles/ programming-with-continuations-exceptions-backtracking-search-threadsgenerators-coroutines/ Key idea: toggle between 2 continuations: one in the outter code and one in the generator Note to self: show this in Scheme interpreter Outline

Closures Continuations Iterators, generators [Lazy evaluation] Monads [the teaser trailier] Monads what is the problem? The problem: how to affect the world Problem is more prevalent in pure functional programming style

No side-effects Thats right: no side-effects! But youve all seen it too! No side effects?! Why? Easier to test: idempotent functions Easier to parallelize But the world is ALL about side-effects, right?

Storage, network, UI, ... Programs affect and control objects and activities in the real world Example def hypotenuse(x, y): return math.sqrt(math.pow(x, 2) + math.pow(y, 2)) Now we want to trace it, or affect the world in it: def hypotenuse(x, y): h = math.sqrt(math.pow(x, 2) + math.pow(y, 2)) print x= + x + ;y= + y + ;h= + h return h Example def hypotenuse(x, y):

h = math.sqrt(math.pow(x, 2) + math.pow(y, 2)) return h, x= + x + ;y= + y + h= + h Signature was Signature now is float, float -> float float, float -> float, string > math.pow(hypotenuse(6, 16), 4); What is a monad? Its a container An active container it has behavior to:

Wrap itself around a type Bind functions together What is a monad? A type constructor, m A function that builds values of that type a -> m a A function that combines values of that type with computations that produce values of that type to produce a new

computation for values of that type m a -> (a -> m b) -> m b