[ prog / sol / mona ]

prog


Inverse Recursion?

6 2020-05-14 21:42

>>5
For the programmer, CPS moves the call stack from the stack to the heap. This way one can avoid stack overflows on huge recursive structures, at the cost of having to reverse the data structure. It also makes control explicit and gives a way to simulate having first-class continuations in languages that don't have them.

More importantly, it is in widespread use as an intermediate language in compilers and interpreters. If you are interested in the topic, and want to learn how to algorithmically transforms programs into CPS, EOPL has two great chapters on the topic.

As for isomorphism, I think you are a bit too generous. The result of transforming =natsum= was both the iterative function and the reversing function. In the case of summing the values of a list, we can skip the reversing because of the commutative property of addition. But this is the rare case, for almost any other function you will still have to use both. For example, the iterative Fibonacci function that you tried to transform into CPS is not the same as what we got as fib-cps by transforming the direct-style definition. It is an interesting topic and people have used these transformations to demonstrate some amazing things, like transforming proofs[0] or abstract machines[1], and it is pretty fun to play around with it. But I have no training in this field so I don't want to claim things that are actually not true.

[0] http://cedric.cnam.fr/~puechm/upside.pdf
[1] https://tidsskrift.dk/brics/article/download/21784/19215

7 2020-05-14 22:25 *

I blurred the distinction between CPS and the defunctionalized version a little, I should be sleeping by now. Anyway, CPS is not really iterative since you carry the stack around.

9


VIP:

do not edit these