3.4 Hypernests: Nested Hypersnippets🔗ℹ

3.4.1 Hypernest Coils🔗ℹ

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

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.

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.

• 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.2 Hypernest Brackets🔗ℹ

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.

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.

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.

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

3.4.3 Hypernest Constructors and Operations🔗ℹ

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.

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.

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

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

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

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.

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

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.

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.

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.