Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.std.c > #749 > unrolled thread

Continuations in C?

Back to article view | Back to comp.std.c

Contents

  Continuations in C? Philipp Klaus Krause <pkk@spth.de> - 2011-08-13 10:47 +0200
    Re: Continuations in C? BGB <cr88192@hotmail.com> - 2011-08-13 03:02 -0700
      Re: Continuations in C? Philipp Klaus Krause <pkk@spth.de> - 2011-08-13 13:19 +0200
        Re: Continuations in C? BGB <cr88192@hotmail.com> - 2011-08-13 12:29 -0700
      Re: Continuations in C? Philipp Klaus Krause <pkk@spth.de> - 2011-08-15 09:49 +0200
        Re: Continuations in C? BGB <cr88192@hotmail.com> - 2011-08-16 10:53 -0700
    Re: Continuations in C? jacob navia <jacob@spamsink.net> - 2011-08-14 10:13 +0200
      Re: Continuations in C? BGB <cr88192@hotmail.com> - 2011-08-14 08:57 -0700
        Re: Continuations in C? Wojtek Lerch <wojtek_l@yahoo.ca> - 2011-08-14 23:38 -0400
          Re: Continuations in C? Philipp Klaus Krause <pkk@spth.de> - 2011-08-15 09:48 +0200
            Re: Continuations in C? BGB <cr88192@hotmail.com> - 2011-08-16 10:56 -0700
    Re: Continuations in C? Tim Rentsch <txr@alumni.caltech.edu> - 2011-08-30 15:36 -0700

#749 — Continuations in C?

I would like to see functions providing continuations in the standard
library. Let's call these c() and j() for now.
Currently C provides setjmp() / longjmp() which is a restricted variant
of continuations: The continuation obtained by setjmp() is only valid as
long as the funtion that called setjmp() doesn't return. c() / j() would
be like setjmp() / longjmp() without that restriction.

Why?
1) C is increasingly used as a target language for compilers. Many of
the languages compiled to C have full continuations. Currently there are
basically two ways of compiling these to C: Continuation passing style,
which makes all funcction calls more expensive and non-portable tricks
to save and restore the stack somehow. c() / j() would provide a
portable way to implement continuations.
2) Full continuations are an extremly powerful control and useful
construct (as proven by all the things that are done using them in other
languages)). C should give programmers a way to use them. Since they
essentially are a more powerful variant of setjmp() / longjmp(), which,
in turn is a more pwoerful goto they might be considered harmful by
some. But C isn't a language designed to protect the programmers from
themselves.

c() / j() would manipulate the stack and thus should be relatively easy
to implement on systems where setjmp() / longjmp() can be implemented
easily (in particular, those that use a stack in memory and a stack
pointer, as AFAIK most implementations do). Nevertheless the feature
could be made optional and it's presence indicated by a macro, as done
e.g. with variable-length arrays in the next C standard.

So, why does C not provide full continuations?
Should, in your opinion, C provide full continuations?
Is there a chance to get them into the next C standard, and if so, how?

Philipp

[toc] | [next] | [standalone]

#750

On 8/13/2011 1:47 AM, Philipp Klaus Krause wrote:
> I would like to see functions providing continuations in the standard
> library. Let's call these c() and j() for now.
> Currently C provides setjmp() / longjmp() which is a restricted variant
> of continuations: The continuation obtained by setjmp() is only valid as
> long as the funtion that called setjmp() doesn't return. c() / j() would
> be like setjmp() / longjmp() without that restriction.
>
> Why?
> 1) C is increasingly used as a target language for compilers. Many of
> the languages compiled to C have full continuations. Currently there are
> basically two ways of compiling these to C: Continuation passing style,
> which makes all funcction calls more expensive and non-portable tricks
> to save and restore the stack somehow. c() / j() would provide a
> portable way to implement continuations.
> 2) Full continuations are an extremly powerful control and useful
> construct (as proven by all the things that are done using them in other
> languages)). C should give programmers a way to use them. Since they
> essentially are a more powerful variant of setjmp() / longjmp(), which,
> in turn is a more pwoerful goto they might be considered harmful by
> some. But C isn't a language designed to protect the programmers from
> themselves.
>
> c() / j() would manipulate the stack and thus should be relatively easy
> to implement on systems where setjmp() / longjmp() can be implemented
> easily (in particular, those that use a stack in memory and a stack
> pointer, as AFAIK most implementations do). Nevertheless the feature
> could be made optional and it's presence indicated by a macro, as done
> e.g. with variable-length arrays in the next C standard.
>
> So, why does C not provide full continuations?
> Should, in your opinion, C provide full continuations?
> Is there a chance to get them into the next C standard, and if so, how?
>

realize, of course, that this is about like asking C to add lambdas (and 
proper ones too, not the half-assed ones added to C++ and GCC...).

theoretically, stuff like this could be done, but not without opening up 
a whole new mess of problems in the process.

