A 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))))))
Re:Total Functional Programming [pdf]
by lomnakkus on Wednesday October 05, 2016 @04:11PM
(#12647374)
> That is "useful despite being sub-turing".
This has been called being "Pacman Complete" by Edwin Brady. I very nice catchy term, IMO.
Re:Total Functional Programming [pdf]
by skybrian on Wednesday October 05, 2016 @11:00PM
(#12649910)
I like that. A search doesn't find anything relevant, though. Got a reference?
Edwin didn't coin it - but he did popularise it:
https://twitter.com/edwinbrady/status/384671269490540544
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.