如何使TypeScript执行尾递归优化？

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严格模式运行这段代码，导致堆栈溢出。递归调用在函数末尾，并在递归函数调用内部执行累加。难道这段代码不应该进行尾递归优化吗？应该如何更改以实现尾递归优化？

- siria

---

尾调用优化是为类型引入的。TypeScript不会优化您的代码。 - zenly

Answer 1

TypeScript不会对尾递归函数进行优化。有关权威答案，请参见microsoft/TypeScript#32743。

通常情况下，在JavaScript中，“尾调用优化”一词表示将尾递归函数重写为迭代版本。这与“尾调用消除”略有不同，后者通常意味着保持递归但重写当前堆栈帧，而不是将新堆栈帧推入堆栈。如果您只关心堆栈增长，两者的行为在外部看起来相似，但尾调用优化通常发生在比尾调用消除更高的抽象级别上。

---

如果您建议TypeScript实现尾调用优化作为性能提升，那么这不符合TypeScript的设计目标（链接1）。一般来说，如果您编写了一些针对目标运行时环境的语法正确的JavaScript代码，则编译器将按原样发出该代码。 TypeScript不应优化您的JavaScript，只需发出它。因此，它本身不会这样做。

---

另一方面，您可能正在谈论ECMAScript 2015（ES2015 / ES6）规范中引入的适当尾调用消除。该功能旨在使JavaScript运行时引擎检测到尾调用，并在这种情况下不向调用堆栈添加内容。但是，此功能从未被广泛采用；目前只有基于Safari的浏览器似乎始终如一地执行此操作。当运行时引擎设计人员研究实施此功能时，他们遇到了可能导致性能下降、开发人员混淆等问题。例如，请参见此V8博客文章。大多数运行时引擎似乎选择了“等待并观望”方法，以获得更理想的版本，例如语法来明确选择此类消除。而唯一一个值得注意的提议已经“停滞”多年。因此，看起来“等待”的部分可能会永远持续下去。

虽然TypeScript可以将downlevel的proper tail call消除转化为类似尾调用优化的形式，但很可能会遇到相同的问题，因此他们选择不这样做。

---

不管好坏，看起来自动尾调用消除已经成为一个事实上的死亡特性，而 TypeScript 不会为我们复活它。

- jcalz

---

非常感谢您的详细介绍，我从中学到了很多东西。但是问题可能是如何修改代码，使其在严格模式下的TypeScript 4.6.2中运行良好（不会出现堆栈溢出），就像这个链接中所示的那样，保持尾调用形式。 - undefined

Answer 2

这可能就是你需要的东西：

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

或者this，它是经典风格的。

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

这是一个由this java blog提供的两种类型的TS模拟。

它只是将尾调用转换为while循环。

代码来自pure.ts。

- ypa y yhm