skip to content

A configuration format's users want general loops; how do you decide whether to let it become Turing complete?

level: principalimportance: should knowfreq 33%

answer

  1. a guarantee traded, not a feature added
  2. collect the cases before designing
  3. who writes the files?
  4. bounded iteration covers most requests
  5. ship the bounds in the same release

basics

~20 s

Decide by what the platform must keep promising. Staying below completeness keeps evaluation bounded by inspection, so files stay reviewable, cacheable and safe to run from untrusted sources. Ask which repetition users actually need before trading that away.

solid answer

~50 s

Treat it as trading a guarantee, not adding a feature. While repetition is bounded — iteration over a collection the input already contains, no general recursion — an evaluator can bound any file's work from the file itself, which is what makes review, caching, cost estimation and running third-party content tractable. Start from the use cases: most requests for loops are "do this once per item I already have", which bounded iteration covers without crossing the line. If a genuine case needs unbounded repetition, prefer an **escape hatch** — let the file call out to a real program, generated or executed under its own bounds — over dissolving the property for every file. If you do cross, do it deliberately: budgets, per-tenant metering and isolation ship in the same release, because after the crossing they are the only bound left. It is close to a one-way door; users will rely on it immediately.

go deeper

for a junior

Understand the shape of the choice: a format that can only repeat over data it already has always finishes, while one with general recursion may not, and that difference is what the decision is about.

for a middle

Explain which constructs cross the line and what bounded iteration still covers, and be able to say why parsing is unaffected while evaluation is where the whole change lands.

for a senior

Show how you would bound the result either way — budgets, caps, isolation, per-author metering — and how you would separate the bounded requests from the genuinely unbounded ones before changing the format.

for a principal

Own the trade explicitly: name the guarantees the platform sells that rest on bounded evaluation, who depends on each, and why the change is close to irreversible once files rely on it. Decide, write it down, and ship the bounds with the feature.

## What the request is actually asking for "We need loops" is almost never a request for unbounded computation. Collected honestly, the cases usually split into three: 1. **Once per item I already have.** Render a block for each entry in a list supplied as input. Bounded: the trip count is the size of a value that is already present. 2. **Repeat until some computed condition holds.** Unbounded in general, because the condition depends on what the computation produces. 3. **Generate structure whose shape depends on computed values.** Also unbounded, and usually a sign the file is trying to be a program. Case 1 is most of the volume and does not require completeness. Cases 2 and 3 do. Separating them before designing anything is the whole decision, and it is the step most often skipped. ## What staying below completeness buys | Property kept | What it makes possible | |---|---| | Evaluation bounded from the file itself | cost estimates and admission control before running anything | | Guaranteed termination | safe evaluation of files from sources you do not control | | Static analysis of the whole file | linting, dead-branch detection, diffing an expanded result | | Deterministic, cheap re-evaluation | caching and pre-computation that actually hold | | A file a reviewer can read | review as a real control rather than a formality | Every one of these weakens the moment evaluation can run forever. Not all vanish — analysis is still possible on files that happen to be simple — but the *guarantee* is gone, and guarantees are what a platform sells. ## What it costs Be honest about the other side, or the decision reads as dogma: - Users with a genuine case-2 need will generate the format from somewhere else, and you lose visibility into the step that produced it. - A restricted format accumulates near-miss features — a special form for each shape someone needed — and can end up more complicated than the general construct would have been. - If the restriction is unprincipled, users route around it and you get completeness anyway, without the bounds you would have designed. ## When completeness is the honest answer Say yes when the artefacts are authored by people who already have full execution rights on the same system, the evaluation is not on a request path, and the cases you collected really are unbounded. In that setting the restriction protects nobody: the author could run arbitrary code a different way, and the format's incompleteness is ceremony. Say no when any of the following holds: files arrive from tenants, customers or contributors; evaluation runs inside a serving path; or the platform's promise depends on being able to expand a file cheaply and predictably. ## The middle path Before choosing either extreme, price the alternatives: - **Bounded iteration only.** Iterate over a finite collection present in the input. Covers case 1, keeps termination by construction. - **Recursion with a cap the file cannot raise.** Covers shallow structural nesting; every evaluation still terminates. - **An escape hatch.** The file names an external program that produces a fragment, executed under its own bounds and identity. The unbounded work is still available, but it is *visible*, isolated and metered, rather than hidden inside an expression. - **Generate the file upstream.** The full language exists where the platform is not the thing evaluating it, and what your evaluator receives is data again. The escape hatch is usually the best trade, because it keeps the property for the 95% of files that do not need to compute anything while giving the remaining few a supported route. ## How to decide 1. **Collect the cases**, and sort them into bounded and unbounded. Refuse to design from the abstract request. 2. **Name the guarantees** the platform currently makes that depend on bounded evaluation, and who relies on each. 3. **Identify who authors the files** and whether they already have execution rights on the evaluating system. 4. **Price the alternatives** above against the unbounded cases specifically. 5. **If you cross, ship the bounds in the same release** — step budget, depth cap, output and memory caps, per-author metering and isolated execution. Retrofitting bounds after users have written unbounded files is a migration, not a patch. ## Why this is close to a one-way door A restricted format can be extended later. A complete one cannot be walked back: within a release or two, files exist that depend on the construct, and each one is somebody's production configuration. That asymmetry is the reason to make the decision explicitly, with the guarantees written down, rather than to let it arrive as the fifth reasonable feature in a row. The stronger the pressure to "just add it and revisit later", the more the decision deserves the write-up.

  • If you allow completeness anyway, what must ship alongside it?
    The bounds that replace the lost guarantee: a step budget, an expansion-depth cap, output and memory ceilings, per-author or per-tenant metering, and evaluation isolated from any serving path. Also the diagnostics that name what consumed the budget. Retrofitting these once unbounded files exist is a migration with user-visible breakage, not an internal change.
  • Why is an escape hatch to an external program often better than in-format loops?
    It confines the unbounded work to a named, visible boundary that can be isolated, metered and attributed, while every file that does not use it keeps the termination guarantee. In-format general recursion removes the guarantee from all files, including the many that never needed it, and hides the computation inside ordinary-looking expressions.

saying these in an interview costs you the question

  • Says add the loops now, you can always take them out in a later release
  • Treats completeness as a feature checkbox rather than a guarantee given up
  • Assumes bounded iteration blocks every real use of repetition
  • Claims sandboxing untrusted files removes the need for evaluation bounds
  • Designs from the abstract request without collecting the actual use cases
  • Argues an external escape hatch is always worse than in-format recursion