I think that you basically can’t, in JavaScript. Or, more accurately: I can’t think of a way to do it.[1]
Oh, this is a case for WeakMaps right?
const MemoCache = new WeakMap();
function memoize(f, x) {
const cache = MemoCache.get(f) || new Map()
MemoCache.set(f, cache)
if (!cache.has(x)) {
cache.set(x, f(x))
}
return cache.get(x);
}
Oh wait:
1. You could create a global memoization map keyed on the function that you’re calling, but this would actually have different semantics than I’m imagining. If I said `memoize(f, 1) + memoize(f, 1)` I would expect those to each invoke `f`, because instances of `memoize` shouldn’t share results. Why not? Because this is a fake example, and a global memoization is a different (easier!) thing than per-call-site memoization.
Like I get what you're saying but you could just cache the call site too?
const MemoCache2 = new WeakMap();
function memoize2(f, x) {
const callsite = new Error().stack
const macro_cache = MemoCache2.get(f) || {};
const micro_cache = macro_cache[callsite] || new Map();
macro_cache[callsite] = micro_cache;
MemoCache2.set(f, macro_cache)
if (!micro_cache.has(x)) {
micro_cache.set(x, f(x))
}
return micro_cache.get(x);
}
I admit that this is something of a trickery though, but I mean, it's trickery specifically to work around that this person doesn't want to write `const my_f1 = memoize(f), my_f2 = memoize(f)` in some location on the screen. Precisely because people who write JavaScript are not accustomed to macros, they are not expecting `memoize(f, 1) + memoize(f, 1)` to be a proper memoization expression, they aren't expecting weird stuff with weakmaps and inspecting stack traces to identify call sites and all that.
I'm intrigued on why you would want those two calls to memoize separately? I'm sure there are reasons it could be needed, such that I'm not trying to argue against it. Genuinely curious to see a situation it would be desired.
You point out a good general problem that I find when blogging -- like, you don't want this, right? The whole premise is absurd; the point is not to memoize an expression, but rather to demonstrate that you can share values between compile-time and runtime. But in order to do this you need some specific example of the idea so that readers have something concrete to hold onto and generalize from. And then the difficulty is trying to present that specific example in a way that gets the general idea across, right, without the reader overfitting to the specific example you presented. It's hard! I don't think this one really succeeded.
I call that the curse of examples. Often conflated with "being in the weeds." Is frustrating, as people will jump on you with the X-Y problem style discussions. Which, fair that that is sometimes apt. Probably more often than makes sense, honestly.
Still, I did the callout that I did not mean that as an argument on if they really wanted it because I think it is fair to explore the intent as stated. And I appreciate how hard it is to make examples.
To your credit, you did explicitly call out your example in the blog post as something you wouldn't _actually_ want to do, so it didn't bother me. I've found that I'm more receptive to contrived examples to demonstrate a point if they aren't trying to hide the fact that they're contrived, so if I'm trying to convey a concept via example, sometimes I'll lean into the fact that the example is unrealistic to make it clear that the lack of utility shouldn't distract from the idea. As a silly example of this (see what I did there?), I might implement a trait with a `len` method that always returns 0 on strings to show how to resolve ambiguity when adding a method with name that a type already has in Rust.
a more plausible example than memoization is something like a polymorphic inline cache, where the cache can be very small and therefore fast to search but tends to be different at different callsites
Makes sense, I was thinking this is largely recreating L2 caches and such. Where you don't mind that they would memoize the same data, but the expectation is more that each caller would have a small subset they are specifically using over and over.
Sometimes it's nice to abstract a place where you need the answer from the way you determine the answer; that's basically why functions exist in the first place! Later on, if you decide that you want to tweak the way the implementation works, you don't need to do it literally everywhere.
i think reflecting on the stack is a valid solution to the problem and one that henry probably didn't think of. technically i think you need to extract just the first frame of the stack though. also reflection is often slow so it wouldn't be surprising if this ended up being a solution that was too slow to be useful
this is a very funny way to do this, thanks! i was thinking of using the (deprecated but still widely supported(?)) `caller` property but was sad that it wouldn't admit multiple memoization dictionaries per calling function (also wouldn't work at the top-level but, like, who cares). but using the stack trace is great.
i mean, you know, this isn't really... this isn't really a thing that you would ever want to do, but i am glad that life found a way
Comments
Oh, this is a case for WeakMaps right?
Oh wait:Like I get what you're saying but you could just cache the call site too?
I admit that this is something of a trickery though, but I mean, it's trickery specifically to work around that this person doesn't want to write `const my_f1 = memoize(f), my_f2 = memoize(f)` in some location on the screen. Precisely because people who write JavaScript are not accustomed to macros, they are not expecting `memoize(f, 1) + memoize(f, 1)` to be a proper memoization expression, they aren't expecting weird stuff with weakmaps and inspecting stack traces to identify call sites and all that.I'm intrigued on why you would want those two calls to memoize separately? I'm sure there are reasons it could be needed, such that I'm not trying to argue against it. Genuinely curious to see a situation it would be desired.
You point out a good general problem that I find when blogging -- like, you don't want this, right? The whole premise is absurd; the point is not to memoize an expression, but rather to demonstrate that you can share values between compile-time and runtime. But in order to do this you need some specific example of the idea so that readers have something concrete to hold onto and generalize from. And then the difficulty is trying to present that specific example in a way that gets the general idea across, right, without the reader overfitting to the specific example you presented. It's hard! I don't think this one really succeeded.
I call that the curse of examples. Often conflated with "being in the weeds." Is frustrating, as people will jump on you with the X-Y problem style discussions. Which, fair that that is sometimes apt. Probably more often than makes sense, honestly.
Still, I did the callout that I did not mean that as an argument on if they really wanted it because I think it is fair to explore the intent as stated. And I appreciate how hard it is to make examples.
To your credit, you did explicitly call out your example in the blog post as something you wouldn't _actually_ want to do, so it didn't bother me. I've found that I'm more receptive to contrived examples to demonstrate a point if they aren't trying to hide the fact that they're contrived, so if I'm trying to convey a concept via example, sometimes I'll lean into the fact that the example is unrealistic to make it clear that the lack of utility shouldn't distract from the idea. As a silly example of this (see what I did there?), I might implement a trait with a `len` method that always returns 0 on strings to show how to resolve ambiguity when adding a method with name that a type already has in Rust.
a more plausible example than memoization is something like a polymorphic inline cache, where the cache can be very small and therefore fast to search but tends to be different at different callsites
Makes sense, I was thinking this is largely recreating L2 caches and such. Where you don't mind that they would memoize the same data, but the expectation is more that each caller would have a small subset they are specifically using over and over.
If you knew the answer, why did you ask the question?
Sometimes it's nice to abstract a place where you need the answer from the way you determine the answer; that's basically why functions exist in the first place! Later on, if you decide that you want to tweak the way the implementation works, you don't need to do it literally everywhere.
I thought of an answer after asking. Still curious if there are others.
so am i! fuck you, lupire
fib(3), fib(2), fib(6), fib(1000000), fib(9), fib(2), fib(8),...
i think reflecting on the stack is a valid solution to the problem and one that henry probably didn't think of. technically i think you need to extract just the first frame of the stack though. also reflection is often slow so it wouldn't be surprising if this ended up being a solution that was too slow to be useful
this is a very funny way to do this, thanks! i was thinking of using the (deprecated but still widely supported(?)) `caller` property but was sad that it wouldn't admit multiple memoization dictionaries per calling function (also wouldn't work at the top-level but, like, who cares). but using the stack trace is great.
i mean, you know, this isn't really... this isn't really a thing that you would ever want to do, but i am glad that life found a way
it might be; you'd have to benchmark it to be sure
Stack is not the same as the callsite. (It’s technically also a non-standard property.)
Wait, can't you just set the property on the function object itself to accomplish this?