3.5 Hyperstacks: The State of a Text-to-Hypernest Parser🔗ℹ

A hyperstack is a stack-like abstraction that makes it easier to maintain the state of a computation that converts between structured hypersnippet data and sequential representations of it (like parsing from text or pretty-printing). Hyperstacks generalize the way a more traditional parser might push onto a stack when it encounters an opening paren and pop from the stack when it finds a closing paren.

In particular, hyperstack pops correspond to inititiating holes in a hypersnippet being parsed. When a hole has degree 0, this is simply a closing paren, but when it has some higher degree N, the hole itself is a degree-N hypersnippet that will have some closing brackets of its own later in the stream. In order to interact properly with all those brackets later on, a hyperstack pop at dimension N basically pushes at every dimension less than N at the same time. (See the description of hyperstack-pop for more details.)

Hyperstack pushes correspond to initiating bumps in a hypernest, generalizing the way opening parens tend to correspond to the nodes of a syntax tree.

Over the course of executing a hyperstack-based stream traversal, the dimension of the hyperstack may change as it’s updated by pushes and pops. It’s important to check up on the dimension sometimes as a way to detect errors in the stream. In particular, if the dimension isn’t large enough before performing a hyperstack-pop operation, that indicates an unmatched closing bracket in the stream, and if the dimension isn’t 0 at the end of the stream, that indicates an unmatched opening bracket.

If the dimension is 0 (in the sense of dim-sys-dim-zero), then it can’t be popped since no dimension is less than that one, so the value of elem makes no difference.

Traditional empty stacks are always created with dimension 0. (Traditional nonempty stacks are created by pushing onto an empty one.)

The updated hyperstack has dimension at least i, and popping it at dimensions less than i will reveal data equal to the given elem value and extra hyperstack detail based on stack.

The updated hyperstack may have dimension greater than i. The behavior when popping it at dimensions greater than i corresponds to the extra hyperstack detail, if any, that was obtained when stack was popped.

Traditional stacks are always popped at dimension 0, so the entire resulting stack is comprised of this "extra information," and we can think of the extra information as representing the next stack frame that was uncovered. When we pop at a dimension greater than 0, we merely initiate a session of higher-dimensional popping. This session is higher-dimensional in the very sense that it may be bounded by several individual popping actions. A 1-dimensional session of popping has a beginning and an end. A 0-dimensional session is just a traditional, instantaneous pop.

When a hyperstack is being used to parse a sequence of hypersnippet brackets (such as hypertee or hypernest brackets), a popping session corresponds to a hole, and each hyperstack-pop call corresponds to one of the collection of higher-dimensional closing brackets that delimits that hole.

Traditional stacks are always pushed with a bump-degree greater than 0, so that the effects of this push can be reversed later with a pop at dimension 0. If the bump-degree is a dimension number with more than one lesser dimension available to pop at, then this push essentially initiates an extended pushing session that can take more than one pop action to entirely reverse.

For instance, if we push with a bump-degree of 2 and then pop at dimension 1, then we need to pop at dimension 0 two more times before the traces of elem are gone from the hyperstack. The first pop of dimension 0 finishes the popping session that was initiated by the pop of dimension 1, and the second pop of dimension 0 finishes the pushing session.

When a hyperstack is being used to parse a sequence of hypernest brackets, a pushing session corresponds to a bump.