Punctree

Punctree is an esolang by User:Arseniiv. It’s based on some ideas from June 2019. It uses binary trees with a hole (i.e., contexts) as its sole data type, an almost-call stack as its sole data store and a holy applicative paradigm as its chosen path to syntax. And it has an awful IO. But there was really no choice in that regard.

Values

Let’s define pure binary trees and pure 1-holed binary trees (“contexts”, or historically, “trees′”) via abstract syntax:

T ::= ‘0’          -- a leaf (an empty tree)
   |  ‘2’ T T      -- branching to two subtrees

C ::= ‘_’          -- a hole (an empty context)
   |  ‘2’ C T      -- branching to two subtrees: one with a hole, the other, whole
   |  ‘2’ T C      -- the same with arguments swapped

Θ ::= T | C        -- in case we don’t care or know

We’ll denote trees T by t, u, …, contexts C by t′, u′, … and trees* Θ as α, β, …. One can define several operations on them:

The simplest values are the constructors: constants 0, _, and three homonymous binary 2’s. One can swap the root branches of a tree*: (2 α β)° := 2 β α; 0° := 0; _° := _.

Also, any glaring hole can be plugged with something, so a hole in some context t′ can be plugged with u, resulting in a tree, or with u′, resulting in a context. Let’s denote this plugging operation as t′ ∘ α. Its formal definition is: _ ∘ α := α; (2 t′ t) ∘ α := 2 (t′ ∘ α) t; (2 t t′) ∘ α := 2 t (t′ ∘ α).

Moreover, consider a tree zipper, which is a pair (t′, t) =: ζ representing a tree t′ ∘ t with the subtree t focused on. We can shift the zipper’s focus in a simple manner:

• If t′ is not _, we can go up, ζ↑.

In case t′ = u′ ∘ (2 _ u), then ζ↑ := (u′, (2 _ u) ∘ t).

Likewise, if t′ = u′ ∘ (2 u _), then ζ↑ := (u′, (2 u _) ∘ t).

• If t is 2 u v, we can go down left ζ↙ or down right ζ↘:

ζ↙ := (t′ ∘ (2 _ v), u).

ζ↘ := (t′ ∘ (2 u _), v).

In this language there are no trees, but remember that u′ = 2 t′ t is a context, and a zipper is a pair isomorphic to u. So further we’ll treat u′ = 2 t′ t as a zipper (t′, t), too.

Also, on the same wave, whenever t′ ≠ _, we can factor t′ as u′ ∘ (2 _ u) or u′ ∘ (2 u _), with a uniquely determined tree τ(t′) := u. We can define a τ-copying operation:

(t′ ∘ (2 _ t)) τ→ (u′ ∘ (2 _ u)) := (u′ ∘ (2 _ t)).

three other cases regarding (2 t _), (2 u _) too, are analogous.

We can destruct trees*:

π₁(2 α β) := α, π₂(2 α β) := β — but these are of no use to us here.

π′(2 t′ t) := t′, π′(2 t t′) := t′ — this one is useful.

π(2 t′ t) := t, π(2 t t′) := t — again no direct use, but we can “get” t via τ-copying:

(2 t′ t) π→ (u′ ∘ (2 _ u)) := (u′ ∘ (2 _ t)), and likewise three other cases.

To make our way to arbitrary while-loops, we only need some testing operations:

Is t′ = _? (Or else t′ = 2 α β.)

Is t′ = 2 u′ u? (Or else t = 2 u u′ in case it’s not _.)

Whether τ(t′) — or maybe π(t′) — is 0? (Or else it’s 2 u v.)

Are t′ and u′ the same? (This abstracts the first one.)

Runtime

We’ll keep contexts in an enhanced stack which may contain bars | in addition to normal values. When a bar is at the top, popping a value is an error, like the stack is empty. It’s presumed that there are infinitely many bars at the bottom. In the following descriptions, elements of the stack are listed from bottom to top.

The following are special bar-related operations:

• Pushing a bar right under i topmost elements but not under another bar:

pushbar i: ... e ei ... e1 → ... e | ei ... e1 where i ≥ 0 and e1, …, ei are not bars.

• Popping the second topmost bar with anything between it and the topmost one:

popbar: ... e | a0 ... an | b0 ... bm → ... e | b0 ... bm where a0, …, an, b0, …, bm are not bars.

• Pushing copy of the i-th element, indexing 0-based from the bottom of the topmost bar up:

