4 ms·
> Which is often the case with claims of solving long-lasting problems This is what I really like about programming language theory: problems which are literal
by chriswarbo 6y ago
> Which is often the case with claims of solving long-lasting problems
This is what I really like about programming language theory: problems which are literally undecidable in existing languages, can be made almost trivial by designing a language with that problem in mind. The trick is to have the language keep track of the information needed for the solution, so we're not dealing with "black boxes".
A classic example is annotating every variable with a type, and propagating that information through compound expressions; lets us spot problems like trying to use a number as a string, without worrying about the halting problem (we do this by forbidding some technically-valid programs, like `1 + (true? 10 : "hello")`).
Of course, this leaves the much harder problems of (a) keeping the burden imposed by this extra information down to a reasonable level, and (b) trying to make the language compelling enough for people to actually use. Rust is one of the few examples of going all-in on a new ecosystem, and it actually being embraced. Often it's easier to "embed" a new language inside an existing language, to piggy-back on the existing tooling (e.g. the variety of auto-differentiating languages built in Python)
- Quekid5 6y agoYes, people often forget that TMs really are "pure runtime". Sure, the program itself is static, but nothing else is. There's no imposed semantics on anything beyond the pure mechanism of the interpreter itself. This lessens the 'problem' part of the Halting Problem drastically if you just impose some constraints on the programs, e.g. static types, maybe a borrow-checker, etc.