Quote-unquote "macros" | Hacker News Reader

Quote-unquote "macros"

ianthehenry.com

101 pointsianthehenry70 comments

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.

To get it you really need to learn enough lisp (not a lot) and try implementing a non-trivial macro.

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

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.

Yeah this is kinda like... this is definitely an advanced topic within the topic of macro writing and not very intelligible if you haven't written simpler macros for a while already.

I wrote a book whose third chapter is a much "gentler" introduction to macros. I don't know if it's actually intelligible (see: the monad tutorial fallacy) but it presents them the way that I was first able to understand them -- explicitly starting without quasiquote and working up to it. Easier for me than getting lost in the notation. https://janet.guide/macros-and-metaprogramming/

Paul Graham's https://paulgraham.com/onlisp.html is a whole book about it that really helped it click for me.

The challenge with the syntax is that there is no syntax. Work that we're used to offloading to syntax is instead carried by your brain.

> Work that we're used to offloading to syntax is instead carried by your brain.

Kinda like the challenge to eating salad is all the chewing. It's not just that the brain needs to parse a lot more language to express a simple concept; it's also that the fingers also need to type all that out.

In neither case should it be a serious issue.

> but the quote-unquote-quasiquote syntax is just so dense that my brain is incapable of comprehending it

Here's JS string interpolation:

`OK ${10+20} == 30` // result: "OK 30 == 30" — a JS string

Here's a quasiquote-unquote:

