Block structured iteration and recursion

Question

Programming languages traditionally have blocks that specifically cater to controlling iteration.

There is the simple while-loop:

while (i < 3) {...};

Then there is the more complicated for-loop:

for (i = 0; i < 3; i++) {...};

There are others, but these examples are sufficient to illustrate a point, which is that a characteristic of these iteration blocks is that the control statements are found in the header.

For the for-loop, these statements specify the setup, the entry condition, and the transition between each iteration. The contents of the block body ideally don't exert any influence over the same matters as the control statements in the header.

These principles of block structured programming exist, and these kinds of blocks have become prevalent, because they are proven in practice to improve the clarity and expressiveness of code.

Now, creating some sort of minimal reproduction of the for-loop mechanics using recursion would look something like this:

void loop(int i, int count, int step)
{
    if !(i < count) return;
    ...
    loop(i+step);
}

int main()
{
    loop(0, 3, 1);
}

And this of course doesn't preserve the scope of the caller, so there might be even more plumbing in a real application.

But even in languages that allow the loop method to be declared inside an existing method block and to access (or "capture") the variables in the outer scope, you still end up having something like this (in C# or pseudo-C):

int main()
{
    int accumulator = 0;

    void loop(int i, int count, int step)
    {
        if !(i < count) return;
        accumulator += 1;
        ...
        loop(i+step, count, step);
    }

    loop(0, 3, 1);
}

Even though the control values are clear enough at the call site, I think anyone can agree that this basic template taken as a whole is a mess compared to a for-loop.

The recursive method has to be declared prior to use, there is boilerplate, and the control statements of the algorithm are widely distributed, with the setup at the call site, the condition at the top of the body, and the transition at the bottom (together with some repetitive piping of parameters which exert overall control, and aren't supposed to change on each iteration/recursion).

Is there any existing language that has something akin to a recursive-for-loop that properly preserves the spirit of a block-structured language?

That is, where the control statements are found at the header of the block. the body of the block which follows (rather than precedes) the header can then be concerned purely with processing a single iteration, and there is no undue ceremony or boilerplate?

Alternatively, is there something about recursion (or about typical recursive algorithms) that I haven't grasped which makes it impossible to reconcile with block structuring along the lines described above?

If necessary to clarify, the sort of recursive algorithm I would have in mind is one that is capable of visiting each element in a tree structure of variable depth, similar to how a for-loop is capable of visiting each element of a simple array of variable length.

Edit: To @Mat who thinks the existing syntax cannot possibly be any simpler, what I have in mind is something like the following (pseudo-C#):

//This is just setting up the scenario.
List nest123 = {1, 2, 3};
List nest456 = {4, 5, 6};
List nest789 = {7, 8, 9};
List whole = {
        0,
        1, 
        nest123, 
        nest456, 
        nest789
    };

int cuml = 0;

//This is where the action occurs.
Recor (List a = whole) {
    for (int i = 0; i < a.Length; i++) {
        if (a[i] is int) cuml += a[i];
        if (a[i] is List) Recurse(a[i]);
    };
};

//Once control reaches this comment line, the 'cuml' variable should have the value 46.

There's two novel keywords here, Recor and Recurse.

'Recor' is just a made-up word specifying the type of block (like 'for' would for the for-loop block). The 'Recurse' keyword causes the containing Recor block to re-enter at the top as a recursive call, with the specified parameter.

When the Recor-block is first entered, it's parameter 'a' is explicitly initialised.

When the Recor-block is recursively entered, the variables from outside the block remain in scope as before, but the variables within are all reset, and the parameter is set to the value given at the site of the calling Recurse keyword.

When the end of the Recor-block is reached, either control returns to the point in the context where the Recurse keyword was last invoked (and all the variables local to that context are also restored), or the Recor-block is exited if all recursive calls are already unwound.

It's all very similar to how recursive calls work already, except without the ceremony of naming the recursive method, without defining the parameters separately from their initialisation, and without having to explicitly call the method for the first time.

Answer 1

Such convenient recursion is possible if you either have lambda functions or some syntactic abstraction.

Fun with higher-order functions

For example, we might have a language where we can define a function that kicks off another function with some starting argument. We can write in Typescript:

function start<T, R>(initial: T, body: (state: T, rec: (state: T) => R) => R): R {
  // Adapt the recursive function so that body can simply "rec(state)"
  const rec: (state: T) => R = (state: T) => body(state, rec);
  return rec(initial);
}

let accumulator = 0;
start(0, (i, rec) => {
  if (i > 3) return accumulator;
  accumulator += 1;
  return rec(i+1);
});

console.log(accumulator);

But is this actually useful? I don't think so. This is a pretty close fit for your Recor/Recurse idea though, with the constraint that Recurse is not a keyword but a function that must be passed to the body explicitly. To translate your specific example using my start function:

type ArrayOrNum = number | ArrayOrNum[];

const whole: ArrayOrNum[] = [
  0,
  1, 
  [1, 2, 3], 
  [4, 5, 6], 
  [7, 8, 9],
];

let cuml = 0;
start(whole, (a: ArrayOrNum[], recurse) => {
  for (const item of a) {
    if (typeof item == "number") cuml += item;
    if (Array.isArray(item)) recurse(item);
  }
});

Though personally, I think that is a fairly imperative way of dealing with the data. I'd rather express your problem as:

const cuml = whole.flat().reduce((acc, x) => x + acc, 0);

(were .flat() is a recursive method to concatenate all nested arrays).

Abstracting iteration patterns with higher-order functions

Such higher-order functions as start() are more useful to encapsulate interesting iteration patterns, potentially using recursion. A classic for-loop could be implemented as:

function forloop(fromIncl: number, toExcl: number, step: number, body: (state: number) => void): void {
  // for (state = fromIncl; state < toExcl; state += step) body(state);

  const rec = (state: number) => {
    if (state < toExcl) {
      body(state);
      rec(state + step);
    }
  }

  rec(fromIncl);
}

forloop(0, 3, 1, (i) => console.log(i));

An in-order traversal through a tree could be written as:

interface Tree<T> {
  left?: Tree<T>;
  right?: Tree<T>;
  value: T;
}

function traverseInOrder<T>(tree: Tree<T> | null | undefined, eachValue: (value: T) => void) {
  if (!tree) return;
  traverseInOrder(tree.left, eachValue);
  eachValue(tree.value);
  traverseInOrder(tree.right, eachValue);
}

const tree = {
  left: {
    value: "A",
    right: { value: "B" },
  },
  value: "C",
  right: {
    left: { value: "D" },
    value: "E",
  }
};

traverseInOrder(tree, console.log);

A tail-recursive variant of that would be possible as well, if the recursive function accepts a continuation argument.

Syntactic abstraction as an alternative

While C does not have lambda functions, it does feature macros for syntactic abstraction. If we allow the GNU-C extension of nested functions, then we could define a recursive for-loop:

#define FORLOOP(i, startIncl, stopExcl, step) \
  auto void FORLOOP_body(int i); \
  void FORLOOP_rec(int i) { if (i < (stopExcl)) { FORLOOP_body(i); FORLOOP_rec(i + (step)); } } \
  FORLOOP_rec((startIncl)); \
  void FORLOOP_body(int i)

FORLOOP(i, 0, 3, 1) {
  printf("got %d\n", i);
}

Of course this is extremely limited in C, for example the loop body would not be able to see local variables. However, languages with closures (not necessarily lambdas/anonymous functions) and a hygienic macro system can be more flexible here. Hygienic macro systems are rare in C-style languages, though Rust is an exception.

macro_rules! forloop {
    (($var:ident: $ty:ty, from = $start:expr, to = $stop:expr, step = $step:expr) $body:expr) => {{
        // Recursive closures need awkward workarounds in Rust
        // see https://stackoverflow.com/questions/16946888/is-it-possible-to-make-a-recursive-closure-in-rust
        struct Rec<'a> { f: &'a dyn Fn(&Rec, $ty) }
        let rec = Rec {
            f: &|rec: &Rec, $var: $ty| {
                if $var < $stop {
                    $body;
                    (rec.f)(rec, $var + $step);
                }
            }
        };
        (rec.f)(&rec, $start);
    }};
}

fn main() {
    use std::cell::RefCell;
    let acc = RefCell::new(0);  // work around Rust's mutation tracking
    
    forloop! {(i: usize, from = 0, to = 3, step = 1) {
        *acc.borrow_mut() += i;
        println!("got {i}");
    }}
    
    let acc = acc.into_inner();
    println!("acc {acc}");
}

There is no compelling reason to do that though when the existing loops are so much simpler.

Answer 2

I believe you can do something like this in existing languages. So long as things like lambdas and currying don't scare you off.

Alternatively, is there something about recursion (or about typical recursive algorithms) that I haven't grasped which makes it impossible to reconcile with block structuring along the lines described above?

I think I can show that there is nothing that makes it impossible. But Javascript is all I have handy at the moment so it's not going to be pretty.

What follows focuses on achieving this requirement in an existing language:

control statements are found in the header.

Give me this:

function header(n) {
  return function(s) {
    return function(f) {
      return f(s, n);
    };
  };
}

And you can do this:

console.log(
  header(5)(function(n) { return (n === 0) } )(
    function(timeToStop, n) {
      if (timeToStop(n)) { 
        return 1
      } else { 
        return n * (arguments.callee(timeToStop, n-1))
      }
    }
  )
)

Output:

120

Not as pretty as a for each loop but it shows there is nothing wrong with this structure.

Answer 3

Disclaimer: I am not taking a stance on whether this is okay or not to do, I am only providing examples of how it is possible to achieve the desired syntax.

In Groovy you can get close to the syntax you suggested

recor(whole) { a ->
    for (...) {
        // ...
        if (...) recurse(a[i])
    }
}

and in Kotlin you can pretty much do exactly the syntax that you want

recor(a = whole) {
    for (...) {
        // ...
        if (...) recurse(a[i]) // `a` is accessible anywhere in the code block
    }
}

except the for loop syntax, because Kotlin does not have the for loop variant that you used in your example, but it does have other for variants that achieve the same, such as for (i in a.indices) and if index access and list (or array) manipulation would have been a requirement you could always use a while loop instead.

If anyone knows of other languages where the suggested syntax is possible, please let us know by providing a new answer (or let us know in the comments).

We will explore how to achieve the above in Groovy and Kotlin, but lets start with Javascript and see what syntax limitations prevent it to achieve the desired syntax.

A Javascript (Typescript) example

Here is a full working example in Javascript

const nest123 = [1, 2, 3]
const nest456 = [4, 5, 6]
const nest789 = [7, 8, 9]
const whole = [0, 1, nest123, nest456, nest789]

function arrayExample() {
    let cuml = 0

    recor(whole, s => {
        const a = s.a
        for (let i = 0; i < a.length; i++) {
            if (typeof(a[i]) == "number") cuml += a[i]
            //else if (Array.isArray(a[i])) s.recurse(a[i])
            // but no need for the check if we know what to expect
            else s.recurse(a[i])
        }
    })

    console.log(cuml) // 46
}

function iteratorExample() {
    let cuml = 0

    recor(whole, _ => {
        for (const v of _.a) {
            if (typeof(v) == "number") cuml += v
            // else if (Symbol.iterator in v) s.recurse(v)
            else _.recurse(v)
        }
    })

    console.log(cuml) // 46
}

// the implementation
// this is a function you would only implement once and then include from some file / library
function recor(a, block) {
    const scope = {
        a: a,
        recurse: a => recor(a, block)
    }
    // the block call happens here, inside the block calls to recor happen recursively
    block(scope)
    // here the flow returns to the caller at the current recursion depth
}

arrayExample()
iteratorExample()

In Typescript, since it is a superset of javascript, the same is possible, but as a bonus some type safety could be added. There could be multiple implementations of recor based on the used type (array vs iterator).

While the above syntax does get close, it has some extra needed syntax (such as =>) and also has that extra scope parameter, which can be shortened to just a single letter (example with s above) or even to just an underscore _, but it still has to be there. Also the block is inside the parenthesis instead of outside.

But can we do better and bring the syntax closer to your example?

A Groovy example

final nest123 = [1, 2, 3]
final nest456 = [4, 5, 6]
final nest789 = [7, 8, 9]
final whole = [0, 1, nest123, nest456, nest789]

def exampleSum(whole) {
    int cuml = 0

    recor(whole) { a ->
        for (int i = 0; i < a.size; i++) {
            if (a[i] instanceof Integer) cuml += a[i]
            else recurse(a[i])
        }
    }

    println(cuml) // 46

    cuml = 0

    // doing it with iterators also works
    recor(whole) { a ->
        for (v in a) {
            if (v instanceof Integer) cuml += v
            else recurse(v)
        }
    }

    println(cuml) // 46
}

// traverses in depth-first order
def exampleDF(whole) {
    recor(whole) { a ->
        for (v in a) {
            if (v instanceof Integer) println(v)
            else recurse(v)
        }
    }
}

// traverses in breadth-first order
def exampleBF(whole) {
    recor(whole) { a ->
        def next = []
        for (v in a) {
            if (v instanceof Integer) println(v)
            else next.addAll(v)
        }
        if (next) recurse(next)
    }
}

// the implementation
// this is a function you would only implement once and then include from some file / library
def recor(a, block) {
    block.recurse = { next_a -> recor(next_a, block) }
    // the block call happens here, inside the block calls to recor happen recursively
    block(a)
    // here the flow returns to the caller at the current recursion depth
}

exampleSum(whole) // prints the sum of all elements (46) twice

// added 10 and 11 so that DF and BF produce different output
def wholeWithMoreData = whole + [10, 11]
exampleDF(wholeWithMoreData) // prints depth-first traversal
exampleBF(wholeWithMoreData) // prints breadth-first traversal

Now this is much closer and the only difference (apart from is being instanceof in Groovy) is the syntax of where the a variable is "named". In your example you had recor(a = whole) { ... }, here you have recor(whole) { a -> ... }. In Groovy you could go with a named argument for a, but I couldn't find a way to set a correctly on the block scope to be able to get rid of a -> as well, but some Groovy gurus out there might be able to do that, which would give you recor(a: whole) { ... }, where the only difference left would be a: whole versus a = whole.

A Kotlin example

Here is a full working example in Kotlin.

val nest123 = listOf(1, 2, 3)
val nest456 = listOf(4, 5, 6)
val nest789 = listOf(7, 8, 9)
val whole = listOf(0, 1, nest123, nest456, nest789)

fun exampleSum(whole: Iterable<*>) {
    var cuml = 0

    recor(a = whole) {
        for (v in a) {
            if (v is Int) cuml += v
            if (v is Iterable<*>) recurse(v)
        }
        /*
        // if you would need the index as well, you would do
        for ((i, v) in a.withIndex()) {
            // i is the current index
            if (v is Int) cuml += v
            if (v is Iterable<*>) recurse(v)
        }
        */
        // and if you would need total index/list manipulation you would
        // convert it to a mutable list and then use a while loop to manipulate it
    }

    println(cuml) // 46
}

// traverses in depth-first order
fun exampleDF(whole: Iterable<*>) {
    recor(a = whole) {
        for (v in a) {
            if (v is Int) println(v)
            if (v is Iterable<*>) recurse(v)
        }
    }
}

// traverses in breadth-first order
fun exampleBF(whole: Iterable<*>) {
    recor(a = whole) {
        val next = mutableListOf<Any?>()
        for (v in a) {
            if (v is Int) println(v)
            if (v is Iterable<*>) next.addAll(v)
        }
        if (next.isNotEmpty()) recurse(next)
    }
}

exampleSum(whole) // prints the sum of all elements (46)

// added 10 and 11 so that DF and BF produce different output
val wholeWithMoreData = whole + listOf(10, 11)
exampleDF(wholeWithMoreData) // prints depth-first traversal
exampleBF(wholeWithMoreData) // prints breadth-first traversal

So in Kotlin you could easily achieve what you are asking in you question.

This is the implementation code that would only need to be written once.

interface RecorScope {
    /**
     * returns the iterable of this [RecorScope]
     */
    val a: Iterable<*>

    /**
     * Calls the block of this [RecorScope] on the given iterable.
     *
     * @param a the iterable to pass to the block of this [RecorScope]
     */
    fun recurse(a: Iterable<*>)
}

fun recor(a: Iterable<*>, block: RecorScope.() -> Unit) {
    val scope = object : RecorScope {
        override val a = a
        override fun recurse(a: Iterable<*>) = recor(a, block)
    }
    // the block call happens here, inside the block calls to recor happen recursively
    scope.block()
    // here the flow returns to the caller at the current recursion depth
}

All this is possible to syntactically look how you suggested in your example because of the following features in Kotlin:

1. Supports passing functions/lambdas as parameters in function calls, so it supports higher order-functions.
2. Supports defining functions at a top-level (as opposed to be limited to defining methods inside classes), which makes it possible to call the recor function from anywhere without any (class) prefix
3. Supports named arguments, which makes the a = part possible in recor(a = whole)
4. If the last parameter of a call is a lambda, it can be moved outside the parenthesis, which makes it look like a "control statement with a block" and makes this part possible recor(...) { ... }.
5. A function literal can be defined (and called) with a receiver (that's how it is called in Kotlin). The receiver then becomes this inside the function/lambda scope.
6. Calling this. can be ommited, which together with 5. makes it possible to write nice DSLs, which allows accessing a inside the block without the need to write this.a and it allows calls such as { recurse(...) } where recurse receives an additional parameter automatically without the need to pass it at the call site.
7. It has smart casts, which means that after checking a value for its type, you don't have to also cast it to that same type, which makes it possible to write if (v is Int) cuml += v

I think that feature 1. is the important one.

Without features 2. - 7. it is still possible to do what you want, but the syntax would be a little more verbose and the block would have to be inside the parenthesis (like in the javascript example).

If you can use a language that supports higher-order functions and at least some features that are mentioned above, then there is a high chance you can implement something similar and make it look good syntax-wise.

But even if you have to use a language that does not have these features, as long as you can pass functions as parameters to other calls/functions, there is a chance that you can still implement this and make it look somewhat okay syntax-wise.

A C# example

C# only supports feature 1. from the list above (as far as I know) so the closest I could get is this

int cuml = 0;

Recor.with(whole, _ => {
    foreach(var v in _.a) {
        if (v is int) cuml += (int)v;
        if (v is IEnumerable<object>) _.Recurse(v as IEnumerable<object>);
    }
});

Console.WriteLine(cuml); // 46

Notice the

• extra prefix required in the starting call because 2. is not possible in C#
• no named argument because 3. is not possible
• lambda is inside parenthesis because 4. is not possible
• _ has to be used because 5. and 6. are not possible
• the extra casts are needed because 7. is also not a thing in C# (I used IEnumerable<T> instead, but with List<T> would have been the same).

The C# implementation

static class Recor {
    public class Scope {
        public IEnumerable<object> a;
        private Action<Recor.Scope> block;

        public Scope(IEnumerable<object> a, Action<Recor.Scope> block) {
            this.a = a;
            this.block = block;
        }

        public void Recurse(IEnumerable<object> a) {
            Recor.with(a, this.block);
        }
    }

    public static void with(IEnumerable<object> a, Action<Recor.Scope> block) {
        block.Invoke(new Recor.Scope(a, block));
    }
}

Answer 4

I do not think there can be a language that implements loops as recursive functions because loops and recursion are fundamentally different concepts.

A loop is just a jump within a state environment. A function call and thus recursion implies a state transition: state is stacked with the call and restored with the return.

The second being the more complex mechanism could technically mimic the basic jump but it would be utterly pointless and highly inefficient. So I do not expect this to be a thing.