for example, continuations would themselves either boil down to nasty 
stack-copying hackery (not a terribly good general-purpose strategy in 
general), or would create severe issues with how C is typically handled 
at the ABI level (probably requiring CPS at this level).

in both cases, what can be done by a compiler for a HLL compiler is 
probably better than what could be devised using a "one size fits all" 
strategy in the standard and waiting for all of the various 
implementations to adopt it.


in all, one is probably better off just using good old CPS or similar.

[toc] | [prev] | [next] | [standalone]

#751

Am 13.08.2011 12:02, schrieb BGB:
> for example, continuations would themselves either boil down to nasty
> stack-copying hackery (not a terribly good general-purpose strategy in
> general),

setjmp() / longjmp() already are nasty stack-adjusting hackery. The
stack-copying would be simple approach that would just work and could
quickly be implemented.
Compilers that care for performance could (if enough people use the
continuations to make it worth) instead handle them in a special way
(like e.g. code is directly being generated for memcpy() instead of a
functionc all). There are many variants of the stack-copying hackery
that are much more efficient than a simple unconditional full copy (see
e.g. "Implementation Strategies for First-Class Continuations" by
Clinger et alii).

Philipp

[toc] | [prev] | [next] | [standalone]

#752

On 8/13/2011 4:19 AM, Philipp Klaus Krause wrote:
> Am 13.08.2011 12:02, schrieb BGB:
>> for example, continuations would themselves either boil down to nasty
>> stack-copying hackery (not a terribly good general-purpose strategy in
>> general),
>
> setjmp() / longjmp() already are nasty stack-adjusting hackery. The
> stack-copying would be simple approach that would just work and could
> quickly be implemented.
> Compilers that care for performance could (if enough people use the
> continuations to make it worth) instead handle them in a special way
> (like e.g. code is directly being generated for memcpy() instead of a
> functionc all). There are many variants of the stack-copying hackery
> that are much more efficient than a simple unconditional full copy (see
> e.g. "Implementation Strategies for First-Class Continuations" by
> Clinger et alii).
>

a big problem with both setjmp/longjmp, and with stack-copying, is that 
they can't be migrated between threads (this is a bit of a problem for 
compiling HLL's which use "soft threading" or "green threading").

