Idris2Doc : Compiler.ES.TailRec

Compiler.ES.TailRec

(source)
Tail-call optimization.

Here is a lengthy explanation how this works at the
moment. Assume the following call graph of functions f1,f2,f3,f4 all
calling each other in tail call position:

```
      ------------ f2 ---- f4 (result)
     /          /     \
f1 ---- f1     /       -- f1
     \        /
      -- f3 --
```

First, a directed graph of all toplevel function calls
(incoming and outgoing) in tail-call position is created:

```idris
MkCallGraph $ fromList [(f1,[f1,f2,f3]),(f2,[f1,f4]),(f3,[f2])]
            $ fromList [(f1,[f1,f2]),(f2,[f1,f3]),(f3,[f1]),(f4,[f2])]
```

Mutually tail-recursive functions form a strongly connected
component in such a call graph: There is a (directed) path from every function
to every other function. Tarjan's algorithm is used to identify
these strongly connected components and grouping them in
a `List` of `List1`s.

A tail-recursive group of functions is now converted to an imperative
loop as follows: Let `obj={h:_, a1:_, a2:_, ...}`
be a Javascript object consisting
of a tag `h` and arguments `a1`,`a2`,... . `h` indicates, whether `obj.a1`
contains the result of the computation (`h = 0`) or describes
a continuation indicating the next function to be invoked, in which
case fields `a1`,`a2`,... are the function's arguments.
together with the necessary arguments. The group of mutually
recursive functions is now converted to a single switch statement
where each branch corresponds to one of the function.
Each function will be changed in such a way that instead of
(recursively) calling another function in its group it will return
a new object `{h:_, a1:_, ...}` with `h` indicating the next
function to call (the next branch to choose in the `switch`
statement and `a1`,`a2`,... being the next function's set of
arguments. The function and initial argument object will then
be passed to toplevel function `__tailRec`, which loops
until the object signals that we have arrived at a result.

Here is an example of two mutually tail-recursive functions
together with the generated tail-call optimized code.

Original version:

```javascript
function isEven(arg){
  switch (arg) {
    case 0  : return 1;
    default : return isOdd(arg - 1);
  }
}

function isOdd(arg){
  switch (arg) {
    case 0  : return 0;
    default : return isEven(arg - 1);
  }
}
```

The above gets converted to code similar to
the following.

```javascript
function tcOpt(arg) {
  switch(arg.h) {
  // former function isEven
  case 1: {
    switch (arg.a1) {
      case 0  : return {h: 0, a1: 1};
      default : return {h: 2, a1: arg.a1 - 1};
    }
  }
  // former function isOdd
  case 2: {
    switch (a1) {
      case 0  : return {h: 0, a1: 0};
      default : return {h: 1, a1: arg.a1 - 1};
    }
  }
}

function isEven(arg){
  return __tailRec(tcOpt,{h: 1, a1: arg})
}

function isOdd(arg){
  return __tailRec(tcOpt,{h: 2, a1: arg})
}
```

Finally, `__tailRec` is implemented as follows:

```javascript
  function __tailRec(f,ini) {
    let obj = ini;
    while(true){
      switch(obj.h){
        case 0: return obj.a1;
        default: obj = f(obj);
      }
    }
  }
```

While the above example is in Javascript, this module operates
on `NamedCExp` exclusively, so it might be used with any backend
where the things described above can be expressed.

Definitions

recordTcFunction : Type
  A (toplevel) function in a group of mutually tail recursive functions.

Totality: total
Visibility: public export
Constructor: 
MkTcFunction : Name->Int->ListName->NamedCExp->TcFunction

Projections:
.args : TcFunction->ListName
  Argument list
.exp : TcFunction->NamedCExp
  Function's definition
.index : TcFunction->Int
  Function's index in its tail call group
This is used to decide on which branch to choose in
the next iteration
.name : TcFunction->Name
  Function's name
.name : TcFunction->Name
  Function's name

Visibility: public export
name : TcFunction->Name
  Function's name

Visibility: public export
.index : TcFunction->Int
  Function's index in its tail call group
This is used to decide on which branch to choose in
the next iteration

Visibility: public export
index : TcFunction->Int
  Function's index in its tail call group
This is used to decide on which branch to choose in
the next iteration

Visibility: public export
.args : TcFunction->ListName
  Argument list

Visibility: public export
args : TcFunction->ListName
  Argument list

Visibility: public export
.exp : TcFunction->NamedCExp
  Function's definition

Visibility: public export
exp : TcFunction->NamedCExp
  Function's definition

Visibility: public export
recordTcGroup : Type
  A group of mutually tail recursive toplevel functions.

Totality: total
Visibility: public export
Constructor: 
MkTcGroup : Int->SortedMapNameTcFunction->TcGroup

Projections:
.functions : TcGroup->SortedMapNameTcFunction
  Set of mutually recursive functions.
.index : TcGroup->Int
  Index of the group. This is used to generate a uniquely
named tail call optimized toplevel function.
.index : TcGroup->Int
  Index of the group. This is used to generate a uniquely
named tail call optimized toplevel function.

Visibility: public export
index : TcGroup->Int
  Index of the group. This is used to generate a uniquely
named tail call optimized toplevel function.

Visibility: public export
.functions : TcGroup->SortedMapNameTcFunction
  Set of mutually recursive functions.

Visibility: public export
functions : TcGroup->SortedMapNameTcFunction
  Set of mutually recursive functions.

Visibility: public export
recordFunction : Type
Totality: total
Visibility: public export
Constructor: 
MkFunction : Name->ListName->NamedCExp->Function

Projections:
.args : Function->ListName
.body : Function->NamedCExp
.name : Function->Name
.name : Function->Name
Visibility: public export
name : Function->Name
Visibility: public export
.args : Function->ListName
Visibility: public export
args : Function->ListName
Visibility: public export
.body : Function->NamedCExp
Visibility: public export
body : Function->NamedCExp
Visibility: public export
functions : Name->List (Name, (FC, NamedDef)) ->ListFunction
  Converts a list of toplevel definitions (potentially
several groups of mutually tail-recursive functions)
to a new set of tail-call optimized function definitions.
Only `MkNmFun`s are converted. Other constructors of `NamedDef`
are ignored and silently dropped.

Visibility: export