[Soot-list] Shimple -> Continuation Passing Style

[J Malcolm]

This is an edited pasting of an email conversation I had this morning
with Patrick Lam.  He suggested opening it up to the list for archival
and to get more input.

-jm

Patrick Lam <plam at sable.mcgill.ca> writes:

> It would not be easy to convert Java into CPS, for two reasons:
> 1) state gets mutated all over the place; and

Very true, but the hope is that control flow analysis will boil all that
out--quite a task.  CPS has side-effects and state just like any other
language.

> 2) typical Java IRs don't contain first-class functions.  People
> usually only use CPS for functional languages, after all.
>
> If you really wanted to convert Java into CPS, then you'd want to
> start with SSA form.  Soot contains an SSA form, Shimple.  Then you
> would need to design an intermediate representation with first-class
> functions; it would include a new family of types for functions.  You
> could then apply the transformation from SSA into CPS on that
> intermediate representation.

The hope was to use Shimple SSA and go from there.  So after I design
that transformation, I also must design a printer for it?

> I'm not sure what you'd have to do about state.  It may not turn out
> to be a problem after all; I haven't thought enough about it.

To keep high fidelity to the original Java program, we hope to have CPS
primitives for things such as malloc, pointer dereferencing, etc.

> I assume that you've seen these references:
>
> * Richard A. Kelsey (March 1995). "A Correspondence between
>   Continuation Passing Style and Static Single Assignment Form". ACM
>   SIGPLAN Notices 30 (3): 13-22.
> * Andrew W. Appel (April 1998). "SSA is Functional Programming". ACM
>   SIGPLAN Notices 33 (4): 17-20.

Yes, that was the hoped for starting point: SSA.  Thanks for pointing
those out.

Any tips on how would I go about starting to design an IR?  It isn't
very clear to me how to transform from Shimple.  Any source you'd
suggest looking through?

Thanks for the fast response and guidance.

-jm