proglang-10-01-19.md

Tail Recursion & Lazy Evaluation - Programming Languages - Oct 1st, 2019

How come we don’t use recursion frequently in every language?

Code 1.1 Recursive factorial function

def fac(n):
	if n==1:
		return n
	else:
		return n*fac(n-1)

Code 1.1 doesn’t work for n > 1000 because by default Python doesn’t allow a recursive depth of above 1000.

This is because each recursive call creates a stack frame in memory and Python wants to prevent a stack overflow.

Does Haskell prevent large recursive calls?

No

This means that Haskell has something in its implementation that is making recursion more feasible. Let’s explore what this is and see if it is also achievable in Python or C++.

Code 1.2 Iterative version of factorial

def fac_iter(n):
	result = 1
	while n > 0:
		result *= n
		n-=1
	return result

Code 1.3 another recursive factorial function

def fac2(n, accumulator=1):
	if n == 0:
		return accumulator
	return fac2(n-1, accumulator*n)

What’s the difference between fac and fac2? In fac, when each recursive call is finished, it has to pass the result in the calling function so that it can be multiplied by n.

In fac2, the final recursive call which is fac2(0, n!) has the answer and doesn’t need to pass the value back to the calling functions BUT Python is not smart enough to do that because it doesn’t have tail-call optimization.

Tail-Call Optimization

In tail-call optimization, there is only one stack frame and it is occupied by the most recently called recursive call.

• You have to write your code in a way that there is nothing left to do after the return function — a.k.a. Tail-call recursion
  • “Is recursion the last thing to do in the function?”

Python does not have tail-call optimization.

Haskell does.

You can enable tail call optimization in Python using a library:

• The library does not check if the function is properly using tail-call recursion

from tailcall import tail_call_optimized

@tail_call_optimized
def fac2(...):
	...

Exercises: Making functions tail-call recursive (Likely to be on an exam 😉)

Make count tail-call recursive

def count(lst):
    if lst == []:
        return 0
    else:
        return 1+count(lst[1:])

Answer:

def count2(lst, acc=0):
    if lst == []:
        return acc
    else:
        return count(lst[1:], acc+1)

Make my_map tail-call recursive

def my_map(f, xs):
    if xs==[]:
        return []
    else:
        head=xs[0]
        tail=xs[1:]
        return [f(head)] + my_map(f, tail)

Answer:

def my_map2(f, xs, result=[]):
    if xs == []:
        return result
    else:
        head = xs[0]
        tail = xs[1:]
        return my_map2(f, tail, result+[f(head)])

Make fib tail-call recursive:

def fib(x):
	if x == 0:
		return 0
	if x == 1:
		return 1
	return fib(x-1) + fib(x-2)

Answer:

# Won't be on exam
# It's tricky
def fib2(x, a=0, b=1):
	if x == 0:
		return a
	if x == 1:
		return b
	return fib(x-1, b, a+b)

Lazy Evaluation

Infinite Lists

let x = [1..]

x !! 500 -> 501 x !! 5000 -> 5001

Is Haskell storing a giant infinite list in memory? No

Let’s look at C for how this works

bool someglobalvariable;

int fun(int z){
	if (someglobalvariable)
		return z;
	else
		return 0;
}

int provider(){
	return // some big complex algorithm
}

int x = fun(provider());

Are there situations in C or C++ where code is called only when it’s needed?

if-statements and short circuiting

if (false){
	print("ASFD");
}

int x = someglobalvariable || provider();

// pre-processor functions that return one thing
# define FOO(x) 3
int x = FOO(processor()) // returns 3 without calling processor

Look at the following C++ code:

using namespace 
int justReturn5(int x){
	return 5
}
int main(){
	cout << justReturn5(12 / 0) << endl;
}

-> Returns an error!

Let’s look at the equivalent code in Haskell:

let justReturn5 _ = 5

justReturn(12/0) -> 5

This is because C++ uses Strict Evaluation and Haskell uses Lazy Evaluation

Lazy Evaluation means that it does not evaluate an expression unless it needs to.

Thunks

bigList :: Integer -> [Integer]
bigList x = x : bigList(x*2)
let x = bigList 1

x in memory is equal to: 1 -> Thunk(bigList 2)

A Thunk is only evaluated when needed

Can we mimic this behavior in Python?

def bigList(n):
	return [n] + bigList(n*2)

def bigList(n):
	def getnextnum():
		return (n*2)
	return (n, getnextnum)

def takeBigList(n, abiglist):
	if n == 0:
		return []
	(item, nextitem) = abiglist
	return [item] + takeBigList(n-1, nextitem())

#proglang-f19