在 TypeScript 中實作一個堆疊安全的 Future；為什麼延遲鏈會引起 s？
我正在根據 https://github.com/scalaz/scalaz/blob/series/7.2.x/concurrent/src/main/scala/scalaz/concurrent/Future.scala 在 TypeScript 中實現一個棧安全的 Future，並且已經幾乎成功，還差最後一個細節：同步延遲計算的鏈仍然沒有使用固定的棧空間，我怎麼也弄不明白自己哪裡做錯了。
我已將實作抽取出來，它是 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 中的實現確實如此。
任何幫助都將不勝感激，如果有任何需要澄清的地方也請告訴我！我知道這不是一個容易理解的代碼量，儘管如此，我已經嘗試從實際實現中刪除盡可能多的冗餘，以產生一個最小可重現的示例。
編輯，12月15日：結果顯示，Scalaz 中的實現對同步延遲計算不是堆疊安全的；我只是測試它的程式碼中犯了一個錯誤。
答案＃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);
+}