Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Mutual recursion of adjacent function statements #5339

Open
rakudrama opened this issue Sep 20, 2012 · 5 comments
Open

Mutual recursion of adjacent function statements #5339

rakudrama opened this issue Sep 20, 2012 · 5 comments
Assignees
Labels
area-language New language issues should be filed at https://github.com/dart-lang/language type-enhancement A request for a change that isn't a bug

Comments

@rakudrama
Copy link
Member

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
Copy link
Member Author

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
Copy link
Contributor

gbracha commented Nov 6, 2012

We decided not to support this for now.


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

@gbracha
Copy link
Contributor

gbracha commented Nov 6, 2012

Issue #5390 has been merged into this issue.

@kasperl
Copy link

kasperl commented Jul 10, 2014

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

@kasperl
Copy link

kasperl commented Aug 4, 2014

Removed Oldschool-Milestone-Later label.

@rakudrama rakudrama added Type-Enhancement area-language New language issues should be filed at https://github.com/dart-lang/language labels Aug 4, 2014
@kevmoo kevmoo added P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug and removed accepted labels Feb 29, 2016
@lrhn lrhn removed the P2 A bug or feature request we're likely to work on label Aug 31, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-language New language issues should be filed at https://github.com/dart-lang/language type-enhancement A request for a change that isn't a bug
Projects
None yet
Development

No branches or pull requests

6 participants