After playing with Flapjax library in Javascript, I moved to Reactive to
learn more about FRP. Because research on Functional Reactive
Programming is most active in Haskell, I thought it would be better to
do that. Reactive seems to be a nice library, but unfortunately I
couldn't find many working code examples. So I show some of them as my
exercise. To write this, I owe a maoe's great
article in Japanese.
As I didn't have much time, I couldn't write a good explanation
now. But still I hope it helps some people who learn Reactive like
me. I used Haskell Platform 2010 (slightly old) and did cabal install reactive --enable-documentation to install Reactive.
The first example shows "Hello, World!" after three
seconds. atTime generates a timer event, and <$>
convert this event to IO action (\_ -> putStrLn "Hello, World!") which
writes a string.
This is as same as above, but it makes events each second.
This makes running Fibonnaci numbers. You can use scanlE
to process previous value and current value of the event in a
function. In this case, (0, 1) is the initial value, and when
an event occurs, the function \(n0, n1) _ -> (n1, n0 + n1) calculates
next value, and the result (the first case is (1, 1)) is used as a
next argument when a new event occurs.
It shows characters as you type. It looks difficult but you don't
have to worry about run function. The important part is
machine :: Event Char -> Event (IO ()) that convert a
character input event to an IO action.
This example shows how to merge two events. onType is same
as machine in the previous example, and onClock is
same as helloMany.hs example. I used `mappend` to
merge the two events
This shows a simple state machine. The function next
defines the state machine, and mealy_ convert the definition
to an event. zipE is another way to merge two events. Unlike
mappend, you can see two values in the two events in a same
time.
Functional Reactive Programming (FRP) is a framework to deal with
time-varying data in a clean way. It is a combination of beauty of
functional programming and dynamics of object oriented
programming. The basic principle is easy enough as spreadsheets,
however, its vague scope and arcane terminologies keep you from
grasping it. It's not quite easy to answer the question such as what
makes FRP different from Observer Pattern, Data Flow, etc ??. I think
a good way to explain FRP is to compare FRP library against non-FRP
library, and I could show you where FRP is special, and pros-and-cons
of FRP.
I examined Flapjax as an example of FRP, and took Bred Victor's
Tangle as the comparison target. Although Tangle has similar goal of
FRP as he wrote "Tangle is a library for creating reactive documents",
its implementation is quite different from Flapjax.
Flapjax
Side-effect is hidden inside the framework. Time-varying data is
represented by dependent tree, and you can compose those trees to
implement a complex behavior.
Tangle
Tangle provides a simple framework and UI widgets, but the data
flow is represented by a normal imperative programming and
assignments.
Because of those properties, I think comparing the two libraries is
helpful to understand what FRP is. I hope it makes clear idea about
FRP in your mind.
Simple Calorie Calculator in Tangle
This is the first example from the Tangle's documentation. You can
modify the number of cookies by dragging, and it keeps calculating the
calories as you change the value.
When you eat cookies,
you will consume calories.
To make this nice reactive document. This document consists with two parts,
HTML for the view and javascript for the model.
<p id="tangle"
When you eat <span data-var="cookies" class="TKAdjustableNumber" data-min="2" data-max="100"> cookies</span>,
you will consume <span data-var="calories"></span> calories.
</p>
The HTML part is straightforward, this is just a normal HTML except
special attributes for Tangle. Data-var is used to connect
HTML elements to Tangle object's
properties. Class name TKAdjustableNumber makes a draggable input
control. Data-min and data-max are its
parameters.
var element = document.getElementById("tangle");
new Tangle(element, {
initialize: function () {
this.cookies = 4;
},
update: function () {
this.calories = this.cookies * 50;
}
});
The actual model of the document is described in the second argument
of Tangle object's constructor (new Tangle). It consists with
just two parts. initialize sets up the initial state,
and update is invoked whenever you modify the input value.
Tangle connects the model and the HTML element specified
by getElementById("tangle").
This initialize-update structure is fairly common among end-user
programming language like Processing and Arduino.
Simple Calorie Calculator in Flapjax
Let's move on to Flapjax. Unfortunately, Flapjax doesn't have a
nice input widget as Tangle has. Instead, we use a traditional input
field. But other than that, the behavior is identical.
When you eat cookies,
you will consume calories.
As Tangle, the Flapjax version has HTML part and Javascript
part. Note that Flapjax provides "Flapjax Syntax" which allows you to
write a simpler notation, but we don't use it because I want to
compare those as Javascript libraries.
<p id="flapjax" class="example">
When you eat <input id="cookies" value="4" /> cookies,
you will consume <span id="calories"></span> calories.
</p>
Flapjax's HTML part is similar as Tangle's. The element identifiers
(cookies and calories) are given by
id attributes. Unlike Tangle, the initial number of cookies is written
in the input field.
var behavior = extractValueB("cookies");
var colories = behavior.liftB(function (n) { return n * 50; });
insertDomB(colories, "calories");
In Flapjax, time-varying data is called behavior. The goal
of the program is to make a behavior which always calculates calories
of the cookies. It's not so difficult than it
seems. ExtractValueB creates a behavior from a form element,
in this case, extractvalueB("cookies") tracks every changes
happening in the input field named "cookies". This created
behavior is processed by the function at the argument
of liftB, in this case, whenever you modify
"cookies" field, colories represents a value which
is always 50 times by the number of cookies.
Eventually, insertDomB insert the content
of colories where HTML element
"calories" is and the calories are shown on the
screen. This element is automatically updated.
Unlike Tangle, there is no side-effect in the program. One
advantage of FRP is that you are not confused between old values and
new values. In Tangle's example, this.cookies is old value
(input) and this.calories is new value (output). But you are
free to be mixed up those. In Flapjax, a new value is always the
return value of a function, and there is no chance to be mistaken.
Implement Adjustable Number Widget in Flapjax
One of advantages of FRP is its composability. You can make a
complicated behavior by combining simple behaviors (occasionally,
imperative programming gives you a hard time for debugging if the bug
involves with connected program modules with side-effects). To
demonstrate this feature, I will show you how to make a Tangle-style
draggable widget in Flapjax. This problem is particularly interesting
because processing drag and drop involves a state machine, but a state
machine is not quite fit with a functional programming style. So you
might find pros and cons of FRP clearly from this example.
When you eat cookies,
you will consume calories.
The HTML part is almost identical except adjustable class in
the input field which points a Tangle like (but not fashionable
enough) stylesheet.
<p id="flapjax-drag" class="example">
When you eat <input id="cookies-drag" value="4" class="adjustable"/> cookies,
you will consume <span id="calories-drag"></span> calories.
</p>
The main Javascript part is also similar as above. But in this
time, we are implementing makeAdjustableNumber to make a draggable
widget from the element named "cookies-drag".
var element = document.getElementById("cookies-drag");
var behavior = makeAdjustableNumber(element);
var colories = behavior.liftB(function (n) { return n * 50; });
insertDomB(colories, "calories-drag");
A drag gesture consists of three events, mousedown, mousemove, and
mouseup. After a mousedown is detected, it has to track mousemove
events to know how far you are dragging. You can make such a state
machine to construct a higher order event stream. Here are two
new concepts. An event stream is similar as behavior, but it is
a stream of discrete events instead of continuous values. But you
don't have to worry about that. It's just another object which has
slightly different API. A higher order event stream is an event
stream of event streams. This is used to make a stream which behavior
is switched depends on the input.
This mouseDownMove makes a higher order event stream that
tracks mousedown and
mousemove. extractEventE(element,"mousedown") extracts
mousedown event in the element. When the event signaled, the function
inside the mapE is evaluated. MapE is similar
as liftB but it is only for an event stream. Inside the
function, extractEventE(document,"mousemove") find mousemove
events and track the distance from mousedown. Note that I
used document to find the event because occasionally you drag
a mouse to outside the widget.
function mouseDownMove (element) {
return extractEventE(element,"mousedown").mapE(function(md) {
var initValue = parseInt(element.value);
var offset = md.layerX;
return extractEventE(document,"mousemove").mapE(function(mm) {
var delta = mm.layerX - offset;
return Math.max(1, Math.round(delta / 20 + initValue));
});
});
}
We need to handle mouseup event also. The mouseUp
function returns a higher order event stream that find mouseUp event
and the zeroE happily does nothing.
And these two event stream make by mouseDownMove
and mouseUp are going to be merged by the
mouseDownMoveUp function to complete a mousedown, mousemove,
and mouseup cycle. MergeE is used to merge two events
streams. We need one more step switchE to convert a higher
order stream to a nomal stream, in this case, a stream of numbers
(distance).
function mouseDownMoveUp(element) {
var downMoveUp = mouseDownMove(element).mergeE(mouseUp(element));
return downMoveUp.switchE();
}
Finally, we connect the event stream into an HTML element. Here I
did slightly dirty work. Whenever a drag gesture happens, the
element.value attribute is set. Probably
using insertDomB to make an output element is cleaner way,
but I chose this dirty way to make it simple. At the last line, the
event stream is converted to a behavior object
by startsWith. And that's how makeAdjustableNumber is
implemented.
function makeAdjustableNumber (element) {
var drag = mouseDownMoveUp(element);
drag.mapE(function(n) { element.value = n; });
return drag.startsWith(element.value);
}
Honestly, Flapjax doesn't seems to be too easy to use. But part of
the reasons might be that I chose to show a plain Javascript syntax to
introduce the mechanism. Flapjax also provides its own compiler which
provides cleaner syntax. This Flapjax syntax should improve
readability a lot. Anyway, I hope this short note helps you to grab a
brief idea of Flapjax and FRP.
Bret Victor came to our office
yesterday, and we had a great chat. He is a great thinker and has a
beautiful sense about visualizing abstract ideas. I really like his
works. I want to learn his idea more, but as a starter, I tried to
implement his early
famous Alligator
Eggs! game. This game was made to teach about lambda calculus to
eight years old kids. But it's even more fun to adult hackers!
This is a green alligator and her egg. This family shows a lambda
expression λx.x (because I know you are not an eight years old, I use
formulas without hesitation!). There is a no animation as there is
nothing to eat.
But things are getting fun when there is something to eat before
the alligator mother. In this case, a blue egg. If you click on the
diagram, you see what's happening (I only tested Chrome, Safari, and
Firefox). The alligator eats the poor blue egg. But price for the
sacrifice is too high. The mother will die, and we will see the
new baby.
And then, things are getting curiouser. The new baby doesn't look
like the mother at all, rather it is like a blue egg, the victim of
the slaughter. What's a amazing nature of the lambda land!
This is slightly a hard example. There are two alligators "x" and
"y", and two victim eggs "a" and "b" on the right side. If there are
more than two things next to an alligator, the alligator eats left one
first (it is called as left associative in jargon). Can you guess what
does happen after the meal? Alligator "x" eats egg "a", and alligator
"y" eats egg "b". And only egg "a" survives (because it transmigrates
through the green "x" egg).
You can think that this alligator family (λx.λy. x) eats two
things and leave the first one. In a same way, can you think of an
alligator family which eats two things and leave the second one? Here
is
the answer.
There are a few things to know more. Old alligators are not
hungry. But they keep guarding their family while they guard more than
one things. They behave like parenthesis in a lambda expression.
This rule is the most tricky one. There are two blue alligators "y"
at left and right, but those two are not in a same family. The only
mother of the blue egg "y" is the right one. It gets trickier when the
family is eaten by the green alligator because the blue family is
reborn at the green egg is, where is bottom of another blue
alligator. To make them different, the right blue family change the
name and color to "y1" and orange.
By these rules, you can make various kinds of alligator
ecosystem. This is my favorite one. (λx.x x) is called a
"Mockingbird" or, rather we should call it Mockingalligator. It
doubles its prey twice. So what happens if a mockingalligator eats a
mockingalligator? The result is called one of omegas, an infinite
loop. They are eating forever. To stop the endless violence, please
click the diagram again. But please do not to click three times!
Because of my bug, something wrong will be happening.
This is dangerous but beautiful one. The omega ecosystem above kills each
other but it doesn't make any, but this Y combinator is very
fertile. It produce many, so you have to watch it carefully, otherwise
it consumes all the CPU power you have eventually!!
Actually, alligators also can do serious jobs. If you design
carefully, you can teach them how to calculate 3 + 4! In this example,
the middle family represents three and the right family represents
four (count green eggs). And the result is a family with seven green
eggs! This is
called Church
numbers (I don't have a time to explain the theory, so please read
the link).
I only introduced very few alligator families. If you want play it,
visit
http://metatoys.org/alligator/
and design by your self. You can also download from
http://github.com/propella/AlligatorEggs. The
source code is messy because I haven't written javascript recently,
but I'll clean it up soon.
If you have played with Etoys, you might have seen The Etoys
Castle (or The Demon Castle) tutorial. But you would never know how
the story ends, because the Etoys distribution only includes the first
chapter, and the last slide shows "To Be Continued ...". However,
there are actually the hidden sequels, and the story has a happy
ending.
When I first wrote the story in 2006, there were three
chapters. The first chapter was about learning "handles", the second
one was about the painter, and the third one was about scripting. But
due to some technical issues, I gave up to publish them. Today, I
happened to clean up my hard drive and I found old files. It's shame
that I have never published rest of them. So I gathered the screen
shots and made up one page html.
