Quote-unquote "macros" (opens in new tab)

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

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

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

  how to fibonacci           space complexity  time complexity
  -------------------------  ----------------  ---------------
  insane recursion           exponential       exponential
  memoized insane recursion  linear            linear

  fib(n)
  fib(n-1)
  fib(n-2)
  ...
  fib(1)

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

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();
    }

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.

Is it really absurd? If the compiler can turn it into iteration, then it's a big boy compiler. If not, then meh?