Tensorflow is apparently some machine learning framework. You probably know Tensorflow best by this clever and thought-provoking logo
Only the cleverest among you will notice that this weird shape is chosen to cast the shadow of a "T" to the left (when lit from the right) and to cast the shadow of an "F" to the right (when lit from the left). Pretty clever!
We've had quite a few questions about Tensorflow and its relationship to timely dataflow (they do have some research ancestry in common!). In this post, we are going to look into implementing Tensorflow in differential dataflow.
Well, implementing the Tensorflow logo in differential dataflow. That seems like the hard part, anyhow.
There is a cute (and fun!) app called Projekt on the Apple app store (and perhaps other places as well). It is a fun game that shows you two 5x5 silhouettes and challenges you to find an arrangement of cubes in a 5x5x5 volume that cast the appropriate shadows (or, "projektions").
Here is an example:
The two shadows on the left and right are the goals, and the space between the two is where you play. In the app, you tap on your screen and through some inverse projektion magic it determines which empty cube should be enabled (or if your tap is held, which filled cube should be removed).
Here is an example after I've added one cube, to see what this looks like.
And here is the same example with another cube on top, and then another cube placed behind. Notice how this isn't right, and an error is expressed over on the left projektion.
These are the rules of Projekt, for which I earn no commission. However, if you are at all interested in it (I recommend it!) you should probably go and grab a copy of it and play a bit now, as we are about to break it wide open.
Let's try and frame the game state of Projekt in differential dataflow. Before doing much of anything, let's put together an empty timely dataflow computation that we will fill in:
// Projekt game logic
//
// Projekt (https://itunes.apple.com/us/app/projekt/id1244456273)
// has you place cubes in a 3-dimensional field in order to create
// two 2-dimensional projektions.
fn main() {
// define a new computational scope, for Projektion!
timely::execute_from_args(std::env::args(), move |worker| {
// Program goes here!
unimplemented!();
}.expect("Computation failed!")I propose that we model the cubes that the player introduces each as a triple (x,y,z). The set of their input cubes can be a collection of these triples, and differential dataflow is great at maintaining and working with collections. Let's create an input for the collection of player cubes, which I will call xyzs.
// An input for (x,y,z) placements.
let mut xyzs = InputSession::new();We will also need some inputs for the two goal projektions. Even though the user doesn't get to adjust these, we do want to be able to adjust the target projektions without recompiling the program. This is also pretty easy: we'll have additional two input collections, each of pairs rather than triples, one for each goal projektion:
// Inputs for (x,y) and (x,z) goals.
let mut xy_goal = InputSession::new();
let mut xz_goal = InputSession::new();With these inputs defined, let's think about building some computations.
The Projekt game lets you make arbitrary changes to the set of input cubes, up to your ability to drive the interface around to add and remove specific cubes. As soon as you exactly meet the two goal projektions, you win!
This sounds like we could define and maintain a computation that determines which cells in the goal projektions are correct, and which are in error. If there are no errors in either projektion (unfulfilled goals or fulfilled non-goals) you win!
// Dataflow to validate input against goals.
worker.dataflow(|scope| {
// Introduce inputs to the scope.
let xyzs = xyzs.to_collection(scope);
let xy_goal = xy_goal.to_collection(scope);
let xz_goal = xz_goal.to_collection(scope);
// Validation rules would go here!
unimplemented!();
});Let's write down how you might surface errors using differential dataflow!
Each cube (x,y,z) projekts to just one square in the (x,y) projektion, which is determined by discarding the z coordinate. All cubes of the form (x,y,_) projekt to (x,y). Following this reasoning, we can transform our collection of cubes into a collection of squares (pairs) using a map operator, and then apply the distinct operator to remove multiplicities (differential dataflow will track the counts, and we only really care about which projekted squares are active, not the number of times each is activated; sounds like "Projekt 2"!).
// projekted (x,y) pairs.
xyzs.map(|(x,y,_)| (x,y))
.distinct()This is great! Let's now compare this with our goal projektions. Each of these collections contain pairs (x,y), and we want the symmetric difference: elements in one collection but not the other. In fact, we might want to distinguish the elements in difference more clearly, to know whether to draw a gray (unfulfilled) square or an "X" for an erroneously fulfilled square.
Let's do both at the same time, by subtracting the (x,y) projektion of the player input from the goal projektions:
// Report unmet XY goals, and met XY non-goals.
let xy_errors =
xyzs.map(|(x,y,_)| (x,y))
.distinct()
.negate()
.concat(&xy_goal)
.consolidate()
.inspect(|x| println!("XY error: {:?}", x));This logic performs the projektion in the first two lines, then negates the counts of the result and merges with the goals, effectively subtracting the projekted input from the goals. We then "consolidate" the results (a logical no-op that ensures matching additions and subtractions are cancelled), and print out any resulting terms.
We can do the same thing with the (x,z) projektions and their corresponding goal projektions.
// Report unmet XZ goals, and met XZ non-goals.
let xz_errors =
xyzs.map(|(x,_,z)| (x,z))
.distinct()
.negate()
.concat(&xz_goal)
.consolidate()
.inspect(|x| println!("XZ error: {:?}", x));These two bits of computation report any errors we might have, and their type: positive errors indicate unfulfilled goals, negative errors indicate fulfilled non-goals. As we play around with the inputs, either the player adding and removing cubes, or the game framework changing the goal projektions, the computation will update and report on the cumulative changes to the set of errors.
With just a touch of additional logic, we can also track the single bit of "are there any errors?" which is what would allow us to announce victory for the player:
let xy_total = xy_errors.distinct().map(|_| ());
let xz_total = xz_errors.distinct().map(|_| ());
let not_done = xy_total.concat(&xz_total).distinct();The not_done collection contains at most a single () item, and as long as it does contain that item the puzzle is not yet solved. Once that element is retracted, then there are no more errors and it is safe to announce victory to the player!
Of course, the most fun part of a game comes from playing it, and our game is an^H^Hno exception!
If you recall, our framework looked roughly like
// An input for (x,y,z) placements.
let mut xyzs = InputSession::new();
// Inputs for (x,y) and (x,z) goals.
let mut xy_goal = InputSession::new();
let mut xz_goal = InputSession::new();
// Dataflow to validate input against goals.
worker.dataflow(|scope| {
// Validation rules went here!
});After defining the dataflow, we want to let people play the game. Let's just let the user make arbitrary changes to each collection, so that they can load a game in (using the x*_goal input collections) and play around with the set of cubes (using the xyzs collection).
For anything to happen, we'll need to start inserting things into the collections. Let's do that now with some hard-wired loading. Remember that puzzle we saw up in those screenshots? Let's load that in.
I'm going to use (0,0) as the lower left corner of each projektion. The the left projektion has 14 squares, corresponding to 14 elements we should insert into the xy_goal collection. Here they are:
xy_goal.insert((0, 0));
xy_goal.insert((0, 1));
xy_goal.insert((0, 3));
xy_goal.insert((0, 4));
xy_goal.insert((1, 1));
xy_goal.insert((1, 3));
xy_goal.insert((2, 1));
xy_goal.insert((2, 2));
xy_goal.insert((3, 2));
xy_goal.insert((3, 3));
xy_goal.insert((3, 4));
xy_goal.insert((4, 0));
xy_goal.insert((4, 1));
xy_goal.insert((4, 2));Coincidentally, the right projektion also has 14 squares. That is actually a coincidence; they don't have to be the same.
xz_goal.insert((0, 2));
xz_goal.insert((0, 3));
xz_goal.insert((0, 4));
xz_goal.insert((1, 2));
xz_goal.insert((1, 4));
xz_goal.insert((2, 1));
xz_goal.insert((2, 2));
xz_goal.insert((2, 3));
xz_goal.insert((3, 0));
xz_goal.insert((3, 1));
xz_goal.insert((3, 3));
xz_goal.insert((3, 4));
xz_goal.insert((4, 1));
xz_goal.insert((4, 4));For anything to happen, computationally, we have to advance our inputs. They are currently happily accepting changes for "time zero", which we should think of as the first round of interaction with the game. For the moment, let's commit the changes to the goal projektions and leave the user input empty.
xyzs.advance_to(1); xyzs.flush();
xy_goal.advance_to(1); xy_goal.flush();
xz_goal.advance_to(1); xz_goal.flush();If we go and run this (at the moment, it is examples/projekt.rs in the differential dataflow repository), we see:
Echidnatron% cargo run --example projekt
Finished dev [unoptimized + debuginfo] target(s) in 0.09s
Running `target/debug/examples/projekt`
Not done: ((), 0, 1)
Echidnatron%
Uh oh. This tells us that we haven't actually solved the problem yet. When this goes away, we will have solved it. I happen to have a handy solution on hand, containing sixteen cubes, which I'll just input like so:
xyzs.insert((0, 0, 2));
xyzs.insert((0, 1, 3));
xyzs.insert((0, 3, 4));
xyzs.insert((0, 4, 4));
xyzs.insert((1, 1, 2));
xyzs.insert((1, 3, 4));
xyzs.insert((2, 1, 1));
xyzs.insert((2, 2, 2));
xyzs.insert((2, 2, 3));
xyzs.insert((3, 2, 0));
xyzs.insert((3, 3, 1));
xyzs.insert((3, 4, 3));
xyzs.insert((3, 4, 4));
xyzs.insert((4, 0, 1));
xyzs.insert((4, 1, 4));
xyzs.insert((4, 2, 4));Of course, if we want anything to happen we will again need to advance our inputs, like so:
xyzs.advance_to(2); xyzs.flush();
xy_goal.advance_to(2); xy_goal.flush();
xz_goal.advance_to(2); xz_goal.flush();Having done that, our program now happily informs us that while we are not initially done, we are done after the second round:
Echidnatron% cargo run --example projekt
Finished dev [unoptimized + debuginfo] target(s) in 0.08s
Running `target/debug/examples/projekt`
Not done: ((), 0, 1)
Not done: ((), 1, -1)
Echidnatron%
Now, I have been hard-wiring these changes into the source code, but you could totally read them from the user somehow. I happen to be weirdly bad at doing that, however, so we aren't going to write some CLI-based "please type integer triples with a +/- sign or I will crash" bit of code. But you could imagine how that might look, depending on how savvy you are with these sorts of things.
Doing this properly almost certainly involves introducing a probe to the end of the relevant dataflow, so that you can report with certainty that user input or puzzle changes have or have not changed the "have you won yet" bit. The example code does this!
You are probably still in a bit of awe over how well I determined the sixteen cubes that satisfy both of those projektion constraints. Admit it!
This is the point at which, if you enjoy relaxing after work with a few rounds of Projekt, perhaps you want to close this browser window and return to you life. We are, unfortunately, now going to show you how differential dataflow can also produce solutions to Projekt puzzles.
Recall your first moments looking at a Projekt puzzle:
Notice over on the lower left how it tells us how many cubes there are in use (zero), but also "min" and "max". Those are the minumum and maximum numbers of cubes you can possibly use in valid solutions for the puzzle. Where do those numbers come from?
We are about to show how to determine the minimum and maximum solutions, explicitly, from the two projektion constraints.
The maximum solution is probably the easier one to find. For starters it is unique, which is not necessarily the case for the minimum solutions.
The way I think about the maximum solutions is to think of the non-shadowed parts of the projektions as "lit", in the sense that light must pass through the 5x5x5 region onto that square. That means that each lit square is a constraint, that five corresponding cubes must be absent. If we start from all 125 cubes and just remove those that must be absent, we get a valid solution, and this solution has the largest number of cubes (proof left as a not-very-hard exercise for the reader).
To keep things simple visually, let's look at what this means for the lowest 5x5 layer, projekted in each dimension as five squares in sequence.
Here we've tried to use all the cubes in the layer, but had to scratch some of the cubes off because they blocked the light.
How might we compute this? There are a number of ways. We could start from all 125 cubes and do some fancy antijoin logic to scratch off cubes, but it turns out there is a much easier way to do it.
For any (x,y,z) where either (x,y) or (x,z) is absent from our goals, we should absolutely not add the cube (x,y,z) to our solution. This is equivant to saying for every (x,y) and (x,z) goal, where x matches, it is safe to add the cube (x,y,z) to our solution.
It turns out this is just a relational join:
xy_goal
.join(&xz_goal)
.map(|(x,(y,z))| (x,y,z));The resulting collection is the maximal solution. I wrote this up using a new dataflow
// Dataflow to produce maximal inputs.
worker.dataflow(|scope| {
// Introduce goals to the scope.
let xy_goal = xy_goal.to_collection(scope);
let xz_goal = xz_goal.to_collection(scope);
// For each x, produce valid pairs of y and z.
xy_goal
.join(&xz_goal)
.map(|(x,(y,z))| (x,y,z))
.probe_with(&mut probe);
});We could also report the size of the maximal solution, so that we can update the display (taunting the player) as the problem changes. This has a somewhat longer but more efficient implementation, where we avoid materializing the output solution and just multiply the counts for the two projektions for each layer.
Or we could just report the maximal solution itself, to admire:
The minimum solutions are not unique, and are a bit more subtle than the maximum solutions. It turns out they aren't especially complicated either, but they won't be a one-liner.
First, let's sketch out some constraints. Each value of x imposes independent constraints, in that we can solve each "layer" of our problem independently. If we come up with a way of solving each layer optimally (with the minimum number of cubes) we can apply that to each level of the problem.
In our running example, our bottom layer has four squares in the left projektion and three squares in the right projektion. We already saw how we could use twelve cubes to solve this, using the largest number of cubes possible, but how might we minimize it?
In each layer, we will need at least as many cubes as the maximum of the number of squares of the two projektions, as we would need at least that many distinct cubes to satisfy the larger projektion. As it turns out, we don't need any more cubes than this. We can satisfy both projektions using exactly as many cubes as the maximum number of squares, layer by layer.
Let's again take the bottom layer, with its four and three projekted squares. Let's start by placing a cube that satisfies the first pair of projekted squares. In this case that would be the (0, 0, 2) cube. Let's do that again with the second pair of projekted squares, using the (0, 1, 3) cube. The third pair of projekted squares is satisfied with the (0, 3, 4) cube.
We are now in a pickle, because we have run out of projekted squares in the right projektion. But that is fine, because we can just re-use the last projeckted square in the right projektion, because we are allowed to cover it multiple times. The (0, 4, 4) cube finishes out our requirements.
We can repeat this process layer by layer, producing a minimum solution:
There are many minimum solutions, as layer by layer we only need to cover the projekted squares, and there are multiple ways to do this (some combinatorics ninja can try and count them, or explain how one counts them).
It is not too tricky to determine the size of the minimum solutions. For each x we count the number of distinct projekted squares in each projektion, take their maximum, and sum up the results. I did that like so, using the weird and magical explode operator (better name incoming):
// Dataflow to produce minimum inputs.
worker.dataflow(|scope| {
// Introduce goals to the scope.
let xy_goal = xy_goal.to_collection(scope);
let xz_goal = xz_goal.to_collection(scope);
let xy_xs = xy_goal.map(|(x,_)| x).count();
let xz_xs = xz_goal.map(|(x,_)| x).count();
xy_xs.join(&xz_xs)
.explode(|(_,(ys,zs))| Some(((), ::std::cmp::max(ys,zs))))
.consolidate()
.inspect(|x| println!("Minimum solution size: {}", x.2));
});This should update in roughly constant time for a single change to either projektion, a property that our solution finder will unfortunately not have.
To produce a solution, we can group the two projektions by their x coordinates and form the list of y or z values to cover, and then join the two lists together. We then need to apply a flat_map operator to enumerate cubes that cover the projekted squares. I chose a different rule than described above, just restarting the shorter list if we run out rather than re-using the last element.
// Produce pairs of lists (x, ys) and (x, zs).
let x_ys = xy_goal.group(|_x,ys,out|
out.push((ys.iter().map(|(&y,_)| y).collect::<Vec<_>>(), 1))
);
let x_zs = xz_goal.group(|_x,zs,out|
out.push((zs.iter().map(|(&z,_)| z).collect::<Vec<_>>(), 1))
);
// Cover ys and zs using minimal cubes.
x_ys.join(&x_zs)
.flat_map(|(x,(ys, zs))| {
let max = ::std::cmp::max(ys.len(), zs.len());
let ys = ys.into_iter().cycle(); // cycle forever
let zs = zs.into_iter().cycle(); // cycle forever
ys.zip(zs).take(max).map(move |(y,z)| (x,y,z))
})
inspect(|x| println!("Minimum solution: {:?}", x))
probe_with(&mut probe);This produces a different solution than we saw up above, but that is all good (I did it by hand). It does have the defective property that if a goal projektion changes we re-perform most of the work for that layer. On the plus side, it isn't very much work, so that's great. But, would be better if we had a sweet way to set up a stable-ish matching between the two.
This post was meant to remind you that you can think about neat problems in a declarative way. Rather than write a horrible tangle of code that may or may not correctly update incrementally, or a simple bit of code that re-evaluates everything about your game state on each interaction, we've described something that some among you may describe as pleasant, and we get out of the exchange an implementation that promptly responds to any changes in game state with the corresponding changes in the observed output.
I'm still looking for a great example of a simple interactive game that might better explain to folks how and why something like differential makes life easy and pleasant, without boring them to tears about graph properties. I still haven't found it yet, unfortunately, but you will be the first to know if I do!
Happy new year!