dup i: ... | a0 ... an → ... | a0 ... an ai where | is topmost and 1 ≤ i ≤ n.

Note this operation doesn’t invalidate indices.

• Popping a value and replacing i-th element, indexing 0-based as above, with it:

set i: ... | a0 ... ai ... an e → ... | a0 ... e ... an where | is topmost and 1 ≤ i ≤ n.

Note this operation doesn’t invalidate almost all indices.

Any other operations mentioned in #Values can and will be treated as popping their arguments and pushing their results afterwards.

Moreover, one can treat the stack as a sequence of frames made up of elements between each consecutive pair of bars, and:

• normal operations work only on elements of the topmost frame,
• elements are indexable (dup and set) also only in that frame,
• that frame can be cut in two by pushbar,
• the second-topmost frame is deleted by popbar.

Syntax and commands

The syntax is applicative: the code is a sequence of commands executed left-to-right.

Any arguments a command needs (placed before “↦” in the description) are popped first (“x y ↦ …” means y is popped first, x afterwards), then it’s run, then the results, if any (currently there are either 1 or 0 result values), are pushed to the stack. When evaluating a code block, no special things are done to the stack before or after it.

Source	Meaning
_	↦ _
+	x y ↦ 2 x (y ∘ 0)
~	x ↦ x°
.	x y ↦ x ∘ y
^	x ↦ x↑ if defined, or _ otherwise
/	x ↦ x↙ if defined, or _ otherwise
\	x ↦ x↘ if defined, or _ otherwise
%	x y ↦ x τ→ y if defined, or _ otherwise
#	x ↦ π′x if defined, or _ otherwise
@	x y ↦ x π→ y if defined, or _ otherwise
=	x y ↦ if x = y then (2 _ 0) else _
<	x ↦ if x = 2 u′ u then x else _ (i. e. if the hole is somewhere in the left branch of x, return x intact, otherwise return _)
[code]	↦ a context representation of code which can be evaluated later; it’s only used in control-flow primitive ?; you shouldn’t rely on representation details
?	see #Loop command
α|, …, ω|	pushbar i where i is 0, …, 23 for α, …, ω
|	popbar
α+, …, ω+	dup i if i (determined as above) is correct, otherwise it’s a run-time error
α=, …, ω=	set i if i (determined as above) is correct, otherwise it’s a run-time error
;	x ↦ a byte corresponding to x as defined in #IO is sent to the output
:	↦ a byte from the input encoded as defined in #IO, or _ on EOF
{comments}	do nothing

As one can see, we went the way of FALSE (and many other languages) for flow control, though in a humble fashion.

It’s a run-time error if there’s not enough (not-bar) values in the stack to match arity of an operation to be performed.

Loop command

? is a loop akin to Python’s while ... else. First, cond, body, else are popped (in reverse order, as to run code like this: cond body else ? as intended). Then, the evaluation is in this manner:

entered := false;

while (true) {

eval(cond);

if (pop = _) break;

entered := true;

eval(body);

}

if (! entered) eval(else);

Here, pop pops a (non-bar) element from the stack and returns it; if there are no non-bar elements, it’s a runtime error. And eval(c) evaluates a code block c.

IO

Idea due to User:int-e. On input, a byte B is transformed thus:

H := 255;

result := _;

while (H ≠ 0) {

c := if B % 2 = 1 then (2 _ 0) else (2 0 _);

result := result ∘ c;

B := B / 2; H := H / 2;

}

You can build such a number yourself starting with _ and using . to “add” __+ for ones and __+~ for zeros. You can also destruct these quite easily using # and <.

Adding bits from another end, one could use just _+ and _+~ applied sequentially to _.

On output, contexts of this shape are converted back to bytes; anything else leads to undefined behavior.

A boring earlier idea

On input, a byte ABCDEFGH₂ is transformed into

2 (2 (2 (2 (2 (2 (2 (2 _ [A]) [B]) [C]) [D]) [E]) [F]) [G]) [H]

where [A] := (if A = 1 then 2 0 0 else 0). You can build such a number yourself starting with _ and using + to “add” _ for zeros and __+ for ones.

Implementations

An implementation in Python by User:arseniiv. For now, it’s not accompanied by unit tests and so it still may have unexpected bugs. Also it lacks code docs, oh.

Examples

Why, maybe write one yourself!

Computational class

To be announced.

Related links

• Basic description of the zipper data structure, applied to binary trees. (Haskell)
• The Zipper, 1997 Paper by Gérard Huet, which introduced the 'zipper' concept.