Здравствуйте, CodingUnit, Вы писали:

CU>Я бы часть функций дописал или переписал в хвостово-рекурсивной манере, но continuationы не работают как надо. Думаю как произвести такие оптимизации чтобы CPS был возможен без использования tail операнда

Вообще использование CPS вопрос ключевой, это может помочь при реализации многих алгоритмов. Только проблема пока в том что компилятор не умеет обрабатывать рекурсивные лямбды. Я думаю можно провести оптимизацию и научить его рекурсивно вызывать лямбды без расхода стэка, вот что можно сделать:

Как известно лямбда состоит из след. частей:

private sealed class _N__N_lambda__4061__4193<T, TRes> : Function<TRes, TRes>
{
    // Fields
    private MutualDefinition2._N_closure_4073<T, TRes> _N_FoldRight_closure_4199;
    private MutualDefinition2._N_closure_4090<T, TRes> _N_loop_closure_4197;

    // Methods
    public _N__N_lambda__4061__4193(MutualDefinition2._N_closure_4090<T, TRes> _N_loop_closure_4197, MutualDefinition2._N_closure_4073<T, TRes> _N_FoldRight_closure_4199);
    public sealed override TRes apply(TRes racc);
}

и замыкание:

private sealed class _N_closure_4090<T, TRes>
{
    // Fields
    internal Function<TRes, TRes> _N_cont_4097; // <--- вот эту функцию компилятор вызывает рекурсивно
    internal T _N_head_4095;

    // Methods
    internal _N_closure_4090()
    {
    }
}

цикл выглядит так:

public sealed override TRes apply(TRes racc)
{
    return this._N_loop_closure_4197._N_cont_4097.apply(this._N_FoldRight_closure_4199._N_fold_4078.apply(this._N_loop_closure_4197._N_head_4095, racc));
}

это то что в алгоритме FoldRight представленном выше выглядит так: cont(fold(head, racc))

Здесь он вызывает функцию вглубь и естественно расходуется стэк, но cont в этом случае имеет два значения, сначала это x => x при первом вызове, далее это всегда экземпляр _N__N_lambda__4061__4193
Можно вот что сделать, в замыкание для такого рода функции добавить поле rec_lambda : _N__N_lambda__4061__4193
и устанавливать его, если функция ссылалась на этот экземпляр лямбды, иначе null

private sealed override apply_rec(racc : TRes) : TRes
{
    this._N_FoldRight_closure_4199._N_fold_4078.apply(this._N_loop_closure_4197._N_head_4095, racc); // убираем рекурсию
}

private sealed override TRes apply_rec(cont : _N__N_lambda__4061__4193, racc : TRes) : TRes
{
    def res =  cont.apply(racc); // вызываем функцию получая результат отложенной лямбды без рекурсивного вызова континуации
    if (cont._N_loop_closure_4197.rec_lambda != null) // если следующая функция это таже лямбда
       apply_rec(cont._N_loop_closure_4197.rec_lambda, res)  // запускаем этотже метод рекурсивно с лямбдой и результатом, компилятор должен это развернуть в цикл
    else
       cont._N_loop_closure_4197._N_cont_4097.apply(res) // иначе просто вызываем обычно      
}

public sealed override TRes apply(racc : TRes)
{
    apply_rec(this, racc) 
}

Эту оптимизацию надо проводить только для лямбд которые вызывают себя же, тогда рекурсивный вызов может не переполнить стэк и это даст реализовать поддержку использования CPS в языке без пресловутого tail опкода. Какие мысли?