Hacker News new | ask | show | jobs
by adi92 5991 days ago
are all languages implementable in every other language?
2 comments
profquail 5991 days ago
Nope. For example, you can't parse HTML or source code with a regular expression, because of limitations on how the language itself works (it doesn't have the ability to parse nested structures).

However, in practice, most common programming languages can be used to implement other programming languages...it's just a matter of how much/little code you're going to need to write to do it. Using this article as an example, it would be much easier to implement Scheme in F# than it would be in C#, due to some features of the F# language.

link
DougBTX 5991 days ago
Not all languages, but many: http://en.wikipedia.org/wiki/Turing_completeness#Examples
link
chancho 5991 days ago
From that wikipedia page: "The untyped lambda calculus is Turing-complete, but many typed lambda calculi, including System F, are not."

Anyone have any details about System F not being turing complete? Is it not straightfoward to implement an untyped lambda calculus in a typed one?

link