Every Simple Language Will Eventually End Up Turing Complete

It is a cliche of the software world that change is the only constant. Nevertheless, despite the constant mushrooming of new technologies, it seems that some principles stay surprisingly constant, at least during the period that I can remember.

In this article, I would like to propose one such constant by postulating the theorem of simple languages: Every simple language will develop enough new features to eventually end up Turing Complete.

I 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):

{{- if (include "kafka.createJaasSecret" .) }}
apiVersion: v1
kind: Secret
  name: {{ template "kafka.fullname" . }}-jaas
  labels: {{- include "common.labels.standard" . | nindent 4 }}
    {{- if .Values.commonLabels }}
    {{- include "common.tplvalues.render" ( dict "value" .Values.commonLabels "context" $ ) | nindent 4 }}
    {{- end }}
  {{- if .Values.commonAnnotations }}
  annotations: {{- include "common.tplvalues.render" ( dict "value" .Values.commonAnnotations "context" $ ) | nindent 4 }}
  {{- end }}
type: Opaque
  {{- if (include "kafka.client.saslAuthentication" .) }}
  {{- $clientUsers := coalesce .Values.auth.sasl.jaas.clientUsers .Values.auth.jaas.clientUsers }}
  {{- $clientPasswords := coalesce .Values.auth.sasl.jaas.clientPasswords .Values.auth.jaas.clientPasswords }}
  {{- if $clientPasswords }}
  client-passwords: {{ join "," $clientPasswords | b64enc | quote }}
  {{- else }}
  {{- $passwords := list }}
  {{- range $clientUsers }}
  {{- $passwords = append $passwords (randAlphaNum 10) }}
  {{- end }}
  client-passwords: {{ join "," $passwords | b64enc | quote }}
  {{- end }}
  {{- end }}
  {{- $zookeeperUser := coalesce .Values.auth.sasl.jaas.zookeeperUser .Values.auth.jaas.zookeeperUser }}
  {{- if and .Values.zookeeper.auth.enabled $zookeeperUser }}
  {{- $zookeeperPassword := coalesce .Values.auth.sasl.jaas.zookeeperPassword .Values.auth.jaas.zookeeperPassword }}
  zookeeper-password: {{ default (randAlphaNum 10) $zookeeperPassword | b64enc | quote }}
  {{- end }}
  {{- if (include "kafka.interBroker.saslAuthentication" .) }}
  {{- $interBrokerPassword := coalesce .Values.auth.sasl.jaas.interBrokerPassword .Values.auth.jaas.interBrokerPassword }}
  inter-broker-password: {{ default (randAlphaNum 10) $interBrokerPassword | b64enc | quote }}
  {{- end }}
{{- end }}

Needless to say, the 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.

In this case, the Simple Language in question was YAML. YAML was selected as a way to configure Kubernetes. The idea was to provide a simple declarative description of a cluster deployment. A good candidate for a human-readable configuration format like YAML, one should think.

However, people started using these configurations to manage their clusters, they grew more complex and a natural question arose: Can’t we make it possible to abstract out common pieces of this infrastructure and make them parameterizable so that we can reuse them across projects? And so the concept of a Helm Chart was born. As YAML itself does not support the necessary abstractions, the Go Templating Language was added on top as a mechanism to inject values into configuration files dynamically.

This evolution has an eerie resemblance with the web development of the late 90s and early 2000s. Take the origin story of PHP for example. Again, we start with a Simple Language, this time not for configuration but markup: HTML. Rasmus Lerdorf noticed, that for his needs, a simple markup language did not provide the necessary abstraction capabilities and so he built a simple preprocessor to generate HTML based on parameters. This was not supposed to be a full programming language at the time but with more and more use cases, more and more involved abstractions were required:

I don’t know how to stop it, there was never any intent to write a programming language […] I have absolutely no idea how to write a programming language, I just kept adding the next logical step on the way.

Rasmus Lerdorf

PHP went full circle when it ended up so feature-rich that people started implementing new templating languages in PHP to inject values in HTML files which in turn quickly started to grow in complexity.

Why Does This Matter?

Is it a problem for a language to be Turing complete? I don’t think it is. Certainly, Turing complete languages are a much more difficult target for static analysis. However, that does not stop us from statically checking parts of the language if needed. Turing completeness is just a measure of expressivity. It is, however, true that more expressive languages have a need for additional facilities and language features to deal with the additional complexity and a templating language on top of YAML does not have these facilities.

Therefore, I want to make 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.

This is not a universal strategy of course. SQL may be a valid counterexample. Well, SQL with recursive common table expressions is actually Turing complete, so it should probably be counted as an instance of the law I propose. Nevertheless, SQL really benefits from the ability to run static analysis so there would be value in sacrificing expressivity.

There’s also the valid concern that users of an embedded DSL need the full developer toolchain to work with your system. For instance, during that phase in which I spent way too much time compiling Gentoo Linux and configuring Emacs, I ran the xmonad window manager whose configuration is an embedded DSL built on top of Haskell. This means that any configuration update is equivalent to recompiling a Haskell application! For situations where the person editing the configuration is not also a developer, this seems inappropriate.

Nevertheless, I really think most developers would benefit from working in a type-checked declarative subset of a higher programming language instead of configuring Kubernetes deployments in a moloch of templated YAML. Building and sharing your own abstractions would come for free.

Note: I should mention that there are some attempts to add embedded DSL layers in various languages on top of Kubernetes. I remain curious where these attempts will lead. However, in tech, it is not always about technical superiority and once a technology like Helm is the de facto standard, all alternatives face an uphill battle.

2 thoughts on “Every Simple Language Will Eventually End Up Turing Complete

Add yours

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: