[MLton-devel] Re: CPS vs SSA

[Stephen Weeks]

> At one extreme, suppose we had a language where programs were call/cc
> centric. Then clearly CPS would be a good choice.

I disagree.  There is no difference between CPS and SSA with respect
to continuations being explicit.  The only difference is that scoping
and dominance information is explicit in CPS.  And scoping and
dominance has nothing to do with call/cc.

> Call/cc would be compiled to primitive function calls that would be
> easily optimized with other constructs.

If you'll show me the extension that you make to the CPS grammar that
I sent so that you can handle call/cc, I'll show you the comparable
extension to the SSA grammar.  In fact, the extension is probably the
same.

> It turns out that compiled Nova programs look like spagetti code, and
> exceptions are a nice way of capturing much of the control flow in a
> high-level language. We find that programs tend to be
> 'exception-centric'. The domain (network processors) places a premium
> on execution and so the exception handling must be compiled away as
> efficiently as possible.
> 
> CPS handles this situation cleanly --- the exception handling is
> expressed as simple function calls, and the handlers are nicely
> bundled up in continuations. 

There is no difference between CPS and SSA with respect to exception
continuations being explicit.  Either can make them explicit in
exactly the same way.  Here is an extension to the grammars that I
sent earlier that makes exception continuations explicit.

<transfer> ::= ...
	     | raise <x>			raise
             | <l> (<f> (<x>*)) handle => <l>	nontail call with handler

This works for either CPS or SSA.  The idea is that at a nontail call,
we can specify a handler continuation just as we explicitly specify a
return continuation.  Then, a raise transfer is simply a return (or in
CPS lingo, a call) to the exception handler continuation.

> Is there a better way to take an absyn to a first order IL where
> exception handling is not implemented using complex prim-ops?

Yes.  Use SSA :-).  The approach to making exception handlers explicit
that I show above is what we do in MLton, and it works well.  The pass
that converts from direct style to SSA does keeps track of the closest
enclosing handle expression.  Then, whenever it converts a nontail
call, it records the appropriate handler (or possibly NONE if there is
no enclosing handler).  Whenever it sees a raise, if there is an
enclosing handle, it creates a jump to it.  If not, it creates a raise
transfer.

Optimizations that run on the SSA IL like inlining and contification
are careful to turn raises into jumps when moving the body of one
function inside another at a nontail call that has a handler.

And of course the IL type system makes sure it all fits smoothly.

You're welcome to have a look at MLton's SSA IL, which is a superset
of what I've described in email.

	http://cvs.mlton.org/cgi-bin/viewcvs.cgi/mlton/mlton/mlton/ssa/ssa-tree.sig?rev=1.44&content-type=text/vnd.viewcvs-markup

We'd be happy to answer any questions you have about it.


-------------------------------------------------------
This SF.NET email is sponsored by: FREE  SSL Guide from Thawte
are you planning your Web Server Security? Click here to get a FREE
Thawte SSL guide and find the answers to all your  SSL security issues.
http://ads.sourceforge.net/cgi-bin/redirect.pl?thaw0026en
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel