6 ms·
All you need is call/cc (2013)
- Koshkin 5y agoThis has reminded me of "closures are poor man's objects; objects are poor man's closures."
- b3morales 5y agoIndeed; a classic hacker koan. For the reader's reference: http://wiki.c2.com/?ClosuresAndObjectsAreEquivalent http://wiki.c2.com/?ClosuresAndObjectsAreEquivalent
- sillysaurusx 5y agoI like how no one voted yes and a bunch of people voted no.
- Jtsummers 5y ago"a bunch" is actually 2. What looks like a second nay vote is actually a rebuttal to the first. It seems most people just skipped the voting and went straight to the discussion.
- yodsanklai 5y agoThis was a "aha" moment for me, realizing objects and closures were the same thing.
- jerf 5y agoI think an even more interesting perspective is that they aren't the same thing, but they can be implemented in terms of each other. "Implemented in terms of each other" is an important metric, and in math that's not an unreasonable definition of "the same thing after all", but in engineering I would say it's not. If nothing else, the different affordances offered by each matter quite a bit in practice. Even in math that's still true, honestly, although in a different way.
- Koshkin 5y agoYou are not incorrect, but in C++ a closure (lambda) is quite literally an object (of an anonymous class).
- codemac 5y agoIt seems anyone that implements objects first, implements closures with them. Anyone that implements closures first, implements objects with them. Let over Lambda being the super fun book of implementing anything with closures.
- gpderetta 5y agovery pedantically anything that occupies memory and has an an address is an object in C and C++. If you mean in the OO way, I wouldn't call a lambda an object as it doesn't even do dynamic dispatch.
- OskarS 5y ago> I think an even more interesting perspective is that they aren't the same thing, but they can be implemented in terms of each other. I don’t know, I think that it’s perfectly reasonable even from an engineering/computer science perspective to say that they are literally the same thing, just viewed from two different perspectives. After all, what is an object? It’s some code, with bundled data. What is a closure? It’s some code… with some bundled data. I think it’s fair to say that this is a “is it a vase or two faces?” situation. You’re looking at the same image, just seeing it from different perspectives.
- sullyj3 5y agoOne key difference is that usually the captured values in a closure can't be mutated.
- pritambaral 5y agoI don't know where you're getting that from. In lambda calculus — where closures were first developed — there's no restrictions against mutation of captured variables or values.
- ncmncm 5y agoExcept, they aren't the same thing at all. A closure could be an object, or not. An object could be a closure, or not. The "aha" should be that it doesn't matter what you call it, what matters is what you can do with it.
- gpderetta 5y agosomehow I have no issues understanding call/cc, but shift reset has never clicked for me.
- oshiar53-0 5y agoYou can basically think of call/cc as subroutine + return/throw (break out of control structures), and delimited continuations as yield + next/send in Python. Of course this explanation is heavily simplified.
- ilammy 5y agoYou sound a bit like those people, “git is just directed acyclic graph of objects, it’s all that simple”.
- jasomill 5y ago“A monad is a monoid in the category of endofunctors, what's the problem?” http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html http://james-iry.blogspot.com/2009/05/brief-incomplete-and-m...
- wbl 5y agoThe difference is that that formulation is exactly correct whereas the other ones are not.
- kazinator 5y agoIs git necessarily acyclic? Or is it just that nobody has bothered to contrive a git repo with cycles? It seems possible in principle: via a kind of quining, a git commit can be created whose parent hash is its own. It involves a bit of a tough search.
- anyfoo 5y agoIt’s very likely specified as an acyclic graph (because, without checking, I see no reason why it would not be). So if you made a cyclic graph it would be wrong. It’s possible, likely even, that a lot of git’s implementation and associated tools don’t check for that, because it’s very hard[1] to achieve, but that just means stuff would break in more non-obvious ways. [1] Constructing a cyclic git graph means finding a hash collision, and git uses SHA1 which is known to have weaknesses. With another hash algorithm it might be “practically impossible” instead of “very hard”.
- tempodox 5y agoMore material about this fascinating topic: http://okmij.org/ftp/continuations/ http://okmij.org/ftp/continuations/ Has many articles and some code in OCaml, Haskell, Scheme.
- martinflack 5y agoI found this fascinating but I need an ELI5. ;-)
- dragontamer 5y agocall/cc is a widget from Scheme / Lisp is a glorified come_here statement (where "come_here" is roughly the exact opposite of a "goto" statement). Its gloriously complicated but its applications are seemingly endless. call/cc calls function "f" with a "come_here" label. Later, if you call the label, you return to the "come_here" point. call/cc saves off the stack-frame, so the "come_here" executes exactly as before (all local variables remain the same as they were before). ------ In C++ (call/cc doesn't exist, but we can imagine it in C++ lambdas) int f(auto come_here){ come_here(25); // call the "come_here" function with the parameter 25 } ... int x; x = call/cc(f); // x now equals 25, because f called come_here with 25. We can imagine the "come_here" function to be the exact line of code "x = call/cc". Now funny things can happen if you do ... funny things. int g(auto come_here){ some_global_variable = come_here; // Yeah, lets store this come_here label off for later. return 0; // Notice, come_here hasn't been called yet. Return 0 normally. } int x; x = call/cc(g); // defaults to the 0, for the "Return 0" in g. if(x < 100){ some_global_variable(x+1); // Loop back to the x=call/cc command, and set x+1. } Look Ma, I created an overly complicated while loop! --------- EDIT: Now for fun, try _writing_ try, catch, finally statements (from Java). By saving off the right labels in the right order, you can experiment with try/catch, or other complicated maneuvers (ex: the "Ambiguous" operator, often named "amb"). This call/cc exists because scheme is catering itself as a meta-language. A language to build other languages out of.
- ahefner 5y agoYou don't need the global variable (at least, the Scheme equivalent does not - I'm not going to lawyer over how variable capture would work in a hypothetical dialect of C++ that added call/cc). Any variable in scope to be captured by 'g' will do. There may be some misunderstanding in your statement "all local variables remain the same as they were before" - the same bindings will exist, but the values are not restored to their values prior to the call/cc, such that any subsequent changes to those variables will be preserved, permitting exactly the sort of thing you used as an example (albeit using a global variable).
- threepio 5y agoFrom the article: > The magic is that all Scheme code, by virtue of supporting the capture (and unwind) of delimited continuation Is that true? I thought Racket was the only Scheme (and maybe the only language in general) that supported delimited continuations.
- rscho 5y agoNope, there are others. Prolog, for example: https://www.swi-prolog.org/pldoc/man?section=delcont https://www.swi-prolog.org/pldoc/man?section=delcont
- pkhuong 5y agoYou can implement delimited continuations with regular call/cc and a mutable cell. Of course, like all abstractions based on raw call/cc, it's not modular: you can't do that and use the result inside, for example, a multitasking scheduler that itself uses raw call/cc as well. http://okmij.org/ftp/continuations/against-callcc.html#traps http://okmij.org/ftp/continuations/against-callcc.html#traps Closer to your point, there are a few other implementations that offer delimited continuations natively. See https://wingolog.org/archives/2010/02/26/guile-and-delimited-continuations https://wingolog.org/archives/2010/02/26/guile-and-delimited... for a 11 year old post on adding them to guile scheme.
- zzo38computer 5y agoAnother variant is "law of excluded middle" continuations. It gives you a function, but when you call that then it will go back and give you the value passed instead. You can implement this in terms of call/cc and vice-versa.
- dharmab 5y agoSlightly OT: Is the title a reference to "All You Need Is Kill", the source material for the Tom Cruise movie "Edge of Tomorrow"?
- unclesaamm 5y agoI'm guessing it's more likely, All You Need is Love, the Beatles song.
- Koshkin 5y agoBut "call" sounds closer to "kill" than to "love".
- daanx 5y agoThe modern way of call/cc and shift/reset is using Effect Handlers instead [1]. If you are interested in this, Ningning Xie and I give a tutorial about effect handlers (and more) at ICFP'21 tomorrow (Thursday 12:30 EST): <https://icfp21.sigplan.org/details/icfp-2021-tutorials/5/Programming-with-Effect-Handlers-and-FBIP-in-Koka https://icfp21.sigplan.org/details/icfp-2021-tutorials/5/Pro...> [1] <https://koka-lang.github.io/koka/doc/book.html https://koka-lang.github.io/koka/doc/book.html>
- rscho 5y agoInteresting! Can one have effect handlers in an untyped language such as scheme ?
- daanx 5y agoYes! a nice aspect of effect handlers is that they have an untyped dynamic semantics. Having said that, tracking effect types can be very beneficial, especially if you do interesting control flow like async/await for example.
- kazinator 5y agoI'm not convinced that effect handlers are other than (at most) just a different name for delimited continuations.
- jimsimmons 5y agoThey are much more structured than mere delimitation. That's the whole point
- daanx 5y agoI like the characterization that Andrej Bauer uses: "while relates to goto, as effect handlers to shift/reset" :-) That is, you indeed need delimited continuations to implement effect handlers, but they have more structure than, say, shift/reset. In particular, instead of being able to just yield (shift) with any function to an innermost context (reset), you can only perform a certain set of operations that are handled by a function defined in the handler. This gives various advantages, in particular, - you can give simple types to effect handlers (while shift/reset for example needs an answer type system), and you can use fine grained effect typing (instead of just a "shift" effect, you have "<exn,console>" effects) - you can do better reasoning as the set of operations is restricted - and (as a consequence) you have more opportunity to optimize them. In particular, tail-presumptive operations can be implemented to execute "in-place" without capturing the continuation for example. - finally, different effect handlers are compositional and can be combined freely (unlike shift/reset; for example shift aways shifts to the innermost reset so we cannot compose arbitrarily compose with multiple resets).