Sunday, January 30, 2022

all languages => Touring Complete?

 Every Simple Language Will Eventually End Up Turing Complete – The Solution Space

Every simple language will develop enough new features to eventually end up Turing Complete.

...stumbled over this realization while working on Helm charts which are implemented in the form of a templating language on top of YAML, resulting in constructions such as the following beauty (extract from the bitnami/kafka chart):

Go Templating Language that this is based on is Turing complete. But what’s more interesting, is how we ended up with such a monstrosity rather than any other high-level language which would allow the same level of expressivity? Well, it’s because it started as a Simple Language.

... a humble proposal for the next time that you feel the need to use a simple configuration or markup language for a feature: Maybe consider an embedded domain-specific language instead. Start from a rich programming environment and include the simple configuration in the form of language constructs provided by the host language. All of a sudden, users have access to all of the abstraction tools that the host language offers – but in a way that does not seem bolted on.

Turing completeness - Wikipedia

Turing-complete or computationally universal if it can be used to simulate any Turing machine. This means that this system is able to recognize or decide other data-manipulation rule sets. Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete. The concept is named after English mathematician and computer scientist Alan Turing.

My observation: the actual problem is that there is no (common) universal way of "translating" between configuration / metadata and code.

Quite simple, when a "restricted subset" of high-level language, like a class or a module in OO language, is converted ("serialized") as data, this solves both issue of too much 
expressiveness (in general prog. languages) and too little expressiveness (in common data formats like JSON or YML) . A common "schema definition" could be applied to both code, in form of interfaces or classes and data, in form of "schema".

In fact this was actually done 50+ years ago by
Lisp language, just "forgotten" :)

Greenspun's tenth rule - Wikipedia

Any sufficiently complicated program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

The rule expresses the opinion that the argued flexibility and extensibility designed into the programming language Lisp includes all functionality that is theoretically needed to write any complex computer program, and that the features required to develop and manage such complexity in other programming languages are equivalent to some subset of the methods used in Lisp.

Other programming languages, while claiming to be simpler, require programmers to reinvent in a haphazard way a significant amount of needed functionality that is present in Lisp as a standard, time-proven base.

paul graham Books

No comments: