# Can we abstract control flow?

Last week, I visited a couple of my professors from Northwestern to chat and
help out with an interesting engineering “bootcamp” class they are teaching.
Beyond the nostalgia, those interactions brought me back to my days in college,
when I regularly felt this mixture of lighthearted fun and simultaneously an
overwhelming awe at learning new things I didn’t even have the cognitive
machinery to *imagine* before.

Maybe I’m blocking out the midterm anxiety, but still.

Switching to now, I’ve been using generators a bit more than usual lately and got curious about how they work. I’d skirted this rabbit hole in the past, but hadn’t dug further, so I decided to give it go without setting a practical goal. Sometimes, an exploration is a worthy end in itself.

Imagine being able to abstract control flow directly. What would that *mean*?

Let’s find out by learning about continuations! We’ll start with generators and dig deeper until we find fun, new stuff.

## Simple Example: Exceptions

There’s a common situation where normal control flow gets subverted: exceptions.

```
# ruby
> def buggy_code
> (0..10).each {|item| if item == 7; raise "oh no it's a 7!"; else; print item; end }
> end
=> :buggy_code
> begin
> buggy_code
> rescue => e
> print e.inspect
> end
0123456#<RuntimeError: oh no it's a 7!> => nil
```

Above, the `buggy_code`

method is being executed, but then the ruby interpreter
yields control to the error handler that wraps the `buggy_code`

invocation, with
a special `raise`

keyword. This can happen regardless of how deep down the
`buggy_code`

invocation is.

This seems like a really interesting way to think about control flow –– it’s like passing the ball to a different player who’s in a totally different part of the field without going through with your previously intended actions.

## More Involved Example: Generators

Now, an example of using generators to obtain even numbers:

```
# python 3.x
>>> import itertools
# infinite generator of incrementing even numbers
# note: the full range is unbounded -- it's realized one item at a time
>>> gen = (i for i in itertools.count() if i % 2 == 0)
# grab the first 10 even numbers
>>> next(gen)
0
>>> next(gen)
2
>>> list(itertools.islice(gen, 10))
[6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
```

Above, we use an already defined basic generator `itertools.count()`

which just
keeps counting up, and then we make use of it, taking the first 10 values. The
underlying range is infinite, but we’re able to do our work in a lazy way, one
item at a time.

That `(i for i in ...)`

expression is a
generator expression, similar to a list
comprehension (which is denoted by `[...]`

instead). Semantically, a generator
expression can be thought of as making an anonymous generator function and
calling it. And a generator function is a function that calls `yield`

in the
body somehow.

Here’s the implicit anonymous generator function that
`gen = (i for i in itertools.count() if i % 2 == 0)`

would make:

```
def __gen(exp):
for i in exp:
if i % 2 == 0:
yield i
gen = __gen(itertools.count())
```

That `yield`

behaves differently from a `return`

, it essentially makes the
invocation of the function produce a generator object, and that generator object
produces new values for consumers like `next(...)`

or `list(...)`

.

Isn’t it interesting how the control flow seemingly switches back and forth as
you keep calling `gen.next()`

?? It’s like a conversation, a boring one but still.

```
<- The generator does some work and yields control to the console.
-> We type some code and return it to the console with an 'enter'.
<- Then, the generator does some more of the remaining work
and yields control to the console again.
```

This is different from our usual experience with function invocations. Usually, invocations intuitively seem like they’re “one and done,” with some effects or returned values being the result.

## What’s the generator doing?

If we were to make that implicit generator object for real (for pedagogical reasons), it might look like this pseudo code:

```
class MyGenerator:
def __init__(self, expression):
self.expression = expression
def my_next_value(self):
## FAKE CODE
value, remaining_expression = $execute_until_yield(self.expression)
self.expression = remaining_expression
return value
my_gen = MyGenerator(lambda: $some_code_that_has_a_yield)
```

This fake generator object is providing step-by-step, resumable execution of an expression (meaning: any piece of computation, like imagine a function being passed as that argument that itself calls a whole host of other functions). It needs to know about how to execute until the next yield somehow… and it likely needs to hold onto the “remaining computation.”

When the consumer calls `my_next_value`

repeatedly, the `my_gen`

generator
object resumes execution of the original code, returns immediately with a value,
and pauses the remaining computation again.

But this is… something we don’t have a direct handle on. How would
`$execute_until_yield`

even work?

How do we get this kind of control over pausing-and-resuming computation?

And since it needs to be generalized for all possible code you could write, what does “remaining computation” really mean?

## Enter: Continuations

