Lambda the Ultimate

Two points about implementing delimited control in terms of call/cc:

1) You need a way to determine if a continuation is empty, so delimited control can be made properly tail-recursive. See A Monadic Framework, section 5.2.

2) All your code that uses delimited control now needs be called inside a wrapper function that establishes necessary structures. This means that e.g. loading a file has to happen inside this wrapper, as does REPL evaluation.

For the second reason, I've decided to implement delimited control natively in my current language.

As I understood the post, it's not saying that continuations are bad, just that delimited continuations are better than call/cc because:

• They are just as easy to implement
• They are cleaner and more expressive
• The implementation of the common things that can be built on top of continuations is far cleaner with delimited continuations (exceptions, non-determinism, etc.)
• Implementing delimited continuations on top of call/cc + set! is awkward and slow, and may leak memory

Personally I find them easier to understand as well, but YMMV.

Actually read Oleg's post.

If you then later say that a language really only needs some of these other more specialized constructs that can built with call/cc [...]

The point is that you actually can't, because call/cc is a leaky abstraction.

Make it optional.

This is the choice that Racket made, and it took a lot of work to figure out the "right" way to make different control operators work together (see this thread). In the end, they still don't have a real call/cc since it respects prompts. The reason it's still there is to still have some reasonable behavior on ported Scheme code, and to provide continuations that don't build up prompts unnecessarily (though I don't know how often that problem crops up). [edited from "hurt immensely" following a discussion with samth]

Call/cc has still helped you compactly and usefully explain all the things you actually want to require in the implementation. All those more practical control concepts conceptually reduce to uses of call/cc.

Source? Oleg refutes this convincingly.

Now suppose that you have a kind of practical but "naive" scheme implementation. [...] Now in that implementation, call/cc in all its horrifying glory is (relative to the other parts of the implementation) cheap and blazingly fast

Relatively fast, where you're relating with a target slower than molasses. Again impractical.

For example, you write:

The point is that you actually can't, because call/cc is a leaky abstraction.

My understanding was that non-leaky implementations of reset/shift in terms of call/cc had been demonstrated. Isn't that what you mean?

My understanding was that non-leaky implementations of reset/shift in terms of call/cc had been demonstrated.

Yes, under very specific conditions which are not met by any Scheme implementation.

Yes, under very specific conditions which are not met by any Scheme implementation.

Wasn't there, for example, an indirect space-safe implementation in Scheme 48? But this is getting silly. Here is what caught my attention in Oleg's paper:

Implementing control features in terms of call/cc has inherently poor performance. The operator call/cc captures so-called multi-shot, escaping continuations, letting us return several times from a single procedure call. Such generality costs performance but is rarely needed. For example, exceptions do not require any continuation capture, let alone multi-shot one. It is much easier and quite more efficient to implement them as primitive, rather than to emulate in terms of control operators. Even R7RS Scheme now specifies a dedicated exception-handling facility; previously, portable Scheme programs were supposed to rely on call/cc. By the same token, simple generators such as those in CLU and Python are realizable on linear stack with standard function calls and need no continuation capture either. They too make sense to implement natively rather than emulate through more powerful and expensive control operators. Using call/cc for threads and coroutines has an unacceptable cost due to dynamic-wind, as described further below.

It has been frequently observed that in most all cases a captured continuation is invoked at most once. Dybvig et al. and Feeley showed that one-shot continuations are much more efficient to implement. The sole, it seems, use case for multi-shot continuations is non-determinism. A better abstractions for non-determinism, such as generators, have long been known in Icon and Scheme predecessors.

Experience shows that call/cc makes a poor trade-off between generality and performance. Implementing exceptions and all other control facilities as library functions in terms of call/cc turns out a bad idea.

For decades people have built and successfully used versions of those other constructs on top of call/cc.

I don't dispute that this is often slow or that a high performance implementation would want to seek another basis.

I do dispute that it "turns out [to be] a bad idea". Taking "call/cc" as core is a bad idea for some applications, a perfectly fine idea for others.

