5 ms·

This 100x. After learning to program in Coq (sub-Turing-complete functional language) and SQL, I've come to recognize that I have never in two dozen years of co

This 100x. After learning to program in Coq (sub-Turing-complete functional language) and SQL, I've come to recognize that I have never in two dozen years of coding needed to express something that wasn't expressible in some sub-Turing-complete language. Turing-completeness is overrated and is more often that not a cop-out excusing poor language design. Sub-Turing-complete domain-specific-languages simplify program design, reduce bug surface area, and aid analyzability and understanding.

mietek 11y ago
You are correct, but you are probably being downvoted because it is difficult to relate to your point of view. How many “sub-Turing-complete” languages can you list? Note “sub-Turing-complete” may not be the right term to use for all languages that do not admit general recursion. There is a particularly interesting subset of total languages for which the preferred term is “languages with control over non-termination”. http://www.cse.chalmers.se/~nad/publications/danielsson-semantics-partiality-monad.pdf http://www.cse.chalmers.se/~nad/publications/danielsson-sema... https://personal.cis.strath.ac.uk/conor.mcbride/TotallyFree.pdf https://personal.cis.strath.ac.uk/conor.mcbride/TotallyFree.... https://github.com/mietek/total-functional-programming https://github.com/mietek/total-functional-programming
- colanderman 11y ago
  There aren't many popular non-Turing-complete languages because most language designers are stuck in a cycle of redesigning Algol and Lisp for the umpteenth time. Very few new mainstream languages have anything new to say that applies to anything outside writing simple algorithms or gluing libraries together. Scala, Ruby, D, Rust, CoffeeScript, Clojure... I could go on. They're all just rehashes of the same ingredients. Why this is the trend I'm not sure, but I bet it's related to the fact that these same languages try to position themselves as complete ecosystems, rather than simple tools which form but part of an engineering solution. There's been some promising movement recently in the direction of DSLs. Reactive programming seems to finally be gaining popularity, which allows us to replace gobs of glue code with simple declarations. Erlang's OTP has been gaining popularity too, allowing declarative design in the large.
  - kibwen 11y ago
    > Very few new mainstream languages have anything new to say > these same languages try to position themselves as complete > ecosystems, rather than simple tools This is where you answer your own implied question. Tools designed to excel at a singular task to the exclusion of general-purpose tasks will necessarily attract a comparatively niche audience. Tools designed for more general applications will attract people doing more general tasks, which is a more "mainstream" audience by definition.
    - colanderman 11y ago
      Yes, it is an unfortunate catch-22. I think the secret is that, due to their simplicity and analyzability, it's possible to make extraordinarily powerful DSLs that can truly excel at their tasks in a way that general-purpose languages can not. SQL is a perfect example of this. The fact that it is (barring recursive CTEs) not Turing-complete is what permits very intelligent automatic query optimization. I can write simple, clear, concise, performant SQL code that blows the pants off anything I can do without extraordinary effort in a general-purpose language. It is this that has made SQL so indispensable and enduring a tool.
      - nickpsecurity 11y ago
        Or you can get both with a powerful general purpose language subject to easy analysis and supporting DSL's. What I can do with that will blow the pants off your SQL. Matter of fact, I can start with a DSL for clarity/automation, manually optimize it if I choose in same language, and (if Scheme) compile that all the way down to logic gates. That's power right there.
        colanderman 11y ago
        I'm not really sure the point of your post. Why should I roll my own relational query engine in Scheme when I can use one with hundreds of man-years of development, and thousands of man-years of testing behind it, like PostgreSQL? Also, I sincerely hope you're not trying to synthesize ASICs out of code from a language with constructs like call/cc.
- Too 11y ago
  I'm not sure if these are strictly non Turing complete or not but they are designed to do one thing only and they are still quite mainstream: makefiles, shaders, flex and yacc. SQL has already been mentioned, other database query languages are usually even more restrictive.
icebraining 11y ago
SQL is actually Turing-complete; using recursive CTEs, you can build a cyclic tag system, which has been proven to be Turing-complete.
- colanderman 11y ago
  You are very correct. I think there is still much to gain even from Turing-complete languages, where the Turing-completeness is relegated to one particular rarely needed construct. Beside the rest of the language being completely analyzable, that one piece that isn't easily stands out as a code smell.
- Avshalom 11y ago
  Yeah the reason there aren't many sub-turing-complete languages is because it's actually really hard to prevent turing completeness.
- Retra 11y ago
  SQL in its original incarnations is not Turing complete. It's mainly the bastardized, enterprised, heavily-extended versions built by people who have to sell it that are Turing complete.
  - colanderman 11y ago
    To be fair, recursive CTEs are somewhat a blessing when you need to compute transitive closures. It is just unfortunate that they were designed as generative constructs (= you can create and recur on rows out of thin air rather than only products of other finite relations).
- bordercases 11y ago
  Turing-hard then?
- mappu 11y ago
  Recursive CTE's aren't universally present in SQL engines (e.g. MySQL doesn't have them)
nickpsecurity 11y ago
Does Coq actually run programs of any significance or do you have to extract to Ocaml, etc to get things done? SQL is certainly a practical, non-Turing-complete language. I'm with the other commenter wondering if those of you opposing Turing-completeness have a list of alternate languages that could replace what we use for systems, applications, web, etc with same productivity and efficiency. If they exist, I'll consider using them and benchmarking. So far, I mostly see articles opposing one thing without corresponding articles with alternatives. Look forward to see what you have as this is a topic I could certainly learn more about. Especially with the "LANGSEC" push throwing labor at it.
- colanderman 11y ago
  There aren't any, that's the problem. Because most language designers these days seem to think that the best way to solve problem X is to develop an entire closed-garden ecosystem that also can solve Y and Z, and ends up doing none of them well, while forcing you to use their language and only their language. Everywhere I've worked, I have seen the same things reimplemented poorly over and over again in general-purpose languages. Every system I've worked on is roughly a mash-up of database, dataflow graph, state machine, work scheduler, IPC, process coordination, programming in the large, and very low-level algorithmic stuff. Each of these could be factored out into a common simple language, but almost invariably they're just patterns imposed on C/C++/Java/what-have-you code. This greatly hampers understanding and analyzability. There are rare occasions I see DSLs used to fulfill these roles, and it's to great benefit. Working with a well-designed PostgreSQL database rather than some half-baked home-grown object database is a dream. You get a concurrency model that works, and you can extract graphs of your data model for free. Same with using a state machine description language like SMC rather than hand-coding stuff as C++ boilerplate. Same with using a process coordinator like Erlang's OTP (which isn't a DSL but is close enough). I'm not writing these posts to try to get developers to use DSLs more often. I'm writing them to try to get language designers to design DSLs more often. On Coq: Coq is not at all a practical programming language, since it has no concept of communication with external processes (i.e. I/O). This is exactly as it should be, since Coq is focused precisely on the domain of functional algorithms (and proofs). And, I have found that, within that domain, the restriction that all my algorithms must provably terminate is nearly invisible. There is a very simple general way to ensure that all programs in Coq terminate: augment each recursive function with one additional argument which is a counter which must always count down to 0 (at which point recursion must halt). On the initial call to a recursive function, select a starting value for this counter which is greater than the number of iterations the algorithm requires. (When proving correctness in Coq, you will be asked to prove that this starting value is in fact suitably high.) I have kept this requirement in mind when designing programs in other languages, and I have found it trivial to meet in all cases. Turing-completeness is not a feature I need in a programming language.
tome 11y ago
> I have never in two dozen years of coding needed to express something that wasn't expressible in some sub-Turing-complete language. This is a truism.
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?

mietek 11y ago

You are correct, but you are probably being downvoted because it is difficult to relate to your point of view. How many “sub-Turing-complete” languages can you list? Note “sub-Turing-complete” may not be the right term to use for all languages that do not admit general recursion. There is a particularly interesting subset of total languages for which the preferred term is “languages with control over non-termination”. http://www.cse.chalmers.se/~nad/publications/danielsson-semantics-partiality-monad.pdf http://www.cse.chalmers.se/~nad/publications/danielsson-sema... https://personal.cis.strath.ac.uk/conor.mcbride/TotallyFree.pdf https://personal.cis.strath.ac.uk/conor.mcbride/TotallyFree.... https://github.com/mietek/total-functional-programming https://github.com/mietek/total-functional-programming

colanderman 11y ago
There aren't many popular non-Turing-complete languages because most language designers are stuck in a cycle of redesigning Algol and Lisp for the umpteenth time. Very few new mainstream languages have anything new to say that applies to anything outside writing simple algorithms or gluing libraries together. Scala, Ruby, D, Rust, CoffeeScript, Clojure... I could go on. They're all just rehashes of the same ingredients. Why this is the trend I'm not sure, but I bet it's related to the fact that these same languages try to position themselves as complete ecosystems, rather than simple tools which form but part of an engineering solution. There's been some promising movement recently in the direction of DSLs. Reactive programming seems to finally be gaining popularity, which allows us to replace gobs of glue code with simple declarations. Erlang's OTP has been gaining popularity too, allowing declarative design in the large.
- kibwen 11y ago
  > Very few new mainstream languages have anything new to say > these same languages try to position themselves as complete > ecosystems, rather than simple tools This is where you answer your own implied question. Tools designed to excel at a singular task to the exclusion of general-purpose tasks will necessarily attract a comparatively niche audience. Tools designed for more general applications will attract people doing more general tasks, which is a more "mainstream" audience by definition.
  - colanderman 11y ago
    Yes, it is an unfortunate catch-22. I think the secret is that, due to their simplicity and analyzability, it's possible to make extraordinarily powerful DSLs that can truly excel at their tasks in a way that general-purpose languages can not. SQL is a perfect example of this. The fact that it is (barring recursive CTEs) not Turing-complete is what permits very intelligent automatic query optimization. I can write simple, clear, concise, performant SQL code that blows the pants off anything I can do without extraordinary effort in a general-purpose language. It is this that has made SQL so indispensable and enduring a tool.
    - nickpsecurity 11y ago
      Or you can get both with a powerful general purpose language subject to easy analysis and supporting DSL's. What I can do with that will blow the pants off your SQL. Matter of fact, I can start with a DSL for clarity/automation, manually optimize it if I choose in same language, and (if Scheme) compile that all the way down to logic gates. That's power right there.
      - colanderman 11y ago
        I'm not really sure the point of your post. Why should I roll my own relational query engine in Scheme when I can use one with hundreds of man-years of development, and thousands of man-years of testing behind it, like PostgreSQL? Also, I sincerely hope you're not trying to synthesize ASICs out of code from a language with constructs like call/cc.
