4 ms·
> Maybe we’re doing it all wrong writing programs in assembler. We should give them to a VM, This is what compilers do. Their input is a program in a more abst
by titzer 5y ago
> Maybe we’re doing it all wrong writing programs in assembler. We should give them to a VM,
This is what compilers do. Their input is a program in a more abstract language, either bytecode, an intermediate representation, or a source language.
The problem is that damn undecidability, which is like a minefield of rakes. It's undecidable for a compiler to tell if a program will do anything (e.g. halt). It's undecidable for a compiler to tell if two programs are equivalent. It's undecidable for a compiler to tell if a program is minimal.
So compilers have to well, be dumber. They approximate a lot.
- freemint 5y agoIn fact finding the for loops to do tensor contractions (think matrix multiply but with many more dimensions) alone was something in NP range. Converting for loops to assembly as is done by https://polly.llvm.org/ https://polly.llvm.org/ is equivalent to Mixed-Integer Linear Programming, is equivalent to MaxSat is equivalent to Sat in a for a loop. In these domains there is a definition of minimal and they are still hard.
- MauranKilom 5y ago> The problem is that damn undecidability, which is like a minefield of rakes. It's undecidable for a compiler to tell if a program will do anything (e.g. halt). It's undecidable for a compiler to tell if two programs are equivalent. It's undecidable for a compiler to tell if a program is minimal. Only for Turing complete languages, to be clear. Now, of course, most interesting problems cannot really be solved in sub-Turing languages, but it's still a fundamental point to consider.