Lambda the Ultimate

Could anybody knowledgeable, please, compare the expressive power of different control handling primitives, such as:

call/cc
run / fcontrol
prompt / cupto
shift / reset (control?)

I learned already that both cupto and shift/reset are expressable with call/cc (http://pauillac.inria.fr/~remy/work/cupto/), and it looks to me that run/fcontrol differ from prompt/cupto only superficially (http://citeseer.nj.nec.com/sitaram93handling.html).

Also, call/cc is expressable with cupto.

What I could not find is whether call/cc is more expressive than shift/reset. Also the intuitive notion of expressiveness, as was mentioned on LtU recently, is more than just emulation with local changes. It would be great to hear subjective experiences of somebody who tried several approaches in the field.

Thanks.

Among the many existing control operators, we only consider call/cc, prompt/control, shift/reset, sequential spawn, splitter/abort/call/pc. We also add dynamic­wind to them although it does not belong to the same family of control operators. Our lingua franca is Scheme extended with a simple class definition facility. We use Scheme (i) to avoid frightening Greek letters and, (ii) to provide implementations people can play with in any plain Scheme system.

I think I finished my quest for a side-by-side comparison paper, but if anybody has practical knowledge of the topic - it's more than welcome.

The funny part is I read SRFI-20 for the first time just yesterday, and today I stumble upon his another paper. Probably I needed to say Schemer's world is very small :-)

Ah, I am starting to usurp this thread, it's time to end here.

I don't have the time to delve into this at the moment, but let us know what you uncover.

His 1999 paper "Using a continuation twice..." is also quite interesting (at least, to me).

But, theory aside, I too would be interested in hearing from anyone with practical experience.

Yes, I really enjoyed this paper, the essence is:

exceptions cannot express continuations (Section 3); conversely, continuations in the absence of state cannot express exceptions (Section 4). If exceptions and continuations are combined in the same language, they cannot express state (Section 5). Exceptions and state cannot express continuations (Section 6)

BTW, this paper cites A Generalization of Exceptions and Control in ML-like Languages, which cites A library of high-level control operators mentioned before. So this thread is steadily moving from early 90's into the 21st century :-)

This statement intrigued me (any EOPL reader knows this ain't true), so I started reading this very interesting paper (more later). Let me clarify the quote Andris gave, with the following (also from Thielecke's paper):

When we say that first-class continuations cannot express exceptions (in the absence of state), this is meant in the sense that callcc cannot express them. That should not be taken to imply that there can be no continuation semantics of exceptions; rather, it merely states that such a semantics does not factor over that of callcc . In fact, a continuation semantics for exceptions can easily be defined by passing two continuations, the current one and one for the current exception handler.

call/cc and abort can both be expressed in terms of shift and reset

Danvy and Filinski (DIKU TR 89/12, page 3)

shift/reset in terms of call/cc and state

Filinski (POPL '94); see also the Scheme48 distribution

control and prompt in terms of call/cc and state;
call/cc (and abort) in terms of control and prompt

Sitaram and Felleisen (LSC '90)
(Errata at Usenet Message-ID: <6079@brazos.Rice.edu>)

shift and reset in terms of control and prompt

Easy: translate "reset" to "prompt" and "shift f" to "control g. let f x = prompt (g x) in".
This is mentioned by Gunter, Rémy, and Riecke (FPCA '95, the paragraph at the upper-right corner of page 4)

control and prompt in terms of shift and reset

The existence of such a translation is implied by the fact that control and prompt as control effects are a monad, because Filinski's "representing monads" result tells us how to simulate any monad using shift and reset. But Gunter, Rémy, and Riecke (same paragraph) seems unaware of such a translation. In any case, I have just produced an explicit translation; it crucially relies on recursive types.

call/cc without state cannot express shift/reset; see Sitaram and Felleisen LFP '90.

Now I am thinking about drawing a diagram of this category... The category of control operators, morphisms being "expressable in terms of". Only half-joking.

Looks like I have to re-visit spawn, it looks more interesting in the light of concurrency requirements I would like to address...