Surprisingly Turing-Complete
gwern.net
gwern.net
It seems to me you can either field these requests as they come in and get a hodge-podge of strangely-interacting features, or you can build some kind of general-purpose scriptability from the start. (Or you can follow the iPhone and 37 Signals and do it one way only, but often that is not an option.) So I've started to wonder about simply embedding a Javascript interpreter with access to a well-defined API into your application objects. Then people can do whatever they want! Of course this assumes savvy users, perhaps 90% an internal "services" team. But JS is easy to embed, e.g. therubyracer, was designed to be secure (no network/file/shell access), and is the most widely-known of all programming languages. What do other people think? Crazy?
What I actually find quite interesting about some of these products is the way they are architected to support multiple overlapping customizations from 3rd party vendors, customer specific customizations and the "core" of the application itself.
e.g. I've worked on an ERP project that had the base product, customizations within the product, very complex integrations with other systems and over ten 3rd party products that ran on the ERP systems own platform. That was fun... :-)
The scripting started pretty simple; one script type. It has access to all of our web services, and runs "as the user" but under a specific fixed permission set. The permission set limits the script to read-only services. It is passed simple data: a timesheet reference, and a user. It returns simple data: an array of dates, pay codes, and amounts to be paid. The scripts run under IronPython, so we're able to use .NET's security to prevent the script from accessing the file-system, network, etc. As an additional precaution, the scripts are run on isolated servers that are firewalled to only have network access to the web services servers, and importantly not the database servers or the Internet. Whenever a timesheet is updated, the pay output for that timesheet is marked as "needs recalculation", and the script is executed in a background task.
It was an ugly roll-out. Our first large customer ran into a ton of intermittent errors, which resulted in stale data calculations being used in actual payroll runs. But we fixed these problems quickly, and it's been incredibly smooth after that first month of hell.
And it was very successful. Its success lead to using scripts more and more for other parts of our application, which gives us some incredible per-tenant flexibility while maintaining a single core application. We've followed a few major rules that have helped:
(a) Scripts always do read-only operations; they can never access services that write data. This makes development of the scripts simple because they can be executed with no side-effects, which we leverage in the form of a script simulator that we provide in the UI.
(b) Scripts always have simple inputs, simple outputs. This is tricky every time we create a new type of script. We've found that the less we feed into the script as an input, the more it has to use services to retrieve data, which is actually a fantastically flexible approach. And the same with data output; it needs to contain the results of a calculation, which the script host then does stuff with.
(c) Background execution is far better than interactive execution. We design for background calculations now, making the UI show that "this is being calculated", and preventing certain operations while data is stale. This makes it easy to scale up and down our script servers, and the occasional badly written script doesn't have much of an impact outside of the specific tenant trying to use it.
Overall, the approach IS somewhat crazy. It's a lot more work than just implementing your product the way you want it to work. But for "enterprise customizability", it rocks.
Oh, and I just have to put this in here, because it's so deserving of a meme of its own... Edwin Brady of dependently-typed Idris fame(?) advocates a different and more, IMO, useful term: Pacman Completeness. If you can implement Pacman in $LANGUAGE, it's Turing Complete enough.
This is also why I find the likes of drools and cucumber utterly wrongheaded. (More generally, there's an antipattern of turing-complete configuration files - often when an organization has convinced itself that "code" needs to go through a long testing and deployment cycle but "configuration" doesn't). If you already have a programming language, use it.
I should probably have complained about HTML templating that allows a template to call into functions (or have logic in it itself), that's a bigger and clearer example of the problem.
I think the underlying principle here is that the more powerful languages need to be outermost. Having a powerful language call into a weak language to do something that needs to happen safely works well. Having a weak language call into a powerful language just results in a worst of both worlds - all of the danger but less of the power.
"But, but, we are making an assumption that a user has to click this particular button until the page doesn't change anymore (assuming infinitely long page [1])"
To which I say, poppycock. The purpose of CSS language is to apply styles to the webpage. Once it is processed, the CSS "program" has done it's purpose and is finished (i.e. halted). Running the same CSS "program" over and over again until it consistently produces identical results is not the point of CSS (unlike, say LaTeX/BibTeX compilation process, where you need to compile one file several times to get citation page numbers right, which is Turing complete). You might want to call it something else, like RCSS (repeated CSS). Then, RCSS is Turing complete, but plain CSS isn't. Much like a calculator that can calculate z^2 + C isn't necessarily Turing complete, while a graphical calculator that can draw a Mandelbrot fractal by iterating that formula is.
[1] which is acceptable, due to infinite memory assumption of a regular Turing machine
Also the possibility to compute anything possible computing with a turing machine. The fact that you can embed this logic into a style description language accidentally is a meme worth propagating, in my opinion.
The difference between being Turing complete and implementing rule 110 is crucial, and any discussion on the subject needs to make clear that these are not the same.
You are obfuscating the role of the driver. In the Turing machine, the driver is part of the Turing machine. In CSS, it is not, and has to be done by the user (or presumably a JS script).
As another post by Grue3 points out, almost any language can implement rule 110, including languages that are not Turing complete, and are explicitly said not to be Turing complete in the CS literature/community.
For example, Coq, Agda, Idris (with totality checking) and other languages based on Martin Lof type theory, are not Turing complete. That it why they are able to prove totality of their functions. But they can all implement rule 110 with no problem.
In particular, you could write some Agda/Coq/Idris program that implements rule 110, and has some trivial user interaction to repeat this until a stable pattern is reached. This simulates a Turing machine.
The article addressed this:
>but the declarations interact with each other just enough to allow an encoding of the cellular automaton Rule 110 (assumption: requires mechanical mouse clicks on the web browser to advance state; see also the Magic: The Gathering example)
[Note: I have omitted links embedded in the original text.]
The claim is not that CSS is Turing-complete, only that it can be used to represent the rules of a Turing-complete automaton. You still need to provide a physical driver.
The same is true of any other model of a Turing machine. If your host computer can simulate a Turing complete machine then the host is also Turing complete.
You can deduce the formulas, but can you make the formulas self-deducing when driven only by a mechanical clock like a steady mouse-click? Or will it require constant adjustment and intervention by the operator?
> But I'm sure we can all agree that this is not Turing completeness
I'm not sure we can. TC can be tricky. That's why people try to give constructions rather than just claim something or other is TC.
Maybe it's a browser-specific quirk; maybe it uses features only implemented after the initial explorations of turing-complete CSS; maybe there isn't any way to hook the two together. CSS will continue to add features over the years, though, and each added feature is another chance to find a missing piece that makes turing-complete CSS easier, more possible, and/or more powerful.
See http://assets.en.oreilly.com/1/event/27/High%20Performance%2... for proof.
Here's a pointer for you to get started: http://www.gamefaqs.com/boards/805618-super-mario-maker/7251...
This guy says he has built a single nand gate, but hasn't been able to connect several together.
As a gamer and a computer scientist, I find Turing complete games intriguing. Minecraft's Redstone is probably intentionally Turing complete, but for example the signalling of trains in OpenTTD probably is not.
http://arxiv.org/abs/1412.0784
I'd guess Super Mario Maker could be similar if monsters can infinitely spawn, be destroyed and interact with one another, skimming the paper it looks like a requirement.
This means you have to include Mario's position in your design if the device is larger than the horizontal simulation area. Just chaining together NAND gates isn't necessarily enough.
Non-turing complete languages are also easier to reason about, less susceptible to bugs and less susceptible to technical debt.
For this reason minimizing as much as possible the amount of turing complete code you write will make your code cleaner.
Configuration and tests in particular are usually best described in a non-turing complete language.
Well, except the technical debt of writing all the code in a language that may not support solving your problem once you know it better.
Better to start out and keep the core configuration representation simple (e.g. json, protobuf, ini file) and generated by something powerful like Flabbergast.org.
In nutshell to those who may not be familiar with the field: total languages differ from partial TC languages in that they must always include internally a "hit the reset button" exit from potential infinite loops, and this is enforced by the type system.
Since we can't actually observe an infinite number of program steps even in TC languages, this makes total languages effectively just as powerful as TC ones, but total languages are better-behaved in the sense that we can make a statically enforced distinction between provably terminating and possibly nonterminating code, therefore having all optimization/reasoning benefits in total parts, but also infinite processes in coindutive parts.
Then, total languages are just a subset of the non TC languages, and those are as prone to accumulating technical debit as TC languages. For avoiding technical debit, one needs something much less expressive.
Citation needed. Not my experience at all. Some well-designed total functional languages perhaps, but not non-turing complete languages in general, and not the typical alternatives for configuration and tests.
It's a hell of a lot cleaner than other DSLs, especially puppet's ruby-turing-complete one.
Then, through some hideous contortions of the syntax, someone managed to construct an "if" statement.
This caused so much CPU load they implemented it as a function.
And then it evolved into a horrifying accidental DSL, ParserFunctions.
They're now trying to rewrite all those clever templates in Lua, having given up avoiding Turing-completeness ...
The curse of Turing-completeness is: if you have it, you will soon have to use it.
http://beza1e1.tuxen.de/articles/accidentally_turing_complet...
Edit: Oops, I see this is already linked in the main article as “accidentally Turing-complete”.
Who doesn't want a Turing Complete monitoring language?
Ref: https://www.reddit.com/r/rust/comments/2o6yp8/brainfck_in_ru...
> why a perfect antivirus program is impossible
What does TC have to do with a perfect antivirus program? Does it have something to do with the Halting problem?
The user still has to manually intervene to advance each iteration of the loop. It would be Turing-complete except for that one little thing, but it's not quite there.