# Is there a described algorithm converting _from_ Continuation Passing Style?

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?

• 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. – John Källén Aug 14 '15 at 22:25
• 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. – jmite Aug 15 '15 at 21:16
• 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? – Nathan Davis Nov 24 '16 at 4:52
• 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. – John Källén Nov 25 '16 at 0:23

## 3 Answers

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.

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.

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.