3 ms·
[...] We consider a simple discipline of total functional programming designed to exclude the possibility of non-termination. [...] So the idea seems to be a p
by DenisM 10y ago
[...] We consider a simple discipline of total functional programming designed to exclude the possibility of non-termination. [...]
So the idea seems to be a programming framework that on one hand guarantees termination, while on the other hand is sufficiently powerful to be useful. That is "useful despite being sub-turing".
I spent some time causally studying the subject of sub-turing languages, and found something notable. If a language guarantees that all its programs consume input as they go, that program is guaranteed to terminate, and so the language itself is sub-turing. One example of such program could be a compiler, which makes for a great example of a useful application of a sub-turing language.
It's a fascinating subject because sub-turing language programs are a lot easier to analyze.
- lomnakkus 10y ago> That is "useful despite being sub-turing". This has been called being "Pacman Complete" by Edwin Brady. I very nice catchy term, IMO.
- skybrian 10y agoI like that. A search doesn't find anything relevant, though. Got a reference?
- barrkel 10y agoA compiler is, at a high level, just a function. And most architectural breakdowns of compilers turn them into sequences of functions, like: link(codegen(analyze(typecheck(parse(lex(source)))))) And compilers are one of the easiest kinds of programs to write naturally in a functional language.