<p>In this answer, I'll take "expressible" to mean "macro-expressible" in the sense of Felleisen 1991, <a href="http://www.ccs.neu.edu/racket/pubs/scp91-felleisen.ps.gz"><em>On The Expressive Power of Programming Languages</em></a>. (Intuitively, a language feature is macro-expressible if you can define it as a local source transformation, without using a whole-program transformation.)</p>

<p>With this definition, the answer is <em>no</em>: 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. </p>

<p>However, delimited control is a universal effect, in the following sense. In his <a href="http://www.diku.dk/hjemmesider/ansatte/andrzej/papers/CE.ps.gz">PhD thesis</a>, <a href="http://www.diku.dk/~andrzej/">Andrzej Filinski</a> 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.</p>

<p>Surprisingly, this idea seems quite interesting in practice. Over the last decade, Gordon Plotkin and John Power have advocated the idea of taking an <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.9582">algebraic semantics of effects</a> 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. </p>

<p>Matija Pretnar and Andrej Bauer took this mathematical approach, and then implemented it in <a href="http://homepages.inf.ed.ac.uk/slindley/papers/handlers.pdf">their Eff language</a> 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. </p>

CC BY-SA 3.0
2013-02-04T19:38:02.813Z
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 http://lambda-the-ultimate.org/node/966 it seems that Oleg Kiselyouv implemented all four F-operators in Scheme with call/cc: http://okmij.org/ftp/continuations/implementations.html#generic-control -- 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".
csl
CC BY-SA 3.0
2013-02-04T19:56:05.390Z
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.
csl
CC BY-SA 3.0
2013-02-05T22:13:22.240Z
I'm going to accept this answer.  I'd also like to point to the text at http://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."
csl
CC BY-SA 3.0
2013-02-04T07:48:21.960Z
2013-02-04T07:48:21.960Z
Neel Krishnaswami
<p>The page <a href="http://people.csail.mit.edu/jhbrown/scheme/" rel="nofollow">"Advanced Scheme: Some Naughty Bits"</a> states:</p>

<blockquote>
  <p>Continuations are a powerful control-flow construct from which
  <strong>nearly any</strong> other control-flow structure [...] may be derived.</p>
</blockquote>

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

<p>With "control flow structure" I'm specifically thinking about <a href="https://en.wikipedia.org/wiki/Control_flow" rel="nofollow">Wikipedia's description</a> of them, e.g. exceptions, coroutines, green threads and so on.</p>

<p>Specifically, are there any examples of control flow structures that <em>cannot</em> be implemented using <code>call/cc</code>?</p>

<p>(*) I haven't been able to dig up any paper that establishes that <code>call/cc</code> is as powerful as the J operator.  <a href="http://www.cs.indiana.edu/l/www/ftp/techreports/TR205.pdf" rel="nofollow">A paper by Felleisen</a> (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.</p>

<p>(Also note that I have updated the question based on the comments below)</p>

<p><strong>Update</strong></p>

<p>Based on the excellent answer by @Neel below, I've looked at <a href="http://okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim" rel="nofollow">sites commenting on delimited and undelimited continuations</a>, and it does indeed seem that while <code>call/cc</code>, being undelimited, is not sufficient. Meanwhile, first-class, <em>delimited</em> continuations (like <code>shift/reset</code>) <em>can</em> be used, it seems, to express any control-flow structure.</p>

CC BY-SA 3.0
2013-02-01T00:13:08.010Z
What is the formal definition of a "control flow structure"?
Huck Bennett
CC BY-SA 3.0
2013-02-01T02:47:56.187Z
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`.)
rici
CC BY-SA 3.0
2013-02-01T08:37:24.997Z
@Rici: I only skimmed the first few pages. (Reading papers takes me a *long* time). Thanks for the comment!
csl
CC BY-SA 3.0
2013-02-01T08:56:54.440Z
@HuckBennett I don't have a formal definition, but informally I mean what it described at https://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.
csl
CC BY-SA 3.0
2013-02-01T14:02:51.220Z
@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).
Martin Berger
CC BY-SA 3.0
2013-02-01T15:54:23.413Z
@MartinBerger Good point, I'll update the question accordingly. I could ask both questions, but will restrict it to the undelimited call/cc and whether it can _implement_ any known control flow structure and try that.
csl
<lambda-calculus><denotational-semantics><scheme><operational-semantics>
Can Scheme's call/cc implement all known control flow structures?
csl
# Can Scheme's call/cc implement all known control flow structures?

(Asked by: username_0 on 2013-01-31)

The page ["Advanced Scheme: Some Naughty Bits"](http://people.csail.mit.edu/jhbrown/scheme/) 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](https://en.wikipedia.org/wiki/Control_flow) 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](http://www.cs.indiana.edu/l/www/ftp/techreports/TR205.pdf) (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](http://okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim), 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.

**Tags:** lambda-calculus, denotational-semantics, scheme, operational-semantics
> **Comments:**
> **username_1**: What is the formal definition of a "control flow structure"?  
> **username_2**: 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`.)  
> **username_0**: @Rici: I only skimmed the first few pages. (Reading papers takes me a *long* time). Thanks for the comment!  
> **username_0**: @HuckBennett I don't have a formal definition, but informally I mean what it described at https://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.  
> **username_3**: @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).  
> **username_0**: @MartinBerger Good point, I'll update the question accordingly. I could ask both questions, but will restrict it to the undelimited call/cc and whether it can _implement_ any known control flow structure and try that.  

---

## 1 answers

### Answer by username_4 on 2013-02-04. Score: 12 | Accepted answer

In this answer, I'll take "expressible" to mean "macro-expressible" in the sense of Felleisen 1991, [*On The Expressive Power of Programming Languages*](http://www.ccs.neu.edu/racket/pubs/scp91-felleisen.ps.gz). (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](http://www.diku.dk/hjemmesider/ansatte/andrzej/papers/CE.ps.gz), [Andrzej Filinski](http://www.diku.dk/~andrzej/) 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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.9582) 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](http://homepages.inf.ed.ac.uk/slindley/papers/handlers.pdf) 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.

> **Comments:**
> **username_0**: 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 http://lambda-the-ultimate.org/node/966 it seems that Oleg Kiselyouv implemented all four F-operators in Scheme with call/cc: http://okmij.org/ftp/continuations/implementations.html#generic-control -- 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".  
> **username_0**: 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.  
> **username_0**: I'm going to accept this answer.  I'd also like to point to the text at http://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."  

---

