在TypeScript中实现堆栈安全的Future；为什么延迟的链会导致堆栈溢出？

Question

我正在基于Future的TypeScript中实现堆栈安全https://github.com/scalaz/scalaz/blob/series/7.2.x/concurrent/src/main/scala/scalaz/concurrent/Future.scala，并且成功完成[[几乎，但缺少最后一个细节：同步延迟计算链仍未使用常量堆栈空间，我无法为自己的生活弄清楚我在做什么错。

我已将实现作为https://github.com/siteimprove/alfa的一部分提取到单个代码段中进行检查：

// Copyright © Siteimprove A/S
// https://github.com/siteimprove/alfa/blob/master/LICENSE.md

type Mapper<T, U = T> = (value: T) => U;

type Thunk<T> = () => T;

type Callback<T, R = void> = (value: T) => R;

type Continuation<T, R = void> = Callback<Callback<T, R>, R>;

interface Either<L, R> {
  isLeft(): this is Left<L>;
  isRight(): this is Right<R>;
  get(): L | R;
  either<T>(left: Mapper<L, T>, right: Mapper<R, T>): T;
  map<T>(mapper: Mapper<L | R, T>): Either<T, T>;
  flatMap<T>(mapper: Mapper<L | R, Either<T, T>>): Either<T, T>;
}

class Left<L> implements Either<L, never> {
  public static of<L>(value: L): Left<L> {
    return new Left(value);
  }

  private readonly _value: L;

  private constructor(value: L) {
    this._value = value;
  }

  public isLeft(): this is Left<L> {
    return true;
  }

  public isRight(): this is Right<never> {
    return false;
  }

  public get(): L {
    return this._value;
  }

  public either<T>(left: Mapper<L, T>): T {
    return left(this._value);
  }

  public map<T>(mapper: Mapper<L, T>): Either<T, T> {
    return new Left(mapper(this._value));
  }

  public flatMap<T>(mapper: Mapper<L, Either<T, T>>): Either<T, T> {
    return mapper(this._value);
  }
}

class Right<R> implements Either<never, R> {
  public static of<R>(value: R): Right<R> {
    return new Right(value);
  }

  private readonly _value: R;

  private constructor(value: R) {
    this._value = value;
  }

  public isLeft(): this is Left<never> {
    return false;
  }

  public isRight(): this is Right<R> {
    return true;
  }

  public get(): R {
    return this._value;
  }

  public either<T>(left: unknown, right: Mapper<R, T>): T {
    return right(this._value);
  }

  public map<T>(mapper: Mapper<R, T>): Either<T, T> {
    return new Right(mapper(this._value));
  }

  public flatMap<T>(mapper: Mapper<R, Either<T, T>>): Either<T, T> {
    return mapper(this._value);
  }
}

abstract class Trampoline<T> {
  public abstract step(): Either<Trampoline<T>, T>;

  public isDone(): boolean {
    return this instanceof Trampoline.Done;
  }

  public isSuspended(): boolean {
    return this instanceof Trampoline.Suspend;
  }

  public run(): T {
    let result = this.step();

    while (result.isLeft()) {
      result = result.get().step();
    }

    return result.get() as T;
  }

  public map<U>(mapper: Mapper<T, U>): Trampoline<U> {
    return this.flatMap(value => Trampoline.Done.of(mapper(value)));
  }

  public abstract flatMap<U>(mapper: Mapper<T, Trampoline<U>>): Trampoline<U>;
}

namespace Trampoline {
  export function done<T>(value: T): Trampoline<T> {
    return Done.of(value);
  }

  export function suspend<T>(thunk: Thunk<Trampoline<T>>): Trampoline<T> {
    return Suspend.of(thunk);
  }

  export function delay<T>(thunk: Thunk<T>): Trampoline<T> {
    return suspend(() => done(thunk()));
  }

  export class Done<T> extends Trampoline<T> {
    public static of<T>(value: T): Done<T> {
      return new Done(value);
    }

    private readonly _value: T;

    private constructor(value: T) {
      super();
      this._value = value;
    }

