Tuesday, 9 June 2015

Half nested arrays

Maskless woman veiling a hierophant's torso

In last blog we extended the superstar quantifier *{c} to a row *{R} of entries. Today its entry separator , will turn into a structure ,[S] of unique nested arrays. This increases at half speed compared to Bird nests. Both systems reload empty arrays to maximal size b.

§1 Dimensional subarray

We start anew and let the first nested index [c count entries on a superstar row. The next index ,d counts such rows on a plane. Further nested indices count multidimensional spaces in the top array.

Show how to evaluate a top array that is planar, where S is the right part of that plane. With rules for reload and elimination, on two index levels.

  • a*{,[c1,d]1S}b = a*{,[c,d]b,[c1,d]S}b
  • a*{,[,d1]S}b = a*{,[b,d]S}b
  • a*{,[,]S}b = a*{,[]S}b = a*{S}b
  • a*{,[c,d],S}b = a*{,S}b
  • a*{,[c,d]}b = a*{}b = ab

Arrays are filled by repeated application == of these rules, as they occur in practice in order of evaluation. The resulting numbers can become just as big as Bird creates with his angle brackets, filling all spaces with series of the same array separators. That is, provided we double our nesting depth.
The seps (separators) our system introduces during an evaluation have a unique index array. This is necessary to build expressions step by step. We don't like the instant repetition that Bird & Bowers (who continue from Knuth's arrows) use in their Beaf.
By doubling the depth of a nested array with unique seps, we occupy the same expression space as an array with multiple similar seps. We've proved this for fluid structures before.

We don't recommend input expressions with more than one sentry, because of details in the evaluation. Like, when two seps with the same index array come next, we cannot just adjoin them and add their entry values. Reducing expressions ltr a left subarray will cause reloads, that inflate a right subarray later. Only single (usually inner) arrays with the same index, can be merged like that in adjacent positions.
But given that reload by b is dominant, we can approximately adjoin similar sentries.

  • ,[p,S]m <≈ ,[p,S]m,[q,S]n < ,[pq,S]mn <≈ ,[p,1S]m

Truly bigger numbers are obtained as we continue to expand the dimensional subarray.
The planes in a cubic array are counted by the 3d nested entry, the cubic subarrays by the 4th entry, etc. Until our row of [m] nested entries captures the level of multidimensional arrays in the Beaf project (they use one nested entry {m} for this).
Note that in the input expression the dominant last subarrays are quantified alone. Before we evaluate the earlier subarrays, the reload rule inflates them to big box size b.

§2 Arrays at any depth

Our system for the first nested arrays, showing the nested depth on white.
Empty entries º 0 can be matched by a lookahead to , or ] in RegExp. #

  • a*{}b = ab (add)
  • a*{T}1 = a (unity)
  • a*{1T}b1 = a*{T}(a*{1T}b) (powers)
  • ,[]1 = 1 (counter)
  • ,[S]º = º (sep elim)
  • a*{,[1S]1R}b = a*{,[S]b,[1S]R}b (reload to entry)
  • a*{,[,[m1]1S]1R}b = a*{,[,[m]b,[m1]S]1R}b (reload to index)

The complete system for nested arrays follows easily, by generalizing the last two rules.
Search the inner (e subexpression )e to work in, or e=0 the outer expression when all is worked out. Scan from the left, until some separator ,[S] matches. If it reads ,[] or if an empty º entry comes next, eliminate that sep. Else subtract 1 from the next entry, and insert a sentry formed by the preceding sep and a big entry b copied from base.

General reload rule for our nested arrays, at any depth or half level. #

  • ( ,[1S]1n .b) => ,[S]b,[1S]n (reload)
  • ( ,[1S] .b) => ,[S]b (reload with sep elim)

We can still write duplicate seps in the input expression, but all the sep arrays our system inserts during the evaluation of a single sentry are unique. This variation could have been exploited to create bigger numbers, but the comparison with Bird's serial arrays suggests that wouldn't be a big help.
Our arrays are half nested, because at depth d*2 function speed is about equal to Bird's nested arrays at level d. This gap is bound to lose significance, once we express nesting depth as a function of big b in the next blog on deeps.

When on a row without indexed seps, as defined in last blog, an entry is reduced to zero, its left comma cannot be eliminated in between. Only at an array's end can plain commas be dropped, if trailing, because of their role in positioning right entries.
The arrayless comma that we reused above in §1 is just a macro , ,[1] substituting for the first sep between two innermost entries. Extending this, the old subsystem can be supplanted here to count off the deepest array level, when convenient.
We can also imagine array variations with plain sep followed by indexed sep, where we count down a right sentry until its index is empty, at last, to reload b in the plain entry ,0 waiting on the left. But it is better to avoid such mixed systems.

~~ Half Machine Lip Moves ~

Out of Phlegethon!
  out of Phlegethon,
                art thou come forth out of Phlegethon?
with Buxtehude and Klages in your satchel, with the
Ständebuch of Sachs in yr/ luggage
                              not of one bird but of many ……
Ezra Pound
Canto LXXV

No comments:

Post a Comment