I think part of the socio-economic problem, so to speak, is that there is an imperative built-in to the rNrs process. The imperative is to identify a unique core language in terms of which the rest of Scheme is specified. So there is natural contention for membership in that core. So arguments arise like whether or not call/cc should be removed and some delimited continuation primitives take its place.

The preciousness of that imperative is captured and perhaps created by the famous Clinger quote about not piling on features. It is as if from the moment that was penned, rNrs became a contest to perfect "core scheme", the ultimate, final tiny language from whence all else can be derived.

In real life, historically, and for decades, the Scheme specification is honoured more in its breach than in its faithful execution. Quite common are dialects that implement "most of" some rXrs, well enough to run various SRFIs of interest or to support this or that programming style of interest. (Formerly, "well enough to run most of SLIB"). Scheme manifests as a family of dialects, many of which approximate ad hoc subsets of an idealized full language. Good!

Scheme understood that way doesn't need or much benefit from having an official "core" because in practice it is a family of subsets of some ideal language. The ideal "core" depends on just what particular subset we're talking about.

That's why I suggested specifying but not requiring call/cc. If your dialect only needs a few basic things and a graph interpreter is plenty fast enough, call/cc can be a useful "core" primitive. If your dialect is sufficiently fancy, on the other hand, you might not even want to support call/cc in any serious way. It's handy to have an explanation for call/cc and to be able to explain some other constructs, in some contexts, in terms of call/cc. It's important to not require (a serious version of) call/cc.

Where's the problem? Specify but don't require it. Why is that controversial?

It comes down to the Plotkin ideology that calculi should correspond to programming languages. A semantics should not only give extensional meaning to programs but also give insight on what it means to compute. If you define everything interesting in terms of the "hand of god" operator, you get religious dogma and not a useful blueprint.

"hand of god" operator?

I'm sure I have no idea what you mean.

call/cc is so heavy-fisted that you might think it the hand of god. It also makes an otherwise intuitionistic logic classical, meaning there is now (in one interpretation) a "function that decides everything," which Bob Constable calls magic, others an oracle and yet others appealing to god. Perhaps I was a bit too clever.

call/cc is so heavy-fisted that you might think it the hand of god. It also makes an otherwise intuitionistic logic classical, meaning there is now (in one interpretation) a "function that decides everything," which Bob Constable calls magic, others an oracle and yet others appealing to god.

Or... it's the operation of consing up a few key registers and tagging them as a kind of procedure.

It's a heavy-fisted "hand of God" operator, *and* it's possible in some systems (eg, those that keep stack frames on the heap) to do it with a very fast, simple operation.

The point he was making is that it's got "hand of God" semantics, regardless of how simple or easy the implementation might be.

Ray

Oleg wrote:

We argue against call/cc as a core language feature, as the distinguished control operation to implement natively relegating all others to libraries.

The tradition in Scheme standards has been to specify a "core" language with additional "library" procedures and syntax. So, what is "core Scheme"? I understand the intended significance of this core to be three-fold:

1) Definitional: The specification of the core is supposed to be an economic expository foundation upon which the greater language can be explained. If something is marked traditionally as a "library" procedure, for example, we expect that to mean that the specification for the procedure could understandably be expressed as a program written in purely "core" Scheme.

2) Instructional: Historically, the Scheme core is small but not minimal. In part that's because of its instructional role. The core is supposed to convey the conceptual essence of Scheme in practice, not just some idealized mathematical essence.

3) Implementation Guiding: Historically, the expectation is that if the core is well implemented, then all the rest of Scheme can in fact be supplied in the form of libraries that are portable to any good implementation of the core. A stronger form of this expectation also lurks: that perhaps the core could be so good that implementations would nearly never need to provide anything but the core, leaving the rest to portable libraries.

Oleg writes that he offers arguments against call/cc as a core feature, one "to implement natively relegating [various other control constructs] to libraries". I understand him to be speaking in the framework of that three-part view of "core Scheme". He is, so to speak, arguing about which direction to move to search for the Ultimate core language.

