A Taste of Continuations

Leslie Hensley

http://www.papermountain.org

An example

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0
amb.assert x >= 3
puts x    # prints '4'

How?

Continuations

The rest

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0
amb.assert x >= 3
puts x    # prints '4'

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0
amb.assert x >= 3

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0

A second look

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0
amb.assert x >= 3

An example

amb = Amb.new
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0
amb.assert x >= 3
puts x    # prints '4'

Reflection

So Meta

The magic

class Amb
  class ExhaustedError < RuntimeError; end

  def initialize
    @back = [
      lambda { fail ExhaustedError, "amb tree exhausted" }
    ]
  end

  def choose(*choices)
    choices.each { |choice|
      callcc { |fk|
        @back << fk
        return choice
      }
    }
    failure
  end

  def failure
    @back.pop.call
  end

  def assert(cond)
    failure unless cond
  end
end

Questions?

Resources