Agenda:
- What is functional programming?
- What's the connection between functional programming and parallelism?
- How do we perform computation in functional languages?
Specifying algorithms¶
We need a way to specify both what and algorithm does and how it does it.
Algorithm specification: defines what an algorithm should do.
Given a sequence $A$ of $n$ elements, return a sequence $B$ such that $B[i] \leq B[j]$ for all $0 \leq i \le j \le n$
May also include cost specification, e.g. $O(n \log n)$ work and. $O(\log^2 n)$ span.
Algorithm implementation (or just algorithm): defines how an algorithm works.
This could be real, working code, or pseudo-code.
Our textbook uses a pseudo code language called SPARC
- based on a functional language called ML.
- suitable for parallel algorithms
- good level of abstraction for talking about parallel algorithms
As much as possible, we will also show Python versions of key algorithms.
Functional languages¶
In functional languages, functions act like mathematical functions.
Two key properties:
- function maps an input to an output $f : X \mapsto Y$
- no side effects
- function can be treated as values
- function A can be passed to function B
Pure function¶
A function is pure if it maps an input to an output with no side effects.
A side effect is any change in the state of a program outside of a function's output
Pure functions are simple. Pure functions
- only take input through parameters and return output calculated from that input.
- do not depend on nor modify outside state.
A computation is pure if all of its functions are pure.
Example¶
def double(value):
return 2 * value
double(10)
20
We can view the double function as a mathematical function, defined by the mapping:
versus...
def append_sum(mylist):
return mylist.append(sum(mylist))
mylist = [1,2,3]
append_sum(mylist)
mylist
[1, 2, 3, 6]
This has the side effecet of changing (or mutating) mylist.
though compare with...
def append_sum(mylist):
return list(mylist).append(sum(mylist))
mylist = [1,2,3]
append_sum(mylist)
mylist
[1, 2, 3]
Why is pure computation good for parallel programming?¶
Recall our race condition example:
from multiprocessing.pool import ThreadPool
def in_parallel(f1, arg1, f2, arg2):
with ThreadPool(2) as pool:
result1 = pool.apply_async(f1, [arg1]) # launch f1
result2 = pool.apply_async(f2, [arg2]) # launch f2
return (result1.get(), result2.get()) # wait for both to finish
total = 0
def count(size):
global total
for _ in range(size):
total += 1
def race_condition_example():
global total
in_parallel(count, 100000,
count, 100000)
print(total)
race_condition_example()
171037
The count function has a side-effect of changing the global variable total.
Heisenbugs¶
- Race conditions can lead to bugs that only appear, e.g., 1 out of 1000 runs of the program.
- Reference to Heisenberg uncertainty principal (the bug disappears when you study it, but reappears when you stop studying it)
More generally, if we want to parallelize two functions $f(a)$ and $g(b)$, we want the same result no matter which order they are run in.
Because of the lack of side-effects, pure functions satisfy this condition.
garbage collection
Functional languages¶
In functional languages, functions act like mathematical functions.
Two key properties:
- function maps an input to an output $f : X \mapsto Y$
- no side effects
- function can be treated as values
- function A can be passed to function B
Functions as values¶
Many languages allow functions to be passed to other functions.
Functions as "first-class values."
def double(value):
return 2 * value
def double_and_sum(double_fn, vals):
total = 0
for v in vals:
total += double_fn(v)
return total
# pass the function double to the function double_and_sum
double_and_sum(double, [1,2,3])
# 1*2 + 2*2 + 3*3
12
double_and_sum is called a higher-order function, since it takes another function as input.
Why is this useful?
def map_function(function, values):
for v in values:
yield function(v)
list(map_function(double, [1,2,3]))
[2, 4, 6]
yield turns the function into an iterable object which returns values in the order that they are yielded. For more info, see this guru99 tutorial.
def square(value):
return value * value
list(map_function(square, [1,2,3]))
[1, 4, 9]
list(map_function(double, map_function(square, [1,2,3])))
[2, 8, 18]
What's the big deal?¶
def map_function(function, values):
for v in values:
yield function(v)
list(map_function(double, [1,2,3]))
If we know that
functionis pure, then we can trivially parallelizemap_functionfor many inputs.By using higher-order functions, we can define a few primitive, high-order functions that will make it easier to reason about and analyze run-time of parallel computations.
Lambda Functions¶
- Lambda functions are anonymous functions that we can quickly define and use in python
- They come from Lambda Calculus developed by Alonso Church
# lambda functions exist in Python.
# these are anonymous functions (no names)
# Here, e_2 is a variable.
(lambda x: x*x)(10)
100
We can also chain functions together. E.g., $e_2$ can be another function.
(lambda x: x*x)((lambda x: x+2)(10))
# square(add_two(10))
144
Doing computation via lambda calculus seems limiting.
Can it compute everything we need?
Surprising result:
The Lambda calculus is equivalent to Turing Machines.
That is...
Anything that can be computed by a Turing Machine can also be computed by the Lambda calculus, and visa versa.
More details:
- CMPS/MATH 3250
- Church-Turing Thesis
Coming up¶
Next we will learn about SPARC, the functional psuedo-language used in our book.