Following up my first experiments with FRP in Javascript I put together a separate github project and demo/tutorial page. Check it out:
Following up my first experiments with FRP in Javascript I put together a separate github project and demo/tutorial page. Check it out:
Functional Reactive Programming, or FRP, is an elegant approach to “purely functional” event-driven programming with values that change over time. It is a change of perspective from the usual meaning of “event driven” in Javascript, and it is very, very cool.
There already exists a from-first-principles implementation of FRP in Javascript via the Flapjax compiler, a lot of related ideas are in knockout.js, and Asana says their Luna framework was inspired by FRP. But I want to demonstrate how simple it is to get a naive implementation of FRP off the ground by using the event-handling API provided by Backbone. Since we are in Javascript, the semantic work that has gone into FRP is pretty much out the window anyhow.
Let’s dive in; here’s the HTML shell I’m going to use:
<!doctype html>
<html lang="en">
<head>
<title>Shortest Path to FRP benefits in Javascript</title>
<script src="jquery.js"></script>
<script src="underscore.js"></script>
<script src="mustache.js"></script>
<script src="ICanHaz.js"></script>
<script src="backbone.js"></script>
<script src="reactive.js"></script>
<script type="text/html" id="icanhaz-example">
<ol>
{{#list}}
<li>{{value}}</li>
{{/list}}
</ol>
</script>
</head>
<body>
<div>Date and time: <span id="datetime"></span></div>
<div>Deciseconds: <span id="deciseconds"></span></div>
<div>Seconds: <span id="seconds"></span> and <span id="seconds2" /></div>
<div>Seconds even: <span id="secondsEven"></span></div>
<div>Stuttering: <span id="stutter"></span></div>
<div>I can haz reactivity: <div id="icanhaz-output"></div></div>
</body>
</html>
You can get jquery, backbone, ICanHaz, mustache, and underscore however you like. I just tossed them in the directory for this demo, here: http://kennknowles.github.com/codeslashslashcomment/2011-12-28-ReactiveJS/reactive.html
$(document).ready(function() {
FRP is based on two main semantic types that are very closely related: event streams and behaviors. Event streams are infinite sequences of data attached to a time, where time is nondecreasing. Behaviors are variables whose value changes continuously over time, i.e. functions of time. In pseudo-Haskell:
// EventStream a = [(Time, Event)] // Behavior a = Time -> a
But “Time” is not a type we actually have available, so we keep these types abstract and expose primitives and combinators. There are many implementation choices available, the latest and greatest is described in Push-Pull Functional Reactive Programming by Conal Elliott, but since we are in a mutatey language already that has some event handling, the best reference is probably this draft of an imperative implementation strategy.
One major takeaway from FRP is make the event stream first class, so let us start with defining that class. It is quite literally just a handle for listening for occurrences of events. In actual use, you have to deal with the fact that listeners should be weak references, but that is a battle for another day.
var EventStream = function() { };
_.extend(EventStream.prototype, Backbone.Events, {
_listen: function(callback) {
this.bind("occur", callback);
},
_unlisten: function(callback) {
this.unbind("occur", callback);
},
_occur: function(payload) {
this.trigger("occur", payload);
}
});
The _listen and _occur methods expose the implementation of EventStream. If you are calling them, then you are not really using FRP, but implementing FRP, and your code would not necessarily be portable to a different implementation strategy.
The most obvious event stream (to me?) is a heartbeat that says the time. From this we can build useful things like pseudo-continuous time. This does violate an FRP notion of time invariance where a program always behaves the same when shifted in time, but oh well!
var timerE = function(delay) {
var stream = new EventStream();
setInterval(function() {
stream._occur(new Date());
});
return stream;
}
An implementation for Behaviors is simply a boxed variable with similar event-handling routines. Again, no client code should call _change or _observe.
var Behavior = function(initialValue) {
this.value = initialValue;
}
_.extend(Behavior.prototype, Backbone.Events, {
_change: function(newValue) {
this.value = newValue;
this.trigger("change", newValue);
},
_observe: function(fn) {
this.bind("change", fn);
},
_unobserve: function(fn) {
this.unbind("change", fn);
}
});
A first primitive form of behavior is the stepper: Starting with some initial value, it listens to an event stream and saves the values that come in.
var stepperB = function(initialValue, stream) {
var behavior = new Behavior(initialValue);
stream._listen(function(eventValue) {
behavior._change(eventValue);
})
return behavior;
}
And now we can make a behavior that counts time upwards
var timeB = function(init, granularity) { return stepperB(init, timerE(granularity)); };
That is a taste of how we build behaviors and event streams without going under the hood, but we will need more primitives. In particular we will definitely need to be able to map a function over an event stream or behavior.
var mapE = function(f, stream) {
var mappedE = new EventStream();
stream._listen(function(ev) {
mappedE._occur(f(ev));
});
return mappedE;
}
var mapB = function(f, behavior) {
var mappedB = new Behavior(behavior.value);
behavior._observe(function(v) {
mappedB._change(f(v));
});
return mappedB;
}
Hmmm, those look very similar. Indeed, we forgot to implement the inverse of stepper, and then we would only need one of mapB and mapE. I’ll add a few more primitives here.
var changesE = function(behavior) {
var stream = new EventStream();
behavior._observe(function(value) {
stream._occur(value);
});
return stream;
}
var mapB_2 = function(f, behavior) {
return stepperB(behavior.value, mapE(f, changesE(behavior)));
}
var filterE = function(p, stream) {
var filtered = new EventStream();
stream._listen(function(event) {
if (p(event)) filtered._occur(event);
});
return filtered;
}
var snapshotE = function(behavior, stream) {
var snapshots = new EventStream();
stream._listen(function(event) {
snapshots._occur(behavior.value); // bad? probably
});
return snapshots;
}
And this all gets to be the most fun when it is higher-order. The switcherB starts as one behavior, but listens for new ones on an event and switches over to them. This is also a primitive.
var switcherB = function(initialB, behaviorsE) {
var b = new Behavior(initialB.value);
var currentB = initialB;
var callback = function(value) {
b._change(value);
}
currentB._observe(callback);
behaviorsE._listen(function (newB) {
currentB._unobserve(callback);
currentB = newB;
currentB._observe(callback);
b._change(currentB.value);
});
return b;
}
To actually see this stuff, we need a “legacy” adapter to the browser’s imperatively-updated DOM. In this implementation, we can actually abuse mapB for this, but that is not in the spirit of the function, so we’ll drop to primitives again.
var bindB = function(elem, behavior) {
behavior._observe(function(value) {
$(elem).html(value);
});
}
One thing to note is that the framework does nothing to minimize the amount of event passing that happens. You’ve got filterE and snapshotE to do that, but it can take some ingenuity to make sure the same value isn’t pushed over and over. I imagine there are solutions and/or wisdom in the literature which I have simply neglected in this quick hack.
Anyhow, we can now bind a bunch of behaviors to the DOM and watch them go.
var startMillis = new Date().getTime();
var datetimeToDecisB = timeB(0, 100);
bindB($('#datetime'), mapB(function(d) { return d.toString(); }, datetimeToDecisB));
var decisB = mapB(function(dt) { return Math.floor(dt.getTime() / 100); }, datetimeToDecisB);
bindB($('#deciseconds'), decisB);
var decisWrapE = filterE(function(value) { return value % 10 == 0; }, changesE(decisB));
var decisWhenWrappedB = stepperB(decisB.value, snapshotE(decisB, decisWrapE));
var secondsB = mapB(function(decis) { return Math.floor(decis / 10); }, decisB);
var secondsB2 = mapB_2(function(decis) { return Math.floor(decis / 10); }, decisB);
bindB($('#seconds'), secondsB);
bindB($('#seconds2'), secondsB2);
var secondsB3 = mapB(function(decis) { return Math.floor(decis / 10); }, decisWhenWrappedB);
var isEven = function(n) { return n % 2 == 0; }
var secondsEvenB = mapB(isEven, secondsB3)
var stutterB = switcherB(decisB,
mapE(function(even) { return even ? decisB : decisWhenWrappedB; },
changesE(secondsEvenB)));
bindB($('#secondsEven'), mapB(function(even) { return even ? "YES \\(^_^)/" : "NO ;_;"; }, secondsEvenB));
bindB($('#stutter'), stutterB);
var template = ich['icanhaz-example'];
bindB($('#icanhaz-output'), mapB(template,
mapB(function(decis) { return {list: _.range(decis % 10)}; },
decisB)));
That was fun! If you agree, I highly recommend the literature surrounding this. There are a number of additional primitives needed, and most libraries provide a huge pile of them. The closest thing I can recall seeing about figuring out canonical primitives is this rather challenging paper.
For real libraries, I think Reactive in Haskell is the state of the art. I’m not sure about libraries in other languages, but would love to hear about them.
});
Type classes are an idea originally from Haskell that you can implement in Scala via implicit parameters. This is not new or obscure, but the technique is so useful that another post just demonstrating the basics can’t hurt. I will keep this brief — I have a lot to say about type classes, but first the fundamentals need to be extremely solid.
Let’s get imports out of the way.
import org.scalacheck._ import org.scalacheck.Prop._ import org.scalacheck.Gen._
Suppose I create a type such as a major-minor version scheme, or some such. It doesn’t really matter for this example.
case class Version(major: Int, minor: Int)
And suppose I want to serialize and deserialize it. To do this with a type class, I create a trait Serialize[T] that provides the ability to serialize/deserialize any value of type T. Implicit values implementing this trait are instances of the type class. (I prefix the methods with underscore to avoid name conflicts later, and this is not going to bother anyone because you should never call these methods directly. This is an entirely optional stylistic choice.)
trait Serialize[T] {
def _serialize(v:T) : String
def _deserialize(s:String) : Option[T] // May fail. In a robust implementation, we'd return Either[T, ReasonItFailed]
}
Next, I define functions that utilize this trait. These are the methods of the type class. A typical place for them is in the companion object. I also include a ScalaCheck property that should hold of any instance of the type class.
object Serialize {
def serialize[T](v: T)(implicit instance: Serialize[T]) =
instance._serialize(v)
def deserialize[T](s: String)(implicit instance: Serialize[T]) =
instance._deserialize(s)
def deserializeSerialize[T](v: T)(implicit instance: Serialize[T]) : Prop
= (deserialize(serialize(v)) ?= Some(v))
}
Now the type class is defined and I move on to instantiating it. In this case, I start by defining instances for standard types to build up to my own; this is common. Often instances for the standard types will also be shipped with the type class in the same companion object, but here they are in a totally separate module (if you are a seasoned OO programmer, this should already blow your mind a little). I’m not actually trying to make this robust, as you will generally want to go through an intermediate format such as JSON or XML which is more trivially compositional.
object SerializeInstances {
import Serialize._
implicit object serializeString extends Serialize[String] {
def _serialize(v: String) = v
def _deserialize(s: String) = Some(s)
}
implicit object serializeInt extends Serialize[Int] {
def _serialize(v: Int) = v.toString
def _deserialize(s: String) =
try { Some(s.toInt) } catch { case _ => None }
}
implicit def serializeTuple2[A, B]
(implicit l: Serialize[A], r: Serialize[B]) = new Serialize[(A, B)] {
def escape(s: String) = s.replaceAll("&", "&")
.replaceAll(",", ",")
def unescape(s: String) = s.replaceAll(",", ",")
.replaceAll("&", "&")
def _serialize(v: (A, B)) =
escape(serialize(v._1)) + "," + escape(serialize(v._2))
def _deserialize(s: String) =
s.split(",", -1).toList match {
case leftS :: rightS :: Nil => {
for(left <- deserialize[A](unescape(leftS));
right <- deserialize[B](unescape(rightS)))
yield (left, right)
}
case _ => None
}
}
}
Now I do a quick check (oblique pun intended) that the property holds via the sbt console.
$ xsbt console
scala> import Serialize._
import Serialize._
scala> import SerializeInstances._
import SerializeInstances._
scala> serialize(3)
res0: String = 3
scala> serialize("foo")
res1: String = foo
scala> serialize( (3, (5, "hello")) )
res2: String = 3,5,hello
scala> serialize( ("foo", 3), (7, 22))
res3: String = foo,3,7,22
scala> import org.scalacheck.Prop._
import org.scalacheck.Prop._
scala> forAll(deserializeSerialize[String] _) check
+ OK, passed 100 tests.
scala> forAll(deserializeSerialize[Int] _) check
+ OK, passed 100 tests.
scala> forAll(deserializeSerialize[(Int, String)] _) check
+ OK, passed 100 tests.
scala> forAll(deserializeSerialize[((String, Int), (Int, (Int, Int)))] _).check
+ OK, passed 100 tests.
In a real project, you probably want to use ScalaTest to manage a suite of tests. I tend to mix in Spec with Checkers.
Coming back to the Version type, we make a Serialize instance for it. To test it, we also need to make an instance of Arbitrary – ScalaCheck is a key example of a great library built on type classes. Note how in a brief and simple line I define a fuzz test generator (org.scalacheck.Gen[Version]) and wrap it into an Arbitrary[Version] instance.
object Version {
import Serialize._
import SerializeInstances._
implicit def arbVersion =
Arbitrary[Version] { resultOf(Version.apply _) }
implicit object serializeVersion extends Serialize[Version] {
def _serialize(v: Version) = Serialize.serialize(v.major, v.minor)
def _deserialize(s: String) = {
for((major, minor) <- deserialize[(Int, Int)](s))
yield Version(major, minor)
}
}
}
And check the property for this instance:
$ xsbt console ... scala> import Version._ import Version._ scala> forAll(deserializeSerialize[Version] _) check + OK, passed 100 tests.
There are a couple of reasonable interpretations of the definition / instantiation of type classes:
Both of the above make sense with the alternate syntax that Scala allows for implicit parameters used in this style: “def foo[T](implicit instance: Serialize[T])” may be shortened to “def foo[T: Serialize]“. In the latter syntax, you cannot actually name and call the methods of the instance; it is simply makes it possible to call serialize and deserialize by bringing the type class instance into scope.
There are huge number of advantages to type classes over simply implementing a trait. Here are some easily tangible ones:
Version type did not have to know about the serialization or deserialization code. In many real-world scenarios the instance may actually be provided by a separate library. This is probably the number one reason to use type classes. They introduce a form of code decoupling and reuse that simply does not exist without them.deserialize in the same type class as serialize. This cannot be done by implementing an interface as in “case class Version(...) extends Serializable” because the method is selected by the return type — it is obviously not an appropriate method of String!. In a more Java-esque world, you tend to have a separate — extraneous, in light of this — interface for a factory. For the logically inclined: Java-style OO has an unfortunate asymmetry between introduction and elimination forms.As a side note, having the scalacheck property helps to avoid the black hole of defensive programming, where you carefully check for errors and unexpected results. Instead, you can enjoy what I like to call offensive programming (pun definitely intended) where you blithely assume your tests have covered all corner cases.
Should you like to see more examples and explanations:
