javascript - How can I get TypeScript to perform Tail Recursion Optimization? - Stack Overflow

admin管理员组

文章数量:1401780

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

I tried running this code with TypeScript 4.6.2 in Strict Mode and it caused the stack to overflow. The recursive call is at the end of the function and the accumulation is done inside the recursive function calls. Shouldn't this code be optimized for tail recursion? What should be changed to get tail recursion optimization to occur?

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

I tried running this code with TypeScript 4.6.2 in Strict Mode and it caused the stack to overflow. The recursive call is at the end of the function and the accumulation is done inside the recursive function calls. Shouldn't this code be optimized for tail recursion? What should be changed to get tail recursion optimization to occur?

• javascript
• typescript
• optimization
• piler-optimization
• tail-recursion

Share Improve this question Follow edited Apr 18, 2022 at 12:45 siria asked Apr 18, 2022 at 9:09 siriasiria 30955 silver badges88 bronze badges 1

• 1 Tail call optimization was introduced for types. TypeScript does not optimize your code. – k.tten Commented Apr 18, 2022 at 13:49

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 7

TypeScript does not optimize tail-called recursive functions. See microsoft/TypeScript#32743 for an authoritative answer.

Usually the term "tail call optimization" in JavaScript denotes rewriting a tail-recursive function to an iterative version. This differs somewhat from "tail call elimination" which usually means keeping the recursion but rewriting the current stack frame instead of pushing a new one onto the stack. Both behave similarly from the outside if all you care about is stack growth, but tail call optimization generally happens at a level of abstraction higher than tail call elimination.

---

If you are suggesting that TypeScript implement tail call optimization as a performance improvement, that's not something that fits with TypeScript's design goals. Generally speaking if you write some code which is syntactically correct JavaScript for your target runtime environment, the piler will emit that code as-is. TypeScript isn't supposed to optimize your JavaScript, just emit it. So there's no chance it would do this by itself.

---

On the other hand, you might be talking about proper tail call elimination, as introduced in the ECMAScript 2015 (ES2015/ES6) specification. This feature was intended so that JavaScript runtime engines would detect tail calls and not add to the call stack in such cases.

This feature was never widely adopted; currently only Safari-based browsers seem to consistently do this.

When runtime engine designers looked into implementing this, they ran into issues with possible performance degradation, developer confusion, etc. See this V8 blog post for example. Most runtime engines seem to have opted for a "wait-and-see" approach for some more desirable version of this, such as a syntax to explicitly opt in to such elimination. And the only notable proposal for such syntax has been "inactive" for years. So it looks like the "wait" part of "wait-and-see" might last forever.

While it would be possible for TypeScript to downlevel proper tail call elimination into something like tail call optimization, it would likely run into the same issues, and they have declined to do it.

---

For better or worse, it looks like automatic tail call elimination is a de-facto dead feature, and TypeScript is not going to revive it for us.

This might be the thing you need:

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

or this which is in classic style:

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

They're two type of TS mock by this java blog.

It just trans a tailcall into a while loop.

Codes from this pure.ts.

本文标签： javascriptHow can I get TypeScript to perform Tail Recursion OptimizationStack Overflow