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.
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.
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-sema...
https://personal.cis.strath.ac.uk/conor.mcbride/TotallyFree....
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.
> 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.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.
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.
You can't synthesize "functional programs"; there's no analogue of recursion in hardware. You can only synthesize things that happen to look like functional programs because they're written using sexprs and macros and expand out to a static circuit graph which is exactly what Verilog is.
https://www.cl.cam.ac.uk/research/security/ctsrd/beri/
Also you might find Synflow's HDL interesting. It's on my backlog as I'd rather get diverse and experienced HDL users to put it through the paces. They have several, non-trivial IP for sale that they coded in it and for cheap, too.
http://scheme2006.cs.uchicago.edu/05-saint-mleux.pdf
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=E53...
Note: DDD scheme also supported call/cc. :P It wasn't in the final circuit, though, except as an execution feature.
"You can only synthesize things that happen to look like functional programs because they're written using sexprs and macros and expand out to a static circuit graph which is exactly what Verilog is."
Oh, come on, that's kind of cheating as you could say the same about almost any level of abstraction. You might as well say you can't synthesize the Verilog constructs: you just synthesize something that looks like it into a connection of analog transistors that it actually is. Yet, if you can use that model and it works, then it's a meaningful thing to say you can synthesize/use such a model to get X done with Y benefits instead of hand-stitching cell libraries and gates. Likewise, the more functional (or other) alternatives to Verilog with their advantages so long as they deliver on them in the field.
For my examples, SHard is a research prototype that works on some, limited examples. DDD was used on numerous real-world projects while the spin-off was still in business. Gone now. Bluespec is still kicking ass in industry. So, Bluespec at the least proves out the concept and its advantages over Verilog.
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.
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.
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.
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.
"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."
I was actually baiting you to blast you given I guessed the answer to number 1. However, I decided against it since you have the more reasonable position of identifying the problem then pushing responsibility onto language designers rather than users. Many posts seem other way around. So, that's refreshing. :)
"There are rare occasions I see DSLs used to fulfill these roles, and it's to great benefit."
I agree. iMatix, REBOL/RED, and LISP community (esp Racket) have shown it consistently in terms of productivity and reliability with performance being better sometimes. True even for general-purpose, systems programming: see Ivory langauge from Galois.
"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)."
OTP as a coordinator DSL I haven't thought about. Might look into it to see if there's design wisdom to learn for a future DSL outside of Erlang.
"I'm writing them to try to get language designers to design DSLs more often."
I know there's been some good books and essays on how to best design DSL's. Most of us don't know which ones are the good ones. Do you have any links for me or others following along on that? I figure the old wisdom augmented with lessons learned from LANGSEC stuff will be a good start.
" 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."
Wait, are we discussing avoiding Turing completeness or requirements for a termination proof? Termination proofs are done on code in Turing complete languages many times a year in academia. Harder than Coq model of an algorithm for sure but way more useful. I'll just let you elaborate on why you focused on that point.
So, trying to cut through the fog that remains, would you say a good approach is using a language like Haskell or ML that compiles to System F (Turing incomplete) with DSL's where possible? Aside from your DSL point, is building on or alternatives to things like System F what you would like to see?
" Turing-completeness is not a feature I need in a programming language."
Curious, how do you handle I/O and other OS interaction without making it so complex a new programmer must learn Haskell, monads, etc? Is there a simple route to that part of things?
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?
This is a truism.