13
$\begingroup$

The page "Advanced Scheme: Some Naughty Bits" states:

Continuations are a powerful control-flow construct from which nearly any other control-flow structure [...] may be derived.

I thought that Scheme's call/cc, being related (*) to Peter Landin's J operator, could be used to implement any known control flow structure?

With "control flow structure" I'm specifically thinking about Wikipedia's description of them, e.g. exceptions, coroutines, green threads and so on.

Specifically, are there any examples of control flow structures that cannot be implemented using call/cc?

(*) I haven't been able to dig up any paper that establishes that call/cc is as powerful as the J operator. A paper by Felleisen (which I haven't read and admittedly have problems understanding it fully) investigates this, and seems to conclude that even though they are in different complexity classes, they are formally equivalent.

(Also note that I have updated the question based on the comments below)

Update

Based on the excellent answer by @Neel below, I've looked at sites commenting on delimited and undelimited continuations, and it does indeed seem that while call/cc, being undelimited, is not sufficient. Meanwhile, first-class, delimited continuations (like shift/reset) can be used, it seems, to express any control-flow structure.

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ What is the formal definition of a "control flow structure"? $\endgroup$
    – Huck Bennett
    Feb 1, 2013 at 0:13
  • 4
    $\begingroup$ Re: undelimited continuations. Did you read the referenced paper by Hayo Thielecke? The actual claim is that undelimited continuations as provided by call/cc cannot express exceptions in the absence of state. (As Thielecke goes on to point out, exceptions can be implemented by passing around two continuations, one for the program and the other for the exception handler, but that requires more than just call/cc.) $\endgroup$
    – rici
    Feb 1, 2013 at 2:47
  • $\begingroup$ @Rici: I only skimmed the first few pages. (Reading papers takes me a long time). Thanks for the comment! $\endgroup$
    – csl
    Feb 1, 2013 at 8:37
  • $\begingroup$ @HuckBennett I don't have a formal definition, but informally I mean what it described at en.wikipedia.org/wiki/Control_flow -- specifically I mean that you can use continuations to express, and more importantly, to implement, coroutines, green threads, exceptions, escape-statements, the amb-operator, and so on. $\endgroup$
    – csl
    Feb 1, 2013 at 8:56
  • 2
    $\begingroup$ @csl In addition to making more precise what "control flow structure" means, you also need to be more clear what it means to "express" something. This is a difficult problem, and the answer to your question depends strongly on what you count as expression. After all, you can always somehow code up a Turing machine which encodes an interpreter of a language with exceptions (e.g. Java). But that's probably not what you have in mind, so you need to put strong constraints on the concept of "expression" (e.g. compositionality and/or full abstraction). $\endgroup$
    – Martin Berger
    Feb 1, 2013 at 14:02

1 Answer 1

Reset to default
12
+100
$\begingroup$

In this answer, I'll take "expressible" to mean "macro-expressible" in the sense of Felleisen 1991, On The Expressive Power of Programming Languages. (Intuitively, a language feature is macro-expressible if you can define it as a local source transformation, without using a whole-program transformation.)

With this definition, the answer is no: delimited control is not macro-expressible in the lambda-calculus + call/cc. To express delimited control operators using call/cc. In order to implement the control delimiters (the reset part of shift/reset), you need some state to simulate the continuation marks, essentially to encode a stack to simulate the dynamic lifetimes of the continuation marks.

However, delimited control is a universal effect, in the following sense. In his PhD thesis, Andrzej Filinski showed that any expressible side effect is encodable using either delimited continuations, or call/cc and a single cell of state. Roughly, an "expressible side effect" is any effect whose monadic type can be defined in terms of the types of the programming language.

Surprisingly, this idea seems quite interesting in practice. Over the last decade, Gordon Plotkin and John Power have advocated the idea of taking an algebraic semantics of effects theories: the idea is that you specify the side-effecting operations you are interested in, and the equations you expect them to satisfy, and then you can generically get a semantics by taking the free monad over this theory.

Matija Pretnar and Andrej Bauer took this mathematical approach, and then implemented it in their Eff language to invent a new language construct dubbed "effect handlers": you can write code that uses a set of imperative features, and then give the imperative features a semantics by writing a set of handlers which say how to implement each effectful operation.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But if the definition is: "Can you implement any control flow structure using Scheme and call/cc" (without emulation), then the answer must be yes? Looking at the LtU discussion lambda-the-ultimate.org/node/966 it seems that Oleg Kiselyouv implemented all four F-operators in Scheme with call/cc: okmij.org/ftp/continuations/… -- excerpt "The code relies on call/cc for capturing undelimited continuations, and uses one global mutable cell. It turns out, this issufficient for implementing [...] the other F operators". ... "-F- through +F+F". $\endgroup$
    – csl
    Feb 4, 2013 at 19:38
  • $\begingroup$ I do acknowledge your use of Felleisen's "macro-expressibility" as a frame for your answer, but as you can see I had already changed my question to specifically mean "implement [in Scheme] using call/cc". And while Oleg Kiselyov needs to introduce a global mutable cell to implement all four F operators for delimited continuations, I don't think this amounts to a "major, global restructuring of the program" --- practically speaking, of course. $\endgroup$
    – csl
    Feb 4, 2013 at 19:56
  • $\begingroup$ I'm going to accept this answer. I'd also like to point to the text at okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim which has additional pointers. It also seems that first-class, delimited continuations like shift/reset can be used to implement any control flow structure. From the link: "First-class delimited continuations can express any expressible computational effect, including exceptions and mutable state." $\endgroup$
    – csl
    Feb 5, 2013 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.