Sunday, July 23, 2017

redo-signals: Breaking cycles

Consider a slider/text-field:

When the user edits one, the other should update to match:

Can we express this in FRP-style?

val textField = new JTextField("50", 6)
val slider = new JSlider

val win = new JFrame("Test")
win.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE)
win.setLayout(new FlowLayout)
win.add(textField)
win.add(slider)
win.pack()
win.setLocationRelativeTo(null)
win.setVisible(true)

textField.text.foreachDelayed { text => implicit u =>
slider.value.updateLater(text map { text =>
Try(text.toInt) match {
case Failure(_) => slider.value.now
case Success(value) => value
}
})
} (slider.value.redoObserving)

slider.value.foreachDelayed { value => implicit u =>
textField.text.updateLater(value map (_.toString))
} (textField.text.redoObserving)

It turns out we can. But the code looks cyclical... how does it not produce an infinite loop?

foreachDelayed comes to the rescue. It runs on the invalidation sweep. A signal can only be invalidated once before it is recalculated. So, the invalidation sweep can never produce an infinite loop; it simply traverses the graph of signals and invalidates each one it hits.

Saturday, July 22, 2017

redo-signals: Planting imperative trees in a declarative forest

redo-signals is a Scala library for functional reactive programming. With redo-signals, you write declarative code:

val x = new Source[Int](0)
val y = new Source[Int](0)

val z = tracking { implicit t =>
x.track + y.track
}

But some behavior is poorly suited to declarative style. Consider the following set of rules:

  1. For every element of sourceList1, ensure there exists a Type1Worker worker in workerList.
  2. For every element of sourceList2, ensure there exists a Type2Worker worker in workerList.
  3. Don't remove or re-create workers.

You could write these rules declaratively, but they are more natural as imperative code:

sourceList1.zipWithStalenessFrom(Seq()).foreach { case (oldXs, newXs) =>
workerList() = workerList.now ++ ((newXs.toSet -- oldXs.toSet) map (new Type1Worker(_)))
}

sourceList2.zipWithStalenessFrom(Seq()).foreach { case (oldXs, newXs) =>
workerList() = workerList.now ++ ((newXs.toSet -- oldXs.toSet) map (new Type2Worker(_)))
}

But this introduces an unintended consequence. Supposing sourceList1 and sourceList2 originate from the same source. Upon every change in the source data, each foreach() will execute once, resulting in two updates to workerList, when there should be only one.

Consider the following complete example:

case class Payload(name: String)
trait Worker
class Type1Worker(val payload: Payload) extends Worker
class Type2Worker(val payload: Payload) extends Worker

val rootSourceList = new Source[Seq[Payload]](Seq())

val sourceList1 = rootSourceList map (_ filter (_.name.startsWith("a")))
val sourceList2 = rootSourceList map (_ filter (_.name.startsWith("b")))

val workerList = new Source[Seq[Worker]](Seq(), debugName = Some("workerList"))

sourceList1.zipWithStalenessFrom(Seq()).foreach { case (oldXs, newXs) =>
workerList() = workerList.now ++ ((newXs.toSet -- oldXs.toSet) map (new Type1Worker(_)))
} (workerList.redoObserving)

sourceList2.zipWithStalenessFrom(Seq()).foreach { case (oldXs, newXs) =>
workerList() = workerList.now ++ ((newXs.toSet -- oldXs.toSet) map (new Type2Worker(_)))
} (workerList.redoObserving)

workerList foreach { workers =>
println(s"Now have ${workers.length} workers")
}

// One update
rootSourceList() = Seq(Payload("a 1"), Payload("b 1"))

This prints

Now have 0 workers
Now have 1 workers
Now have 2 workers

Two updates appear in output: from 0 to 1, and from 1 to 2. How can we merge these into a single update?

The solution is to use foreachDelayed:

sourceList1.zipWithStalenessFrom(Seq()).foreachDelayed { xs => implicit u =>
workerList.updateLater {
xs map { case (oldXs, newXs) =>
workerList.now ++ ((newXs.toSet -- oldXs.toSet) map (new Type1Worker(_)))
}
}
}(workerList.redoObserving)

sourceList2.zipWithStalenessFrom(Seq()).foreachDelayed { xs => implicit u =>
workerList.updateLater {
xs map { case (oldXs, newXs) =>
workerList.now ++ ((newXs.toSet -- oldXs.toSet) map (new Type2Worker(_)))
}
}
}(workerList.redoObserving)

How does this work? In redo-signals, changes to the state of the world are made in two sweeps: the first sweeps invalidates all signals, and the second sweep executes listeners, which, in the process, often re-evaluate signals, causing them to become valid. foreachDelayed and updateLater allow the user to tap in to this procedure, by scheduling code to run on either the first or second sweep.

The body of the function passed to foreachDelayed runs on the first sweep -- the invalidation sweep. This means that it is guaranteed to run exactly once per update. However, because it is on the invalidation sweep, it's not allowed to look at the state of any signals, because any signal is at risk of being invalid.

So, it passes the work on to updateLater. updateLater is the complement to foreachDelayed. It schedules an update to run on the second sweep, execution sweep, at which time it may evaluate xs and workerList.now.

The result is that you can write imperative code that executes like declarative code -- no more than it has to. The various parts are schedules to run on the correct sweeps, and signals change their values exactly as many times as their are root changes to the system. And so imperative code mixes seamlessly into the declarative world.

Peaks

Sunday, June 4, 2017

The ∞ levels of programming

At the 0th level are functions. Functions operate on data. Data like 1 or 2 or "three".

def f(x):
    return x + 1

At the 1th level are meta-functions, what you might call macros. Meta-functions operate on code.

def reapply(c):
    return apply(c.func, c)

reapply(f(2))f(f(2))4

There is of course meta-data as well, and a meta-function can operate on meta-data:

map(reapply, [f(2), f(3), f(4)])

At the 2th level are meta-meta-functions, that operate on meta-functions and meta-meta-data.

def reapply(c):
    return apply(c.func, c)

reapply(reapply(f(2)))reapply(reapply(f(2)))reapply(f(f(2))f(f(f(2)))5

And so on.

What the ∞ levels of programming give you is precision. Remember Scala continuations? Remember how you couldn't use shift inside a map or a foreach? Well that was because shift was a meta-function, and map was a function, and functions can't operate on meta-functions.

Or more concretely, shift tears apart the code itself. But when shift is mapped, you don't know yet--at compile time--where it will land. So you can't pull the code apart.

But with a meta-meta-map, and a meta-meta-list, you could meta-meta-map your shift over your meta-meta-list.

There's some analogy to universes in type systems, that the way to clarify statements about statements is to separate them by levels. When code may only refer to the level below it, a multitude of paradoxes go away.

And then the puzzle is how to compile it efficiently.

Monday, March 13, 2017

My computer is haunted

After my computer sleeps, in certain GTK+ 3 applications, specific colors will not appear:

(Note the blank spaces)

After causing enough unique colors to be drawn, the problem goes away.

Some googling around suggests that this may be related to the i915 driver for Intel graphics cards, at which point it became apparent that this was the kind of problem that will literally never be fixed.

It was suggested either to add the following incantation to /etc/X11/xorg.conf.d/50-device.conf:

Section "Device"
  Identifier "Default Device"
  Driver "intel"
  Option "AccelMethod" "UXA"
EndSection

or the following in /etc/environment:

COGL_ATLAS_DEFAULT_BLIT_MODE=framebuffer

neither of which, of course, made any difference.

Or, instead of waiting for the impossible to happen I can just run this bit of code:

for i in $(seq 0 255) ; do
    bash -c 'echo -n $'"'"'\033[38;5;'"$i"'mhi\033[0m'" '"
done
echo

and then everything is good.