A gentle introduction to Hatter

Version 0.1, 2012-02-21.

Many (two) people have complained that they haven't grasped how to program in Hatter by reading the language standard. This is probably because it is badly written, even though it is fairly thorough. Like all good standards should be. Anyway, to ameliorate this problem, I have decided to write this "gentle introduction" to Hatter.

Hats

The basic program unit in Hatter is, not surprisingly, the hat. You drop pieces of data into a hat, and take pieces of data out of them. Just like real hats. You do this with data movement commands:

foo<-2               drop the number 2 into a hat named 'foo'
2->foo               the same thing

The pieces of data you drop into a hat are stored in an internal stack. All data movement takes a datum from the top of the stack of one hat and drops it onto the top of the stack of another hat. Numeric constants (like the 2 in the examples above) behave like hats that contain infinitely many copies of the number in question (you can take as many 2s as you want from the hat called 2).

You can express many movements in a single expression (a movement stream):

a->b->c                 take a datum from 'a', drop it into 'b';
                        take a datum from 'b', drop it into 'c'.

a<-b<-c                 take a datum from 'b', drop it into 'a';
                        take a datum from 'c', drop it into 'b'.

a->b<-c                 take a datum from 'a', drop it into 'b';
                        take a datum from 'c', drop it into 'b'.

As you can see, movement streams are executed by taking every two adjacent hats and executing the operation between them (i.e., a->b<-c is a->b, b<-c).

If hats were limited to accumulating elements, they wouldn't be particularly useful. To do any computation, you must associate magic with the hat: movement streams that are executed whenever a datum is dropped into the hat, and whenever an attempt is made to take a datum from the hat. A hat declaration looks like this:

hat foo:
  init initmagic
  in inmagic
  out outmagic

inmagic is the movement stream to be executed after a datum is dropped into the hat, and outmagic the the movement stream to be executed before a datum is taken from the hat. initmagic is a movement stream to set up the initial state of the hat stack, and is run before the main program starts.

Any magic can be omitted. If all magic is omitted, the hat does nothing and behaves like a stack.

In hat magic, @ refers to the hat stack. Magic runs in the bottom of the hat, though, so you see the stack from the bottom (i.e., you take the elements from @ in the same order they were dropped into the hat). You can use additional stacks @1, @2, etc. for temporary storage.

All operations are performed by hats in Hatter. Take for example addition: There is a hat called add. You drop into it all numbers you want to add together, and take the sum out of it.

Magic is limited to a single movement stream. This is probably the hardest part of programming in Hatter.

Simple examples

There is a standard hat succ, which takes a number (n) and gives back its sucessor (n+1). The following hat definition:

hat foo:
  in @->succ->@

says: when a number is dropped into foo, take the number from the stack, drop it into succ (@->succ), take the result back, and drop it into the stack (succ->@). So this hat just increments the number it is given.

hat bar:
  in @->succ->@->succ->@

This hat "dips" the number it gets twice into succ: if you drop a 2 into it, it will drop it into succ, take back a 3, drop it into succ again, take back a 4, and drop it into @. So this hat adds two to the number it is given. (The magic of this hat could be rewritten as @->succ->succ->@, without the intermediate @.)

Sometimes you need to use the same datum twice. For this, you use the cornucopia hat, horn: you drop a number into it, and you can take back as many copies of the number as you wish. For example, this hat squares the number it gets:

hat square:
  in @->[horn->mul]->mul->@

That is: take a number from the stack, drop it into horn, take a copy and drop it into mul, take another copy and drop it into mul, and take the product and drop it into @. Here we have something new: the brackets allow one to group movements.

[a->b]->c                      a->b, then a->c
[a->b]->[c->d]                 a->b, then a->c, then c->d

That is, first run what is inside of the brackets on the left side of the movement arrow, then use the leftmost element inside the brackets as the operator for the arrow, then run what is inside of the brackets on the right side of the arrow. The backward arrow is slightly different: it first evaluates both arguments, then executes its movement:

[a->b]<-[c->d]             a->b, then c->d, then a<-c

You may find this confusing. This is probably due to the fact that it is. Just re-read the last paragraphs until you feel dizzy, and then proceed.

Now for a slightly more complicated example: we will write a hat that receives a, b, and c, in this order, and computes b*b - 4*a*c.

hat delta:
  in ~4->[[mul<-@]<-[@->@1]]->[add<-[mul<-[horn<-@1]->mul]]->@
  

Let's proceed by parts. First we compute -4*a*c:

~4->[[mul<-@]<-[@->@1]]->...
The first thing this does is to move -4 into mul (the leftmost hat named in the bracketed group): ~4->[[mul.... Then we take a from @ and move it into mul ([mul<-@]). Then we take b from @ and move it into @1, a temporary stack ([@->@1]). Then we take c from the stack and move it into mul ([[mul...]<-[@...]]). At this point, we've dropped ~4, a and c into mul, and saved b for later use. Finally, we take the result (-4*a*c) from mul ([[mul...]...]->...), and give it to the second part of our expression:
...->[add<-[mul<-[horn<-@1]->mul]]->@

Here we take the result computed earlier (-4*a*c), and drop it into add (...->[add...). Then we compute b*b:

[mul<-[horn<-@1]->mul]

That is: we take @1, which is b, and drop it into the cornucopia hat ([horn<-@1]). Now we put one copy of b into mul ([mul<-[horn...), and then another copy again into mul ([horn...]->mul). Finally, we take the result (b*b) from mul and drop it into add, which was waiting with the result of -4*a*c all along:

...->[add<-[mul...

In a last deep breath, we move the result from add, which now contains (-4*a*c) + (b*b), back to the stack ([add...]->@), where it can be taken by some other hat, which will surely do something important and useful with it.

That's enough for today, folks. Go outside for a while, then proceed.

[to be continued]


Copyright © 2012 Vítor Bujés Ubatuba De Araújo
The content of this site, unless otherwise specified, can be freely used, with or without modifications, provided that the author is mentioned, preferably with the URL of the original document.