12 ms·

Quote-unquote "macros"

101 points by ianthehenry 2y ago

anonymoushn 2y ago
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 2y ago
  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 2y ago
> 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 2y ago
  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 2y ago
  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 2y ago
    it might be; you'd have to benchmark it to be sure
- taeric 2y ago
  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 2y ago
    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 2y ago
      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.
MathMonkeyMan 2y ago
Programmer uses lisp macro to invent new keyword. It's a beautiful thing.
- deleted 2y ago
  [deleted]
dools 2y ago
""macros""
29athrowaway 2y ago
Macros are an unmaintainable mess.
- fungiblecog 2y ago
  Substitute any non-trivial programming idiom for “macros” and that is true for some subset of working programmers.
deathanatos 2y ago
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/ 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?
- ianthehenry 2y ago
  ha thanks, you are absolutely right. i updated the table :)
  - lilyball 2y ago
    In that same article, you have some iterations 8 / 41 = 0.1951219 (8 + 41 = 49) / 8 = 6.125 (49 + 8 = 57) / 49 = 1.16326531 (57 + 49 = 106) / 57 = 1.85964912 (106 + 57 = 163) / 106 = 1.53773585 That second line is screwed up, which also screws up the subsequent lines. It should look like (41 + 8 = 49) / 41 = 1.19512195 which then means the line after that should be (49 + 41 = 90) / 49 = 1.83673469 and so on
    - ianthehenry 2y ago
      i think this is just very badly worded. the initial conditions are current=8, previous=41, not the other way around. i should make that more clear
cryptonector 2y ago
> Leaving aside the absurdity of computing Fibonacci numbers recursively Is it really absurd? If the compiler can turn it into iteration, then it's a big boy compiler. If not, then meh?
- lupire 2y ago
  Computing Fibonacci numbers iteratively is only slightly less absurd. It's `O(n)` for what should be an `O(log(n))` problem (`fib(n) = round ((phi^n - phi^-n)/(2phi-1))`).
  - cryptonector 2y ago
    Ay, yes, I was focused on the idea that I want my compilers to do TCO and other optimizations, so I missed the point.
    - ianthehenry 2y ago
      Eh, by recursion I meant specifically the exponential "fib(n - 1) + fib(n - 2)" flavored definition. If you're writing the linear-time algorithm and happen to do the iteration via tail recursion, I don't think there's anything absurd about that
markovs_gun 2y ago
I am going to be honest I didn't really understand what an eigenvalue was until reading this. I'd read the definition but like I didn't really understand why you'd care about that. This was a great article
- JHonaker 2y ago
  Did you post this on the wrong article?
  - disconcision 2y ago
    see the first link in the article, 'the absurdity of computing Fibonacci numbers recursively'
    - JHonaker 2y ago
      Ah, I see. I read the article, but not the links. I even searched for eigenvalue/eigenvector to see if I was crazy. The first linked article is very good. I always enjoy Ian’s work.
  - markovs_gun 2y ago
    Woops I clicked on the first link and it was so long I forgot that it wasn't the originally linked article
pxc 2y ago
Wow. I haven't really played with Lisp since college. But I just started reading The Little Schemer with some friends, and hope to move on to SICP some time this year or next. This blog post made me a little dizzy, but also a little excited about what I'm hoping to explore with these lessons.
tyg13 2y ago
Every time I see a post from Lisp fans about macros, I want to be amazed, but I always just walk away confused. I can tell there's something interesting in there, but the quote-unquote-quasiquote syntax is just so dense that my brain is incapable of comprehending it.
- fungiblecog 2y ago
  To get it you really need to learn enough lisp (not a lot) and try implementing a non-trivial macro.
  - Zambyte 2y ago
    Yep, they are a foreign idea in pretty much all languages, but they are super easy once you figure them out. If anyone actually wants to get their hands dirty to learn about Lisp macros, I recommend picking a Lisp implementation like SBCL, GNU Guile, Emacs, Clojure, or Hylang depending on what kind of environment you're comfortable with. The key about each of the Lisp implementations I mentioned here is that they all support "Common Lisp style macros", which are the bare bones most obvious way to do macros in Lisp. Then I recommend using your choice of Lisp to implement a language feature you use in another language. It doesn't matter if that language feature already exists in your choice of Lisp, you can still implement it yourself. For example, you can choose to implement C-style for loops or while loops, asynchronous coroutines like Go, pattern matching, lambdas, whatever. I actually implemented asnyc/await in IronScheme and pushed it upstream[0]. If you want to read more about Lisp macros, I have really enjoyed the book Let over Lambda. I have also heard a lot about On Lisp by pg, but I haven't read that myself yet. Also if you really want to dive off the deep end into the beauty of programming, I recommend SICP. [0] https://github.com/IronScheme/IronScheme/pull/141 https://github.com/IronScheme/IronScheme/pull/141
  - klyrs 2y ago
    Been there, done that. The real challenge is not implementing a non-trivial macro; it's coming back to that non-trivial macro a week later.
