Are Helm Charts Turing-Complete?

Helm charts are one of the most widely adopted ways to provide flexible templates to configure Kubernetes objects. This article is certainly not for readers starting to work with Helm. It is more for chart developers, like me, who try to push template rendering to the limits from time to time.

Consider a Helm chart as a program, taking values as input and producing Kubernetes manifests as output. More generally, the output is just some long string. I asked myself if one can produce the same output one could produce with a Turing-complete language taking that same input.

If you expect a formal proof of Turing completeness down this article, you can stop reading here. You won't find it. You might want to read on, though, take this as an inspiration, and prove it yourself. I would be very interested in reading it.

Set up a Sample Chart

To be able to play around with the following examples, I recommend setting up the following sample chart.

mkdir -p turing/templates
echo '
apiVersion: v2
name: turing
version: 0.1.0
' > turing/Chart.yaml
echo '
{{- define "turing" }}
{{- .foo }}
{{- end }}
' > turing/templates/_helpers.tpl
echo '
output: |
  {{- include "turing" .Values | nindent 2 }}
' > turing/templates/output.yaml
helm template turing --set foo=bar

This should produce the following output.

# Source: turing/templates/output.yaml
output: |
  bar

Of course, this is no valid Kubernetes object, but should be sufficient to explain the concepts.

Iterative Factorial

Computing a factorial in a Helm chart is a nice problem, and will serve as an example for more complex algorithms.

First, let’s try to implement the iterative algorithm:

factorial n
  f = 1
  for i from 0 to n - 1
    f *= i + 1
  return f

In our Helm template, replace content of _helpers.tpl with

{{- define "iterative-factorial" }}
{{- $n := .n -}}
{{- $f := 1 -}}
{{- range $i :=  until ( int $n ) }}
    {{- $f = mul $f ( add $i 1 ) }}
{{- end }}
{{- $_ := set . "out" $f -}}
{{- end }}

{{- define "turing" }}
{{- $args := dict "n" .foo "out" 0 -}}
{{- include "iterative-factorial" $args -}}
{{- $args.out }}
{{- end }}

and run it

helm template turing --set foo=6
---
# Source: turing/templates/output.yaml
output: |
  720

The code in _helpers.tpl introduces the well known concept of procedure (or function) definitions, and procedure calls in a clunky syntax.

Procedures

Since there is no official way to define custom procedures or functions, one can mimic a procedure by defining a template. It takes a dictionary as input and is writing the result to the out value of that dictionary, as shown in the previous section.

{{- define "iterative-factorial" }}
{{- $n := .n -}} unwrap argument from dict
...
{{- $args.out }} write result to dict
{{- end }}

Calling such a procedure is a bit clunky as well, but demonstrates the concept.

{{- $args := dict "n" .foo "out" 0 -}} prepare the call
{{- include "iterative-factorial" $args -}} do the call
{{- $args.out }} access the result

Recursive Factorial

Implementing iterative algorithms in Helm templates are somewhat limited due to the limited range loop. It is a for-each style loop with no ability to break or continue (though this might come with Go 1.18).

Recursion is another way to implement complex algorithms. Thankfully, recursion is supported by Helm templates. It can be demonstrated with factorials as well. The algorithm is

factorial n
  if n ≤ 1
    return 1
  return n * factorial n - 1

Which can be implemented by replacing the content of _helpers.tpl with:

{{- define "recursive-factorial" }}
{{- $n := .n -}}
{{- if le $n 1 -}}
    {{- $_ := set . "out" 1 -}}
{{- else }}
    {{- $args := dict "n" ( sub $n 1 ) -}}
    {{- include "recursive-factorial" $args -}}
    {{- $_ := set . "out" ( mul $n $args.out ) -}}
{{- end }}
{{- end }}

{{- define "turing" }}
{{- $args := dict "n" .foo "out" 0 -}}
{{- include "recursive-factorial" $args -}}
{{- $args.out }}
{{- end }}

Run it again

helm template turing --set foo=6
---
# Source: turing/templates/output.yaml
output: |
  720

Conclusion

So are Helm Charts Turing-complete? My guess would be: yes. But, to be honest, I don’t know.

I have shown, though, how to define procedures and do recursion. In combination with branching (if, else) maths (add, sub, mul) and iteration (range) this gives a powerful toolbox. It allows implementing algorithms that you could implement with any other Turing-complete language.

Even if I cannot provide a definite answer, I think the demonstrated implementations of the well known factorial algorithm shows some concepts on handling more complicate problems in (library) Charts.

Should You Use these Patterns in Real Charts?

Implementing a large algorithm in Helm templates can be quite hard to test, given there are no unit tests for template functions. Also, reading code with the clunky syntax for procedure calls requires some experience. So I would say “use with care” and think twice before implementing something in a template.

My next article An Advanced API for Environment Variables in Helm Charts demonstrates a real world implementation of an algorithm in a chart.