---
tags: programming languages, haskell
---
# Imperative vs Functional Programming

(Part of the course *Programming Languages*)

The hello-world of recursive programming is the factorial function or the Fibonacci sequence. The Fibonacci numbers are defined mathematically as follows.

\begin{align}
fib(0) & = 0\\
fib(1) & = 1\\
fib(n+2) & = fib(n) + fib(n+1)
\end{align}

**Discussion:** Write a Python function `fib` such that `fib(n)` computes the `n`-th Fibonacci number. (Feel free to choose another programming language such as C or Java or ....). Compare the different solutions among themselves and with the mathematical definition.

## On Python's Memory Model

We are all familiar with the model of computation underpinning imperative programming languages like Python. It is based on the assignment as an operation that modifies memory.

The following experiments are a bit of a digression, but show that the Python memory model is more complicated than one might expect at first.

**Discussion:** Replay the following experiments in your version of Python. What do they tell you about the memory model of Python?

		>>> a=256
		>>> b=256
		>>> a is b
		True
        
		>>> a=257
		>>> b=257
		>>> a is b
		False
        
		>>> a=257; b=257
		>>> a is b
		True

This mysterious behaviour has something to do with integers being objects. But even then ...

		>>> x=1
		>>> y=x
		>>> y=2
		>>> y==x
		False
		
		>>> x=[1]
		>>> y=x
		>>> y[0]=2
		>>> y==x
		True

After all of this, what do you expect will be the answer to the following? [^answer]

[^answer]: `False`

		>>> x=[1]
		>>> y=x
		>>> y=[2]
		>>> y==x

To sumarize, the above experiments show that **the memory model of Python is not simple**.

As we will explore next, in order to compute the Fibonacci numbers we can simply use the defining equations directly, using a model of computation that, like the one in high-school algebra, only has one[^one] simple rule: **replacing-equals-by equals**.

[^one]: We will later refine our analysis of equational reasoning.

## A Model of Computation Based on Equational Reasoning

We first want to understand whether it is possible at all to turn a mathematical definition such as

\begin{align}
fib(0) & = 0\\
fib(1) & = 1\\
fib(n+2) & = fib(n) + fib(n+1)
\end{align}

into a computation in a principled way that could be automatised.

**Remark:** This style of definition is called **recursive**, because, in order to define $fib(n+2)$ we are *recurring* (=going back) to the values $fib(n-1)$ and $fib(n-2)$. This definition looks almost circular, since we define $fib$ in terms of itself. But it is a good definition, because at each step one *recurs* to smaller values. (We read the equations from left to right, *rewriting* the left-hand side by the right-hand side.) The recursion will terminate when we reach $fib(0)$ and $fib(1)$. (Among the three cases that make up the definition, the first two are called the *base cases* while $fib(n+2) = fib(n) + fib(n+1)$ is called the *inductive case*.)

**Activity:** Compute $fib(6)$ by writing out a sequence of mathematical equations, that is, fill in the dots below.
\begin{align}
fib(6) & = fib(4) + fib(5)\\
& = fib(2) + fib(3) + fib(5)\\
& \ldots \\
& = 8
\end{align}

each step corresponding to either the application of one of the three defining equations above or to one of the usual rules of mathematics for addition.

**Activity:** Draw the computation above in tree form by completing the figure below.

fib(6)
|
+
/ \
fib(4) fib(5)
| |
+ +
/ \ / \
... ...

The equational reasoning and the tree look quite different. It is important to understand that they are both just two different ways to picture the same computation. Discuss.

**Discussion:** If you have not done so already, write a recursive program in Python computing the Fibonacci numbers. Explain its execution with the help of the tree above. In what order does Python traverse the tree?

By now we have seen both iterative and recursive implementations of the Fibonacci numbers. But even Python's recursive implementation is not as short and elegant as the mathematical definition. The reason is that Python incorporates only some of the features of a modern funtional programming language. So let us look at Haskell.

## Recursion in Haskell

In Haskell, the following is a program.

	fib 0 = 0
	fib 1 = 1
	fib n = fib (n-1) + fib (n-2)

Haskell is quite close to mathematical practice in many ways. One of the main differences are the conventions of how to place parentheses. For example, where in maths we would write $fib(n)$, in Haskell we can simply write `fib n`.