    public step(): Right<T> {
      return Right.of(this._value);
    }

    public run(): T {
      return this._value;
    }

    public flatMap<U>(mapper: Mapper<T, Trampoline<U>>): Trampoline<U> {
      return Suspend.of(() => mapper(this._value));
    }
  }

  export class Suspend<T> extends Trampoline<T> {
    public static of<T>(thunk: Thunk<Trampoline<T>>): Suspend<T> {
      return new Suspend(thunk);
    }

    private readonly _thunk: Thunk<Trampoline<T>>;

    private constructor(thunk: Thunk<Trampoline<T>>) {
      super();
      this._thunk = thunk;
    }

    public step(): Left<Trampoline<T>> {
      return Left.of(this._thunk());
    }

    public flatMap<U>(mapper: Mapper<T, Trampoline<U>>): Trampoline<U> {
      return Suspend.Bind.of(this._thunk, mapper);
    }
  }

  export namespace Suspend {
    export class Bind<S, T> extends Trampoline<T> {
      public static of<S, T>(
        thunk: Thunk<Trampoline<S>>,
        mapper: Mapper<S, Trampoline<T>>
      ): Bind<S, T> {
        return new Bind(thunk, mapper);
      }

      private readonly _thunk: Thunk<Trampoline<S>>;
      private readonly _mapper: Mapper<S, Trampoline<T>>;

      private constructor(
        thunk: Thunk<Trampoline<S>>,
        mapper: Mapper<S, Trampoline<T>>
      ) {
        super();
        this._thunk = thunk;
        this._mapper = mapper;
      }

      public step(): Either<Trampoline<T>, T> {
        return this._thunk()
          .flatMap(this._mapper)
          .step();
      }

      public flatMap<U>(mapper: Mapper<T, Trampoline<U>>): Trampoline<U> {
        return this._thunk().flatMap(value =>
          this._mapper(value).flatMap(mapper)
        );
      }
    }
  }
}

abstract class Future<T> {
  public step(): Future<T> {
    return this;
  }

  public listen(callback: Callback<T, Trampoline<void>>): void {
    let future = this.step();

    while (true) {
      const step = future.step();

      if (future === step) {
        return future.listen(callback);
      }

      future = step;
    }
  }

  public then(callback: Callback<T>): void {
    this.listen(value => Trampoline.done(callback(value)));
  }

  public map<U>(mapper: Mapper<T, U>): Future<U> {
    return this.flatMap(value => Future.Now.of(mapper(value)));
  }

  public abstract flatMap<U>(mapper: Mapper<T, Future<U>>): Future<U>;
}

namespace Future {
  export function now<T>(value: T): Future<T> {
    return Now.of(value);
  }

  export function defer<T>(continuation: Continuation<T>): Future<T> {
    return Defer.of(callback =>
      Trampoline.done(continuation(value => callback(value).run()))
    );
  }

  export function suspend<T>(thunk: Thunk<Future<T>>): Future<T> {
    return Suspend.of(thunk);
  }

  export function delay<T>(thunk: Thunk<T>): Future<T> {
    return suspend(() => now(thunk()));
  }

  export class Now<T> extends Future<T> {
    public static of<T>(value: T): Now<T> {
      return new Now(value);
    }

    private readonly _value: T;

    private constructor(value: T) {
      super();
      this._value = value;
    }

    public listen(callback: Callback<T, Trampoline<void>>): void {
      callback(this._value).run();
    }

    public flatMap<U>(mapper: Mapper<T, Future<U>>): Future<U> {
      return Suspend.of(() => mapper(this._value));
    }
  }

  export class Defer<T> extends Future<T> {
    public static of<T>(
      continuation: Continuation<T, Trampoline<void>>
    ): Defer<T> {
      return new Defer(continuation);
    }

    private readonly _continuation: Continuation<T, Trampoline<void>>;

    private constructor(continuation: Continuation<T, Trampoline<void>>) {
      super();
      this._continuation = continuation;
    }

    public listen(callback: Callback<T, Trampoline<void>>): void {
      this._continuation(callback);
    }

