Destroying the universe

Hi everyone, this talk is called "Destroying the Universe", for reasons that will become obvious...

Stop me if you've heard this one. Once there were five people who lived in five houses. I know this picture only shows four houses... But I had a boss once who said that there's some sort of rule, that you really only need to do 80% of the work to get 20% of the value, or something. So I'm just trying to be efficient here.

There was number 1 at the end, by the park; then 2, 3, and 4; and number 5, not shown, on the corner. And in these houses there lived a baker, a miller, a smith, and so on. You may want to take notes by the way. So yes, one craftsperson per house.

The baker did not live in #5, the cooper did not live in #1, and the fletcher didn't live in either #5 or #1, and he was not next-door neighbors with either the smith or the cooper. The cooper lived closer to the park than the miller.

Also the cooper's name was Fletcher Miller, can you believe that? That's not part of the puzzle. Just a funny coincidence...

Now, can you tell me who lived where?

What we're going to do tonight is solve this puzzle using some cool technology that I discovered in an old book. You can probably do it faster on your own, but that's not the point, right?

Scheme

This talk is about a programming language called Scheme. It's a Lisp; and it has some little-known and very surprising features that we'll talk about tonight.

There are several implementations of Scheme. I'm using one that I wrote from scratch in Rust. So if you want to play along today, first you need to get Rust, and then you need to get my Scheme VM, and then you need to build my Scheme VM.

rustup.rs

github.com/jorendorff/cell-gc

cd cell-gc/lisp
cargo run --release

Or, if you want something that's a little easier to install, you can use Guile. I'm not gonna judge you or anything.

brew install guile

Anyway, let me just kind of give you an idea of what this programming language looks like.

$ scheme
» (+ 21 75)
96

In Scheme, whenever you want to do anything at all, you're pretty much always calling a function, which means you use parentheses. This is the syntax for function calls in Scheme. The first thing inside the parens is the function that you're calling. The other things are arguments. Sometimes this is called prefix notation.

Like many functional languages, Scheme treats addition as just another function.

Introduction to `amb` and `require`

First example

I have a bunch of Scheme code in a file, let's load it up.

» (load "amb.scm")

That just defined a couple functions, which I'll show you now. The first one is called amb, and here's what it does:

» (amb 1 2 3)
1
» (amb "ok" "go")
"ok"

So clearly this function, you call it, it takes any number of arguments, and it returns the first argument you passed it. That's amb.

Before we get too far along, I should show how to define a variable.

» (define x (amb 1 2 3 4 5))
» x
1

Make sense?

OK. The other function is called require, and here's how that works.

Suppose we need x to be greater than 2. We can say:

» (require (> x 2))

Again, in Scheme, > is a function; you pass it two numbers, and it returns true if the first number is greater than the second.

OK, so what is the value of x?

» x
3

OK? Everybody with me?

(discuss, play dumb)

Second example

So a second example, real quick, just to make totally clear what's going on here. I'll define a function that returns some digit.

» (define (digit) (amb 1 2 3 4 5 6 7 8 9 0))

And then we can call this function whenever we want to define a variable that's a digit. Of course it just returns the first digit, 1.

» (define x (digit))
» x
1

And I can define a second variable...

» (define y (digit))
» y
1

And if we require the product of those two numbers to be 24, we can just say...

» (require (= (* x y) 24))

(the numbers on the previous lines change to 3 and 8)

And if we require x to be greater than y, then...

» (require (> x y))

(the numbers change again, to 6 and 4)

And I really would like for at least one of these to be odd, so...

» (require (or (odd? x) (odd? y)))

(the numbers change again, to 8 and 3)

(If I'm very lucky, someone will ask what happens if we add another requirement now, since the constraints we've already put on this now produce a unique solution. I blanch and mumble something about not wanting to do that because of how this is implemented.)

Discussion

All right. So amb returns one of the values you pass to it, such that all future requirements on that value are met. And require is for specifying the requirements.

