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

Question

我正在基于 https://github.com/scalaz/scalaz/blob/series/7.2.x/concurrent/src/main/scala/scalaz/concurrent/Future.scala 在 TypeScript 中实现堆栈安全的 Future 并且几乎成功了，还有一个最后的细节缺失：同步延迟计算链仍然没有使用常量堆栈space，我终究无法弄清楚我做错了什么。

我已将作为 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 中的实现是~~ .

任何帮助将不胜感激，如果有任何需要澄清的地方，请告诉我！我知道这对 grok 来说不是微不足道的代码量，尽管我已经尝试从实际实现中删除尽可能多的废话以生成一个最小的可重现示例。

编辑，12 月 15 日：事实证明，Scalaz 中的实现对于同步延迟计算来说不是堆栈安全的；我只是在测试它的代码中犯了一个错误。

Answer 1

最后我决定除了接受所有延期期货实际上被延期之外没有解决这个问题的好方法:

diff --git a/packages/alfa-future/src/future.ts b/packages/alfa-future/src/future.ts
index 8a9d11ec..faf7863f 100644
--- a/packages/alfa-future/src/future.ts
+++ b/packages/alfa-future/src/future.ts
@@ -135,7 +135,7 @@ class Defer<T> extends Future<T> {
   }

   public then(callback: Callback<T>): void {
-    this._continuation(callback);
+    this._continuation(value => defer(() => callback(value)));
   }

   public flatMap<U>(mapper: Mapper<T, Future<U>>): Future<U> {
@@ -169,7 +169,9 @@ namespace Defer {
     }

     public then(callback: Callback<T>): void {
-      this._continuation(value => this._mapper(value).then(callback));
+      this._continuation(value =>
+       defer(() => this._mapper(value).then(callback))
+      );
     }

     public flatMap<U>(mapper: Mapper<T, Future<U>>): Future<U> {
@@ -234,3 +236,7 @@ namespace Suspend {
     }
   }
 }
+
+async function defer<T>(thunk: Thunk<T>): Promise<T> {
+  return Promise.resolve().then(thunk);
+}

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

Implementing a stack-safe Future in TypeScript; why are deferred chains causing stack overflows?

stack-overflow

future

typescript