#### 3.4Hypernests: Nested Hypersnippets

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

##### 3.4.1Hypernest Coils

 syntax
 syntax
 match expander
 procedure v : any/c
Struct-like operations which construct and deconstruct a hypernest-coil/c value that represents one layer of recursion in a hypernest of degree 0 (in the sense of dim-sys-dim-zero).

Every two hypernest-coil-zero values are equal?.

 syntax
 syntax(hypernest-coil-hole overall-degree hole data tails-hypertee)
 match expander(hypernest-coil-hole overall-degree hole data tails-hypertee)
 procedure v : any/c
 procedure coil : hypernest-coil-hole?
 procedure coil : hypernest-coil-hole?
 procedure coil : hypernest-coil-hole?
 procedure coil : hypernest-coil-hole?
Struct-like operations which construct and deconstruct a hypernest-coil/c value that represents one layer of recursion in a hypernest that would start with a hole in its bracket representation. Every hypernest of nonzero degree (in the sense of dim-sys-dim-zero) has at least one hole, and there’s nothing it can begin with other than a hole, so this is the most common case.

This has four parts: The overall-degree is the degree of the hypernest, the hole is the shape of the hole (carrying trivial? data in its own holes), the data is the data value carried in the hole, and the tails-hypertee is a hypertee of the same shape as hole, but where the data values are hypernests representing the rest of the structure. The tail hypernest carried in a hole of degree N is expected to have trivial? data in its holes of degree less than N. Its holes of degree not less than N can carry any data; they represent additional holes in the overall hypernest.

Note that the hole is basically redundant here; it’s just the same as tails-hypertee but with the data values trivialized. Most of our traversal operations make use of values of this form, and some of the places we would construct a typernest already have values of this form readily available, so we save ourselves some redundant computation by keeping it separate. (TODO: Offer an alternative way to create a hypernest-coil-hole without specifying its hole shape.)

On the other hand, we save ourselves some verbosity and some repetitive contract-checking by leaving out the dimension system. If we stored a dimension system alongside the rest of the fields in a hypernest-coil-hole, we could enforce far more precise contracts on the field values, but instead we allow any value to be stored in any of the fields and rely on hypernest-coil/c in the contract of any operation that needs to enforce the structure. (TODO: Reconsider this choice. In most places, we pass a coil to something that associates it with a dimension system as soon as we create it, so we’re effectively passing in the dimension system at the same time anyway. But for the sake of people doing a lot of computation at the coil level, perhaps enforcing contracts is too costly. We’ll probably need more practical experience before we understand the tradeoffs.)

A hypernest based on this kind of coil is essentially created from a snippet-sys-snippet-done in the shape of the hole, concatenated with the tail hypernests using snippet-sys-snippet-join.

Two hypernest-coil-hole values are equal? if they contain equal? elements.

 syntax

syntax

 (hypernest-coil-bump overall-degree data bump-degree tails-hypernest)

match expander

 (hypernest-coil-bump overall-degree data bump-degree tails-hypernest)
 procedure v : any/c
 procedure coil : hypernest-coil-bump?
 procedure coil : hypernest-coil-bump?
 procedure coil : hypernest-coil-bump?
 procedure coil : hypernest-coil-bump?
Struct-like operations which construct and deconstruct a hypernest-coil/c value that represents one layer of recursion in a hypernest that would start with a bump in its bracket representation.

This has four parts: The overall-degree is the degree of the hypernest, the data is the data value carried on the bump, the bump-degree is the degree of the bump, and the tails-hypernest is a hypernest of degree equal to the max of overall-degree and bump-degree, where the data values of holes of degree lower than bump-degree are hypernests representing the rest of the structure. The tail hypernest carried in a hole of degree N is expected to have trivial? data in its holes of degree less than N. Its holes of degree not less than N can carry any data; they represent additional holes in the overall hypernest.

Note that the bump-degree may be higher than the overall-degree.

