6 ms·
Writing a Lisp: Continuations
- pmoriarty 9y agoDo any non-Lisp/Scheme languages have continuations?
- grzm 9y agoWikipedia provides a list of continuation implementations in a variety of languages: https://en.wikipedia.org/wiki/Continuation#Programming_language_support https://en.wikipedia.org/wiki/Continuation#Programming_langu... Some of these are first-class continuations; others support continuation passing style.
- nathell 9y agoAs an example, here's a simple proof-of-concept webapp I wrote in Ruby, based on continuations: https://github.com/nathell/ruby-continuation-webapp https://github.com/nathell/ruby-continuation-webapp
- deleted 9y ago[deleted]
- rprospero 9y agoHere's the obligatory "Haskell has a monad for that" comment http://hackage.haskell.org/package/mtl-2.2.1/docs/Control-Monad-Cont.html http://hackage.haskell.org/package/mtl-2.2.1/docs/Control-Mo...
- kmill 9y agoSpeaking of monads, one of the themes in Prof. Sussman's "Adventures in advanced symbolic programming" course was that many metacircular evaluator experiments can be set up by using mostly the same core evaluator but swapping out the underlying monad. I'm pretty sure I implemented the "ambivalent operator" that way, using the list monad (in Scheme), but when we lifted amb to the host Scheme, it needed call/cc to be able to use the built-in control flow. One thing I like about Haskell is that it's designed so that adding new control flow is not a big deal -- just design a monad. In Scheme it seems to be more work to get it all right.
- penpapersw 9y agoThat kind of feels like cheating though. I mean, the complicated part of a continuation is that it restores the same context and state that the app had right before the plunge. But Haskell inherently doesn't have "floating" state, it's all self-contained within each parameter. So in Haskell it's more or less a fancy goto-statement.
- mbrock 9y agoThe linked module defines a "monad transformer" that can wrap other monads with a continuation-capturing layer. This means, among other things (Haskell's solution is awesomely general) that you can indeed use it with state, if you compose it with the state monad, or even the IO monad. (The bottom of the documentation page has a contrived example of this.)
- white-flame 9y agoThere's lots of continuation styles & libraries, but most are delimited continuations. In my opinion, delimited ones are far cleaner to implement and to work with than the more universal continuations of Scheme. call/cc, as a product of Scheme's efforts on simplicity[1], has to encompass a larger amount of low-level state than most real-world uses of it use (and it's used far less frequently in "real applications" than academically). Having a better suite of flow control forms and keeping continuations delimited has far less constraints on the design of the runtime and leads to more focused and explicit operation without a bunch of implicit unused implications hanging around. [1 = simplicity as in fewer built-in operations]
- michaelsbradley 9y agoAny recommendations for write-ups on how delimited continuations are implemented?
- convolvatron 9y agomy reading is that by 'delimited continuations', white-flame is just referring to explicit closures and function calls. which lets you build up event-driven machines in any language that supports closures. the distinction is that in scheme, where (at least in the standard implementation) each function call takes an implicit continuation and the code is everted using a bulk cps-transform before being interpreted or further compiled. in this later case, its possible to use call/cc to create a continuation at any point in a 'normal' program, without having to construct the control flow explicitly. its this 'continuations everywhere' approach that can burden the runtime with a lot of consequences, possibly even precluding the use of a stack at all depending on the implementation. in the former case you can basically do by-hand cps or event-handling in anything. asm, C, c++, python (3), go, js..
- Johnny_Brahms 9y agoCheck out Andy wingo's blog. He implemented delimited continuations for guile, and provides lots of sources for his implementation. And ofcourse everything by Oleg Kiselyov
- 9y ago
- tonyg 9y agoThe Rhino javascript implementation has continuations. Chris Double once stuck it in Jetty, and I threw together a horrifying proof-of-concept Seaside-like continuation-based web programming library based on that: http://homepages.kcbbs.gen.nz/tonyg/lshift_archive/a-rhino-at-the-seaside-20060718.html http://homepages.kcbbs.gen.nz/tonyg/lshift_archive/a-rhino-a... As a proof-of-concept, it was fun, but that's as far as it went :-)
- doublec 9y agoRhino was a fun JS system. One of the continuation examples I did for a talk was migrating threads in Rhino: https://bluishcoder.co.nz/2006/06/11/migrating-javascript-threads.html https://bluishcoder.co.nz/2006/06/11/migrating-javascript-th.... Start a thread on one machine, serialize the continuation and send it across the network and resume it on that machine.
- mamcx 9y agoI wonder how it could affect the performance of a interpreter if is build around (internal) continuations, so all the other cool things as exceptions are made on top of it. I try a small demo, and the complexity of the interpreter get high fast. Also, if not continuation, what else can be used?
- penpapersw 9y agoRuby has `#callcc` which produces first-class continuations AFAIK https://ruby-doc.org/core-2.2.0/Continuation.html https://ruby-doc.org/core-2.2.0/Continuation.html
- paulddraper 9y agoYep. Relatedly, Ruby also has fibers.
- bbcbasic 9y agoC# has async/await and TPL, e.g. .ContinueWith(...) Javscript has promises and async/await
- bbcbasic 9y agoIf anyone can feedback on why my comment is wrong I'd appreciate it. I know we're not meant to comment on downvoting but I want to uncover the error in my understanding of this subject because at least 3 people downvoted but there is no reply yet??
- AstralStorm 9y agoAsync/await does not allow you to suspend a computation and then resume it, and it is not easy to chain.
- bbcbasic 9y agoThanks. I took continuation to include cases where you respond to asynchronous call backs while the program is still executing, in which case suspension isn't needed.
- somethingsimple 9y agoIf you implement your own awaiter with INotifyCompletion [1], you get the continuation as an Action that you can invoke as you will. TBH I haven't done it, but I believe you could use that to implement something akin to call/cc. [1] https://msdn.microsoft.com/en-us/library/system.runtime.compilerservices.inotifycompletion(v=vs.110).aspx https://msdn.microsoft.com/en-us/library/system.runtime.comp...
- protomyth 9y agoSome Smalltalks have them and they are used by Seaside but made optional in Seaside 3.0 because of the platforms that don't have them.
- tbodt 9y agoMy favorite part of this blog post is the Fira Code webfont
- kpil 9y agoContinuations are strangely underused, as they enables writing long-living processes in a simple way, without having to keep them in running in a thread, or even in memory. Then a real programming language can replace all "business processing" crap languages. Let's say you write a framework that escapes to a continuation whenever the "process" is waiting for Futures or Promises to complete, and returns the thread to a pool. Depending on what you are waiting for, such as webhooks, asynch events/messages, or with some work even outstanding network requests ( if it's meaningful ), it would be possible to serialize the continuation to storage, potentially restore it on another machine, weeks later. With some bookkeeping, it would be possible to also store what Futures have been completed, and what the continuation is currently waiting for, so it would be possible to keep track of the progress of the long running process, and use that information to show a nice status report.
- pimeys 9y agoWe are doing exactly this in my current company. There is a quite nice language called Orc for this. A site can do IO, we can serialize the state and return to it weeks later when we have a triggering event.
- kazinator 9y agoContinuations have a context which takes up space in memory. That context keeps a reference on an environment (or chain of environments) containing all the resources which must be there when the continuation is invoked.
- panic 9y agoIf only Brendan Eich had ended up "doing Scheme" in Netscape as he was originally recruited to! (https://news.ycombinator.com/item?id=2786720 https://news.ycombinator.com/item?id=2786720)
- coldtea 9y agoJavascript survived (and eventually caught on) not just because it was the "only game in town" for the web, but also because it was familiar. If Eich indeed had produced a scheme, then it would have been superseded and replaced by another algol-derived language by browser makers soon -- and users would have flocked to that.
- e40 9y agoAre there any continuation implementations in Common Lisp?
- xfer 9y agothere is cl-cont which works by CPS transformation, so if performance is your concern it's not ideal.
- ScottBurson 9y agoYes, cl-cont by our very own Slava "coffeemug" Akhmechet. Unfortunately, a recent site rebuild at common-lisp.net seems to have left the project page blank; nor do I see a cl-cont repo on Slava's Github page. It's Quicklisp-installable, though.
- Blackthorn 9y agoNot first-class, no. They all depend on using macros to turn your code into CPS. You'd need some sort of special form that CL doesn't have in order to do better than that.
- simplify 9y agoI remember trying to learn continuations during my CS degree, and evidently even today I still don't understand them. The examples don't seem to help either – how exactly does the control flow function?
- kmill 9y agoYou know how in Python the "yield" statement is actually an expression and can be sent values using "next"? Imagine there is a special "yield" called "call-with-current-continuation" that can be used anywhere (not just in generators) which bundles everything up and makes a generator-like thing called a "continuation." This continuation object can be called later on, like using "next" in Python. Unlike generators, though, continuations can usually be resumed repeatedly, always resuming at the same point where the call-with-current-continuation expression was. A weird thing is that call-with-current-continuation doesn't yield back to something; it yields to the function given to call-with-current-continuation.
- coldtea 9y agoWould that be like having a yield statement AND passing a context (e.g. binding a this that represents "current-continuation")?
- kmill 9y agoHere are two examples in Python syntax, assuming "yield" is no longer a keyword. def f(): def receiver(yield): yield(2) # yield jumps out of the 'receiver' function and never returns print("This never prints") x = callcc(receiver) return x+1 print(f()) # f returns 2+1 # backtracks stores (continuation,[values]) pairs. Whenever a computation fails, we pull out another # value from the list and feed it to the continuation. The idea is to perform a depth-first search. backtracks = [] def fail(): """Aborts the current continuation and backtracks to another alternative stored in backtracks.""" if not backtracks: raise Exception('amb ran out of alternatives') yield, alternatives = backtracks.pop() alt = alternatives.pop() if alternatives: # this continuation still has alternatives, so put them back on the list in case of a future 'fail' backtracks.push((yield, alternatives)) yield(alt) def amb(*alternatives): """The "ambivalent operator." The arguments to amb are alternatives, and the return value of amb is an alternative which makes the future computation not fail.""" if not alternatives: fail() def receiver(yield): backtracks.append((yield, alternatives)) fail() return callcc(receiver) def expect(b): if not b: fail() def test_amb(): """Let's find a Pythagorean triple.""" x = amb(*range(1,100)) y = amb(*range(1,100)) z = amb(*range(1,100)) expect(x**2 + y**2 == z**2) return (x,y,z) # We can print out all the Pythagorean triples. trip = test_amb() print("(x,y,z)=(%s,%s,%s)" % trip) fail() # fail every time so it keeps backtracking, but the side effect of printing out remains