Hatter
Hatter is an esoteric programming language devised by user:huangho on May 4th, 2009 and finished about nine months later. It is a hat-oriented language, 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.
Data movement and grouping
The commands for data movement are:
a->b Takes 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.
Data type and constants
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
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
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.
Hat declaration
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.
Hat stacks and recursion
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.
Standard hats
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).
Primitive hats
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.
Prelude hats
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.
I/O hats
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.
Program execution
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:
- By default, all arguments are numbers. In this case, the runtime will make each number available as one value to 'main'. The values returned by 'main' are also numbers and will be printed to stdout, separated by a space and followed by a newline.
- An implementation may provide support for string arguments. In this case, the runtime will first drop the number of strings passed into 'main', and then provide each character of each string, terminating each string with an ASCII NUL character. The values returned by 'main' are also a sequence of characters and will be printed to stdout, without an extra newline. To activate this mode, the implementation provides a pragma "!string".
Miscellaneous notes
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.
Examples
Fibonacci 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.
Recursive factorial
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.
Print a number
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.