Thursday, 25 June 2015

Birth of the Superdeep

Woman reading on the bed, devilish bookkeeper overhead

To construct deep nested arrays, we attached a second array to the closing bracket of the first. Such arrays appended in series were called deeps.
Seeking an new point of attachment, the left inside of opening brackets comes to mind. There is more space than in Bird's initial [[T]] Beyond arrays, but after the 2nd point comes a 3d and then what?

Bird solved the issue by introducing a new \ separator. We will stick to our deeps attached on the outside, and build a superstar * system for deeps on top.
The left operand of deep multiplication [V]* counts the number of added deeps. Multiple stars **.. can be indexed by superdeeps *{[W]} attached inside.

This blog article clarifies in detail, how the elementary operations with deep arrays work.

§1 Deep addition

Deeps are series of nestable arrays, that can be counted. Sentry ,[U][V]d1 where [U] has m arrays and [V] has n arrays, counts in total m+n deep arrays.
The function of a next array [Ti+1] is to nest the former [Ti]. If we append a single array this hugely increases the result. Yet we score this as deep addition of one array.

To begin with [U] can have many arrays, nested to great depth. Evaluation of appended deeps [V] = [Tm+j].. :n is postponed until the left expression is fully reduced and the preceding arrays [].. :m are all empty. Only then the first entry in array Tm+1 of V will be decremented and the last array Tm0 of U nested, by recursion deeper than before.

  • `[][c1,V]d1 = `[`[][c1,V]d][c,V]d1
    == `[..1..][c,V]í :d1:
  • where ` ,.[].. :m is empty deep
    V is deep Tj][..] :n
    or superdeep Tj]*{kj}[..] :n etc.
    and í decrements rtl from d12 to 2

By repetition we reach depth level d and then depth d+b*c and later even deeper. This was worked out in last blog. One by one the appended arrays in deep V will fill their run down left sibling again, by nesting and reload.

Deeps are naturally added by appending them. The reason for introducing a deep addition sign + is to give precedence to a higher operation on the right.
In a series of additions the last plus + matters directly for precedence. The first plus + is kept in place for when the last plus expires, that is when its right multiplication is just completed. Any deep pluses in the middle can always be removed.

Define addition over deeps. Given an empty deep [:] [].. :x0 array series on the separator stack. We rely on nesting adjacent arrays as defined before. #

  • [:][1V] => [U][V] (refill by nesting)
  • ,[:]+[1V]+[W] => ,[U]+[V]+[W] (nesting over first plus of pair)
    <= ,[:]+[V]+[W] == ,[:]+[:]+[W]
  • ,[:]+[:]+[V]+[W] = ,[:]+[:][V]+[W] (drop middle plus)
  • ,[:]+[V]d = ,[:][V]d (drop final plus)

Please click the grey board: to remove (toggle) the colons : from view, and the highlighting applied to the part of the expression that changes.

The first plus + remains in place as the left delimiter of deep operations. For the nesting rule over the first plus of a pair, it is mostly transparent. So the empty left array can be nested, as if the array that refills it was appended on the right.
But sometimes a single + will block the nesting, because the deep on its right belongs to a star operation. For the nesting rule over + to apply, another + must follow after the right deep. When the first addition comes last, both sides are just appended (drop final plus).

Only arrays can be appended to arrays, not numbers. The number d that follows this separator's index deep, is the next entry in the parent array.
Deep addition is not commutative, and we don't think of it as associative because operations are resolved ltr (left to right).
Syntax layout is just to aid the human eye, all code can be well interpreted in plain ascii.

Looking ahead, the action of an operator must be locked (postponed) in case a higher star operation follows right after. But we want to express right precedence without comparison rules for operator sizes, which would eventually become tedious.
To put a temporary lock on an operator we apply pluses + as markers. The higher star operation puts the + mark on the new operator that is inserted left, like a closing bracket.

§2 Deep multiplication

To multiply arrays is to repeat addition of the same arrays.
Although step by step addition is the rule, there is no practical difference if we append n times [V] directly, or if one deep [V]+ is added and run empty [:] before the next in separate steps. The inner reduction of each of these copied arrays must wait anyhow, until the subexpression on their left is fully emptied.
After we append a deep array, its left sibling arrays are nested again. They are rich and fat from the reload of big values b' that were grown far outside.

Follows an evaluation example of a deep multiplication, where a singleton deep (one array) is multiplied twice by a big number. To multiply arrays, the first entry of the left operand counts, how many times the right operand is added.
We reformat the deep A[T] for convenience. A copy of A is appended on the left side of the operation, and the original operand A remains shielded on the right from the reduction train that drives west (leftwards).

Let a sep macro `,.[]..+ :k represent a separator with any subsequent empty arrays, set apart by a first plus + from the operations on the right that have our attention.
For ease of use , ,[1] functions as a first nested comma. Evaluation steps in between that can be skipped are dotted grey.
Because A is a singleton deep, we can count how many empty arrays remain. Anyway, the two big reloads in this evaluation dominate their number, and the last b2 is biggest.

  • `[1,2]*A = `A+[,2]*A
  • <= `[]+[,2]*A => `[]+[b1,1]*A
  • = `[]+A+[b1-,1]*A = `[]A+[b1-,1]*A
  • == `.[]..+[1,1]*A :b1 = `.[]..A+[,1]*A :b1
  • => `.[]..+[b2]*A :b1+1
  • == `.[]..+[1]*A :b1+b2 = `.[]..A+[]*A :b1+b2
  • = `.[]..A :b1+b2

Line 1: Instead of attaching left to a separator or an outer bracket, the counter deep [1,2] on the left and the original deep A on the right both belong to the * operator sign.
The deep star * copies operand A to add-append-attach it to the deeps on the left. Instead, if we had multiple stars, we'd copy-insert the preceding star operation with A as its new counter.

Line 2: After A+ is appended, its plus signals that nesting is allowed over the first + plus (waiting in the ` macro). The ltr scan defers the star * operation until the stack is completely <= worked out.
Reducing the added deep gives a big boost to value b1 at base, before we reload it => to the empty multiplication counter.

Line 3: The second plus + becomes obsolete after inserting a third addition A+ and so we drop it.
The system can manage these two reductions in one rule. Make sure not to conflict with the reduction step on the first line: take the first plus + into account and preserve it.

Line 4: Decrement a first entry with value 1 just like any higher iterator value, provided it is not both the final single entry of its operand deep (case discussed below).

Line 5: The reduction train moves, between stations as it were, delivering ever larger numbers back and forth. New b' replace all counted down entries, also in preceding deep star operands. Every reload coming from base is pretty maximal again, so the system is swell…

Line 6: This last reduction of +[1]*[V] to [V] is tricky. Here you could take two steps: first copy the right array and then drop the +[0]*[V] zero operation. But this may lead to an unwanted collapse, as we explain: Because of the second plus, nesting over the first plus still goes, and all arrays to its right would thus be emptied. Scanning ltr the zero operation is dropped then, exposing a new left operand which has just run empty, collapsing the operations issued next from the right.
So we should finalize the unit array operation on the spot, and drop it together with the second plus. This way the left operand ranges from the first + to the remaining A[V] arrays.

Line 7: The resulting series of appended arrays is truly big. Although all are empty but one, the last appended deep will be counted off [-V] next step, to reload => the added deep +[1W] operand. Here it merges (drop final plus) and in turn revives ,[1W'] the whole separator deep.
In general, evaluating a deep multiplication [U]*[V] we count off the 2nd entry in [U] to add an increasingly big number bi of copies of the [V] deep. Later entries in the arrays of operand [U] iterate over the former, and increase the number of copied deeps appended on the left.

How does our system take a multiplication step? When exactly does it decide?
An operation +[U]*[V] can only be addressed, when the expression on the left is fully counted down, all arrays emptied.
The program searches ltr for an entry to count off. Then it passes the first deep + plus. In case the next deep is empty too, and a second + sign is met, the multiplication continues from there. To determine if this current plus owns the operand on its right, the program looks forward for another operator, see if there is a plus, finding the single * star of multiplication. This star is active, not postponed, so any operators further right do not matter.
Sometimes empty entries must be reloaded or left arrays nested, before a multiplication +[1U]*[V] starts to work. If the first entry [1 is available we count it off, copy the right deep and paste [V]+ left of the multiplier [U] deep.
In case a middle + plus is pasted, we remove it, so the new deep [V] is appended on the operation stack: the series of arrays right of the + created by the ongoing operation.

Define multiplication over deep arrays.
Let [:] be empty deeps, and - decrement a first entry. Word U>0 is not empty. #

  • ,[:]+[1U]*[V] = ,[:]+[V]+[U]*[V] (first step add)
    <= ,[:]+[:]+[U]*[V]
    = ,[:]+[:][V]+[-U]*[V] (next append)
  • ,[:]+[:]+[1]*[V] = ,[:]+[:][V] (last step append)
    => ,[:]+[U][-V]

Imagine the left operand in [U]*[V] to expand: to a linear array, nested arrays, and then into the deep… The next math event occurs, when [U]=[V] defines an array square [V]*[V] = [2]**[V] with exponent 2.
We insert passive *+ operators in the step rules of deep powers. Such marked operations stay inert and function like a closing bracket. So the evaluation of exponents is slightly more intricate than a series of deep multiplications, which we look at now.

Combine two deep multiplications ,.[]..+[U]*[V]*[W] :t to work out ltr in stages. First stage [U]*[V] reduces to a bigger series +[]..[V] :u>>t of empty arrays than we had before.
Because the first plus will block without a second free plus, only the empty arrays remaining from the first deep multiplication are nested. This so called operation stack is refilled to its leftmost entry, to form a new left deep, to multiply [W] on the right.
This second multiplication appends a bigger number of [W]+.. over left. Until +[1]*[W] reduces to [W] and the first plus + can finally be dropped.

Multiplication of arrays is like multiplication of numbers as defined earlier with superstars, but now with reversed operators. Of course the results from multiplying arrays are much bigger, but given that we had deep arrays the change is not so significant.
Structurally the deep plus + is void, it does nothing. And the deep star * on its own just doubles the available expression space, because both its operands are deeps.

§3 Deep powers

Sometimes precedence determines that a left operation has to wait for a right operation to be handled first. We may group operations by (round) brackets, and by using introduction and elimination rules for brackets we evaluate those operations. Or else we may use a subsystem of conditional precedence rules for operators.
A system that depends on operator comparison for precedence will become unwieldy as operator {index} complexity grows. Even though we can only theoretically reduce an input expression to output series of ones, our rules should be practical. We should be able to solve all expressions straight ltr [left to right] without conditional lookaheads.
Here we apply a marker sign on passive operations: our push + plus, supported by intro and elim rules. We never compare operators or array sizes <like Bird does>.

By comparing operators of some mixed expressions (without brackets) we found that rigid right to left evaluation holds up well against the rule of minority precedence for superstars.
Here we have changed the evaluation direction to the left, so the larger operations wait on the right and get the bigger reloads, to push more of the smaller operations left.
Array powers in push style should work the same as for numbers. We've just reversed the pop (postponed operator) method that pops smaller stars on top.
This step by step table of pop stars shows (vice versa) that the superpower 3****2 reduces to 1.. :65536 as we push exponents to the left.

Given a sequence [c1].*[Vi].. :n of deep multiplications, the deep [V1] is added c times and <= reduced to [].. empty arrays. When the left array is down to +[1]* this drops off, leaving [V1] on the empty stack.
The operation stack revives again, and when base value b reloads => the leftmost entry the next multiplication starts to append scores of [V2] deeps. After this multiplication runs empty, the next left operand deep is even bigger, and so on…
Series of deep multiplications can form an array power. The equal deeps [V]*..[V] :n express a power [n1]**[V] with exponent n+1.

To evaluate an array power we copy and insert star operations over to the left side. The first copied multiplication [V]*+ is postponed and stays passive. Every next copy we get an active multiplication [V]* that has to be reduced first.
As we append deeps on the waiting stack +[:] of empty arrays, the reduction train starts again. Box in box storage of ever bigger b, carried down to empty entries inside arrays, inside deeps, inside deep operands possibly, again and again…

The active parts in the equations below are highlighted. The red parts are changed next (towards the right), the green parts have just changed (from the left), and the yellow part changes in both equations: from the left and towards the right (yellow = green + red).
Click to toggle highlights. Click twice to showcase superstar indexing.

  • `+[b2]**{[2]}[a] = `+[a]*{[1]}+[b1]**{[2]}[a]
    = `+[a]*{[1]}[a]*{[1]}+[b]**{[2]}[a]
  • `+[a]*{[1]}[a] = `+[a]*{[]}+[a-]*{[1]}[a] <= `+[]+[a-]*{[1]}[a]
    = `+[][a]+[a--]*{[1]}[a] <= `+[][]+[a--]*{[1]}[a]
    == `+.[]..+[1]*{[1]}[a] :a- = `+.[]..[a] :a-
    => `+.[1Ti]..[a-] :a- `+[1V1]
  • `+[a]*{[1]}+[1b]**{[2]}[a] `+[1V1]*{[1]}+[b]**{[2]}[a]
    = `+[1V1]*{[1]}[a]*{[1]}+[b-]**{[2]}[a]
    = `+[a]+[V1]*{[1]}[a]*{[1]}+[b-]**{[2]}[a]
    == `+[V2]*{[1]}+[b-]**{[2]}[a]
    == `+[Vb]*{[1]}+[1]**{[2]}[a] = `+[Vb]*{[1]}[a]
    <= `+.[]..[a] :m `+[Vb1]

Here the sep macro ` ≡ ,.[].. :k stands for the empty left arrays and comma.
With just the comma, not the initial passive left deep, you might omit the first + obligation, and adapt the details of your algorithm accordingly. We simply declare that a plus + is always required at the start of a top-left superoperation.

Operands with one entry can be expanded to linear arrays, nested arrays and deeps, as shown before. Deep operands provide for deep powers, whose exponents can be repeated to form power towers. What's usually the upper part of an exponential tower is evaluated first in our ltr system, while we push lesser star operations towards the left.

Define powers over deeps, where [:] are empty. Word U>0. #

  • ,[:]+[1U]**[V] = ,[:]+[V]*+[U]**[V] (first)
  • ,[:]+[W]*+[1U]**[V] = ,[:]+[W]*[V]*+[U]**[V] (next)
  • ,[:]+[W]*+[1]**[V] = ,[:]+[W]*[V] (last)

The + opens the context of deep operations, where we scan ltr to find an active operator. At a passive star *+ marked by a plus, move to the next operator, and so on. The first unmarked star operation we encounter will be evaluated by one step.
During a next step (second line): count off the left operand deep - minus one, copy and paste a new operand deep [V]*+ and a passive multiplication, then drop the + from the waiting multiplication to activate it. So the passive starplus shifts right.
Every exponentiation step (after the first) is followed by a multiplication in a series of steps of deep additions, that continue as <= deep nesting over the first + plus.

In deep context a plus sign + + + can have three different tasks. But the second + can be derived from the mark for the index 0 superstar *{[]}+ inserted by deep multiplication.
We use double brackets to distinguish superstar deeps [U]*{[T]}[V] from their right operand. This index system is described below, but we define it properly in a next blog.

§4 Deep superpowers

Addition is not a copy or move operation and (therefore?) functionally void. By removing pluses between deeps [U]+[V] = [U][V] we directly append series of arrays, similar to addition a+b = ab = of natural numbers. But these are not series 1.. of units one: each next array has the property of nesting the previous array.
Here we maintain plus signs to signify precedence, to time the operation. A deep addition, with a first + or next + plus, can only be evaluated, if no higher operation follows past its right operand deep: either there comes another addition or the parent separator ends.
At evaluation time we perform nesting of left arrays over the first + while we keep it in place and ignore it. We drop a middle plus + when a new addition is put on the right.

One first plus + represents all opening (.. brackets for the deep operations that follow. Star operators that are plus + marked come ) in ) place ) of ) closing ) brackets ) to postpone these operations, because evaluation of the right context has precedence.
This helps to resolve deep star operations on arrays similar to superstar operations on numbers. Because the evaluation structure is similar, it follows that deep and superdeep (indexed) operations increase maximally, for the number of input characters employed.

Define superpowers over deeps. Word U0 is not empty.
We use repex {k0} quantifiers, where *{0} can be dropped. #

  • first step: +[1U]*{k1}[V] = +[V]*{k}+[U]*{k1}[V]
  • next step: +[W]*{k}+[1U]*{k1}[V] =
  • last step: +[W]*{k}+[1]*{k1}[V] = +[W]*{k}[V]

An active superpower *{k1} first spawnes a passive + marked operator to the left, which in the next such step becomes the active operator *{k} with one star less.
Eventually a pair of every subordinate *{0jk} operation will be present: one unmarked and active *{j} followed right by a marked and passive *{j}+ operator.

Instead of multiple deep stars for tetration *** and superpowers *.. :k in general, we can count stars *{[k]} with a first entry, inside an array for deep star indices.
These new generation index arrays have to be distinguished from the right operand deep. We delimit superdeep index arrays by double brackets ]*{[V]}[ to make the context clear. So the deep star operator *{k} equals *{[k]} in the superdeep.

Exploring structures, we find there is room for two array words *{{W}V} inside. But the less nested array V is not counted down ltr, which feels unnatural. We won't do it.
The next structure in our superdeep system will be supercomma arrays ,[[m]] with multiple brackets, to separate deeps [V] with single brackets.
Bird never attached his arrays to a comma, and we only need it to express 0 entries and deeps, both insignificant in their wider context. Same with the supercomma: its , sign is not essential for the algorithm. So we do not break even on the busy beaver characters yet.
Note that curly and square brackets {X}[X] differ visually, but are formally identical.

Evaluating the superstar operation [U]*{[1V]}[W] the system issues a locked operation [W]*{[V]}+ on the left. Further left a previously locked operator loses its mark, so the operation [1W']*{[V]}[W] becomes activated. Last step, the plus mark in *{[V]}+ is eliminated, when the operation +[1]*{[1V]}[W] is reduced to [W].
A locked index deep will be reloaded while we scan ltr, and not after activation, but this makes no difference. To place the marker plus + right of the superstar is fine.

Next blog we will present the new mathematical algorithm for our superdeeps. We prefer to scan expressions ltr and will adapt the original superstar operation accordingly. Lock it with passive pluses instead of brackets to push smaller operations left.
Because parent entry d seems too far away to help nest arrays inside our next level star index superdeeps, we have to devise a new nesting rule that keeps its account on the appended array only. Reserve its first two entries for nesting, in a general nesting rule for deep arrays, independent of their wider context.

This new nesting rule counts down the first entry over the range == of the nested depth, which is an insignificant loss against the old rule, applied above in §1.
The case of the single entry is somewhat unclear. Click the two initial nesting rules of null and basic insertion, to see how these unfold at the deepest level.

  • ` ≡ .[].. :s0 macro for empty arrays
  • `[][1p,1V] = `[,`[][p,1V]1][1p,V] new nesting rule
    == `[,..`[][1,1V]..1][j,V] :p: steps 2jp1
    = `[,..`[,`[][b,V]1][1,V]..1][j,V] :p: reload
  • [][p1] = [][p] == [][] null init
  • then Q ≡ ,[][b,0]1 = ,[][]1 = ,[]1 = 1
    up next Q' ≡ ,[Q][1]1 = ,[1][1]1 = ,[][1]b = ,[]b = b
    up next ,[Q'][2]1 = ,[b][2]1 = ,[b-][2]b forms big deep
  • [][p1] = [b][p] basic init
  • then ,[][b,0]1 = ,[b][b-]1 = ,[b-][b-]b big deep

Each nesting we insert a sentry with minimum value 1 for single use. Instead, suppose you take the maximum b from base, this change would hardly matter. As time comes each entry will be decremented and the same b reloads the entry before.
On this scale the nested depth dominates the rule and the extra entries are insignificant. Also the deep at the deepest level dominates those copied to all the other nesting levels.
So, building step by step, your alternative is to move = the right deep V to the inner level, and eventually == all the way down to the end of the nesting cascade. Your system output would hardly suffer any loss, not even under recursion of this move rule. Take care, if you craft such a rule, that it doesn't collapse the deep to zero at the inner level. Anyhow, we feel it isn't proper style for our deep numbers to go under cover inside an array unit.

Consider that the continuation in V of the right part of the deep runs at least to the end of this series of appended arrays, and can be further specified to contain all subsequent superdeep operations up to its parent structure's end.
As long as the expression is reducible anything goes. Suppose you transcend the word space the nesting originates from, and download the nested sentry from a top level array. For example, you insert a copy of the base array at the very top into the separator deeps, are your nestings still reducible?
Our first consideration would be that it is not natural to download a parent array in a child, but you need not bother about that. Second, observe that your rule wouldn't increase the number of depth levels much. Compared to the new deeps, that soon become nested by repeated reloads at depths in excess of big box value b, the extra levels inserted with the top arrays are dwarfed. Perhaps to make the most of the characters a system uses (the busy beaver principle), you don't need parent nesting. Or perhaps you do, if recursive array substitution with top levels stretching right to the edge, dominates.

Still we seem stuck on the question of reducibility: what token from the expression allows a maximum nesting rule, while avoiding an infinite loop? Suppose we insert the base array with every nesting step, decrementing the next deep as explained above could guarantee that the expression remains reducible, n'est pas?

  • 2b*{1C}a = a*{C}+1b*{1C}a (base power)
    = a*{C}a*{C}+b*{1C}a
  • b*{`,[1V]1X}a = b*{`,[V]b,[1V]X}a (sentry reload)
  • b*{`][2p,1X}a = (maximal nesting)
    b*{`,[`][1p,1X]a][2p,X}a =

Scanning ltr up to the nesting site, the left part of the base array is completely reduced, apart from ` := ,([]){mi}[` :n the empty left nested deeps. The right part X then contains the corresponding closing brackets.
Can you still imagine how this nesting rule reduces the deep? Does it grow significantly bigger number output? Bigger than Bird? Optimisation becomes harder as structures expand and the rule system grows. Sooner or later each mathematical genius will be lost with only vague clues. Yet we continue the expansion of our superdeep…

The two operands of a superdeep operation are series of nestable arrays or deeps. Equal word spaces, attached to the * star operator, one left, one right: two attachments.
We can count these two types with the superstar: representing the right operand by the empty 0 array as it were, and calling the left operand into existence at entry value 1.
With star index superdeeps *{[V]} we open a new word space, but we know the rule system is maximal for the structures employed. Bird's 1st beyond sign \ as exhausted \.. in his Beyond Nested Arrays, should almost equal our *.. deep stars. But now we will (also) reload whole deeps, and it's not clear yet how to classify such systems.

We can allow for single and multiple stars as well as stars indexed by arrays. Superdeep star index arrays have double brackets and their comma index arrays have double brackets too, in order to separate the deeps inside, that come in place of numbers.
The first deep inside contains the deep star counter, and continues its arrays as usual, with reloads b' from the expression star base. The next deep entry is to reload the previous empty deep with the big deep B from its deep star base. Our new superimposed reload mechanism!
Rows of deep entries follow, in comma positions indexed by superdeeps, which can be nested and appended as such. These superdeeps again are subject to superpowers, of which the index array is written with three brackets. Meaning they have no numbers, no deeps, but superdeep entries inside…

~~ Godstar p-Ov power ~~~

Hebban olla vogala nestas hagunnan hinase hic enda thu wat unbidan we nu.
Abent omnes uolucres nidos inceptos nisi ego et tu, quid expectamus nunc.
Have all birds begun nests, except me and you - what are we waiting for?

No comments:

Post a Comment