Wooden Half Adder Video

*UPDATED* New half adder video is released!

A 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.

First Passage

ARTCOURT Gallery Tenmabashi 1-8-5, Kita-ku, Osaka 530-0042 Japan

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

• December 15 - 26, 2009
• Gallery Hours: 11:00 - 19:00 ( - 17:00 on Saturdays) Closed on Sundays

• Event : Artists Talk Show
• Saturday, Dec.19, 14:00 - 15:30 (*15:30 - 17:00 Reception)

Wooden half adder

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.

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.

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.

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.

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.

• 0 + 0 = 0 0
• 0 + 1 = 0 1
• 1 + 0 = 0 1
• 1 + 1 = 1 0

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(¬).

• C = A ∧ B
• S = A xor B = ¬(A ∧ B) ∧ ¬(¬ A ∧ ¬B)

Finally, I constructed parts along with this formula. I used gears as NOT operator.

1 + 1 = 1 0	1 + 0 = 0 1	0 + 1 = 0 1	0 + 0 = 0 0

An Assembler for AVM2 using S-Expression

These 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.

Overview

ABCSX is an assembler and disassembler for the ActionScript Virtual Machine 2 (AVM2) [1] 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 [4]) are shown.

;;;; 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 ())))))

// A "Hello world World!" program in abcasm
function hello():*
{
    getlocal 0
    pushscope
    findpropstrict print
    pushstring "Hello, World!!"
    callproperty print (1)
    returnvoid
}

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 ((package "") "print"). 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.

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.

;;;; 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 ())))))

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).

Background

One of goals of the STEPS project [3] 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.

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.

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.

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.

Usage

Command line tool

A version of ABCSX is publicly available on the github repository [2]. It includes command line tools run on PLT-Scheme. There are also example programs at examples/ directory. The assembler and disassembler use same file format and the assembler asm.ss can read an output file generated by disassembler dump.ss.

asm.ss filename.sx

Generate an ABC binary file from ASM-form or ABC-form. The output file name is filename.sx.abc.

dump.ss [-abc] filename.abc

Disassemble an ABC binary file. The output is printed to stdout. If -abc option is specified, ABC-form is chosen as output format.

runasm.sh filename.sx

Assemble ASM-form or ABC-form and execute it by avmshell. It requires avmshell installed. Avmshell is included in Tamarin VM's source tree [4].

swf_abc.erl width height classname abcfile.abc

A helper program to generate a flash file from an abc file. It requires Erlang.

Function

(write-asm list port) procedure

Assemble ASM- or ABC-form to a binary stream.

(read-asm port) procedure

Disassemble a binary stream to ASM-form.

(from-asm list) procedure

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

(to-asm list) procedure

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.

Data Type

ABC's data is expressed as scheme expression in ABCSX. In ASM-form, data conversion has subtle context dependency in code-subsection.

• integer - An integer value in Scheme is converted to ABC integer value depend on the context.
  • int (s32) - In code-subsection, an integer is converted to a signed 32 bit integer if the opcode requires integer e.g. pushint.
  • uint (u32) - In code-subsection, an integer is converted to a unsigned 32 bit integer if the opcode requires integer e.g. pushuint.
  • u30 - An integer is converted to a unsigned 30 bit integer in ABC anywhere else.
• double (d64) - A floating point number value is converted to a 64-bit double precision IEEE 754 value.
• string - A string is converted a string value in ABC.
• namespace - Some list expressions are converted to namespace values in ABC. The format is (kind string). For example, (package "org.vpri") is converted to a package namespace named "org.vpri".
  • Namespace - (ns string) is converted to Namespace
  • PackageNamespace - (package string) is converted to PackageNamespace
  • PackageInternalNs - (internal string) is converted to PackageInternalNs
  • ProtectedNamespace - (protected string) is converted to ProtectedNamespace
  • ExplicitNamespace - (explicit string) is converted to ExplicitNamespace
  • StaticProtectedNs - (static string) is converted to StaticProtectedNs
  • PrivateNs - (private string) is converted to PrivateNs
