4 ms·
Optimal beta reduction is a very technical term. In effect it means any "family" of lambda terms will all be reduced "at once." What is a family? Go take two se
by voxl 5y ago
Optimal beta reduction is a very technical term. In effect it means any "family" of lambda terms will all be reduced "at once." What is a family? Go take two semesters in rewriting theory and then perhaps our two heads together can pin it down exactly.
In laymen's terms, it means that you're doing a variant of call-by-need, except you can be absolutely sure you don't copy applications without need.
I am personally skeptical it's a useful idea at all. Machine computation is what we really care about (how fast can you push instructions through the pipeline) and graph reduction systems were already all the rage in the 80s. We gave up on them because they didn't interact with the cache well.
So, this is the "motherload" of all graph reduction strategies, yet it will get absolutely trounced in settings like numerical computation.
- Azsy 5y agoAs a counter argument ( and i'm not 100% sure it holds up ). The cache failures was because the cache was to small. Whereas now we care about CPU OP data dependencies.
- txdv 5y agoCan you link to learning resources?
- JonChesterfield 5y agoThere's an interesting interaction with implicit parallelism. For a given reduction to occur at most once you need communication across threads so that two don't do the same reduction at once. I suspect at most once per hardware thread is a faster choice - repeating some calculation for decreased communication. Or you need a static assignment of reduction to threads which means predicting how long each reduction will take.