A continuation is “remaining computation,” essentially. It makes some sense, then, that a generator would be dealing with continuations. But how do we get more specific?

More and more, I turn to Scheme when building intuition.

Racket’s docs describe their evaluation model *so well*, I’ll quote them:

```
Racket evaluation can be viewed as the simplification of expressions
to obtain values. For example, just as an elementary-school
student simplifies
1 + 1 = 2
Racket evaluation simplifies
(+ 1 1) -> 2
```

Computation can be understood as simply repeated reduction of expressions down
to a level where we’re left with just values, a `value`

being anything that
can’t be reduced further.

Paraphrasing some other resources here – but basically, *operational semantics*
tries to answer “how is a program executed?”. There have been many presentations
of operational semantics, and one of them is reduction semantics (introduced by
Hieb and Felleison in ‘92).

The operational semantics for a programming language describe how a valid program is interpreted as sequences of computational steps. With the reduction semantics presentation, the description is a series of reductions.

Back to understanding basic evaluation:

```
Some simplifications require more than one step. For example:
(- 4 (+ 1 1)) → (- 4 2) → 2
------ -------
An expression that is not a value can always be partitioned into two
parts: a redex, which is the part that changed in a single-step
simplification (highlighted), and the continuation, which is the evaluation
context surrounding an expression.
In (- 4 (+ 1 1)), the redex is (+ 1 1), and the continuation is (- 4 []),
where [] takes the place of the redex. That is, the continuation says
how to “continue” after the redex is reduced to a value.
```

Continuations are described as the evaluation context surrounding some expression. But that’s just prose!

What does `(- 4 [])`

look like? It’s some kind of closed form that has a hole in
it. It looks like a lambda (anonymous function)!

So, continuations can be thought of as just functions!

Let’s apply this idea to understand the even number generators a bit more:

```
#lang racket
(require racket/generator)
(define evens
(generator
()
(let loop ([x 1])
(if (zero? (modulo x 2))
(begin
(yield x)
(loop (+ 1 x)))
(loop (+ 1 x))))))
;; and in the console:
> (evens)
2
> (evens)
4
```

Here’s one way to read the above if you’re unfamiliar with LISP-like languages:

- The literal values look like
`1`

,`0.5`

,`'c`

,`#t`

,`my-func`

,`#hash((a . 1) (b . 2))`

. - Function applications look like
`(foo bar ...)`

.`foo`

here is in the function application position (the head of the form), and the parens indicate that this is an s-expression.`bar ...`

are one or many arguments.

Alright, we see the familiar `yield`

here, inside an infinite iteration counting
up from 1.

Let’s say we invoke the generator once: `(evens)`

.

What happens is that the generator evaluates some code, produces some effects, and then yields control. In the background, there is a continuation, a function, representing the rest of the computation. Each time this generator is called, it’s then calling this implicit continuation and yielding control.

But how do you implement a generator?

## Introducing shift and reset

Racket provides a lot of firepower for us. I enlisted the help of my friend Max
(PhD student at Northeastern) to put all this power to good use. I had started
the exploration by just reading about `call/cc`

on wikipedia, and after enough
experimentation to figure that out and sharing that with Max, Max suggested
something even better: `shift`

and `reset`

.

What are `shift`

and `reset`

?

They are control operators that work together to allow you to do things like “non local return”. “The reset operator sets the limit for the continuation while the shift operator captures or reifies the current continuation up to the innermost enclosing reset” (from wikipedia, haha). But let’s unpack that.

When you have an expression you’re trying to compute, you essentially go from
the leaves to the root of the tree. For example, `(+ (+ 2 3) 4)`

is a tree with
`+`

at the root, and with `(+ 2 3)`

and `4`

as the leaves. So, the “remaining
computation” roughly corresponds to the earlier parts of the tree. Like in the
explanation about `redex`

and `continuation`

, the `redex`

here would be
`(+ 2 3)`

(`4`

is already reduced to a value and can’t be reduced, and the
only other leaf not already a value is `(+ 2 3)`

). And the continuation would be
`(lambda (x) (+ x 4))`

.

So, `reset`

marks the node of the tree until which the continuation is
delimited, and then `shift`

captures the continuation up to that point.

Let’s try to use `shift`

and `reset`

to figure them out:

```
;; some basics examples
> (require racket/control)
> (reset 3)
3
> (reset (shift k 1))
1
> (reset (shift k (k 1)))
1
;; now, the same buggy_code from above, but with shift/reset!
> (define (buggy-code)
(for-each
(lambda (x) (and (= x 7) (shift k "oh no it's a 7")))
(range 0 10)))
> (reset (print (string-append "Runetime Error: " (buggy-code))))
"oh no it's a 7"
```

