I'm in the process of implementing a stack-safe Future in TypeScript based on https://github.com/scalaz/scalaz/blob/series/7.2.x/concurrent/src/main/scala/scalaz/concurrent/Future.scala and have almost succeeded, with one final detail missing: Chains of synchronous deferred computations are still not using constant stack space and I cannot for the life of me figure out what I'm doing wrong.
I've extracted the implementation, which is part of https://github.com/siteimprove/alfa, to a single code snippet for inspection:
// 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)
);
}
}
}
}
Besides Future, the code above also defines some additional classes used in the implementation of Future: Either and Trampoline. Given the above implementation, this code will cause a stack overflow:
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);
The first obvious question would of course be: Why would one make a deferred computation that resolves synchronously? It's true that had we instead used Future.now(0) and Future.now(i + 1), the code would run just fine. The point is however that the Future should be stack-safe regardless of whether we resolve deferred computations synchronously or asynchronously and indeed the implementation in Scalaz is.
Any help would be greatly appreciated and do let me know if anything needs clarification! I know it's not a trivial amount of code to grok, though I've tried to remove as much cruft as possible from the actual implementation in order to produce a minimal reproducible example.
Edit, Dec 15: As it turns out, the implementation in Scalaz is not stack-safe for synchronous deferred computations; I just made a mistake in the code that tested it.
In the end I decided that there was no good way to solve this problem other than accepting that all deferred futures actually be deferred:
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);
+}