5
$\begingroup$

Continuation Passing Style (CPS) is a form of code where the control is passed explicitly, by passing the continuation of the code at each call point, unlike direct style.

There are many descriptions in the literature for how to convert from direct style to CPS. The following pseudo-JavaScript:

function direct() {
    var a = foo(1);
    return bar(a);
}

becomes:

function cps(cont) {
    foo(1, function(a) {
        bar(a, cont);
    }
}

But are there any descriptions of the reverse transformation, where the CPS representation is taken back to a direct style?

$\endgroup$
  • $\begingroup$ Are you suggesting performing a CPS => SSA transformation and then proceeding from there? Many of the continuations will be constant, so constant propagation should make the resulting code saner. $\endgroup$ – John Källén Aug 14 '15 at 22:25
  • 1
    $\begingroup$ You need some sort of formal definition of direct style. The CPS transformation is defined as a function from any $\lambda$-calculus expression to a strict subset of the $\lambda$-calculus. Without a definition of what style you're trying to get back into, you can't really define a transformation to do that. $\endgroup$ – jmite Aug 15 '15 at 21:16
  • $\begingroup$ I'm curious as to what the motivation is. Usually, you transform to CPS because you want to use the continuation (e.g., callback). What do you gain by doing the reverse? $\endgroup$ – Nathan Davis Nov 24 '16 at 4:52
  • $\begingroup$ I'm working on the Reko decompiler (github.com/uxmal/reko), and am evaluating approaches to reconstruct C code from a very low level intermediate representation (IR). I'm particularly interested in untangling clarifying code that has been deliberately obfuscated, by tracing the continuations implicit of the IR. $\endgroup$ – John Källén Nov 25 '16 at 0:23
3
$\begingroup$

I did some additional research to answer this question but find nothing better suited.

To do reverse of CPS to direct programming you have to assign functions to variables, this makes direct structural code.

Automated and well described technique comes from compilers - SSA (Single Static Assignment). This has additional bonus like compacting code and constant propagating to some extend.

This is not per se technique to reverse CPS, but structure of assignments creates direct code, so it is usable in your situation.

$\endgroup$
3
$\begingroup$

The transformation to CPS style converts from

r = foo_direct(...);
bar(r);

to

foo_cps(..., bar);

If you want to go backwards, I think the following works. In CPS, every function call will have a continuation as its last argument. So, at each function call site, you find the continuation and unwind it. In other words,

foo_cps(..., ct);

gets translated to

r = foo_direct(...);
ct(r);

where ct can be filled in with any expression of your choice. At the same time the body of foo_cps() gets translated by changing

function foo_cps(..., c) { ...; c(x); }

to

function foo_direct(...) { ...; return x; }

(Note that x might be any expression; in general it might be a tuple of arguments.) You may then have to unwind the call ct(r) if ct is in CTS style. You might want to follow this with some optimizations to detect variable equivalences, e.g., inter-procedural copy propagation.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.