Comment by neongreen | Hacker News Reader

Comment by neongreen | Hacker News Reader

Parent Full thread

There are three (maybe more?) ways things can be Turing-incomplete:

1. You are limited to N evaluation/reduction steps.

2. The language doesn't include primitives like recursion or loops.

3. You can have recursion or loops, but the language makes you somehow prove that your program will terminate.

I think (1) would be fine, but I don't know any configuration languages that use this approach.

(2) is restrictive/annoying whenever you want to implement any logic in the config language library. Eg. a tool uses a homegrown data format BAML and you need to convert JSON to BAML in the config. Now either you have to write and manually call a preprocessor, or you need to use a patched version of the <config language evaluator> that will have JSON->BAML as a built-in, or you must implement JSON->BAML without loops or recursion. For a more realistic example, imagine that a certain config string has to be HTML-escaped and the config language doesn't provide a built-in for that purpose.

(3) -- you don't want it. There are languages (like Agda) that let you prove things like "this program terminates", but writing those proofs can be harder than writing the program itself.

I think the C preprocessor is an interesting example of (2), because the metaprogramming community has converged on an extremely clever paradigm to circumvent the lack of recursion: continuation machines. By defining a linear number of “continuation evaluation” macros, you can generate an exponential number of “recursive” macro expansions, which trivially scales to the point that it could take until the heat death of a universe for an arbitrary program to terminate, but a program can choose to terminate at any time. The Chaos-pp and Order-pp projects are good implementations of this!

I think 2) seems incorrect. What you can’t have is unbounded loops and recursion. Bounded loops are perfectly fine and I don’t tend to need unbounded ones when programming (with exceptions being infinite loops for handling asynchronous events, which a configuration language doesn’t need to do).

Recursion is trickier. I think banning it or simply limiting stack depth seems fairly reasonable? In fact I’m pretty sure most Turing-complete languages have a stack depth limit, so unbounded recursion is not allowed for those either. I don’t see a limit being a problem, because again this is a config language.

I don’t see why HTML escaping needs Turing-completeness. It shouldn’t need any unbounded iteration (it should be limited to the size of the input string) or unbounded loops. In general, I can’t think of any typical data processing code where turning completeness is required, but could be wrong. Do you have any practical examples of transformations that need unbounded iteration?

> I don’t see why HTML escaping needs Turing-completeness.

First of all, let's avoid "Turing-completeness" because then we might start arguing about whether a language with unrestricted recursion is or isn't Turing-complete since there are stack depth limits / memory limits / universe will end one day / etc.

I would phrase this question as "why would HTML escaping need unrestricted recursion or loops" -- since in practice config languages either have unrestricted recursion or loops (Nickel), or they don't (CUE, Dhall, Starlark).

For HTML escaping specifically, just having `.map(f)` and `.concat` available (in functional languages), or `for char in string` (in imperative languages), would be enough.

For something like HTML un-escaping, it's already trickier. If you are using recursion, your language needs to understand the concept of the string becoming "smaller" at each step. If you are using loops, `for ... in ...` is not enough anymore.

An even trickier example would be mergesort:

  merge(xs, ys) = ...

  mergeSort(xs) =
    let len   = xs.length
        left  = mergeSort(xs.slice(0, len/2))
        right = mergeSort(xs.slice(len/2, len))
    in merge(left, right)

It might seem obvious that this should terminate, because of course `.slice` will return a smaller array, but the actual termination proof in Agda is already something I wouldn't want in my config language: <https://stackoverflow.com/a/22271690/615030>

(Not to mention that this implementation is faulty and will loop at len=1.)

Limiting stack depth at [arbitrary number] -- this is similar to (1). I don't know why configuration languages don't do it, to be honest.

I think there is another option:

2a. The language includes limited primitives for recursion or loops.

If that’s done right, somehow proving that your program will terminate becomes trivial.

For example, allowing looping over a previously defined array with (key,value1) pairs to generate many more complex definitions that include common value2, value3, etc fields trivially guarantees termination, but a generic “while” loop doesn’t.

That will make you language less powerful, but IMO shouldn’t be problem for a configuration language.

In this example, I’m not sure you would even need that, as the language has ways to share common config values.

See my examples with html un-escaping and mergesort, down the comment chain.

Limited recursion/iteration is ok if all you need is to fill existing values into a template and possibly reduce repetition.

But in a large system with many components I might want to take a single timestamp, parse it, and generate timestamps in five different formats for five different subcomponents.

Or I might want to generate a piece of yaml config for an Ansible playbook that needs it, and now my config language needs to know how to escape yaml strings.

Or a config for a static site generator needs to be able to calculate a hash of a local css file because I’d like to use links like `style.css?hash` (a popular cache-defeating mechanism).

Or a certain path has to be split on “.” and reversed (Java-style com.example.blah things).

Or a Unix path needs to be converted to a Windows path, except [some special-cased paths that live in a map in an adjacent config].

There are endless reasons to want arbitrary logic in my config files, beyond reducing repetition. A lot of things I’ve listed are provided as primitives in various config/templating languages, but you always end up stumbling upon something that’s not provided.

Of course, one could say “You should use a real programming language for this kind of stuff”, and I’m happy that the JavaScript ecosystem is converging on allowing .js/.ts files for configs, because that’s exactly what I want too. But I’d like to have the same features available in projects that aren’t allowed to touch JS.

Reply on news.ycombinator.com