如何获得打字稿来执行尾部递归优化？

Question

const isPositive = (n: number) => n > 0;

function fitsIn(dividend: number,
                divisor: number,
                count: number,
                accum: number): number {
  if (accum + divisor > dividend) {
    return count;
  }
  return fitsIn(dividend, divisor, count + 1, accum + divisor);
}

function divide(dividend: number, divisor: number): number {
  let timesFits = fitsIn(Math.abs(dividend), Math.abs(divisor), 0, 0);
  return isPositive(dividend) === isPositive(divisor) ? timesFits : -timesFits;
}

console.log(divide(10, 3));
// 3

console.log(divide(-2147483648, -1));
// RangeError: Maximum call stack size exceeded

console.log(divide(10000, 1));
// RangeError: Maximum call stack size exceeded

我尝试在严格模式下使用Typescript 4.6.2运行此代码，这导致堆栈溢出。递归调用是在功能的末尾，积累是在递归功能调用中完成的。是否应该为尾部递归优化此代码吗？应该更改什么以使尾随递归优化发生？

Answer 1

Typescript不会优化尾部递归功能。请参阅 Microsoft/typeScript＃32743 提供权威答案。

通常，JavaScript中的术语“尾声呼叫优化”表示将尾部回复功能重写为迭代版本。这与“尾声消除”有所不同，这通常意味着保持递归，但要重写当前的堆栈框架，而不是将新的堆栈框架推向堆栈。如果您关心的只是堆栈的增长，则两者的行为也相似，但是通常以高于尾巴呼叫消除的抽象水平进行尾声优化。

---

如果您建议使用Typescript empasion 尾部调用优化作为绩效改进，那么这与打字稿的设计目标。一般而言，如果您为目标运行时环境编写一些句法正确的JavaScript，则编译器将发射该代码为IS。打字稿不应该优化您的JavaScript，而只是发出。因此，没有机会自己做到这一点。

---

另一方面，您可能正在谈论正确的尾巴呼叫消除，如《 Ecmascript 2015》（ES2015/ES6）规范中所介绍的。此功能的目的是使JavaScript运行时引擎可以检测到尾声，并且在这种情况下不会添加到呼叫堆栈中。

此功能从未被广泛采用； 当前只有基于Safari 。

当运行时引擎设计师考虑实施此功能时，他们会遇到可能的性能退化，开发人员混乱等问题。请参阅例如，此V8博客文章。大多数运行时引擎似乎都选择了一些更理想的版本的“等待观察”方法，例如一种语法可以明确选择进行这种消除。唯一的此类语法的明显建议多年来一直“不活跃”。因此，看起来“等待”的“等待”部分可能会永远持续下去。

虽然typeScript可以

---

无论好坏，看起来自动尾声消除是一个事实上的死亡功能，而打字稿不会为我们恢复它。

Answer 2

this 可能是您需要的东西：

type Tailcall <T> = { head: T, tail: () => Tailcall<T>, done: boolean } ;

const Tailcall = 
(done: boolean) => 
<T,> (head: T) => 
(tail: () => Tailcall<T>)
: Tailcall<T> => 
    
    ({ head: head, tail: tail, done: done }) as Tailcall <T> ;

Tailcall.done = 
<T,> (head: T)
: Tailcall<T> => 
    
    Tailcall (true) (head) 
        (() => { throw new Error("not implemented"); }) ;

Tailcall.call = 
<T,> (tail: () => Tailcall<T>)
: Tailcall<T> => 
    
    Tailcall (false) (null as any) (tail) ;

Tailcall.RUN = 
<T,> (self: Tailcall<T>)
: T => 
{
    let RUNNING = self;
    while (!RUNNING.done) 
    { RUNNING = RUNNING.tail (); }
    return RUNNING.head ;
} ;




const rem = 
(n: number, r: number)
: Tailcall<number> =>
    
    (n < r) ? Tailcall.done(n) 
    : Tailcall.call(() => rem(n-r, r)) ;


const pipeline = <T,> (x: T) => <R,> (f: (x: T) => R) => pipeline((f) (x)) ;

pipeline (rem(10000002,2))
    (Tailcall.RUN)
    (console.log); // 0, won't stack overflow

或以经典风格为：

class TailCall
<T> 
{
    constructor
    (
        public readonly isComplete: boolean ,
        public readonly result: T ,
        public readonly nextCall: () => TailCall<T> ,
    ) {} ;
    
    static done
    <T>(value: T)
    : TailCall<T> 
    {
        return new TailCall(true, value, () => { throw new Error("not implemented"); }) ;
    } ;
    
    static call
    <T>(nextCall: () => TailCall<T>)
    : TailCall<T> 
    {
        return new TailCall(false, null as any, nextCall);
    } ;
    
    invoke(): T 
    {
        let tailcall: TailCall<T> = this ;
        while (!tailcall.isComplete) 
        { tailcall = tailcall.nextCall() ; } ;
        return tailcall.result ;
    } ;
} ;

const rem = 
(n: number, r: number)
: TailCall<number> =>
    
    (n < r) ? TailCall.done(n) 
    : TailCall.call(() => rem(n-r, r)) ;

console.log(rem(10000001,2).invoke()); // wait, ans: 1

它们是此Java博客。

它只是将一个尾声转换为一段时间循环。

来自此 pure.ts 的代码。