[Resolved] [Beyond] Optimize tail-calls in Fable AST

[alfonsogarciacaro]

RESOLVED: There are some difficulties in optimizing tail calls in Fable AST, for example optimization for JS requires the LabelStatement which is only present in Babel AST and a specific use of declared JS variables (let instead of var). For now we will leave the optimization to each language final step.

When @dbrattli started adapting Fable to compile to Python we initially suggested to use Babel AST because some important optimizations like tail-calls were done in the Fable2Babel step instead of FableTransforms. As this is proving to be not ideal and, if I'm not mistaken, currently both php and python PRs are working from the Fable AST, it makes sense to move the tail-call optimization to FableTransforms so Fable2Php and Fable2Python (and Fable2Rust?) can get it automatically.

The main reason originally to make the optimization in the Fable2Babel was because F# doesn't have a break statement, but it shouldn't be too problematic to add a Break of label: string option expression to the Fable AST, together with an optional label for While loops. In fact, @dbrattli also suggested to add back the Throw statement, so we could have something like SideEffect of (Break|Debugger|Throw).

What do you think? @ncave @dbrattli @thinkbeforecoding

[ncave]

@alfonsogarciacaro A good idea, I agree.

[dbrattli]

This sounds great. One of the problems of using the Babel AST is that it's not always easy to know the intent of the code e.g with classes vs object expressions and method calls vs property access. E.g with the code below it's hard to say if e is a class or an object. If it's an object I need to call e["System.Collections.IEnumerator.MoveNext"]() but if it's a class I should call e. System_Collections_IEnumerator_MoveNext(). The classes becomes quite complicated if I need to intercept attribute access for something that might be a method access (since I need to rewrite method names to not include . or `. etc. I would like classes to become Python classes and objects to become Python dictionary (or namedtuple).

export class Enumerator_Seq {
    constructor(f) {
        this.f = f;
    }
    toString() {
        const xs = this;
        const maxCount = 4;
        let i = 0;
        let str = "seq [";
        const e = getEnumerator(xs);
        try {
            while ((i < maxCount) ? e["System.Collections.IEnumerator.MoveNext"]() : false) {
                if (i > 0) {
                    str = (str + "; ");
                }
                str = (str + toString(e["System.Collections.Generic.IEnumerator`1.get_Current"]()));
                i = ((i + 1) | 0);
            }
            if (i === maxCount) {
                str = (str + "; ...");
            }
            return str + "]";
        }
        finally {
            e.Dispose();
        }
    }
    GetEnumerator() {
        const x = this;
        return x.f();
    }
    [Symbol.iterator]() {
        return toIterator(this.GetEnumerator());
    }
    ["System.Collections.IEnumerable.GetEnumerator"]() {
        const x = this;
        return x.f();
    }
}

Thus I'm trying (in parallel) to work directly from Fable AST to see if that makes things easier.

[thinkbeforecoding]

It is easier to get this kind of info in the Fable AST as long at it is not an import.
To fix this, it would require adding target information (is it a type, an instance property, a static function, a plain function ?) to the import node.
#2462

[dbrattli]

I btw. just discovered that the current TCO does not work with Python. Making closures within loops is tricky since closures close over variables, not values (ref: https://eev.ee/blog/2011/04/24/gotcha-python-scoping-closures/). I guess it's because Python does not have let or const.

Thus JS code like will not work with Python:

export function functionArguments(x_mut, f_mut) {
    functionArguments:
    while (true) {
        const x = x_mut, f = f_mut;
        if (!isEmpty(x)) {
            if (isEmpty(tail(x))) {
                return f(head(x)) | 0;
            }
            else {
                x_mut = tail(x);
                f_mut = ((arg) => (3 + f(arg)));
                continue functionArguments;
            }
        }
        else {
            throw new Error("empty list");
        }
        break;
    }
}

To make it work, the the arrow function ((arg) => (3 + f(arg))) needs to be outside the while-loop and called with the while -loop e.g:

def Functions_functionArguments(x_mut, f_mut):
    def get_lambda(f):
        return lambda arg=None: 3 + (f(arg))

    while True:
        (x, f) = (x_mut, f_mut)
        if not (is_empty(x)):
            if is_empty(tail(x)):
                return f(head(x))

            else:
                x_mut = tail(x)
                f_mut = get_lambda(f)
                continue

        else:
            raise Exception("empty list")

        break

I'm trying to figure how to deal with this in Fable2Python.fs.

[dbrattli]

This is btw complicated to get right wrt the variables captured by the closure, so I might decide to use a trampoline instead e.g:

class TailCall:
    def __init__(self, *args: Any, **kw: Any):
        self.args = args
        self.kw = kw

def tailrec(fn):
    def trampoline(bouncer) -> Any:
        while isinstance(bouncer, TailCall):
            args, kw = bouncer.args, bouncer.kw
            bouncer = fn(*args, **kw)

        return bouncer

    @functools.wraps(fn)
    def wrapper(*args: Any, **kw: Any) -> Any:
        return trampoline(fn(*args, **kw))

    return wrapper

@tailrec
def Functions_functionArguments(x, f):
    if not (is_empty(x)):
        if is_empty(tail(x)):
            return f(head(x))

        else:
            return TailCall(tail(x), lambda arg=None: 3 + (f(arg)))

    else:
        raise Exception("empty list")

It's not as fast as the while-loop, since there's the extra call and alloc of the special return type, but simpler to code.

[dbrattli]

I think I managed to find a way by appending the tc-args to any new function declared within a tail-call opportunity. E.g If xand f are the arguments, then I also append them as args with themselves as default values e.g f=f to make a new variable that captures the value and not the variable in the closure.

def function_arguments(x_mut, f_mut):
    while True:
        (x, f) = (x_mut, f_mut)
        if not (is_empty(x)):
            if is_empty(tail(x)):
                return f(head(x))

            else:
                x_mut = tail(x)
                f_mut = lambda arg=None, x=x, f=f: 3 + (f(arg))
                continue

        else:
            raise Exception("empty list")

        break