4 ms·

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

by 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.
lmkg 16y ago
> it requires the list of return values to be precomputed. I thought Scheme's semantics were allowed to be lazy to some extent, but I'm unaware of the finer points of it. Would a conforming implementation allow being lazy in this instance? I definitely agree that this seems like a strange place to pull out continuations. I get the impression that the author started from wanting an example of continuations, rather than an implementation of yield. As other people have pointed out, continuations and closures are equivalently powerful given CPS, but continuations seem simply gratuitous for this example. Just to make my point, here's my Common Lisp implementation: (defun generator (list last-val) (lambda () (if list (pop list) last-val))) Scheme would have to roll its own Pop macro, but I don't see how that would require a raw continuation primitive.
- PieSquared 16y ago
  I'm the one who wrote the post, and in retrospect I can see why people would be a bit confused at this example. I started out wanting to explain my actual implementation of a 'yield' command. As I wrote the post, though, it grew overcomplicated and filled with explanations of Scheme's syntax macros, which was not at all my intention. I guess in simplifying the implementation I also lost a bit of the idea behind it. You do need continuations to implement a general-case yield; if you just want generators for a list, you can use closers (and be more efficient, too). Thanks to you (and to parent) for pointing that out; if you don't mind, I'll add mention of what you said to the blog post?
  - lmkg 16y ago
    By all means, go ahead =). I'm actually a fan of continuations, I just didn't see what the purpose was in the example that you gave. What would be helpful is an explanation of why a yield with continuations is more powerful than one with closures. That will probably require an explanation of what you mean by a "general-case yield" (I'm not that familiar with Python).
xtho 16y ago
Isn't it the very idea of the yield "command" that you don't have to generate a list in advance but create it's values as needed? Hence, a statement like "you don't need ... but you have to ..." sounds funny to me.

by philh 16y ago

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.

lmkg 16y ago

> it requires the list of return values to be precomputed. I thought Scheme's semantics were allowed to be lazy to some extent, but I'm unaware of the finer points of it. Would a conforming implementation allow being lazy in this instance? I definitely agree that this seems like a strange place to pull out continuations. I get the impression that the author started from wanting an example of continuations, rather than an implementation of yield. As other people have pointed out, continuations and closures are equivalently powerful given CPS, but continuations seem simply gratuitous for this example. Just to make my point, here's my Common Lisp implementation: (defun generator (list last-val) (lambda () (if list (pop list) last-val))) Scheme would have to roll its own Pop macro, but I don't see how that would require a raw continuation primitive.

PieSquared 16y ago
I'm the one who wrote the post, and in retrospect I can see why people would be a bit confused at this example. I started out wanting to explain my actual implementation of a 'yield' command. As I wrote the post, though, it grew overcomplicated and filled with explanations of Scheme's syntax macros, which was not at all my intention. I guess in simplifying the implementation I also lost a bit of the idea behind it. You do need continuations to implement a general-case yield; if you just want generators for a list, you can use closers (and be more efficient, too). Thanks to you (and to parent) for pointing that out; if you don't mind, I'll add mention of what you said to the blog post?
- lmkg 16y ago
  By all means, go ahead =). I'm actually a fan of continuations, I just didn't see what the purpose was in the example that you gave. What would be helpful is an explanation of why a yield with continuations is more powerful than one with closures. That will probably require an explanation of what you mean by a "general-case yield" (I'm not that familiar with Python).

xtho 16y ago

Isn't it the very idea of the yield "command" that you don't have to generate a list in advance but create it's values as needed? Hence, a statement like "you don't need ... but you have to ..." sounds funny to me.