    public flatMap<U>(mapper: Mapper<T, Future<U>>): Future<U> {
      return Defer.Bind.of(this._continuation, mapper);
    }
  }

  export namespace Defer {
    export class Bind<S, T> extends Future<T> {
      public static of<S, T>(
        continuation: Continuation<S, Trampoline<void>>,
        mapper: Mapper<S, Future<T>>
      ): Bind<S, T> {
        return new Bind(continuation, mapper);
      }

      private readonly _continuation: Continuation<S, Trampoline<void>>;
      private readonly _mapper: Mapper<S, Future<T>>;

      private constructor(
        continuation: Continuation<S, Trampoline<void>>,
        mapper: Mapper<S, Future<T>>
      ) {
        super();
        this._continuation = continuation;
        this._mapper = mapper;
      }

      public listen(callback: Callback<T, Trampoline<void>>): void {
        this._continuation(value =>
          Trampoline.delay(() => this._mapper(value)).map(future =>
            future.listen(callback)
          )
        );
      }

      public flatMap<U>(mapper: Mapper<T, Future<U>>): Future<U> {
        return Suspend.of(() =>
          Bind.of(this._continuation, value =>
            this._mapper(value).flatMap(mapper)
          )
        );
      }
    }
  }

  export class Suspend<T> extends Future<T> {
    public static of<T>(thunk: Thunk<Future<T>>): Suspend<T> {
      return new Suspend(thunk);
    }

    private readonly _thunk: Thunk<Future<T>>;

    private constructor(thunk: Thunk<Future<T>>) {
      super();
      this._thunk = thunk;
    }

    public step(): Future<T> {
      return this._thunk();
    }

    public flatMap<U>(mapper: Mapper<T, Future<U>>): Future<U> {
      return Suspend.Bind.of(this._thunk, mapper);
    }
  }

  export namespace Suspend {
    export class Bind<S, T> extends Future<T> {
      public static of<S, T>(
        thunk: Thunk<Future<S>>,
        mapper: Mapper<S, Future<T>>
      ): Bind<S, T> {
        return new Bind(thunk, mapper);
      }

      private readonly _thunk: Thunk<Future<S>>;
      private readonly _mapper: Mapper<S, Future<T>>;

      private constructor(thunk: Thunk<Future<S>>, mapper: Mapper<S, Future<T>>) {
        super();
        this._thunk = thunk;
        this._mapper = mapper;
      }

      public step(): Future<T> {
        return this._thunk()
          .flatMap(this._mapper)
          .step();
      }

      public flatMap<U>(mapper: Mapper<T, Future<U>>): Future<U> {
        return this._thunk().flatMap(value =>
          this._mapper(value).flatMap(mapper)
        );
      }
    }
  }
}

除了Future，上面的代码还定义了在Future的实现中使用的一些其他类：Either和Trampoline。鉴于以上实现，此代码将导致堆栈溢出：
let n = Future.defer<number>(done => done(0));

for (let i = 0; i < 10000; i++) {
  n = n.flatMap(i => Future.defer(done => done(i + 1)));
}

n.then(console.log);

当然，第一个显而易见的问题是：为什么要进行一个延迟解析的同步解析？的确，如果我们改为使用Future.now(0)和Future.now(i + 1)，代码将运行良好。但是，要点是，无论我们是同步还是异步解析延迟的计算，Future都应该是堆栈安全的。[[实际上，Scalaz中的实现是。
任何帮助将不胜感激，如果有任何需要澄清的地方，请告诉我！我知道这不是琐碎的代码，尽管我已尝试从实际实现中删除尽可能多的杂项，以便产生最少的可重现示例。
Edit，Dec 15：事实证明，对于同步延迟计算，Scalaz中的实现对栈是安全的。我只是在测试它的代码中犯了一个错误。

我正在基于https://github.com/scalaz/scalaz/blob/series/7.2.x/concurrent/src/main/scala/scalaz/concurrent在TypeScript中实现堆栈安全的Future /Future.scala并具有...

Answer 1