• 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. (ns_set 1).
• multiname - Some list expressions are converted to multiname (symbol) in ABC.
  • QName - (namespace string) is converted as QName e.g. ((package "flash.display") "Sprite"))
  • RTQName - is not supported.
  • RTQNameL - is not supported.
  • Multiname - ((ns_set integer) string) is converted as a Multiname e.g. ((ns_set 1) "addChild")
  • MultinameL - is not supported.

Syntax

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.

ASM-form

(asm [ns_set-section] method-section [metadata-section] [instance-section] [class-section] script-section)

ASM-form begins with a symbol asm, and contents are followed. ns_set-section, instance-section, and class-section are optional.

ns_set-section

(ns_set (ns_set namespace ...) ...)

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.

Ns_set-section begins with a symbol ns_set and a list of ns_set_info is followed. A ns_set_info begins with a symbol ns_set 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 (ns_set 1).

method-section

(method (signature-subsection code-subsection) ...)

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 (method 0).

signature-subsection

(signature (return_type multiname) (param_type (multiname ...)) (name string) (flags integer) (options (option...)) (param_names (multiname ...)))

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.

code-subsection

(code (instructions...))

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:

([offset-number] inst-name args ...)

offset-number is optional and used just as a place holder. It can be a integer or symbol _. ABCSX's disassembler put a byte offset number at this place, but the assembler ignores it.

metadata-section

(metadata (metadata_info ...))

Metadata-section describes a list of metadata entries.

instance-section

(instance (((name multiname) (super_name multiname) (flags integer) (interface (multiname ...)) (iinit method) (trait (trait_info ...)) ...)))

Instance-section describes a list of class definitions. Class members are defined by a list of trait_info.

class-section

(class (((cinit method) (trait (trait_info...))) ...))

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.

script-section

(script (((init method) (trait (trait_info...))) ...))

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.

trait_info

Trait_info defines a fixed property of an object, class, or method. ABCSX only supports Trait_Slot and Trait_Class.

Trait_Slot

((kind slot) (name multiname) (slot_id integer) (type_name multiname) (vindex integer) (vkind integer) (metadata (metadata_info...)))

Trait_Slot defines a named slot in the context.

Trait_Class

((kind class) (name multiname) (slot_id integer) (classi class) (metadata (metadata_info...)))

Trait_Class defines a named slot with a class in the context.

metadata_info

((name string) (items (((key string) (value string)) ...)))

Metadata_info defines an entry including arbitrary key/value pairs.

Current Status

Currently, only major elements in AVM2 are implemented.

• All primitive data types are implemented.
• 75 instructions (about a half of the whole instruction set) are implemented.
• Only QName (Qualified Name) and Multiname (Multiple Namespace Name) are implemented.
• Optional parameters or parameter names are not implemented.
• Trait_Method, Trait_Getter, Trait_Setter, Trait_Function, or Trait_Const are not implemented.
• Exception is not implemented.

Example

As a complete example, A GUI version of "Hello World!" program is shown with commentary. This file is available at examples/textField.sx on the source tree.

(asm
 (ns_set
  ((ns_set (package "") (package "flash.text"))))

An ASM-form begins with a symbol asm, and a ns_set-section follows if necessary. This example declare one namespace set including package namespaces "" and "flash.text" as (ns_set 1). 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.

 (method
  (((signature ((return_type *) (param_type ()) (name "")
                (flags 0) (options ()) (param_names ())))
    (code
     ((returnvoid))))

The first method is referred as (method 0). It is used as a class initializer in the class-section, but nothing to do in this case.

   ((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))))

The second method is later used in the instance-section as class Hello's constructor. It builds an instance of flash.text.TextField and set "Hello, World!" to the property named text. Finally, the text field is added to this (Hello) object.

   ((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))))))

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 newclass instruction.

 (instance
  (((name ((package "") "Hello"))
    (super_name ((package "flash.display") "Sprite"))
    (flags 0)
    (interface ())
    (iinit (method 1))
    (trait ()))))
 (class (((cinit (method 0)) (trait ()))))

Instance-section and class section define classes. In this case, A class named Hello is defined as a subclass of flash.display.Sprite. 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 swf_abc.erl's third argument does this task.

 (script
  (((init (method 2))
    (trait
     (((kind class)
       (name ((package "") "Hello"))
       (slot_id 1)
       (classi (class 0))
       (metadata ()))))))))

