Hacker News Reader

Comment by scj | Hacker News Reader

Have language X implement language Y and vice-versa?

See, that's the problem: it doesn't work!

If both languages are Turing-complete, you can always implement language X in Y, and Y in X. That's basically the definition of Turing-completeness.

Any feature can be implemented in the destination language, even if it is by something as silly as running the source language compiler and executing the resulting bytecode in a x86 VM in your destination language.

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.

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

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.

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).

You can even prove that languages that can do IO are equally fast. For example for every Java program there is a C program with the same performance: just put the binary of the JVM in a .c file, and write out a JVM on the disk at compile time, and start it from C at runtime. Then you have a C program for every Java program, which has the same performance.

How do you implement sleep() in lambda calculus?

Or `read` or `write` or invocation of any syscall. There is more to computer system than pure computation.

Reply on news.ycombinator.com