3 ms·

I recently ran into this issue when trying to memoize a simple numerical sequence in Hoon (yes, that Hoon. I know, I know...). Let's use the fibonacci sequence

by narski 2y ago

I recently ran into this issue when trying to memoize a simple numerical sequence in Hoon (yes, that Hoon. I know, I know...). Let's use the fibonacci sequence as an example. Let's write it the classic, elegant way: f(n) = f(n-1) + f(n-2). Gorgeous. It's the sum of the two previous. With the caveat that f(n=0|1) = n. In Python: # fib for basic b's def fib(n): ## Base case if n == 0 or n == 1: return n return fib(n-1) + fib(n-2) Right off the bat, performance is O(n)=n*2. Every call to f(n-1) will also need to compute f(n-2) anyways! It's a mess. But since Python passes arrays and dictionaries as pointers (cough, sorry! I meant to say references) it's super easy to memoize: # optimize-pilled memoize-chad version def fib(n, saved={}): if n in saved: return saved[n] if n == 0 or n == 1: saved[n] = n else: saved[n] = fib(n-1) + fib(n-2) return saved[n] Okay, now our version is nearly as fast as the iterative approach. This is the normal pattern in most languages, memoizing otherwise "pure" functions is easy because you can reference a shared object using references, right? Even with multithreading, we're fine, since we have shared memory. Okay, but in Hoon, there are no pointers! Well, there kinda are. The operating system lets you update the "subject" of your Urbit (the context in which your programs run), and you can do this via the filesystem (Clay) or daemons (Gall agents, which have their own state kind of). But to do this within a simple function, not relying on fancy OS features? It's totally possible, but a huge pain the Aslan. First, here's our bog-standard fib in Hoon: |= n=@ud ?: (lte n 1) n %+ add $(n (dec n)) $(n (sub n 2)) Now, I memoize on the way down, by calculating just f(n-1) and memoizing those values, to acquire f(n-2): :- %say |= [* [n=@ud ~] [cache=(map @ud @ud) ~]] :- %noun ^- [sum=@ud cache=(map @ud @ud)] =/ has-n (~(get by cache) n) ?~ has-n ?: (lte n 1) [n (~(put by cache) n n)] =/ minus-1 $(n (dec n)) =/ minus-2 =/ search (~(get by cache.minus-1) (sub n 2)) ?~ search 0 (need search) :- (add sum.minus-1 minus-2) (~(put by cache.minus-1) n (add sum.minus-1 minus-2)) [(need has-n) cache] and that works in the Dojo: > =fib-8 +fib 8 > sum.fib-8 21 but it sure is easier in Python! And I'm not picking on Hoon here, it's just pure functional programming that makes you think this way - which as a hacker is fun, but in practice is kinda inconvenient. I even wonder how much faster I actually made things. Let's see: > =old now > =res +fib 18 > sum.res 2.584 > (sub now old) 1.688.849.860.263.936 :: now with the non-memoized code... > =before now > +fib 18 2.584 > (sub now before) 1.125.899.906.842.624 Ha! My super improved memoized code is actually slower! That's because computing the copies of the map costs more than just recurring a bunch. This math should change if I try to compute a bigger fib number... Wait. Nevermind. My memoized version is faster. I tested it with the Unix time command. It's just that Urbit Dojo has a wierd way of handling time that doesn't match my intuition. Oh well, I guess I can learn how that works. But my point is, thinking is hard, and in Python or JS or C I only have to think in terms of values and pointers. And yes, that comes with subtle bugs where you think you have a value but you really have a pointer! But most of the time it's pretty easy. Btw sorry for rambling on with this trivial nonsense - I'm a devops guy so this is probably super boring and basic for all you master hn swe's. But it's just a tiny example of the constant frustrations I've had trying to do things that would be super simple if I could just grab a reference and modify something in memory, which for better or worse, is how every imperative language implicitly does things.

sirsinsalot 2y ago
Note to self: never code Hoon
nine_k 2y ago
The standard way to expel stated mutable state us to push it into function parameters and returned values. With Fibonacci numbers, you cab just compute two if them outright: def fib_(n: int) -> tuple[int, int]: if n == 0: return (1, 1) prev, this = fib_(n - 1) return (this, this + prev) def fib(n): return fib_(n)[0] Now there is no mutable state that survives between function calls, the performance is linear. With true memoization though accessing a previously computed value.would be constant time.
- narski 2y ago
  >The standard way to expel stated mutable state us to push it into function parameters and returned values. This is precisely what I did in my Hoon solution :) However, I wasn't aware that this approach is the standard way, and I'm glad to have learned that! Thanks
juped 2y ago
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 2y ago
  Ha! I read the docs for ~+ (https://docs.urbit.org/language/hoon/reference/rune/sig#-siglus 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.

by narski 2y ago

sirsinsalot 2y ago

Note to self: never code Hoon

nine_k 2y ago

The standard way to expel stated mutable state us to push it into function parameters and returned values. With Fibonacci numbers, you cab just compute two if them outright: def fib_(n: int) -> tuple[int, int]: if n == 0: return (1, 1) prev, this = fib_(n - 1) return (this, this + prev) def fib(n): return fib_(n)[0] Now there is no mutable state that survives between function calls, the performance is linear. With true memoization though accessing a previously computed value.would be constant time.

narski 2y ago
>The standard way to expel stated mutable state us to push it into function parameters and returned values. This is precisely what I did in my Hoon solution :) However, I wasn't aware that this approach is the standard way, and I'm glad to have learned that! Thanks

juped 2y ago

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 2y ago
Ha! I read the docs for ~+ (https://docs.urbit.org/language/hoon/reference/rune/sig#-siglus 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.