Script-section defines the startup script and predefined named slot.

References

• [1] ActionScript Virtual Machine 2 (AVM2) Overview. http://www.adobe.com/devnet/actionscript/articles/avm2overview.pdf
• [2] ABCSX github repository. http://github.com/propella/abcsx
• [3] Steps Toward the Reinvention of Programming (First Year Progress Report). http://www.vpri.org/pdf/tr2007008_steps.pdf
• [4] Tamarin Project http://www.mozilla.org/projects/tamarin/

A simple boolean logic table generator in Javascript

http://languagegame.org/pub/booltable/booltable.html

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.

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.

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.

Here are a couple of examples to link boolean tables:

• A or B
• A implies B
• (P=>Q)*(Q=>R)=>(P=>R)

Lazy list and Data flow in Squeak

Introduction

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.

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.

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.

SICP is a good tutorial and I found further discussions in SRFI-40 and SRFI-41. Ruby has good implementation similar to SRFI-41. And even Squeak has two implementations (LazyList and LazyCollections)! And here is my story.

Natural numbers

You can download a demo image from LazyList.zip or current source code from Collections-Lazy-tak.5.mcz. 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.

This is an expression to make natural numbers with LazyList.

list := LazyList nat.

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.

And when you open a list at the explorer (the right window), values of public accessors head and tail are shown, and also the inspector is updated. The first element 1 is made only because someone send head message. And you can get further numbers with clicking tail accessor. Note that while explorer triggers the list, inspector is inert so that you can freely observe internal behavior of the list.

You can do this by a program. Message head answers the first element of a list, and tail answers following list. This is same as CAR and CDR pair in lisp. Many other methods are defined e.g. take: returns a LazyList including first n elements, and contents convert LazyList to Array.

list head. "=> returns 1"
list tail. "=> returns LazyList .."

(list take: 10) contents. "=> #(1 2 3 4 5 6 7 8 9 10)"

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.

list select: [:e | e odd].

Define a new LazyList

Most useful way to construct a new lazy list would be using followedBy: 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.

1 followedBy: (2 followedBy: (3 followedBy: LazyList nil))
"=> same as LazyList withAll: #(1 2 3)"

You can define natural numbers using followedBy: like this.

nat := 1 followedBy: [nat collect: [:e | e + 1]].

It seems very strange! But please be relax. The first element of the list is obviously 1. How about the second? collect: is sometimes called as map function in other languages, and nat collect: [:e | e + 1] answers a LazyList with all element is just larger by 1 than nat itself. Therefore the sequence is generated by recursive fashion. How clever!

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, ...

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.

nat := 1 followedBy: [nat + 1].

It reminds me an ugly assignment expression with side effect.

x := x + 1.

This is ugly because it looks like an equation but it is not. x is never equal to x + 1! 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, nat := 1 followedBy: [nat + 1] is similar enough to x := x + 1 yet, it is actually an equation. This is a significant coincidence, isn't it?

Iteration, Data flow, Lazy list, and Polymorphic functions

One of the problems in x := x + 1 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.

x1 = 1 --- some initial number
xn = xn - 1 + 1

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 xn - 100.

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).

x1 = 1 --- some initial number
xn + 1 = xn + 1

It makes the relationship between an iteration x := x + 1 and a lazy list more clear. This iteration can be converted a lazy list definition directly.

nat := 1 followedBy: [nat + 1].
      ~~~            ~~~~~~~~~
    x1 = 1;        xn + 1 = x + 1

I know this discussion is still rough. You can find better discussion from Lucid. However, my theory is that data flow structures (mathematical iteration) can be expressed by lazy lists and polymorphic methods without special language.

Here is another example of definition of a lazy list in iterative way to compute Fibonnaci numbers. next is a synonym of tail.

fib := 1 followedBy: [1 followedBy: [fib + fib next]].

This corresponds next mathematical equations.

fib1 = 1
fib2 = 2
fibn + 2 = fibn + fibn + 1

Simulations

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!

Y := 400 followedBy: [Y + Speed next].

