6
$\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?

Improve this question
$\endgroup$
4
  • $\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
    Commented Aug 14, 2015 at 22:25
  • 2
    $\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$
    – Joey Eremondi
    Commented Aug 15, 2015 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
    Commented Nov 24, 2016 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
    Commented Nov 25, 2016 at 0:23

3 Answers 3

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
2
$\begingroup$

From "Back to Direct Style" by Oliver Danvy:

Much work has been devoted to transforming programs into continuation-passing style (CPS). ... By contrast, programs that are not in CPS (e.g., programs before CPS transformation) are said to be in "direct style" (DS). Their procedure calls can occur anywhere (i.e., not necessarily in tail position). In contrast to the work mentioned above, the present paper studies the transformation of CPS programs into DS. ...

That is expanded upon in "Back to Direct Style II: First-Class Continuations" by Danvy & Lawall:

The direct-style transformation aims at mapping continuation passing programs back to direct style, ... In this paper, we continue to investigate the direct-style transformation by extending it to programs with first-class continuations.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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