Mutual recursion of adjacent function statements

[rakudrama]

Dart does not support mutual recursion of functions declared in blocks (aka function-statements)

In this respect Dart is inferior to almost every other language that has a decent functional subset (including Python and JavaScript).

One solution would be for adjacent function-statements come into scope together to allow mutually recursion.

I am opening this feature request as Issue #315 could be narrowly construed to be concerned with the mismatch between the language and the specification.

The work-around are all painful:

W1. Use global functions - this pollutes the top level namespace, requires the programmer to manually lambda-lift the closed-over values and to manually box closed-over mutated variables. The code has to be moved out of the current function/method body to somewhere else in the file.

W2. Use a class with mutually recursive methods. This also pollutes the top level namespace and requires manual lambda-lifting or the extra hand-written code of a constructor.

W3. Use local variables and assign them with closures. This has the problem that the variables are not guarantee to not change. The reader of the code would be justifiably nervous that some tricky control flow might be implemented by a second assignment to one of the variables. This version also pollutes the global namespace with typedefs if the local variables are to be declared with a function type.

When you are writing a program you don't necessarily anticipate mutual recursion. When the need arises you have to refactor your program. It is really the job of a compiler to do the leg-work involved in these work-arounds, and a compiler is better situated to choose the implementation strategy depending on the characteristics of the mutually recursive functions.

The proposal is that adjacent function-statements come into scope together to allow mutually recursion.
The grouping of the function-statements can be expressed in the grammar.
Breaking the mutual recursion at labels or other statements is a simple way to ensure that there is no possibility of intermediate half-initialized state visible to the programmer while giving the compiler maximum latitude for implementation.

What follows is an example of a function that I believe should work in Dart and I would not need to rewrite in some awkward way if I was using Python or JavaScript.

/** Format nested lists, with strings in quotes. */
format(object, [prefix = '\n', suffix = '\n', open = '[', close = ']', comma = ', ']) {
  var fragments = [];
  void emit(e) { fragments.add(e); }

  void walkObject(o) {
    if (o == null) {
      emit('null');
    } else if (o is String) {
      emit("'$o'");
    } else if (o is List) {
      walkList(o);
    } else {
      emit('$o');
    }
  }
  void walkList(List xs) {
    emit(open);
    var sep = '';
    for (var x in xs) {
      emit(sep);
      sep = comma;
      walkObject(x);
    }
    emit(close);
  }

  emit(prefix);
  walkObject(object);
  emit(suffix);
  return Strings.concatAll(fragments);
}

[rakudrama]

Another case where grouped functions coming into scope together would be useful is in callback-based asynchronous programming.

I might like to compose a sequence of asynchronous calls in helper function:

threeSteps(arg, finished) {
  asyncApi1(arg1, (result1) {
      asyncApi2(result1, (result2) {
          asyncApi3(result2, finished);
        });
    });
}

In practice, the nesting rapidly gets out of hand, and the calls often require some preparation statements (for example, in IndexedDB programming, there are success and error callbacks which are attached to a request object, i.e. at least three statements per step.

So I'd like to name each step:

threeSteps(arg, finished) {
  step1(arg1) {
    asyncApi1(arg1, step2);
  }
  step2(result1) {
    asyncApi2(result1, step3);
  }
  step3(result2) {
    asyncApi3(result2, finished);
  }
  step1(arg);
}

I can't do this currently. The scoping rules force me to invert the
sequence which makes the program read out-of-order.

threeSteps(arg, finished) {
  step3(result2) {
    asyncApi3(result2, finished);
  }
  step2(result1) {
    asyncApi2(result1, step3);
  }
  step1(arg1) {
    asyncApi1(arg1, step2);
  }
  step1(arg);
}

The program now is a mish-mash of forward code (function bodies and where I chose not to introduce new names) and backward code. The scoping rules make it too difficult to fluidly change between large expressions and explicit named steps.

[gbracha]

We decided not to support this for now.

---

Set owner to @gbracha.
Added this to the Later milestone.
Added Accepted label.

[gbracha]

Issue #5390 has been merged into this issue.

[kasperl]

Removed this from the Later milestone.
Added Oldschool-Milestone-Later label.

[kasperl]

Removed Oldschool-Milestone-Later label.