Speed := 0 followedBy: [Y > 0 whenTrue: Speed - 1
                             whenFalse: Speed negated].

Morphic part of this demo used a special morph named ListPointer that worked as an interface between LazyList and Morphs.

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.

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!

A complete example of generating a sound in Flash with SampleDataEvent

Flash version 10 has significant feature about audio, SampleDataEvent. 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 how to make actionscript 3 play generated pcm wave data 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!

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.

There are a couple of tricks you might trap.

• 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
• Some documentation might use Event.SAMPLE_DATA, but this is not true.

Generated SWF file: http://languagegame.org/pub/SineSound.swf

A Prolog In Haskell

Prolog In Haskell

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.

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 http://darcs.haskell.org/hugs98/demos/prolog/. I think this is a great Haskell program, but its too difficult to me. Rewriting it as my level would be a good exercise.

Data structures

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.

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

I used Parsec as a parser, and defined some data structures.

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)]

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 Struct "apple" [].

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 Struct "mortal" [Var "X" 0] :- [(Struct "man" [Var "X" 0])]. 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.

-- 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])

Using this functions, now "mortal(X) :- man(X)" is written as s"mortal" [w"X"] :- [s"man" [w"X"]] . It is much better, isn't it?

Unification

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.

---- Unification ----

type Substitution = [(Term, Term)]
true = []

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, [(w"X", w"apple"), (w"Y", w"orange")] ). 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.

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

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.

	Equation	Substitution(solution)
1	Y = banana, X = Y
2	X = Y	Y = banana (append)
3	X = banana (apply: Y = banana)	Y = banana
4		Y = banana, X = banana (append)

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;

• No Answer : Nothing
• Always true (like apple = apple) : Just true (true is a synonym of empty list [])
• Substitution found : Just [X = some answer...]

-- 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')

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.

Solver

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.

• Goals (AND relationship) : are terms which should be solved.
• Branches (OR relationship) : are options which might have a solution

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?

• If branch returns [] <--- this is failed
• If branch returns [ [some goals] [some goals] [(empty)] <--- this is succeed! ]

The goal of find function is traverse all of goals to find whether if it is true or false.

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

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.

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

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 http://github.com/propella/prolog/tree. Someday I might write some of interesting topics in the program...

Learning Erlang and Adobe Flash format same time part 2

I have already written most important part about SWF format and Erlang's bit syntax at previous post. 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.

In the previous example, I only made three control tags:

• End (Tag type = 0)
• ShowFrame (Tag type = 1)
• SetBackgroundColor (Tag type = 9)

Here, I introduce you two additional tags,

• DefineShape (Tag type = 2) defines a vector graphics, and
• PlaceObject2 (Tag type = 26) shows the graphics to an actual screen.

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.

% 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}]
        }}}}.

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.

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.

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.

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>>).

shape_with_style/1 is used to construct SHAPEWITHSTYLE structure in the specification.

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].

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.

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)].

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

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

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.

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).

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.

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

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.

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.

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

I uploaded final program http://languagegame.org/pub/swf.erl.

Learning Erlang and Adobe Flash format same time

Since Luke Gorrie encouraged me to learn Erlang, I have been playing with a bit with the language. One of the most attracting points is bit syntax. 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!

$ 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">>

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, the SWF specification is now free and everybody can write a flash editor by themselves.

First of all, I chose scripting style because I'm too lazy to wait for a compiler. And I start a shell bang line.

#!/usr/bin/env escript
%% -*- erlang -*-
%%! debug verbose

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.

% 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}]}.

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.

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.

main(_) ->
    Filename = "simple.swf",
    {ok, S} = file:open(Filename, [binary, write]),
    file:write(S, swf(spec())),
    file:close(S).

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.

% 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>>.

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 patterns. Thanks to to tuples and patterns, I don't have to remember an order of arguments. It looks like keyword arguments 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.

A list comprehensions 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.

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

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.

% 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>>.

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.

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.

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

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.

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|

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).

% 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].

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.

% 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)).

I uploaded an entire program at swf_simple.erl 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.

• The SWF Specification: http://www.adobe.com/devnet/swf/pdf/swf_file_format_spec_v10.pdf