I like to refer to code that has been overly injected with syntactic sugar as "caramelized". We need more culinary metaphors for programming jargon!
mpoteat•3mo ago
@marvinborner
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.
mpoteat•3mo ago
mpoteat•3mo ago
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
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
Maybe it's a soufflé? Highly unstable, but occasionally very nice.
marvinborner•3mo ago
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.