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.
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
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
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 |
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
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. __________________________________________________________________________
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
barmar@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.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
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
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