[Soot-list] Shimple -> Continuation Passing Style

[Chris Pickett]

J Malcolm wrote:
> Chris Pickett <chris.pickett at mail.mcgill.ca> writes:
> 
>> No, forget about Java, your input files would be a textual
>> representation of the toy SSA IR.
> 
> I'm thinking that, since toy SSA to CPS is seemingly trivial (Kelsey
> 1995 and Appel's texts "Modern Compiler Implementation"), I can go
> directly to getting that basic framework up in Soot.  The toy SSA->CPS
> algorithm is really quite simple.

So then actually just implement it first if it's so simple.  Getting 
your head around that and SableCC in two weeks, well, I'd say that was a 
realistic target.  If it's too easy, try adding some Java-like features 
and then figure out how to deal with them.  At some point it will become 
too cumbersome and then you'll say, OK, I feel like doing this in Soot 
now.  The whole point is just to reduce the complexity by breaking it up 
into manageable pieces.

> Any specific Java stuff you have in mind that I will hit?

I really don't know that much about functional languages, so I'll just 
list all of the Java features I know to be problematic in general:

object allocation
static (class) and dynamic (object) fields
virtual functions
primitive vs. object types
pointers
native methods
exceptions
class loading
threads
finals
volatiles
synchronization

>> example.toy_ssa (written by you)
>>      |
>>      | (SableCC-generated parser)
>>      |
>>      V
>> in-memory toy SSA IR
>>      |
>>      | (your SSA->CPS compiler)
>>      |
>>      V
>> in-memory toy CPS IR
>>      |
>>      | (SableCC-generated printer)
>>      |
>>      V
>> example.toy_cps (which you manually compare against example.toy_ssa)
> 
> Ahh, I see.  The SSA->CPS compiler will be a series of switch
> statements, basically implementing the denotational semantics in
> Kelsey's paper.  The algorithm reproduced in Appel's book for his toy
> language is less than a full page with its maybe 8 or so cases.
> 
> A stripped down Shimple/Java would have the same basic cases.  Starting
> to compile a list of things that will be tricky, I see method invocation
> (virtual, static, etc.) and array access as nontrivial.

For starters.  See above :)

> The printer is obviously trivial since it can be generated in a nested
> fashion with S-expressions.

Well, you'll have this CPS IR, and therefore you'll also have a SableCC 
grammar for that IR (unless for some reason you intend on building your 
CPS IR without a grammar, but I don't recommend that), and so finally 
you'll also have a mechanism to print out something in that 
IR---literally ast.toString() IIRC.  (I possibly don't.)

Cheers,
Chris