- ianthehenry 2y ago
homedirectory 2y ago
You can achieve memoization of an expression inside a function without any global state and macros: (defun compute-hash (key hash f) "Get the value for KEY in HASH or compute it with F, enter into HASH and return." (multiple-value-bind (val win) (gethash key hash) (if win val (setf (gethash key hash) (funcall f key))))) (defun memoized (f) (let ((cache (make-hash-table))) (flet ((memo (x g) (compute-hash x cache g))) (lambda (&rest args) (apply f #'memo args))))) (defun fib (n) (if (<= n 1) n (+ (fib (1- n)) (fib (- n 2))))) ;; MEMO is a function that takes a key and a computing function. ;; If a key has been memoized, it returns the cached value, otherwise it calls the computing ;; function with the key and caches the result. (let ((example (memoized (lambda (memo x) (format t "X: ~a~%" x) (let ((result (funcall memo x #'fib))) (format t "~a~%" (* 2 result))))))) (trace fib) (funcall example 5) (funcall example 5) (funcall example 5) (untrace fib))
- layer8 2y ago
  TFA wants to memoize separately per call site.
  - homedirectory 2y ago
    From the article: > I want it to be the case that this function only actually calls do-something-very-expensive once per unique value of x, even across separate invocations of dumb-example. My code memoizes results of function FIB _inside_ the lambda assigned to EXAMPLE, even across separate invocations of EXAMPLE.
    - deleted 2y ago
      [deleted]
artemonster 2y ago
Isnt this something that John Shutt solved with his Vau calculus? Basically, each "macro" (actually kinda like fexpr) invocation creates its own static environment, which neatly solves all hygiene problems and problems outlined in this article?
spankalee 2y ago
In JavaScript tagged template literals have the ability to identify the callsite. This is really powerful and used to create template identity in lit-html. I've wanted the ability to reference the callsite in functions, and lobbied the V8 team for something like arguments.callsite, but was (probably rightly) politely told no. But if you're willing to abuse tagged template literal syntax, they're really just function calls, so you can do something like: const dumbExample = (x) => { while (someComplicatedStuffHappens()) { pretendLikeThisFunctionIsBig(); } const result = memoize(doSomethingVeryExpensive, x)``; doMoreInterestingWork(); } memoize() must return a template tag function, which will be invoked with a TemplateStringsArray (because of the ``) that can act like a callsite identifier, which can be a key into a WeakMap of memoization dictionaries. It's mostly a curiosity because who wants that syntax, but it's interesting that JavaScript does have the special power hidden behind one feature.
- ianthehenry 2y ago
  Wait this is very interesting but I don't follow -- how do the template arguments let you identify the callsite? I thought this was basically just syntax sugar for memoize(doSomethingVeryExpensive, x)([""]), but there's something extra on that argument list that's stable across invocations?
  - aziis98 2y ago
    It looks like the first argument passed to tagged templates is always the same across all invocations for the same callsite. > This allows the tag to cache the result based on the identity of its first argument. To further ensure the array value's stability, the first argument and its raw property are both frozen, so you can't mutate them in any way. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Template_literals#tagged_templates:~:text=a%20new%20object-,console.log,-(callHistory%5B https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
    - ianthehenry 2y ago
      Ah, thanks! Got it. Okay that's wild. I would not expect that to be stable across dynamically-generated template functions, but it seems to work!

101 points by ianthehenry 2y ago

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 2y ago
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 2y ago

> 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 2y ago
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 2y ago
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 2y ago
  it might be; you'd have to benchmark it to be sure
taeric 2y ago
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 2y ago
  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 2y ago
    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.

MathMonkeyMan 2y ago

Programmer uses lisp macro to invent new keyword. It's a beautiful thing.

deleted 2y ago
[deleted]

dools 2y ago

""macros""

29athrowaway 2y ago

Macros are an unmaintainable mess.

fungiblecog 2y ago
Substitute any non-trivial programming idiom for “macros” and that is true for some subset of working programmers.

deathanatos 2y ago

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/ 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?

ianthehenry 2y ago
ha thanks, you are absolutely right. i updated the table :)
- lilyball 2y ago
  In that same article, you have some iterations 8 / 41 = 0.1951219 (8 + 41 = 49) / 8 = 6.125 (49 + 8 = 57) / 49 = 1.16326531 (57 + 49 = 106) / 57 = 1.85964912 (106 + 57 = 163) / 106 = 1.53773585 That second line is screwed up, which also screws up the subsequent lines. It should look like (41 + 8 = 49) / 41 = 1.19512195 which then means the line after that should be (49 + 41 = 90) / 49 = 1.83673469 and so on
  - ianthehenry 2y ago
    i think this is just very badly worded. the initial conditions are current=8, previous=41, not the other way around. i should make that more clear

cryptonector 2y ago

> Leaving aside the absurdity of computing Fibonacci numbers recursively Is it really absurd? If the compiler can turn it into iteration, then it's a big boy compiler. If not, then meh?

lupire 2y ago
Computing Fibonacci numbers iteratively is only slightly less absurd. It's `O(n)` for what should be an `O(log(n))` problem (`fib(n) = round ((phi^n - phi^-n)/(2phi-1))`).
- cryptonector 2y ago
  Ay, yes, I was focused on the idea that I want my compilers to do TCO and other optimizations, so I missed the point.
  - ianthehenry 2y ago
    Eh, by recursion I meant specifically the exponential "fib(n - 1) + fib(n - 2)" flavored definition. If you're writing the linear-time algorithm and happen to do the iteration via tail recursion, I don't think there's anything absurd about that

markovs_gun 2y ago

I am going to be honest I didn't really understand what an eigenvalue was until reading this. I'd read the definition but like I didn't really understand why you'd care about that. This was a great article

JHonaker 2y ago
Did you post this on the wrong article?
- disconcision 2y ago
  see the first link in the article, 'the absurdity of computing Fibonacci numbers recursively'
  - JHonaker 2y ago
    Ah, I see. I read the article, but not the links. I even searched for eigenvalue/eigenvector to see if I was crazy. The first linked article is very good. I always enjoy Ian’s work.
- markovs_gun 2y ago
  Woops I clicked on the first link and it was so long I forgot that it wasn't the originally linked article

pxc 2y ago

Wow. I haven't really played with Lisp since college. But I just started reading The Little Schemer with some friends, and hope to move on to SICP some time this year or next. This blog post made me a little dizzy, but also a little excited about what I'm hoping to explore with these lessons.

tyg13 2y ago

Every time I see a post from Lisp fans about macros, I want to be amazed, but I always just walk away confused. I can tell there's something interesting in there, but the quote-unquote-quasiquote syntax is just so dense that my brain is incapable of comprehending it.

fungiblecog 2y ago
To get it you really need to learn enough lisp (not a lot) and try implementing a non-trivial macro.
- Zambyte 2y ago
  Yep, they are a foreign idea in pretty much all languages, but they are super easy once you figure them out. If anyone actually wants to get their hands dirty to learn about Lisp macros, I recommend picking a Lisp implementation like SBCL, GNU Guile, Emacs, Clojure, or Hylang depending on what kind of environment you're comfortable with. The key about each of the Lisp implementations I mentioned here is that they all support "Common Lisp style macros", which are the bare bones most obvious way to do macros in Lisp. Then I recommend using your choice of Lisp to implement a language feature you use in another language. It doesn't matter if that language feature already exists in your choice of Lisp, you can still implement it yourself. For example, you can choose to implement C-style for loops or while loops, asynchronous coroutines like Go, pattern matching, lambdas, whatever. I actually implemented asnyc/await in IronScheme and pushed it upstream[0]. If you want to read more about Lisp macros, I have really enjoyed the book Let over Lambda. I have also heard a lot about On Lisp by pg, but I haven't read that myself yet. Also if you really want to dive off the deep end into the beauty of programming, I recommend SICP. [0] https://github.com/IronScheme/IronScheme/pull/141 https://github.com/IronScheme/IronScheme/pull/141
- klyrs 2y ago
  Been there, done that. The real challenge is not implementing a non-trivial macro; it's coming back to that non-trivial macro a week later.
ianthehenry 2y ago

homedirectory 2y ago

You can achieve memoization of an expression inside a function without any global state and macros: (defun compute-hash (key hash f) "Get the value for KEY in HASH or compute it with F, enter into HASH and return." (multiple-value-bind (val win) (gethash key hash) (if win val (setf (gethash key hash) (funcall f key))))) (defun memoized (f) (let ((cache (make-hash-table))) (flet ((memo (x g) (compute-hash x cache g))) (lambda (&rest args) (apply f #'memo args))))) (defun fib (n) (if (<= n 1) n (+ (fib (1- n)) (fib (- n 2))))) ;; MEMO is a function that takes a key and a computing function. ;; If a key has been memoized, it returns the cached value, otherwise it calls the computing ;; function with the key and caches the result. (let ((example (memoized (lambda (memo x) (format t "X: ~a~%" x) (let ((result (funcall memo x #'fib))) (format t "~a~%" (* 2 result))))))) (trace fib) (funcall example 5) (funcall example 5) (funcall example 5) (untrace fib))

layer8 2y ago
TFA wants to memoize separately per call site.
- homedirectory 2y ago
  From the article: > I want it to be the case that this function only actually calls do-something-very-expensive once per unique value of x, even across separate invocations of dumb-example. My code memoizes results of function FIB _inside_ the lambda assigned to EXAMPLE, even across separate invocations of EXAMPLE.
  - deleted 2y ago
    [deleted]

artemonster 2y ago

Isnt this something that John Shutt solved with his Vau calculus? Basically, each "macro" (actually kinda like fexpr) invocation creates its own static environment, which neatly solves all hygiene problems and problems outlined in this article?

spankalee 2y ago

In JavaScript tagged template literals have the ability to identify the callsite. This is really powerful and used to create template identity in lit-html. I've wanted the ability to reference the callsite in functions, and lobbied the V8 team for something like arguments.callsite, but was (probably rightly) politely told no. But if you're willing to abuse tagged template literal syntax, they're really just function calls, so you can do something like: const dumbExample = (x) => { while (someComplicatedStuffHappens()) { pretendLikeThisFunctionIsBig(); } const result = memoize(doSomethingVeryExpensive, x)``; doMoreInterestingWork(); } memoize() must return a template tag function, which will be invoked with a TemplateStringsArray (because of the ``) that can act like a callsite identifier, which can be a key into a WeakMap of memoization dictionaries. It's mostly a curiosity because who wants that syntax, but it's interesting that JavaScript does have the special power hidden behind one feature.

ianthehenry 2y ago
Wait this is very interesting but I don't follow -- how do the template arguments let you identify the callsite? I thought this was basically just syntax sugar for memoize(doSomethingVeryExpensive, x)([""]), but there's something extra on that argument list that's stable across invocations?
- aziis98 2y ago
  It looks like the first argument passed to tagged templates is always the same across all invocations for the same callsite. > This allows the tag to cache the result based on the identity of its first argument. To further ensure the array value's stability, the first argument and its raw property are both frozen, so you can't mutate them in any way. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Template_literals#tagged_templates:~:text=a%20new%20object-,console.log,-(callHistory%5B https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
  - ianthehenry 2y ago
    Ah, thanks! Got it. Okay that's wild. I would not expect that to be stable across dynamically-generated template functions, but it seems to work!