We save ourselves some verbosity and some repetitive contract-checking by leaving out the dimension system. If we stored a dimension system alongside the rest of the fields in a hypernest-coil-bump, we could enforce far more precise contracts on the field values, but instead we allow any value to be stored in any of the fields and rely on hypernest-coil/c in the contract of any operation that needs to enforce the structure. (TODO: Reconsider this choice. In most places, we pass a coil to something that associates it with a dimension system as soon as we create it, so we’re effectively passing in the dimension system at the same time anyway. But for the sake of people doing a lot of computation at the coil level, perhaps enforcing contracts is too costly. We’ll probably need more practical experience before we understand the tradeoffs.)

Two hypernest-coil-bump values are equal? if they contain equal? elements.

 procedure ds : dim-sys?
Returns a flat contract that recognizes a well-formed hypernest coil for the given dimension system. For a value to be suitable, it must fall into one of the following cases:

• A hypernest-coil-zero? value.

• A hypernest-coil-hole? value which abides by stricter expectations. Namely: The overall degree (hypernest-coil-hole-overall-degree) must be a nonzero dimension number in the given dimension system. The hole shape must be a hypernest (of any degree) with the given dimension system and with trivial? values in its holes. The tails hypertee must be a hypertee similar to the hole shape, but with hypernests (the tails) in its holes. If a tail appears in a hole of degree N, each of its own holes of degree lower than N must have a trivial? value in it, and those holes must be in the same arrangement as the hole’s holes.

• A hypernest-coil-bump? value which abides by stricter expectations. Namely: The overall degree (hypernest-coil-bump-overall-degree) and the bump degree (hypernest-coil-bump-bump-degree) must be dimension numbers in the given dimension system, and the overall degree must be nonzero. The tails hypernest must be a hypernest of degree equal to the max of the overall degree and the bump degree, and it must have hypernests (the tails) in its holes of degree lower than the bump degree. If a tail appears in a hole of degree N, each of its own holes of degree lower than N must have a trivial? value in it, and those holes must be in the same arrangement as the hole’s holes.

##### 3.4.2Hypernest Brackets

 syntax
 syntax(hnb-open degree data)
 match expander(hnb-open degree data)
 procedure v : any/c
 procedure b : hnb-open?
 procedure b : hnb-open?
Struct-like operations which construct and deconstruct a hypernest-bracket? value that represents one of the brackets of a bump in a hypernest, and in particular the bracket that appears first in the hypernest’s bracket representation.

The given degree is the degree of the bump, and the given data is the data value to be carried on the bump.

The data has to be placed somewhere among the bump’s brackets, and we place it at the first bracket as a stylistic choice for readability: This way, the placement of data values is comparable to the placement of section headings in a document or prefix operators in a Racket program.

Two hnb-open values are equal? if they contain equal? elements.

 syntax
 syntax(hnb-labeled degree data)
 match expander(hnb-labeled degree data)
 procedure v : any/c
 procedure b : hnb-labeled?
 procedure b : hnb-labeled?
Struct-like operations which construct and deconstruct a hypernest-bracket? value that represents one of the brackets of a hole in a hypernest, and in particular the bracket that appears first in the hypernest’s bracket representation.

The given degree is the degree of the hole, and the given data is the data value to be carried in the hole.

The data has to be placed somewhere among the hole’s brackets, and we place it at the first bracket as a stylistic choice for readability: This way, the placement of data values is comparable to the placement of section headings in a document or prefix operators in a Racket program.

Two hnb-labeled values are equal? if they contain equal? elements.

 syntax
 syntax(hnb-unlabeled degree)
 match expander(hnb-unlabeled degree)
 procedure v : any/c
 procedure b : hnb-unlabeled?
Struct-like operations which construct and deconstruct a hypernest-bracket? value that represents any non-first bracket of a bump or hole in a hypernest, as it appears in the hypernest’s bracket representation.

The given degree is the degree of the hole that’s being initiated by this bracket. Even though this bracket isn’t the first bracket of a hole of the hypernest, it’s still the first bracket of some hole. It could be

• The first bracket of a hole of a bump of the hypernest;

• The first bracket of a hole of a hole of the hypernest;

• The first bracket of a hole of a hole of a bump of the hypernest;

• The first bracket of a hole of a hole of a hole of the hypernest; and

• Generally, the first bracket of (a hole of)+ a (hole|bump) of the hypernest.

Two hnb-unlabeled values are equal? if they contain equal? elements.

 procedure v : any/c
Returns whether the given value is a hypernest bracket. That is, it checks that the value is either an hnb-open? value, an hnb-labeled? value, or an hnb-unlabeled? value.

 procedure(hypernest-bracket/c dim/c) → contract? dim/c : contract?
Returns a contract that recognizes a hypernest-bracket? value where the degree abides by the given contract.

The resulting contract has the same contract obstinacy as the given one.

 procedure(hypertee-bracket->hypernest-bracket bracket) → (or/c hnb-labeled? hnb-unlabeled?) bracket : hypertee-bracket?
Given a hypertee bracket, returns a similar hypernest bracket.

 procedure → hypertee-bracket? bracket : (or/c hnb-labeled? hnb-unlabeled?)
Given a suitable hypernest bracket, returns a similar hypertee bracket. This only works for hypernest brackets that are hnb-labeled? or hnb-unlabeled?, not those that are hnb-open?.

##### 3.4.3Hypernest Constructors and Operations

 procedure v : any/c
Returns whether the given value is a generalized hypernest, such as a (non-generalized) hypernest.

A (non-generalized) hypernest is a specific data structure representing hypersnippets of a stream that contain fully matched-up arrangements (bumps) of brackets.

This is sufficient to represent, for instance, hypersnippets of character or token streams; each miscellaneous token in the stream can be treated as a bump-opening bracket (hnb-open?) of degree 0, which matches up with itself.

A generalized hypernest is a less specific data structure, one which might be based on an arbitrary snippet format system rather than just the kind that represents higher-dimensional snippets of streams (namely, (hypertee-snippet-format-sys)). For instance, if a certain snippet format system represents polygon-bounded snippets of a 2D Euclidean plane, the appropriate notion of "hypernest" would be a similar kind of snippet that could additionally contain some number of unbroken arrangements of matched-up polygon boundaries.

A generalized hypernest can be represented by a snippet in the underlying snippet format system. In this approach, each hole is represented with a hole that has the same shape, and each bump is represented with an infinite-degree hole that has a snippet-sys-snippet-done shape.

We don’t currently offer tools to construct or pull apart generalized hypersnippets (TODO), so (non-generalized) hypernests are the only particularly useful ones for now. Whenever we do supply better support for them, or whenever we decide the support we already have isn’t worth enough to keep around, we might make substantial changes to the hypernest utilities described here.

If a hypernest utility described here doesn’t mention the phrase "generalized hypersnippet," then the hypersnippets it refers to are the ones based on (hypertee-snippet-format-sys). For instance, all the hypernest-coil/c and hypernest-bracket? values are specialized to hypertee-based hypernests.

 procedure hn : hypernest?
Returns the dimension system the given hypernest’s degrees abide by. The hypernest can be a generalized hypernest.

 syntax

syntax

(hypernest-furl dim-sys coil)

 dim-sys : dim-sys?
 coil : (hypernest-coil/c dim-sys)
 match expander(hypernest-furl dim-sys coil)
Constructs or deconstructs a hypernest value, regarding it as being made up of a dimension system and a hypernest-coil/c value.

Two hypernests are equal? if they contain equal? elements when seen this way. Note that this isn’t the only way to understand their representation; they can also be seen as being constructed by hypernest-from-brackets.

 procedure → (hypernest-coil/c (hypernest-get-dim-sys hn)) hn : hypernest?
