This is a series of notes taken from the Coursera course: “Programming Language” by professor Dan Grossman. I plan to chain these notes up with the catchy terms that I learnt from the course.
From our last discussion of higher order functions, functions can be evaluated, stored and passed as arguments just as other variables. Storing a function (closure) into a variable means something new to the code paths: it means we get to delay evaluation of some routines of your code until they are needed.
Starting from a dumb example, that we want to define our own
if statement in python. Notice that
the syntax and semantics of
if require the condition variable to be evaluated as
the true/false statements to be first evaluated, and returned.
# Mimics # if cond: # texpr # else: # fexpr # Ignore the case where texpr not a callable def myif (cond, texpr, fexpr): return texpr() if cond else fexpr()
Now we use
myif in a Fibonnaci series calculation:
def myfib(n): return myif( n == 1 or n == 2, lambda: 1, lambda: myfib(n-1) + myfib(n-2) )
Some interesting observation here: when
myfib is invoked, the arguments are two higher order
functions, not just two expressions. This is because when
myif is called, we don’t know which
code path will be excuted yet, so we want to delay their execution until appropriate. The two
code paths are wrapped in a 0-argument, anonymous function, which is often called as
Next, a few common programming idioms related to
thunk and delayed execution is introduced.
When we have some large computation to work on, but do not know if it is required to do so, we
usually wrap such operations inside a thunk. Combining it with memoization, we could create a
def delay(f): return [False, None, f] def force(f_promise): if not f_promise: f_promise = True f_promise = f() return f_promise else: return f_promise
delay creates a promise, which is a mutable list where the first indicates whether the thunk
is used or not, the second saves the result and the third is the thunk that contains the large
force check whether the thunk is evaluated. If not, set the execution flag to be
True, it would evaluate the thunk, memoize the evaluation result, then return the result.
A stream is an infinitely long sequence of values. Computer memories are finite so it cannot actually store infinite amount of values on the memory. To define a stream strcuture, we make use of thunks to wrap a stream generator into the stream structure.
The following code constructs a stream object that produces all natural numbers:
def make_nat_stream(): def make_n_stream(n): return (n, lambda: make_n_stream(n+1)) return make_n_stream(0)
Stream is defined as a tuple, where the first element is the value. THe second is a generator
that produces the next natural number. When
make_n_stream is first invoked, a closure is
created for the second element of the tuple. The clsoure contains the binding for the argument
of the next recursive call to
make_n_stream, which is
n+1, the next natural number.
s0 = make_nat_stream() # (0, thunk) s1 = s0() # (1, thunk) s2 = s1() # (2, thunk) ...