💾 Archived View for gemini.sh0.xyz › log › 2014-06-14-explaining-continuations.gmi captured on 2024-09-29 at 00:37:25. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
The other day I was reading through [/r/scheme][1] and found an interesting post about [continuations][2]. The post did a pretty good job of showing some examples of how to use continuations, but seemed to miss the mark explaining how they work and how to add them into your design. So I thought why not take a crack at it.
"A Continuation is an abstract representation of the control state of a computer program." Thats how [Wikipedia][3] explains it. So it is a snapshot of the current state of your application at some given point in time. But how can that be useful?
When using Continuations I like to think about what they can do for me. Image that you had a spool of string, string that can traverse space and time. You can tie one end of this string to a specific location in Space-Time and as you go on your way the spool unwinds. Throughout your day you move further and further from where you tied off that string but you always have a connection to that moment in time.
There is another special property to this string. If you pull on this string you magically get whisked back to that point in Space-Time where you first tied it off. You also are able to retain the information you learned over the day.
Imagine you decide to go for a long hike and wind up getting attacked by a bear, you can pull on your string and get sent back to the moment you first set off on your adventure. If you decide to go out for the walk again you remember where the bear was hiding and can take a completely new path. This time without worrying about running into that bear.
Lets think about a function, one that takes in a list of numbers and returns back a list of reciprocals. Sounds easy enough.
(define (map-/ lst)
(map (lambda (x)
(/ 1 x))
lst))
The only problem is when one of the numbers is Zero. We could test for a zero denominator and cons in a false, but our result would no longer be a list of reciprocals.
(define (map-/ lst)
(map (lambda (x)
(if (zero? x)
#f
(/ 1 x)))
lst))
(let ([results (map-/ lst)])
(if (member #f results)
#f
results))
This works but we are running through the list twice: `map-/` and `member`. If only we could do both tasks at the same time. If only we could undo the generation of our reciprocal list if we ran into a zero.
Looking at our latest version of `map-/` if we hit the `(zero? (car lst))` case it would be great if we could just undo everything. Using continuations we can.
`(call/cc)` takes in a function with a single parameter, our magic string. Really its a call to restore our state to where `call/cc` is.
(define (odd-test x)
(call/cc
(lambda (k)
(when (odd? x) (k)) ; If Odd, pull string
(displayln "Only evens get here"))))
If we call this functionwith an odd number we hit our test case and pull out of what we were doing. Better yet, if we passed a parameter to `(k)` then `call/cc` would return that value. Otherwise, as typical functional programming, the last value on the last line contained in the lambda will be returned when the execution of the body in `call/cc` completes.
So how can this help our `map-/` function? If we wrapped it up inside a `call/cc` we could go through our normal operation and if we hit the Zero test case pull out.
(define (map-/ lst)
(call/cc
(lambda (k)
(map (lambda (x)
(if (zero? x)
(k #f) ; Divide by zero, return #f
(/ 1 x)))
lst))))
If we run `map-/` with a list of positive numbers `call/cc` will return the result of `map`. If the list contains a Zero, it will return the value passed to `k`...`#f`.
(map-/ '(1 3 2)) ; -> '(1 1/3 1/2) (map-/ '(1 0 2)) ; -> #f
Unlike real time travel, what you do prior to going back has affect. How can this knowledge help up? We can do work and then go back keeping the current changes. If we do this over and over we can get very interesting results.
[Daniel Martins' Post][2] that started this all off gave an example of an iterator that uses continuations.
(define (iterate lst)
(define (state return)
(for-each
(lambda (item)
(let/cc state-cc
(set! state state-cc)
(return item)))
lst)
(return 'done))
(define (generator)
(call/cc state))
generator)
Lets start by looking at the `state` function. As we noticed in the previous example, this function fits the Continuation Passing format (a function that takes a single argument...a continuation argument). Inside it runs `for-each` on a list applying a lambda function. Notice the last call in the lambda is `(return item)`. This is the call that pulls us back to the original context where the continuation was created.
(define lst '(1 2 3 4))
(define (state return)
(for-each
(lambda (item)
(return item))
lst))
(call/cc state) ; -> 1
(call/cc state) ; -> 1
It looks as if our code works. `for-each` iterates over the list and when the first item is run we call our continuation function and return the item. But this doesn't really help us as we never can get past the first item.
What if we could change our state function so that the next time it is called we have moved on to the next item in the list. By using `let/cc` we get the current continuation. Since Scheme functions are really just variables you call, we could change the value of `state` to the current iteration in the loop.
(let/cc state-cc ; Takes our current stack (set! state state-cc)) ; and stores it in state
What does this do? We are using our magic string and tying it off inside our loop. When we pull on it we get yanked back inside the iteration of our loop. Essentially we are able to track our run through the `for-each`, return out of it with the current item and then later jump back in to pull the next item.
(define lst '(1 2 3 4))
(define (state return)
(for-each
(lambda (item)
(let/cc state-cc
(set! state state-cc)
(return item)))
lst))
(call/cc state) ; -> 1
(call/cc state) ; -> 2
To top it off Daniel packages it all up returning a function you can call that does the `(call/cc)` for us. This is a nice simple design using Continuations. In the spirit of this post we'll go one step further and make this into a real generator, not just an iterator.
A stream generator is a pattern that where you take an iterator function and an initial value to create an infinite list of results, each being the input for it's successor.
F(init) -> x1
F(x1) -> x2
F(x2) -> x3
...
F(xM) -> xN
Obviously we cannot actually create an infinite list as we would never be able to return it after generation as it would go on forever. What if we could create one of the items in our infinite list and return it using our continuation functionality. We could then come back and create the next item and return that.
Lets start by creating an infinite loop that runs our function.
(define f add1)
(define (state)
(let loop ([value 0])
(let ([x (f value)])
(loop x))))
Probably a bad idea to run this as it runs forever. So the next step is to add in our continuation passing
(define f add1)
(define (state return)
(let loop ([value 0])
(let ([x (f value)])
(return value)
(loop x))))
(call/cc state) ; -> 0
(call/cc state) ; -> 0
Again, we never get past that first call of `return`. If we could change `state` at each iteration we can get the result we are looking for. Since our loop is infinite we can do this forever.
(define f add1)
(define (state return)
(let loop ([value 0])
(let ([x (f value)])
(let/cc state-cc
(set! state state-cc)
(return x))
(loop x))))
(call/cc state) ; -> 0
(call/cc state) ; -> 1
(call/cc state) ; -> 2
Lets wrap this up so we can call `(generate f)` and get a nice object to iterate over. While we're at it we can add an option initial value to start our list.
(define (generate f [init 0])
(define (state return)
(let loop ([value init])
(let ([x (f value)])
(let/cc state-cc
(set! state stat-cc)
(return x))
(loop x))))
(define (generator)
(call/cc state))
generator)
(define numbers (generate add1))
(numbers) ; -> 0
(numbers) ; -> 1
(numbers) ; -> 2
(define twos (generate (lambda (x) (* 2 x)) 1))
(twos) ; -> 1
(twos) ; -> 2
(twos) ; -> 4
(twos) ; -> 8
It was pointed out to me by [jrapdx][4] that my `(generate)` example was very Racket specific. So here is an update that will make it work for pretty much any Scheme with `call/cc` support.
`let/cc` is a macro in Racket that generates the following code:
(let/cc k body ...+) (call/cc (lambda (k) body ...))
So we can replace the `let/cc` call with `call/cc` and a few extra lines and our generator turns into:
(define (generate f [init 0])
(define (state return)
(let loop ([value init])
(let ([x (f value)])
(call/cc (lambda (state-cc)
(set! state stat-cc)
(return x)))
(loop x))))
(define (generator)
(call/cc state))
generator)
Thanks [jrapdx][4] for the update.
There are tons of other situations to use continuations. Creating coroutines, exception handling, maintaining state in web-servers. But they all use the basic concept of exiting the current execution. Once you understand the basic concept all the other examples make a lot more sense.
Why are continuations so darn cool [2]
$ date: 2014-06-14 00:00 $
$ tags: programming, scheme, racket, continuations $
-- CC-BY-4.0 jecxjo 2014-06-14