fp.

Is there any hope for a "hashlife" style cache for a TC language? My understanding is that hashlife exploits spatial locality / "causation speed" in GoL, which isn't available in LC because of beta reduction. Thoughts?

marvinborner•3mo ago

I don't know any quadtree/lowlevel encoding of LC that could be memoized like that. Though you could, for example, cache the reduction of any term by hash and substitute the matching hashes with its nf. This doesn't really work for lazy reducers or when you do not reduce strongly. And, of course (same as hashlife), this would use a lot of memory. With a lot more possibilities than GoL per "entity" (NxN grid vs variables/applications/abstractions), there will also be a lot more hash misses.

There's also graph encodings like interaction nets, which have entirely local reduction behavior. Compared to de Bruijn indices, bindings are represented by edges, which makes them more applicable to hash consing. I once spent some time trying to add this kind of memoization but there are some further challenges involved, unfortunately.

nixpulvis•3mo ago

Problem is caramel is better than sugar, and I generally think adding too many layers of sugar makes things worse.

Maybe it's a soufflé? Highly unstable, but occasionally very nice.

marvinborner•3mo ago

Good idea, I like "caramelized"!

However, I wouldn't define bruijn as being caramelized just yet. Personally, I view as syntactic sugar only syntax that's expanded to the target language by the parser/compiler. In bruijn's case, there is barely any of such syntax sugar aside of number/string/char encodings. Everything else is part of the infix/prefix/mixfix standard library definitions which get substituted as part of the translation to LC.