[juped]

Hoon has magic memoization, though (~+)

    ++  fib
      |=  a=@
      ^-  @
      ~+
      ?:  (lte a 1)  a
      %+  add
        $(a (sub a 2))
      $(a (sub a 1))

Try e.g. (fib 100) (don't try it without the ~+)

The compiled code is itself memoizable at the VM execution level. This memo cache is transient within one system event (i.e., pressing enter after (fib 100) to get the result).

[narski]

Ha! I read the docs for ~+ (https://docs.urbit.org/language/hoon/reference/rune/sig#-sig...) and fibonacci sequence is actually the example they use!

Thanks so much for this enlightening comment :3

Although I'm curious why Hoon doesn't just detect and cache identical computations by default. I guess it's a tradeoff, since using ~+ is more memory intensive, and you don't always want that either. Especially is Urbit itself is already fairly memory intensive.

[juped]

There's a lot of reductions that happen during execution, and not many are usefully going to be repeated identically; you'd end up with an extremely large and nearly entirely useless cache if you tried to cache everything. So you hint the VM when it turns out that something does repeat.

What has to repeat is an identical subject (which will have a shape like [argument-to-fib other-local-context standard-library]) and formula (the compiled code for fib). Pretty much the only time this will ever happen is something recursing into itself. Most tail recursion doesn't reevaluate the exact same arguments multiple times. It just so happens that naive fib's exponential self-recursion into itself twice does do that.

So it wouldn't be useful to stick a ~+ on, say, factorial. Except! If you're, say, computing every factorial from 1 to 100 in a loop, it comes in handy - because now you can reuse your computation of, say, 50! when computing 51!, so it's just one multiplication.

But most Nock reductions by volume are not anything that repeats usefully.