**Activity:** You can run the code at [codeworld](https://code.world/haskell#PZVArMVFOFPm9aKSsLuCqqA).

## Optional Practice Problems

### Run Fibonacci From Your Terminal

Install the Haskell platform. Save the program

	fib 0 = 0
	fib 1 = 1
	fib n = fib (n-1) + fib (n-2)

into a file called `recursion_fib.hs`.[^hs]

Run the program as follows.[^cd]

ghci
:load recursion_fib.hs
fib 5

Also add a main function (see the replit above) that calls `fib 5` and then run the program as

runhaskell fib.hs

**Remark on Executing Haskell:** Haskell programs can be interpreted and can be compiled.

- `ghci` is the Haskell interpreter. After loading a file you can call all functions in the file with arguments of your choice.
- `runhaskell` compiles the file and run the `main` function. To compile and run a Haskell program it needs a `main` function.

#### Write a Recursive Function in Haskell

- Probably the first recursive function to implement is factorial.
- Not more difficult, but more interesting: Write a function `hailstone` implementing the recursive computation at heart of the [Collatz problem](https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/).
- Explore on your own ... [triangular numbers](https://en.wikipedia.org/wiki/Triangular_number) ...

### Fibonacci in Python

Implement the mathematical specification

\begin{align}
fib(0) & = 0\\
fib(1) & = 1\\
fib(n+2) & = fib(n) + fib(n+1)
\end{align}

with a recursive Python program.

This direct implementation has the advantage of being clear and direct, but the disadvantage of being inefficient. I call it the "naive" recursive implementation for the purposes of this homework.

- What is the largest $n$ such that the naive implementation of $fib(n)$ returns a value in less than 10 seconds?
- What is the time complexity of the naive recursive program? Why is the time complexity of the naive implementation of $fib(n)$ not linear in $n$?
- Improve the program (while keeping the recursive part) by storing results in a "cache" to avoid computing the same value twice. (This technique is called **memoization**.)
- What is the largest $n$ such that the improved implementation of $fib(n)$ returns a value in less than 10 seconds?
- Use the `lru_cache` library to achieve the same by just adding one line of code to the naive program.

Shortcut: A solution to this exercise is in [this video](https://www.youtube.com/watch?v=Qk0zUZW-U_M&feature=emb_rel_end).

One can also write a [memoized fib in Haskell](https://wiki.haskell.org/Memoization#Memoization_with_recursion). I am not sure whether this really has linear time complexity. If you want to benchmark programs you can do this inside `ghci` using `:set s+`. You can also add a main function and call the program from your terminal using `runhaskell`.

## Summary: Imperative vs Functional Programming

(functional programming languages are also called applicative languages, in particular in the older literature)

In an imperative language such as Python one typically distinguishes statements and expressions. Expressions such as $1+2$ can be evaluated. Statements such as conditionals, loops, assignments do not return values but compute via the side effects they have on the control flow or the memory.

In a functional programming language such as Haskell everything is an expression. Evaluation of expressions is how computation proceeds.

Consequently, the computational model of functional programming languages is much simpler than the one of imperative programming languages. The computational model of functional programming is in its essence just equational reasoning as in high-school algebra.[^equational]

This is one reason why we start out the course with functional programming languages. Another reason is that I assume that most students will be familiar with imperative langauges such as Java, C++ and Python, but not with functional ones. Moreover, in the next semester, in Compiler Construction, we will learn how to write a compiler for C++ and the compiler will be written in Haskell. So we should start learning some Haskell already now.

## Epilogue: Lazy Lists (Streams)

Using list comprehension, pattern matching and the built-in functions `zip` and `tail` we can write down the following cute Haskell definition of the sequence of **all** Fibonacci numbers.

fib = 0 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]

Note that here the equation operates not on elements of the sequence, as before, but on sequences (or rather *streams*, which are potentially infinite sequences).

To print the first 10 elements of the sequence use

take 10 fib

You can run this at [codeworld](https://code.world/haskell#P_JjZB_NPKLkHgBAPfOgEYw).

## Further Reading

- My notes on [First Steps in Haskell](https://hackmd.io/@alexhkurz/SJgHGZ_nw).
- [GeekforGeeks: Program for Fibonacci numbers](https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)
- [Haskell Wiki: The Fibonacci sequence](https://wiki.haskell.org/The_Fibonacci_sequence)
- [A Gentle Introduction to Haskell: Case Expressions and Pattern Matching](https://www.haskell.org/tutorial/patterns.html)
- One of the characteristic features of functional programming is that there are no statements and everything is an expression. The blog [Why Expressions are Safer and Make Better Building Blocks](https://fsharpforfunandprofit.com/posts/expressions-vs-statements/) contains an eloquent explanation of the benefits. Explain why `// note that the else case must be specified` is important.

[^hs]: The ending `.hs` has no meaning in itself, it is just a convention used by Haskell programmers to indicate that the file contains the source code of a Haskell program. `recursion_fib.hs` is a text file that can be created and modified with any text editor. Popular text editors include [vsCode](https://code.visualstudio.com/), which I use myself, [Sublime](https://www.sublimetext.com/) and [Atom](https://atom.io/).

[^cd]: The code below requires that the file is in the working directory of the terminal. There are several ways to get a terminal with the correct working directory. In vsCode I can right-click on a file and open it in an integrated terminal. Alternatively, one can use the command `cd` in the terminal to change directory. A basic list of linux commands can be found [here](https://www.pcsuggest.com/basic-linux-commands/).

[^equational]: With one addition that we will see shortly, probably in Week 3.