also, if one needs the stack copying hack, they can implement it 
themselves already (say, as part of the HLL's runtime or similar). 
adding it to the standard doesn't offer much obvious advantage IMO.

also, stack copying can't generally accurately reflect the semantics of 
lexical binding capture either absent additional hackery (heap-based 
lexical variables, ...).


IMO, CPS is better, since then one can migrate the continuations between 
threads, but CPS would likely be, problematic, for C compilers, and is 
better off built as a layer on top (as is more typical).


or such...

[toc] | [prev] | [next] | [standalone]

#758

Am 13.08.2011 12:02, schrieb BGB:
> 
> realize, of course, that this is about like asking C to add lambdas (and
> proper ones too, not the half-assed ones added to C++ and GCC...).

lambdas would require a change in the language. My proposal is just two
new function in the standard library.

Philipp

[toc] | [prev] | [next] | [standalone]

#759

On 8/15/2011 12:49 AM, Philipp Klaus Krause wrote:
> Am 13.08.2011 12:02, schrieb BGB:
>>
>> realize, of course, that this is about like asking C to add lambdas (and
>> proper ones too, not the half-assed ones added to C++ and GCC...).
>
> lambdas would require a change in the language. My proposal is just two
> new function in the standard library.
>

except that one would end up with either:
something that generally sucks;
potentially requiring non-trivial changes in the implementations.

the "sucks" option (IOW: something like setcontext), could itself be 
implemented as part of the HLL's runtime, and is in-fact one of the less 
complex parts of implementing a VM or compiler.

[toc] | [prev] | [next] | [standalone]

#753

I have serious doubts about using continuation passing style in
general.

Compared to that, the computed goto of fortran is nothing
serious.

Programs written using that feature are (by definition) unreadable.
You never know where the program will continue since continuations
are just variables that can be passed around. It is incredibly difficult
to follow such a program by reading the source text.

[toc] | [prev] | [next] | [standalone]

#754

On 8/14/2011 1:13 AM, jacob navia wrote:
> I have serious doubts about using continuation passing style in
> general.
>

"Continuation Passing Style" is a way of implementing basic control flow 
to allow continuations (such as in C), not a reference to continuations 
themselves.

IMO, CPS is preferable to the option of using stack copying for various 
reasons (such as being generally cheaper, more resistant against 
"funkiness", and able to migrate between OS threads).

http://en.wikipedia.org/wiki/Continuation_passing_style

internally, most of my VMs work in a CPS-like manner, mostly to make 
them easy to halt/resume as needed (useful in implementing soft 
threading, where a larger number of language-level threads runs on a 
smaller number of OS threads).


interestingly, is seems what the OP wanted is partly defined here:
http://en.wikipedia.org/wiki/Setcontext


> Compared to that, the computed goto of fortran is nothing
> serious.
>
> Programs written using that feature are (by definition) unreadable.
> You never know where the program will continue since continuations
> are just variables that can be passed around. It is incredibly difficult
> to follow such a program by reading the source text.
>

inference: "that feature" in this case being a reference to 
continuations proper.

http://en.wikipedia.org/wiki/Continuation


yep, and are also in general not all that generally useful.

they can sort-of be used to implement threading and exceptions, but not 
generally as good as dedicated mechanisms, ...

halt/resume is nice, but there may be other more preferable ways to do 
this (such as "soft threads" / "green threads" and "sleeping"), ...


or such...

[toc] | [prev] | [next] | [standalone]

#755

On 14/08/2011 11:57 AM, BGB wrote:
> interestingly, is seems what the OP wanted is partly defined here:
> http://en.wikipedia.org/wiki/Setcontext

Even more interestingly, even though (as Wikipedia mentions) 
setcontext() is specified in POSIX.1-2001, the 2004 version of POSIX 
marks it as obsolescent and the 2008 version does not mention it at all. 
  Perhaps before adding it to C, it would be good to find out why POSIX 
decided to drop it.

[toc] | [prev] | [next] | [standalone]

#757

Am 15.08.2011 05:38, schrieb Wojtek Lerch:
> On 14/08/2011 11:57 AM, BGB wrote:
>> interestingly, is seems what the OP wanted is partly defined here:
>> http://en.wikipedia.org/wiki/Setcontext
> 
> Even more interestingly, even though (as Wikipedia mentions)
> setcontext() is specified in POSIX.1-2001, the 2004 version of POSIX
> marks it as obsolescent and the 2008 version does not mention it at all.
>  Perhaps before adding it to C, it would be good to find out why POSIX
> decided to drop it.


POSIX had it as a portable means for user-level threading (for use with
makecontext() which was made obsolecsent the same way). POSIX now
provides real multi-threading (which is better than the
makecontext()/getcontext()/setcontext way(), since it can use parallel
hardware).

Philipp

[toc] | [prev] | [next] | [standalone]

#760

On 8/15/2011 12:48 AM, Philipp Klaus Krause wrote:
> Am 15.08.2011 05:38, schrieb Wojtek Lerch:
>> On 14/08/2011 11:57 AM, BGB wrote:
>>> interestingly, is seems what the OP wanted is partly defined here:
>>> http://en.wikipedia.org/wiki/Setcontext
>>
>> Even more interestingly, even though (as Wikipedia mentions)
>> setcontext() is specified in POSIX.1-2001, the 2004 version of POSIX
>> marks it as obsolescent and the 2008 version does not mention it at all.
>>   Perhaps before adding it to C, it would be good to find out why POSIX
>> decided to drop it.
>
>
> POSIX had it as a portable means for user-level threading (for use with
> makecontext() which was made obsolecsent the same way). POSIX now
> provides real multi-threading (which is better than the
> makecontext()/getcontext()/setcontext way(), since it can use parallel
> hardware).
>

which points out something else:
probably as far as POSIX was concerned, continuations weren't even on 
the table.

[toc] | [prev] | [next] | [standalone]

#768

Philipp Klaus Krause <pkk@spth.de> writes:

> I would like to see functions providing continuations in the standard
> library. [snip]
>
> So, why does C not provide full continuations?

Probably one or more of the following:

1. Lack of experience with prior art.
2. Perception of high cost and little benefit.
3. Lack of interest among the implementation community.
4. Lack of demand among the development community.
5. Lack of demand from vendors or their customers.


> Should, in your opinion, C provide full continuations?

No.  If someone wants to offer continuations as an
extension, more power to them, but adding FC to the
Standard, even as an optional feature, has negative ROI.


> Is there a chance to get them into the next C standard, and if so, how?

No, but if one wanted to try, the natural steps would be

1. Do an implementation in an existing C compiler;
2. Get developers to use it to shake bugs out and
   gain some experience both with the implementation
   and with development done using it;
3. Talk to one or more WG14 members to see if there
   is interest or support;
4. Write a description/proposal explaining the new
   language elements/features, and motivating their
   addition to the language;
5. Attend a WG14 meeting (or more likely, several),
   to present the proposal and defend it during the
   ensuing discussion;
6. Draft followup memos as they are called for, and
   repeating steps 3, 4, and 5, as necessary;
7. Draft additional text for the Standard defining
   all the added language elements, including changes
   to existing sections when/were they are affected;
8. Work with whatever WG14 members are interested to
   make sure there is enough support for actually
   adding the proposed text to the Standard so it
   doesn't get tabled and forgotten.

Good luck!

[toc] | [prev] | [standalone]

Back to top | Article view | comp.std.c

csiph-web