Because that traditional view of "core Scheme" looks for a kind of platonic ideal, Oleg has to make absolute statements that are not quite true, like:

The only reward for the hard work to capture the whole continuation efficiently is more hard work to get around the capture of the whole continuation.

Actually, the trade-offs depend quite a bit on the implementation techniques and goals. Sometimes a native call/cc is quick, easy, and perfectly practical -- better than any alternative.

We can reconcile all this and understand Oleg's points in a more productive way, I think, if we alter the traditional "core scheme" framework. There is no ideal core that scores on all the three points (definitional, instructional, and implementation guiding). There is not even any reason to believe in principle that any such core could exist.

If we abandon the traditional pursuit of a chemeric Ultimate core then it's perfectly sensible to (a) say something like "it's handy to specify but not require call/cc" and (b) Oleg's note is a list of reasons to sometimes avoid call/cc.

(As an aside, Ray, I'm not familiar with terms of art like "hand of God semantics".)

The "Hand of God" reference is part of a very different intellectual tradition. A few centuries ago, when (Christian) religious intellectuals, in a world as yet largely unexplained by science and uninfluenced by scientists, were trying to explain the physical world as an artifice or creation of God for the purpose of mankind's moral instruction, they were occasionally presented with questions relating to things so fundamental or pervasive that their moral relevance, or the possibility of alternatives, was not readily apparent. To such things they could only respond, "So it was made by the Hand of God."

The context or "moral lesson," they went on to explain, was that God sometimes does things or makes things a certain way for reasons we don't necessarily understand, that this is to be expected because God's wisdom is perfect and ours is not, and it is therefore the moral duty of a good Christian to accept the (perfect, whether we know it or not) decisions and creations of the Supreme Being, even when we don't understand them and may actively dislike their results, thankfully and with good grace. Or, as we would say in the modern era, the good men of the cloth were adroitly ducking the question by making a moral lesson of the fact that nobody knew the answers.

Over time this singularly unhelpful response became the Canonical answer to a larger and larger body of requests for enlightenment, and over time a non-religious intellectualism emerged comprised of people who were more and more unsatisfied with that answer, and particularly with its repetition or excessive applicability.

When someone refers to the "Hand of God" in a scientific context, it usually refers to that old argument. It expresses frustration or dissatisfaction with a single explanation that tries to explain too much, can't be reasonably examined or disproved, or is formulated primarily for its effectiveness in shutting the questioners up rather than to provide them with useful information.

BTW, I have living relatives, whom I respect deeply, who have taken this difficult lesson to heart and have trained themselves to be satisfied with it. They have both a monastic stoicism and an inner peace that I, as an "outlander" to them and their religious tradition, find to be unattainable and almost surreal. So I'm in the odd position of having seen both sides of this argument, or at least understanding and having empathy for the way the mindset it advocates works.

Hope that helps,

Ray

1. Isn't any form of lazy evaluation leaky, since resources are held until the value is effectively used (if ever)?

I don't know whatever gave you that idea, and the question seems nonsensical to me. From a 'lazy' perspective, strict evaluation might be called leaky since sometimes you tediously need to program around holding all resources until a value is demanded. It's just a reduction order, both reduction orders 'leak' their timed behavior.

I really don't understand call-cc like Oleg does so I wouldn't know about the other question. Then again, it wouldn't surprise me if there are less than five people in the world who really understand call-cc.

I think I was not clear.

Oleg makes the point that call/cc is leaky because the whole program needs to be there and ready to be resumed as long as you have a continuation in scope (if I understand right).

My question is, isn't this true to a certain extent for any lazy evaluation since you need a closure to maintain the "live" state of the program until the value is needed, at which point it can be freed? For memory resources this is not a big deal but it can matter if there are I/O resources involved. I suppose this is not a problem in Haskell because I/O lives in the monad world, isn't it?

AFAIK, monadic IO doesn't enforce a strict order of evaluation even when you think you sequentially chained IO; there is only lazy reduction on a demanded value, so problems with lazy IO are probably independent of whether you approach a problem monadically.

My question is whether you'ld call that 'leaky'. As stated, in a strict language you also need to program around timed behavior of evaluation, it's just that strict evaluation is much simpler and better ingrained into people's mind that it isn't seen as 'leaky'.

So much more basic answers.

Call-cc leaks memory. As I said, I don't understand call-cc, but extrapolating from what I implemented: Leaking memory can probably be avoided, and is probably due to that the program stated which is stored between different call-cc invocations needs to be copied. My bet: There isn't enough sharing, on a stack machine, between different program states. I think it can be made lightweight, but only if program states live in the heap, and can be seen as a collection of linked states.

Then, again, the lazy evaluation question. No.

Lazy evaluation is a reduction order. Strict evaluation is also a reduction order. The only, but real, benefit of lazy evaluation is that it is normalizing. You can make examples which blow up under strict evaluation and not under lazy evaluation (print a list of the first five hundred Fibonacci numbers), and the converse (lots of list insertions or concatenations). Except for the normalizing, or implied expressiveness, part, both reduction orders have similar merits and pitfalls.

Then, again, the lazy evaluation question. No.
Lazy evaluation is a reduction order. Strict evaluation is also a reduction order. The only, but real, benefit of lazy evaluation is that it is normalizing. You can make examples which blow up under strict evaluation and not under lazy evaluation (print a list of the first five hundred Fibonacci numbers), and the converse (lots of list insertions or concatenations). Except for the normalizing, or implied expressiveness, part, both reduction orders have similar merits and pitfalls.

Thanks. That is interesting.

In the example with lots of concatenations, there is a large amount of input (say strings) which reduce into a single result. You could imagine a structure which reflects both the operations to do (string concatenation) and the final result (list of strings as a string). But there are cases where only a small part of the input is used, even if there is a lot of input needed to get a result. Even worse, the input may require access to resources which must be prebooked (with locks or others) at a time where the program has appropriate privileges, to only be used - and released - at a later stage.

This is where I see a parallel with the "leakage" issue in call/cc, made manifest with dynamic-wind.

Are resumable exceptions akin to refirable continuations? If they are,
what makes them better than call/cc in terms of practicality,
performance and safety?

Resumable exceptions have finite extent (finite lifetime): an
exception cannot be resumed after its handler has exited. In
contrast, a continuation captured within a function has an indefinite
extent, and can be invoked well after the function has exited. That's
why call/cc-captured continuations are sometimes called `escaping
continuations'. One may say that the difference between resumable
exceptions and captured continuations is akin to the difference
between stack-allocated values and heap-allocated ones.

Resumable exceptions are also very easy to implement: raising a
resumable exception is just an ordinary function call (where the
function to invoke, the handler, is determined from the dynamic
environment). Lisp has no call/cc but it has had resumable exceptions
for a very long time (which are used frequently and turned out a great
feature).

Yes. Is "escaping" the difference between a delimited and a full continuation?

I am interested in the subject because I am using continuation-passing style of calling convention in dodo. The language has to take explicit steps to prevent a call/cc, I devised these ones at the moment:

1- A continuation cannot take another continuation as argument
2- An exception to -1- is for generators, which pass a continuation to the return continuation
3- A generator cannot capture a non-local continuation (by non-local I mean outside the scope which introduces the return continuation)
4- The return continuation invoked by a generator is always fresh, which means it cannot be called twice

There is still the problem of cleaning up the resources held by the generator, like heap space, eventual file handles etc. I do not see a way to solve it except by doing a special invocation of the generator before it goes out of scope (like automatic resource management in C++, Java...)

It is indeed true that lazy evaluation makes it quite a challenge to
analyze the space behavior of a program. Memory leaks are quite
possible. Fortunately GHC has become quite good at strictness
analysis: it figures out if a value will be needed and if so, computes
it eagerly. Sometimes however, we do have to give a strictness
annotation (in the form of a bang pattern or seq). In my experience,
if program runs out of memory, the most common culprit is an
arithmetical expression (since an integer takes less space than a
closure to compute it).

There are cases where leaks become show-stoppers. The following
article documents one such case and a difficult work-around:

http://okmij.org/ftp/Haskell/misc.html#memo-off

When resources other than memory are involved (so-called `lazy IO'),
leaks are quite common and are very well-known. Please see the
overview in Sec 2 of the paper

http://okmij.org/ftp/Haskell/Iteratee/describe.pdf

(The paper also shows an example when a small change in a Lazy IO program changes the O(1)-space behavior to O(n) -- forcing loading of the whole file in memory. This is indeed a big problem in practice.)

Ah, memory leak, not leaky abstraction. I was thinking about 'leaky' lazy evalution. As in, what's the difference between these two programs:

main = do inFile <- openFile "foo" ReadMode
          contents <- hGetContents inFile
          putStr contents
          hClose inFile

Prints the contents of the file.

main = do inFile <- openFile "foo" ReadMode
          contents <- hGetContents inFile
          hClose inFile
          putStr contents

Prints nothing.

Moreover, with this:

Fortunately GHC has become quite good at strictness
analysis: it figures out if a value will be needed and if so, computes
it eagerly.

I think you can probably exploit the strictness analysis to switch between these two behaviors, though I wouldn't know exactly how at the moment.

Whatever, my point in the other post is: I don't think monadic IO solves the inherent problem around evaluation order 'leaking' into the pure semantics of the two programs. Personally, I would expect only that defaulting back to (timed) stream processing functions would solve the problem of this 'leaking' behavior, since (only) with stream processing functions the output is fully defined, or specified, given some input.

But that would only fix a somewhat academic problem at best, 'fail' in a context of concurrent evaluation, and -in general- not be worth it.

I agree with your greater point about not making call/cc a primitive but non-termination should not be modeled as an effect in a general purpose programming language. It should be modeled as an error that you might not be able to prove isn't there. Modeling it as an error is fine: programs that run forever between generating effects are not ever what was intended. Modeling it with effects is going to force a bunch of functions that ought to terminate (based on informal reasoning) into a different semantic class for no good reason.

Tim, I'm sure you've come across this material in your research, and I'd appreciate hearing your thoughts on Griffin's A Formulae-as-Types Notion of Control and the follow-up work on Krivine realizability if you can spare a moment to discuss it. I guess what I'm driving at is that call/cc is now known to have (classical) logical content, and can be seen as enabling considerably more than multiple-return, but I don't really know if that observation actually implies more than what you already said. Does it make sense to talk about a functional/logic language, say, in the spirit of Mercury, but based on Krivine realizability instead of Curry-Howard? Even if it makes conceptual sense, would there be any practical benefit you can see?

I'm also curious about your thoughts regarding Disciple and Eff, while I'm bending your virtual ear. :-)

