4 ms·

Python's "yield" - In Scheme (Using Continuations)

24 points by PieSquared 16y ago

dododo 16y ago
call/cc was introduced, as i understand it, as a means of formalising goto in this paper: Denotational semantics of goto: An exit formulation and its relation to continuations. Cliff B. Jones. http://www.springerlink.com/content/f340274565373810/ http://www.springerlink.com/content/f340274565373810/ this implementation of yield in scheme reminds me of the procedure linkage table in ELF executables, roughly in C: goto *current_entry_point then update current_entry_point on return (in the ELF PLT this is a one shot update).
- carterschonwald 16y ago
  actually it goes back even farther! ftp://ftp.cs.cmu.edu/user/jcr/histcont.pdf has a history written by John Reynolds, probably the world's most senior (and baller in the sense of doing amazing work) among currently active programming language theoreticians. Quote from pages 2-3 of the linked pdf: Apparently, the earliest description of a use of continuations was given by Adriaan van Wijngaarden (Director of the Mathematisch Centrum in Amsterdam) in September 1964, at an IFIP Working Conference on For- mal Language Description Languages held in Baden bei Wien, Austria. A written version of this talk, along with a transcript of the discussion that followed, appears in the conference proceedings [45]. Van Wijngaarden’s goal was to formulate a preprocessor that would translate Algol 60 into a more restricted sublanguage. The final stage of the preprocessing was (what we would now call) a transformation of proper procedures into continuation-passing style (CPS) [41], with an at- tendant elimination of labels and goto statements. (An earlier stage of the preprocessing replaced function procedures by proper procedures.) As van Wijngaarden described the transformation: Provide each procedure declaration with an extra formal param- eter — specified label — and insert at the end of its body a goto statement leading to that formal parameter. Correspond- ingly, label the statement following a procedure statement, if not labeled already, and provide that label as the correspond- ing extra actual parameter. [45]
  - dododo 16y ago
    oops. you're right. i provided a bad reference. sorry!
