On this page:
hyperstack/  c

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

 (require punctaffy/hypersnippet/hyperstack)
  package: punctaffy-lib

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.


(hyperstack? v)  boolean?

  v : any/c
Returns whether the given value is a hyperstack. A hyperstack is a stack-like data structure that helps to keep track of nested hypersnippet structure while traversing a stream of text and brackets. It helps in the same way that a stack helps to keep track of s-expression-like nesting while traversing a stream of text and parentheses.


(hyperstack/c ds)  contract?

  ds : dim-sys?
Returns a contract which recognizes hyperstacks whose dimension system is an ok/c match for the given one.


(hyperstack-dim-sys stack)  dim-sys?

  stack : hyperstack?
Returns the dimension system of the given hyperstack.


(hyperstack-dimension stack)

  (dim-sys-dim/c (hyperstack-dim-sys stack))
  stack : hyperstack?
Returns the hyperstack dimension of the given hyperstack. This is a dimension number describing which dimensions of popping the hyperstack currently offers. A hyperstack of dimension N can be popped at any dimension M as long as (M < N).

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.


(make-hyperstack ds dimension elem)  (hyperstack/c ds)

  ds : dim-sys?
  dimension : (dim-sys-dim/c ds)
  elem : any/c
Returns an hyperstack (in some sense, an empty hyperstack) which has the given hyperstack dimension. When it’s popped at some dimension N, it reveals the data elem and an updated hyperstack that’s no more detailed than the caller specifies.

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.)


(hyperstack-pop i stack elem)

  (list/c any/c (hyperstack/c (hyperstack-dim-sys stack)))
  i : 
(let ([ds (hyperstack-dim-sys stack)])
  (dim-sys-dim</c ds (hyperstack-dimension stack)))
  stack : hyperstack?
  elem : any/c
Pops the given hyperstack at dimension i, which must be less than the hyperstack’s own hyperstack dimension. Returns a two-element list consisting of the data value that was revealed by popping the hyperstack and an updated hyperstack.

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.


(hyperstack-push bump-degree stack elem)

  (hyperstack/c (hyperstack-dim-sys stack))
  bump-degree : (dim-sys-dim/c (hyperstack-dim-sys stack))
  stack : hyperstack?
  elem : any/c
Returns a hyperstack which has hyperstack dimension equal to either the given hyperstack’s dimension or bump-degree, whichever is greater. When it’s popped at a dimension less than bump-degree, it reveals the given elem as its data and reveals an updated hyperstack that’s based on stack. When it’s popped at any other dimension, it reveals the same data and extra hyperstack detail that the given hyperstack would reveal.

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.