website | twitter

Thursday, December 15, 2011

Various examples in Haskell's FRP.Reactive

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.

(This page has been translated into Spanish language by Maria Ramos from Webhostinghub.com.)

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.

Tuesday, December 06, 2011

Flapjax vs Tangle

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.

function mouseUp (element) {
  return extractEventE(document,"mouseup").mapE(function() {
    return zeroE();
  });
}

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.

References

Thursday, September 22, 2011

Yet Another "Alligator Eggs!" Animation

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!

Alligator and an egg : λx.x

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.

An alligator eats an egg : (λx.x) y

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!

Take first : (λx.λy. x) a b

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.

Old alligator : (λx.x) ((λy.y) (λz.z))

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.

Color rule : (λx.λy.x) (λy.y)

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.

Omega (Mockingbird hears the Mockingbird song) : (λx.x x) (λx.x x)

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.

Y combinator : λg.(λx.g (x x)) (λx.g (x x))

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!!

3 + 4 : (λa.λb.λs.λz.(a s (b s z))) (λs.λz.(s (s (s z)))) (λs.λz.(s (s (s (s z)))))

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.

Saturday, July 09, 2011

A hidden story behind the EToys Castle

http://metatoys.org/demonCastle/

Demon Castle Demon Castle Demon Castle Demon Castle Demon Castle Demon Castle

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.

 
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 Unported License.