philh 16y ago
This doesn't require call/cc - you can do it with just closures (I've done it in perl, for example). It's also not as powerful as yield, in that it requires the list of return values to be precomputed. However, call/cc could be used to implement something of equivalent power to yield.
- carterschonwald 16y ago
  to be fair, anything you can do with call/cc (or even delimited continuations, or whatever) can be done with closures, its just a matter of being willing to write all of your code in the continuation passing style :-). Please see the linked article ftp://ftp.cs.cmu.edu/user/jcr/histcont.pdf or wikipedia for further reading.
  - philh 16y ago
    Yes, but that seems a trivial application of "lambda calculus is turing-complete" (or of some similar statement, if that one doesn't quite work). CPS is a slight improvement on that theorem, but not particularly relevant. Here, we have a piece of code which relies on both closures and continuations, and which is less clear than the equivalent code would be without continuations.
- jerf 16y ago
  A closer equivalent in perl, and other similar languages with closures, is the manually-unrolled continuation: sub continuationish { my $args = shift; my $state = {args => $args, state => 'INIT'}; return sub { goto $state->{state}; INIT: { # initial setup... $state->{state} = 'NORMAL'; return $first_output; } NORMAL: { # do stuff if (!$almost_done) { return $next_thingy; } else { $state->{state} = 'TERMINATING'; return $next_thingy; } } TERMINATING: { $state->{state} = 'TERMINATED'; return $state->{last_thingy}; # set above somewhere } TERMINATED: { return $sentinal_value; } }; } Everywhere you'd use a variable, you have to use something out of $state. This works. Any function can be rewritten using this approach to become a "generator" in Perl or similar languages. (Just remember that for and while loops all ultimately compile to "goto"s, and just perform the transform yourself.) But... you'll come to appreciate continuations or Python's yield pretty quickly. I think there have been three functions in my ~10 years of perl programming where I deemed it worth jumping through these hoops. Nice tool, but if you're using it a lot something's wrong. There exist some modules that try to do this automatically, however I have had some trouble with them, and they have the major problem that they end up being relatively opaque, often involving things like source code filters. Also, the module documentation can feed you bad ideas about this enabling multithreading or being a good idea for routine use; in fact it doesn't affect threading at all and I'd run screaming from any module written by an author confused enough to think it's related even tangentially to multithreading. Since you really shouldn't be doing this all the time, I actually recommend doing it manually in a Perl-like language, or switching to a language that has much better support for this style if at all possible. YMMV.

24 points by PieSquared 16y ago

call/cc was introduced, as i understand it, as a means of formalising goto in this paper: Denotational semantics of goto: An exit formulation and its relation to continuations. Cliff B. Jones. http://www.springerlink.com/content/f340274565373810/ http://www.springerlink.com/content/f340274565373810/ this implementation of yield in scheme reminds me of the procedure linkage table in ELF executables, roughly in C: goto *current_entry_point then update current_entry_point on return (in the ELF PLT this is a one shot update).

carterschonwald 16y ago
actually it goes back even farther! ftp://ftp.cs.cmu.edu/user/jcr/histcont.pdf has a history written by John Reynolds, probably the world's most senior (and baller in the sense of doing amazing work) among currently active programming language theoreticians. Quote from pages 2-3 of the linked pdf: Apparently, the earliest description of a use of continuations was given by Adriaan van Wijngaarden (Director of the Mathematisch Centrum in Amsterdam) in September 1964, at an IFIP Working Conference on For- mal Language Description Languages held in Baden bei Wien, Austria. A written version of this talk, along with a transcript of the discussion that followed, appears in the conference proceedings [45]. Van Wijngaarden’s goal was to formulate a preprocessor that would translate Algol 60 into a more restricted sublanguage. The final stage of the preprocessing was (what we would now call) a transformation of proper procedures into continuation-passing style (CPS) [41], with an at- tendant elimination of labels and goto statements. (An earlier stage of the preprocessing replaced function procedures by proper procedures.) As van Wijngaarden described the transformation: Provide each procedure declaration with an extra formal param- eter — specified label — and insert at the end of its body a goto statement leading to that formal parameter. Correspond- ingly, label the statement following a procedure statement, if not labeled already, and provide that label as the correspond- ing extra actual parameter. [45]
- dododo 16y ago
  oops. you're right. i provided a bad reference. sorry!

philh 16y ago

This doesn't require call/cc - you can do it with just closures (I've done it in perl, for example). It's also not as powerful as yield, in that it requires the list of return values to be precomputed. However, call/cc could be used to implement something of equivalent power to yield.

carterschonwald 16y ago
to be fair, anything you can do with call/cc (or even delimited continuations, or whatever) can be done with closures, its just a matter of being willing to write all of your code in the continuation passing style :-). Please see the linked article ftp://ftp.cs.cmu.edu/user/jcr/histcont.pdf or wikipedia for further reading.
- philh 16y ago
  Yes, but that seems a trivial application of "lambda calculus is turing-complete" (or of some similar statement, if that one doesn't quite work). CPS is a slight improvement on that theorem, but not particularly relevant. Here, we have a piece of code which relies on both closures and continuations, and which is less clear than the equivalent code would be without continuations.
jerf 16y ago
A closer equivalent in perl, and other similar languages with closures, is the manually-unrolled continuation: sub continuationish { my $args = shift; my $state = {args => $args, state => 'INIT'}; return sub { goto $state->{state}; INIT: { # initial setup... $state->{state} = 'NORMAL'; return $first_output; } NORMAL: { # do stuff if (!$almost_done) { return $next_thingy; } else { $state->{state} = 'TERMINATING'; return $next_thingy; } } TERMINATING: { $state->{state} = 'TERMINATED'; return $state->{last_thingy}; # set above somewhere } TERMINATED: { return $sentinal_value; } }; } Everywhere you'd use a variable, you have to use something out of $state. This works. Any function can be rewritten using this approach to become a "generator" in Perl or similar languages. (Just remember that for and while loops all ultimately compile to "goto"s, and just perform the transform yourself.) But... you'll come to appreciate continuations or Python's yield pretty quickly. I think there have been three functions in my ~10 years of perl programming where I deemed it worth jumping through these hoops. Nice tool, but if you're using it a lot something's wrong. There exist some modules that try to do this automatically, however I have had some trouble with them, and they have the major problem that they end up being relatively opaque, often involving things like source code filters. Also, the module documentation can feed you bad ideas about this enabling multithreading or being a good idea for routine use; in fact it doesn't affect threading at all and I'd run screaming from any module written by an author confused enough to think it's related even tangentially to multithreading. Since you really shouldn't be doing this all the time, I actually recommend doing it manually in a Perl-like language, or switching to a language that has much better support for this style if at all possible. YMMV.