23 ms·

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

by 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.
        fabulist 11y ago
        > Also, I sincerely hope you're not trying to synthesize ASICs out of code from a language with constructs like call/cc. Many EEs prefer to use functional languages. If you're wondering why, spend some quality time with Verilog and VHDL. Edit: Though after looking up call/cc, my guess is that hardware compilers don't support it.
- icebraining 11y ago
  You talk about Scala and Clojure, yet they agree with you about the advantages of DSLs, which is why both promote their features as DSL-building toolkits, and there are plenty of modules for those languages that provide DSLs. The thing with DSLs is that almost by definition, unless you're building something almost cookie-cutter, you can't build a whole system with a single one. So Scala and Clojure are supposed to be the common ground in which you use and connect the programs made in these DSLs. Of course, since these are internal DSLs, it's often hard or impossible to isolate the code written in the DSL from the rest of the program, so it's hard to apply optimizations and such, but you still gain the code reduction that you talk about.
  - fauigerzigerk 11y ago
    >Of course, since these are internal DSLs, it's often hard or impossible to isolate the code written in the DSL from the rest of the program Exactly, but that is also why you lose basically all advantages of DSLs. I don't think internal DSLs deserve to be called DSLs at all. They are simply libraries that tend to use a lot of operator overloading. The whole point of DSLs is to formally restrict what a given expression could possibly mean. That's what allows inference, optimization and sensible error messages that use the terminology of the DSL and not that of some underlying much more general language.
  - tel 11y ago
    It's trivial to via the use of types... So long as you have some amount of "purity" anyway.
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.

by mietek 11y ago

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.
      - fabulist 11y ago
        > Also, I sincerely hope you're not trying to synthesize ASICs out of code from a language with constructs like call/cc. Many EEs prefer to use functional languages. If you're wondering why, spend some quality time with Verilog and VHDL. Edit: Though after looking up call/cc, my guess is that hardware compilers don't support it.
icebraining 11y ago
You talk about Scala and Clojure, yet they agree with you about the advantages of DSLs, which is why both promote their features as DSL-building toolkits, and there are plenty of modules for those languages that provide DSLs. The thing with DSLs is that almost by definition, unless you're building something almost cookie-cutter, you can't build a whole system with a single one. So Scala and Clojure are supposed to be the common ground in which you use and connect the programs made in these DSLs. Of course, since these are internal DSLs, it's often hard or impossible to isolate the code written in the DSL from the rest of the program, so it's hard to apply optimizations and such, but you still gain the code reduction that you talk about.
- fauigerzigerk 11y ago
  >Of course, since these are internal DSLs, it's often hard or impossible to isolate the code written in the DSL from the rest of the program Exactly, but that is also why you lose basically all advantages of DSLs. I don't think internal DSLs deserve to be called DSLs at all. They are simply libraries that tend to use a lot of operator overloading. The whole point of DSLs is to formally restrict what a given expression could possibly mean. That's what allows inference, optimization and sensible error messages that use the terminology of the DSL and not that of some underlying much more general language.
- tel 11y ago
  It's trivial to via the use of types... So long as you have some amount of "purity" anyway.

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.