4 ms·

Coroutine iters in Common Lisp

59 points by codr4life 10y ago

ykm 10y ago
Shameless plug: I had created a similar library[0] for common lisp, though it didn't use conditions and restarts, also lacked a definitive yield construct. It still is profound how a major feature for other programming language is trivial to add to common lisp. [0]: https://github.com/ykm/cl-iterators https://github.com/ykm/cl-iterators
- codr4life 10y ago
  But you still require extensions to cut up the algorithm in discrete blocks, right? Much thanks to macros, as usual; without that support, the approach wouldn't really be feasible for general purpose use.
  - ykm 10y ago
    Hmmm, frankly its just a CLOS object, with the defmethods controlling the iteration. I tried to model the object like Python iterators, however the API ended up a bit more like Haskell.
    - codr4life 10y ago
      Aight, just to clarify; the step wise, stuttering experience that normally comes with extending iterators is what I'm trying to get away from here :)
ScottBurson 10y ago
I have long thought that a coroutine mechanism was one of the most unfortunate omissions from the ANSI Common Lisp standard. The Lisp Machines had a mechanism called "stack groups" that supported efficient coroutines, but I guess it wasn't considered critical for Common Lisp to have such a thing. As you've noticed, though, adding coroutines in a way that's general, efficient, and portable is very hard.
- codr4life 10y ago
  Indeed, I have made the same experience the hard way by trying all other ways to get there. It's one of the few things that I can't seem to pull off without help from above in Lisp. I'll settle for faster conditions for iters, but oh how I would have loved to do green threads with the same ease.
- kazinator 10y ago
  Coroutines are a hack that is inferior to both real threads (OS supported, true concurrency) and delimited continuations (are functions that multiply instantiate, compose and recurse). Both of these mechanisms can easily simulate coroutines. Many Common Lisp implementations have threads so effectively, Common Lisp de facto supports coroutines.
  - codr4life 10y ago
    I guess you could implement generators and cooperative scheduling (which are useful abstractions with their own strengths, not inferior alternatives to threads) using threads. I never tried myself, but it feels backwards to me; like using 'loop' to iterate a list.
  - ScottBurson 10y ago
    > Coroutines are a hack that is inferior to [...] real threads I don't agree. Sometimes you don't want to pay the price of the OS context switch. Anyway, in the context of the ANSI spec, threads were out of scope, but they could have done coroutines anyway. > ... and delimited continuations But CL doesn't have these, even de facto. Yes, there's CL-Cont, but it's pretty slow.
  - codr4life 10y ago
    I went ahead and brain dumped the most obvious multi-threaded solution I could come up with, to get some performance facts to go with all the rumors. It comes out roughly 5x slower than using conditions/restarts. Just in case someone was wondering where we are atm...
kazinator 10y ago
TXR Lisp is a dialect with CL roots, supporting delimited continuations. They can be used directly via a lower-level API or via the obtain/yield mechanism. http://www.nongnu.org/txr/txr-manpage.html#N-01C4E6B4 http://www.nongnu.org/txr/txr-manpage.html#N-01C4E6B4 Here is an example of obtain/yield wrapped in the object system to create green-thread-like objects: http://www.nongnu.org/txr/rosetta-solutions-main.html#Synchronous%20concurrency http://www.nongnu.org/txr/rosetta-solutions-main.html#Synchr...
- codr4life 10y ago
  Interesting, never heard of TXR before. Too close for comfort on first blush though, changing arbitrary details in existing programming languages divides. Even having both Scheme and Common Lisp so close together takes a lot of energy that could be used more constructively. Thanks for the links.
  - kazinator 10y ago
    Oh well; I'm not interested in making a conforming implementation of ANSI Lisp. Some things are worth throwing out. For instance setq and setf are "onions in the varnish". Lisp has a set function which is rarely used. Because it exists, we cannot give the general assignment operator the name it wants: set. The q in setq refers to its historic relationship with set: "like set but with the var implicitly quoted". This relationship broke decades ago when Lisp went lexical: (setq x y) is (set 'x y) only when x is a dynamic var. And of course setq is redundant since every setq can be replaced with setf, and setf even replaces set since symbol-value is an accessor. Can I be blamed for not wanting to reproduce this baggage and just having one set macro? It may seem like a small thing, but most programmers are used to assignment just being =. The name "set" is still reasonably acceptable. We see it in vi, some shells, and such. "set" with a gratuitous letter added for fifty-year-old reasons: not so much.
    - codr4life 10y ago
      Me neither, as much as I love that standard and the people involved in making it happen :) Just getting the implementation details right is at least a life time effort. And like you say, a lot could be improved and some is still missing. But as a solid, mature foundation; it beats the mine field that is exploratory language design.
vseloved 10y ago
I presented a very similar implementation here: http://lisp-univ-etc.blogspot.com/2016/05/improving-lisp-ux-one-form-at-time.html http://lisp-univ-etc.blogspot.com/2016/05/improving-lisp-ux-... Still, a lot of interesting questions remain, which are discussed here: http://lisp-univ-etc.blogspot.com/2016/05/improving-lisp-ux-one-form-at-time.html#comment-2682947352 http://lisp-univ-etc.blogspot.com/2016/05/improving-lisp-ux-...

59 points by codr4life 10y ago

ykm 10y ago

Shameless plug: I had created a similar library[0] for common lisp, though it didn't use conditions and restarts, also lacked a definitive yield construct. It still is profound how a major feature for other programming language is trivial to add to common lisp. [0]: https://github.com/ykm/cl-iterators https://github.com/ykm/cl-iterators

codr4life 10y ago
But you still require extensions to cut up the algorithm in discrete blocks, right? Much thanks to macros, as usual; without that support, the approach wouldn't really be feasible for general purpose use.
- ykm 10y ago
  Hmmm, frankly its just a CLOS object, with the defmethods controlling the iteration. I tried to model the object like Python iterators, however the API ended up a bit more like Haskell.
  - codr4life 10y ago
    Aight, just to clarify; the step wise, stuttering experience that normally comes with extending iterators is what I'm trying to get away from here :)

ScottBurson 10y ago

I have long thought that a coroutine mechanism was one of the most unfortunate omissions from the ANSI Common Lisp standard. The Lisp Machines had a mechanism called "stack groups" that supported efficient coroutines, but I guess it wasn't considered critical for Common Lisp to have such a thing. As you've noticed, though, adding coroutines in a way that's general, efficient, and portable is very hard.

codr4life 10y ago
Indeed, I have made the same experience the hard way by trying all other ways to get there. It's one of the few things that I can't seem to pull off without help from above in Lisp. I'll settle for faster conditions for iters, but oh how I would have loved to do green threads with the same ease.
kazinator 10y ago
Coroutines are a hack that is inferior to both real threads (OS supported, true concurrency) and delimited continuations (are functions that multiply instantiate, compose and recurse). Both of these mechanisms can easily simulate coroutines. Many Common Lisp implementations have threads so effectively, Common Lisp de facto supports coroutines.
- codr4life 10y ago
  I guess you could implement generators and cooperative scheduling (which are useful abstractions with their own strengths, not inferior alternatives to threads) using threads. I never tried myself, but it feels backwards to me; like using 'loop' to iterate a list.
- ScottBurson 10y ago
  > Coroutines are a hack that is inferior to [...] real threads I don't agree. Sometimes you don't want to pay the price of the OS context switch. Anyway, in the context of the ANSI spec, threads were out of scope, but they could have done coroutines anyway. > ... and delimited continuations But CL doesn't have these, even de facto. Yes, there's CL-Cont, but it's pretty slow.
- codr4life 10y ago
  I went ahead and brain dumped the most obvious multi-threaded solution I could come up with, to get some performance facts to go with all the rumors. It comes out roughly 5x slower than using conditions/restarts. Just in case someone was wondering where we are atm...

kazinator 10y ago

TXR Lisp is a dialect with CL roots, supporting delimited continuations. They can be used directly via a lower-level API or via the obtain/yield mechanism. http://www.nongnu.org/txr/txr-manpage.html#N-01C4E6B4 http://www.nongnu.org/txr/txr-manpage.html#N-01C4E6B4 Here is an example of obtain/yield wrapped in the object system to create green-thread-like objects: http://www.nongnu.org/txr/rosetta-solutions-main.html#Synchronous%20concurrency http://www.nongnu.org/txr/rosetta-solutions-main.html#Synchr...

codr4life 10y ago
Interesting, never heard of TXR before. Too close for comfort on first blush though, changing arbitrary details in existing programming languages divides. Even having both Scheme and Common Lisp so close together takes a lot of energy that could be used more constructively. Thanks for the links.
- kazinator 10y ago
  Oh well; I'm not interested in making a conforming implementation of ANSI Lisp. Some things are worth throwing out. For instance setq and setf are "onions in the varnish". Lisp has a set function which is rarely used. Because it exists, we cannot give the general assignment operator the name it wants: set. The q in setq refers to its historic relationship with set: "like set but with the var implicitly quoted". This relationship broke decades ago when Lisp went lexical: (setq x y) is (set 'x y) only when x is a dynamic var. And of course setq is redundant since every setq can be replaced with setf, and setf even replaces set since symbol-value is an accessor. Can I be blamed for not wanting to reproduce this baggage and just having one set macro? It may seem like a small thing, but most programmers are used to assignment just being =. The name "set" is still reasonably acceptable. We see it in vi, some shells, and such. "set" with a gratuitous letter added for fifty-year-old reasons: not so much.
  - codr4life 10y ago
    Me neither, as much as I love that standard and the people involved in making it happen :) Just getting the implementation details right is at least a life time effort. And like you say, a lot could be improved and some is still missing. But as a solid, mature foundation; it beats the mine field that is exploratory language design.

vseloved 10y ago

I presented a very similar implementation here: http://lisp-univ-etc.blogspot.com/2016/05/improving-lisp-ux-one-form-at-time.html http://lisp-univ-etc.blogspot.com/2016/05/improving-lisp-ux-... Still, a lot of interesting questions remain, which are discussed here: http://lisp-univ-etc.blogspot.com/2016/05/improving-lisp-ux-one-form-at-time.html#comment-2682947352 http://lisp-univ-etc.blogspot.com/2016/05/improving-lisp-ux-...