Low-stack iteration technique

1 files changed, 10 insertions, 5 deletions

diff --git a/docs/doc/control.html b/docs/doc/control.html
index bf8f65de..ad6c65f8 100644
--- a/docs/doc/control.html
+++ b/docs/doc/control.html
@@ -8,12 +8,12 @@
 <p>BQN does not have ALGOL-style control structures. Instead, functional techniques can be used to control when code is evaluated. This page describes how BQN functionality can be used to emulate something more familiar to an imperative programmer.</p>
 <p>Control structures here are always functions that act on lists of functions, although alternatives might be presented. This is because stranded functions can be formatted in a very similar way to blocks in curly-brace languages. However, there are many ways to write control flow, including simple operators and a mix of operators and more control-structure-like code. Implementing a control structure rarely takes much code with any method, so there are usually several simple ways to implement a given flow or a variation of it.</p>
 <p>The surfeit of ways to write control structures could be a bit of an issue for reading BQN. My hope is that the community can eventually settle on a smaller set of standard forms to recommend so that you won't have to recognize all the variants given here. On the other hand, the cost of using specialized control structures is lower in a large project without too many contributors. In this case BQN's flexibility allows developers to adapt to the project's particular demands (for example, some programs use switch/case statements heavily but most do not).</p>
-<p>The useful control structures introduced here are collected as shortened definitions below.</p>
-<pre><span class='Function'>If</span>      <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>𝕏</span><span class='Modifier2'>⍟</span><span class='Function'>𝕎</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span>               <span class='Comment'># Also Repeat
+<p>The useful control structures introduced here are collected as shortened definitions below. <code><span class='Function'>While</span></code> uses the slightly more complicated implementation that avoids stack overflow, and <code><span class='Function'>DoWhile</span></code> and <code><span class='Function'>For</span></code> are written in terms of it in order to share this property. The more direct versions with linear stack use appear in the main text.</p>
+<pre><span class='Function'>If</span>      <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>𝕏</span><span class='Modifier2'>⍟</span><span class='Function'>𝕎</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span>                 <span class='Comment'># Also Repeat
 </span><span class='Function'>IfElse</span>  <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>c</span><span class='Ligature'>‿</span><span class='Function'>T</span><span class='Ligature'>‿</span><span class='Function'>F</span><span class='Value'>:</span> <span class='Value'>c</span><span class='Modifier2'>◶</span><span class='Function'>F</span><span class='Ligature'>‿</span><span class='Function'>T</span><span class='String'>@</span><span class='Brace'>}</span>
-<span class='Function'>While</span>   <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕨</span><span class='Brace'>{</span><span class='Function'>𝕊</span><span class='Modifier2'>∘</span><span class='Function'>𝔾</span><span class='Modifier2'>⍟</span><span class='Function'>𝔽</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Value'>𝕩</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span>        <span class='Comment'># While 1‿{... to run forever
-</span><span class='Function'>DoWhile</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕨</span><span class='Brace'>{</span><span class='Function'>𝕊</span><span class='Modifier2'>⍟</span><span class='Function'>𝔽𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Value'>𝕩</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span>
-<span class='Function'>For</span>     <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>I</span><span class='Ligature'>‿</span><span class='Function'>C</span><span class='Ligature'>‿</span><span class='Function'>P</span><span class='Ligature'>‿</span><span class='Function'>A</span><span class='Value'>:</span> <span class='Function'>I</span><span class='String'>@</span> <span class='Separator'>⋄</span> <span class='Brace'>{</span><span class='Function'>𝕊</span><span class='Modifier2'>∘</span><span class='Function'>P</span><span class='Modifier2'>∘</span><span class='Function'>A</span><span class='Modifier2'>⍟</span><span class='Function'>C</span> <span class='Value'>𝕩</span><span class='Brace'>}</span><span class='String'>@</span><span class='Brace'>}</span>
+<span class='Function'>While</span>   <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Value'>𝕨</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span>  <span class='Comment'># While 1‿{... to run forever
+</span><span class='Function'>DoWhile</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>𝕏</span><span class='String'>@</span> <span class='Separator'>⋄</span> <span class='Function'>While</span> <span class='Value'>𝕨</span><span class='Ligature'>‿</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Modifier'>´</span>
+<span class='Function'>For</span>     <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>I</span><span class='Ligature'>‿</span><span class='Function'>C</span><span class='Ligature'>‿</span><span class='Function'>P</span><span class='Ligature'>‿</span><span class='Function'>A</span><span class='Value'>:</span> <span class='Function'>I</span><span class='String'>@</span> <span class='Separator'>⋄</span> <span class='Function'>While</span><span class='Bracket'>⟨</span><span class='Function'>C</span><span class='Separator'>,</span><span class='Function'>P</span><span class='Modifier2'>∘</span><span class='Function'>A</span><span class='Bracket'>⟩</span><span class='Brace'>}</span>
 
 <span class='Comment'># Switch/case statements have many variations; these are a few
 </span><span class='Function'>Match</span>   <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>𝕏</span><span class='Value'>𝕨</span><span class='Brace'>}</span><span class='Modifier'>´</span>
@@ -160,6 +160,11 @@
 <pre><span class='Function'>DoWhile</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕨</span><span class='Brace'>{</span><span class='Function'>𝕊</span><span class='Modifier2'>⍟</span><span class='Function'>𝔽𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Value'>𝕩</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span>
 </pre>
 <p>Because the condition is run repeatedly, it has to be a function, and can't be a plain expression as in an if conditional.</p>
+<h3 id="low-stack-version">Low-stack version</h3>
+<p>The above version of <code><span class='Function'>While</span></code> will fail in a fairly small number of iterations, because it consumes a new stack frame with each iteration. While tail call optimization could solve this, detecting the tail call in a compound function like <code><span class='Function'>𝕊</span><span class='Modifier2'>∘</span><span class='Function'>𝔾</span><span class='Modifier2'>⍟</span><span class='Function'>𝔽</span></code> is technically difficult and would introduce overhead into a BQN interpreter. However, there is a method to make the number of required stack frames logarithmic in the number of iterations instead of linear:</p>
+<pre><span class='Function'>While</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Value'>𝕨</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span>
+</pre>
+<p>The innovation is to use <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> instead of the equivalent <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> or <code><span class='Brace'>{</span><span class='Function'>𝕊</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> (these are the same, as <code><span class='Function'>𝕊</span></code> in a modifier is defined as <code><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span></code>). Here <code><span class='Function'>𝔽</span></code> performs one iteration and <code><span class='Function'>𝔾</span></code> tests whether to continue. The simplest approach is to perform one iteration and recurse with the same two functions. The modified approach replaces <code><span class='Function'>𝔽</span></code> with <code><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span></code>, that is, it doubles it while making sure the condition is still checked each iteration. The doublings compound so that recursion level <code><span class='Value'>n</span></code> performs <code><span class='Function'>𝔽</span></code> up to <code><span class='Number'>2</span><span class='Function'>⋆</span><span class='Value'>n</span></code> times while using on the order of <code><span class='Value'>n</span></code> additional stack frames. Only a hundred or two stack frames are needed to give a practically unlimited number of iterations.</p>
 <h2 id="for">For</h2>
 <p>To begin with, are you sure you don't want a for-each loop instead? In BQN that's just a function with Each (<code><span class='Modifier'>¨</span></code>), and it covers most common uses of a for loop.</p>
 <pre><span class='Function'>Fn</span><span class='Modifier'>¨</span> <span class='Value'>v</span>      <span class='Comment'># for (𝕩 in v)