✓ Reducing Python Into Functional Core¶

We will look at the Python programming language, and identify how we can eliminate imperative parts of the language while still retaining its expressiveness.

Selected parts of Python¶

Variables¶

x = "Hello world"
x

'Hello world'

Variables are mutable in the sense that their values can change during the execution of the program.

x += ", everyone."
x

'Hello world, everyone.'

Loop¶

i = 0
x = ""
while i < 3:
    x += "*"
    print(x)
    i += 1

*
**
***

Function declaration¶

A function can have arbitrary number of parameters.

def power(x, y):
    result = 1
    for i in range(y):
        result *= x
    return result

power(2, 8)

Python also support anonymous functions, called lambda functions.

(lambda x, y: x + y)(10, 20)

Statements¶

A block is a sequence of statements which will be executed sequentially. This style of programming is known as procedural programming.

x = 2
y = 10
z = power(x, y)
print("z =", z)

z = 1024

Reducing Python¶

No variables¶

We can do without variable assignments.

x = 1
y = 2
print(x + y)

def f(x, y):
    print(x + y)
    
f(1,2)

No loops¶

Since Python supports recursion, we can do without loops.

i = 0
x = ""
while i < 3:
    x += "*"
    print(x)
    i += 1

*
**
***

def f(i, x):
    if i < 3:
        print(x)
        f(i+1, x + "*")

f(0, "*")

*
**
***

Unary functions¶

Did you know that we only need functions of a single variable? The trick to simulate functions with multiple parameters is called currying and higher order functions. Both concepts will be explored in greater detail.

def power(x, y):
    result = 1
    for i in range(y):
        result *= x
    return result

power(2, 10)

def f(x):
    def g(y):
        if y == 0:
            return 1
        else:
            return x * g(y-1)
    return g

f(2)(10)

No statements¶

We can simulate procedural blocks without statements.

x = 1
y = 2
print(x + y)

(lambda x: (lambda y: print(x+y)))(1)(2)

Summary¶

The minimal core programming constructs are:

Variable names as parameter names
Function declaration with a single variable
Function invocation
Data and functions as return values and arguments

We are ready to formalize the core as a formal language known as lambda calculus.