Too 11y ago
I'm not sure if these are strictly non Turing complete or not but they are designed to do one thing only and they are still quite mainstream: makefiles, shaders, flex and yacc. SQL has already been mentioned, other database query languages are usually even more restrictive.

icebraining 11y ago

SQL is actually Turing-complete; using recursive CTEs, you can build a cyclic tag system, which has been proven to be Turing-complete.

colanderman 11y ago
You are very correct. I think there is still much to gain even from Turing-complete languages, where the Turing-completeness is relegated to one particular rarely needed construct. Beside the rest of the language being completely analyzable, that one piece that isn't easily stands out as a code smell.
Avshalom 11y ago
Yeah the reason there aren't many sub-turing-complete languages is because it's actually really hard to prevent turing completeness.
Retra 11y ago
SQL in its original incarnations is not Turing complete. It's mainly the bastardized, enterprised, heavily-extended versions built by people who have to sell it that are Turing complete.
- colanderman 11y ago
  To be fair, recursive CTEs are somewhat a blessing when you need to compute transitive closures. It is just unfortunate that they were designed as generative constructs (= you can create and recur on rows out of thin air rather than only products of other finite relations).
bordercases 11y ago
Turing-hard then?
mappu 11y ago
Recursive CTE's aren't universally present in SQL engines (e.g. MySQL doesn't have them)

nickpsecurity 11y ago

Does Coq actually run programs of any significance or do you have to extract to Ocaml, etc to get things done? SQL is certainly a practical, non-Turing-complete language. I'm with the other commenter wondering if those of you opposing Turing-completeness have a list of alternate languages that could replace what we use for systems, applications, web, etc with same productivity and efficiency. If they exist, I'll consider using them and benchmarking. So far, I mostly see articles opposing one thing without corresponding articles with alternatives. Look forward to see what you have as this is a topic I could certainly learn more about. Especially with the "LANGSEC" push throwing labor at it.

colanderman 11y ago
There aren't any, that's the problem. Because most language designers these days seem to think that the best way to solve problem X is to develop an entire closed-garden ecosystem that also can solve Y and Z, and ends up doing none of them well, while forcing you to use their language and only their language. Everywhere I've worked, I have seen the same things reimplemented poorly over and over again in general-purpose languages. Every system I've worked on is roughly a mash-up of database, dataflow graph, state machine, work scheduler, IPC, process coordination, programming in the large, and very low-level algorithmic stuff. Each of these could be factored out into a common simple language, but almost invariably they're just patterns imposed on C/C++/Java/what-have-you code. This greatly hampers understanding and analyzability. There are rare occasions I see DSLs used to fulfill these roles, and it's to great benefit. Working with a well-designed PostgreSQL database rather than some half-baked home-grown object database is a dream. You get a concurrency model that works, and you can extract graphs of your data model for free. Same with using a state machine description language like SMC rather than hand-coding stuff as C++ boilerplate. Same with using a process coordinator like Erlang's OTP (which isn't a DSL but is close enough). I'm not writing these posts to try to get developers to use DSLs more often. I'm writing them to try to get language designers to design DSLs more often. On Coq: Coq is not at all a practical programming language, since it has no concept of communication with external processes (i.e. I/O). This is exactly as it should be, since Coq is focused precisely on the domain of functional algorithms (and proofs). And, I have found that, within that domain, the restriction that all my algorithms must provably terminate is nearly invisible. There is a very simple general way to ensure that all programs in Coq terminate: augment each recursive function with one additional argument which is a counter which must always count down to 0 (at which point recursion must halt). On the initial call to a recursive function, select a starting value for this counter which is greater than the number of iterations the algorithm requires. (When proving correctness in Coq, you will be asked to prove that this starting value is in fact suitably high.) I have kept this requirement in mind when designing programs in other languages, and I have found it trivial to meet in all cases. Turing-completeness is not a feature I need in a programming language.

tome 11y ago

> I have never in two dozen years of coding needed to express something that wasn't expressible in some sub-Turing-complete language. This is a truism.

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?