This is interesting! We’re able to mimic the behavior of rasing exceptions
with `shift`

and `reset`

.

Instead of prose about shift and reset, here are the reduction rules for
`reset`

:

```
1. (reset val) => val
2. (reset E[(shift k expr)]) => (reset ((lambda (k) expr)
(lambda (v) (reset E[v]))))
; where E has no reset
```

Rule 1 is easy. If the argument that reset is being applied to doesn’t have
`shift`

in it, we just reduce the reset form down to that value.

Rule 2 tells us a lot about how this works.

Notice that the reduction removes the `shift`

form in `E`

, and that there’s a
sort of switching of things happening. The `expr`

inside the `shift`

form is now
the function body of a lambda abstraction, with `k`

as the parameter. Also, what
is being provided as the argument to this lambda with the `k`

parameter? It
seems like it’s E but with the `shift`

form punched out by the parameter `v`

,
inside another lambda abstraction with `v`

as the parameter.

`(lambda (v) (reset E[v]))`

is basically the current continuation. What
`reset`

does is to set the outer boundary up to which the continuation is
delimited, and what `shift`

does is to “capture” that delimited continuation.

For example, in `(reset (print (string-append "Runetime Error: " (shift k "oh no it's a 7"))))`

,
the continuation is `(lambda (v) (reset (print (string-append "Runetime Error: " v))))`

.

Continuing that example, the `reset`

would reduce to:

```
((lambda (k) "oh no it's a 7")
(lambda (v) (reset (print (string-append "Runetime Error: " v)))))
```

So, when `shift`

captures the delimited current continuation and passes it
`k`

as the parameter, it’s doing a control flow switch to that continuation.

## Implementing Generators

Turns out, we can implement generators easily with `shift`

and `reset`

.

Here is an approach by making our own `yield`

to do a non-local return of a
value:

```
> (define (yield x)
(shift k (cons x (k (void)))))
> (reset
(for-each
(lambda (x) (and (zero? (modulo x 2)) (yield x)))
(range 1 10)))
(2 4 6 8 . #<void>)
```

Above, `for-each`

goes through a list and applies the supplied function to each
item. What’s happening is that the supplied function captures the `(for-each ...)`

continuation, since it’s beneath the `reset`

.

As the interpreter starts to reduce this `reset`

form, it follows its reduction
rules down to `for-each`

, which essentially becomes a series of function
applications that each get applied one by one. For example, here’s the
application of the function to `0`

.

```
((lambda (x)
(and
(zero? (module x 2))
(yield x)))
0)
```

Which reduces a bit further to…

```
((lambda (x)
(shift k (cons x (k (void)))))
0)
; and then...
(shift k (cons 0 (k (void))))
```

And that `shift`

reduces according to reset’s reduction rules above to:

```
(lambda (k) (cons 0 (k (void))))
```

…called with the current continuation, which includes the rest of the
`for-each`

, which reduces to just more applications of `yield`

(which only gets
called when it’s an even number) just with different values!

And that’s how we end up with:

```
(2 4 6 8 . #<void>)
```

It comes down to straightforward reduction of expressions!

Also, here is yet another implementation of a simple “generate one at a time” generator. Max noodled about this and provided this quick example.

```
(define (generate-one-at-a-time lst)
(define k #f)
(define (go)
(if k
(k)
(reset (let ()
(for-each
(lambda (x)
(shift cur-k
(let ()
(set! k cur-k)
x)))
lst)
‘done))))
go)
;; some usage:
> (define my-gen (generate-one-at-a-time '(1 2 3 4)))
> (my-gen)
1
> (my-gen)
2
> (my-gen)
3
```

The interesting thing about this one is that it’s all enclosed and feels much
more like the generator from the very top of this post. It similarly has the
`for-each`

inside the `reset`

, so the continuation contains the full remaining
list, but it interestingly maintains and updates some simple state so that it
knows where it is and can “resume” properly.

A nice way to sort of fill in the pseudo/fake code we had from before!

## End Notes

For more, check out Danvy and Filinski’s *Abstracting Control*, from 1990.
Really good one, I’m still reading it honestly.

Also, check out pypy’s source code instead of CPython’s if you are itching to dig into the Python implementation. It uses continuations and seemed easier to read to me.

Thoughts? Suggestions for what I should explore next? Find me as @gnarmis on Twitter.

Also, a big thank you to Max New for his super thorough review. Another thank you for Hillel Wayne for his overall feedback.