shap@delrey.sgi.com (Jonathan Shapiro) (11/28/89)
I do not believe that it is feasible to add continuations to C++ for
any number of reasons, but I would be interested to hear the reactions
in this community regarding their utility in object-oriented programming.
For those of you who are not already conversant with continuations,
the idea comes from Scheme (though it has earlier antecedents), and
looks like this:
(call-with-current-continuation
(lambda (continuation)
(body...)))
the call-with-current-continuation form potentially returns multiple
times, because the continuation can be saved to a global variable. A
subsequent invocation can be done with:
(continuation value-producing-form)
which causes a return from the call-with-current-continuation with
that value.
Logically, the continuation captures the future state of the program
at the point at which it was captured. That is, it captures a pc, a
set of registers, and a stack. Note that this implies garbage
collection of stack frames, because a live frame in an enclosing
context can be shared between a continuation and subsequent code.
Continuations have seen use as error handlers, because they look like
function invocations. One can set up an exception handling routine,
capture it with a continuation, and use the continuation as a
"longjump" type mechanism to get out of a bad state.
Continuations are different from longjump in that they capture the
stack as well as the registers.
A detailed description can be found in the Revised Revised... Report
on scheme, which can be obtained via anonymous FTP from
zurich.ai.mit.edu.
Jonathan Shapiro
Silicon Graphics, Inc.davidm@uunet.UU.NET (David S. Masterson) (11/28/89)
In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes:
I do not believe that it is feasible to add continuations to C++ for
any number of reasons, but I would be interested to hear the reactions
in this community regarding their utility in object-oriented programming.
Hmmm. Something in this caught my interest, but I'm not quite sure what.
Taking a purely object-oriented stab at it, might the idea of continuations be
implemented as merely messaging a static data area? Is there more to it?
--
===================================================================
David Masterson Consilium, Inc.
uunet!cimshop!davidm Mt. View, CA 94043
===================================================================
"If someone thinks they know what I said, then I didn't say it!"dlw@odi.com (Dan Weinreb) (11/29/89)
In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes:
I do not believe that it is feasible to add continuations to C++ for
any number of reasons, but I would be interested to hear the reactions
in this community regarding their utility in object-oriented programming.
They are just as useful in object-oriented programming as in straight
Lisp or Scheme. However, continuations in the Scheme style are only
useful if full support is provided for lexical scoping. C and C++
have no lexical scoping whatsoever. So I agree that it is not
feasible to add them to C++. Even lexical scoping alone, with or
without continuations, would be a great benefit, but I'm sure I'll
never see it in C or C++.peterd@cs.washington.edu (Peter C. Damron) (11/29/89)
In article <1989Nov28.183816.15252@odi.com> dlw@odi.com writes: >In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: > > I do not believe that it is feasible to add continuations to C++ for > any number of reasons, but I would be interested to hear the reactions > in this community regarding their utility in object-oriented programming. > >They are just as useful in object-oriented programming as in straight >Lisp or Scheme. How can you make this claim? >However, continuations in the Scheme style are only >useful if full support is provided for lexical scoping. C and C++ >have no lexical scoping whatsoever. I just had to reply when I saw this. C and C++ are definitely "lexically scoped" (I would prefer to call it statically scoped). Peter. --------------- Peter C. Damron Dept. of Computer Science, FR-35 University of Washington Seattle, WA 98195 peterd@cs.washington.edu {ucbvax,decvax,etc.}!uw-beaver!uw-june!peterd
gateley@m2.csc.ti.com (John Gateley) (11/29/89)
In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: >I do not believe that it is feasible to add continuations to C++ for >any number of reasons, but I would be interested to hear the reactions >in this community regarding their utility in object-oriented programming. I don't see why it would not be feasible, C++ has for loops and other control structures, why not continuations as well? As for object oriented continuations: A continuation is a technique for modelling/creating flow of control. In pure object oriented systems, this is done by message passing. Thus, a OO continuation would probably be something which modelled a process: like a coroutine object, which you send messages to (like resume). This is a half baked idea, but maybe worthwhile. John gateley@m2.csc.ti.com
grover%brahmand@Sun.COM (Vinod Grover) (11/29/89)
In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: >I do not believe that it is feasible to add continuations to C++ for >any number of reasons, but I would be interested to hear the reactions >in this community regarding their utility in object-oriented programming. > I do not know if you are talking about first-class continuations or not, but in languages which are stack-based first-class continuations are not trivial to add. (By stack-based I mean that the procedure entry exit sequance behaves in a stack-like fashion) In C the idea of setjmp/longjump comes as close to continuations as one can get. Admittedly, this is not as elegant as Scheme's notion of continuation but workable in concept. > >Jonathan Shapiro >Silicon Graphics, Inc. Vinod Grover Sun Microsystems.
shap@delrey.sgi.com (Jonathan Shapiro) (11/29/89)
In article <CIMSHOP!DAVIDM.89Nov27231415@uunet.UU.NET> cimshop!davidm@uunet.UU.NET (David S. Masterson) writes: >In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: > > I do not believe that it is feasible to add continuations to C++ for > any number of reasons, but I would be interested to hear the reactions > in this community regarding their utility in object-oriented programming. > >Hmmm. Something in this caught my interest, but I'm not quite sure what. >Taking a purely object-oriented stab at it, might the idea of continuations be >implemented as merely messaging a static data area? Is there more to it? >-- >David Masterson Consilium, Inc. >uunet!cimshop!davidm Mt. View, CA 94043 I don't believe so. What is interesting about continuations is that they freeze an execution context into an object whose internals are not exposed to the programmer, but which can be invoked at a later time and passed a single value which is the value to return. Since the object can be saved outside of the scope in which it was defined, the continuation can be returned from multiple times. The reason messaging a static data area isn't enough is that you need to preserve the stack, and portions of the stack can be shared between the captured continuation and the main program thread. As an example: (if (call-with-current-continuation (lambda (cont) (set! *saved-continuation* cont) #f)) (do-something-interesting)) When first run, the continuation is passed to the lambda, which saves it and returns #f, causing the IF to fail. At any later time, the user can say: (*saved-continuation* non-#f-value) and the body of the if will be run, along with any code that ran following the execution of the if the first time. One could therefore package up an error routine in a top level loop as shown above and then implement (define (recover-from error-type cause-info) (call-with-current-continuation (lambda (cont) (function-that-handles-error-type cont cause-info)))) (define (catch-math-error where-happened cause-description) (if (try-to-recover cause) (cont #t) (*saved-continuation-for-unrecoverable-math-error where-happened))) And then say in the code encountering the error: (if (recover-from 'math-error 'overflow) (continue-happily) (die-horribly)) Note that the "cont" can be invoked by any handler in the chain to get back to the *original* context, and that if any of these pass #t to the continuation, execution will continue appropriately. If some handler gives up and invokes the continuation with #f, we call DIE-HORRIBLY, and presumably exit. I don't know if that makes things clearer or not... Jonathan Shapiro Silicon Graphics, Inc.
plogan@mentor.com (Patrick Logan) (11/29/89)
Jonathan Shapiro (shap@delrey.sgi.com) is interested in the utility of
continuations in object-oriented programming.
My response is they have great utility. He mentioned an example of
defining an exception handling system using continuations. If you're
unfamiliar with continuations, consider another, unrelated example and
you may begin to realize the power of continuations.
ASIDE...
Before I continue with the example, I think it's important to point
out that continuations exist conceptually in any programming language
that provides sequential execution. For example C, Pascal, and C++
have sequential statements that can be described using the concept of
continuations. Even Prolog messes with sequential execution with the
concepts of backtracking and cut. The real *power* of continuations
comes with languages such as Scheme that provide continuations as
full-fledged objects in the language.
END OF ASIDE
My example of an object that uses continuations is a discrete event
simulator. Let's say your simulating (very simplistically**) a digital
electronic circuit. You could have an object representing a two-input
AND gate. This object has (among others) a method for setting the
value of an input. Here is some pseudo code describing that method:
When one of the input pins is assigned a new value perform...
(1) Assign the new value to the input pin.
(2) Notify the discrete event simulator that the next step
should execute two simulation time units from the current time.
This models the delay of the real AND gate.
(3) Assign to the output pin the result of AND'ing the input pins.
In a Scheme-based object system this might look like:
(define-method (set-input-pin! and-gate pin-number new-value)
;; Step #1.
(case pin-number
(1 (set! input-pin-one new-value))
(2 (set! input-pin-one new-value))
(else (error "Invalid pin number." pin-number)))
;; Step #2.
(simulator 'wait-for 2)
;; Step #3.
(self 'set-output-pin! (and input-pin-one input-pin-two)))
The wait-for message to the simulator object implements step #2 above and
uses continuations. The pseudo code may be:
When the wait-for message is sent perform...
(1) Capture the current continuation.
(2) Schedule it to be executed at the current time plus the value
sent in the message.
(3) Choose the next scheduled continuation.
(4) Set the current time to be the time of that continuation.
(5) Execute that continuation.
The Scheme-like code may be:
(define-method (wait-for simulator relative-time)
;; Step #1.
(call-with-current-continuation
(lambda (k)
;; Step #2.
(scheduler 'schedule k (+ (self 'current-time) relative-time))
(receive (next-scheduled-k new-time) ;; Bind these two names
(scheduler 'next) ;; to the two values returned by this message. Step #3.
(self 'set-time! new-time) ;; Then set the new time (Step #4.)
(next-scheduled-k #t) ;; and execute the continuation with a meaningless argument. Step #5.
So you can see that continuations are used to schedule future events
in a neat way. They allow control to be handed over to other events
that are scheduled to occur sooner. By embedding the capturing of
continuations in the simulator object, the details are abstracted so
that the description of the model is also very clean.
** This algorithm does not correspond to Mentor Graphics' products! 8)
--
Patrick Logan | ...!{decwrl,sequent,tessi}!mntgfx!plogan
Mentor Graphics Corporation | plogan@pdx.MENTOR.COM
Beaverton, Oregon |barmar@think.com (11/29/89)
In article <128489@sun.Eng.Sun.COM> grover@sun.UUCP (Vinod Grover) writes: >I do not know if you are talking about first-class continuations or not, but >in languages which are stack-based first-class continuations are not trivial >to add. (By stack-based I mean that the procedure entry exit sequance >behaves in a stack-like fashion) This is a circular argument. It's the very existence of first-class continuations in Scheme-like languages that causes them not to be stack-based. If Scheme didn't have continuations then it would be stack-based, according to your definition. Scheme is simply the result of adding continuations to Lisp. Of course, when you add them you have to redesign implementations to handle them properly. This means that you can't always use a linear stack to implement activation records -- you may have to allocate activations in the heap and garbage collect them. Upward closures also require similar support. First-class continuations are simply an extension of upward closures to include control information as well as variable bindings. Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
shap@delrey.sgi.com (Jonathan Shapiro) (11/30/89)
In article <31794@news.Think.COM> barmar@think.com writes: >... Scheme is simply the result of adding continuations to Lisp. >...Upward closures also require similar support. First-class continuations >are simply an extension of upward closures to include control information >as well as variable bindings. I think you got it right the second time. The major thing that Scheme offers is first-class closures (of which functions, continuations, and in some implementations, environments are examples). There are also some miscellaneous alterations, such as eliminating the namespace distinction between functions and variables, that are a consequence of making closures first class. Jon
max@Neon.Stanford.EDU (Max Hailperin) (11/30/89)
In article <1989Nov28.224937.4183@mentor.com> plogan@mentor.com (Patrick Logan) writes: > ... >My example of an object that uses continuations is a discrete event >simulator. > ... This is a superb example, but stops one step short of showing the real power of the idea. If all you are simulating is simple things like and gates, you can just code the simulator the way Abelson and Sussman do in their book, something like (simulator 'after-delay 2 (lambda () (self 'set-output-pin! (and input-pin-one input-pin-two)))) instead of (simulator 'wait-for 2) (self 'set-output-pin! (and input-pin-one input-pin-two)) The win in doing it the latter way (where simulator's wait-for uses call-with-current-continuation) comes if you are simulating something higher level. For example, I've been involved in some multiprocessor simulations where you want to just treat the processing elements as black boxes and simulate them by directly running the application code on the real machine that's doing the simulating, time how long it takes, and apply some scaling factor. *However*, whenever a remote reference happens, you want to trap back to the simulator, which will cause the right sequence of events to happen to simulate the network traffic, etc. Meanwhile, other processors may be doing their thing. Eventually, the event happens that corresponds to the memory contents from the remote reference arriving back at the processor, and you wnat to pick up where you left off -- which may be arbitrarily deeply nested in procedure calling. This can trivially be done by embedding a call-with-current-continuation in the remote-reference code, but otherwise is a real nightmare. I know--I've done it both ways. The key difference between the processor and the and-gate is that the point at which you want to delay may be buried deep in calls. This can happen in other, simpler situations as well, basically any time you have a notion of "interruption" in the normal, non-trivial, behavior of an entity. The fact that this comes up all the time in simulating bussiness organizations or what-not explains why Simula had coroutining (which is what first-class continuations are being used for in this example).
kend@tekchips.LABS.TEK.COM (Ken Dickey) (11/30/89)
In article <31794@news.Think.COM> barmar@think.com writes: >... It's the very existence of first-class >continuations in Scheme-like languages that causes them not to be >stack-based. ... [I saw this and could not help but respond... 8^] People interested in this discussion might want to look at R. Kent Dybvig's thesis "Three implementation models for Scheme", U of North Carolina at Chappel Hill, 1987. It describes heap and *stack* based scheme implementation techniques. Many (most?) compiled Scheme implementations do use (possibly segmented) stacks. A good discussion of implementation techniques can be found in "Implementation Strategies for Continuations" by Clinger, Hartheimer and Ost in the '88 ACM Lisp & FP Conference Proceedings. I guess the gist of the above is that you can use a stack strategy until a continuation is captured, at which time the used part of the stack is `captured', marked immutable, and may be shared. If indeed shared, then it must be copied to be reexecuted--otherwise it could not be reexecuted multiple times. How the capture occurs depends on your storage recycling (gc) strategy and may involve copying to the heap, playing with page tables, etc. There are some technical wrinkles, but stack strategies are certainly widely used. Some people now believe that stacks are no longer required (e.g. Appel, "Garbage Collection can be Faster than Stack Allocation", Information Processing Letters, v25 #4, 1987), but that is another question. -Ken Dickey kend@mrloog.WR.TEK.COM
dlw@odi.com (Dan Weinreb) (11/30/89)
In article <9964@june.cs.washington.edu> peterd@cs.washington.edu (Peter C. Damron) writes: In article <1989Nov28.183816.15252@odi.com> dlw@odi.com writes: >In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: > > I do not believe that it is feasible to add continuations to C++ for > any number of reasons, but I would be interested to hear the reactions > in this community regarding their utility in object-oriented programming. > >They are just as useful in object-oriented programming as in straight >Lisp or Scheme. How can you make this claim? Easy, I just press the keys, and... Seriously, I have used continuations in an object-oriented programming language (Lisp with Flavors), for years, as have several of my former colleagues. So I feel pretty qualified to claim that they're useful. Do you have any more specific rebuttal than amazement that I could even say such a thing? >However, continuations in the Scheme style are only >useful if full support is provided for lexical scoping. C and C++ >have no lexical scoping whatsoever. I just had to reply when I saw this. C and C++ are definitely "lexically scoped" (I would prefer to call it statically scoped). In a sense, C and C++ are lexically scoped, but only in a trivial sense, since there are no internal procedures and no block structure. So, you are technically right, and I should revise my statement to say that continuations are only useful if the continuation can reference variables of lexically enclosing blocks, and classic "continuation-passing style" in the Sussman and Steele sense requires further that they should be able to refer to such variables even if the enclosing block is no longer being executed (what is traditionally known in the Lisp/Scheme community as "supporting upward funargs"). Few languages support upward funargs; Common Lisp and Scheme are two that do. Many languages support downward funargs; Algol-60, Pascal, and PL/I come to mind. In C, you can pass a function around as an argument, but there is no "lexical link" allowing it to reference variables in its parent block; in fact, there are no parent blocks in C. (It can refer to static and extern, but that's not the same thing.) Dan Weinreb Object Design, Inc. dlw@odi.com
dlw@odi.com (Dan Weinreb) (11/30/89)
In article <99894@ti-csl.csc.ti.com> gateley@m2.csc.ti.com (John Gateley) writes:
I don't see why it would not be feasible, C++ has for loops and other
control structures, why not continuations as well?
It depends what you mean. It would certainly be possible to invent a
definition of a language that was like C, but also had the features
needed to do continuation-style programming. Then you'd have a
definition of a new programming language. However, if you're talking
about getting the ANSI X3J11 committee to incorporate such features
into their next draft standard, I think you'd have a lot of trouble,
since the changes would be large and would entail various tradeoffs.plogan@mentor.com (Patrick Logan) (11/30/89)
>>From: grover%brahmand@Sun.COM (Vinod Grover) >In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: >>I do not believe that it is feasible to add continuations to C++ for >>any number of reasons... > >I do not know if you are talking about first-class continuations or not, but >in languages which are stack-based first-class continuations are not trivial >to add. (By stack-based I mean that the procedure entry exit sequance >behaves in a stack-like fashion) In C the idea of setjmp/longjump comes as >close to continuations as one can get. Admittedly, this is not as elegant as >Scheme's notion of continuation but workable in concept. > >> >>Jonathan Shapiro >>Silicon Graphics, Inc. > >Vinod Grover >Sun Microsystems. To be more accurate, longjump is not workable in concept because a longjump can only be executed once per setjmp. A continuation in Scheme can be captured once and executed zero or more times. Things become more complicated when you start considering nested setjmps and longjumps. For example, in my last article, I gave an example of a discrete event simulator. There is no way on Earth to implement that with setjmp and longjump. Essentially, setjmp/longjump implement a subset of what first-class continuations implement. There is no way to implement first-class continuations in C/C++ without fundamentally changing the semantics of the language. At that point, you have to poke yourself in the eye with a sharp object and ask yourself why do that? Have fun. -- Patrick Logan | ...!{decwrl,sequent,tessi}!mntgfx!plogan Mentor Graphics Corporation | plogan@pdx.MENTOR.COM Beaverton, Oregon |
psrc@pegasus.ATT.COM (Paul S. R. Chisholm) (11/30/89)
In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: > I do not believe that it is feasible to add continuations to C++ for > any number of reasons . . . In article <99894@ti-csl.csc.ti.com>, gateley@m2.csc.ti.com (John Gateley) writes: > I don't see why it would not be feasible, C++ has for loops and other > control structures, why not continuations as well? >John, gateley@m2.csc.ti.com "For loops and other control structures" just require conditional branches. Continuations require something for subroutine calling more complicated than a simple stack. Remember, many C++ implementations generate C code. If C++ provides a feature that can't be implemented in C, that whole method (which has made it much easier and faster to get object-oriented programming methods into the hands of programmers) goes down the tubes. In article <128489@sun.Eng.Sun.COM> grover@sun.UUCP (Vinod Grover) writes: > I do not know if you are talking about first-class continuations or not, but > in languages which are stack-based first-class continuations are not trivial > to add. (By stack-based I mean that the procedure entry exit sequance > behaves in a stack-like fashion) In article <31794@news.Think.COM>, barmar@think.com writes: > This is a circular argument. It's the very existence of first-class > continuations in Scheme-like languages that causes them not to be > stack-based. >Barry Margolin, Thinking Machines Corp., barmar@think.com, >{uunet,harvard}!think!barmar So you're saying that C++ (and by implication, C) would have to abandon their simple stacks in order to have first-class continuations? Efficiency (that is, allowing for the straightforward implementation of translators that produce efficient code) is one of the goals of the C++ programming languages. Even with inline functions, a C++ program will have lots of subroutine calls. A simple stack helps minimize the overhead of those calls. BTW, C++ class iterators either return a magic pointer, which can be trivially convinced to reference the next element, or separate iterator classes, which set aside memory (conceptually, and *very* roughly) like separate stack frames. They're not as elegant as iterators in Icon, CLU, or Smalltalk. I realize that continuations are useful for a *lot* more things than iteration. (Having said all that, I've painted myself into a corner: AT&T's C++ 2.0 library includes "tasks", a set of classes for coroutines. The library reference manual tells how they're implemented, but I've never read that part. Does anyone know how well the same techniques could be applied to continuations, first-class or otherwise?) Paul S. R. Chisholm, AT&T Bell Laboratories att!pegasus!psrc, psrc@pegasus.att.com, AT&T Mail !psrchisholm I'm not speaking for the company, I'm just speaking my mind.
mjl@cs.rit.edu (11/30/89)
In article <1663@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: > >... What is interesting about continuations is that >they freeze an execution context into an object whose internals are >not exposed to the programmer, but which can be invoked at a later >time and passed a single value which is the value to return. Since >the object can be saved outside of the scope in which it was defined, >the continuation can be returned from multiple times. > >The reason messaging a static data area isn't enough is that you need >to preserve the stack, and portions of the stack can be shared between >the captured continuation and the main program thread. What is the essential difference between a continuation in Scheme and the classic notion of a coroutine? Coroutines have been around for years (Conway's paper describing them came out in the '60s), and can be found in Simula-67 (where they are used with the object metaphor to represent the semi-independent entities in a simulation). The "processes" of Modula-2 are also ccoroutines. There are several packages for C that implement "light weight processes", and these are essentially ccoroutines (I have one available if anyone is interested). Finally, Stroustrup has a tasking package for C++ which captures this concept. This is not to deny that Scheme may have a more elegant, general,and formal (and thus less ad-hoc) approach, but I think we have to be alert enough to recognize essential similarities buried under surface differences. Have I found such a similarity here? On a side note, aren't lexical scoping and continuations independent concepts? Why I couldn't define a consistent language with continuations where the meaning of a variable depends on the dynamic invocation sequence rather than static nesting? I might not want to *use* such a language (dynamic scoping makes it almost impossible to understand a module/function in isolation) but that's an engineering issue, not one of feasibility. Mike Lutz Mike Lutz Rochester Institute of Technology, Rochester NY UUCP: {rutgers,cornell}!rochester!rit!mjl INTERNET: mjlics@ultb.isc.rit.edu
barmar@think.com (12/01/89)
In article <1419@cs.rit.edu> mjl@prague.UUCP (Michael Lutz) writes: >What is the essential difference between a continuation in Scheme and >the classic notion of a coroutine? I think a coroutine can only have one saved state at a time. Whenever you invoke a coroutine you return from the operation that last exited the coroutine. With continuations you can snapshot the state any number of times, and return to any one of them. Coroutines also don't permit you to return to functions that have already performed a normal return. Continuations do. >On a side note, aren't lexical scoping and continuations independent >concepts? Why I couldn't define a consistent language with >continuations where the meaning of a variable depends on the dynamic >invocation sequence rather than static nesting? I might not want to >*use* such a language (dynamic scoping makes it almost impossible to >understand a module/function in isolation) but that's an engineering >issue, not one of feasibility. I think you're right. I believe that the relationship between lexical scoping and continuations is more philosophical than architectural. I.e., lexical scoping and continuations are two aspects of a larger idea about programming, and they work well together. Also, continuation-based programming can be confusing, and lexical scoping makes it easier to understand what is going on. You are right that dynamic scoping makes it hard to understand modules (I was taught that it violates "referential transparency"), and adding continuations would make it even harder. Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
barmar@think.com (12/01/89)
In article <4286@pegasus.ATT.COM> psrc@pegasus.ATT.COM (Paul S. R. Chisholm) writes: >Remember, many C++ implementations generate C code. If C++ provides a >feature that can't be implemented in C, that whole method (which has >made it much easier and faster to get object-oriented programming >methods into the hands of programmers) goes down the tubes. Anything can be implemented in C (it's Turing complete, or whatever the term is). The C code may not look like the corresponding C++ code, but who cares? There are Lisp compilers that generate C code, and they have no problem dealing with the fact that C doesn't have complex and infinite-precision numbers or a garbage collector. And on Symbolics Lisp Machines, the C compiler generates Lisp code. In both directions, there is no rule that similar concepts must be implemented using the corresponding features of each language; for instance, C++ activation records don't have to map directly to C activation records. >So you're saying that C++ (and by implication, C) would have to abandon >their simple stacks in order to have first-class continuations? > >Efficiency (that is, allowing for the straightforward implementation of >translators that produce efficient code) is one of the goals of the C++ >programming languages. Even with inline functions, a C++ program will >have lots of subroutine calls. A simple stack helps minimize the >overhead of those calls. It's a common fallacy that continuations impose excessive overhead. First of all, the overhead is generally only imposed when continuations are actually used. A program that obeys pure stack discipline should not be affected. Only when the compiler sees that a continuation is being used might it have to generate extra code to deal with it. Other people have pointed out the literature on "segmented stacks", which are alternatives to heap-allocated activation records. I'm not extremely familiar with Scheme implementation, but implementors I've talked to have convinced me that the availability of continuations doesn't prevent efficiency. Many of the languages that provide continuations and/or upward closures also provide a garbage-collected heap, so heap-allocation of activation records (when necessary) is the simplest, and hence frequently initial, technique used by implementors of such languages; such implementations should not be used as a benchmark to indict continuations in general. Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
peter@ficc.uu.net (Peter da Silva) (12/01/89)
In article <1989Nov29.230331.19595@odi.com> dlw@odi.com writes: > It depends what you mean. It would certainly be possible to invent a > definition of a language that was like C, but also had the features > needed to do continuation-style programming. There is. It's called C. Almost. Seriously. All you need to do is have a bit of unportable code that mucks around in struct jmp_buf. Save the stack between here and there, do a setjmp to mark the end of the current stack, and then longjmp back to the saved spot. To continue, restore the saved stack and longjmp back to the mark. It would be advisable to write this code in assembly language :->. This would also give you the ability to add coroutines, threads, and all sorts of other good stuff. Let's call it ++C. -- `-_-' Peter da Silva <peter@ficc.uu.net> <peter@sugar.lonestar.org>. 'U` -------------- +1 713 274 5180. "The basic notion underlying USENET is the flame." -- Chuq Von Rospach, chuq@Apple.COM
peterd@cs.washington.edu (Peter C. Damron) (12/01/89)
In article <1989Nov29.225826.19483@odi.com> dlw@odi.com writes: >In article <9964@june.cs.washington.edu> peterd@cs.washington.edu (Peter C. Damron) writes: >>In article <1989Nov28.183816.15252@odi.com> dlw@odi.com writes: >>>In article <1623@odin.SGI.COM> shap@delrey.sgi.com (Jonathan Shapiro) writes: >>>>I do not believe that it is feasible to add continuations to C++ for >>>>any number of reasons, but I would be interested to hear the reactions >>>>in this community regarding their utility in object-oriented programming. >>> >>>They are just as useful in object-oriented programming as in straight >>>Lisp or Scheme. >> >>How can you make this claim? >Easy, I just press the keys, and... Seriously, I have used >continuations in an object-oriented programming language (Lisp with >Flavors), for years, as have several of my former colleagues. So I >feel pretty qualified to claim that they're useful. Do you have any >more specific rebuttal than amazement that I could even say such a >thing? The problem I have with including continuations into an object oriented language is a philisophical one. Objects should be self-contained and hide information. All interactions with objects should be through the well defined methods of the object. Now, if you add continuations, there is the potential to pass the continuation outside of the object, thus creating another entry point into the object that is not a member function. I see this as an information hiding problem for continuations in OO languages. Perhaps you can relate why this is not a problem in CLOS. >>>However, continuations in the Scheme style are only >>>useful if full support is provided for lexical scoping. C and C++ >>>have no lexical scoping whatsoever. >> >>I just had to reply when I saw this. C and C++ are definitely "lexically >>scoped" (I would prefer to call it statically scoped). >In a sense, C and C++ are lexically scoped, but only in a trivial >sense, since there are no internal procedures and no block structure. >So, you are technically right, and I should revise my statement to say >that continuations are only useful if the continuation can reference >variables of lexically enclosing blocks, and classic >"continuation-passing style" in the Sussman and Steele sense requires >further that they should be able to refer to such variables even if >the enclosing block is no longer being executed (what is traditionally >known in the Lisp/Scheme community as "supporting upward funargs"). >Few languages support upward funargs; Common Lisp and Scheme are two >that do. Many languages support downward funargs; Algol-60, Pascal, >and PL/I come to mind. In C, you can pass a function around as an >argument, but there is no "lexical link" allowing it to reference >variables in its parent block; in fact, there are no parent blocks in C. >(It can refer to static and extern, but that's not the same thing.) Let's get this straight. 1. Lexical (static) scoping is orthogonal to both continuations and first-class functions. C and C++ are fully lexically scoped langauges. Scoping has to do with naming -- which value does a name refer to. 2. C and C++ do not allow nested functions, but they do support block structure. Thus the lexical scoping is not "trivial". 3. Continuations are orthogonal to first-class functions (e.g. languages that allow both upward and downward funargs) and are orthogonal to block structure. It is not apparent to me that continuations are any less useful without block structure (though C and C++ have it anyway). It is also not apparent to me that continuations are any less useful without nested functions (though maybe more cumbersome). 4. C and C++ have first class functions. Functions can be passed as parameters, returned as function values, and assigned to variables. The reason that C and C++ do not allow nested functions is precisely so that they can have first-class functions implemented on a stack (e.g. no closure required). The "parent block" of a function is simply the global variables. Hope this helps to clear up any mis-understandings, Peter. --------------- Peter C. Damron Dept. of Computer Science, FR-35 University of Washington Seattle, WA 98195 peterd@cs.washington.edu {ucbvax,decvax,etc.}!uw-beaver!uw-june!peterd
chewy@apple.com (Paul Snively) (12/01/89)
In article <1419@cs.rit.edu> mjl@cs.rit.edu writes: > What is the essential difference between a continuation in Scheme and > the classic notion of a coroutine? Coroutines have been around for > years (Conway's paper describing them came out in the '60s), and can be > found in Simula-67 (where they are used with the object metaphor to > represent the semi-independent entities in a simulation). The > "processes" of Modula-2 are also ccoroutines. There are several > packages for C that implement "light weight processes", and these are > essentially ccoroutines (I have one available if anyone is > interested). Finally, Stroustrup has a tasking package for C++ which > captures this concept. > > This is not to deny that Scheme may have a more elegant, general,and > formal (and thus less ad-hoc) approach, but I think we have to be alert > enough to recognize essential similarities buried under surface > differences. Have I found such a similarity here? No, but you've come very close. It's trivially easy to implement coroutines using continuations, but they are not the same thing. Explaining why continuations are more general than coroutines is a tad tricky. George Springer and Dan Friedman have a new book out from The MIT Press, "Scheme and the Art of Programming," that devotes an entire chapter to continuations, and a section in that chapter to coroutines. I'd advise looking there for a reasonably full treatment of the subject. __________________________________________________________________________ Just because I work for Apple Computer, Inc. doesn't mean that they believe what I believe or vice-versa. __________________________________________________________________________ C++ -- The language in which only friends can access your private members. __________________________________________________________________________
jcg@iris.brown.edu (James Grandy) (12/01/89)
A question: if you fix up Smalltalk blocks so that their state is not stored with the creator method (that is, so that they are re-entrant, etc.), would they be classified as continuations? James Grandy (401) 862-1610 jcg@iris.brown.edu IRIS Brown University Box 1946, Providence, RI 02912
peter@ficc.uu.net (Peter da Silva) (12/01/89)
Another question: what distinguishes continuations from generators? -- `-_-' Peter da Silva <peter@ficc.uu.net> <peter@sugar.lonestar.org>. 'U` -------------- +1 713 274 5180. "The basic notion underlying USENET is the flame." -- Chuq Von Rospach, chuq@Apple.COM
ttwang@polyslo.CalPoly.EDU (Thomas Wang) (12/01/89)
My nitpick with continuations is that it does not fit the model of
object programming.
Continuations saves the function context to be able to continue the
function at a later time. The information is tied to the function
activation record.
The object programming style on the other hand suggest that important
data structures should be tied to the object, not the function.
The need for continuations should be lessened if one has some light weight
process implementations at hand.
Actually I am still wondering about how one is supposed to build a
general pupose iterator in a OO language. One can always have
Ad Hoc iterators, but a consistent iterator interface I suspect would
be hard to do.
-Thomas Wang (Mak-Kuro Kurosuke, come on out! If you don't come out,
we'll pull your eyeballs out!
- as heard in Tonari No Totoro )
ttwang@polyslo.calpoly.edubarmar@think.com (12/01/89)
In article <10008@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: > Now, if you add continuations, >there is the potential to pass the continuation outside of the object, thus >creating another entry point into the object that is not a member function. >I see this as an information hiding problem for continuations in OO languages. >Perhaps you can relate why this is not a problem in CLOS. CLOS makes no attempt to implement information hiding. (slot-value <object> <slot-name>) may be called from anywhere, not just methods. In CLOS, methods are just functions that know what the types of their required arguments are, and they are invoked through generic function dispatching. Lisp, in general, doesn't restrict the programmer's options for philosophical reasons. If the programmer wants to pass a lexical closure out of a method, that's his prerogative. Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
shap@delrey.sgi.com (Jonathan Shapiro) (12/01/89)
In article <10008@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: >4. C and C++ have first class functions. Functions can be passed as > parameters, returned as function values, and assigned to variables. >Hope this helps to clear up any mis-understandings, >Peter. Actually, Peter, it creates one. C and C++ do not have fist class functions. Functions cannot be passed as values. Function pointers can, whcih is a somewhat different thing. To be first class, it must be possible to treat functions as *values* rather than as *labels*. For example, the following is a syntax error: int foo(int); int bar(int); foo = bar If functions were first class, this would be altogether legal. Otherwise, your posting was correct. Jonathan Shapiro Silicon Graphics, Inc.
twl@brunix (Ted "Theodore" (W) Leung) (12/02/89)
In article <10008@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: >4. C and C++ have first class functions. Functions can be passed as > parameters, returned as function values, and assigned to variables. > The reason that C and C++ do not allow nested functions is precisely > so that they can have first-class functions implemented on a stack > (e.g. no closure required). The "parent block" of a function is > simply the global variables. > It seems like it would be useful to make a distinction between "first class" functions which require their implementation via a closure, and those which do not. There is a fairly standard trick in the Scheme community, which uses closures to create objects. The closed over variables are used to represent the local state of the object, and the code of the closure is a big case statement which selects the correct method to be invoked. It seems to me that you cannot use C "first class" functions to create objects, because they have no closure..... I do think that C/C++ functions are not first class because it is not possible to create a function on the fly the way that you can in LISP or Scheme. Ted -------------------------------------------------------------------- Internet/CSnet: twl@cs.brown.edu | Ted "Theodore" Leung BITNET: twl@BROWNCS.BITNET | Box 1910, Brown University UUCP: uunet!brunix!twl | Providence, RI 02912
allen@sbcs.sunysb.edu ( Allen Leung) (12/02/89)
In article <10008@june.cs.washington.edu>, peterd@cs.washington.edu (Peter C. Damron) writes: > 4. C and C++ have first class functions. Functions can be passed as > parameters, returned as function values, and assigned to variables. > The reason that C and C++ do not allow nested functions is precisely > so that they can have first-class functions implemented on a stack > (e.g. no closure required). The "parent block" of a function is > simply the global variables. > > Peter. > peterd@cs.washington.edu > {ucbvax,decvax,etc.}!uw-beaver!uw-june!peterd I must disagree. C and C++ definitely *don't* have first class functions. From a function programming view point, type alpha is first class means that values of alpha enjoy all the privilages granted to first class types. In terms of C this means you are supposed to be able to do things like this with functions: int(*)() foo( int y; ) { int x; // if you can local declare int/float/* ....etc float r; char *a; int bar( int z ) // you should be able to local declare bar { return y + z; } // y is free in bar but bound in foo return bar; } --Allen allen@sbcs.sunysb.edu
max@Neon.Stanford.EDU (Max Hailperin) (12/02/89)
In article <21989@brunix.UUCP> twl@boojum.UUCP (Ted "Theodore" (W) Leung) writes: >In article <10008@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter >C. Damron) writes: >>4. C and C++ have first class functions. >> ... no closure required ... >It seems like it would be useful to make a distinction between "first >class" functions which require their implementation via a closure, and >those which do not. As an asside to this discussion, it appears to me that closures can be emulated relatively smoothely in C++. The two key features that support this are: 1) The procedure-call operator can be overloaded, so that you can define a class of closure objects which can be called as if they were procedures. The constructor (lambda equivalent) can copy the closed-over variables into slots with the same name, so that then the procedure-call member function can use them. 2) The notion of a reference type (explicit aliasing) allows the closures to share mutable variables that are in a common scope. Of course, this is still a bit messy, but nothing compared with emuating closures in C. Also, there are other language features that interact poorly with a higher-order style, limiting the utility. I haven't actually used this technique (I'm lucky enough to have a real lisp, instead of having to make C++ pretend it's one). I'd be very interested to hear from anyone who has.
dlw@odi.com (Dan Weinreb) (12/02/89)
In article <10008@june.cs.washington.edu> peterd@cs.washington.edu (Peter C. Damron) writes:
The problem I have with including continuations into an object oriented
language is a philisophical one. Objects should be self-contained and
hide information. All interactions with objects should be through
the well defined methods of the object. Now, if you add continuations,
there is the potential to pass the continuation outside of the object, thus
creating another entry point into the object that is not a member function.
I see this as an information hiding problem for continuations in OO languages.
Perhaps you can relate why this is not a problem in CLOS.
Well, I admit that this is all rather hard to articulate. I see
continuations as a control structure concept. It is part of the way
you tell your computer program what to do next, how the locus of
control should move throughout the lines of code. As such, it is
really orthogonal to the important concepts of object-oriented
programming: you can have loops in OOPS, and you can have recursion in
OOPS, so why not coroutines and continuations?
In this specific case, no, I don't think it creates a new
"entrypoint", although this statement is based on a concept of
"entrypoint" that I'm having trouble articulating. Part of the
important point is that encapsulation is not violated, because only a
method of a class can create a continuation that continues within that
class. I hope that explains what I mean; sorry I can't do better.
Let's get this straight.
Yes, I used the terminology in an inexact (wrong) way, as I said in
recent postings. I apologize. I meant to say that C and C++ do not
have first-class nested functions that are block structured with
respect to their containing functions.
3. Continuations are orthogonal to first-class functions (e.g. languages
that allow both upward and downward funargs) and are orthogonal to
block structure.
Hmm. The only continuation-passing-style programs that I've ever seen
certainly spent a lot of time dealing with first-class objects that
were upward and downward funargs. Perhaps you could sketch out an
extension to C that would provide continuations, without providing
such functional objects, and then I'd see what you're getting at.dlw@odi.com (Dan Weinreb) (12/02/89)
In article <7159@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: In article <1989Nov29.230331.19595@odi.com> dlw@odi.com writes: > It depends what you mean. It would certainly be possible to invent a > definition of a language that was like C, but also had the features > needed to do continuation-style programming. There is. It's called C. Almost. Seriously. All you need to do is have a bit of unportable code that mucks around in struct jmp_buf. Save the stack between here and there, do a setjmp to mark the end of the current stack, and then longjmp back to the saved spot. To continue, restore the saved stack and longjmp back to the mark. It would be advisable to write this code in assembly language :->. This would also give you the ability to add coroutines, threads, and all sorts of other good stuff. Let's call it ++C. But it would not give me the ability to write programming that are in what is traditionally (at the MIT AI lab -- OK, I'm provincial, but that's where I was trained) referred to as continuation-passing style". When all the interesting papers about "continuation-passing style" were coming out at MIT in the late '70s, they showed a lot of very interesting techniques and things that you could do with continuations. But these techniques also employed funargs (both kinds). It's true that you could add the control structure all alone, and call what you get "continuation-passing style", but it would not be the style to which I had become accustomed. Obviously my posting was unclear because I had in mind this particular specialized meaning of the phrase "continuation-passing style", and I didn't explain what I meant. Sorry about that.
grover%brahmand@Sun.COM (Vinod Grover) (12/02/89)
In article <31794@news.Think.COM> barmar@think.com writes: >In article <128489@sun.Eng.Sun.COM> grover@sun.UUCP (Vinod Grover) writes: >>I do not know if you are talking about first-class continuations or not, but >>in languages which are stack-based first-class continuations are not trivial >>to add. (By stack-based I mean that the procedure entry exit sequance >>behaves in a stack-like fashion) > >This is a circular argument. It's the very existence of first-class >continuations in Scheme-like languages that causes them not to be >stack-based. If Scheme didn't have continuations then it would be >stack-based, according to your definition. One can also argue that it is the existence of lexical scoping, and higher-order functions that cause a language not to be stack based. In this sense, continuations are simply functions whose environment may be embedded in other functions. Vinod Grover Sun Microsystems
mikpe@majestix.ida.liu.se (Mikael Pettersson) (12/02/89)
In article <1989Dec1.205817.5178@Neon.Stanford.EDU> mxh@sumex-aim.Stanford.EDU (Max Hailperin) writes: >As an asside to this discussion, it appears to me that closures can be >emulated relatively smoothely in C++. > [...] >I haven't actually used this technique (I'm lucky enough to have a >real lisp, instead of having to make C++ pretend it's one). I'd be >very interested to hear from anyone who has. I have. The idea is this: whenever you want to create a closure with type T, body B and (list of) free variables FV, you derive from an abstract base class `funcT' a class `foo_funcT' with instance variables `FV' and whose operator() does `B' when invoked. Something like this: (define (bar L) (let ((i 1)) (for-each (lambda (item) (princ i)(princ ":")(print item) (set! i (1+ i))) L))) (assuming a left-to-right calling order in for-each, this should print each item in the list L preceeded by its position in the list). The C++ emulation could look like: class funcT { // say: Obj->void public: virtual void operator()(Obj); }; class ObjList { ... friend void for_each(funcT&, ObjList); ... }; ... class foo_funcT : public funcT { int& i; public: foo_funcT(int& j) : i(j) {} void operator()(Obj); } void foo_funcT::operator()(Obj item) { cout << i << ":" << item << "\n"; ++i; } void bar(ObjList L) { int i = 1; foo_funcT fun(i); for_each(fun, L); } This technique handles downwards funargs quite nicely, upwards funargs require explicit heap allocation. -- Mikael Pettersson, Dept of Comp & Info Sci, University of Linkoping, Sweden email: mpe@ida.liu.se or ...!{mcsun,munnari,uunet,unido,...}!sunic!liuida!mpe
kend@tekchips.LABS.TEK.COM (Ken Dickey) (12/03/89)
Sorry, you got me in a bad mood. FLAME ON! In article <10008@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: > >The problem I have with including continuations into an object oriented >language is a philisophical one. Objects should be self-contained and >hide information. All interactions with objects should be through >the well defined methods of the object. Now, if you add continuations, >there is the potential to pass the continuation outside of the object, thus >creating another entry point into the object that is not a member function. >I see this as an information hiding problem for continuations in OO languages. So Smalltalk is not object oriented because it has blocks and returns objects (remember that may be internal to/components of other objects)? How do you implement backtracking objects? Having the ability to deal with control flow in well structures ways is very helpful. It seems that you are trying to push everything through an OO keyhole. Functional interfaces are also well defined. In languages such as Scheme, you can program in functional, imparative, OO, etc. styles as appropriate to the solutions you are trying to structure. There are real problems in trying to use a single paradigm to cover all solutions. Some just don't fit. >Let's get this straight. >... >2. C and C++ do not allow nested functions, but they do support block > structure. Thus the lexical scoping is not "trivial". In C you get a local/global namespace. You don't have name scoping in blocks nested more than 1 deep. That's pretty trivial. >3. Continuations are orthogonal to first-class functions (e.g. languages > that allow both upward and downward funargs) and are orthogonal to > block structure. It is not apparent to me that continuations are > any less useful without block structure (though C and C++ have it anyway). > It is also not apparent to me that continuations are any less useful > without nested functions (though maybe more cumbersome). I suggest that you look at some of the Scheme literature for examples (e.g. Abelson & Sussman: "Structure and Interpretation of Computer Programs", MIT Press/McGraw-Hill, 1985). >4. C and C++ have first class functions. Functions can be passed as > parameters, returned as function values, and assigned to variables. They cannot be unnamed. They cannot be parameterized. They are *not* first class. Perhaps a concrete example would help: (define (curried-add x) (lambda (y) (+ x y)) ) ; returns an unnamed function (define add3 (curried-add 3)) ; function is parameterized & bound ; to a variable. (add3 5) --> 8 ; usage: add 5 and 3 to get 8 > The reason that C and C++ do not allow nested functions is precisely > so that they can have first-class functions implemented on a stack > (e.g. no closure required). The "parent block" of a function is > simply the global variables. Here you have something. To quote from David Kranz's thesis ("ORBIT, an optimizing Compiler for Scheme", Yale U, 1988; p. 9): The important thing to realize is that Pascal and C are really just restricted subsets of Scheme, in particular those parts of Scheme which can be implemented efficiently using conventional compiler technology! You have to use non-standard compiler/runtime technology to compile Scheme efficiently. However, Scheme is a much smaller, more powerful language than C. When C++ becomes a language (when it is described in a single document and has a well defined semantics) Scheme will be smaller than C++ as well [the Scheme language report is ~50 pages, including a formal semantics]. END-FLAME! -Ken
boehm@flora.rice.edu (Hans Boehm) (12/04/89)
In article <5153@tekcrl.LABS.TEK.COM> kend@mrloog.WR.TEK.COM (Ken Dickey) writes: >In C you get a local/global namespace. You don't have name scoping in >blocks nested more than 1 deep. That's pretty trivial. What about: int i; int f() { int i; ... { int i; ... } } I won't argue about whether this is trivial, but there are certainly nested scopes. > >>3. Continuations are orthogonal to first-class functions (e.g. languages >> that allow both upward and downward funargs) and are orthogonal to >> block structure. It is not apparent to me that continuations are >> any less useful without block structure (though C and C++ have it anyway). >> It is also not apparent to me that continuations are any less useful >> without nested functions (though maybe more cumbersome). > >I suggest that you look at some of the Scheme literature for examples >(e.g. Abelson & Sussman: "Structure and Interpretation of Computer >Programs", MIT Press/McGraw-Hill, 1985). A more specific argument would help here. I am reasonably familiar with the Scheme literature, and it seems to me that most of the standard examples involving continuations translate reasonably easily into a world without closures, though they may be much less clean. Call/cc is probably not quite the right primitive. An interface closer to setjmp/longjmp (but without the restriction on the caller to setjmp exiting, and with a cleaner distinction of what's saved, and what isn't) probably makes more sense. This would certainly be adequate for implementing coroutines and the like. It would be similar to Call/cc(lambda x . (jmpbuf := x; 0)) in Scheme-like languages. Note that unlike in Scheme, there is no analog to "continuation- -passing-style" in C/C++. But this is orthogonal to the above discussion. > >>4. C and C++ have first class functions. Functions can be passed as >> parameters, returned as function values, and assigned to variables. > >They cannot be unnamed. They cannot be parameterized. They are *not* >first class. I'm not sure what "They cannot be parametrized" means. For most interpretations of the sentence, it's wrong. I would be among the first to argue that languages should provide real higher-order functions. However, it also seems clear that this requires garbage collection of one form or another. Furthermore it removes some control over allocation behavior from the programmer. Both of these in turn cause some difficulty with programs operating under severe real-time constraints. C and C++ chose not to go this route. Given that they didn't, I know of no way to implement continuations efficiently, while sticking to the design philsophy of either language. Thus it doesn't make sense to me to add first-class continuations to C++. But this argument has nothing to do with their utility to the programmer. Hans-J. Boehm boehm@rice.edu
allen@sbcs.sunysb.edu ( Allen Leung @ SUNY at Stony Brook, L.I., NY ) (12/04/89)
In article <3374@brazos.Rice.edu>, boehm@flora.rice.edu (Hans Boehm) writes: > In article <5153@tekcrl.LABS.TEK.COM> kend@mrloog.WR.TEK.COM (Ken Dickey) writes: > > >In C you get a local/global namespace. You don't have name scoping in > >blocks nested more than 1 deep. That's pretty trivial. > What about: > > int i; > int f() > { > int i; > ... > { > int i; > ... > } > } > > I won't argue about whether this is trivial, but there are certainly nested > scopes. True, C has nested scopes, but only with non-functions. We certainly can't write int i; int f() { int i; int g() { ... i ... }; ... } When we disallow local declaration of functions, I think all the sub-blocks can be lifted up to the main block with proper renaming of bound variables ( If you treat sub-blocks as lambda expression with a throw-away parameter, then they can always be beta-reduced at compile time. ) C with nested scopes actually has no more power( not the Turing Machine sense) than one without, even though its more convenient. > A more specific argument would help here. I am reasonably familiar with > the Scheme literature, and it seems to me that most of the standard > examples involving continuations translate reasonably easily into a > world without closures, though they may be much less clean. Call/cc is > probably not quite the right primitive. An interface closer to > setjmp/longjmp (but without the restriction on the caller to setjmp > exiting, and with a cleaner distinction of what's saved, and what isn't) > probably makes more sense. This would certainly be adequate for > implementing coroutines and the like. It would be similar to > Call/cc(lambda x . (jmpbuf := x; 0)) in Scheme-like languages. > > Note that unlike in Scheme, there is no analog to "continuation- > -passing-style" in C/C++. But this is orthogonal to the above > discussion. > > > > >>4. C and C++ have first class functions. Functions can be passed as > >> parameters, returned as function values, and assigned to variables. > > > >They cannot be unnamed. They cannot be parameterized. They are *not* > >first class. > > I'm not sure what "They cannot be parametrized" means. For most > interpretations of the sentence, it's wrong. Maybe the original author means that C functions cannot reference non-global free variables. In any case, I'm extremely doubtful that continuation in a language with *side-effects* can be translated easily into a language without the concept of a closure. Since a continuation is essentially a closure( entrypoint + environment ). A language with side effects complicates the implementation of closure/continuation tremendously: A variable must reside in one place, either on the stack or in the heap; any duplication will make the variable's update non-trivial. I'm not familiar with Scheme, but I guess it only *solves* this problem by allocation the stack frame of a possibly 'closurised'( you know what I mean ) code on the heap, similar to what most lisp do with a upward funarg( or is it downward? I can never remember which is which.) A language that supports continuation must/should support first-class/higher order functions. They have about the same complexity. I believe we can simulate continuation with higher order functions easily enough. A continuation is just a function that never returns; that "never returns" part have some problem related to stack allocation, of course. allen@sbcs.sunysb.edu
pcg@aber-cs.UUCP (Piercarlo Grandi) (12/04/89)
It has been my long held belief that really objects and closures are much the same thing, to a certain extent. In many ways you can simulate closures with objects (especially if you have suspend/resume) and objects with closures. My reckoning has always been that the most powerful possible entity is a triple (dictionary, code, saved state), where each member of the triple may be possibly null. If you also have the three steps for procedure invocation directly available, like in SL5, then you can do wonderful things, and even more incredible ones if you can have code executed at compile time (e.g. like in Lisp, or in the "supercompiler" concept). The BETA language has "patterns" that are really something like this. As to more mundane things, under certain respects most current popular OO languages are a step backwards from Simula 67, e.g. detach/suspend/resume, inner, and block prefixing, etc... -- Piercarlo "Peter" Grandi | ARPA: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcvax!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk
grover%brahmand@Sun.COM (Vinod Grover) (12/05/89)
In article <1989Nov30.002204.4899@mentor.com> plogan@mentor.com (Patrick Logan) writes: > > >>From: grover%brahmand@Sun.COM (Vinod Grover) > > Admittedly, this is not as elegant as > >Scheme's notion of continuation but workable in concept. > > >To be more accurate, longjump is not workable in concept because a >longjump can only be executed once per setjmp. A continuation in >Scheme can be captured once and executed zero or more times. Things >become more complicated when you start considering nested setjmps >and longjumps. Yes, you are quite right. In fact the problem is even deeper than that, as I just learned, if the function calling setjmp returns before the call to longjmp is made then the longjmp is made to a non-existent environment. Thanks for correcting me. Vinod Grover Sun Microsystems.
jste@PacBell.COM (Joshua Stein) (12/05/89)
Can someone post a non-implementation dependent definition of continuations;
what they are, what they do, and how they fit into the object-oriented paradigm.
--
*******************************************************************************
Joshua Stein/Pacific*Bell/415 823-2411 |"I make it a rule to never get involved
the usual generic disclaimer goes here |with somone who's possessed ... well,
uucp:{world}!pacbell!pbhyf!jste |it's more of a guideline than a rule"peter@ficc.uu.net (Peter da Silva) (12/06/89)
In article <1989Nov30.002204.4899@mentor.com> plogan@mentor.com (Patrick Logan) writes: > To be more accurate, longjump is not workable in concept because a > longjump can only be executed once per setjmp. What if you (as I suggested in another post) save and restore the whole stack? -- `-_-' Peter da Silva. +1 713 274 5180. <peter@ficc.uu.net>. 'U` Also <peter@ficc.lonestar.org> or <peter@sugar.lonestar.org>. "If you want PL/I, you know where to find it." -- Dennis
djones@megatest.UUCP (Dave Jones) (12/06/89)
From article <1713@odin.SGI.COM>, by shap@delrey.sgi.com (Jonathan Shapiro): > In article <10008@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: >>4. C and C++ have first class functions. Functions can be passed as >> parameters, returned as function values, and assigned to variables. > >>Hope this helps to clear up any mis-understandings, >>Peter. > > Actually, Peter, it creates one. Oh, gimme a break. I think the only misunderstanding is in the definition of the value-charged adjectival phrase, "first class". If by "first class", you mean "variable", then C's function-names are not "first class", but that certainly does not make them second or third class! For most purposes, constant-names for functions are to be prefered over function-valued variables. > C and C++ do not have fist class > functions. Functions cannot be passed as values. Function pointers > can, whcih is a somewhat different thing. To be first class, it must > be possible to treat functions as *values* rather than as *labels*. What is a function's "value", if not a label? What other candidates are there? The only issue here is whether the name always refers to the same function: Is the name effectively a label, or does it refer to a variable which can contain any of a number of different labels? That is the choice. There are benefits to constant function-names. I can recall some awful, XDR-related debugging sessions, struggling to figure out whether this or that function-variable was bound to this or that procedure. It's best to use constants when possible, reserving the use of variables for the few occasions when they are really needed. Besides, on most machines, the procedure call will be quicker if the name is a constant, resolved by the linker, rather than at runtime. > For example, the following is a syntax error: > > int foo(int); > int bar(int); > > foo = bar > > If functions were first class, this would be altogether legal. > Then we would have to add something like ... constant int foo(int); ... to recover the lost functionality. I would much prefer that function-names be constants in the default case. Here's how you can have it both ways, constants and variables, in plain old K&R C. extern int bar(); /* "bar" names an external constant. */ int (*foo)(); /* "foo" names a variable. */ void foozle() { foo = bar; /* What could be simpler? */ }
nn@wheaties.ai.mit.edu (Nick Nussbaum) (12/07/89)
Those interested in continuations in C might want to look at a paper by Thomas Bruel which I believe was presented at the Usenix 88 conference. He proposed implementing closures by generating pointer to some automatically generated code which sets up the environment and then jumps into the function. Thus closures can be used in the same way as vanilla function pointers. He also discusses the desirablility of nested functions. -- Nick Nussbaum PO 68 - MIT Branch nn@rice-chex.ai.mit.edu Cambridge, MA 02139
kend@tekchips.LABS.TEK.COM (Ken Dickey) (12/07/89)
In article <3374@brazos.Rice.edu> boehm@flora.rice.edu (Hans Boehm) writes: >In article <5153@tekcrl.LABS.TEK.COM> kend@mrloog.WR.TEK.COM (Ken Dickey) writes: > >>In C you get a local/global namespace. You don't have name scoping in >>blocks nested more than 1 deep. That's pretty trivial. >What about: > >int i; >int f() >{ > int i; > ... > { > int i; > ... > } >} > >I won't argue about whether this is trivial, but there are certainly nested >scopes. Try it with functions. >... I am reasonably familiar with >the Scheme literature, and it seems to me that most of the standard >examples involving continuations translate reasonably easily into a >world without closures, though they may be much less clean. Call/cc is >probably not quite the right primitive. An interface closer to >setjmp/longjmp (but without the restriction on the caller to setjmp >exiting, and with a cleaner distinction of what's saved, and what isn't) >probably makes more sense. This would certainly be adequate for >implementing coroutines and the like. It would be similar to >Call/cc(lambda x . (jmpbuf := x; 0)) in Scheme-like languages. The literature I was thinking of is on the order of: Wand, Mitchell: "Continuation-Based Program Transformation Strategies" JACM V 27, #1, January 1980 Friedman, Haynes, & Kohlbecker: "Programming with Continuations" in "Program Transformations and Programming Environments" Ed: P. Pepper Springer-Verlag 1984 Haynes, Friedman, & Wand: "Obtaining Coroutines with Continuations" Computer Languages: V11, #3/4 1986 Haynes, Friedman, & Wand: "Continuations & Coroutines" 1984 Symposium on Lisp and Functional Programming Friedman, Haynes: "Constraining Control" Proceedings 12th Annual Symposium on Principles Of Programming Languages (ACM), January 1985 Wand: "Continuation-Based Multiprocessing" Proceedings of the 1980 Lisp Conference Felleisen, Friedman, Kohlbecker, & Duba: "Reasoning with Continuations" Proceedings of the Symposium on Logic in Computer Science, IEEE Press, 1986 Haynes & Friedman: "Engines Build Process Abstractions" 1984 Symposium on Lisp and Functional Programming Haynes & Friedman: "Abstracting Timed Preemption with Engines" Computer Languages, V20, #2, 1987 (pub Great Britain). Clinger, Will: "The Scheme Environment: Continuations" Lisp Pointers, V1, #2, June-July 1987 I guess I don't quite see what you are looking for here. With a timer interrupt, you can implement multitasking. Other applications [8^] of continuations are non-blind backtracking, dynamic-wind, reasonable error recovery (correct & reexecute), etc. Yes, you can do these things in the os/runtime environment (outside of the C language). Yes, you can do this in less clean ways. Yes, call/cc is not necessarily intuitive to think about. Why do you want something less clean? How do you `reexecute' code in sane ways without a segmented stack? >>>4. C and C++ have first class functions. Functions can be passed as >>> parameters, returned as function values, and assigned to variables. >> >>They cannot be unnamed. They cannot be parameterized. They are *not* >>first class. > >I'm not sure what "They cannot be parametrized" means. For most >interpretations of the sentence, it's wrong. I am thinking of parameterization by currying. With higher order functions, you create families of functions parameterized/specialized for particular tasks. E.g. a function which does numerical integration becomes a specialized integrator by being parameterized with a particular function and can then be used to integrate various intervals. A generic device interface becomes specialized for a particular hardware environment by being parameterized by a particular HW device driver. Et cetera. Sorry for the confusion. > >I would be among the first to argue that languages should provide real >higher-order functions. However, it also seems clear that this requires >garbage collection of one form or another. I have yet to see an open system without a memory allocator. Languages without a `pointer' abstraction save a certain class of errors (i.e. one does not dereference bogus pointers). Dealing with *values* and having the language implementation deal with what fits in a register and what does not can save significantly in implementation time. I do not view automatic storage management as a bad thing. The "GC in an uncooperative environment" people observed that even with partial collection of C code, they were able to take care of storage leaks which they found in almost all large C programs they looked at. Using more memory to get faster development may buy market share where time-to-market is important. >... Furthermore it removes >some control over allocation behavior from the programmer. I don't fully agree with this. Don't use CONS. Allocate data statically. Parameterize your functionals at compile time. Demand and use non-cons runtime services. > .. Both of >these in turn cause some difficulty with programs operating under severe >real-time constraints. C and C++ chose not to go this route. Again, I don't fully agree. It depends on how close you are to the limits. Some C implementations have allocators which don't allocate in constant time (e.g. best fit) and fail in the real-time area. Some highly constrained RT systems are coded in assembler because C is too slow. Some real time applications have enough margin to collect adequately if coded in low-cons style. The Appel-Ellis-Li real-time collector (e.g. with a 68030) looks very interesting. I think that the general picture is unclear enough here that it is difficult to make a blanket statement about real-time systems in general. > ... Given that >they didn't, I know of no way to implement continuations efficiently, >while sticking to the design philsophy of either language. Thus it doesn't >make sense to me to add first-class continuations to C++. But this >argument has nothing to do with their utility to the programmer. > >Hans-J. Boehm >boehm@rice.edu Questions of design philosophy aside, it is interesting to look more closely at what `efficiency' is being asked for. The ability to mix compiled and interpreted code gives a very short design-code-test loop. Not dereferincing bogus pointers eliminates a class of programming errors. *Efficiency in bringing products rapidly to market. Having first class functions help encapsulation and can lead to smaller, cleaner code and more code reuse--which means lower maintainance costs. This means more production efficiency because engineers can be building new product rather than doing maintenance. *Efficiency in product production; less rework, less spoilage. I guess if you are not building production code, you don't care about time-to-build/time-to-market. But you probably aren't worried about hard real-time performance either. ===== Having gone this far, I guess I should make a philosoply statement and do some language bashing so people really have something to flame about. [ Don't get too excited; but I do like a good discussion! ] I think the C is a great language for writing device drivers. When it comes to do doing large systems (>200-500 KLOC), system complexity becomes a larger dragon than execution speed. C has won because of its simple execution model, closeness to assembler, and Un*x usage. In C++, the simple execution model is lost [An assignment statement may copy data 3 times. Strings may be reference counted within the parameter passing mechanism. Arrays may not be allocated until first use. Et cetera.] I know a number of people programming in C++ and none who is happy with it. Using a very complex artifact [a Language has a single defining document and a well understood semantics] like C++ does not help in minimizing system complexity. Go ahead! Call me a language bigot! I deserve it! I have also written 50-100 KLOC each of Pascal and C code, some Smalltalk, APL, FP, Fortran, and a fair amount of Scheme code. I find that Scheme gets in my way the least. Having said that, I think that implementation technologies only make sense in the context of implementations. In some contexts, the language of choice may be C, Basic, Beta, Scheme, Ada, assembler, etc. I go for the best technology I can to solve problems in a given context. I think that the important thing is to know more than 1 technology so that one knows what reasonable choices exist and how to evaluate what is reasonable. [Please, flames to /dev/null -- I freely admit, I don't know it all]. [Non-continuation follow-ups probably belong somewhere other than comp.object] -Ken
beard@ux1.lbl.gov (Patrick C Beard) (12/08/89)
In article <5153@tekcrl.LABS.TEK.COM> kend@mrloog.WR.TEK.COM (Ken Dickey) writes: >In article <10008@june.cs.washington.edu> peterd@june.cs.washington.edu (Peter C. Damron) writes: >>Let's get this straight. >>... >>2. C and C++ do not allow nested functions, but they do support block >> structure. Thus the lexical scoping is not "trivial". > >In C you get a local/global namespace. You don't have name scoping in >blocks nested more than 1 deep. That's pretty trivial. Not true. In C you have a global namespace, a struct namespace, and multiple nested local namespaces. For example: int x; /* in global namespace. */ struct foo { int x; /* struct namespace. */ }; routine() { int x; /* first local namespace. */ { int x; /* first of many possible nested local namespaces. */ /* you can nest as deep as you like. */ ... } } At every new scope, the x's in the outer scopes are hidden. Why does this constitute "trivial" name scoping? Sorry if this response was long winded. Let's quit quibbling over legitimate language differences. Some languages are good for one thing, some another, none are suitable for every programming task. ------------------------------------------------------------------------------- - Patrick Beard, Macintosh Programmer (beard@lbl.gov) - - Berkeley Systems, Inc. ".......<dead air>.......Good day!" - Paul Harvey - -------------------------------------------------------------------------------
chase@Ozona.orc.olivetti.com (David Chase) (12/08/89)
In article <5369@rice-chex.ai.mit.edu> nn@rice-chex.WISC.EDU (Nick Nussbaum) writes: > Those interested in continuations in C might want to look >at a paper by Thomas Bruel which I believe was presented at the >Usenix 88 conference. He proposed implementing closures by >generating pointer to some automatically generated code which sets >up the environment and then jumps into the function. Thus closures >can be used in the same way as vanilla function pointers. It's a neat trick (Stallman put me in touch with Thomas Breuel, who described it to me), and I even used it for a while in a Modula-3 compiler. Most unfortunately, life gets much more complicated on architectures/OSes that separate instructions and data (by page protection, or in potentially inconsistent caches). Some calling conventions also make this difficult -- it's dead easy on a Sun 1, 2, or 3, less easy on a SPARC, and I'm not sure that it's tractable at all on a MIPS, i860, or 88000. Bummer, that. It was great fun while it lasted. David
gateley@m2.csc.ti.com (John Gateley) (12/12/89)
In article <6527@pbhyf.PacBell.COM> jste@PacBell.COM (Joshua Stein) writes: >Can someone post a non-implementation dependent definition of continuations; >what they are, what they do, and how they fit into the object-oriented paradigm. A continuation of some point during the execution of a program is a function which accepts any results at the point, and returns the result of the rest of the program. To be more technical, you need to define points occuring during execution and so on. Basically continuations are a different flavor of goto. They can do forward jumping (called escape continuations) where you want to punt and jump out of 20 levels of function calls at once. They can do backwards jumping where you invoke the continuation after you passed the point in the program which created it (causing looping). They are used to model different control constructs. Coroutines are the canonical example; it is very easy to model coroutines given continuations. They are extremely powerful, and consequently extremely dangerous, and also tend to be as controversial as gotos. I don't know how they fit in an object oriented paradigm. John gateley@m2.csc.ti.com
ge@kunivv1.sci.kun.nl (Ge' Weijers) (12/13/89)
chase@Ozona.orc.olivetti.com (David Chase) writes: >However, the languages listed differ in their treatment of nested >procedures: >C forbids them (no closures). >Pascal allows them, but (in Pascal Classic, at least) forbids > their assignment to variables, use as parameters to > procedures, or use in a RETURN. (no closures, because it > turns out that a display can be used). Not quite true, in the original Pascal procedures were allowed as parameters, though type-safety goes out of the window, as the parameters were not indicated. PROCEDURE example (PROCEDURE error); BEGIN IF NOT (assertion) THEN error(4711); END example; I believe something like this was actually legal. In more current versions of the language the procedure must be typed. mr. Wirth probably did not dare to throw away the Algol-60 call by name at the time, as some people thought is was useful. They still are. >Modula-3 allows them, but forbids their assignment to variables or > their use in a RETURN. (closures needed, but must obey > stack lifetime rules). (I hope this example isn't too > obscure -- I'm rather familiar with it at the moment). Just like in Algol 68. Only the lifetime rule was very tricky there: the lifetime of a procedure is the lifetime of the 'youngest' non-local name accessed. The lifetime of a function not referencing any globals was therefore infinite, whereever it was declared. Ge' Weijers Internet/UUCP: ge@cs.kun.nl Faculty of Mathematics and Computer Science, (uunet.uu.net!cs.kun.nl!ge) University of Nijmegen, Toernooiveld 1 6525 ED Nijmegen, the Netherlands tel. +3180612483 (UTC-2)