Given a hypernest, computes the hypernest-coil/c value that would need to be passed to hypernest-furl to construct it.

 procedure(hypernest-from-brackets ds degree brackets) → (hypernest/c (hypertee-snippet-format-sys) ds) ds : dim-sys? degree : (dim-sys-dim/c ds) brackets : (listof (hypernest-bracket/c (dim-sys-dim/c ds)))
Constructs a hypernest value, regarding it as being made up of a dimension system, a degree, and a properly nested sequence of hypernest-bracket? values.

If the brackets aren’t properly nested, the exn:fail:contract exception is raised.

Proper nesting of hypernest brackets is a rather intricate matter which is probably easiest to approach by thinking of it as a series of hyperstack push and pop operations, along with tracking some state about whether bumps are allowed. (The hypertee-from-brackets situation is similar, but in that case it’s just a series of pop operations, and bumps are never allowed.)

Thinking about it this way, the hyperstack starts out with a dimension of degree and data of (hash 'should-be-labeled #t 'bumps-allowed #f) at every dimension. Bumps start out as being allowed, and this status updates each time we update the hyperstack by becoming whatever 'bumps-allowed entry was revealed (not whichever entry was pushed or popped). We iterate through the list of brackets. An hnb-open? bracket may only be encountered while bumps are allowed, and it performs a hyperstack-push with data of (hash 'should-be-labeled #f 'bumps-allowed #t). Each hnb-labeled? or hnb-unlabeled? bracket performs a hyperstack-pop with data of (hash 'should-be-labeled #f 'bumps-allowed ba), where ba is the existing bumps-allowed state. (A hyperstack-pop in some sense simultaneously "pushes" that data value onto every lower dimension. See the hyperstack documentation for more information.) If the pop reveals a 'should-be-labeled entry of #t, the bracket should have been hnb-labeled?; otherwise, it should have been hnb-unlabeled?. Once we reach the end of the list, the hyperstack should have a dimension of 0 (in the sense of dim-sys-dim-zero).

Two hypernests are equal? if they’re constructed with equal? elements this way. Note that this isn’t the only way to understand their representation; they can also be seen as being constructed by hypernest-furl.

(TODO: Write some examples.)

procedure

(hn-bracs ds degree bracket ...)

(hypernest/c (hypertee-snippet-format-sys) ds)
ds : dim-sys?
degree : (dim-sys-dim/c ds)
bracket :
 (let ([dim/c (dim-sys-dim/c ds)]) (or/c (hypernest-bracket/c dim/c) dim/c))
Constructs a hypernest value, regarding it as being made up of a dimension system, a degree, and a properly nested sequence of hypernest-bracket? values (some of which may be expressed as raw dimension numbers, which are understood as being implicitly wrapped in hnb-unlabeled).

If the brackets aren’t properly nested, the exn:fail:contract exception is raised.

Rarely, some dimension system might represent its dimension numbers as hypernest-bracket? values. If that’s the case, then those values must be explicitly wrapped in hnb-unlabeled. Otherwise, this will understand them as brackets instead of as dimension numbers.

This is simply a more concise alternative to hypernest-from-brackets. See that documentation for more information about what it takes for hypernest brackets to be "properly nested."

(TODO: Write some examples.)

 procedure → (listof (hypernest-bracket/c (dim-sys-dim/c ds))) hn : hypernest?
Given a hypernest, computes the list of hypernest-bracket? values that would need to be passed to hypernest-from-brackets to construct it.

 procedure(hypernest/c sfs ds) → flat-contract? sfs : snippet-format-sys? ds : dim-sys?
Returns a flat contract that recognizes a generalized hypernest (hypernest?) value where the snippet format system and the dimension system are ok/c matches for the given ones.

In particular, this can be used to recognize a (non-generalized) hypernest if the given snippet format system is (hypertee-snippet-format-sys).

procedure

 (hypernestof/ob-c sfs ds ob b-to-value/c h-to-value/c) → (obstinacy-contract/c ob)
sfs : snippet-format-sys?
ds : dim-sys?
ob : obstinacy?
b-to-value/c :
 (let* ( [ffdstsss (snippet-format-sys-functor sfs)] [ss (functor-sys-apply-to-object ffdstsss ds)]) (-> (snippet-sys-unlabeled-shape/c ss) (obstinacy-contract/c ob)))
h-to-value/c :
 (let* ( [ffdstsss (snippet-format-sys-functor sfs)] [ss (functor-sys-apply-to-object ffdstsss ds)]) (-> (snippet-sys-unlabeled-shape/c ss) (obstinacy-contract/c ob)))
Returns a contract that recognizes any generalized hypernest (hypernest?) value if its snippet format system and its dimension system are ok/c matches for the given ones and if the values carried by its bumps and holes abide by the given contracts. The contracts for the bumps are given by a function b-to-value/c that takes the hypersnippet shape of a bump’s interior and returns a contract for values residing on that bump. The contracts for the holes are given by a function h-to-value/c that takes the shape of a hole and returns a contract for values residing in that hole.

As a special case, this can be used to recognize a (non-generalized) hypernest if the given snippet format system is (hypertee-snippet-format-sys).

The ability for the contracts to depend on the shapes of the bumps and holes they apply to allows us to require the values to somehow fit those shapes. It’s rather common for the value contracts to depend on at least the degree of the hole, if not on its complete shape.

The resulting contract is at least as reticent as the given contract obstinacy. The given contracts must also be at least that reticent.

 procedure(hypernest-shape ss hn) → (snippet-sys-snippet/c (snippet-sys-shape-snippet-sys ss)) ss : hypernest-snippet-sys? hn : (snippet-sys-snippet/c ss)
Given a generalized hypernest (such as a (non-generalized) hypernest), returns a hypersnippet shape that has the same degree and all the same holes carrying the same data values.

(TODO: Not all snippet systems necessarily support an operation like this, but all the ones we’ve defined so far do. It may turn out that we’ll want to add this to the snippet system interface.)

procedure

hn :
 (and/c hypernest? (hypernest/c (hypertee-snippet-format-sys) (hypernest-get-dim-sys hn)))
Given a non-generalized hypernest, returns a maybe? value containing the value associated with its hole of degree 0, if such a hole exists.

(TODO: Not all snippet systems necessarily support an operation like this, but all the ones we’ve defined so far do. It may turn out that we’ll want to add this to the snippet system interface.)

(TODO: We may want to change the design of this to support generalized hypernests.)

procedure

 (hypernest-join-list-and-tail-along-0 ds past-snippets last-snippet)

 (let ([ss (hypernest-snippet-sys (hypertee-snippet-format-sys) ds)]) (snippet-sys-snippet-with-degree=/c ss (snippet-sys-snippet-degree ss last-snippet)))
ds : dim-sys?
past-snippets :
 (let* ( [ss (hypernest-snippet-sys (hypertee-snippet-format-sys) ds)] [shape-ss (snippet-sys-shape-snippet-sys ss)]) (listof (and/c (snippet-sys-snippet-with-degree=/c ss (snippet-sys-snippet-degree ss last-snippet)) (snippet-sys-snippetof/ob-c ss (flat-obstinacy) (fn hole (if (dim-sys-dim=0? ds (snippet-sys-snippet-degree shape-ss hole)) trivial? any/c))))))
last-snippet :
 (let ( [ss (hypernest-snippet-sys (hypertee-snippet-format-sys) ds)]) (snippet-sys-snippet-with-0
Given a list of non-generalized hypernests and a final hypernest of the same degree, returns a concatenation of them all along their degree-0 holes. Every snippet but the last must have a trivial? value in its degree-0 hole, reflecting the fact that that hole will be filled in in the result. The degree of the hypernests must be greater than 0 so as to accommodate these degree-0 holes.

In general, snippet concatenations like snippet-sys-snippet-join aren’t list-shaped. However, list-shaped concatenations do make sense when each operand has exactly one designated hole and the shapes of the operands are compatible with each other’s holes. Since each hypernest of degree greater than 0 has exactly one degree-0 hole, and since every hypernest fits into every degree-0 hole, it’s particularly simple to designate concatenations of this form, and we supply this specialized function for it.

 syntax

syntax

(hypernest-snippet-sys snippet-format-sys dim-sys)

 snippet-format-sys : snippet-format-sys?
 dim-sys : dim-sys?
 match expander(hypernest-snippet-sys snippet-format-sys dim-sys)
 procedure v : any/c
 procedure → snippet-format-sys? ss : hypernest-snippet-sys?
 procedure ss : hypernest-snippet-sys?
Struct-like operations which construct and deconstruct a snippet system (snippet-sys?) where the dimension numbers are those of the given dimension system, the hypersnippet shapes are the same as those of the given snippet format system instantiated at that dimension system, and the hypersnippets are generalized hypernests which are based on that snippet format system and that dimension system. (In particular, when the snippet format system is (hypertee-snippet-format-sys), the generalized hypernests are just (non-generalized) hypernests.)

The resulting snippet system’s operations have behavior which corresponds to the sense in which we’ve described hypernests as hypersnippets throughout the documentation. Consider the snippet-sys-snippet-splice and snippet-sys-snippet-zip-map-selective operations, which iterate over all the holes of a hypersnippet. In the case of a hypernest, they iterate over each of the hypernest-coil-hole/hnb-labeled nodes exactly once (notwithstanding early exits and the skipping of unselected? data values), so indeed each of these nodes legitimately represents one of the hypernest’s holes. We’ve chosen to directly describe operations like hypernest-coil-hole in terms of hypersnippet holes, largely because the very purpose of hypernests is tied to the functionality they have as hypersnippets. Because of this, "hypernest-coil-hole nodes really do correspond to holes" may sound tautological, but in fact the behavior of this snippet system is the reason we’ve been able to describe those nodes in terms of holes in the first place.

(TODO: This isn’t really a complete specification of the behavior. A complete specification might get very exhaustive or technical, but let’s see if we can at least improve this description over time. Perhaps we should go through and hedge some of the ways we describe hypernests so that they specifically appeal to hypernest-snippet-sys as the basis for their use of terms like "hypersnippet," "degree," and "hole.")

Two hypernest-snippet-sys values are equal? if they contain equal? elements. One such value is an ok/c match for another if the first’s elements are ok/c for the second’s.

 syntax

syntax

(hypernest-snippet-format-sys original)

 original : snippet-format-sys?
 match expander(hypernest-snippet-format-sys original)
 procedure v : any/c
 procedure → snippet-format-sys? sfs : hypernest-snippet-format-sys?
Struct-like operations which construct and deconstruct a snippet format system (snippet-format-sys?) where, given any particular dimension system, the hypersnippet shapes are the same as those of the given snippet format system (original) instantiated at that dimension system, and the hypersnippets are generalized hypernests which are based on that snippet format system and that dimension system. (In particular, when original is (hypertee-snippet-format-sys), the generalized hypernests are just (non-generalized) hypernests, and the shapes are hypertees.)

The shapes and snippets are related according to the same behavior as hypernest-snippet-sys. In some sense, this is a generalization of hypernest-snippet-sys which puts the choice of dimension system in the user’s hands. Instead of merely generalizing by being more late-bound, this also generalizes by having slightly more functionality: The combination of functor-from-dim-sys-sys-apply-to-morphism with snippet-format-sys-functor allows for transforming just the degrees of a hypernest while leaving the rest of the structure alone.

Two hypernest-snippet-format-sys values are equal? if they contain equal? elements. One such value is an ok/c match for another if the first’s elements are ok/c for the second’s.