`(OK ,(+ 10 20) == 30) ; result: (OK 30 == 30) — a list of 4 atoms

In my toy Lisp I used $ instead of comma, which I found a tad "more readable" coming from today's JS, Perl, Bash world. (And makes quasiquote... "the money quote"? =)

Focus on the problem that is being solved, not the mechanism. Consider this classic trick:

    handle = (exists(file) and open(file))

That uses the short-circuiting behaviour of && to only open a file if it exists. Not great practice to write it in that way IMO but whatever. You can't implement it as a function:

    handle = and(exists(file), open(file))

    def and(exists, file):
       ... No viable implementation in Python afaik ...

That doesn't work because functions arguments don't/can't implement short circuiting - both arguments are evaluated before our function is called (although we could make it work in this case by passing the file name in - the point is that the function signature has to change).

Macros however can implement something that has short circuiting behaviour. It is a mechanism for implementing new syntax - more powerful than functions but as a trade off more error prone. Quasiquoting and whatever falls out of that as implementation details once you've got all that as context.

I know it’s not the point of your example, but you should not check if a file exists right before opening it. It could get deleted in between exists(file) and open(file), so you still have to handle the case where opening fails with FileNotFound.

I find myself increasingly preferring the exists()-then-open() sequence to open()-and-catch-NotFound (not just in Python, but generally).

Yes, it is classically frowned upon, but:

1. It is typical that there are multiple checks that need to be done in addition to exists(). It is a given that conditionals are more flexible than exceptions (even in Python). As long as some checks are in conditionals, it makes the code more legible and easier to reason about when all preliminary checks are in the same fashion and in the same place.

2. You still need to handle the other possible sub-varieties of OSError and other exceptions that can arise due to, say, I/O being famously unreliable. If you implement that handling gracefully, you will have the FileNotFoundError covered for free. From end user experience perspective, since a file being deleted between exists() and immediate open() on a single system within a single thread is an out of ordinary one-in-a-thousand-years case, it is OK if it is handled slightly less gracefully than if it occurs during the preliminary checks.

You still have to handle the exceptional case, but also checking beforehand can lead to better error messages, and in situations involving multiple resources can avoid having to rollback a second resource in the non-racy case.

I think everybody gets that (basic understanding of macros); but that’s not the level of apparent sophistication TFA is about. I agree with the GP comment.

Well then, extending my example:

We'll need a mechanism to suppress evaluation (quote '), we want a mechanism to trigger evaluation in a quote (unquote ,) but because we aren't barbarians we don't allow unquoting inside a quote since that would be confusing, so unquote is only meaningful in a quasiquote (ie, a quote that allows unquoting ~) and then there is splice syntax (;) because that is a convenient operation. That is a mumbo-jumbo explanation and the real one involves some treatment of the read-eval-print loop, symbol resolution and whatnot I dunno about Janet; but it isn't that badly wrong.

It is annoying to use the first few times because macros demand an unusually precise understanding about how evaluation works, but that is to some extent the point of the article - working through some things that could be misunderstood about how to build an unevaluated blob of code. It'll look weird to people who use languages without macros because there isn't a reason to get into the weeds of evaluation ... unless writing new syntax with macros.

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))

TFA wants to memoize separately per call site.

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.

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.

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

> 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.

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

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.

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

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.

fib(3), fib(2), fib(6), fib(1000000), fib(9), fib(2), fib(8),...

Wait, can't you just set the property on the function object itself to accomplish this?

Stack is not the same as the callsite. (It’s technically also a non-standard property.)

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?

ha thanks, you are absolutely right. i updated the table :)

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

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

"the absurdity of computing Fibonacci numbers recursively"

It's absurd to actually compute it that way, but it's beautiful to express it that way.

From the blog post:

  def fib(n):
      if n <= 1:
          return n
      return fib(n - 1) + fib(n - 2)

Easy to read, easy to comprehend. You just need a smart compiler to do it efficiently.

I too also appreciate the beauty of the "insane" algorithm, from a mathematical view. What I think gets lost on some programmers¹ is that, while that's all good and fine, we're not just doing a computation, we are doing a computation and we're inherently expending time and space to do that computation, and the amount of time and space is inherently part of the problem, or part of the requirements. I want to compute X, but I also do want to do it before the heat death of the universe. Attempting to sweep those under the rug with a "sufficiently smart compiler" is fun when it works, but I think in the sense of engineering software, we need a more rigorous answer to "it will not consume bonkers amounts of space/time to compute X."

"Accidentally Quadratic" was a fun tumblr dedicate to more real world instances of this, and it's sad they're not longer posting, though I still use that term to name real-world sightings of O(lol) time. (O(lol) space is just called "Java".)

¹and since you say "to actually compute it that way", I think you get this, but I want to point it out here

Do you have any idea who the poster behind "Accidentally Quadratic" is? Spounds like he/she would have some interesting stories.

Are there any existing compilers that could compile a function like this -- non-tail recursive and non-tail recursive modulo cons -- into something that executes in sub-exponential time? How would that even work? I've never heard of a compiler sufficiently smart to optimize a definition like this and now I'm very curious

Well, both Clang [0] and GCC [1] do compile the "insanely-recursive" fib into something less insane (or, in case of GCC, something that's insane in a different way). It looks like it's done with partial unrolling/inlining?

And, well, if you disregard heavy optimizations, then this "insanely-recursive" function is actually a somewhat decent way to measure the efficiency of the function calls and arithmetic.

[0] https://godbolt.org/z/3fce1qTdv

[1] https://godbolt.org/z/4jqa453qY

in lua:

  local fib do
    local impl impl = function(n, n1, n2)
      if n == 0 then return n1 end
      return impl(n - 1, n1 + n2, n1)
    end
    fib = function(n) return impl(n - 1, 1, 0) end
  end
  for i = 1, 10 do print(fib(i)) end

If we account for arbitrary precision operations necessary for large N, I believe the memoized insane recursion is quadratic in space and time. This is actually not as bad of a pessimization as I thought it would be over just using Binet's formula, but it's still a hit.

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.

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?

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/Refe...

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!

This is how lit-html implements efficient re-renders of the same template at the same location in DOM. It uses the template strings identity to mark that some DOM was generated from a specific template, and if rendering there again it just skips all the static parts of the template and updates the bound values.

Tagged template literals are crazy powerful, and it would be really neat to add some of that magic to other language features. If functions could access the callsite, you could implement React hooks without the whole hooks environment. Each hook could just cache it's state off the callsite object.

The key thing to note here is that it is completely _lexical_ in scope - this only generates one tagged template even when called multiple times:

  function lexicalMagic() {
    const callHistory = [];
  
    function tag(strings, ...values) {
      callHistory.push(strings);
      // Return a freshly made object
      return {};
    }

    function evaluateLiteral() {
      return tag`Hello, ${"world"}!`;
    }
    return { evaluateLiteral, callHistory }
  }

We can create multiple "instances" of our closures, just as we expect and they do in fact produce distinct everything-else:

  > const first = lexicalMagic()
  > const second = lexicalMagic()
  > first.evaluateLiteral === second.evaluateLiteral
  false
  > first.callHistory === second.callHistory
  false

Using them doesn't behave any differently than the unclosured versions (as expected):

  > first.evaluateLiteral() === first.evaluateLiteral()
  false
  > first.callHistory[0] === first.callHistory[1]
  true
  > second.evaluateLiteral() === second.evaluateLiteral()
  false
  > second.callHistory[0] === second.callHistory[1]
  true

However, there is only one instance of the template literal, not two as we might expect. This is really helpful for some cases, but it definitely is surprising given the rest-of-JS:

  > first.callHistory[0] === second.callHistory[1]
  true

Wow this is awesome, I just tried to thinker with this and you can actually build "lexical hooks" using this feature [1]. As syntax I tried with use`state` use`memo` and this feels kind of readable.

[1]: https://gist.github.com/aziis98/c8de74a29d5b1721983501fe28eb...

I don't know precisely but this feels like this would be very useful for something. I'll continue to experiment with this in the future

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.

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?

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

Did you post this on the wrong article?

see the first link in the article, 'the absurdity of computing Fibonacci numbers recursively'

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.

Woops I clicked on the first link and it was so long I forgot that it wasn't the originally linked article

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

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

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))`).

Ay, yes, I was focused on the idea that I want my compilers to do TCO and other optimizations, so I missed the point.

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

""macros""

Macros are an unmaintainable mess.

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

Reply on news.ycombinator.com