[MLton-devel] Re: CPS vs SSA

[Stephen Weeks]

> In any case, I don't understand what you are saying here.  In CPS,
> you don't need any extension to handle call/cc (or exceptions).  The
> base language itself is already able to express these things.  The
> same is not true for a direct-style SSA form.

I think that your confusion at my use of the word "extension" arises
because the grammars that I presented make distinctions that are not
present in traditional CPS, where everything is expressed as a
function call.  My grammar has 6 different kinds of transfers (jump,
raise, return, tail call, nontail call, nontail call with handler).
All 6 of those would be expressed as function call in CPS.  So, in one
sense, when I added the transfers (raise, nontail call with handler)
to implement exceptions I was extending the IL.  But, in the
traditional CPS sense, I wouldn't have been, since those are all
function calls anyway.

I prefer my way of expressing CPS to the traditional way because
making those distinctions allows me to use different implementation
techniques for the different kinds of transfers (and in fact we do
this in MLton).  I have found that that CPS-based compilers like
SML/NJ (and Orbit before it) do make those distinctions in practice
even though they still use the slogan that "everything is a call".  I
prefer to make the distinctions more explicit by using different
syntax for the different kinds of calls.

I completely understand what you mean when you say that traditional
CPS doesn't need an extension to handle callcc.  I am familiar with
the usual translation of callcc into CPS.

	[[x]] = fn k => k x
	[[fn x => e]] = fn k => k (fn x => [[e]])
	[[e1 e2]] = fn k => [[e1]] (fn v1 => [[e2]] (fn v2 => v1 v2 k))
	[[callcc e]] = fn k => [[e]] (fn f => f (fn v => fn k' => k v) k)

I also understand that if one chooses to implement continuations and
functions with the same mechanism (e.g. allocate both as immutable
objects on the heap), then one can use the same syntactic construct in
the IL.  Hence, no extension is required in traditional CPS for
continuations.

However, my question about callcc was in the context of the grammars
that I sent.  In those grammars, all control transfers aren't
expressed as calls.  The only difference between CPS and SSA is that
CPS makes certain scoping/dominance more explicit.  Continuations (be
they regular continuations or exception continuations) are equally
explicit in both ILs.  Because those grammars do not express
everything as a call, there must be some extension (a primitive,
syntax, whatever) to implement callcc.  I claimed (and still claim)
that the same extension will work in either.

I got the impression from Lal that he is interested in optimizing
callcc to some extent.  Because of that I thought it was possible that
he might add support for it to the IL differently than we do in MLton,
where we haven't worried about optimizing callcc at all.  I was
curious to know how.  Anyways, here's how we do it in MLton.

<p>        ::= ...
             | copyCurrentCont
             | copyCont

<transfer> ::= ...
             | switchToCont

As with exceptions, these extensions to the language make sense for
both CPS and SSA.  To construct the continuation, we use a primapp of
copyCurrentCont.  Looking at the CPS translation

	[[callcc e]] = fn k => [[e]] (fn f => f (fn v => fn k' => k v) k)

copyCurrentCont builds the representation of (fn v => fn k' => k v).
Because MLton mutates its stacks, we then use copyCont followed by a
switchToCont to implement throw.

One other point that I'd like to make.  Making these distinctions that
between control transfers that are not made in traditional CPS does
not preclude using the same implementation technique for them.  It
merely opens the possibility of using different ones.  And, in the
tradition of typed ILs, lets the IL type checker make sure that the
implementations are consistent.


-------------------------------------------------------
This SF.NET email is sponsored by: Take your first step towards giving 
your online business a competitive advantage. Test-drive a Thawte SSL 
certificate - our easy online guide will show you how. Click here to get 
started: http://ads.sourceforge.net/cgi-bin/redirect.pl?thaw0027en
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel