HatStack

HatStack is a unityped stack language, kind of like Forth! There is only one type: Hereditarily Finite Sets, represented as arbitrary-precision natural numbers using the Ackermann coding. Except we are sneaky, and it has multiple representations under the hood:

data HFS
  = NumLike Base BigNat
  | SetLike (Set HFS)
data Base = Bin | Dec | Hex

This is both good for preserving user intent (helping you remember if you intended a datum to be a number or set, maybe) and necessary for efficiency, indeed, feasibility.

For example, {{{{{{{}}}}}}} 2 65536 ^. == evaluates to true (in infix notation: ({{{{{{{}}}}}}} == 2 ^ 65536)), meaning that even relatively small sets like these would require huge BigInts to display, due to the power tower nature of the numeric representation. And in fact, 2 65536 ^. and 1 65536 <<. are both special-cased to compute as the singleton set {65536} instead of a natural number with 65537 bits.

Documentation

The implementation consists of:

A stack of stacks of HFSes
- Braces {…} and brackets […] add a new stack, so they can keep track of how many items were added. They differ in important ways, make sure to read up!
- .0, .1, etc. refer to a previous stack while $0, $1, etc. refer to the current stack. Nested brackets […] increment the stack that .0 et al. refer to, while nested braces {…} keep it the same.
Functions (procedures) and variables.
A control stack to keep track of constructs like if…(else)…end and begin…while…end.
Current error/skipping state, etc.

It is literally concatenative and interpreted: there is no compile-time checking, all the control flow constructs interact on the control flow stack.

Even set notation {…} and stack notation […] are concatenative!

Since we have access to the stack, we often encode lists on it as a length (at the top of the stack) followed by that number of items.

For example, {} {{}} 2 {#} tells {#} to pop 2 and construct a new set out of the next 2 items on the stack, viz. {} (the empty set) and {{}} (a singleton set). This makes the set { {{}}, {} }.

Data and Stack Manipulation

There are eight grouping operators, of various usefulness:

the brackets #[, [, ], ]#, for manipulating the stack
the braces #{, {, }, }#, for building sets

Each opening operator creates a new stack on top of the existing stacks, though their semantics differ. Each closing operator will close off the stack, and they must correspond to the same shape of operator (you cannot mix and match braces and brackets).

They are used in combination with variables .0, .1, et al. to bring in data from the outside stacks. You may also use the variables $0 and so on to refer to the current stack, whatever that is, just like you can at the top level. (So $0 always means dup, for example.)

Stack manipulation

The stack manipulation operators are really cool. As a warmup, swap can be expressed as 2 #[ .0 .1 ]. We can describe its execution on the stack {} {{}} like so:

Queue the deletion of 2 items from the stack, namely {} and {{}}
Create a new stack
Push .0 from the previous stack, this refers to {{}}
Push .1 from the previous stack, this refers to {}

Notice that the indexing has not changed, since we pushed to a different stack than we are referencing! This is why it is so cool. You can just say what you want, without having to think about how each operation will affect the indices you are referring to!
Delete the queued items {} {{}} from the previous stack
Pop the new stack, appending its items {{}} {} onto the previous stack (thus the opposite order of before ~)

Set creation

Quickref

#[

Immediately pop a number and queue deletion of that many items from the stack. Push a new stack and make the previous stack referenced by .0 and so on.

[

Push a new stack and make the previous stack referenced by .0 and so on.

]

Run the queued deletions and pop the new stack and append its items to the previous stack.

]#

Run the queued deletions and pop the new stack and append its items to the previous stack. Also push the length of the popped stack, to tell you how many items were pushed.

That is, this operator is meant for creating length-headed lists.

#{

Immediately pop a number and immediately float that many items, who will appear as members of the final result. Then push a new stack, but do not reference the previous stack with .0 et al. (unless it was the only stack!).

{

Push a new stack, but do not reference the previous stack with .0 et al. (unless it was the only stack!).

}

Pop the new stack and push a single item, being the set of items from the popped stack along with any elements floated by #{.

}#

Additionally push the length of the popped stack. Equivalent to } dup count.

Implementation

Operators

There are binary operators, which pop two and push one, and n-ary operators which pop their arity, pop that many operands, and push the result. (In general it is common for functions to take a variable number of arguments in this way, see length-headed lists.) Some operators will throw an error if they are called as 0-ary, since they do not have an identity.

There are three syntactic categories:

Symmetric operators like + and ==.
Sided operators like .-/-. and .\/\., where the . indicates which side the top of the stack goes to.
Orderings like < ( $<$ ) and =| ( $\subseteq$ ).

List of Binary Operators

There are N-ary versions of all of the operators: #+/+# and #-/-# and so on. For symmetric ones, the two operators are equivalent, but for sided operators you probably want to use the left-sided variants like #-, which means “repeatedly subtract the lower items from the top of the stack”, instead of -# which is an alternating subtraction.

Most of them are implemented as stack folds (of the natural associativity: top of the stack is evaluated first and the tail is folded in). Additionally, there are some special cases:

#== checks that all operands are equal,
#!= checks that no operands are equal,
#>< returns the only nonzero operand, or zero,
and the ordering relations like #<, #@, and #=> apply transitively: #< checks if the list is ascending from tail to head (for consistency of 2#< with <), and so on.

List of N-Ary Operators

Control Flow

All blocks end with the end keyword! As mentioned above, there is no compile-time checking for these constructs, they just interact on the stack in a way that works with these conventions.

begin…end (no-op, does not loop)
begin…while…end (loops), with continue and break
- while pops the condition, end loops back to begin
- This gives you both while () {} and do {} while() and an unholy mix of the two!
if…end and if…else…end
- if pops the condition
def…end with return
try…catch…end with throw and rethrow
recover…end with rethrow (maybe scuffed??)

Builtins/stdlib

Set, Nat/Num, Bin, Dec, Hex, HFS: Type hints: set a preferred display style for the HFS at the top of the stack. Set is shallow while HFS is deep. Nat/Num preserve the current base, but default to hexadecimal.

Do not turn deep sets into numbers! HFSes with depth greater than 6 are (probably) too large to fit into a BigInt.

Sets

single ({.}, 1#{}, 1 .<<, 2 .^): Create a singleton set (pop one, push one).
pack ({#}): Turn a stack-list into a set.
unpack ($#): Turn a set into a stack-list, with the smallest member on top (after the length of the set).

Constants

false, ⊥ (0, {}): An empty set.

true, ⊤ (1, {{}}): A nice non-empty set.

Ordered pairs and maps

Finite maps are encoded as graphs of functions: a set of pairs indicating the mapping from domain to range.

pair, >-

Make an ordered pair, where the top item of the stack $0 is considered the first element of the pair, and the second item $1 the second element.

To make a map (finite function), create a set of pairs, where the first elements form the domain and the second elements form the range.

For example, the map { 1: 5, 4: 7 } can be written as,

{
  5 1 pair
  7 4 pair
}

This can be applied with 1 apply and 4 apply, and any other apply will fail.

Note that it looks backwards!

unpair, -<

Destruct an ordered pair, putting the first element on top of the stack with the second element below it. Will throw if its argument is not an ordered pair.

apply, @@

Apply an argument $0 to the finite map $1, looking it up. Will throw if it discovers the map is invalid, or if the argument is not in the map.