Implementation using Caches? (Edited from: Implementation using Lazy Lists?)
Closed this issue · 4 comments
I vaguely remember reading from some blog post that immutagen has asymptotic performance issues.
Edit: Which is well-documented in the README, kudos for that!
If you're interested here's a lazy list implementation that can be used in immutagen.
You don't have to use it, just sharing in case it's useful.
type LazyList<T> = Iterable<T> &
({ empty: true } | { empty: false; head: T; lazyTail: () => LazyList<T> });
const Empty: LazyList<never> = {
empty: true,
*[Symbol.iterator]() {},
};
const Cons = <T>(head: T, lazyTail: () => LazyList<T>): LazyList<T> => {
return {
empty: false,
head,
lazyTail,
*[Symbol.iterator]() {
yield head;
yield* lazyTail();
},
};
};
const ofGenerator = <Params extends any[], T>(
f: (...params: Params) => Generator<T>,
...params: Params
): LazyList<T> => {
const g = f(...params);
const cache: T[] = [];
function lazyListSlice(startIndex: number): LazyList<T> {
while (startIndex >= cache.length) {
const { done, value } = g.next();
if (done) {
return Empty;
}
cache.push(value);
}
return Cons(cache[startIndex], () => lazyListSlice(startIndex + 1));
}
return lazyListSlice(0);
};Motivating example demonstrating its capabilities:
function map<T, U>(ts: LazyList<T>, f: (t: T) => U): LazyList<U> {
if (ts.empty) {
return Empty;
}
return Cons(f(ts.head), () => map(ts.lazyTail(), f));
}
function merge(as: LazyList<number>, bs: LazyList<number>): LazyList<number> {
if (as.empty) {
return bs;
}
if (bs.empty) {
return as;
}
// Note: No eager `lazyTail` calls in recursive functions or it stackoverflows
const [a, alt] = [as.head, as.lazyTail];
const [b, blt] = [bs.head, bs.lazyTail];
if (a < b) {
return Cons(a, () => merge(alt(), bs));
}
if (a === b) {
return Cons(a, () => merge(alt(), blt()));
}
if (a > b) {
return Cons(b, () => merge(as, blt()));
}
throw new Error(`Numbers (${a}) and (${b}) are incomparable!`);
}
const smooth = (function () {
const smoothInstance = Cons(1, makeSmooth);
function makeSmooth(): LazyList<number> {
const smoothTimes = (n: number) =>
map(smoothInstance, (x: number) => x * n);
return merge(smoothTimes(2), smoothTimes(3));
}
return smoothInstance;
})();
const smoothList = [];
for (const i of smooth) {
if (i > 100000) {
break;
}
smoothList.push(i);
}
console.log(smoothList);
/*
[
1, 2, 3, 4, 6, 8, 9, 12, 16,
18, 24, 27, 32, 36, 48, 54, 64, 72,
81, 96, 108, 128, 144, 162, 192, 216, 243,
256, 288, 324, 384, 432, 486, 512, 576, 648,
729, 768, 864, 972, 1024, 1152, 1296, 1458, 1536,
1728, 1944, 2048, 2187, 2304, 2592, 2916, 3072, 3456,
3888, 4096, 4374, 4608, 5184, 5832, 6144, 6561, 6912,
7776, 8192, 8748, 9216, 10368, 11664, 12288, 13122, 13824,
15552, 16384, 17496, 18432, 19683, 20736, 23328, 24576, 26244,
27648, 31104, 32768, 34992, 36864, 39366, 41472, 46656, 49152,
52488, 55296, 59049, 62208, 65536, 69984, 73728, 78732, 82944,
93312,
... 1 more item
]
*/I vaguely remember reading from some blog post that immutagen has asymptotic performance issues.
Yes it does, but only for non-deterministic monads such as List. This is because generators in JavaScript can't be resumed from a specific position multiple times. Instead, we have to emulate this behavior by creating and replaying multiple generators. This behavior is described in the following StackOverflow answer, https://stackoverflow.com/a/56815335/783743.
If you're interested here's a lazy list implementation that can be used in immutagen.
Lazy lists won't be able to fix the inherent problem of JavaScript generators. In fact, it's impossible to fix that problem. You can't resume a JavaScript generator from a specific point more than once. It's an inherent flaw in the design of iterators. Hence, I'm closing this issue.
Thank you for your explanation and the link. The link was a great read.
Yes it does, but only for non-deterministic monads such as
List.
Just to make sure, does "non-deterministic monad" in this context mean "monads used to model non-deterministic behavior by computing all possible outcomes", as in this link?
Lazy lists won't be able to fix the inherent problem of JavaScript generators. ...
Apologies, I was mistaken when writing the issue. I should have said "caches", not "Lazy Lists".
I see now that Lazy Lists are mostly irrelevant in this context and used only to demonstrate the caching behavior.
I edited the name of this issue to better specify the intent.
I'm fine with this issue closed, but feel free to reopen this issue if it's worth discussing.
Just to make sure, does "non-deterministic monad" in this context mean "monads used to model non-deterministic behavior by computing all possible outcomes", as in this link?
Yes, that's precisely what it means.
Apologies, I was mistaken when writing the issue. I should have said "caches", not "Lazy Lists".
I see now that Lazy Lists are mostly irrelevant in this context and used only to demonstrate the caching behavior.
Caching won't help here. The problem is that once a JavaScript generator is advanced using .next you can never reset it to the same point again. Consider the following code.
function* pairs() {
const x = yield [10, 20, 30];
const y = yield [40, 50];
return [[x, y]];
}
const gen = pairs();
const xs = gen.next(); // xs = { done: false, value: [10, 20, 30] }
const ys = gen.next(xs.value[0]); // ys = { done: false, value: [40, 50] }
const zs = gen.next(ys.value[0]); // zs = { done: true, value: [[10, 40]] }As you can see, we first called gen.next() which started the execution of the generator and returned [10, 20, 30]. We then resumed the generator with the first of these values, i.e. 10, and got back the result [40, 50]. We again resumed the generator with the first of these values, i.e. 40, and got the final result [[10, 40]].
This is a deterministic execution. However, now we want to backtrack to the const y = yield [40, 50]; line in the generator function and resume the generator with the second value, i.e. 50, to get the second result [[10, 50]].
Unfortunately, there's no way to reset a JavaScript generator to a previous point. So, this is impossible to do. This problem can't be solved by lazy lists, caching, memoization, etc. It's an inherent problem of JavaScript generators.
Just to be clear, I 100% agree with your points and understand that JavaScript generators are inherently mutable and cannot be "augmented" to implement immutagen.
My intention was not patching generators to behave like immutagens, but rather using a cache to implement immutable objects like regens and immutagens in order to have a better asymptotic complexity.
Since apparently the example in the first message did a terrible job at expressing this point, I'll make a new issue when I do have a prototype of that working.
Thank you so much for your attention and letting me learn something new!