tag:blogger.com,1999:blog-82729792024-03-07T00:59:08.935-08:00TAKASHI'S WORKSPACETakashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.comBlogger82125tag:blogger.com,1999:blog-8272979.post-66056225238965917432011-12-15T11:17:00.000-08:002013-04-12T18:43:25.019-07:00Various examples in Haskell's FRP.Reactive<p>After playing with Flapjax library in Javascript, I moved to <a
href="http://www.haskell.org/haskellwiki/Reactive">Reactive</a> 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 <a
href="http://d.hatena.ne.jp/maoe/20100116/1263661213">maoe's great
article in Japanese</a>.</p>
(This page has been translated into <a href="http://www.webhostinghub.com/support/es/misc/varios-ejemplos-en-haskells">Spanish</a> language by Maria Ramos from <a href="http://www.webhostinghub.com/">Webhostinghub.com</a>.)
<p>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 <tt>cabal install reactive --enable-documentation</tt> to install Reactive.</p>
<script src="https://gist.github.com/1482263.js?file=hello.hs"></script>
<p>The first example shows "Hello, World!" after three
seconds. <tt>atTime</tt> generates a timer event, and <$>
convert this event to IO action (\_ -> putStrLn "Hello, World!") which
writes a string.
</p>
<script src="https://gist.github.com/1482263.js?file=helloMany.hs"></script>
<p>This is as same as above, but it makes events each second.</p>
<script src="https://gist.github.com/1482263.js?file=fibs.hs"></script>
<p>This makes running Fibonnaci numbers. You can use <tt>scanlE</tt>
to process previous value and current value of the event in a
function. In this case, <tt>(0, 1)</tt> 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.</p>
<script src="https://gist.github.com/1482263.js?file=type.hs"></script>
<p>It shows characters as you type. It looks difficult but you don't
have to worry about <tt>run</tt> function. The important part is
<tt>machine :: Event Char -> Event (IO ())</tt> that convert a
character input event to an IO action.</p>
<script src="https://gist.github.com/1482263.js?file=typeClock.hs"></script>
<p>This example shows how to merge two events. <tt>onType</tt> is same
as <tt>machine</tt> in the previous example, and <tt>onClock</tt> is
same as <tt>helloMany.hs</tt> example. I used <tt>`mappend`</tt> to
merge the two events</p>
<script src="https://gist.github.com/1482263.js?file=mealy.hs"></script>
<p>This shows a simple state machine. The function <tt>next</tt>
defines the state machine, and <tt>mealy_</tt> convert the definition
to an event. <tt>zipE</tt> is another way to merge two events. Unlike
<tt>mappend</tt>, you can see two values in the two events in a same
time.</p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com1tag:blogger.com,1999:blog-8272979.post-71879278266036470002011-12-06T01:00:00.000-08:002011-12-06T01:12:21.466-08:00Flapjax vs Tangle<style type="text/css">
.example {
border: 1px solid #9cc;
padding: 1em 1em 1em 1em;
border-radius: 10px;
-moz-border-radius: 10px;
}
dt {
font-weight: bold;
}
dd {
margin: 0em 0em 1em 2em;
}
pre { padding: 6px; background-color: #dee; }
.adjustable {
cursor: col-resize;
border-style: none;
color: #46F;
border-bottom: 1px dashed #46F;
font-size: medium;
}
.TKCursorDragHorizontal {
cursor: pointer;
cursor: move;
cursor: col-resize;
}
.TKAdjustableNumber {
position:relative;
color: #46f;
border-bottom: 1px dashed #46f;
}
.TKAdjustableNumberHover {
}
.TKAdjustableNumberDown {
color: #00c;
border-bottom: 1px dashed #00c;
}
.TKAdjustableNumberHelp {
position:absolute;
color: #00f;
font: 9px "Helvetica-Neue", "Arial", sans-serif;
}
</style>
<script type="text/javascript" src="http://metatoys.org/flapjax/Tangle.js"></script>
<script type="text/javascript" src="http://metatoys.org/flapjax/TangleKit/mootools.js"></script>
<script type="text/javascript" src="http://metatoys.org/flapjax/TangleKit/sprintf.js"></script>
<script type="text/javascript" src="http://metatoys.org/flapjax/TangleKit/BVTouchable.js"></script>
<script type="text/javascript" src="http://metatoys.org/flapjax/TangleKit/TangleKit.js"></script>
<script type="text/javascript" src="http://metatoys.org/flapjax/flapjax.js"></script>
<script type="text/javascript" src="http://metatoys.org/flapjax/TangleFlapjax.js"></script>
<p>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.
</p>
<p>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.
</p>
<dl>
<dt>Flapjax</dt>
<dd>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.</dd>
<dt>Tangle</dt>
<dd>Tangle provides a simple framework and UI widgets, but the data
flow is represented by a normal imperative programming and
assignments.</dd>
</dl>
<p>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.</p>
<h4>Simple Calorie Calculator in Tangle</h4>
<p>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.</p>
<p id="tangle" class="example">
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>
<p>To make this nice reactive document. This document consists with two parts,
HTML for the view and javascript for the model.</p>
<pre>
<p id="tangle"
When you eat <span <b>data-var</b>="cookies" class="<b>TKAdjustableNumber</b>" <b>data-min</b>="2" <b>data-max</b>="100"> cookies</span>,
you will consume <span data-var="calories"></span> calories.
</p>
</pre>
<p>The HTML part is straightforward, this is just a normal HTML except
special attributes for Tangle. <tt>Data-var</tt> is used to connect
HTML elements to Tangle object's
properties. Class name <tt>TKAdjustableNumber</tt> makes a draggable input
control. <tt>Data-min</tt> and <tt>data-max</tt> are its
parameters.</p>
<pre>
var element = document.getElementById("tangle");
new Tangle(element, {
initialize: function () {
this.<b>cookies</b> = 4;
},
update: function () {
this.<b>calories</b> = this.cookies * 50;
}
});
</pre>
<p>
The actual model of the document is described in the second argument
of Tangle object's constructor (<tt>new Tangle</tt>). It consists with
just two parts. <tt>initialize</tt> sets up the initial state,
and <tt>update</tt> is invoked whenever you modify the input value.
Tangle connects the model and the HTML element specified
by <tt>getElementById("tangle")</tt>.
</p>
<p>This initialize-update structure is fairly common among end-user
programming language like Processing and Arduino.
</p>
<h4>Simple Calorie Calculator in Flapjax</h4>
<p>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.</p>
<p id="flapjax" class="example">
When you eat <input id="cookies" value="4" /> cookies,
you will consume <span id="calories"></span> calories.
</p>
<p>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>
<pre>
<p id="flapjax" class="example">
When you eat <input id="<b>cookies</b>" value="4" /> cookies,
you will consume <span id="<b>calories</b>"></span> calories.
</p>
</pre>
<p>Flapjax's HTML part is similar as Tangle's. The element identifiers
(<tt>cookies</tt> and <tt>calories</tt>) are given by
id attributes. Unlike Tangle, the initial number of cookies is written
in the input field.</p>
<pre>
var behavior = extractValueB("<b>cookies</b>");
var colories = behavior.liftB(function (n) { return n * 50; });
insertDomB(colories, "<b>calories</b>");
</pre>
<p>In Flapjax, time-varying data is called <b>behavior</b>. 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. <tt>ExtractValueB</tt> creates a behavior from a form element,
in this case, <tt>extractvalueB("cookies")</tt> tracks every changes
happening in the input field named "<tt>cookies</tt>". This created
behavior is processed by the function at the argument
of <tt>liftB</tt>, in this case, whenever you modify
"<tt>cookies</tt>" field, <tt>colories</tt> represents a value which
is always 50 times by the number of cookies.
</p>
<p>Eventually, <tt>insertDomB</tt> insert the content
of <tt>colories</tt> where HTML element
"<tt>calories</tt>" is and the calories are shown on the
screen. This element is automatically updated.
</p>
<p>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, <tt>this.cookies</tt> is old value
(input) and <tt>this.calories</tt> 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.
</p>
<h4>Implement Adjustable Number Widget in Flapjax</h4>
<p>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.
</p>
<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>
<p>The HTML part is almost identical except <tt>adjustable</tt> class in
the input field which points a Tangle like (but not fashionable
enough) stylesheet.</p>
<pre>
<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>
</pre>
<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 "<tt>cookies-drag</tt>".</p>
<pre>
var element = document.getElementById("cookies-drag");
<b>var behavior = makeAdjustableNumber(element);</b>
var colories = behavior.liftB(function (n) { return n * 50; });
insertDomB(colories, "calories-drag");
</pre>
<p>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 <b>a higher order event stream</b>. Here are two
new concepts. <b>An event stream</b> 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. <b>A higher order event stream</b> is an event
stream of event streams. This is used to make a stream which behavior
is switched depends on the input. </p>
<p>This <tt>mouseDownMove</tt> makes a higher order event stream that
tracks mousedown and
mousemove. <tt>extractEventE(element,"mousedown")</tt> extracts
mousedown event in the element. When the event signaled, the function
inside the <tt>mapE</tt> is evaluated. <tt>MapE</tt> is similar
as <tt>liftB</tt> but it is only for an event stream. Inside the
function, <tt>extractEventE(document,"mousemove")</tt> find mousemove
events and track the distance from mousedown. Note that I
used <tt>document</tt> to find the event because occasionally you drag
a mouse to outside the widget.</p>
<pre>
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));
});
});
}
</pre>
<p>We need to handle mouseup event also. The <tt>mouseUp</tt>
function returns a higher order event stream that find mouseUp event
and the <tt>zeroE</tt> happily does nothing.</p>
<pre>
function mouseUp (element) {
return extractEventE(document,"mouseup").mapE(function() {
return zeroE();
});
}
</pre>
<p>And these two event stream make by <tt>mouseDownMove</tt>
and <tt>mouseUp</tt> are going to be merged by the
<tt>mouseDownMoveUp</tt> function to complete a mousedown, mousemove,
and mouseup cycle. <tt>MergeE</tt> is used to merge two events
streams. We need one more step <tt>switchE</tt> to convert a higher
order stream to a nomal stream, in this case, a stream of numbers
(distance).
</p>
<pre>
function mouseDownMoveUp(element) {
var downMoveUp = mouseDownMove(element).<b>mergeE(mouseUp(element))</b>;
return downMoveUp.<b>switchE()</b>;
}
</pre>
<p>Finally, we connect the event stream into an HTML element. Here I
did slightly dirty work. Whenever a drag gesture happens, the
<tt>element.value</tt> attribute is set. Probably
using <tt>insertDomB</tt> 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 <tt>startsWith</tt>. And that's how makeAdjustableNumber is
implemented.
<pre>
function makeAdjustableNumber (element) {
var drag = mouseDownMoveUp(element);
drag.mapE(function(n) { element.value = n; });
return drag.startsWith(element.value);
}
</pre>
<p>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.
</p>
<h4>References</h4>
<ul>
<li><a href="http://www.flapjax-lang.org/tutorial/">Flapjax Tutorial</a></li>
<li><a href="http://worrydream.com/Tangle/guide.html">Tangle: Getting Started</a></li>
</ul>
<script type="text/javascript">
initialize();
</script>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com1tag:blogger.com,1999:blog-8272979.post-1980372818312143652011-09-22T19:49:00.000-07:002011-09-22T19:51:16.092-07:00Yet Another "Alligator Eggs!" Animation<p><a href="http://worrydream.com/">Bret Victor</a> 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 <a href="http://worrydream.com/AlligatorEggs/">Alligator
Eggs!</a> game. This game was made to teach about lambda calculus to
eight years old kids. But it's even more fun to adult hackers!</p>
<h4>Alligator and an egg : <a href="http://metatoys.org/alligator/#!/%CE%BBx.x">λx.x</a></h4>
<iframe width="400" height="300" src="http://metatoys.org/alligator/iframe.html?width=400&height=300#!/%CE%BBx.x" style="border: 0px solid #8c8;"></iframe>
<p>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.
</p>
<h4>An alligator eats an egg : <a href="http://metatoys.org/alligator/#!/(%CE%BBx.x)%20y">(λx.x) y</a></h4>
<iframe width="400" height="300" src="http://metatoys.org/alligator/iframe.html?width=400&height=300#!/(%CE%BBx.x)%20y" style="border: 0px solid #8c8;"></iframe>
<p>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.</p>
<p>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!</p>
<h4>Take first : <a href="http://metatoys.org/alligator/#!/(%CE%BBx.%CE%BBy.%20x)%20a%20b">(λx.λy. x) a b</a></h4>
<iframe width="400" height="300" src="http://metatoys.org/alligator/iframe.html?width=400&height=300#!/(%CE%BBx.%CE%BBy.%20x)%20a%20b" style="border: 0px solid #8c8;"></iframe>
<p>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).</p>
<p>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 <a href="http://metatoys.org/alligator/#!/(%CE%BBx.%CE%BBy.%20y)%20a%20b">answer</a>.</p>
<h4>Old alligator : <a href="http://metatoys.org/alligator/#!/(%CE%BBx.x)%20((%CE%BBy.y)%20(%CE%BBz.z))">(λx.x) ((λy.y) (λz.z))</a></h4>
<iframe width="400" height="300" src="http://metatoys.org/alligator/iframe.html?width=400&height=300#!/(%CE%BBx.x)%20((%CE%BBy.y)%20(%CE%BBz.z))" style="border: 0px solid #8c8;"></iframe>
<p>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.</p>
<h4>Color rule : <a href="http://metatoys.org/alligator/#!/(%CE%BBx.%CE%BBy.x)%20(%CE%BBy.y)">(λx.λy.x) (λy.y)</a></h4>
<iframe width="400" height="300" src="http://metatoys.org/alligator/iframe.html?width=400&height=300#!/(%CE%BBx.%CE%BBy.x)%20(%CE%BBy.y)" style="border: 0px solid #8c8;"></iframe>
<p>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.
</p>
<h4>Omega (Mockingbird hears the Mockingbird song) : <a href="http://metatoys.org/alligator/#!/(%CE%BBx.x%20x)%20(%CE%BBx.x%20x)">(λx.x x) (λx.x x)</a></h4>
<iframe width="400" height="300" src="http://metatoys.org/alligator/iframe.html?width=400&height=300#!/(%CE%BBx.x%20x)%20(%CE%BBx.x%20x)" style="border: 0px solid #8c8;"></iframe>
<p>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.</p>
<h4>Y combinator : <a href="http://metatoys.org/alligator/#!/%CE%BBg.(%CE%BBx.g%20(x%20x))%20(%CE%BBx.g%20(x%20x))">λg.(λx.g (x x)) (λx.g (x x))</a></h4>
<iframe width="400" height="300" src="http://metatoys.org/alligator/iframe.html?width=400&height=300#!/%CE%BBg.(%CE%BBx.g%20(x%20x))%20(%CE%BBx.g%20(x%20x))" style="border: 0px solid #8c8;"></iframe>
<p>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!!
</p>
<h4>3 + 4 : <a href="http://metatoys.org/alligator/#!/(%CE%BBa.%CE%BBb.%CE%BBs.%CE%BBz.(a%20s%20(b%20s%20z)))%20(%CE%BBs.%CE%BBz.(s%20(s%20(s%20z))))%20(%CE%BBs.%CE%BBz.(s%20(s%20(s%20(s%20z)))))">(λa.λb.λs.λz.(a s (b s z))) (λs.λz.(s (s (s z)))) (λs.λz.(s (s (s (s z)))))</a></h4>
<iframe width="400" height="300" src="http://metatoys.org/alligator/iframe.html?width=400&height=300#!/(%CE%BBa.%CE%BBb.%CE%BBs.%CE%BBz.(a%20s%20(b%20s%20z)))%20(%CE%BBs.%CE%BBz.(s%20(s%20(s%20z))))%20(%CE%BBs.%CE%BBz.(s%20(s%20(s%20(s%20z)))))" style="border: 0px solid #8c8;"></iframe>
<p>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 <a href="http://en.wikipedia.org/wiki/Church_encoding">Church
numbers</a> (I don't have a time to explain the theory, so please read
the link).
</p>
<p>I only introduced very few alligator families. If you want play it,
visit
<a href="http://metatoys.org/alligator/">http://metatoys.org/alligator/</a>
and design by your self. You can also download from
<a href="http://github.com/propella/AlligatorEggs">http://github.com/propella/AlligatorEggs</a>. The
source code is messy because I haven't written javascript recently,
but I'll clean it up soon.
</p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-36690259791203606872011-07-09T19:21:00.000-07:002011-07-09T19:24:18.985-07:00A hidden story behind the EToys Castle<p>
<a href="http://metatoys.org/demonCastle/">http://metatoys.org/demonCastle/</a>
</p>
<a href="http://www.flickr.com/photos/propella/5920655510/" title="Demon Castle by propella, on Flickr"><img src="http://farm7.static.flickr.com/6135/5920655510_1f6f026939_m.jpg" width="240" height="171" alt="Demon Castle"></a>
<a href="http://www.flickr.com/photos/propella/5920092791/" title="Demon Castle by propella, on Flickr"><img src="http://farm7.static.flickr.com/6123/5920092791_fe9a83d539_m.jpg" width="240" height="180" alt="Demon Castle"></a>
<a href="http://www.flickr.com/photos/propella/5920656128/" title="Demon Castle by propella, on Flickr"><img src="http://farm7.static.flickr.com/6012/5920656128_e3d26cb172_m.jpg" width="240" height="180" alt="Demon Castle"></a>
<a href="http://www.flickr.com/photos/propella/5920093141/" title="Demon Castle by propella, on Flickr"><img src="http://farm7.static.flickr.com/6145/5920093141_2f7b7583ef_m.jpg" width="240" height="180" alt="Demon Castle"></a>
<a href="http://www.flickr.com/photos/propella/5920093223/" title="Demon Castle by propella, on Flickr"><img src="http://farm7.static.flickr.com/6146/5920093223_3e64a8ab9d_m.jpg" width="240" height="180" alt="Demon Castle"></a>
<a href="http://www.flickr.com/photos/propella/5920656468/" title="Demon Castle by propella, on Flickr"><img src="http://farm7.static.flickr.com/6018/5920656468_204175df6a_m.jpg" width="240" height="180" alt="Demon Castle"></a>
<p> If you have played with <a
href="http://squeakland.org/">Etoys</a>, 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. </p>
<p> 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. </p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-74142732641582866942010-09-24T00:45:00.000-07:002010-10-04T14:38:03.632-07:00Tamacola (5)Tamacola is not just another LISP language, it is designed as a
meta-language to make a new language. I'll explain this feature today.
Today's goal is to design a subset of lisp language. If you think that
a lisp is too simple to keep your passion, sorry, be patient, simple
thing first.
<h4>Prepare your Tamacola environment</h4>
To setup Tamacola environment, you need to download both Tamacola
distribution and Tamarin VM. Those are available on
<a href="http://www.vpri.org/vp_wiki/index.php/Tamacola">http://www.vpri.org/vp_wiki/index.php/Tamacola</a>. You
need add the PATH environment variable to find the avmshell command,
and also it would be useful to set the PATH to bin/ in the tamacola
tree.
To make sure Tamacola works, plese type:
<pre>
make run-example
</pre>
It runs all of the examples in the Tamacola distribution as well as
recompile the compiler. If you don't find any error, you are ready to
go. Otherwise, please let me know the problem.
<h4>Tamacola command</h4>
Tamacola command read a tamacola program and run immediately. If you
want to make a Flash contents, another command tamacc (Tamacola
Compiler) is more suitable. Now we are playing with an interactive
shell of tamacola command, so I'll give you a brief explanation.
The interactive shell starts with minus (-) option. Let's try a simple
arithmetic. If you didn't setup PATH environment, please specify the
directory name, too.
<pre>
$ tamacola -
Cola/Tamarin
> (+ 3 4)
7
</pre>
You can also give Tamacola source files as well as compiled binary
names. Typically, source code ends with .k, and a binary ends with
.abc. Tamacola is smart enough to detect newer file between .k and
.abc.
<h4>Match against a string constant</h4>
<p>Suppose you are on some working directory, and you have already set
PATH environment to the bin/ directory. And then, we are going to
write a very simple language, greeting:</p>
<pre>
;; greeting.g - A simple PEG example
greeting = "morning" -> "Good Morning!"
| "evening" -> "Good Evening!"
</pre>
<p>This stupid example answers "Good Morning!" if you say "morning", and
it answers "Good Evening!" if you say "evening". This PEG syntax is
easy to understand. The right hand side of = is a rule name. A rule
name is translated as a function once it is built. -> means an action
rule, where if the left hand is matched the right hand side is
returned. | is an Ordered options. In this case, the parser tries the
first case "morning", and tries the second case "evening" only if the
first case fails.</p>
<p>Save this syntax named "greeting.g". To test this language, type those
commands:</p>
<pre>
$ mkpeg greeting.g
$ tamacola greeting.k -
compiling: greeting.k
Cola/Tamarin
> (parse-collection greeting "morning")
"Good Morning!"
> (parse-collection greeting "evening tokyo")
"Good Evening!"
</pre>
<p>Mkpeg command converts grammar file (greeting.g) to tamacola source
(greeting.k), a rule "greeting" the result can be read by tamacola
shell. Greeting.k is built on the fly and the command prompt is shown.</p>
<p>Parse-collection's first argument is a parser name (in this case
"greeting"), and the second is a input collection. As the name
implies, it accepts any collection as the input stream.</p>
<p>The second case shows an interesting property of PEG syntax. Although
the second rule matches the beginning part of the input "evening
tokyo", still the input remains more string " tokyo". PEG doesn't care
if the input is competely consumed or not. If you really want to make
sure that the entire input is matched, you need to explicitly tell the
Parser the point where end of the file.</p>
<h4>Number parser</h4>
<p>The last example only matched a predefined constant, but we make a
parser for any integer number here.</p>
<pre>
;; number.g -- A number parser
digit = [0123456789]
number = digit+
</pre>
<p>We also convert the grammar specification into the tamacola program,
but in this case, we give -n option to tell the namespace. A namespace
is useful when you want to use a common name as a rule name like
"number". Because "number" is already used in the system, you can not
use it without namespace.</p>
<p>The grammar itself is easy to understand if you have an experience
with regular expressoins. Brackets ([]) matches one of characters
inside, and postfixed plus (+) repeats previous expression with
one-or-many times.</p>
<pre>
$ mkpeg -n number number.g
$ tamacola number.k -
compiling: number.k
Cola/Tamarin
> (parse-collection number/number "xyz")
FAIL
> (parse-collection number/number "345")
{token-group:
(53 52 51)}
</pre>
<p>Because we use the namespace "number", we need specify the
namespace before slash(/) in the function name.</p>
<p>As you might notice, this parser correctly rejects a non-number like
"xyz", and accepts "345". But the result is not so useful. The return
value of plus is a special object named "token-group", but we would
want a number represented by the string, instead. So we put a
conversion function to get the value.</p>
<pre>
number = digit+:n -> (string->number (->string n))
</pre>
<pre>
$ tamacola number.k -
compiling: number.k
Cola/Tamarin
> (parse-collection number/number "345")
345
</pre>
<p>Now parser returns a number conveniently. Perhaps you might think that
it is somewhat cheating. As the string->number function itself is a
kind of number parser, we should have write a number parser without
string->number! Yes we could. But it leads more interesting topic
about left and right recursion, so I leave it for later.</p>
<h4>S-expression parser</h4>
<p>Now we are going to write a parser for almost real S-expression. This
parser can only handle number and list, but it is useful enough to
explain the essence of Tamacola.</p>
<pre>
;; sexp.g
;; Lexical Parser
spaces = [ \t\r\n]*
digit = [0123456789]
number = digit+ :n spaces -> (string->number (->string n))
char = [+-*/abcdefghijklmnopqrstuvwxyz]
symbol = char+ :s spaces -> (intern (->string s))
sexp = symbol
| number
| "(" sexp*:e ")" -> (->list e)
</pre>
<p>In this grammar, only new operator is the postfix star (*) which
repeats zero-or-many times. Rest is straightforward. To test this
grammar, we use Tamacola's simple test framework. Writing test case is
better than the interactive shell, because you don't have to type same
expression many times.</p>
<pre>
;; sexp-test.k
(check (parse-collection sexp/spaces " ") => 'SPACES)
(check (parse-collection sexp/digit "0") => 48)
(check (parse-collection sexp/number "345") => 345)
(check (parse-collection sexp/char "a") => 97)
(check (parse-collection sexp/symbol "hello") => 'hello)
(check (parse-collection sexp/sexp "345") => 345)
(check (parse-collection sexp/sexp "hello") => 'hello)
(check (parse-collection sexp/sexp "(hello world)") => '(hello world))
(check (parse-collection sexp/sexp "(3 4)") => '(3 4))
(check (parse-collection sexp/sexp "(print 4)") => '(print 4))
</pre>
<p>The check function comes from SRFI-78. This function complains only if
the left hand value and the right hand value differ. Otherwise, does
nothing. I like this UNIX stile conciseness.</p>
<p>As a convention, a test program is added a postfix "-test" with the
main program's name. I borrowed this custom from Go language.</p>
<p>Make sure this program do nothing.</p>
<pre>
$ tamacola sexp.k sexp-test.k
</pre>
<h4>Lisp Compiler</h4>
<p>The PEG parser can handle any list structure as well as string. It
allows you to write compiler in PEG. In a string parser, the input is
a string and the output is some object (a list in our case), but in a
compiler, the input is a lisp program and the output is a assembler
code.</p>
<pre>
;; Compiler
arity = .*:x -> (length (->list x))
insts = inst* :xs -> (concatenate (->list xs))
inst = is-number:x -> `((pushint ,x))
| is-symbol:x -> `((getlex ((ns "") ,(symbol->string x))))
| '( '+ inst:x inst:y ) -> `(,@x ,@y (add))
| '( '- inst:x inst:y ) -> `(,@x ,@y (subtract))
| '( '* inst:x inst:y ) -> `(,@x ,@y (multiply))
| '( '/ inst:x inst:y ) -> `(,@x ,@y (divide))
| '( inst:f &arity:n insts:a ) -> `(,@f (pushnull) ,@a (call ,n))
</pre>
<p>There are some new elements in the grammar. Quoted list '( ) matches a
list structure, and a quoted symbol matches a symbol.</p>
<p>A prefix ampersand (&) prevents to consume the stream even if the rule
matches. For example, &arity rule examine the rest of the list, but
the contents are matched again by the insts rule later.</p>
<p>Is-number is matched against number, and is-symbol is for a
symbol. Those rule can not be described as PEG grammar, but as a lisp
function.</p>
<pre>
(define is-number
(lambda (*stream* *parser*)
(if (number? (peek *stream*))
(begin (set-parser-result *parser* (next *stream*))
#t)
#f)))
(define is-symbol
(lambda (*stream* *parser*)
(if (symbol? (peek *stream*))
(begin (set-parser-result *parser* (next *stream*))
#t)
#f)))
</pre>
<p>A rule is a function which receives the stream and the parser (an
object which store the result). The rule function returns #t if it
matches, and #f if it fails.</p>
<p>I think it is easier to see the test code than read my explanation.</p>
<pre>
(check (parse-collection sexp/arity '(a b c)) => 3)
(check (parse-collection sexp/insts '(3 4) => '((pushint 3)
(pushint 4)))
(check (parse-collection sexp/inst '(3)) => '((pushint 3)))
(check (parse-collection sexp/inst '((+ 3 4))) => '((pushint 3)
(pushint 4)
(add)))
(check (parse-collection sexp/inst '((f 3 4))) => '((getlex ((ns "") "f"))
(pushnull)
(pushint 3)
(pushint 4)
(call 2)))
</pre>
<h4>Put it in an envelope</h4>
<p>We still need a little bit to construct a real assembler code. This
detail topic is out of the context, so I simply show the code.</p>
<pre>
program = inst:x -> `(asm
(method (((signature
((return_type *) (param_type ()) (name "program")
(flags 0) (options ()) (param_names ())))
(code ((getlocal 0)
(pushscope)
,@x
(returnvalue))))))
(script (((init (method 0)) (trait ())))))
</pre>
<p>And the test case.<p>
<pre>
(check (parse-collection sexp/program '((print 42)))
=> '(asm
(method
(((signature ((return_type *) (param_type ()) (name "program")
(flags 0) (options ()) (param_names ())))
(code ((getlocal 0)
(pushscope)
(getlex ((ns "") "print"))
(pushnull)
(pushint 42)
(call 1)
(returnvalue))))))
(script (((init (method 0)) (trait ()))))))
</pre>
<p>You can read the entire program in example/sexp.g in the Tamacola
distribution. To try the program, please enter:</p>
<pre>
make -C example test-sexp
</pre>
<h4>Left recursion</h4>
<p>We left an interesting topic about left and right recursion. Let me show you our number parser again.</p>
<pre>
digit = [0123456789]
number = digit+:n -> (string->number (->string n))
</pre>
<p>If we don't want to use string->number function, I would write the parser as:</p>
<pre>
;; Use fold-left
digit1 = [0123456789]:d -> (- d 48)
number1 = digit1:x digit1*:xs -> (fold-left
(lambda (n d) (+ (* n 10) d))
x
(->list xs))
</pre>
<p>Digit1 rule converts the ascii value of the the digit character,
and number1 rule construct a decimal number. As you see, you need to
use fold-left function to construct a number because a number notation
is essentially left recursion. For example, a number 34567 actually
means:</p>
<pre>(((3 * 10 + 4) * 10 + 5) * 10 + 6) * 10 + 7</pre>
<p>However, PEG parser doesn't parse left recursion grammar in
general. So I had to reconstruct the left recursion structure by
fold-left. This is not hard at all if you familiar with functional
programming. In functional programming, a list is considered as a
right recursive data structure and it is even natural that a list is
parsed by a right recursive way. However, I admit that it looks
awkward for some people.</p>
<p>Yoshiki Ohshima provides a very useful extension to support a direct
left recursion. To use his extension, the number parser is written as:<p>
<pre>
;; Use left-recursion
digit2 = [0123456789]:d -> (- d 48)
number2 = number2:n digit2:d -> (+ (* n 10) d)
| digit2
number2s = number2
</pre>
<p>You need to load runtime/peg-memo-macro.k to use this extension.</p>
<pre>
$ tamacola ../runtime/peg-memo-macro.k number.k -
Cola/Tamarin
> (parse-collection number/number2s "345")
345
</pre>
<p>The real parser and compiler are bigger than presented grammars here,
but I explained all of the essential ideas. I hope it helps you to
make your own language!</p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com2tag:blogger.com,1999:blog-8272979.post-34949880458872887482010-09-15T22:47:00.001-07:002010-09-15T22:47:57.304-07:00Tamacola (4)<h4>Tamacola in Tamacola</h4>
<p>After I made the Tamacola compiler written in COLA, next thing to do
was to implement it in Tamacola itself. A language is called
self-hosting if the language is written in the language itself. This
implies various advantage.</p>
<p>First, once self-hosting is done, you don't need to use COLA anymore,
you can improve or modify any language aspects on Tamarin VM. If I
carefully design the environment, it would be possible to do language
design only on the Web browser (it needs server side help for security
reason, so it hasn't done yet).</p>
<p>Second, self hosting is a benchmark for the language to tell that it
is good enough. Scheme is especially simple language, so there are a
lot of people who implement toy-Scheme. But because my Tamacola is now
self-hosting, I could proudly claim that this is not a toy! Well, this
is rather self satisfaction, though.</p>
<p>Third, it provides a rich library including "eval" function. A
compiler uses various programming techniques, and those must be useful
for other programs, too.</p>
<p>To make it self-hosting, there were two key problem which are macros
and eval.</p>
<h4>Bootstrapping Macros</h4>
<p>I heavily used macros in my compiler, for example, the parser written
in PEG was converted a bunch of macro expressions. The problem is,
expanding macros requires eval function but I wasn't able to make eval
before the parser was done. It's a deadlock! Here is a typical macro
written in COLA:</p>
<pre>
(define-form begin e (cons 'let (cons '() e)))
</pre>
This is how the macro works. When the compiler find a expression like:
<pre>
(begin
(print "Hello")
(print "World"))
</pre>
Expressions inside <code>begin</code> is bound to <code>e</code>, the
body <code>(cons 'let (cons '() e))</code> is executed in compile time
and the expression is expanded to:
<pre>
(let ()
(print "Hello")
(print "World"))
</pre>
<p>Such expansion is impossible without eval function because the
compiler need to evaluate a list <code>(cons 'let (cons '() e))</code>
given by user. What I would do when I didn't have eval yet. But I
realized that macros only include basic list functions like car, cdr,
and cons in many cases. And a more complicated macro could be hard
corded as a special form in the compiler. So I invented a pattern base
macros.</p>
<pre>
(define-pattern ((begin . e) (let () . e)))
</pre>
<p>Basically this is a subset of Scheme's syntax-rule. If the compiler
finds an expression starting with <code>begin</code>, rest of the
expression is bound to <code>e</code> and substituted as a right hand
side. Those expansion requires only limited set of list functions, so
the compiler doesn't have to provide full eval function. This macro
syntax made my compiler readable, and I was able to continue happily.</p>
<p>Even after I implemented more dynamic traditional macro with eval
function, I keep using this pattern base macros mainly.</p>
<h4>Eval</h4>
<p>To implement eval function, you need to understand the dynamic code
loading facility provided by the VM. Note that this is not part of
AVM2 specification, and Avmshell (a console Tamarin shell program) and
Adobe Flash have different API.</p>
<p>Avmshell has straightforward API. You give compiled byte code, and the
function returns the value. Because Tamacola is now written in
Tamacola, you can invoke the compiler as a library function and get
byte code you want to execute.</p>
<pre>
avmplus.Domain.loadBytes(byteArray:ByteArray)
</pre>
<p>You can get the domain object by Domain.currentDomain() static method.
Those useful functions in Avmshell are found <code>shell/</code>
directory in the Tamarin-central repository.</p>
<p>Flash Player has somewhat tricky API for dynamic code loading. The
signature is normal.</p>
<pre>
flash.display.Loader.loadBytes(bytes:ByteArray, context:LoaderContext = null):void
</pre>
<p>There are two problems for our purpose. First, this method is not
designed mainly for dynamic loading, it only accepts SWF, JPG, PNG, or
GIF files, and byte code happen to be accepted inside a SWF file. So I
had to construct SWF file to load code. In case if you don't know
about SWF file, SWF file is a kind of container format. You can
embedded vector graphics, mp3 sounds, and ActionScript byte
code. Making a SWF file is not particularly difficult though, it needs
nasty bit fiddling.</p>
<p>Second, this is far more problematic, is that this method works as
asynchronously. In other words, this doesn't return the result
value. Instead, you need to give it a callback function to wait to
finish the code. Additionally, this method doesn't return value at
all, so if you want the return value, you need to setup some explicit
return mechanism by yourself.</p>
<p>Practically, this cause a problem if you want to write a traditional
macro definition and use the macro in a same source code. Because a
traditional macro need to evaluate a lisp expression in a compile
time, but the eval function doesn't return before the compilation
thread is done. I could solve the problem by setting up compilation
queue or something, but it would cost performance penalty which I
don't want. And now I simply gave up.</p>
<p>I have explained pretty much all interesting aspect of the self
hosting compiler. I'll talk about how to make a new language on the
Tamacola environment later.</p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-62548099666840792772010-09-14T23:03:00.000-07:002010-09-14T23:04:07.286-07:00Tamacola (3)<h4>How a lisp program is compiled to Tamarin VM</h4>
<p>Now I'm going to talk a bit about how a lisp (almost Scheme) program
is compiled into Tamarin's byte code. This topic is especially
interesting if you are curious to make your own language or VM.</p>
<p>Tamarin VM is made for ActionScript, so its byte code is also
specifically designed for ActionScript. In other words, it is a
slightly tricky to implement other language than ActionScript. In
case if you don't know about ActionScript, it is almost identical as
JavaScript in the execution model. Difference between them is about
optimization with explicit type notion and static field.</p>
<p>ActionScript and Scheme are common for those aspects:</p>
<ul>
<li>Lexical scope.</li>
<li>Function object.</li>
<li>Variable arguments with no curring.</li>
<li>Dynamic typing (a value has type, not variable).</li>
</ul>
<p>But there are significant difference.</p>
<ul>
<li>ActionScript doesn't have a simple function call. Everything is a method call.</li>
<li>In ActionScript, a function has a scope. No scope block or let expression.</li>
<li>Tail call optimization is not supported.</li>
<li>Call stack can not be accessed.</li>
</ul>
<p>Those limitations sound like that Tamarin VM is inferior. But no,
actually those limitations come from Tamarin VM's advantage and
optimization. If you happen to have a chance to design your VM, please
learn from the lesson. There ain't no such thing as a free
optimization. Any optimization kills some generality. I'll explain each
case.</p>
<p>ActionScript doesn't have a simple function call neither Tamarin
VM. This is rather harmless though. When you see a function like
expression like <code>trace("hello")</code>, this is actually mean
<code>(the global object).trace("hello")</code>, and eventually, the
receiver passes to the function as the first argument. In other words,
if you want to construct a function call with two arguments, you need
to make three arguments where the first argument is "this" object. A
slightly tricky part is primitive operators like + or -, which don't
have "this" object. Those primitives are special case.</p>
<p>ActionScript also has lexical scope, but only a function has a
scope. So I have to be careful when I compile let expression in
Scheme. Most simplest way to implement a let expression is to use a
function. A let expression can be always translated to a lambda in
theory though, this is a huge performance disadvantage. So I use
"with" expression in ActionScript. "With" expression is an unpopular
syntax in ActionScript, but you can use any object as a scope
object. I borrowed this idea from Happy-ABC project <a
href="http://github.com/mzp/scheme-abc">http://github.com/mzp/scheme-abc</a>.</p>
<p>Lack of the tail call optimization in Tamarin VM was the most
disappointed thing to me. It prevents a functional programming
style. I simply gave up it. Tail call optimization is not difficult
topic at all. If the target were a native code like x86, it would be a
matter of swapping stack and jump. But Tamarin VM doesn't allow direct
access of stack or jump to other function. I understand that it might
cause a security issue though, it would be wonderful if VM would provide
special byte code for tail call.</p>
<p>Finally, you can't access the call stack directly, therefore you can't
implement call/cc. The reason why I can't call Tamacola as Scheme is
the lack of tail call optimization and call/cc. It prevents many
experimental language features like generator, process, or so. But
considering rich libraries provided by the Flash API, I would say
Tamacola will be a reasonably useful language eventually.</p>
<p>I'll tell you convolved self hosting process and macros tomorrow.</p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-85062530643886106822010-09-14T09:43:00.001-07:002010-09-14T09:43:37.003-07:00Tamacola (2)<h4>COLA</h4>
<p>Once the assembler was done, I was able to test verious Tamarin VM's
features, even I wrote a tiny GUI application on Adobe Flash in the
assembler. Then next step is the compiler.</p>
<p>Another goal of the project was to port Ian Piumarta's COLA framework
to Tamarin (the project name came from this). And perhaps this is only
the real technical contribution of the project. COLA is a meta
language (a programming language to design another language) which
resembles Scheme. COLA has a nice sub-language called Parser
Expression Grammar that makes parser very terse. My plan was to write
a boot-strappng compiler in PEG and COLA, then to implement COLA
library, and to write the real compiler in PEG and Tamacola itself.</p>
<p>I won't give you the detail of PEG. But briefly, it is as simple as a
regular expression and as powerful as a context free grammar.</p>
<p>When that time I started writing the compiler, COLA has no library at
all except PEG framework, so I needed to write necessary libraries by
myself from scratch. Fortunately COLA has quite a powerful external
function call feature (a kind of FFI), macro sysytem, and a flexible
object oriented framework. So writing library is not so hard. But I
tried not to use COLA specific features as possible because it would
be a problem when I rewrite the compiler in Tamacola itself later.</p>
<p>To implement the library, I borrowed function specifications from R6RS
as well as possible to avoid unnecessary confusion. There were
exception because COLA treat a slash "/" character as special for
namespaces, I took PLT's function names in this case.</p>
<p>Writing lisp libraries is interesting puzzle to me because there were
some requirements and constrain for the domain. Those requiments are:</p>
<ul>
<li>Unit testing framework.</li>
<li>Library framework.</li>
<li>List manipulations.</li>
<li>String functions.</li>
<li>Bit operations and streams.</li>
<li>Pretty printer for debugging.</li>
</ul>
<p>These requirements were carefully chosen. Because COLA has only modest
debugging facility, the unit test framework must be there. So my first
goal was to implement all functions needed by the unit testing. I
needed a pretty printer for debugging, too.</p>
<p>Another "must have" library was bit operators, and file / in-memory
streams that is needed to the assembler. Interestingly enough, R6RS
doesn't define enough functions to support those. For example, there
are no portable way to specify a stream to be binary or text. So I
needed a bit creativity.</p>
<p>Eventually, I wrote all libraries and the compiler. And I got a pretty
good sense about a minimun set of functions needed for compiler, which
are testing framework, pretty printer, bit operators, and streams. In
other words, if your language has those features, your language can be
self-hosting.</p>
<p>The real puzzle part was the order. Those requirements must be
precisely ordered by need. For example, the pretty printer must follow
stream and string functions because the pretty printer uses those
functions. Although you can write functions in random order as you
like in Lisp, precise order makes testing and debugging is easy. I
kept this discipline. I even implemented the test library twice, the
first one was concise assert function, and the second one has more
friendly fail message by the pretty printer.</p>
<p>It took a few weeks to build a simple compiler, but still there were
long way up to the point where self-hosting can be done. One thing
that I had learned from the stage was, even without debugger,
debugging is not so hard if you have enough test cases and a good
pretty printer.</p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-27697069914561417592010-09-12T16:40:00.000-07:002010-09-24T00:51:00.432-07:00Tamacola (1)<h4>Table of Contents</h4>
<ul>
<li><a href="http://propella.blogspot.com/2010/09/tamacola-1.html">Intro, How I started the assembler</a></li>
<li><a href="http://propella.blogspot.com/2010/09/tamacola-2.html">COLA</a></li>
<li><a href="http://propella.blogspot.com/2010/09/tamacola-3.html">How a lisp program is compiled to Tamarin VM</a></li>
<li><a href="http://propella.blogspot.com/2010/09/tamacola-4.html">Tamacola in Tamacola, Bootstrapping Macros, Eval</a></li>
<li><a href="http://propella.blogspot.com/2010/09/tamacola-5-tamacola-is-not-just-another.html">How to make your own compiler</a></li>
</ul>
<h4>Intro</h4>
<p>I have published the source code of Tamacola, a lisp compiler which
runs on Adobe Flash / Tamarin VM (or Adobe Virtual Machine 2) <a
href="http://github.com/propella/tamacola">http://github.com/propella/tamacola</a>. I'm
pretty sure that the current version is useless if you are just
looking for a lisp implementation on Tamarin (las3r and scheme-abc are
much better), but Tamacola includes abundant tips if you are
interested in making a self-hosting compiler on Tamarin VM. That's why
I decided to publish it as-is.</p>
<p>I'm also working on a presentation slide for S3 conference
<a href="http://www.hpi.uni-potsdam.de/hirschfeld/s3/s3-10/">http://www.hpi.uni-potsdam.de/hirschfeld/s3/s3-10/</a> to show it. I'm writing
random thoughts about the compiler here so that I will compile them to
a thread of talk.</p>
<p>I've already written the motivation on the paper (perhaps I will paste
the URL in a month) so I don't repeat it. But in short, I wanted make
a tiny language which bootstraps and runs on Adobe Flash.</p>
<p>A tiny language and bootstrapping seem contradicting idea as
bootstrapping requires various language functions which tends to be
large. On the other hand, this is practically a nice constrain because
it keeps the language from too simple or too fat. Choosing Scheme like
language as a target is natural to me because I wanted to concentrate
basic implementation technique instead of language design.</p>
<p>Well, as one reviewer of the paper said, this is not particularly
surprising or dramatically different in comparison with previous
systems in the area, but some of the stories from the compiler should
interest you!</p>
<h4>How I started the assembler</h4>
<p>In the beginning I created the assembler. Honestly, I wanted to avoid
the task because writing assembler seemed not quite an interesting
job. But in that time, I couldn't find a nice AVM2 assembler that
suite my project. So I've done it. In retrospect, this was not bad at
all. I could understand what avm2overview.pdf (the AVM2 specification)
said quite well, and I got self confidence.</p>
<p>I wrote my assembler in PLT-Scheme because Ian Piumarta's COLA
(Tamacola was supposed to be written in COLA and Tamacola itself, I'll
tell you this later) is not finished yet in that time and Duncan Mak,
a friend of mine, recommend it. This was actually a good choice. This
is my first Scheme application and PLT's good documentation helped me
a lot.</p>
<p>An interesting part of PLT-Scheme was it encourages a functional
programming style, even PLT doesn't suppport set-car! and set-cdr! in
the default library. So it was natural that my assembler was written
without side-effect except I/O. This is the first key of the
development of the assembler. Unfortunately, because Tamarin doesn't
support tail-recursion optimazion and Tamarin's stack size is small, I
gave up to eliminate all side-effect later. But the implementation was
pure functional up to the time, and it was quite clean.</p>
<p>Indeed, it had to be clean considering boot-strapping. I wanted to
make the assembler run in my language itself even before enough
debugging facility is not ready. If it were not clean, a tiny bug
would cause a few days of debugging. I avoided the nightmare with a
functional style and Test Driven Development.</p>
<p>Test Driven Development is the second key. I virtually wrote every
test case for each function even if it looks silly. Scheme has a
couple of options of testing frame work. I chose SRFI-78. It only
report assertion failer only something happen, otherwise it keeps
silence. I somewhat like this UNIX taste terse.</p>
<p>The third key was to write an assembler and a disassembler in a same
time. It sounds like an unnecessary job because I only needed an
assembler eventually. But I had to analyze an output from asc (an
asembler in Adobe Flex) and learn how an ActionScript program was
converted to the Tamarin byte-code. The disassembler was very helpful
to read the byte-code as well as debugging. If output of the
disassembler generates the original byte-code by the assembler, there
is high chance that my imprementation is correct, unless my
understanding is wrong.</p>
<p>The assembler is named ABCSX <a
href="http://github.com/propella/abcsx">http://github.com/propella/abcsx</a>
and it was ported to Gauche, COLA, and Tamacola later. I ported it to
Gauche because I was curious about portability of Scheme language.</p>
<p>I had realized there are many places where I could reduce code
redundancy in the assembler. An assembler tends to include repetitive
process, but some of them are not quite captured well by function
abstraction. I would be effective to apply macro and domain specific
language in those part. I didn't have tried to solve it yet, but I
want to solve it later.</p>
<p>(to be continued)</p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-60526165516722641602010-01-29T12:30:00.000-08:002010-01-29T13:58:05.064-08:00Recent Tamarin and ABC toolsTamarin-central, the stable source tree of open source VM used by
Adobe Flash, <a
href="https://mail.mozilla.org/pipermail/tamarin-devel/2009-December/001335.html">was
updated last December</a> (Dec 22 2009) after relatively long
blank. The newer tree has faster VM and includes updated ABC
assembler and disassembler. Especially those ABC utilities are quite
useful to a binary hacker of AVM2.
<h4>Download latest Flex SDK</h4>
I found that neither Flex SDK 3.5 nor 4.0 stable build can compile
abcdump. You need to download later version from the <a
href="http://opensource.adobe.com/wiki/display/flexsdk/Download+Flex+4">Download
Flex site</a>. Flex 4-Beta 2 (4.0.0.10485) works well. I would set the
Flex directory to environment variable FLEX.
<pre>
$ export FLEX=~/Downloads/flex_sdk_4.0.0.10485_mpl
</pre>
<h4>Download and build Tamarin-central</h4>
Building procedure is well documented in <a
href="https://developer.mozilla.org/En/Tamarin_Build_Documentation">Tamarin_Build_Documentation</a>. Only
my additional suggestion is to add --enable-debugger, it makes error
messages easy to read, it helps you, really.
<pre>
$ hg clone http://hg.mozilla.org/tamarin-central/
$ cd tamarin-central
$ mkdir objdir-release
$ cd objdir-release
$ python ../configure.py --enable-shell --enable-debugger
$ make
$ ./shell/avmshell -Dversion
shell 1.5 release-debugger build cyclone
features AVMSYSTEM_32BIT; ...
</pre>
<h4>Build abcdump</h4>
There are various useful utilities in utils/ directory. Some utilizes
are written in ActionScript, so you need to compile them to
use. Abcdump, ABC disassembler, is one of such utilities.
<pre>
$ cd ..
$ java -jar $FLEX/lib/asc.jar -import core/builtin.abc -import shell/shell_toplevel.abc utils/abcdump.as
</pre>
core/builtin.abc and shell/shell_toplevel.abc are basic libraries
provided by tamarin, you can use them to try to see how abcdump
works. Note that you need to separate abc file names with --,
otherwise arguments are processed by avmshell instead of abcdump.
<pre>
$ ./objdir-release/shell/avmshell ./utils/abcdump.abc -- core/builtin.abc
// magic 2e0010
// Cpool numbers size 158 0 %
...
</pre>
I recommend you to make a tiny shell script to ease such a complicated command line.
<pre>
#!/bin/sh
~/tmp/tamarin-central/objdir-release/shell/avmshell ~/tmp/tamarin-central/utils/abcdump.abc -- $@
</pre>
<h4>How to use abcasm</h4>
Abcasm is a ABC assembler. It is written in java and shell script, so
you don't need to compile to try it. utils/abcasm/test/ directory
includes various interesting sample programs. You can test them easily
and quickly.
<pre>
$ cd utils/abcasm/
$ ./abcasm.sh test/hello.abs
test/hello.abs
$ ../../objdir-release/shell/avmshell test/hello.abc
Hello, world
</pre>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com3tag:blogger.com,1999:blog-8272979.post-57191128573698038562009-12-18T06:12:00.000-08:002010-01-24T17:19:35.730-08:00Wooden Half Adder Video<object width="425" height="344"><param name="movie" value="http://www.youtube.com/v/WOdN-d-JogQ&hl=en_US&fs=1&"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/WOdN-d-JogQ&hl=en_US&fs=1&" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="425" height="344"></embed></object>
<p>
*UPDATED* New half adder video is released!
</p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com1tag:blogger.com,1999:blog-8272979.post-54285910357152981712009-11-28T22:30:00.000-08:002009-11-28T22:36:48.991-08:00A group exhibition "First Passage"I'm going to Osaka in the chiristmas season to join the exhibition. This is a kind of "college reunion show" and all of artists were students of Prof. Hitoshi Nomura. I'm very excited to see old friends of the sculpture course. Now I'm quite busy to build a new version of wooden half adder. This is my first exhibition since 1999 anyway. Time is running so fast.
<h4><a href="http://www.artcourtgallery.com/e/ex/upcoming.html">First Passage</a></h4>
<p>ARTCOURT Gallery <a href="http://maps.google.com/maps?f=q&source=s_q&hl=en&geocode=&q=ARTCOURT+Gallery+Tenmabashi+1-8-5,+Kita-ku,+Osaka+530-0042+Japan&sll=34.702054,135.518975&sspn=0.011131,0.013926&ie=UTF8&hq=ARTCOURT+Gallery+Tenmabashi+1-8-5,&hnear=〒530-0042&ll=34.702054,135.518825&spn=0.011131,0.013926&z=16">Tenmabashi 1-8-5, Kita-ku, Osaka 530-0042 Japan</a></p>
<p>
Hitoshi Nomura, Koji Nishimatsu, Kawai+Okamura, Osamu Kokufu, Tamaki Nagatani,
Takashi Yamamiya, Yui Ishiyama, Kohei Nawa, Yasutaka Yamada, Yoshihiko Maeda,
Ichiro Okada, Takao Machiba, Kenta Ogaya, Takayuki Okamoto, SHINCHIKA,
Yasuyoshi Uchiyama and Taro Okumura
</p>
<ul>
<li>December 15 - 26, 2009</li>
<li>Gallery Hours: 11:00 - 19:00 ( - 17:00 on Saturdays) Closed on Sundays</li>
</ul>
<ul>
<li>Event : Artists Talk Show</li>
<li>Saturday, Dec.19, 14:00 - 15:30 (*15:30 - 17:00 Reception)</li>
</ul>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com3tag:blogger.com,1999:blog-8272979.post-68229163344829710252009-11-05T22:21:00.000-08:002009-11-05T22:44:57.781-08:00Wooden half adder<p><a href="http://www.flickr.com/photos/propella/4075677552/"
title="P1060931 by propella, on Flickr"><img src=
"http://farm3.static.flickr.com/2487/4075677552_0be04e0c14.jpg"
width="500" height="375" alt="P1060931" /></a></p>
<p>Since I encountered an essay by A. K. Dewdney over ten years ago,
somewhat I had been obsessed about mechanical implementation of
boolean logic. The essay introduced ideas of kinetic binary
calculator as an imaginary story of ancient civilization. This
fantastic tale attracted me, and my theme at the art college became
how to make a computer made from wood.</p>
<p>Last year, my boss gave me a Dewdney's book "The Tinkertoy
Computer and Other Machinations", which includes the essay, and my
enthusiasm came back. I made a couple of prototypes to realize
boolean logic without electronics. This is the latest attempt.</p>
<p>I chose a half adder as the motive because half adders are used
everywhere in a computer hardware, and it seems nice complexity for
the project. I thought this is the best example to show the idea
that computer's concept is independent with hardware. In other
words, I wanted to prove that computer is purely conceptual entity
and you can make it from any material besides electronics parts.</p>
<table>
<tr>
<td><a href="http://www.flickr.com/photos/propella/4079121563/"
title="P1070004 by propella, on Flickr"><img src=
"http://farm3.static.flickr.com/2571/4079121563_0518beffba_m.jpg"
width="240" height="180" alt="P1070004" /></a></td>
<td><a href="http://www.flickr.com/photos/propella/4079880288/"
title="P1070009 by propella, on Flickr"><img src=
"http://farm3.static.flickr.com/2658/4079880288_93d15391c0_m.jpg"
width="240" height="180" alt="P1070009" /></a></td>
</tr>
</table>
<p>I first built a wooden AND operator. Can you tell how this toy
work? The top two holes show the input, and the center hole shows
the answer. Background board shows two kind of state T (True) and F
(False). Because of gravity, initial state is T AND T = T, once you
pull one of bars up, the center piece is also pulled up, and the
answer becomes F. This is how AND works.</p>
<p>Basically, any boolean logic can be possible with AND, and
another operator NOT (even OR can be constructed from AND and NOT).
Let's think about a half adder. A half adder is a primitive adder
and you can only add two bits. There are only four positions.</p>
<ul>
<li>0 + 0 = 0 0</li>
<li>0 + 1 = 0 1</li>
<li>1 + 0 = 0 1</li>
<li>1 + 1 = 1 0</li>
</ul>
<p>Let the inputs A and B, and the outputs S (sum, the low bit) and
C (carry, the high bit). A half adder can be shown two boolean
equations from AND(∧) and NOT(¬).</p><a href=
"http://www.flickr.com/photos/propella/4079918064/" title=
"halfAdderDiagram by propella, on Flickr"><img src=
"http://farm3.static.flickr.com/2715/4079918064_b4fa0f38dd_o.png"
width="140" height="303" alt="halfAdderDiagram" /></a>
<ul>
<li>C = A ∧ B</li>
<li>S = A xor B = ¬(A ∧ B) ∧ ¬(¬ A ∧
¬B)</li>
</ul>
<p>Finally, I constructed parts along with this formula. I used
gears as NOT operator.</p>
<table>
<tr>
<td><a href="http://www.flickr.com/photos/propella/4075676754/"
title="P1060912 by propella, on Flickr"><img src=
"http://farm3.static.flickr.com/2732/4075676754_11b43f8176_m.jpg"
width="240" height="180" alt="P1060912" /></a></td>
<td><a href="http://www.flickr.com/photos/propella/4075675984/"
title="P1060908 by propella, on Flickr"><img src=
"http://farm3.static.flickr.com/2647/4075675984_a2ffb5c677_m.jpg"
width="240" height="180" alt="P1060908" /></a></td>
<td><a href="http://www.flickr.com/photos/propella/4075675256/"
title="P1060900 by propella, on Flickr"><img src=
"http://farm3.static.flickr.com/2771/4075675256_c99dacda86_m.jpg"
width="240" height="180" alt="P1060900" /></a></td>
<td><a href="http://www.flickr.com/photos/propella/4074919483/"
title="P1060894 by propella, on Flickr"><img src=
"http://farm3.static.flickr.com/2430/4074919483_250c28e51f_m.jpg"
width="240" height="180" alt="P1060894" /></a></td>
</tr>
<tr>
<td>1 + 1 = 1 0</td>
<td>1 + 0 = 0 1</td>
<td>0 + 1 = 0 1</td>
<td>0 + 0 = 0 0</td>
</tr>
</table>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com6tag:blogger.com,1999:blog-8272979.post-58570625649512963242009-10-04T23:28:00.000-07:002009-10-04T23:30:32.905-07:00An Assembler for AVM2 using S-ExpressionThese days, I have been writing a documentation about my latest AVM2
assembler. Because it took very long time, I tempted to copy it here
to make my blog seem substantial.
<h4>Overview</h4>
<p>ABCSX is an assembler and disassembler for the ActionScript
Virtual Machine 2 (AVM2) <a href="#AVM2">[1]</a> and the
ActionScript Byte Code (ABC). It runs on Cola/Amino language or
PLT-Scheme. The syntax consists of s-expressions and a program
can be constructed with normal list operations in Scheme like
language. The goal of this utility is to build a high level
language compiler for Adobe Flash Player. To get the idea, "Hello
World!" programs for both ABCSX and abcasm (a standard assembler
utility consisted in the AVM2 source tree <a href=
"#tamarin">[4]</a>) are shown.</p>
<pre>
;;;; A "Hello World!" program in ABCSX ASM-form
(asm
(method
(((signature
((return_type *) (param_type ()) (name "hello")
(flags 0) (options ()) (param_names ())))
(code
((getlocal 0)
(pushscope)
(findpropstrict ((package "") "print"))
(pushstring "Hello, World!!")
(callproperty ((package "") "print") 1)
(returnvoid))))))
(script (((init (method 0)) (trait ())))))
</pre>
<pre>
// A "Hello world World!" program in abcasm
function hello():*
{
getlocal 0
pushscope
findpropstrict print
pushstring "Hello, World!!"
callproperty print (1)
returnvoid
}
</pre>
<p>Although a program written in abcasm syntax is more concise
than ABCSX, the semantics is rather ambiguous. For example, in
spite of each symbol name in ABC belongs to namespace(s), the
syntax of abcasm doesn't describe it clearly. In this case,
"print" is implicitly interpreted to a Multiple Namespace Name
with a namespace set including PackageNamespace with no name. In
case of ABCSX, it is explicitly represented as PackageNamespace
with no name by <tt>((package "") "print")</tt>. This implicit
behavior might be useful for writing a program by hand, but not
necessary for a machine generated code. ABCSX rather takes a
direction toward verbose but unambiguous style.</p>
<p>ABCSX offers two forms of syntax. ASM-form is higher level
syntax introduced above. ABC-form is identical to an abstract
syntax tree of ABC binary file. This is useful when exact
behavior is need to know while debug.</p>
<pre>
;;;; A "Hello World!" program in ABCSX ABC-form
(abc
(minor_version 16)
(major_version 46)
(constant_pool
((integer ())
(uinteger ())
(double ())
(string ("hello" "" "print" "Hello, World!!"))
(namespace ((package (string 2))))
(ns_set ())
(multiname (((namespace 1) (string 3))))))
(method (((return_type (multiname 0)) (param_type ())
(name (string 1)) (flags 0) (options ()) (param_names ()))))
(metadata ())
(instance ())
(class ())
(script (((init (method 0)) (trait ()))))
(method_body
(((method 0) (max_stack 2) (local_count 1)
(init_scope_depth 0) (max_scope_depth 1)
(code
((getlocal 0)
(pushscope)
(findpropstrict (multiname 1))
(pushstring (string 4))
(callproperty (multiname 1) 1)
(returnvoid)))
(exception ())
(trait ())))))
</pre>
<p>Using ASM-form, a compiler writer doesn't have to care about
building a constant pool, or code hint information (AVM2 requires
a frame information like stack size and register size used in a
code).</p>
<h4>Background</h4>
<p>One of goals of the STEPS project <a href="#STEPS">[3]</a> and
COLA programming language is to provide full control of computer
environment from application level to machine language level, so
that users could experiment and design their own programming
language best fit to their task. It also will be used as a basis
of next generation of EToys programming environment for kids.</p>
<p>We chose Adobe Flash Player as one of platforms of the system
because of its popularity and usability. Using Flash's virtual
machine on a web browser, we could deliver our programming
environment without concerning about installation or security
issue.</p>
<p>AVM2 has some disadvantages compared to Java VM. AVM2 lacks
multi task support, and its dynamic dispatching function is
relatively slow. But the startup speed and memory footage are
good, and these aspects are essential to casual users. Especially
AVM2 will be good platform to implement EToys.</p>
<p>ABCSX is designed to be a back end module for COLA, command
line assembler / disassembler, and a Scheme library. While it is
a part of COLA/ABC compiler, it also can be used as a command
line tool to examine and debug ABC binary file.</p>
<h4>Usage</h4>
<h5>Command line tool</h5>
<p>A version of ABCSX is publicly available on the github
repository <a href="#ABCSX">[2]</a>. It includes command line
tools run on PLT-Scheme. There are also example programs at
<tt>examples/</tt> directory. The assembler and disassembler use
same file format and the assembler <tt>asm.ss</tt> can read an
output file generated by disassembler <tt>dump.ss</tt>.</p>
<dl>
<dt class="code">asm.ss <i>filename.sx</i></dt>
<dd>Generate an ABC binary file from ASM-form or ABC-form. The
output file name is filename.sx.abc.</dd>
<dt class="code">dump.ss [-abc] <i>filename.abc</i></dt>
<dd>Disassemble an ABC binary file. The output is printed to
stdout. If <tt>-abc</tt> option is specified, ABC-form is
chosen as output format.</dd>
<dt class="code">runasm.sh <i>filename.sx</i></dt>
<dd>Assemble ASM-form or ABC-form and execute it by avmshell.
It requires avmshell installed. Avmshell is included in Tamarin
VM's source tree <a href="#tamarin">[4]</a>.</dd>
<dt class="code">swf_abc.erl <i>width height classname
abcfile.abc</i></dt>
<dd>A helper program to generate a flash file from an abc file.
It requires Erlang.</dd>
</dl>
<h5>Function</h5>
<dl>
<dt><span class="code">(write-asm <i>list</i>
<i>port</i>)</span> procedure</dt>
<dd>Assemble ASM- or ABC-form to a binary stream.</dd>
<dt><span class="code">(read-asm <i>port</i>)</span>
procedure</dt>
<dd>Disassemble a binary stream to ASM-form.</dd>
<dt><span class="code">(from-asm <i>list</i>)</span>
procedure</dt>
<dd>Convert ASM-form to ABC-form. This is a part of process of
assemble. Each literal value is replaced to a reference, and a
constant pool is created</dd>
<dt><span class="code">(to-asm <i>list</i>)</span>
procedure</dt>
<dd>Convert ABC-form to ASM-form. This is a part of process of
disassemble. Each constant reference in the ABC-form is
replaced to a literal value based on the constant pool.</dd>
</dl>
<h4>Data Type</h4>
<p>ABC's data is expressed as scheme expression in ABCSX. In
ASM-form, data conversion has subtle context dependency in
code-subsection.</p>
<ul>
<li>integer - An integer value in Scheme is converted to ABC
integer value depend on the context.
<ul>
<li>int (s32) - In code-subsection, an integer is converted
to a signed 32 bit integer if the opcode requires integer
e.g. <tt>pushint</tt>.</li>
<li>uint (u32) - In code-subsection, an integer is
converted to a unsigned 32 bit integer if the opcode
requires integer e.g. <tt>pushuint</tt>.</li>
<li>u30 - An integer is converted to a unsigned 30 bit
integer in ABC anywhere else.</li>
</ul>
</li>
<li>double (d64) - A floating point number value is converted
to a 64-bit double precision IEEE 754 value.</li>
<li>string - A string is converted a string value in ABC.</li>
<li>namespace - Some list expressions are converted to
namespace values in ABC. The format is (<i>kind</i>
<i>string</i>). For example, <span class="code">(package
"org.vpri")</span> is converted to a package namespace named
<tt>"org.vpri"</tt>.
<ul>
<li>Namespace - <tt>(ns <i>string</i>)</tt> is converted to
Namespace</li>
<li>PackageNamespace - <tt>(package <i>string</i>)</tt> is
converted to PackageNamespace</li>
<li>PackageInternalNs - <tt>(internal <i>string</i>)</tt>
is converted to PackageInternalNs</li>
<li>ProtectedNamespace - <tt>(protected <i>string</i>)</tt>
is converted to ProtectedNamespace</li>
<li>ExplicitNamespace - <tt>(explicit <i>string</i>)</tt>
is converted to ExplicitNamespace</li>
<li>StaticProtectedNs - <tt>(static <i>string</i>)</tt> is
converted to StaticProtectedNs</li>
<li>PrivateNs - <tt>(private <i>string</i>)</tt> is
converted to PrivateNs</li>
</ul>
</li>
<li>namespace set - A namespace set can not be described as a
literal. Instead, it is declared in a constant pool of
ns_set-section at first, and be made reference by index e.g.
<span class="code">(ns_set 1)</span>.</li>
<li>multiname - Some list expressions are converted to
multiname (symbol) in ABC.
<ul>
<li>QName - <tt>(<i>namespace</i> <i>string</i>)</tt> is
converted as QName e.g. <span class="code">((package
"flash.display") "Sprite"))</span></li>
<li>RTQName - is not supported.</li>
<li>RTQNameL - is not supported.</li>
<li>Multiname - <tt>((ns_set <i>integer</i>)
<i>string</i>)</tt> is converted as a Multiname e.g.
<span class="code">((ns_set 1) "addChild")</span></li>
<li>MultinameL - is not supported.</li>
</ul>
</li>
</ul>
<h4>Syntax</h4>The syntax of ASM-form is explained. ABCSX uses
same symbol names as "ActionScript Virtual Machine 2 (AVM2)
Overview" unless it is too strange. Especially, underline
delimited names and capital names are derived from the document.
<h5>ASM-form</h5>
<p><tt>(asm <i>[ns_set-section]</i> <i>method-section</i>
<i>[metadata-section]</i> <i>[instance-section]</i>
<i>[class-section]</i> <i>script-section)</i></tt></p>
<p>ASM-form begins with a symbol <tt>asm</tt>, and contents are
followed. ns_set-section, instance-section, and class-section are
optional.</p>
<h5>ns_set-section</h5>
<p><tt>(ns_set (ns_set <i>namespace ...</i>) ...)</tt></p>
<p>Ns_set-section will be a part of constant pool, and it is only
necessary if namespace set is used in other part of the ASM-form.
You can not specify a namespace set directly as a literal, but
you need to define it in ns_set-section and point it with the
index number.</p>
<p>Ns_set-section begins with a symbol <tt>ns_set</tt> and a list
of ns_set_info is followed. A ns_set_info begins with a symbol
<tt>ns_set</tt> and it includes a list of namespaces. A namespace
set is referred with one-based index by other part. For example,
the first namespace set is referred as <tt>(ns_set 1)</tt>.</p>
<h5>method-section</h5>
<p><tt>(method (<i>signature-subsection code-subsection</i>)
...)</tt></p>
<p>Method-section includes a list of pairs of signature and code.
A method is referred by zero-based index. For example, the first
method is referred as <tt>(method 0)</tt>.</p>
<h6>signature-subsection</h6>
<p><tt>(signature (return_type <i>multiname</i>) (param_type
(<i>multiname</i> ...)) (name <i>string</i>) (flags
<i>integer</i>) (options (<i>option</i>...)) (param_names
(<i>multiname</i> ...)))</tt></p>
<p>Signature-subsection describes method's signature. If * is
specified at the return_type. It is treated as Any Type. A name
entry is not used as a method name in a program. In a typical
case, methods are explicitly bound to named slots in
initialization code at script-section or object constructor.</p>
<h6>code-subsection</h6>
<p><tt>(code (<i>instructions</i>...))</tt></p>
<p>Code subsection describes a sequence of instruction code of
the method. A label is specified as a symbol, and normal
instruction is specified as a list as:</p>
<p><tt>([<i>offset-number</i>] <i>inst-name args</i>
...)</tt></p>
<p>offset-number is optional and used just as a place holder. It
can be a integer or symbol <tt>_</tt>. ABCSX's disassembler put a
byte offset number at this place, but the assembler ignores
it.</p>
<h5>metadata-section</h5>
<p><tt>(metadata (<i>metadata_info</i> ...))</tt></p>
<p>Metadata-section describes a list of metadata entries.</p>
<h5>instance-section</h5>
<p><tt>(instance (((name <i>multiname</i>) (super_name
<i>multiname</i>) (flags <i>integer</i>) (interface
(<i>multiname</i> ...)) (iinit <i>method</i>) (trait
(<i>trait_info</i> ...)) ...)))</tt></p>
<p>Instance-section describes a list of class definitions. Class
members are defined by a list of trait_info.</p>
<h5>class-section</h5>
<p><tt>(class (((cinit <i>method</i>) (trait
(<i>trait_info</i>...))) ...))</tt></p>
<p>Class-section describes a list of static members of class
definition. The number of this list is same as instance-section,
and each entry of class-section corresponds to instance-section.
A definition consists of a class initializer and trait_info
definitions.</p>
<h5>script-section</h5>
<p><tt>(script (((init <i>method</i>) (trait
(<i>trait_info</i>...))) ...))</tt></p>
<p>Script-section defines a list of static functions. It is also
used as a program's startup code. Once the virtual machine reads
a program, the last entry of script-section is invoked. Each
entry consists of a method reference and a list of trait_info.
Trait_info is used as a function's environment.</p>
<h5>trait_info</h5>
<p>Trait_info defines a fixed property of an object, class, or
method. ABCSX only supports Trait_Slot and Trait_Class.</p>
<h6>Trait_Slot</h6>
<p><tt>((kind slot) (name <i>multiname</i>) (slot_id
<i>integer</i>) (type_name <i>multiname</i>) (vindex
<i>integer</i>) (vkind <i>integer</i>) (metadata
(<i>metadata_info</i>...)))</tt></p>
<p>Trait_Slot defines a named slot in the context.</p>
<h6>Trait_Class</h6>
<p><tt>((kind class) (name <i>multiname</i>) (slot_id
<i>integer</i>) (classi <i>class</i>) (metadata
(<i>metadata_info</i>...)))</tt></p>
<p>Trait_Class defines a named slot with a class in the
context.</p>
<h5>metadata_info</h5>
<p><tt>((name <i>string</i>) (items (((key <i>string</i>) (value
<i>string</i>)) ...)))</tt></p>
<p>Metadata_info defines an entry including arbitrary key/value
pairs.</p>
<h4>Current Status</h4>
<p>Currently, only major elements in AVM2 are implemented.</p>
<ul>
<li>All primitive data types are implemented.</li>
<li>75 instructions (about a half of the whole instruction set)
are implemented.</li>
<li>Only QName (Qualified Name) and Multiname (Multiple
Namespace Name) are implemented.</li>
<li>Optional parameters or parameter names are not
implemented.</li>
<li>Trait_Method, Trait_Getter, Trait_Setter, Trait_Function,
or Trait_Const are not implemented.</li>
<li>Exception is not implemented.</li>
</ul><!--
<h4>Releated Work</h4>
- Sassy: http://home.earthlink.net/~krautj/sassy/sassy.html
- format.abc: ActionScript Bytecode in HaXe http://haxe.org/com/libs/format/abc
- scheme-abc: http://github.com/mzp/scheme-abc
-->
<h4>Example</h4>
<p>As a complete example, A GUI version of "Hello World!" program
is shown with commentary. This file is available at
<tt>examples/textField.sx</tt> on the source tree.</p>
<pre>
(asm
(ns_set
((ns_set (package "") (package "flash.text"))))
</pre>An ASM-form begins with a symbol <tt>asm</tt>, and a
ns_set-section follows if necessary. This example declare one
namespace set including package namespaces <tt>""</tt> and
<tt>"flash.text"</tt> as <tt>(ns_set 1)</tt>. Ns_set's index number
starts with 1 because this is a member of constant pool. Other kind
of index number (method, class) starts with 0.
<pre>
(method
(((signature ((return_type *) (param_type ()) (name "")
(flags 0) (options ()) (param_names ())))
(code
((returnvoid))))
</pre>
<p>The first method is referred as <tt>(method 0)</tt>. It is
used as a class initializer in the class-section, but nothing to
do in this case.</p>
<pre>
((signature ((return_type *) (param_type ()) (name "")
(flags 0) (options ()) (param_names ())))
(code
((getlocal_0)
(pushscope)
(getlocal_0)
(constructsuper 0)
(findpropstrict ((ns_set 1) "TextField"))
(constructprop ((package "flash.text") "TextField") 0)
(coerce ((package "flash.text") "TextField"))
(setlocal_1)
(getlocal_1)
(pushstring "Hello, World!")
(setproperty ((package "") "text"))
(findpropstrict ((package "") "addChild"))
(getlocal_1)
(callproperty ((package "") "addChild") 1)
(pop)
(returnvoid))))
</pre>
<p>The second method is later used in the instance-section as
class Hello's constructor. It builds an instance of
<tt>flash.text.TextField</tt> and set "Hello, World!" to the
property named <tt>text</tt>. Finally, the text field is added to
this (Hello) object.</p>
<pre>
((signature ((return_type *) (param_type ()) (name "")
(flags 0) (options ()) (param_names ())))
(code
((getlocal_0)
(pushscope)
(getscopeobject 0)
(findpropstrict ((package "") "Object"))
(getproperty ((package "") "Object"))
(pushscope)
(findpropstrict ((package "flash.display") "Sprite"))
(getproperty ((package "flash.display") "Sprite"))
(pushscope)
(findpropstrict ((package "flash.display") "Sprite"))
(getproperty ((package "flash.display") "Sprite"))
(newclass 0)
(popscope)
(popscope)
(initproperty ((package "") "Hello"))
(returnvoid))))))
</pre>
<p>The third method is used as the startup script. It creates an
environment and initialize a new class defined in
instance-section and class-section by <tt>newclass</tt>
instruction.</p>
<pre>
(instance
(((name ((package "") "Hello"))
(super_name ((package "flash.display") "Sprite"))
(flags 0)
(interface ())
(iinit (method 1))
(trait ()))))
(class (((cinit (method 0)) (trait ()))))
</pre>Instance-section and class section define classes. In this
case, A class named <tt>Hello</tt> is defined as a subclass of <tt>
flash.display.Sprite</tt>. When a SWF file is created from ABC
file, a SymbolClass tag in the SWF creates association between a
class name defined here and the main timeline of the SWF. In
ABCSX tool set, script <tt>swf_abc.erl</tt>'s third argument does
this task.
<pre>
(script
(((init (method 2))
(trait
(((kind class)
(name ((package "") "Hello"))
(slot_id 1)
(classi (class 0))
(metadata ()))))))))
</pre>
<p>Script-section defines the startup script and predefined named
slot.</p>
<h4>References</h4>
<ul>
<li id="AVM2">[1] ActionScript Virtual Machine 2 (AVM2)
Overview. <a href=
"http://www.adobe.com/devnet/actionscript/articles/avm2overview.pdf">
http://www.adobe.com/devnet/actionscript/articles/avm2overview.pdf</a></li>
<li id="ABCSX">[2] ABCSX github repository. <a href=
"http://github.com/propella/abcsx">http://github.com/propella/abcsx</a></li>
<li id="STEPS">[3] Steps Toward the Reinvention of Programming
(First Year Progress Report). <a href=
"http://www.vpri.org/pdf/tr2007008_steps.pdf">http://www.vpri.org/pdf/tr2007008_steps.pdf</a></li>
<li id="tamarin">[4] Tamarin Project <a href=
"http://www.mozilla.org/projects/tamarin/">http://www.mozilla.org/projects/tamarin/</a></li>
</ul>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com1tag:blogger.com,1999:blog-8272979.post-46804210632775702932009-07-19T16:35:00.000-07:002009-07-19T17:00:34.986-07:00A simple boolean logic table generator in Javascript<a href="http://www.flickr.com/photos/propella/3737237456/" title="booltable by propella, on Flickr"><img src="http://farm3.static.flickr.com/2469/3737237456_00b3fa5d6c_o.jpg" width="581" height="354" alt="booltable" /></a>
<p><a href="http://languagegame.org/pub/booltable/booltable.html">http://languagegame.org/pub/booltable/booltable.html</a></p>
<p>
Boolean logic is a basic knowledge for all programmers. The idea is
very simple and straightforward, yet still it often annoys you a
lot. One of the reasons might be that boolean logic is not continuous
behavior, and just a bit of changes makes completely different
result. This is why it is hard to grab whole character of a boolean
expression, I think.
</p>
<p>
This tiny program shows every possible state of a boolean expression
to make sure your logic is correct. I wrote this to help me reading a
textbook about logic, and to make programming nested condition
statements easy.
</p>
<p>
One nice thing is "permlink" function. You can bookmark your favorite
boolean expressions to play again. It works even in file URL as this
is written entirely in Javascript. So feel free to download to your
local disk.
</p>
<p>
Here are a couple of examples to link boolean tables:
</p>
<ul>
<li><a href="http://languagegame.org/pub/booltable/booltable.html?q=A%2BB">A or B</a></li>
<li><a href="http://languagegame.org/pub/booltable/booltable.html?q=-P%2BQ">A implies B</a></li>
<li><a href="http://languagegame.org/pub/booltable/booltable.html?q=(P%3D%3EQ)*(Q%3D%3ER)%3D%3E(P%3D%3ER)">(P=>Q)*(Q=>R)=>(P=>R)</a></li>
</ul>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com2tag:blogger.com,1999:blog-8272979.post-76923501291075741452009-06-12T14:18:00.000-07:002009-06-12T14:42:28.369-07:00Lazy list and Data flow in Squeak<h4> Introduction </h4>
<p>I have been working on lazy list these days. A lazy list is a
collection where each element is evaluated only when it's
necessary. Lazy lists are very useful to express mathematical infinite
sequence naturally like all natural numbers, entire prime numbers, or
so.</p>
<p>Lazy lists are also practical when you deal with a large sequence
of data. Imagine that you want to replace particular words in a large
text, and print out just the first 100 characters. Without lazy list,
you must either, 1) replace all words and take first 100 characters,
or 2) count character position carefully each time when a word is
replaced. 1) requires time, and 2) tend to lost modularity. With lazy
lists, you can write such program as simple as former way, but
performance is still reasonable.</p>
<p>Non-strict functional language like Haskell supports this feature
in everywhere, but I was also interested in implementations of lazy
lists in "normal" languages. Even though its long history, lazy lists
have not been widely used. Lazy lists are sometimes called as
"Stream", and indeed, Unix's pipe can be seen as a kind of lazy
list. But it lacks generality. I wondered if I can find some traps to
be solved when I implement it myself. Squeak is a powerful tool for
the purpose because it has flexible runtime debugging support. And I
believe most part of difficulty in the concept comes from difficulty
of its runtime behavior.</p>
<p><a href="http://mitpress.mit.edu/sicp/full-text/sicp/book/node69.html">SICP</a>
is a good tutorial and I found further discussions
in <a href="http://srfi.schemers.org/srfi-40/srfi-40.html">SRFI-40</a>
and
<a href="http://srfi.schemers.org/srfi-41/srfi-41.html">SRFI-41</a>. Ruby
has good <a href="http://lazylist.rubyforge.org/">implementation</a>
similar to SRFI-41. And even Squeak has two implementations
(<a href="http://www.squeaksource.com/LazyList.html">LazyList</a>
and <a href="http://www.squeaksource.com/LazyCollections.html">LazyCollections</a>)!
And here is my story.</p>
<h4> Natural numbers </h4>
<p>You can download a demo image
from <a href="http://languagegame.org/pub/LazyList.zip">LazyList.zip</a>
or current source code from
<a href="http://www.squeaksource.com/Leisure/Collections-Lazy-tak.5.mcz">Collections-Lazy-tak.5.mcz</a>.
This source only uses basic functions in my home brewed image, but
please let me know if it doesn't work in your Squeak image.</p>
<p>This is an expression to make natural numbers with LazyList.</p>
<pre>
list := LazyList nat.
</pre>
<p>I took advantage of Squeak tools, inspector and explore. If you
inspect the variable "list" (select "inspect it" in the context menu),
you will see internal structure of the list. And if you explore the
list (select "explore it"), you see public "interface" of the
list. I'll show you what I meant.</p>
<p><a href="http://www.flickr.com/photos/propella/3618079605/" title="LazyList1 by propella, on Flickr"><img src="http://farm4.static.flickr.com/3342/3618079605_3252d9eb72_o.jpg" width="435" height="202" alt="LazyList1" /></a></p>
And when you open a list at the explorer (the right window), values of
public accessors <code>head</code> and <code>tail</code> are shown,
and also the inspector is updated. The first element 1 is made only
because someone send
<code>head</code> message. And you can get further numbers with
clicking <code>tail</code> accessor. Note that while explorer triggers
the list, inspector is inert so that you can freely observe internal
behavior of the list.
<a href="http://www.flickr.com/photos/propella/3618974548/" title="LazyList2 by propella, on Flickr"><img src="http://farm3.static.flickr.com/2455/3618974548_b828e71321_o.jpg" width="432" height="197" alt="LazyList2" /></a>
<p>You can do this by a program. Message <code>head</code> answers the
first element of a list, and <code>tail</code> answers following
list. This is same as CAR and CDR pair in lisp. Many other methods are
defined e.g. <code>take:</code> returns a LazyList including first n
elements, and contents convert LazyList to Array.</p>
<pre>
list head. "=> returns 1"
list tail. "=> returns LazyList .."
(list take: 10) contents. "=> #(1 2 3 4 5 6 7 8 9 10)"
</pre>
<p>And then, try next expression. You might know that select: is a
message where a selected collection specified by a block as a
condition is returned (this is "filter" in other language). But how
possibly all natural numbers can be used with select:? Unlike other
collection methods, it doesn't evaluate a condition block
immediately. Instead, this method returns a new list which will be
behave as a filter of natural numbers.</p>
<pre>
list select: [:e | e odd].
</pre>
<a href="http://www.flickr.com/photos/propella/3618367779/" title="LazyList3 by propella, on Flickr"><img src="http://farm4.static.flickr.com/3614/3618367779_5ea1c429ba_o.jpg" width="420" height="196" alt="LazyList3" /></a>
<h4> Define a new LazyList </h4>
Most useful way to construct a new lazy list would be using
<code>followedBy:</code> method. The receiver becomes head of new
list, and the argument becomes tail. You can use it with any receiver,
and the argument must be a LazyList or block that returns a
LazyList. LazyList nil is used to specify end of the list.
<pre>
1 followedBy: (2 followedBy: (3 followedBy: LazyList nil))
"=> same as LazyList withAll: #(1 2 3)"
</pre>
You can define natural numbers using <code>followedBy:</code> like
this.
<pre>
nat := 1 followedBy: [nat collect: [:e | e + 1]].
</pre>
It seems very strange! But please be relax. The first element of the
list is obviously 1. How about the second? <code>collect:</code> is
sometimes called as map function in other languages, and <code>nat
collect: [:e | e + 1]</code> answers a LazyList with all element is
just larger by 1 than nat itself. Therefore the sequence is generated
by recursive fashion. How clever!
<pre>
nat = 1, ...
nat collect: [:e | e + 1] = 2, ...
nat = 1 followedBy: nat collect: [:e | e + 1] = 1, 2, ...
nat collect: [:e | e + 1] = 2, 3, ...
nat = 1 followedBy: nat collect: [:e | e + 1] = 1, 2, 3, ...
nat collect: [:e | e + 1] = 2, 3, 4, ...
nat = 1 followedBy: nat collect: [:e | e + 1] = 1, 2, 3, 4, ...
</pre>
Squeak Smalltalk has some great heritage from APL. Many arithmetic
functions are defined in collections. So does LazyList. There is a
much simple definition of natural number.
<pre>
nat := 1 followedBy: [nat + 1].
</pre>
It reminds me an ugly assignment expression with side effect.
<pre>
x := x + 1.
</pre>
<p>This is ugly because it looks like an equation but it is
not. <code>x</code> is never equal to <code>x + 1</code>! Sometimes
it confuses a beginner programmer. Still, it is too useful to
ignore. We need some reasoning of such side effect to use safely. On
the other hand, <code>nat := 1 followedBy: [nat + 1]</code> is similar
enough to <code>x := x + 1</code> yet, it is actually an
equation. This is a significant coincidence, isn't it?</p>
<h4> Iteration, Data flow, Lazy list, and Polymorphic functions </h4>
<p>One of the problems in <code>x := x + 1</code> is that value of x
depends on the position in the source code. So you have to be careful
about order of each expression. Are there any better ways? You can
imagine more mathematical programming language to allow you to define
a function as a equation.</p>
<pre>
x<sub>1</sub> = 1 --- some initial number
x<sub>n</sub> = x<sub>n - 1</sub> + 1
</pre>
<p>In this equations, it is clear that right hand side of x is older
than left hand side of x. This is pure and easy to reason. But another
problem occurs. In practice, the program requires whole history of xs
because now a programmer can specify any old value like <code>x<sub>n -
100</sub></code>.</p>
<p>So I would add a restriction. What if only addition is allowed in
subscript. In other words, what if only "future" value can be referred
but "past" so that we can forget our unnecessary past conveniently (it
is possible with nice GC).</p>
<pre>
x<sub>1</sub> = 1 --- some initial number
x<sub>n + 1</sub> = x<sub>n</sub> + 1
</pre>
It makes the relationship between an iteration <code>x := x + 1</code>
and a lazy list more clear. This iteration can be converted a lazy
list definition directly.
<pre>
nat := 1 followedBy: [nat + 1].
~~~ ~~~~~~~~~
x<sub>1</sub> = 1; x<sub>n + 1</sub> = x + 1
</pre>
<p>I know this discussion is still rough. You can find better
discussion
from <a href="http://en.wikipedia.org/wiki/Lucid_(programming_language)">Lucid</a>. However,
my theory is that data flow structures (mathematical iteration) can be
expressed by lazy lists and polymorphic methods without special
language.</p>
<p>Here is another example of definition of a lazy list in iterative
way to compute Fibonnaci numbers. <code>next</code> is a synonym
of <code>tail</code>.</p>
<pre>
fib := 1 followedBy: [1 followedBy: [fib + fib next]].
</pre>
<p>This corresponds next mathematical equations.</p>
<pre>
fib<sub>1</sub> = 1
fib<sub>2</sub> = 2
fib<sub>n + 2</sub> = fib<sub>n</sub> + fib<sub>n + 1</sub>
</pre>
<h4> Simulations </h4>
<p> As a little bit more realistic example, I will show you a gravity
simulation using lazy lists. In this demo, a global variable Y shows
height of an object, the first position is 400, and it is increased by
Speed. The initial value of Speed is 0 and the value is decreased by 1
while the hight Y is positive. If Y is negative, Speed is negated
which means the object is bounced by the ground!</p>
<pre>
Y := 400 followedBy: [Y + Speed next].
Speed := 0 followedBy: [Y > 0 whenTrue: Speed - 1
whenFalse: Speed negated].
</pre>
<p><a href="http://www.flickr.com/photos/propella/3620577198/" title="LazyList by propella, on Flickr"><img src="http://farm4.static.flickr.com/3591/3620577198_689d22aba0_o.gif" width="628" height="426" alt="LazyList" /></a></p>
<p>Morphic part of this demo used a special morph named ListPointer
that worked as an interface between LazyList and Morphs.</p>
<p> I began this library as a replacement of Stream and
OrderedCollection. But it turned out that combination of polymorphic
methods and LazyList has unexpected cute property as data flow. I'm
very happy about the fact! If you are interested in rather practical
aspect of lazy lists, please check out List >> show method in this
library. printString for LazyList is implemented this framework
itself. </p>
<p> I already noticed that there are a lot of rooms I could improve
it. The design was briefly along with SRFI-40, but I will include more
ideas in SRFI-41 and Ruby's lazylist. I have ignored them so far
simply because I am lazy! </p>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com2tag:blogger.com,1999:blog-8272979.post-31495920689683676862009-05-26T13:48:00.000-07:002009-05-26T14:01:52.028-07:00A complete example of generating a sound in Flash with SampleDataEvent<p>Flash version 10 has significant feature about audio, <a href="http://help.adobe.com/en_US/AS3LCR/Flash_10.0/flash/events/SampleDataEvent.html">SampleDataEvent</a>. Until
this version, there was no way to generate a sound wave easily. Some
people have tried to do that by rather magical way of <a href="http://www.flashbrighton.org/wordpress/?p=9">how to make
actionscript 3 play generated pcm wave data</a> in Flash 9, however,
now we have a straightforward API from Flash 10. I think this is a
great improvement for hobby programmers who are interested in computer
generated music. While it's shame from some perspective. Just this API
finally brings us a point where old BASIC and PLAY statement could
do a quarter centry ago!</p>
<p>You would find a lot of examples about SampleDataEvent, but some of
those are wrong or uncompleted, since I think this API have been
changed so often in beta version. And I wrote my version of simplest
example for exercise.</p>
There are a couple of tricks you might trap.
<ul>
<li>If you get an error message: "Flex error: type was not found or was
not a compile-time constant: SampleDataEvent", you have to specify the
Flash version to 10.0.0. Set -target-player option or Flex builder's
Project's Properties - ActionScript Compiler - HTML Wrapper</li>
<li>Some documentation might use Event.SAMPLE_DATA, but this is not true.</li>
</ul>
<script src="http://gist.github.com/117424.js"></script>
Generated SWF file: <a href="http://languagegame.org/pub/SineSound.swf">http://languagegame.org/pub/SineSound.swf</a>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-77537163553367851522009-04-28T02:51:00.000-07:002009-05-01T11:26:43.100-07:00A Prolog In Haskell<h3>Prolog In Haskell</h3>
<p>I have been obsessed by Prolog language recent weeks. While I first
learned Prolog long time ago, and actually I was attracted, I have
never used it fluently because it's too hard to get familiar without
any practical necessity. Although, there are a lot of interesting
literatures which require certain knowledge of logic programming in
computer science. So, I decided to do another approach; writing a
Prolog interpreter to learn Prolog.</p>
<p>I chose Haskell as the implementation language because of its
succinctness. I'm a beginner Haskell programmer, and I thought it was
also a good opportunity to learn Prolog and Haskell same time! The
starting point was a Prolog implementation in Hug98 distribution
<a href="http://darcs.haskell.org/hugs98/demos/prolog/">http://darcs.haskell.org/hugs98/demos/prolog/</a>. I
think this is a great Haskell program, but its too difficult to
me. Rewriting it as my level would be a good exercise.
</p>
<h4>Data structures</h4>
<p>Here is my version of Prolog in Haskell. Entire program is about
200+ lines. There is no cut operator but it has a list notation so
that you can write [apple, orange | banana] stile literal. Let's take
a look at the first part.
</p>
<pre>
module Prolog
(Term(..), Clause(..), w, s, cons,
parse, parse',
atom, variable, struct, list, nil, terms, arguments, term, clause, clauses, query,
display,
unify, unifyList, applyTerm, prove, rename, solveString) where
import Text.ParserCombinators.Parsec
import Data.Maybe
import Char
</pre>
<p>I used Parsec as a parser, and defined some data structures. </p>
<pre>
infix 6 :-
data Term = Var String Int | Struct String [Term] deriving (Show, Eq)
data Clause = Term :- [Term] deriving (Show, Eq)
data Command = Fact Clause | Query [Term] | ShowAll | Noop
type Rules = [Clause]
type Substitution = [(Term, Term)]
</pre>
<p>Term represents Prolog's term like "apple" or "father(abe,
homer)". It can be a variable, or a structure. A variable has an index
number which I used it later to distinct a same variable name in
different contexts. A simple term like "apple" is also represented as
a structure without elements like <code>Struct "apple" []</code>.
</p>
<p>Clause is a Prolog rule like "mortal(X) :- man(X)". I stole a user
defined operator constructor ":-" from original Hugs' Prolog to write
a Haskell expression in Prolog like. So "mortal(X) :- man(X)" in
Haskell expression becomes <code>Struct "mortal" [Var "X" 0] :-
[(Struct "man" [Var "X" 0])]</code>. Well, it's not quite
nice. Although the parser will provide better notation later, I have
to use this expression when debugging the interpreter meanwhile. Its
cumbersome. So I made up tiny utility functions to make Prolog data
easier.
</p>
<pre>
-- Utility constructors for debugging
w :: String -> Term
w s@(x:xs) | isUpper x = Var s 0
| otherwise = Struct s []
s :: String -> [Term] -> Term
s n xs = Struct n xs
cons s cdr = (Struct "cons" [w s, cdr])
</pre>
Using this functions, now "mortal(X) :- man(X)" is written as <code>
s"mortal" [w"X"] :- [s"man" [w"X"]] </code>. It is much better, isn't
it?
<h4>Unification</h4>
<p> By the way, I like the word unification. It sounds peace and
spiritual! Unification is one of two most peculiar concept in Prolog
(another one is the control structure by depth first
search). Unification is solving a logical equation. For example, the
answer of "[X, orange] = [apple, Y]" must be X = apple, and Y =
orange. It is almost same as variable binding in a normal programming
language, but tricky part is that a direction is symmetry, so X = Y
and Y = X is same meaning. How can it be possibly implemented?? Think
about the data structure of the answer at first.
</p>
<pre>
---- Unification ----
type Substitution = [(Term, Term)]
true = []
</pre>
<p> I used a list of tuples of terms, or an associate list to
represent a substitution. For example, "X = apple, Y = orange" is
represented as [(X, apple), (Y, orange)] (in actual Haskell
code, <code> [(w"X", w"apple"), (w"Y", w"orange")] </code>). A tuple
of left hand side is always a variable name, and right hand side is
any term, concrete value preferably. The goal of unification is making
associations with variable and term. To make this process easier,
"transitive" substitution is allowed. Think about an equation "X = Y,
Y = banana". It is represented like [(X, Y), (Y, banana)], which is
solved as X = banana, and Y = banana in apply function. Let's look at
the implementation.
<pre>
-- apply [(w"X", w"Y"), (w"Y", w"Z")] [(w"X"), (w"Y")] == [(w"Z"), (w"Z")]
apply :: Substitution -> [Term] -> [Term]
apply s ts = [applyTerm s t | t <- ts]
applyTerm [] (Var y n) = Var y n
applyTerm ((Var x i, t):s) (Var y j) | x == y && i == j = applyTerm s t
| otherwise = applyTerm s (Var y j)
applyTerm s (Struct n ts) = Struct n (apply s ts)
</pre>
<p>The function apply substitutes a variable name of its value. To
support transitive apply, applyTerm is called recursively if the value
is also a variable. But it can solve only one way. Think about opposite
case "Y = banana, X = Y". Apply can't find the fact X = banana because
"Y = banana" is appeared before. So what I should do is applying X = Y
before adding the substitution.
</p>
<table border="1">
<tr><td></td><td>Equation</td><td>Substitution(solution)</td></td></tr>
<tr><td>1</td><td>Y = banana, X = Y</td><td></td></tr>
<tr><td>2</td><td>X = Y</td><td>Y = banana (append)</td></tr>
<tr><td>3</td><td>X = banana (apply: Y = banana) </td><td>Y = banana</td></tr>
<tr><td>4</td><td></td><td>Y = banana, X = banana (append)</td></tr>
</table>
<p>I suppose that this two fold way solve all of logical
equation. Apply is always needed before append it to the
solution. Actual source implementation seems to be complicated because
there are cases where a variable can appears any side, and sometimes
there is no solution. To represent no-answer case, a Maybe monad is
used. So there are variations such as;
</p>
<ul>
<li> No Answer : Nothing </li>
<li> Always true (like apple = apple) : Just true (true is a synonym of empty list []) </li>
<li> Substitution found : Just [X = some answer...] </li>
</ul>
<pre>
-- unify (w"X") (w"apple") == Just [(w"X", w"apple")]
unify :: Term -> Term -> Maybe Substitution
unify (Var x n) (Var y m) = Just [(Var x n, Var y m)]
unify (Var x n) y = Just [(Var x n, y)]
unify x (Var y m) = Just [(Var y m, x)]
unify (Struct a xs) (Struct b ys)
| a == b = unifyList xs ys
| otherwise = Nothing
unifyList :: [Term] -> [Term] -> Maybe Substitution
unifyList [] [] = Just true
unifyList [] _ = Nothing
unifyList _ [] = Nothing
unifyList (x:xs) (y:ys) = do s <- unify x y
s' <- unifyList (apply s xs) (apply s ys)
return (s ++ s')
</pre>
<p>Note that I just use append (++) to add a new substation in
unifyList. But if you design carefully, recursive apply is not
necessary. Using something like a map is a better idea.
</p>
<h4>Solver</h4>
<p>As a programming language, Prolog is unique as it has no explicit
control structure. Instead, a Prolog program can be seen as a big
nested if then else statement. This find and branch functions are
implemented of this behavior. While unification is a technique of how
to solve a equation, solver deals with when each equation should be
solved. There are two most important concepts to understand control
structures in Prolog.
</p>
<ul>
<li>Goals (AND relationship) : are terms which should be solved.</li>
<li>Branches (OR relationship) : are options which might have a solution</li>
</ul>
<p> A proof's fate is decided by branch function, branch function
returns a list of goals (with corresponding substitutions). If the
list is empty, this branch is failed. If the list includes empty goal,
it is actually succeed because empty goal means that it is unified
against a fact like "food(apple).". Well, is it complicated?
</p>
<ul>
<li> If branch returns [] <--- this is failed </li>
<li> If branch returns [ [some goals] [some goals] [(empty)] <--- this is succeed! ] </li>
</ul>
The goal of find function is traverse all of goals to find whether if
it is true or false.
<pre>
---- Solver ----
prove :: Rules -> [Term] -> [Substitution]
prove rules goals = find rules 1 goals
-- Depth first search
-- find (parse' clauses "p(X):-q(X). q(a).") 1 [parse' term "p(X)"]
find :: Rules -> Int -> [Term] -> [Substitution]
find rules i [] = [true]
find rules i goals = do let rules' = rename rules i
(s, goals') <- branch rules' goals
solution <- find rules (i + 1) goals'
return (s ++ solution)
-- Find next branches. A branch is a pair of substitution and next goals.
-- branch (parse' clauses "n(z). n(s(X)):-n(X).") (parse' query "?-n(X).")
branch :: Rules -> [Term] -> [(Substitution, [Term])]
branch rules (goal:goals) = do head :- body <- rules
s <- maybeToList (unify goal head)
return (s, apply s (body ++ goals))
</pre>
<p> Find function has an argument for index number to show the depth
of the tree. This number is used to rename all variables used in whole
rules. This is necessary because same variable name in different
clauses are actually represented different variables.</p>
<pre>
-- Rename all variables in the rules to split namespaces.
rename :: Rules -> Int -> Rules
rename rules i = [ renameVar head :- renameVars body | head :- body <- rules]
where renameVar (Var s _) = Var s i
renameVar (Struct s ts) = Struct s (renameVars ts)
renameVars ts = [renameVar t | t <- ts]
</pre>
I have only explained evaluator part of the REPL, but still there are
reader, printer, and loop. You can browse and download whole source
code
from <a href="http://github.com/propella/prolog/tree">http://github.com/propella/prolog/tree</a>.
Someday I might write some of interesting topics in the program...Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com7tag:blogger.com,1999:blog-8272979.post-87831197716833267172009-04-05T00:01:00.000-07:002009-04-05T00:02:19.138-07:00Learning Erlang and Adobe Flash format same time part 2<img src="http://languagegame.org/pub/erlang_swf.png" />
<p>
I have already written most important part about SWF format and
Erlang's bit syntax
at <a href="http://propella.blogspot.com/2009/03/learning-erlang-and-adobe-flash-format.html">previous
post</a>. But just for the record, I take a note of miscellaneous
knowledge to construct an interesting Flash shape. This entire note
doesn't have any practical value because there are already many other
useful libraries to build a swf file. But some of historical esoteric
magical peculiar internal might interests you.
</p>
<p> In the previous example, I only made three control tags:</p>
<ul>
<li>End (Tag type = 0)</li>
<li>ShowFrame (Tag type = 1)</li>
<li>SetBackgroundColor (Tag type = 9)</li>
</ul>
<p> Here, I introduce you two additional tags,</p>
<ul>
<li>DefineShape (Tag type = 2) defines a vector graphics, and</li>
<li>PlaceObject2 (Tag type = 26) shows the graphics to an actual screen.</li>
</ul>
<p>I designed new data structure to represent a SWF shape. While
spec/0 is almost same as previous program, I add sample_shape/0 to
define DefineShape.</p>
<pre>
% an example shape.
spec() ->
{{frame_size, 6000, 3000},
{frame_rate, 16},
{frame_count, 160},
[{set_background_color, {rgb, 240, 250, 250}},
sample_shape(),
{place_object2, 1},
{show_frame},
{end_tag}]}.
sample_shape() ->
{define_shape,
{shape_id, 1},
{bounds, {rectangle, 2000, 3000, 1000, 2000}},
{shapes, {{fills, [{solid_fill, {rgb, 50, 200, 50}}]},
{lines, [{line_style, 100, {rgb, 100, 255, 100}},
{line_style, 100, {rgb, 50, 150, 50}}]},
{shape_records,
[{style_change, [{move_to, 2000, 2000}]},
{style_change, [{line_style, 1},
{fill_style0, 1}]},
{straight_edge, 0, -1000},
{straight_edge, 1000, 0},
{style_change, [{line_style, 2},
{fill_style0, 1}]},
{straight_edge, 0, 1000},
{straight_edge, -1000, 0},
{end_shape}]
}}}}.
</pre>
<p> It looks complicated though, it is actually very
straightforward. A DefineShape has a shape ID (or character ID), its
bounding box, and actual shapes. "shape_id", "bounds", and "shapes"
tuples at sample_shape/0 denote these information. Shape ID is used
later for a reference by PlaceObject2. </p>
<p> A Shapes part consists of further sub elements, fills, lines and
shape records. Every style information are defined in advance, and
referenced with corresponding ID. In this case, one solid fill and two
line styles are defined. After styles are defined, shape records are
followed. A shape record is the most interesting and complicated
part. I'll draw a moss green rectangle in 1000 x 1000 twips (20 twips
= 1 pixel) with light and dark green borders in a pseudo 3-D
style.</p>
<p> This is an actual implementation of DefineShape and
PlaceObject2. I'm afraid it seems to be complicated, but it is just a
direct translation from the specification. Thanks to Erlang's pattern
matching syntax, It is easy to add a new tag by putting a new
pattern. But sometimes distinction between ; (semi colon is used
between patterns in a function) and . (dot is used after a function
definition) annoys me.</p>
<pre>
tag({define_shape,
{shape_id, ShapeId},
{bounds, Bounds},
{shapes, ShapesWithStyle}}) ->
BoundsBits = rectangle(Bounds),
Shapes = shape_with_style(ShapesWithStyle),
record_header_body(2, list_to_binary([<<ShapeId:16/unsigned-little>>, BoundsBits, Shapes]));
tag({place_object2, CharacterId}) ->
PlaceFlagHasClipActions = 0,
PlaceFlagHasClipDepth = 0,
PlaceFlagHasName = 0,
PlaceFlagHasRatio = 0,
PlaceFlagHasColorTransform = 0,
PlaceFlagHasMatrix = 0,
PlaceFlagHasCharacter = 1,
PlaceFlagMove = 0,
Depth = 1,
record_header_body(26, <<PlaceFlagHasClipActions:1,
PlaceFlagHasClipDepth:1,
PlaceFlagHasName:1,
PlaceFlagHasRatio:1,
PlaceFlagHasColorTransform:1,
PlaceFlagHasMatrix:1,
PlaceFlagHasCharacter:1,
PlaceFlagMove:1,
Depth:16/unsigned-little,
CharacterId:16/unsigned-little>>).
</pre>
<p> shape_with_style/1 is used to construct SHAPEWITHSTYLE structure
in the specification. </p>
<pre>
shape_with_style({{fills, Fills}, {lines, Lines}, {shape_records, Shapes}}) ->
FillBits = nbits_unsigned([length(Fills)]),
LineBits = nbits_unsigned([length(Lines)]),
ShapeRecords = shape_records({shape_records, Shapes}, FillBits, LineBits),
[fill_style_array({fills, Fills}),
line_style_array({lines, Lines}),
<<FillBits:4,
LineBits:4>>,
ShapeRecords].
</pre>
<p>The tricky part is FillBits and LineBits. As I have already
mentioned when explaining a rectangle format in previous post, the SWF
format tries to shorten a file size by all means, bit by bit. FillBits
defines maximum bit size needed by fill style id. For example, if you
use only one fill style, one is enough for FillBits. But if you use
seven, FillBits is three (because seven is 111 as a binary). After
FillBits and LineBits are calculated, they are needed in next helper
function shape_records/3. But before I show you shape_records/3, some
simple functions to construct styles are followed. </p>
<pre>
fill_style_array({fills, FillStyleArray}) ->
FillStyleCount = length(FillStyleArray),
[<<FillStyleCount:8>>, [fill_style(X) || X <- FillStyleArray]].
fill_style({solid_fill, RGB}) -> [<<16#00:8>>, rgb(RGB)].
line_style_array({lines, LineStyleArray}) ->
LineStyleCount = length(LineStyleArray),
[<<LineStyleCount:8>>, [line_style(X) || X <- LineStyleArray]].
line_style({line_style, Width, RGB}) ->
[<<Width:16/unsigned-little>>, rgb(RGB)].
</pre>
<p> I think these are straightforward. Perhaps, next is the most
tricky part of the SWF shape. Shape records include a number of
records, each record represents style change or position change or
so. While a rectangle format must to be byte aligned, each record must
not be aligned, but whole shape records including them must be
aligned! This fact is described in the specification very obscure way,
so I didn't find out what to do unless many try-and-errors. Although,
I might misunderstood what is a shape record...</p>
<blockquote>
Each individual shape record is byte-aligned within an array of shape records; one shape
record is padded to a byte boundary before the next shape record begins. --- SWF File Format Specification Version 10
</blockquote>
<p>
To concatenate many bit strings into one, and align whole bits, I made
two functions padding/1 and concat_bits/1 (padding/1 is same one as
previous post). It is likely that concatenating bitstrings exists
already, but I couldn't find out from the library.
</p>
<pre>
shape_records({shape_records, ShapeRecords}, FillBits, LineBits) ->
padding(concat_bit([shape_record(X, FillBits, LineBits) || X <- ShapeRecords])).
padding(Bits) ->
Padding = 8 - bit_size(Bits) rem 8,
<<Bits/bitstring, 0:Padding>>.
concat_bit(XS) -> lists:foldl(fun(X, Y) -> <<Y/bitstring, X/bitstring>> end, <<>>, XS).
</pre>
Rest of the source is definitions of each record. I omitted a lot of
features to the explanation purpose. EndShapeRecord and
StraightEdgeRecord are quite simple.
<pre>
shape_record({end_shape}, _, _) -> <<0:1, 0:5>>;
shape_record({straight_edge, DeltaX, DeltaY}, _, _) ->
NumBits = nbits_signed([DeltaX, DeltaY]),
GeneralLineFlag = 1,
<<1:1, 1:1, (NumBits - 2):4, GeneralLineFlag:1, DeltaX:NumBits, DeltaY:NumBits>>;
</pre>
<p> But StyleChangeRecord is the second tricky and daunting part in
spite of Erlang's succinct syntax. A part of reasons of the complexity
is that StyleChangeRecord allows to define a couple of operations at
once optionally; line style, fill style, and pen move. So we need some
data structure to represent such option. </p>
<p> In object oriented languages, a dictionary or a map is commonly
used while an associated list is popular in functional languages. In
Erlang, a list of tuples might be enough. lists:keysearch/3 find a
tuple in a list where first argument is matched, so we can use it as a
dictionary like structure. In our example, [{line_style, 1},
{fill_style0, 1}] means we want to change line style and fill style
same time. and lists:keysearch(line_style, 1, ChangeSpec) detects a
line style change option.</p>
<pre>
shape_record({style_change, ChangeSpec}, FillBits, LineBits) ->
TypeFlag = 0,
StateNewStyles = 0,
StateFillStyle1 = 0,
{StateLineStyle, LineStyleData} =
case lists:keysearch(line_style, 1, ChangeSpec) of
{value, {_, LineStyle}} -> {1, <<LineStyle:LineBits>>};
false -> {0, <<>>} end,
{StateFillStyle0, FillStyle0Data} =
case lists:keysearch(fill_style0, 1, ChangeSpec) of
{value, {_, FillStyle0}} -> {1, <<FillStyle0:FillBits>>};
false -> {0, <<>>} end,
{StateMoveTo, MoveData} =
case lists:keysearch(move_to, 1, ChangeSpec) of
{value, {_, MoveDeltaX, MoveDeltaY}} ->
MoveBits = nbits_signed([MoveDeltaX, MoveDeltaY]),
{1, <<MoveBits:5,
MoveDeltaX:MoveBits/signed,
MoveDeltaY:MoveBits/signed>>};
false -> {0, <<>>} end,
<<TypeFlag:1,
StateNewStyles:1,
StateLineStyle:1,
StateFillStyle1:1,
StateFillStyle0:1,
StateMoveTo:1,
MoveData/bitstring,
FillStyle0Data/bitstring,
LineStyleData/bitstring>>.
</pre>
I uploaded final
program <a href="http://languagegame.org/pub/swf.erl">http://languagegame.org/pub/swf.erl</a>.Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com3tag:blogger.com,1999:blog-8272979.post-83319477570262527092009-03-27T13:40:00.000-07:002009-03-27T13:41:08.987-07:00Learning Erlang and Adobe Flash format same time<img src="http://languagegame.org/pub/swf_simple.png"></img>
<p>
Since <a href="http://lukego.livejournal.com/">Luke Gorrie</a>
encouraged me to learn Erlang, I have been playing with a bit with the
language. One of the most attracting points is
<a href="http://erlang.org/doc/programming_examples/bit_syntax.html">bit
syntax</a>. When you want a byte array with 65, 66, 67. I can write it
as <<65,66,67>>. Further more, When you want a bit pattern of 4 in
four bits, 1 in four bits and 0x4243 in 16 bits, you may say <<4:4,
1:4, 16#4243:16>>. What a cool!
</p>
<pre>
$ erl
Eshell V5.6.4 (abort with ^G)
1> <<65,66,67>>. % numbers are printed with ASCII
<<"ABC">>
2> <<4:4, 1:4, 16#4243:16>>.
<<"ABC">>
</pre>
<p>I was soon tempted to build a meaningful binary data with this
syntax. What does suit? Adobe Flash format would be the weirdest and
coolest. It's weirdest because of very bits oriented taste by perhaps
historical reasons. It's coolest because it's popular. I want to show
you how Erlang is powerful by writing complicated SWF format in the
sophisticated
syntax. Fortunately, <a href="http://www.adobe.com/devnet/swf/">the
SWF specification</a> is now free and everybody can write a flash
editor by themselves.</p>
<p>First of all, I
chose <a href="http://erlang.org/doc/man/escript.html">scripting
style</a> because I'm too lazy to wait for a compiler. And I start a
shell bang line.</p>
<pre>
#!/usr/bin/env escript
%% -*- erlang -*-
%%! debug verbose
</pre>
<p>I don't understand how it works, but I just copied from the
manual. And then, I have to decide what my first flash file looks
like. I'm modest enough to satisfy just a salmon colored window. This
is a spec file representing my flash.</p>
<pre>
% an example flash contents.
spec() ->
{{frame_size, 2000, 3000},
{frame_rate, 10},
{frame_count, 10},
[{set_background_color, {rgb, 250, 100, 100}},
{show_frame},
{end_tag}]}.
</pre>
<p>This is already reflected by the structure of a flash file. A flash
file starts with meta data of file size, frame rate, and frame
count. And a bunch of tagged data are followed. Tagged data is the key
of extensibility of the flash format. You can embed various kinds of
media as various type of tags in a file. In Erlang, fixed sized data
is represented as {tuples}, and variable sized data is [lists]. I
write each element as {key, arg1, arg2, ...} style, and tags are
represented as a list. You might understand each tuple's meaning. You
can change the color or size if you like.</p>
<p>Rest of the program reads this data and write a SWF file. I'll
explain the program in a top down fashion. The simple main function
opens a file and write something. Actual data is created by swf/0
(name/arity is Erlang's way to point to a function) as a sequence of
binary.</p>
<pre>
main(_) ->
Filename = "simple.swf",
{ok, S} = file:open(Filename, [binary, write]),
file:write(S, swf(spec())),
file:close(S).
</pre>
<p>Now interesting part begins. If you read Chapter 2: SWF Structure
Summary in the SWF specification, you may find that the Erlang program
is much more concise and easier to understand than long description in
the specification (although, I admit that I omitted some
details). Especially, a bit syntax part is obvious, "FWS" is three
byte characters, 'Version:8/unsigned-little' is a 8 bits integer for
version number, and 'FileLength:32/unsigned-little' follows as a 32
bits little endian unsigned integer for file length. 'Rest/binary'
looks tricky, but it means that another binary data Rest is embedded
here.</p>
<pre>
% SWF Structure
swf(Spec) ->
Version = 10,
Rest = swf_rest(Spec),
FileLength = size(Rest) + 8,
<<"FWS",
Version:8/unsigned-little,
FileLength:32/unsigned-little,
Rest/binary>>.
</pre>
<p>Because I needed to know the file size in advance, I had to split
the main part in two. Swf_rest/1 composes every elements in data, and
swf/1 mesures its file size and puts to the top. To pass my sample
data to swf_rest/1, I
use <a href="http://erlang.org/doc/reference_manual/expressions.html#pattern">patterns</a>. Thanks
to to tuples and patterns, I don't have to remember an order of
arguments. It looks
like <a href="http://docs.python.org/tutorial/controlflow.html#keyword-arguments">keyword
arguments</a> and more generic. Note that words begins with a lower
case like 'frame_size' are symbols and words begins with a capital
like 'Width' are variables in Erlang, in my case, 2000 is set to
Width. In SWF file, a special unit 'twips' is used, 20 twips are a
pixel.</p>
<p>A <a href="http://erlang.org/doc/programming_examples/list_comprehensions.html">list
comprehensions</a> is another useful feature. I only used it as a
shorthand of "map" function like [tag(X) || X <- Tags], which means
apply tag/1 function to each element in Tags, but it saved many
typing.</p>
<pre>
swf_rest({{frame_size, Width, Height},
{frame_rate, FrameRate},
{frame_count, FrameCount},
Tags}) ->
FrameSize = rectangle({rectangle, 0, Width, 0, Height}),
FrameRateData = fixed8dot8(FrameRate),
TagsData = list_to_binary([tag(X) || X <- Tags]),
<<FrameSize/binary,
FrameRateData/binary,
FrameCount:16/unsigned-little,
TagsData/binary>>.
</pre>
Let's take a look at some detail of data type used in SWF. Color is
simple, it is just an array of three bytes for Red, Green, and Blue.
The description of 16-bit 8.8 fixed-point number in the specification
looks very complicated, but it just said that you have to put the
integer part last.
<pre>
% Basic Data Types
rgb({rgb, R, G, B}) -> <<R:8, G:8, B:8>>.
fixed8dot8(N)->
IntegerPart = trunc(N),
SmallPart = trunc((N - IntegerPart) / 1 * 256),
<<SmallPart:8, IntegerPart:8>>.
</pre>
<p>This is my favorite part. Rectangles are stored as very
bit-oriented way. First, you must get a enough bit size to store each
element (Nbits). Second, four elements are stored in this bit
size. Third, entire bits should be byte-aligned. This kind of tasks
are very tricky in other languages, it require a lots of shifts, ands,
ors, etc. But Erlang's bit syntax helps me a lot.</p>
<p>I wrote two (actually three) helper functions to make rectangle/1
simpler. nbits_signed/1 calculate enough bit size for a list of signed
integers, and padding/1 fills zeros to align byte width. '/bitstring'
is same as '/binary', but you can use it for any odd size of bits data
while binary works only byte arrays.</p>
<pre>
rectangle({rectangle, Xmin, Xmax, Ymin, Ymax}) ->
Nbits = nbits_signed([Xmin, Xmax, Ymin, Ymax]),
padding(<< Nbits:5,
Xmin:Nbits/signed-big,
Xmax:Nbits/signed-big,
Ymin:Nbits/signed-big,
Ymax:Nbits/signed-big>>).
nbits_unsigned(XS) -> % Necessary bits size for a list of integer values.
Max = lists:max([abs(X) || X <- XS]),
trunc(math:log(Max) / math:log(2)) + 1.
nbits_signed(XS) -> nbits_unsigned(XS) + 1.
padding(Bits) ->
Padding = 8 - bit_size(Bits) rem 8,
<<Bits/bitstring, 0:Padding>>.
</pre>
<p>Tags are the most important data structure in SWF. There are short
and long tags. Short one is used for 62 bytes of data or less. Because
tag code and length is packed in one place, you can save precious 16
bits space with short tag! Tricky part is here. In short tag, type
code and length are stored respectively 10 bits and 6 bits, however,
you have to save it as whole 16 bits integer in a little endian.
<pre>
Big endian
|Type |Length |
|9|8|7|6|5|4|3|2|1|0|5|4|3|2|1|0|
Little endian
|Typ|Length |Type |
|1|0|5|4|3|2|1|0|9|8|7|6|5|4|3|2|
</pre>
What a crazy?! (actually, it is not so strange than it looks if you
see carefully. Hint: bits runs right to left, bytes runs left to
right). Even these funny endianess conversion is handled easily in
Erlang because bit syntax can be used in patterns (input).
<pre>
% Tag Format
record_header_body(Type, Body) -> record_header_body(Type, Body, size(Body)).
record_header_body(Type, Body, Length) when Length < 63 ->
<<TagCodeAndLength:16/unsigned-big>> = <<Type:10, Length:6>>,
[<<TagCodeAndLength:16/unsigned-little>>, Body];
record_header_body(Type, Body, Length) ->
<<TagCodeAndLength:16/unsigned-big>> = <<Type:10, 63:6>>,
[<<TagCodeAndLength:16/unsigned-little>>,
<<Length:32/unsigned-little>>,
Body].
</pre>
Finally, I'll show you the format of actual contents. Now I have only
three tags for End (type=0), ShowFrame(type=1), and
SetBackgroundColor(type=9). You might easily add new tags to support
more convincing flash contents. Latest tag number is 91 for
DefineFont4, see APPENDIX B Reverse index of tag values in the
specification.
<pre>
% Control Tags
tag({end_tag}) -> record_header_body(0, <<>>);
tag({show_frame}) -> record_header_body(1, <<>>);
tag({set_background_color, RGB}) -> record_header_body(9, rgb(RGB)).
</pre>
I uploaded an entire program
at <a href="http://languagegame.org/pub/swf_simple.erl">swf_simple.erl</a> Erlang
is famous for its concurrent programming model, but I found another
aspects like bit syntax and pattern matching are also attractive and
useful to real application.
<ul>
<li>The SWF Specification:
<a href="http://www.adobe.com/devnet/swf/pdf/swf_file_format_spec_v10.pdf">http://www.adobe.com/devnet/swf/pdf/swf_file_format_spec_v10.pdf</a></li>
</ul>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-56108338019874400202008-10-06T20:37:00.000-07:002008-10-06T21:07:05.276-07:00Inspy from Turtle Geometry<p><a href="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7287">Turtle
Geometry</a> by Harold Abelson and Andrea diSessa has a lot of
interesting examples of turtle graphics. Especially I was fascinated
"inspy" program. The basic structure of inspy is same as spiral. But
instead of the side, value of the angle is changed in each step. I
have explored a bit for a demo of Chalkboard project
<a href="http://tinlizzie.org/chalkboard/#Inspi">http://tinlizzie.org/chalkboard/#Inspi</a>.
</p>
<p>To make the study easier, I made a trick to connect an event
handler and an inspy program. You can play with a dynamic version of
inspy program with it (Please move the mouse on next rectangle). And
you may find various patterns even from such simple program. Here I
present stand alone version (Only Firefox and Safari are supported).
</p>
<canvas width="400" height="400"
id="canvas"
onmousemove="turtleInit()"
style="border: 1px solid #808080; background: #e0f0e0;">
<a href="http://www.flickr.com/photos/propella/2920068605/" title="inspy by propella, on Flickr"><img src="http://farm4.static.flickr.com/3126/2920068605_ff84d6909a_o.png" width="410" height="409" alt="inspy" /></a>
</canvas>
<div id="watcher">
</div>
<script type="text/javascript">
if (window.Element && !Element.prototype.getBoundingClientRect) {
Element.prototype.getBoundingClientRect = function() {
var coords = { left: 0, top: 0, width: this.offsetWidth, height: this.offsetHeight };
var element = this;
while (element) {
coords.left += element.offsetLeft;
coords.top += element.offsetTop;
element = element.offsetParent;
}
return coords;
};
}
turtleInit = function() {
if (window._watcher) return
canvas = document.getElementById("canvas");
_watcher = document.getElementById("watcher");
source = document.getElementById("source");
ctxt = canvas.getContext('2d')
ctxt.lineWidth = 1
canvas.onmousemove = canvas_onmousemove
Turtle = {
x: canvas.width / 2,
y: canvas.height / 2,
angle: 0,
color: "black",
}
move(function() {
inspi(15, mouseX(), mouseY())
})
}
forward = function(n) {
ctxt.strokeStyle = Turtle.color
ctxt.beginPath()
ctxt.moveTo(Turtle.x, Turtle.y)
Turtle.x += n * Math.cos(Turtle.angle)
Turtle.y += n * Math.sin(Turtle.angle)
ctxt.lineTo(Turtle.x, Turtle.y)
ctxt.stroke()
ctxt.closePath()
}
back = function(n) { forward(0 - n) }
right = function(n) {
Turtle.angle += n * Math.PI / 180
}
left = function(n) { right(0 - n) }
clean = function(n) {
ctxt.clearRect(0, 0, canvas.width, canvas.height)
Turtle.x = canvas.width / 2
Turtle.y = canvas.height / 2
Turtle.angle = 0
Turtle.penDown = true
}
color = function(aColor) {
Turtle.color = aColor
}
// Register an event handler
move = function(func) {
_whenMove = function() {
clean()
func()
}
}
// Utility functions
mouseX = function() { return _mouseX }
mouseY = function() { return _mouseY }
_whenMove = null
_mouseX = 0
_mouseY = 0
canvas_onmousemove = function (e) {
var rect = this.getBoundingClientRect()
_mouseX = Math.floor(e.pageX - rect.left)
_mouseY = Math.floor(e.pageY - rect.top)
_watcher.innerHTML = "mouseX: " + _mouseX + " mouseY: " + _mouseY
source.innerHTML = "inspi(15, " + _mouseX + ", " + _mouseY + ")"
if (_whenMove != null) _whenMove()
}
// if (window.addEventListener) window.addEventListener("load", turtleInit, false)
</script>
<script type="text/javascript">
inspi = function(side, angle, inc) {
for (var i = 0; i < 720; i++) {
forward(side)
right(angle + inc * i)
}
}
</script>
<pre>
inspi = function(side, angle, inc) {
for (var i = 0; i < 720; i++) {
forward(side)
right(angle + inc * i)
}
}
</pre>
<pre id="source">
inspi(15, mouseX(), mouseY())
</pre>Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com3tag:blogger.com,1999:blog-8272979.post-26903825467411521662008-09-23T00:11:00.000-07:002008-09-23T00:12:12.817-07:00Ostranenie - Crossover between Art and Programming<p>It looks like that I have to say something at a camp next
week. So I trumped up the most easy topic for me, the art. For me, the
art is very common and familiar thing that I spent a lot of time to
discuss such matter in my youth. And more importantly, it is somewhat
strange topic for colleagues. I hope it will be fun.
<p>One of the most important functions in the art is ostranenie.
Ostranenie is a term coined by Russian critic Shklovsky,
which means looking a familiar things in unfamiliar ways to find a
unexpected side of the subject. For example, most surprising thing for
a student who learns a sketch first time was there are no outlines in
the world. Young kids often draw an outline to express the mom's
face. But reality is that a human brain extracts an outline from a
contrast of of light and shade.
<p>Also a programmer often faces ostranenie. A human tends to think based
on an intuition. But a computer only obeys logics, it never cares
about human's common sense or intuition. The conflict often cause
errors. But the errors give us precious ideas that we have never
noticed. Human beings have developed common sense and intuition
through the long history and culture, so it is very difficult to
perceive a difference between logic and intuition without a computer.
<p>We can regard the invention of computer in philosophy as the invention
of photograph in the history of art. The invention of photograph
provided an artist first different eyes beside human's. And it brought
Impressionism in 19th. Likewise, we met another kind of brain for the
first time by computers. No one knows what is born from there because
the history of computer is still young. But we can explore new
directions in terms of ostranenie.Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com6tag:blogger.com,1999:blog-8272979.post-54944570143728165452008-09-11T14:31:00.000-07:002008-09-11T14:32:47.901-07:00Chalkboard<a href="http://www.flickr.com/photos/propella/2848646517/" title="Chalkboard by propella, on Flickr"><img src="http://farm4.static.flickr.com/3038/2848646517_728c485d17.jpg" width="500" height="363" alt="Chalkboard" /></a>
<p>Chalkboard is my latest web authorizing tool for active essay. I have
just uploaded it here <a
href="http://tinlizzie.org/chalkboard/">http://tinlizzie.org/chalkboard/</a>.
I tested both Firefox and Safari. I know there are still a lot of UI /
technical issues though, I am sure that basic feature is enough for my
purpose, and I will keep it simple.
<p>My biggest concern at now is supporting Internet Explorer. I thought
it was not so difficult for such a simple web application. But
actually it was horrible! and I couldn't solve yet. I might go bad
direction though, I was really disappointed about different behavior
of layout. One can say that it is unnecessary to support various
platforms for such an experimental project. But I think it is
important because I hope it will get real users finally.
<p>When I had to decide a name of directory for this project. I named it
"chalkboard". I felt the spell was too long as a directory name, but
I'm comfortable about this naming now.
<h3>Here are features.</h3>
<p>The screen have three areas, editor, play area, and transcript. You
can write text or source code on the editor. Any text is executed as a
JavaScript program with [do it] or [print it] command. [do it] command
prints the answer on the transcript, and [print it] shows the answer
on the point of cursor. The play area provides a free space to
user. It is used any purpose, for example, you can make a drawing tool
to attach canvas element on it. See <a
href="http://tinlizzie.org/chalkboard/#Scribble">http://tinlizzie.org/chalkboard/#Scribble</a>.
<p>The Chalkboard includes a bunch of pages. Each page consists text and
source code. Sauce code is usually written on <pre> tag.
<p>All source codes written on <pre> tag in a page are invoked with
[run] from top to bottom. This is useful when you encounter unknown
page, and want to try at first. <pre> tag is used when the
project is called by includes function. See <a
href="http://tinlizzie.org/chalkboard/#Polygon">http://tinlizzie.org/chalkboard/#Polygon</a>
<p>You can make a new page to specify new name after hash mark of the URL
like http://tinlizzie.org/chalkboard/#NewPage. In this case, a page
named NewPage will be made.
<h3>Here are some design decisions.</h3>
<p>The editor allows only paragraph level editing. You can make a line
become h1 (header 1), p (paragraph), or pre (program), but you cannot
make a word become bold or italic. Link command is only exception case
(you can make a word become a link). The reason is web browsers have
different behavior on the editor component, and I don't want to
support each corner case. Rather than that, decided to provide minimal
set of features.
<p>Chalkboard uses IFRAME + editorMode property for the rich text
editor. There were another possibility. One is DIV + contentEditable,
and another one is FRAMESET. Those were pros and cons. I use IFRAME
simply because it was easiest way in Firefox and Safari to make
available this layout configuration, but I might change my mind.Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com0tag:blogger.com,1999:blog-8272979.post-46193982880336630212008-09-02T23:41:00.001-07:002011-06-30T14:54:51.646-07:00My personal history of Web Authorizing Tools (2)<h3>Tinlizzie Wiki</h3>
<p>Tinlizzie Wiki is a wiki written in Tweak. It uses OpenDocument Format
(ODF) as data format, and WebDAV as server.
<p>Although data format in StackWiki was Squeak specific binary, In
Tinlizzie Wiki existing common format is used. A part of reason why I
choose ODF was that it was a research project to find a possibility to
exchange eToys content among different platform. So it was necessary
to find platform independent and transparent format. ODF, especially
its presentation format, was quite close to my demonds which are a)
text based b) enable to embed graphics c) enable to use original
element d) internal and external link supported.
<p>A ODF file is just a zip archive which includes XML text and
multimedia binary files. And it is easy to extract image file in a
project by an another tool. Both embeded object and external resource
can be represented by common URL notation. And if necessary, new tag
for Tweak specific object can be used. For example, a project which
includes fully dynamic behavior written as Tweak objects can be viewed
on ordinary OpenOffice Org application, although dynamic feature would
in it be disabled.
<p>To export Tweak object to ODF as natural as possible, special care was
needed to save. It is not the best way to define a new tag for Tweak
specific object even though it is possible. It was preferable to map
from Tweak to ODF properly. For example, if a Book object in Tweak is
stored as a presentation within frame in ODF, the project looks
somewhat more normal even on other application.
<p>There is a issue how much detail information is needed to save an
object. For example, if a text is saved during its editing, whether if
position of the cursor should be saved or not?? There are two strategy
in terms of implementation. One is to save everything except specified
status (deep copy), another one is to save only specified
status. Tinliziie Wiki adopted the latter one although Squeak and
Tweak native serialize mechanism were the former.
<p>Saving only specific status has two disadvantages. a) A user might
expect to save everything including minor information because
combining arbitrary objects in even any peculiar way is possible in
Tweak. b) Each new widget needs to implement each exporter. But
"saving everything by default" strategy has a problem of compatibility
because even just one change of variable name makes trouble for old
version. Especially it is problematic for sharing in Internet. So I
din't choose this strategy.
<p>WebDAV is used as the server. Both StackWiki and Tinlizzie doesn't
need server side logic, but simple storage is required. WebDAV is the
best option for that matter. Even version control system can be
plugged in the server with Subversion modlule in Apache for free,
<h3><a href="http://metatoys.org/propella/js/workspace.cgi/Home">Javascript Workspace</a></h3>
<p>Javascript Workspace is a simple web application. It uses bare
Javascript on client, and Ruby CGI on server. It behave like a
Smalltalk Workspace, and the contents are managed same manner as Wiki.
<p>Let me make sure about workspace again. Workspace is a text editor,
and it has two additional commands "do it" and "print it". Do it
command envokes a source code selected by user, and print it command
output the result into cursor position. The function is similar to
REPL shell on dynamic language, but the use case is slightly
different. A typical way to use workspace is as an explanation of
program. An author writes example source code inside the
documentation, so that a user can try actual function while reading a
text. Namely, REPL is two ways dialog between a machine and a human,
but workspace is tree ways conversation among a machine, an author,
and a user.
<p>Workspace is indispensable tool for Smalltak though, which doesn't
mean only for Smalltalk. It would be nice if there is a workspace for
Javascript language. This was the initial motivation of Javascript
Workspace. And then, it was a natural consequence that Wiki was used
to save the content because Javascript lives on web browser
intrinsically, and there are no way to save to local disk.
<p>During the development, however, I realize that it can be more than
just a workspace in terms of media. Javascript workspace has only
simple user interface, which includes a couple of buttons and one big
text area. Even there are no hyper link nor emphasized text. But
variety things can be happend from such minimal configuration by
source code. Hyper link is enable to make from location property, rich
text can be shown to modify DOM tree, and even game can be made to set
up event hander. Source code can do everthing.
<p>Just one textbox on a web page is a very radical idea. This is
completely opposite direction to current trend of rich internet
application. Web application consists with number of hidden functions
these days, but Javascript Workspace can not have any invisible
information. Everything what it does is shown to you as source code
entirely on the screen. Javascritp Workspace looks like dangerous as
it runs any Javascript code, but in fact, it is a quite safe system.
<p>The idea of uset interface of Javascript Workspace is adopted to
OMeta/JS.
<h3>TileScript</h3>
<p>TileScript uses Scriptaculous as GUI library and WebDAV for server
storage. JSON is used for its data format.
<p>A TileScript document consists with one or more paragraphs, and a
paragraph is either Javascript code, "tile script", or HTML
expression. A tile script is set of tiles, which each tile represents
some syntactical element in a programming language. A user can connect
tiles to construct a program with drag and drop. This is an easy way
to make a program avoiding syntax error. Javascript is used to
represent more complicated program than tile script. And HTML is used
as annotation. It can be seen as rich version of Javascript Workspace.
<p>The initial motivation of TileScript was to remake eToys on the web
environment. The research had got started by making tile available on
web browser. I considered to use Lively Kernel (SVG), but it was
unnecessary if Table element in HTML DOM is used as
tile. Scriptaculous is used to keep the source code simple.
<p>After tile is ported, then next step was eToys environment itself
which includes event handling, scheduling, and bitmap animation,
etc. But those issues seemed too difficult for nature of web document.
<p>Flow layout, which actual position of document elements are
dynamically changed by reader's browser environment, is a significant
feature of web. An author don't specify concrete position of elements,
but rather care about logical structure. And then, a part of document
which can not be shown on the screen is accessable by a vertical
scrool bar.
<p>On the other hand, eToys provides page layout, which size and position
of elements is fixed, and presume particular screen size. Althogh, it
is quite fit as a metaphor of physical paper, and best for a graphical
environment like eToys, but clumsy operation like zooming and
horizontal scrool is required.
<p>Because ultimate goal of TileScript was not just reinventing eToys,
but investigating further possibility, flow layout is adopted to
TileScript. But still absolute coordination can be supported in form
of embeded object even in flow layout. TileScript provides variable
watcher like eToys, but those widget is also layouted along with flow.
<h3>And then</h3>
<p>Now I'm working on next version of Javascript Workspace, which
especially its target application is Active Essays. Our group have
found that Javascript is quite reasonable tool to show some ideas of
computer science. One reason is language's simplicity, and other one
is easiness of collaboration. We have a lot of new ideas about
programming language, and some of the part should be simple enough to
understand even by junior high student. I believe my tool can be used
to explain such ideas.
<p>The problem is any project intoroduced here is not intended for real
use, rather just for demo or prototype of further real development. So
it is not be so useful as it looks because it includes too
experimental aspect, too fragile, or too slow. Now I'm thinking that
it is not bad idea if I make somewhat stable version of them. Even it
might not have exotic feature like tile script, but only basic and
simple functions are enough to play with everyone. I really like my
first idea of Javascript Workspace, which has only simple text. I
admit it is extreme, so next version might support emphasized text and
inline image (basic HTML elements) at least.Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com2tag:blogger.com,1999:blog-8272979.post-12289750229622674312008-09-02T00:10:00.000-07:002008-09-02T00:11:09.639-07:00My personal history of Web Authorizing Tools (1)<p>I have been facinated by the idea of combining web authorizing and
programming even before I realize it is called Active Essay. Actually
I made a numbers of projects along with the idea. Here is a short
story of my side.
<h3>Scamper Workspace</h3>
<p>Scamper Workspace is a extention for Scamper, a web browser written in
Squeak. It runs a Smalltalk code on any web page with simple
operation.
<p>I often write a tiny source code in Squeak on my blog. And it is
natural that you want to run the code without any effort. Usually, you
might have to copy and paste from web browser to Squeak. However,
although Squeak has already a web browser named "Scamper", why do we
need such clumsy way? What's wrong if a web page is just a text as
same as other Squeak's text object, and if you can use full features
which Squeak IDE has on it. Scamper has very limited as a web
browser, but it is just O.K. to examine a code on blog. Only missing
thing is a direct way to execute code on web page.
<p>"No Application" is Squeak's original motto. Squeak consists with a
number of objects that they have each different tiny functions, and
those are connected naturally. In that sense, there are no need of
"Application" because application is just an artificial boundary. So
it seems to me natural to add Workspace menu into Scamper.
<p>Because all necessary code is already available in Squeak image. The
implementation was very easy. However the result was surprisingly
attractive and profound. Thoru Yamamoto made a lot of contents for
Scamper Workspace and each of them are so exciting.
<p>Typical page written for Scamper Workspace consists with a short story
and a couple of codes. A reader would executes the codes while reading
a story. This format is very effective when the story is to explain
how to make a graphical program in Squeak. Especially the fearure is
emphasized when a page consists only text and source code. Even it
lookes if it were 1995's website, it make large variety of effects if
you run the code. I would say that it could be another possible
evolution path for the Web.
<h3>StackWiki</h3>
<p>StackWiki is a multimedia authorizing tool written in Squeak. Document
is saved as original binary format with Swiki Server.
<p>I made StackWiki inspired by Zest and Marmalade. Zest is WYSIWYG
authoring tool like Wiki uses local disk, which allows you to make
link to other page, and dynamic content in Smalltalk language. Above
all, StackWiki emphasis more features in HyperCard and Wiki.
<p>A StackWiki project consists with one or more pages. In WWW, nomally
relationship between pages is maintained only hyper link, but there is
no structure like hierarchy or order. Some websites attempt to show
such structure with navigation link.
<p>Structure among pages helps user to know a point within the context
though, it often makes UI complicated. Addition to historical
navigation, forward and backword navigation is needed if pages have an
order. Above all, if there is hierarchy, three dimensional navigation
would be necessary, In StackWiki, only foward and backword structure
is used.
<p>With background, you can put together similar structures in multiple
place in one. StackWiki only allows one background, although HyperCard
could handle more. Background is implemented as a special "background"
page. If you add something onto background page, the element are shown
same place behind other elements in all pages.
<p>Here is another interesting trade off. How complicated background is
needed? Background can be seen as a special version of macro. Macro
is a generic term to represent common structure among document. Macro
is very useful to reduce redundancy and to improve maintenance
factor. However, it is easy to make too complicated macro which
includes macro of macro. In end user's point of view, background can
be better than full macro.
<p>Each StackWiki's page is stored as a binary format in Swiki
serer. Although, Swiki is itself web application, it is used just as
file upload feature. StackWiki doesn't use any web standard except
HTTP transport to save data. It doesn't so good attitude in terms of
data transparency. But it makes the development so quick that it took
only three days to implement it.Takashihttp://www.blogger.com/profile/00275489652316753838noreply@blogger.com3