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 --- docs/doc/control.html | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) (limited to 'docs/doc/control.html') 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)
-- 
cgit v1.2.3