3 ms·
What are some approaches one might take to consciously design a sub-turing-complex language? It should perhaps be driven from some concrete and critical use cas
by kartickv 11y ago
What are some approaches one might take to consciously design a sub-turing-complex language? It should perhaps be driven from some concrete and critical use case.
For example, I can imagine a language that you can analyse statically to determine not just whether it halts, but how long it will take to do so. As an extreme example, imagine a language with only the four arithmetic operators. No functions, no classes, no references / pointers, no recursion or loops or goto, nothing else. You can statically analyse a program in this language to determine, for example, that if each arithmetic operator takes 1ms to execute, then a program containing 100 of them in its source file will be done in 100ms.
Now, what can you add to this language while still keeping it analysable? Maybe functions, as long as they are not recursive. You'd add only things you can mathematically prove have a bounded runtime. Maybe fixed-length arrays, like int[10], not int[n]. Maybe loops that run a constant number of times, like:
repeat (10) {
...
}
not:
repeat(n) {
...
}
What good would such a language be? Maybe for document macros, where I won't be able to hang or crash your document viewer or editor with a macro that runs forever? Maybe there are better uses for such a language than this made up example.
Or maybe bounded running time is not the most useful subset of Turing-completeness one can design. Maybe a language that's immune from side-channel attacks, if that's possible? Or something entirely different?