Is there a way to enable Tail Recursion Optimization in TypeScript?

Question

Is there a way to enable Tail Recursion Optimization in TypeScript?

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 attempted to execute this code using TypeScript 4.6.2 in Strict Mode and encountered a stack overflow error. The issue seems to be related to the recursive nature of the function combined with accumulation within each recursive call. Is there a way to optimize this code for tail recursion? What modifications are needed to achieve tail recursion optimization?

javascript typescript optimization compiler-optimization tail-recursion

Answer 1

Answer №1

When it comes to TypeScript, optimizing tail-called recursive functions is not on the cards. For more information, refer to microsoft/TypeScript#32743.

In JavaScript, 'tail call optimization' typically involves converting a tail-recursive function into an iterative version. This differs slightly from 'tail call elimination,' where recursion is maintained but the current stack frame is rewritten instead of creating a new one. While both methods appear similar in terms of stack growth, optimization generally operates at a higher level than elimination.

If you are considering suggesting that TypeScript should incorporate 'tail call optimization' for performance gains, it goes against TypeScript's design principles. The compiler aims to emit your code as it is written, without optimizing or altering it. Therefore, automatic optimization is not within TypeScript's scope.

Alternatively, you might be referring to 'proper tail call elimination' introduced in ECMAScript 2015 (ES6). Although this feature was intended to prevent adding to the call stack with tail calls, its adoption has been limited, primarily observed in Safari-based browsers. Runtime engine developers encountered challenges like potential performance issues and user confusion when implementing this feature, leading many engines to take a cautious approach. As of now, there is no concrete proposal for explicit syntax to enable such eliminations.

While it is technically feasible for TypeScript to downlevel proper tail call elimination into a form of tail call optimization, similar limitations would likely arise, prompting the team to refrain from pursuing it.

In conclusion, automatic tail call elimination seems to be inactive in the current landscape, with TypeScript showing no intentions to revive this feature.

Answer 2

When it comes to TypeScript, optimizing tail-called recursive functions is not on the cards. For more information, refer to microsoft/TypeScript#32743.

In JavaScript, 'tail call optimization' typically involves converting a tail-recursive function into an iterative version. This differs slightly from 'tail call elimination,' where recursion is maintained but the current stack frame is rewritten instead of creating a new one. While both methods appear similar in terms of stack growth, optimization generally operates at a higher level than elimination.

If you are considering suggesting that TypeScript should incorporate 'tail call optimization' for performance gains, it goes against TypeScript's design principles. The compiler aims to emit your code as it is written, without optimizing or altering it. Therefore, automatic optimization is not within TypeScript's scope.

Alternatively, you might be referring to 'proper tail call elimination' introduced in ECMAScript 2015 (ES6). Although this feature was intended to prevent adding to the call stack with tail calls, its adoption has been limited, primarily observed in Safari-based browsers. Runtime engine developers encountered challenges like potential performance issues and user confusion when implementing this feature, leading many engines to take a cautious approach. As of now, there is no concrete proposal for explicit syntax to enable such eliminations.

While it is technically feasible for TypeScript to downlevel proper tail call elimination into a form of tail call optimization, similar limitations would likely arise, prompting the team to refrain from pursuing it.

In conclusion, automatic tail call elimination seems to be inactive in the current landscape, with TypeScript showing no intentions to revive this feature.

Answer 3

Answer №2

Check this out - it might be exactly what you're looking for:

function 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, no stack overflow here

Alternatively, you can also explore this classic-style implementation:

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()); // output: 1

These implementations are based on tail recursion concepts discussed in this Java blog.

The code is sourced from pure.ts.

Answer 4

Check this out - it might be exactly what you're looking for:

function 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, no stack overflow here

Alternatively, you can also explore this classic-style implementation:

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()); // output: 1

These implementations are based on tail recursion concepts discussed in this Java blog.

The code is sourced from pure.ts.

Is there a way to enable Tail Recursion Optimization in TypeScript?

Answer №1

Answer №2

Similar questions

"Discover the power of D3.JS with three dazzling charts on a single page, plus a host of additional

Steps for choosing the nth HTML row with jQuery

Encountered an issue with the Mongoose Schema method: The model method is not recognized as a

React: a versatile and type-specific onChange() function

How does Backbone.js tackle error handling when receiving messages from Rails?

Successfully resolving the API without encountering any response errors, even after sending a response

the process of accessing information from a service in an Angular Typescript file

Why did the homepage load faster than the app.component.ts file?

Encountering a DOM exception with React 16.6 due to lazy loading/Susp

Displaying time text in input element due to browser bug

WordPress: Issue with Dropdown onchange Event Not Triggering

Assign custom keys to request object parameters before reaching the controller in the map

`req.user` seems to be unresolved, but it is actually defined

How to automatically set the radio button as "checked" with Javascript upon loading the page

Utilize the 'response.download' method to retrieve unique data not typically expected for a given request

Can we selectively execute certain tests in Cypress using support/index.js?

Identify the page search function to reveal hidden content in a collapsible section

Exploring the Possibilities of Greensock within Meteor Templates

Different ways to display a static content list using Vue's named slots

Utilizing the @keypress event handler in VueJS