INF 141 Latent Semantic Analysis and Indexing

INF 141 Latent Semantic Analysis and Indexing

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

Recently Viewed Presentations

  • Introduction To Epilepsy Semiology diagnosis Treatment

    Introduction To Epilepsy Semiology diagnosis Treatment

    Case 16 year old female with first unprovoked seizure, described as generalized tonic clonic Case 8 y/o with frequent episodes of staring, at times associated with lip smacking Introduction To Epilepsy Semiology diagnosis Treatment M. Scott Perry, M.D. Emory University...
  • Energy stores - WordPress.com

    Energy stores - WordPress.com

    This relationship is known as Ohm's Law (or V=IxR) Walk through how to use the triangle, also why the equation works. After the students calculate the results in the table for resistance see if they can identify any patterns?
  • Chalcogen - UI Health Care

    Chalcogen - UI Health Care

    Chalcogen ('kal-kă-jěn) chemistry and biochemistry: The many faces of O, S, and Se in proteins and enzymes Garry R. Buettner and Freya Q. Schafer Free Radical and Radiation Biology Program and ESR Facility The University of Iowa Iowa City, IA...
  • Electric and Electronic Principles Circuit symbols Diode Earth

    Electric and Electronic Principles Circuit symbols Diode Earth

    The resonance of a series RLC circuit occurs when the inductive and capacitive reactancesare ... When the input is a square wave the tuned circuit acts as a bandpass filter selecting the fundamental frequency and filtering out harmonics ... Low...
  • Patent Pools - University of Wisconsin-Madison

    Patent Pools - University of Wisconsin-Madison

    * * Up until then, an action was only considered a taking if the government took physical possession of the property Pennsylvania Coal was the first recognition of a regulatory taking That is, a situation where the government removed the...
  • Vhled do praxe - Masaryk University

    Vhled do praxe - Masaryk University

    V databázi PDB najděte informace o jedu mamby zelené (jed = venom :-). Stáhněte si soubor s geometrií proteinu (PDB soubor), tvořícího daný jed a prohlédněte si ho v nějakém vizualizačním programu.
  • Critical regions - cl.cam.ac.uk

    Critical regions - cl.cam.ac.uk

    Concurrency - a cautionary tale Grand Central Dispatch (GCD) by Apple API for lightweight threads Work queues hold functions (or code blocks) to be called
  • Argumentation Strategies

    Argumentation Strategies

    Argumentation Strategies The Structure of Arguments The Toulmin Model Data Claim Warrant Evidence (logos) The argument you are trying to make Ties your evidence to your argument Types of Claims Fact Makes a statement about something that can be proven...