Programming Language:Higher-order functions and closures
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.
In programming language, higher-order functions and closures are often two closely related concepts that needs to be discussed together.
Funcion as first class objects
In Python, functions are first class objects
, in other words, they are
expressions that can be evaluated, stored and passed as function arguments,
just like other primitive types such as int
, float
etc. When we start
passing a function to another function as an argument, we call the argument
as higher-order function.
def apply(x, f):
return f(x)
def concat_myname(s):
return s + 'Michael'
apply('Hello', concat_myname)
def double(d):
return d * d
apply(3, double)
In this somewhat naive example, we see that function as first class objects
made function more generic than before - that we can not only define routines
dependent on primitive types, but also dependent on function behaviors.
Frequent use cases are map
, reduce
and filter
. Their behaviors are:
def mymap(l, f):
if len(l) == 0:
return []
else:
return [f(l[0])] + mymap(l[1:], f)
def myreduce(l, f, acc):
if len(l) == 0:
return acc
else:
return myreduce(l[1:], f, f(acc, l[0]))
def myfilter(l, f):
if len(l) == 0:
return []
else:
return ([l[0]] if f(l[0]) else []) + myfilter(l[1:], f)
Using these functions can be greately simplified with lambda
keyword, which
creates an anonymous function upon evaluation.
l = [1, 2, 3, 4]
mymap(l, lambda x: x*2) # doubles list
myreduce(l, lambda a,b: a + b, 0) # summing list
myfilter(l, lambda x: x % 2 == 0) # drop non-even numbers
Lexical scope and closure
With higher order functions, behaviors can be passed around like variables. However, as they gets passed around, the environment where the function expresion is evaluated also changes. Take at look at the example below:
class Dog:
def __init__(self, name):
self.name = name
def bark(self):
print(f'Bark! My name is {self.name}')
a_dog = Dog('Charlie')
# Say we want to adopt the Charlie dog
def adopt_charlie():
a_dog.bark()
# However, the pet center has other dogs.
# Specifically, variable `a_dog` is shadowed
# by another dog named 'Milo'
def in_pet_care_center(my_action):
a_dog = Dog('Milo')
b_dog = Dog('Oscar')
# When we execute our action, which dog will we adopt?
my_action()
# Bark! My name is Charlie
in_pet_care_center(adopt_charlie)
Yay! We still have Charlie! But let us look closer what happened there. Upon
defining adopt_charlie
, a_dog
is bound to “Charlie”. Inside care center,
a_dog
is shadowed by another Dog
instance. When my_action
is evaluated,
the current environment of evaluation has a_dog
bound to “Milo”. However,
the actual evaluation of my_action
used the environment at which the function
is defined. Evaluating a funtion under the environment where it is defined,
is called Lexical scope rules. Most modern programming languages follow
this rule.
It has many benefits, one of them is that one can easily understands the behavior of a function, only required to read the function body and all the codes before it, without having to worry about where it is called.
As an implementation detail of lexical scope, when one defines a function, the compiler/interpreter will need to save not only the function body, but all (free) variable bindings used by the function. Putting the function body and the bindings together creates a closure. Thus, when we defines a function inside our code, we are actually adding a new binding of the function name to its closure into the environment.
In languages that does not support higher order functions such as C
, we could
simulate the behavior with function pointers, except, we need to also pass the
bindings as an extra argument. For example:
#include "stdio.h"
/* A simplified environment structure */
struct Env
{
char **names;
int **values;
};
/* Same apply as above */
void apply(void* x, void (*f)(void*, struct Env*), struct Env* f_env)
{
f(x, f_env);
}
/* Can retrieve free variables from my_env here */
void power_of_2(void *x, struct Env* my_env)
{
int *i_x = (int*)x;
*i_x = (*i_x) * (*i_x);
}
int main()
{
struct Env some_env; // Empty env upon definition
int n = 4;
apply((void*)&n, power_of_2, &some_env);
printf("%d\n", n); // 16
return 0;
}