4 ms·
What’s the computational efficiency though? (Is there a general way to study the relative gains of adding primitives to a computation base*? I suspect just def
by harperlee 5y ago
What’s the computational efficiency though? (Is there a general way to study the relative gains of adding primitives to a computation base*? I suspect just defining the complex one in terms of the simpler one would risk losing the measure of some expressivity options further than just defining the complex one).
* EDIT: Not merely expanding a base but e.g. comparing a 6-set with a /different/ 2-set, as above.
- tromp 5y agoThere are several possible ways to quantify expressiveness of a basis. For instance, you can count how many unique lambda normal forms you can generate with combinator expressions up to a certain size (modulo some terms that take too long to normalize). I once counted this for various choice of single-point combinator bases and up to size 16, and found that the above S' produced over 2 million normal forms whereas for instance the more well known \x.x S K produced only 244 normal forms. When you look only at how easy you can recover S and K, then the latter is much superior though (length 16/11 versus 3/3).
- stouset 5y agoAIUI, in theory, they're all the same given a sufficiently advanced optimizing compiler. They're all equivalently-powerful way to model computation, so can all in principle be translated back and forth. In practice extracting optimal efficiency is difficult.