[HN Gopher] Quote-unquote "macros"
___________________________________________________________________
Quote-unquote "macros"
Author : ianthehenry
Score : 50 points
Date : 2024-08-12 17:40 UTC (1 days ago)
(HTM) web link (ianthehenry.com)
(TXT) w3m dump (ianthehenry.com)
| anonymoushn wrote:
| Rust macros are sort of sufficient to do the kind of rewriting
| mentioned, but it's maybe cheating because you have to annotate
| the function with the macro which allows the macro to mangle the
| whole function body.
| kragen wrote:
| yeah, i don't think that's valid because it turns a local
| transformation into a global transformation (sort of local, but
| only to the entire top-level function, which can be arbitrarily
| large)
|
| if you're willing to do the global transformation yourself
| instead of enlisting the computer to do it for you, you don't
| even need macros at all; you can do that with henry's example:
| const resultMap = new Map();
|
| above the function
| crdrost wrote:
| > How do you implement `memoize`?
|
| > 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.
| kragen wrote:
| 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
| ianthehenry wrote:
| 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
| kragen wrote:
| it might be; you'd have to benchmark it to be sure
| taeric wrote:
| 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.
| kragen wrote:
| 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
| taeric wrote:
| 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.
| ianthehenry wrote:
| 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.
| taeric wrote:
| 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.
| MathMonkeyMan wrote:
| Programmer uses lisp macro to invent new keyword. It's a
| beautiful thing.
| dools wrote:
| ""macros""
| 29athrowaway wrote:
| Macros are an unmaintainable mess.
| deathanatos wrote:
| In the associated article linked to at "Leaving aside the
| absurdity of computing Fibonacci numbers recursively,"[1] (which,
| yes, I agree), we list the various algorithms as (roughly):
| how to fibonacci space complexity time complexity
| ------------------------- ---------------- ---------------
| insane recursion exponential exponential
| memoized insane recursion linear linear
|
| The space complexity of "insane recursion" without memoization is
| the maximum stack-depth; the worst case stack is,
| fib(n) fib(n-1) fib(n-2) ... fib(1)
|
| Which is _n_ stack frames (and the stack frames are of constant
| size); the space complexity of the whole thing is thus linear in
| the size of _n_. (While the call tree is itself exponential in
| size, the memory required is only the depth of that tree, since
| we can 't call fib(n-1) & fib(n-2) simultaneously[2].
|
| (The time complexity is, of course, exponential, and I agree with
| the "insane" moniker. I also like your comment elsewhere in this
| thread about people hyperfocusing on the example and missing the
| larger point of the article ... and I'm so sorry but I've been
| sniped by this.)
|
| [1]: https://ianthehenry.com/posts/fibonacci/
|
| [2]: the little demons in my mind are now trying to scheme up an
| insaner recursion that attempts this. Threads maybe?
___________________________________________________________________
(page generated 2024-08-13 23:00 UTC)