Sometimes when I give this talk, people complain that it would make more sense to specify the requirements first and call amb after that, but in Scheme you define variables first, before using them. So it sort of makes sense we have to do it this way.

These functions are actually very easy to implement in Scheme. amb is ten lines of code, and require is I think three lines of code. Scheme is cool.

So uh, that's all I've got. Questions?

How it works

To understand exactly what is going on here, we're going to have to cover some background information. Very important topics.

Bogosort
the "many worlds" interpretation of quantum mechanics
the famous P vs. NP problem
continuations in Scheme.

First, let's talk about Bogosort.

Bogosort

So you've probably heard about sorting algorithms. There are several different ways to write a program that puts values in order. Different techniques have different advantages; some are faster for large collections, others are faster for small collections, some require less memory, some are easier to implement, and so on.

Bogosort is a sorting algorithm that is unique in that it has no redeeming qualities whatsoever. Bogosort is an amazingly bad algorithm.

Here's how it works. It's a three step process.

Step 1: Randomly shuffle the collection. Just put all the values in a random order.

Step 2: Look at the values and see if they're in order. If so, we're done.

Step 3: Otherwise go back to step 1.

So that's quite easy to implement.

(I don't know if you like fluxogramas, but in case you do, here's a fluxograma of the algorithm.)

(slide: Bogosort flow chart in Portuguese)

It's not exactly guaranteed to terminate, but if you really are mixing the values randomly in step 1 then you will almost certainly succeed eventually. In fact, if you use this technique on a deck of cards, say it takes about a minute to shuffle a deck thoroughly, then you could finish in around 8 years.

And if you want, you can do this clever optimization where you check to see if the data is sorted before shuffling instead of after, saving one shuffle.

"Many worlds"

So what does that have to do with anything, well, let me tell you, I am totally going to clarify that right the heck now. Because if you like bogosort, you are going to love quantum bogosort.

Before I get started here I want to clarify that this is not an algorithm that you can run on a quantum computer, because that would be potentially useful, no, this is—well, you'll see what it is. I'm just going to read this off to you, because it's so, so good.

http://wiki.c2.com/?QuantumBogoSort

QuantumBogoSort is a quantum sorting algorithm which can sort any list in O(n), using the "many worlds" interpretation of quantum mechanics.

It works as follows:

Quantumly randomise the list, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(n!) universes; however, the division has no cost, as it happens constantly anyway.

If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)

All remaining universes contain lists which are sorted.

In other words, if you get to the end and you're still alive, you have a sorted list.

But having had our laugh, let's consider this a little more seriously. How long does it take to sort an array in this way? It's O(n) because shuffling the array in step 1 takes n steps, and again checking that it's sorted in step 2 takes n steps.

This is much more efficient than the sort method in your favorite programming language. Sorting a list of a million records the normal way requires over 18 million comparisons. This takes one million.

And quantum bogosort generalizes quite nicely. What if instead of some data to sort, you have literally any other problem?

Quantumly choose a random solution to the problem.

Check the solution. If it is not correct, destroy the universe.

All remaining universes contain a solution to the problem.

This algorithm shows that when you have the ability to destroy the universe, P = NP, solving one of the longstanding problems in computer science. A lesser talk would stop there, but we're just getting warmed up.

Continuations

Now we come to item number four, continuations. And you might be thinking, all right, surely this is where the threads tie together and things start to make sense. Nope.

Stay with me, though...

Continuations are a feature of Scheme that most other languages don't have. They're a little hard to explain, so I'm going to try coming at it from several directions.

= "the stack"

You may have heard of the stack. What is it? (discuss)

Each thread of a program has a stack, the chain of function calls that got us where we are right now. main() called this function, called that function, called the current function. You usually see it when there's an error. It's handy because it tells us how we got here.

A continuation is just that—it's just a snapshot of the stack.
= "the future"

Another way to think about the stack is, it's the future of your program.

Think about it: whenever anything returns in your program, the computer has to answer the question: now what? It's not obvious from looking at the source code! You're executing a return statement. You can't just go on to the next line of code! There is no "next line"!

