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

"I'm encountering an issue with the discord.js module when I try to launch my bot using node. Any ideas on how

The functionality of jQuery binding is not functioning properly

Accessing JSON data stored locally and initializing it into a TypeScript variable within a React application

Challenges arising with the express search feature

Interacting with external domains through ajax queries

Creating a seamless vertical marquee of several images that continuously scroll from bottom to top without interruption can be achieved by following these

method for sorting labels in Select element in ReactJS

Altering the innerHTML of a <p> tag with a smooth transition

Acquire information from an Angular service and output it to the console

A step-by-step guide to displaying API data in a React frontend using functional components

Discovering a Match within a JavaScript Object and Array with the help of Jquery's Each

Contrast between utilizing a WebApp that connects to an API and one that relies on backend

Create a dropdown menu using a PDO query to populate the selectable options

Unable to incorporate node-vibrant into Angular 7 project

Launching a React project using the terminal - my step-by-step process

Basic inquiries concerning Vue.js and JavaScript

Is it possible to transfer files using web-bluetooth technology?

Create a data attribute object and assign to it the prop object received from the parent component

I'm encountering an issue with my function in Vuejs where it is only going through one loop before breaking out. How can I

Implementing a PHP button update functionality sans utilizing an HTML form