4 ms·

I found this fascinating but I need an ELI5. ;-)

dragontamer 5y ago
call/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 ago
  You 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).
  - dragontamer 5y ago
    You're right: there's lots of little mistakes I have in that post. And I think the variable binding vs variable-values thing is a major mistake I left in there... and I appreciate the corrections. Hopefully my relatively low-effort translation is useful to someone out there. But yes, I do admit that I "err on the side of incorrect", trying to favor simplicity in the explanation instead.
- gpderetta 5y ago
  Interestingly it is relatively straightforward to implement one shot continuations in C++ (i.e. call/cc1), but your example implicitly relies on being able to invoke a continuation multiple times. You can sort of implement multishot continuations with fork (more than just a curiosity, that's how reversible debuggers work in fact).
Twisol 5y ago
There are two important ideas to pick up here, I think. First, functional programming prefers a reduction-based model of computation: the whole program text represents the current state of the program, and a "step" of computation corresponds to simplifying ("reducing") the expression in a well-defined way. Second, `call/cc` adds a novel reduction rule that behaves a bit like function application, but looks a bit backwards. (`shift` and `reduce` then generalize the basic idea, but use the same machinery.) In detail: Consider a program `fib 2`, which simply computes the third Fibonacci number and then exits. We can define `fib` like so (using Haskell-y syntax, which I find a little lighter for this purpose): fib n = fib' n 0 1 fib' 0 a b = b fib' n a b = fib (n - 1) b (a + b) If we run this program, what do the individual steps look like? print (fib 2) = print (fib' 2 0 1) -- Substitute the definition of fib = print (fib' (2 - 1) 1 (0 + 1)) -- Substitute the second clause of fib' = print (fib' 1 1 1) -- Simplify - and + (technically, this is two steps) = print (fib' (1 - 1) 1 (1 + 1)) = print (fib' 0 1 2) = print 2 -- Substitute the first clause of fib' = () This isn't just an analogy; this is exactly how an unoptimized interpreter could fully implement a simple functional language. There's no need for an actual call stack when evaluating this program: the program text itself describes "what to do next" (which is the point of a call stack). Now, what does `call/cc` do? Well, remember what function application does: we take something like `(\x. FOO) A` and substitute `A` into `FOO` where ever `x` appears, no matter how deep into the program it is (unless it's shadowed, i.e. not the same `x`). We could write this as `apply (\x. FOO) A` if we wanted, although by syntax rules we know that the first value in a call is the function to call. (The capitalized names could be entire other expressions, whereas `x` is just a variable name.) Similarly, if the whole program looks like `A (call/cc \x. FOO)`, we substitute `\y. A` into `FOO` wherever `x` appears (unless it's shadowed)`. It's a weird kind of function call, where the function is nested inside `call/cc` like normal, but the argument is everything outside `call/cc`. And since `A _` has got a value-shaped hole where the `call/cc` was, we know that if `FOO` is going to use it, it needs to provide it a value -- hence why we substitute `\y. A`, not just `A`. (So we have to fill the hole with the new variable name `y`.) print (call/cc (\x. x 42)) = (\x. x 42) (\y. print y) -- `\y. print y` is equivalent to `print`, = (\y. print y) 42 -- so I'll elide this expansion next time. = print 42 This example seems kind of useless -- call/cc did nothing! But what if we had more values to return than just `42` -- what if we had a whole bunch of things, and we wanted to run the same processing for all of them? print (call/cc (\x. x 42 >> x 101 >> x 0)) = (\x. x 42 >> x 101 >> x 0) print = print 42 >> print 101 >> print 0 (`>>` is just a Haskell operator for sequencing, like `;` in C or Java.) Now we've replicated the rest of our program based on each of the three values returned by the inner function. It's like we've bifurcated (trifurcated?) our program into multiple independent programs that continue from where the original program left off. (You might know that `fork` in Linux returns a different value depending on whether you're in the original process or in the spawned child process. This is very similar!) But what if we don't want to do everything in our program multiple times? What if we just want to do some of it for each value, but join everything back together at the end for some final processing? Well, `shift` and `reset` let you do that. The `shift` operator slots in where `call/cc` was, but you now get to choose how much of the rest of the program to replicate by placing a `reset` somewhere else in the program. You can wrap the whole program in `reset` to get the same behavior as `call/cc`, or you can scope it to a smaller portion: (reset (print (shift (\x. x 42 >> x 101 >> x 0)))) >> print "Done" = ((\x. x 42 >> x 101 >> x 0) print) >> print "Done" = (print 42 >> print 101 >> print 0) >> print "Done" (We definitely didn't want to print `Done` three times, right?) None of the program's behavior needed call/cc or shift / reset. They're fundamentally rewriting rules that let us give such a program a different form. Sometimes the forms we can achieve with call/cc are more readable or provide better modularity. Sometimes they don't (so we shouldn't use them!). Shift and reset let you write your own coroutine system like it was nothing, though, so it's certainly not without merit :)

call/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 ago
You 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).
- dragontamer 5y ago
  You're right: there's lots of little mistakes I have in that post. And I think the variable binding vs variable-values thing is a major mistake I left in there... and I appreciate the corrections. Hopefully my relatively low-effort translation is useful to someone out there. But yes, I do admit that I "err on the side of incorrect", trying to favor simplicity in the explanation instead.
gpderetta 5y ago
Interestingly it is relatively straightforward to implement one shot continuations in C++ (i.e. call/cc1), but your example implicitly relies on being able to invoke a continuation multiple times. You can sort of implement multishot continuations with fork (more than just a curiosity, that's how reversible debuggers work in fact).

Twisol 5y ago

There are two important ideas to pick up here, I think. First, functional programming prefers a reduction-based model of computation: the whole program text represents the current state of the program, and a "step" of computation corresponds to simplifying ("reducing") the expression in a well-defined way. Second, `call/cc` adds a novel reduction rule that behaves a bit like function application, but looks a bit backwards. (`shift` and `reduce` then generalize the basic idea, but use the same machinery.) In detail: Consider a program `fib 2`, which simply computes the third Fibonacci number and then exits. We can define `fib` like so (using Haskell-y syntax, which I find a little lighter for this purpose): fib n = fib' n 0 1 fib' 0 a b = b fib' n a b = fib (n - 1) b (a + b) If we run this program, what do the individual steps look like? print (fib 2) = print (fib' 2 0 1) -- Substitute the definition of fib = print (fib' (2 - 1) 1 (0 + 1)) -- Substitute the second clause of fib' = print (fib' 1 1 1) -- Simplify - and + (technically, this is two steps) = print (fib' (1 - 1) 1 (1 + 1)) = print (fib' 0 1 2) = print 2 -- Substitute the first clause of fib' = () This isn't just an analogy; this is exactly how an unoptimized interpreter could fully implement a simple functional language. There's no need for an actual call stack when evaluating this program: the program text itself describes "what to do next" (which is the point of a call stack). Now, what does `call/cc` do? Well, remember what function application does: we take something like `(\x. FOO) A` and substitute `A` into `FOO` where ever `x` appears, no matter how deep into the program it is (unless it's shadowed, i.e. not the same `x`). We could write this as `apply (\x. FOO) A` if we wanted, although by syntax rules we know that the first value in a call is the function to call. (The capitalized names could be entire other expressions, whereas `x` is just a variable name.) Similarly, if the whole program looks like `A (call/cc \x. FOO)`, we substitute `\y. A` into `FOO` wherever `x` appears (unless it's shadowed)`. It's a weird kind of function call, where the function is nested inside `call/cc` like normal, but the argument is everything outside `call/cc`. And since `A _` has got a value-shaped hole where the `call/cc` was, we know that if `FOO` is going to use it, it needs to provide it a value -- hence why we substitute `\y. A`, not just `A`. (So we have to fill the hole with the new variable name `y`.) print (call/cc (\x. x 42)) = (\x. x 42) (\y. print y) -- `\y. print y` is equivalent to `print`, = (\y. print y) 42 -- so I'll elide this expansion next time. = print 42 This example seems kind of useless -- call/cc did nothing! But what if we had more values to return than just `42` -- what if we had a whole bunch of things, and we wanted to run the same processing for all of them? print (call/cc (\x. x 42 >> x 101 >> x 0)) = (\x. x 42 >> x 101 >> x 0) print = print 42 >> print 101 >> print 0 (`>>` is just a Haskell operator for sequencing, like `;` in C or Java.) Now we've replicated the rest of our program based on each of the three values returned by the inner function. It's like we've bifurcated (trifurcated?) our program into multiple independent programs that continue from where the original program left off. (You might know that `fork` in Linux returns a different value depending on whether you're in the original process or in the spawned child process. This is very similar!) But what if we don't want to do everything in our program multiple times? What if we just want to do some of it for each value, but join everything back together at the end for some final processing? Well, `shift` and `reset` let you do that. The `shift` operator slots in where `call/cc` was, but you now get to choose how much of the rest of the program to replicate by placing a `reset` somewhere else in the program. You can wrap the whole program in `reset` to get the same behavior as `call/cc`, or you can scope it to a smaller portion: (reset (print (shift (\x. x 42 >> x 101 >> x 0)))) >> print "Done" = ((\x. x 42 >> x 101 >> x 0) print) >> print "Done" = (print 42 >> print 101 >> print 0) >> print "Done" (We definitely didn't want to print `Done` three times, right?) None of the program's behavior needed call/cc or shift / reset. They're fundamentally rewriting rules that let us give such a program a different form. Sometimes the forms we can achieve with call/cc are more readable or provide better modularity. Sometimes they don't (so we shouldn't use them!). Shift and reset let you write your own coroutine system like it was nothing, though, so it's certainly not without merit :)