Low-stack iteration technique

4 files changed, 26 insertions, 10 deletions

diff --git a/doc/control.md b/doc/control.md
index 6ffd8c8b..d3b47d29 100644
--- a/doc/control.md
+++ b/doc/control.md
@@ -8,13 +8,13 @@ Control structures here are always functions that act on lists of functions, alt
 
 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).
 
-The useful control structures introduced here are collected as shortened definitions below.
+The useful control structures introduced here are collected as shortened definitions below. `While` uses the slightly more complicated implementation that avoids stack overflow, and `DoWhile` and `For` 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.
 
-    If      ← {𝕏⍟𝕎@}´               # Also Repeat
+    If      ← {𝕏⍟𝕎@}´                 # Also Repeat
     IfElse  ← {c‿T‿F: c◶F‿T@}
-    While   ← {𝕨{𝕊∘𝔾⍟𝔽𝕩}𝕩@}´        # While 1‿{... to run forever
-    DoWhile ← {𝕨{𝕊⍟𝔽𝔾𝕩}𝕩@}´
-    For     ← {I‿C‿P‿A: I@ ⋄ {𝕊∘P∘A⍟C 𝕩}@}
+    While   ← {𝕩{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}𝕨@}´  # While 1‿{... to run forever
+    DoWhile ← {𝕏@ ⋄ While 𝕨‿𝕩}´
+    For     ← {I‿C‿P‿A: I@ ⋄ While⟨C,P∘A⟩}
 
     # Switch/case statements have many variations; these are a few
     Match   ← {𝕏𝕨}´
@@ -196,6 +196,14 @@ The same modifier technique used in `Forever` works for a while loop as well. Be
 
 Because the condition is run repeatedly, it has to be a function, and can't be a plain expression as in an if conditional.
 
+### Low-stack version
+
+The above version of `While` 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 `𝕊∘𝔾⍟𝔽` 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:
+
+    While ← {𝕩{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}𝕨@}´
+
+The innovation is to use `{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}` instead of the equivalent `{𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}` or `{𝕊∘𝔽⍟𝔾𝕩}` (these are the same, as `𝕊` in a modifier is defined as `𝔽_𝕣_𝔾`). Here `𝔽` performs one iteration and `𝔾` tests whether to continue. The simplest approach is to perform one iteration and recurse with the same two functions. The modified approach replaces `𝔽` with `𝔽⍟𝔾∘𝔽`, that is, it doubles it while making sure the condition is still checked each iteration. The doublings compound so that recursion level `n` performs `𝔽` up to `2⋆n` times while using on the order of `n` additional stack frames. Only a hundred or two stack frames are needed to give a practically unlimited number of iterations.
+
 ## For
 
 To begin with, are you sure you don't want a for-each loop instead? In BQN that's just a function with Each (`¨`), and it covers most common uses of a for loop.
diff --git a/doc/fromDyalog.md b/doc/fromDyalog.md
index 0540c875..71a61b48 100644
--- a/doc/fromDyalog.md
+++ b/doc/fromDyalog.md
@@ -84,6 +84,8 @@ In BQN `⎉` is Rank and `∘` is Atop. Dyalog's Atop (`⍤`) and Over (`⍥`) w
 
 The tables below give approximate implementations of Dyalog primitives for the ones that aren't the same. First- and last-axis pairs are also mostly omitted. BQN just has the first-axis form, and you can get the last-axis form with `⎉1`.
 
+The form `F⍣G` (Power with a function right operand; Power limit) must be implemented with recursion instead of primitives because it performs unbounded iteration. The modifier `_while_ ← {𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}` provides similar functionality without risk of stack overflow. It's discussed [here](control.md#low-stack-version) and called as `Fn _while_ Cond arg`.
+
 <table>
 <tr><th colspan=3>Functions</th></tr>
 <tr><th> Glyph          </th><th> Monadic                      </th><th> Dyadic </th>               </tr>
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)
diff --git a/docs/doc/fromDyalog.html b/docs/doc/fromDyalog.html
index fdafbf13..d213dbb5 100644
--- a/docs/doc/fromDyalog.html
+++ b/docs/doc/fromDyalog.html
@@ -274,6 +274,7 @@
 <p>In BQN <code><span class='Modifier2'>⎉</span></code> is Rank and <code><span class='Modifier2'>∘</span></code> is Atop. Dyalog's Atop (<code><span class='Value'>⍤</span></code>) and Over (<code><span class='Value'>⍥</span></code>) were added in version 18.0.</p>
 <h2 id="for-writing">For writing</h2>
 <p>The tables below give approximate implementations of Dyalog primitives for the ones that aren't the same. First- and last-axis pairs are also mostly omitted. BQN just has the first-axis form, and you can get the last-axis form with <code><span class='Modifier2'>⎉</span><span class='Number'>1</span></code>.</p>
+<p>The form <code><span class='Function'>F</span><span class='Value'>⍣</span><span class='Function'>G</span></code> (Power with a function right operand; Power limit) must be implemented with recursion instead of primitives because it performs unbounded iteration. The modifier <code><span class='Modifier2'>_while_</span> <span class='Gets'>←</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></code> provides similar functionality without risk of stack overflow. It's discussed <a href="control.html#low-stack-version">here</a> and called as <code><span class='Function'>Fn</span> <span class='Modifier2'>_while_</span> <span class='Function'>Cond</span> <span class='Value'>arg</span></code>.</p>
 <table>
 <tr><th colspan=3>Functions</th></tr>
 <tr><th> Glyph          </th><th> Monadic                      </th><th> Dyadic </th>               </tr>