You can regard call/cc as effectful, and use effects-typing to limit
the scopes where it is allowed, and hence allow greater optimization
of code where it is guaranteed not to occur.

Effect typing is indeed a good idea in general. In fact, for delimited
continuations (shift/reset rather than call/cc), Scala has used effect
typing to great success, to see which expressions have to be
CPS-converted. Assuredly pure expressions can be compiled as usual;
only the expressions that may really use delimited control suffer the
CPS conversion penalty.

As for call/cc: adding it to a simple functional language (even with
fix) does not give much expressiveness. We can't even get exceptions
(try/raise), let alone generators or non-determinism. We have to add
state. The problems of that approach have been described already. Let
me add one more. As I said, the effect system for shift/reset is
relatively simple -- and helpful, for compilers and programmers. In
that effect system, reset e is a always a pure expression
regardless of the purity of e. In the familiar
implementation of shift/reset via call/cc, the implementation of reset
involves both call/cc and the state. It is not straightforward to
deduce that this combination of effects somehow should produce a pure
expression. So, the effect system for shift/reset does not look like a
simple `instantiation' of the effect system for call/cc. As I argue,
call/cc is just not a good abstraction.

As to Haskell's Continuation monad, I should stress that it is a monad
for delimited continuations. One has to work hard to get
undelimited continuations.

http://okmij.org/ftp/continuations/undelimited.html#proper-contM

Although Haskell's continuation monad has the operation callCC, it
works very differently from Scheme's call/cc. The name clash is
unfortunate.

Doesn't the effect typing lose the advantage of first class delimited continuations that you can use them in places where it was not specifically arranged for? For example if you have a nondeterminism abstraction built on delimited continuations, can you still do this?

powerset(xs) = nondet { xs.filter{x => amb(true,false)} }

Effectively you have to duplicate a lot of the standard library just like in Haskell filter vs filterM?

If a function, say, filter, was written under the assumption that its first argument (the predicate) is pure, then you really can't use this filter with any effectful predicate, regardless of the effect typing.

That's not really true. For example, if the effect is to access a cached value (computing it only if it's missing) or if the effect is just logging then it's reasonable to use a pure filter with an effectful pred. The main obstruction to doing this safely is that the filter function may not cache calls to pred. i.e. filter could call 'pred x' in two places with the same 'x' and expect them to give the same result.

Never doubt the wisdom of Oleg. ;-)

Come on. Of course there are side effecting functions which are, in some sense, 'pure' in their return value. And, of course, in an elaborate language setting one would override the type of such functions as being 'pure', this is really well known.

Oleg's reasoning is sound.

First, let me say that I have plenty of respect for Oleg and am a fan of some of his work, but this is an area I've been through recently in the context of my Processes and I stand by the point I was making.

Whether or not it's a well known hack, just labeling certain functions as "pretend this is pure" is not a good solution. The problem is that while you may occasionally want to ignore certain effects in a certain context, you almost never want to ignore them in every context. The function you get back from filter needs to be labeled as 'uses logging'.

The core point I'm making is that for purposes of establishing correctness of your code, purity of the functions you call is never a required assumption. You can always make due with the assumption that calls you make will not affect the abstract state governing the results returned from the other effectful calls you make.

Thing is, when I was a student they introduced me to a language which made a distinction between side effect free and side effecting constructs. In hindsight, I think it was more a 'courtesy' extension of the base language given by the then raging debate between the superiority of functional programming languages versus imperative Pascal like languages, than a feature the compiler could exploit. (OO was just invented and not widely adopted at that time.)

The thing I took from that was that pragmatically people couldn't be bothered too much with making the distinction, and a lot of side effecting functions were, for various reasons like your examples, coercifully declared as being side effect free.

From a compiler perspective this opens a can of worms. In order to exploit purity, the coercion from 'dirty' to pure should somehow really cleanly wash the dirty construct. And I wouldn't know how to do the latter. (Compare it to needing a Haskell like UnsafePerformIO which makes sure that a number of invariants concerning the resulting purity are maintained. Academically, I find that a pretty interesting question though, nice for a PhD to solve.)

Conclusion: Making a distinction between side effecting and pure functions doesn't add too much, at least not from the perspective of a programmer. Moreover, in order for the compiler to use the fact that some functions are pure, the manner in which you coerce effectfull routines to pure routines starts to matter.

From that experience, I would say that making the distinction isn't worth it.

But this was before multicore processors, purity can be exploited much more these days than before. But then still it would be a feature which would only make sense to be exploited in very mature compilers. I.e., Haskell and Ocaml could exploit it to optimize another 5% running time away. Most languages are that slow that it doesn't make sense to support it from a programmer's or compiler's perspective.

Sometimes purity isn't just usable for optimizations. Sometimes it's necessary for correctness.

The semantic difference between 'assert foo()' and 'if (not foo()) halt' is that whether foo() even gets called depends on the build configuration. Assert depends for correctness on the property of purity, in that omitting the test must not affect the behavior of the program. Therefore if foo() isn't pure with respect to the rest of our program, the assert form is an error in that the behavior of the testing build is not the behavior of the release build.

So, short version? Yes, it would be very much worth it to be able to check for sure that a call to a function returning a value can be omitted when we don't need that value, and that the omission will have no effect on the subsequent behavior of the program.

Ray