4 ms·
"Mean time to turing completeness" is a mental metric that I use to decide whether making a domain-specific language is warranted or it would be better to just
by StefanKarpinski 13y ago
"Mean time to turing completeness" is a mental metric that I use to decide whether making a domain-specific language is warranted or it would be better to just use a general purpose language. If you can really limit the scope of the task to something non-turing complete, then a DSL might be a good idea. If you don't think you can keep the thing from becoming turing complete, you're going to fall prey to Greenspun's Tenth Rule [1] and you might as well skip all the nonsense and just use a Lisp in the first place (or another well-designed, fully powered language).
[1] http://en.wikipedia.org/wiki/Greenspun's_tenth_rule http://en.wikipedia.org/wiki/Greenspun's_tenth_rule
- eru 13y agoDeliberately limiting the power of your (domain specific) language can be a useful thing to do, too. As an example, SQL (ignoring the crazy bits) is so amenable to query optimization precisely because it is not Turing complete.
- nly 13y agoIndeed. Bitcoin transactions all contain validation scripts that are run through a stack-based interpreter. This Forth-like language does lack loops but, even after being there for years, the current client still only accepts a small set of standard templates.
- mtdewcmu 13y agoThis has been codified in the Rule of Least Power: http://en.wikipedia.org/wiki/Rule_of_least_power http://en.wikipedia.org/wiki/Rule_of_least_power
- tel 13y agoThis shows up all the time in the myriad Haskell eDSLs. Monad-based interfaces are obvious but throw away information that is useful for optimization (see http://homepages.inf.ed.ac.uk/slindley/papers/unembedding.pdf http://homepages.inf.ed.ac.uk/slindley/papers/unembedding.pd... for how to get some of it back). Applicative interfaces are really amenable to optimization, though (see Facebook's Haxl project: http://www.reddit.com/r/haskell/comments/1le4y5/the_haxl_project_at_facebook_slides_from_my_talk/ http://www.reddit.com/r/haskell/comments/1le4y5/the_haxl_pro...)
- eru 13y agoApplicatives were the example that I had in mind. See also http://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_applicatives/ http://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_ap..., or think about how regular expressions' limited power makes parsing with them a linear affair. (Incidentally, regular language parsers are Applicatives, too.)
- tel 13y agoAh! That was the blog post I was looking for... but I kept searching for "Cactus Applicative" with no luck.