call/cc

From Esolang
Jump to navigation Jump to search
This article is a stub, which means that it is not detailed enough and needs to be expanded. Please help us by adding some more information.

call/cc is a strange language construct. It's common in LISP-like languages, notably Scheme. It has a reputation for being difficult to get an intuition for. Even though it may work through simple mechanisms, the effects are abstract and counter-intuitive. Its primary use is to change the result of an immutable value after it has already been calculated.

An attempt to put it in English (by someone who kinda understands it)

call/cc takes a single function as an argument. It calls that function with the "continuation" of this specific instance of call/cc. This continuation, when invoked, will automatically return from call/cc specifically, regardless of where it may be invoked. You can pass the continuation around, store it in variables, and do whatever - but once you invoke it, execution returns to the end of call/cc - and if you pass a value, that is the value that call/cc will now return.

If you understand exceptions, you can think of call/cc passing a special "exception" to the function given to it, and when that exception is invoked, call/cc returns with an optional value. The difference here is, though, that even if this special "exception" is invoked outside of call/cc, once it has already returned, execution will return to call/cc again.

If you understand goto, you can think of this as a higher-level equivalent - call/cc is passing a special "label" to the given function that you can then "goto" from any point in the program where the "label" value is accessible without breaking anything.

A cryptic metaphor

Picture a gift-wrapped present. Now, a magician creates a magical hat of time-travel. Any object put inside the hat will be sent through time to the exact moment when the present is unwrapped, and will become the contents of the gift. So, if the magician puts a rabbit in the hat, the gift will contain a rabbit. Instead of putting a rabbit in the present, the magician places her own magic hat. The receiver of the present opens the present and pulls out the magic hat. Into it he puts a lump of coal for no particular reason. The coal is sent back in time; suddenly, the receiver of the gift never pulled a hat out of the present, but instead a lump of coal. The magician's hat is nowhere to be found. call/cc is a magic hat, which leads to a specific moment in the execution of a program. If you feed the magic hat a value, the evaluation of a function, in other words, the unwrapping of the present, has that value. The program flow reverses or jumps forward to when it would evaluate the call/cc function, then returns the given value.

Continuations

The full name of call/cc is "call with current continuation". A continuation on its own is a way of storing what to do next. For example, when counting to 10, a program runs through each number in turn. Once it has counted to 8, it knows that it still needs to count 9 and 10. The information of counting onwards to 9 and 10, what to do next, is the continuation.

There exists a style of writing programs, called Continuation-Passing Style (CPS). In CPS, whenever a function finishes, it should return another function. The returned function is run afterwards, and it too will tell the program what function to execute next. Each of those functions is called a continuation, because it tells the computer what to do next. Control flow is explicit: an if/else conditional can be represented by returning either the if branch (as a function), or the else branch (as a function). The program will proceed by running the appropriate function, then proceeding with the continuation that results from the branch.

The explicit control flow can be a blessing for enabling time-travel-esque features. Consider a program that can run the TRUE branch of a function, then if something about the TRUE branch failed, simply run the FALSE continuation function, and continue as if it had picked FALSE all along. This can be viewed as time travel, but in logic programming is more commonly visualised as "backtracking", as if the program was navigating a maze and hit a dead-end. A program that can return to previous states is powerful; an interpreter that allows the program it is running to tell it to return to a previous point in the execution is a versatile interpreter.

With respect to call/cc

With continuations in mind, we can return to what call/cc does. call/cc is a function which accepts another function. The second function, which we'll call f, is to be passed the cc in call/cc, i.e. the current continuation. The current continuation is another function (bear with me here). Whatever f returns, is treated as the result of the entire call/cc function. However, if the continuation is ever called, lets say on the number 42, whatever argument is passed to it i.e. 42, will replace the return value of f. The interpreter will load the continuation of when it was working out the value of f, but this time it'll have a new return value, 42. Execution will continue as normal from there. If the continuation is then called on 43, then execution again returns to the continuation, giving 43 instead of either 42 or the original value of f. The continuation needn't ever be called, or it may be called before f finishes running in order to effectively return earlier than usual. It can be called more than once, and it will never get to return a value, because execution will always jump away from where its return value would be needed. Unless it is called, the continuation is just another function.

Examples may help to understand.

Technical Specs

Example code

Usage in Esolangs

call/cc basically makes any language that uses it an honorary esolang. However, this section will only cover intentional esolangs.

See Also