Оптимизирована ли реализация факториального хвостового вызова (TCO) в стиле продолжения?

Вот две реализации факториала с этого сайта:

Оптимизированный хвостовой вызов (TCO):

function fact(n) {
  return tail_fact(n,1) ;
}

function tail_fact(n,a) {
  if (n == 0)
    return a ;
  else
    return tail_fact(n-1,n*a) ;
}

И тот, который переписан в стиле программирования продолжения (обратный вызов):

function fact(n,ret) {
  tail_fact(n,1,ret) ;
} 

function tail_fact(n,a,ret) {
  if (n == 0)
    ret(a) ;
  else
    tail_fact(n-1,n*a,ret) ;
}

Похоже, что в учебнике предполагается, что вторая версия также является TCO, но последнее, что возвращает вторая версия, это undefined, и ее вызов не находится в хвостовой позиции в соответствии с это руководство.

Однако также кажется, что return здесь вообще не используется, и, следовательно, нет необходимости создавать новый кадр в стеке с адресом для возврата. Так это то, что делает вторую реализацию TCO?


javascript tail-call-optimization
person Max Koretskyi    schedule 10.04.2017    source источник
comment
Node7 с --harmony_tailcalls не считает второй действительным для TCO. Аксель Раушмайер говорит нет, это не хвостовой вызов, потому что после него стоит неявный return undefined;. Я не уверен, что верю этой логике (но несогласие с Акселем Р. на самом деле очень нервирует меня); JS проводит различие между выходом из функции без return и return; или return undefined;, хотя результат их вызова одинаков. В какой-то момент я достану свой мачете и возьму на спек...   -  person T.J. Crowder    schedule 10.04.2017
comment
Если бы мы могли объявить возвращаемый тип tail_fact как void (неопределенный), мы могли бы тривиально увидеть, что return ничего не меняет (по-прежнему возвращает неопределенное) и что вызов находится в хвостовой позиции. К сожалению, у нас нет статических типов в JS, поэтому вам нужно явно добавить return и надеетесь, что он всегда возвращает undefined…   -  person Bergi    schedule 10.04.2017
comment
Я предполагаю, что умный интерпретатор мог бы также оптимизировать вторую версию - он помещает return <constant> после местоположения возврата, и когда следующий кадр стека делает то же самое, он знает, что возвращаемое значение будет проигнорировано, и может избежать создания внутреннего стека. кадры. Но, конечно же, спецификация ES6 этого не требует…   -  person Bergi    schedule 10.04.2017
comment
@ T.J.Crowder, спасибо, как вы обнаружили, что Node не считает второй действительным для совокупной стоимости владения?   -  person Max Koretskyi    schedule 10.04.2017
comment
@T.J.Crowder, @Bergi, спасибо, ребята, так что пока я могу сделать вывод, что, скорее всего, TCO в JS не гарантируется, верно?   -  person Max Koretskyi    schedule 10.04.2017
comment
@Maximus: попробовав это на fact(1e6, result => console.log(result)) и получив исключение переполнения стека. :-) А вот с первым - нет. Это вариант теста kangax для поддержки совокупной стоимости владения здесь.   -  person T.J. Crowder    schedule 10.04.2017
comment
@T.J.Crowder, умница :)   -  person Max Koretskyi    schedule 10.04.2017

Ответы (1)


arrow_upward
3
arrow_downward

Node7 с --harmony_tailcalls не считает второй действительным для TCO, но TCO не на 100% завершена в V8 (поэтому находится за флагом времени выполнения).

Аксель Раушмайер говорит нет , это не хвостовой вызов, потому что есть неявный return undefined; после этого:

Вызов функции bar() в следующем коде не находится в хвостовой позиции:

function foo() {
    bar(); // this is not a tail call in JS
}

Причина в том, что последним действием foo() является не вызов функции bar(), а (неявно) возврат undefined. Другими словами, foo() ведет себя так:

function foo() {
    bar();
    return undefined;
}

Вызывающие могут полагаться на то, что foo() всегда возвращает undefined. Если бы bar() вернула результат для foo() из-за оптимизации хвостового вызова, это изменило бы поведение foo.

Другими словами, в конце foo мы не можем просто перейти к bar, потому что bar может выдать return со значением, отличным от undefined, тогда как foo вообще не возвращает никакого значения (и, таким образом, вызов его гарантированно чтобы получить undefined). Что-то должно остаться позади (по крайней мере, на данный момент), когда мы вызываем bar, чтобы сказать, но не возвращать возвращаемое значение bar. Это что-то — кадр стека.

Теоретически движок JavaScript может передать какой-то флаг при вызове bar, говорящий себе отбрасывать любое значение, возвращаемое bar, тем самым разрешая совокупную стоимость владения в этом случае, но я не вижу ничего в спецификации, что делает это.

person T.J. Crowder    schedule 10.04.2017