From 78af096e176ab416d160a0bfeb9e6ffaaecec49d Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Wed, 21 Jul 2021 21:52:30 -0400 Subject: Low-stack iteration technique --- doc/control.md | 18 +++++++++++++----- doc/fromDyalog.md | 2 ++ docs/doc/control.html | 15 ++++++++++----- docs/doc/fromDyalog.html | 1 + 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`. + 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 @@

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.

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.

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.

-
If      ← {π•βŸπ•Ž@}Β΄               # Also Repeat
+
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
 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   ← {𝕏𝕨}Β΄
@@ -160,6 +160,11 @@
 
DoWhile ← {𝕨{π•ŠβŸπ”½π”Ύπ•©}𝕩@}Β΄
 

 
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.

 
FnΒ¨ v      # 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 @@
 
In BQN βŽ‰ is Rank and ∘ is Atop. Dyalog's Atop (⍀) and Over (β₯) were added in version 18.0.

 
For writing

 
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 and called as Fn _while_ Cond arg.
Functions
Glyph Monadic Dyadic
-- cgit v1.2.3
Functions
Glyph Monadic Dyadic