undefined | Better HN

0 pointsklyrs2y ago0 comments

Giving the GP a more generous interpretation: let L(X, Y) be the shortest possible size of an interpreter of language X written in language Y. If L(X, Y) > L(Y, X), then implementing X in Y requires more than implementing Y in X, and X could be considered "more expressive" than Y. That said, the answer in OP is much more insightful and thought-provoking.

0 comments

tromp2y ago

A very large L(X, Y) need not indicate that Y lacks expressiveness, but instead could indicate that X is a hugely complicated language. E.g. X might have a primitive that greps from all of Wikipedia snapshotted at some fixed time. Or X could have a huge standard library (think Mathematica).

I think a better way to compare languages is to take some collection of tasks, e.g. the first so many Euler problems, and see how concise the best known solutions in language X compare to those in other languages.

It would be best to express the length of all programs in bits, so that languages with alphabets significantly smaller than ASCII like Brainfuck or Binary Lambda Calculus are not unfairly penalized. The latter would seem to be particularly expressive [1].

[1] https://tromp.github.io/cl/cl.html

Joker_vD2y ago

So if you add "EVAL_AS_Y{ ... }" core primitive into X, it becomes strictly more expressive as Y until you add "EVAL_AS_X { ... }" to Y: then they become exactly as exressive as each other.

scj2y ago

This would be in line with my thoughts.

Of course, my off-hand comment is just an exercise rather than an objective measurement. It'd only suffice for trivial examples (say, where X is a strict subset of Y).

j / k navigate · click thread line to collapse