What your computer actually does is, it looks at the stack. It sees, oh, here's the function that called us. We'll just jump back there, and that function can pick up where it left off. The stack contains everything your computer needs to revive that function: its arguments, local variables, and so on. ...And the same information for its caller, and that function's caller, all the way back to main().

So you might think of the stack as "how we got here". It tells a story about what's happened so far, about the past. But the same information, the same stack, is really the future of the current thread.

That's where the word "continuation" comes from. A continuation is "the rest of the computation".
= "save points"

Continuations are kind of like a save point in a game. You can capture a continuation at any time. You can hold on to that continuation. And you can "invoke" it later to teleport to that captured future.

It's like a return statement, except you're saying, "return from that function over there, remember when I was over there?" And Scheme will replace your stack with the saved stack and place you over there, and pick up whatever you were doing when the snapshot was taken.

It's not so weird: every program you've ever written does this automatically every time you return from a function.

...So how are we doing? I've tried explaining continuations three different ways now. If you're still totally, hopelessly lost, that could mean you're getting it.

Let's try another tack. What are continuations actually good for?
useful for "escape"

Well, pretty much any time you want control flow to do something weird, continuations can do that.

Take exceptions. When an error happens, your program wants to "bail out". It's not like a normal return, right? You want to ditch the current call chain and teleport to some code that is specifically written to cope with errors.

So in Scheme, you can actually write try and throw not as special keywords but just regular functions, using continuations. That's kind of neat.
useful for coroutines (yield, async/await)

If you've written asynchronous code in Python, C#, or JavaScript, you've used the await keyword, right? What does that keyword actually do? Well, it sets aside the current stack, to be continued later, whenever we finish waiting.

If you've used generators, same deal.

So in Scheme, you could implement yield and async/await not as special keywords but just regular functions, using continuations.

Continuations are this common building block that unifies a lot of control-flow things programming languages do. return, throw, yield, await, and more.
horrifyingly powerful

The only problem is, continuations are kind of like goto across time and space. They are as weird in the lab as in the lecture. They break abstractions.

What do I mean by that?

You know how sometimes you might have some code that doesn't cope if an exception is thrown? You just weren't thinking about exceptions that day, maybe. So you have a bug. Well, continuations are like exceptions turned up to 11. They punch right through all your normal assumptions about how your code is going to behave. And features that break programmer assumptions are bad, right? Continuations are maybe too powerful for us mortals. Beware! Turn back now before it's too late!

Live-coding `(amb)` and `(require)`

(no detailed script here)

(we want to end up with something like this:)

