Hatter is an esoteric programming language devised by Vítor De Araújo in a moment of glory on May 4th, 2009 and finished about nine months later. It is a hat-oriented language (HOL), which means that all computation is represented as dropping and taking data into/from hats. Hats are objects consisting of an argument stack and descriptions of data movements (called 'magic') associated with dropping and taking elements into/from it. Hats can also have other stacks for internal use. Data is generally moved, not copied. A hat can be called recursively, but all instances of a hat share the same argument and internal stacks.
The commands for data movement are:
| a->b | Take the topmost datum from a's argument stack and drops it into b |
| b<-a | The same thing. |
Data movements can be composed into a stream of movements. The movements are executed from left to right. For example, a->b<-c->d is interpreted as the sequence of movements a->b, b<-c, c->d. Movements can be grouped with brackets. The semantics is:
| [a->b]->[c->d] | a->b is evaluated, then a->c, then c->d |
| [a->b]<-[c->d] | a->b is evaluated, then c->d, then a<-c |
That is, in GROUP1->GROUP2, GROUP1 is evaluated, then the topmost datum from GROUP1's leftmost hat is dropped into GROUP2's leftmost hat, and then GROUP2 is evaluated. In GROUP1<-GROUP2, GROUP1 is evaluated, then GROUP2, then the topmost datum from GROUP2's leftmost hat is dropped into GROUP1's leftmost hat.
Data is always moved, not copied, from one hat to another. The only exception is the builtin cornucopia hat, horn, which produces as many copies as desired of the last element that was dropped into it. Since this hat is shared by all hats in a program, data copying is somewhat contrived in Hatter.
The only data type present in Hatter is an integer of a fixed size (usually 32 bits). Standard hats always interpret this data as unsigned, but a hat is free to interpret this data in any way.
A numeric constant behaves as a hat that always yields the corresponding value. Data dropped into a numeric constant is lost. The two's complement of a number is represented as ~ followed by the number.
Each hat has a unique identifier, called 'hatid'. The hatid of a hat is represented by \ followed by the hatname. Note that ~ and \ are compile-time operators. Numeric constants are not true hats and don't have a hatid.
Comments are introduced by the word WTF and extend to the end of the line. They must either occur at the beginning of a line, or after whitespace.
Pragmas are compile-time directives that control the behavior of the compiler or runtime environment. The syntax is as follows:
!pragma_name [args...]
The only standard pragma is !use LIBRARY, which will make the hats declared by LIBRARY available to the program; it raises an error if the library does not exist. An implementation may provide other pragmas. It is recommended that an implementation support the !string pragma, which is explained in the appropriate section.
The syntax for declaring a hat is as follows (newlines and indentation are optional):
hat HATNAME: init INIT_MAGIC in IN_MAGIC out OUT_MAGIC
This creates a hat with the specified name, and the specified magic to be executed when the hat is initialized, when data is dropped into the hat, and when data is taken from the hat. Note that the magic must consist of only one movement stream. Any of these magics may be omitted; if all magic is omitted, the hat is unreactive and behaves like a stack.
Initialization magic is executed sometime before the first data movement operation involving the hat. It should only change the internal state of the hat, and should not depend on other hats. The results of using other hats in the initialization magic are undefined and likely to fail miserably.
The input magic is executed whenever a datum is dropped into the hat. If the magic attempts to read more data than there is available in its argument stack, its execution state is saved and execution goes back to the point where the hat was called. When more data is dropped into the hat, the execution of its input magic resumes from the saved point.
The output magic is executed whenever there is an attempt to take data from the hat. It is executed before the datum is taken. If the hat fails to provide a datum for output, the program terminates with an error. If it attempts to read more data than is available from its argument stack, the program also terminates, since execution of the calling hat cannot be resumed if the called hat fails to provide a value for the movement operation that called it.
A hat's argument stack is available through the special hat @. This stack is seen from below by the hat, i.e., the arguments are read in the same order as they were dropped. The hat can also have other internal stacks, named @1, @2, and so on. They need not be declared before use. Reading from an empty stack terminates the program with an error.
If a hat attempts to take or drop data from/into itself, directly or indirectly (by some hat it used, or some hat these other hats used, etc.), a new instance of the hat will be run. Note, however, that all running instances of a hat share the same stacks; they only differ in their execution point.
All runtime operations are provided by hats (except data moving, of course). The standard hats must be provided by every implementation of Hatter, and they guarantee that the state of other hats will be the same before and after they are used (although they may use other hats in their execution). An implementation is allowed to catch fire if any of the standard hats is redefined.
In this section, the notation foo(a,b) means dropping a and then b into the hat foo and taking the result(s).
These are the core operations of the language.
| pred(n) | Predecessor of n: yields n-1. |
| succ(n) | Sucessor of n: yields n+1. |
| horn(x) | The cornucopia: yields x, and the result can be taken as many times as desired. |
| if(t,x,y) | If t is non-zero, yields x; otherwise, yields y. |
| apply(h) | Higher-order hat: after a hatid is dropped into it, behaves like the corresponding hat. |
| nop | The no-operation hat: discards any value dropped into it, always yields 0. |
pred(0) yields the greatest unsigned integer available in the implementation; succ(pred(0)) is 0. Taking from pred without dropping an argument will yield the predecessor of the last number yielded (i.e., the result will be one unit less each time); likewise for succ. If pred and succ have never received an argument, they will behave as though 0 had been dropped. Taking from if with not enough arguments will raise an error. If horn has never received an argument, taking from it raises an error.
The nop hat is guaranteed to have the hatid 0.
apply is special compared to other hats: after dropping a hatid into it, execution continues as though the corresponding hat itself had been substituted for apply. Sucessive calls to 'apply' in other points of the code are unaffected. Thus, apply can be seen as a keyword or operator.
These are hats that can be implemented using the primitive hats, but are provided for convenience (!). An implementation may implement them as builtin hats for performance reasons. Here, "true" means yielding a non-zero value (generally 1, but not necessarily). "Iff" means "if and only if".
| equal(...) | True iff all values dropped are equal. |
| less(x,y) | True iff x is less than y. |
| add(...) | Yields the sum of all numbers dropped into it. |
| mul(...) | Yields the product of all numbers dropped into it. |
| div(x,y) | Yields the quotient of the division of x by y. |
| mod(x,y) | Yields the remainder of the division of x by y. |
| neg(x) | Yields the two's complement of x. |
| and(...) | Logical and: true iff all values dropped are non-zero. |
| or(...) | Logical or: true iff at least one of the values dropped is non-zero. |
After taking the result of these hats, their internal state is reset: add and or will indefinitely yield 0, mul and and will indefinitely yield 1, and the other hats will raise an error if used without dropping enough arguments into them. equal with one argument is true.
These are hats that implement interaction with the external environment. There is currently only one such hat.
| stdio | When a value is dropped into it, it is interpreted as a Unicode codepoint and the corresponding character is printed to stdout. When there is an attempt to read from it, a character is read from stdin, and the corresponding Unicode codepoint value is yielded. If end-of-file is encountered, yields ~1. |
The execution of a Hatter program begins with a hat called main. After its initialization magic is run, the runtime drops the number of arguments that the program received into it, and so its input magic runs. main can read the actual arguments through @ (the stack will be empty, so the execution will be suspended, the environment will drop the next available argument into main, and then execution will continue from the point where it stopped). After it finishes, the runtime will take values from main/'s stack until no values are available (the situation which would normally raise an error); these values will be returned to the runtime environment in the order they were taken.
How values are passed from and to the runtime environment will depend on the implementation. One possible form is:
Hatter has no control structures; conditional execution is performed through if and apply:
[[[if<-condition]<-\truehat]<-\falsehat]->apply
That is: if condition is non-zero, yields the hatid of truehat; otherwise, yields the hatid of falsehat. Then drop the resulting hatid into apply; from now on all movements involving that instance of apply will happen to the corresponding hat.
The Fibonacci hat yields all numbers of the Fibonacci sequence:
hat fib: init 1->@<-1 out [@->@1]->[[[[horn->add]->@]<-@1]->@]->add->@
That is: the hat is initialized to contain [1,1] in its argument stack. When a value is taken from it, it moves the bottommost value of the hat to the temporary stack @1, moves the next value to the cornucopia, copies it to add and back to @, moves the value in @1 to the horn, copies it back to @ and to add, and puts the sum (i.e., the next value in the sequence) into @. Now the topmost value can be taken by the calling hat. As can be seen from this example, Hatter can easily handle infinite sequences.
This hat receives a non-negative integer and calculates its factorial:
hat fac: in @->[[horn->@1]->pred]->[[if<-\fac]<-\nop]->[apply<-pred]->[mul<-@1]->@ out @->[horn->if]->[if<-1]->@
When a value n is dropped into this hat, it is copied to @1, passed to pred, and used as a condition to if. If n is non-zero, fac is recursively applied to pred(n); this result is multiplied by n and goes to @. If n is zero, nop is applied to pred(n), and yields zero. This value is multiplied by n (zero), so @ ends up with zero. When the value is taken from fac, a zero is corrected to one, and other values are left unchanged.
This hat receives a non-negative integer and prints it to screen:
hat printnum:
in @->[[[horn->@1]->[less<-10]->[[if<-\nop]<-\printnum]->apply
<-[[div<-horn]<-10]]<-@1]->[mod<-10]->[add<-48]->stdio
When a value n is dropped into this hat, it is copied to @1 and passed to less. If n>=10, printnum is recursively applied to n/10 (the number without the last digit); otherwise, nop is called. Note that printnum is called only for its side effect; it does not return any value. This subcall to printnum will modify the contents of horn, so n is restored from @1. Now, n modulo 10 (only the last digit of the number) is computed, the result is added to 48 (the ASCII value of '0'), and this value is sent to stdout.
Copyright © 2011 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.