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.
== External resources ==
* The author's page
* A gentle introduction to Hatter
* Hatter half-compiler half-interpreter in JavaScript
Category:Languages
Category:2009
Category:Stack-based
Category:Functional paradigm