Novelties

Call with current continuation (callCC)

Berp provides a callCC primitive, which is inspired by the one from Scheme. callCC allows you to capture the evaluation context at some point in a computation and reinstate it at a later point. You can use it to implement all sorts of control flow operators.

The example below demonstrates how callCC can be used to “return early” from a function call:

>>> def f(g):
...     g(True)
...     return False
... 
>>> f(lambda x: x)
False
>>> callCC(f)
True
>>>

Here’s another example which shows how callCC can be used to implement loops:

>>> def f():
...    count = 0
...    k = callCC(lambda x: x)
...    print(count)
...    if count < 3:
...       count = count + 1
...       k(k)
... 
>>> f()
0
1
2
3
>>> 

Tail call optimisation

Tail call optimisation allows for efficient implementation of certain function calls – those that appear in “tail positions”. In Python tail calls occur when a return statement is applied to an expression which is itself a function call. Tail call optimisation avoids the creation of a new stack frame for such calls, which saves memory and time. It is especially useful in situations where the tail call is a recursive call. This allows us to employ recursive functions efficiently.

Here is a tail recursive version of the factorial function:

>>> def fac(n, acc):
...     if n == 0:
...        return acc
...     else:
...        return fac(n-1, n*acc)
... 
>>> fac(1000, 1)
402387...

The result of fac(1000, 1) is a very big number, so I have truncated it for the purposes of demonstration. Due to tail call optimisation, the above code uses constant stack space in berp.

CPython does not perform tail call optimisation, so the above code will consume stack space proportional to the depth of recursion (1000). At this point it runs out of space and yields an error saying “RuntimeError: maximum recursion depth exceeded”.

One of the downsides of tail call optimisation is that it avoids the creation of stack frames, which could be useful information for debugging. As usual it is a tradeoff.