[MLton] CPS in MLton

[Matthew Fluet]

> I am a student at the Georgia Institute of Technology.  As part of a project 
> for Olin Shivers, I have been asked to take the MLton frontend and perform a 
> CPS transformation on the IR in order to experiment with some optimizations 
> techniques.

Great.  This wouldn't happen to be super-beta inlining with delta-CFA?  I 
was _very_ impressed by Matthew Might's presentation at POPL, and that 
paper is next on my reading list.

> Before diving into the source code, I was wondering if you could provide 
> any insight into how difficult it would be to do this.  Any insight into 
> how to do this would also be greatly appreciated.

The easiest way to add an optimization to MLton is to express it as a 
source-to-source transformation on one of the compiler ILs.  See
   http://mlton.org/CompilerOverview
for a list of the intermediate languages and the optimizations for each.
Most likely, you will want to focus on the XML and SXML ILs:
   http://mlton.org/XML
   http://mlton.org/SXML

These ILs are not in CPS per-se; you can think of them as polymorphic and 
simply-typed lambda calculi respectively.  You could, of course, run the 
CPS transform as a source-to-source translation on these ILs, though I 
suspect that would impact the effectiveness of MLton's 
defunctionalization/closure converter pass:
   http://mlton.org/ClosureConvert
(On the other hand, that might be an interesting experiment in itself.)

> As far as I understand the project, currently, an optimization has been 
> written that will take an IR that uses CPS, and spits out an improved IR 
> in CPS.  I have to take at least the frontend from MLton, connect it to 
> a CPS transformation, and connect that to the optimization.  Then, I 
> will either connect it back to the MLton backend, or write my own 
> backend.

If the optimization that you want to investigate really relies on the 
source being in CPS, then you'll have a slightly harder time integrating. 
Could you describe the optimization you have in mind?

As I said above, you ought to be able to CPS convert the SXML IL, but it 
might have detrimental effect on the resulting code.  On the other hand, 
you might still be able to measure the effectiveness of your optimization, 
even if it doesn't compare favorably with not CPS converting.