1
$\begingroup$

I am reading this Defunctionalization at work paper. So, in order to ascertain that I got it right, I request a little code review. I'll start with a recursive definition of a factorial function and iteratively translate it to the almost iterative version.

Ok, this is what we start with:

def factorial(value: int) -> int:
    if value == 1:
        return 1
    else:
        return factorial(value-1) * value

Now, we'll traslate factorial from direct style to CPS form (mixed CPS and direct style really, but this would work):

def factorial(value: int, cont: Callable[[int], T]) -> T:
    if value == 1:
        return cont(1)
    else:
        return factorial(value-1, lambda res: res * value)

Identify two basic continuations here - Done and Mul. We'll use Done to simply print things to the screen, and Mul to do a multiplication after a recursive call. So, again, theese are our defunctionalized continuations.

class Cont(Generic[T]):
    """The base class for my defunctionalized continuations."""
    pass


@dataclass
class Mul(Cont[T]):
    value: int
    and_then: Cont[T]


@dataclass
class Done(Cont[T]):
    pass

Here is an apply function, that accompanies our defunctionalized continuations:

def apply(cont: Cont[T], value: int) -> T:
    if isinstance(cont, Done):
        return print(value)
    elif isinstance(cont, Mul):
        return apply(cont.and_then, cont.value * value)
    else:
        raise TypeError("Should be unreachable!")

We notice, that the apply function is in it's tail call form, why no make it iterative:

def apply(cont: Cont[T], value: int) -> T:
    while isinstance(cont, Mul):
        value = cont.value * value
        cont = cont.and_then
    return print(value)

This is what the factorial function looks like now:

def factorial(value: int, cont: Cont[T]) -> T:
    if value == 1:
        return apply(cont, 1)
    else:
        return factorial(value-1, Mul(value, cont))

Optimize it's tail call recursion:

def factorial(value: int, cont: Cont[T]) -> T:
    while value > 1:
        cont = Mul(value, cont)
        value -= 1
    return apply(cont, 1)

And inline the apply function:

def factorial(value: int, cont: Cont[T]) -> T:
    while value > 1:
        cont = Mul(value, cont)
        value -= 1
    while isinstance(cont, Mul):
        value = cont.value * value
        cont = cont.and_then
    return print(value)

And here we have it - an iterative version of the factorial function.

So, my thoughts:

  • Did I get I right? The result makes sense to me - Mul(value, cont) is exactly equivalent to pushing to the stack, and cont = cont.and_then is similar to the stack pop.
  • Although this synthesized factorial function is technically iterative (uses constant stack space), it is obvious that having two while loops is redundant. Moreover, factorial can be trivially written without any stacks what so ever, for example using an accumulator. How do I handle this?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.