(define (fail)
  (error 'require "no solutions"))

(define backtrack fail)

(define (require ok)
  (if (not ok)
      (backtrack)))

;; Return one of the values in `values` such that all future `(require)` calls
;; are satisfied.
(define (amb . values)
  (let ((backtrack-further backtrack))
    (call/cc (lambda (ctn)
               (define (next values)
                 (if (null? values)
                     (backtrack-further)
                     (begin (set! backtrack
                                  (lambda () (next (cdr values))))
                            (ctn (car values)))))
               (next values)))))

(Here are some points we don't have to lecture on, because we can cover them during live-coding:)

continuations are procedures
they don't return (this is how calling a continuation is like destroying the universe)
when you capture a continuation, the function whose continuation you captured can return more than once

Explain the terminal's behavior

when I enter a new (require) call, that may cause backtracking.
when all (require) calls pass, the program reaches the part where it prints a prompt and calls (read-line)

I said earlier that this Scheme is one that I wrote myself in Rust. The nice thing about that is that naturally I also wrote my own REPL in Scheme, which might be just slightly custom-built for this demo. It knows about continuations, and it keeps a log of all the lines you've typed. The custom bit is, if you call a continuation that takes you back in time, the REPL knows you've done that, and it erases all the output that's been generated since then. It emits escape codes that tell the terminal to erase those lines of output from the screen. And then it replays the commands that you typed after that point. When you saw things changing on screen, that's what was happening. I'm not actually teleporting you to different universes as we go. It's all stupid VT100 tricks.

But I had you wondering, right?

The puzzle

So let's define a function that produces a street number...

(define (sn)
   (amb 1 2 3 4 5))

And let's define five variables, the addresses of the five characters in our puzzle.

(define baker (sn))
(define cooper (sn))
(define fletcher (sn))
(define miller (sn))
(define smith (sn))

And I would like something like a scoreboard, so I'll just do this real quick...

(list (list 'baker baker)
      (list 'cooper cooper)
      (list 'fletcher fletcher)
      (list 'miller miller)
      (list 'smith smith))

What are the requirements we're trying to satisfy? We know the baker does not live at #5. The cooper does not live at #1.

(require (not (= baker 5)))
(require (not (= cooper 1)))

And the fletcher doesn't live in either of those.

(require (not (or (= fletcher 5) (= fletcher 1))))

The miller's house number is greater than the cooper's.

(require (> miller cooper))

OK! So far, so good.

The fletcher is not neighbors with the smith or the cooper. How can we say that?

(define (neighbors? a b) (= (abs (- a b)) 1))

(require (not (neighbors? fletcher smith)))
(require (not (neighbors? fletcher cooper)))

And I guess we should require that they all live in different houses.

(require
  (distinct? (list baker cooper fletcher miller smith)))

Some quotes from SICP

It is instructive to contrast the different images of time evoked by nondeterministic evaluation and stream processing. Stream processing uses lazy evaluation to decouple the time when the stream of possible answers is assembled from the time when the actual stream elements are produced. The evaluator supports the illusion that all the possible answers are laid out before us in a timeless sequence. With nondeterministic evaluation, an expression represents the exploration of a set of possible worlds, each determined by a set of choices. Some of the possible worlds lead to dead ends, while others have useful values. The nondeterministic program evaluator supports the illusion that time branches, and that our programs have different possible execution histories. When we reach a dead end, we can revisit a previous choice point and proceed along a different branch.

Abstractly, we can imagine that evaluating an amb expression causes time to split into branches, where the computation continues on each branch with one of the possible values of the expression. We say that amb represents a nondeterministic choice point. If we had a machine with infinite processors, we could implement the search in a straightforward way. Execution would proceed as in a sequential machine, until an amb expression is encountered. At this point, more processors would be allocated and initialized to continue all of the parallel executions implied by the choice. Each processor would proceed sequentially as if it were the only choice, until it either terminates by encountering a failure, or it further subdivides, or it finishes.

On the other hand, if we have a machine that can execute only one process (or a few concurrent processes), we must consider the alternatives sequentially. One could imagine modifying an evaluator to pick at random a branch to follow whenever it encounters a choice point. Random choice, however, can easily lead to failing values. We might try running the evaluator over and over, making random choices and hoping to find a non-failing value, but it is better to systematically search all possible execution paths. The amb evaluator that we will develop and work with in this section implements a systematic search as follows: When the evaluator encounters an application of amb, it initially selects the first alternative. This selection may itself lead to a further choice. The evaluator will always initially choose the first alternative at each choice point. If a choice results in a failure, then the evaluator automagically backtracks to the most recent choice point and tries the next alternative. If it runs out of alternatives at any choice point, the evaluator will back up to the previous choice point and resume from there. This process leads to a search strategy known as depth-first search or chronological backtracking.

More advanced points to hit, depending on the audience

livecoding amb
- this is what it's like to work with continuations, they're way too low-level and mind-bending to use directly in programs. instead you design and laboriously implement a higher-level feature, like generations, or like amb.
- this won't work for stateful programs, as assignments aren't rolled back
amb is like the list monad in Haskell. Haskell automatically creates continuations as plain old functions for each <- in do notation; the right-hand argument of the >>= operator in Haskell is a continuation.
amb is a little like logic programming in Prolog.
continuations are bad: delimited continuations are a better idea

jorendorff/amb.md