What it looks like

Before dissecting what the language refuses, look at the language — if you are deciding whether you'd want to live in it, this is the whole tour. Starlark wears two faces, and if you can read Python, you can already read both.

The everyday face — the one you'd touch daily — is the BUILD file: pure declaration. Name a target, list its sources and dependencies, and you're done. No commands, no control flow, and the order of the blocks doesn't matter:

c_library(
    name = "hello_c",
    srcs = ["hello.c"],
    hdrs = ["hello.h"],
    policy = "strict",
)

c_test(
    name = "hello_c_test",
    size = "small",
    srcs = ["hello_test.c"],
    policy = "strict",
    deps = [":hello_c"],
)

Read the declarations as a graph, not a script. Each name creates a target node. A file in srcs or hdrs becomes an input edge; a target label in deps becomes an edge between targets. size = "small" is metadata on the test, so it changes no edge:

The second face lives in .bzl library files that BUILD files load(): a small, friendly Python — functions, for loops over collections that already exist, comprehensions, if / else — used to stamp out repetitive declarations. Here is a complete macro:

def echo_targets(names):
    """One rule per name — a for loop over a list that already exists."""
    for name in names:
        native.genrule(
            name = name + "_txt",
            outs = [name + ".txt"],
            cmd = "echo %s > $@" % name,
        )

echo_targets(names = [
    "alpha",
    "beta",
    "gamma",
])

Here is what "produces" means. A target declaration is a node; every label in srcs, deps, or data is an edge; evaluating the file is the mapping from one to the other:

Look again at that fan-out. The for loop walked names, a list that was fully formed before the loop began, so the interpreter knew its trip count the moment it entered — three. A loop whose length is fixed at entry is one the evaluator can, in effect, unroll: paste the body out once per element and throw the loop away. To the build system, the macro never loops at all. What it sees is three flat genrule declarations:

# echo_targets(names = ["alpha", "beta", "gamma"]) as the graph builder
# sees it — the loop unrolled to a flat, finite run of declarations:
native.genrule(name = "alpha_txt", outs = ["alpha.txt"], cmd = "echo alpha > $@")
native.genrule(name = "beta_txt",  outs = ["beta.txt"],  cmd = "echo beta > $@")
native.genrule(name = "gamma_txt", outs = ["gamma.txt"], cmd = "echo gamma > $@")

That is the graph on the previous page, written out as text — the three nodes the caption promised. The for was only ever shorthand for a fixed run of declarations.

That move has a name a systems engineer already knows: loop unrolling. When a loop's trip count is a constant the compiler can read, it can replace the loop with its body pasted out that many times — no counter, no branch back, no test at the top. It is a routine optimization, bounded loop on the left, flat sequence on the right. Read it in whichever language you think in:

# rolled
for i in range(3):
    total += a[i]

# unrolled
total += a[0]
total += a[1]
total += a[2]

// rolled
for i := 0; i < 3; i++ {
    total += a[i]
}

// unrolled
total += a[0]
total += a[1]
total += a[2]

// rolled
for (let i = 0; i < 3; i++) {
  total += a[i];
}

// unrolled
total += a[0];
total += a[1];
total += a[2];

/* rolled */
for (int i = 0; i < 3; i++) {
  total += a[i];
}

/* unrolled */
total += a[0];
total += a[1];
total += a[2];

Here is the whole essay in one sentence: what a compiler treats as an optional optimization for performance, Starlark enforces as a hard rule for computability. -funroll-loops is a favor you can decline; in Starlark the unrollability is the price of admission — a loop that couldn't be flattened would not be allowed to run.

And that is the line the whole language is drawn along. If every loop in a program can be unrolled into a flat, finite sequence, its evaluation can be unfolded into a finite, acyclic trace. A loop's exact bound may become known only when evaluation reaches it, but by then the finite collection already exists. That is the Turing boundary, stated in graph vocabulary. A while loop is the one construct that steps over it, because it cannot be unrolled: its trip count isn't a number the evaluator can read at entry — it's whatever the running program discovers about its own state, one iteration at a time. There is no finite sequence to paste out at the loop boundary, and so no promise that the pasting ever stops.

Do not confuse that evaluation graph with the build dependency graph the program emits. Non-Turing-completeness does not make dependencies acyclic: a terminating macro can still declare A → B → A. The two restrictions are independent. Starlark's bounded evaluation guarantees that Bazel finishes constructing the graph; Bazel's dependency model separately requires the resulting target graph to be a DAG. One bounds the graph builder. The other bounds traversal of the graph it built.

And that is very nearly the entire language. What you will never see in any Starlark file — what the rest of this essay is about — is either of these:

def countdown(n):
    while n > 0:
        n -= 1

def size(t):
    n = 1
    for k in t.kids:
        n += size(k)
    return n

So: Python's readable surface, minus the two constructs whose iteration count is discovered rather than declared. Why those two, exactly — and what refusing them buys — is where the dissection starts.

What Starlark refuses

Starlark looks like a small, friendly Python. It has functions, for-loops over collections, comprehensions, if / else, immutable data. What it pointedly lacks, you can read straight out of the parsers and evaluators of both implementations.

case WHILE -> "'while' not supported, use 'for' instead";

// Check recursion
if (!thread.isRecursionAllowed() && thread.isRecursiveCall(owner)) {
  throw Starlark.errorf("function '%s' called recursively", owner.getName());
}

The ladder and the cliff

"Not Turing-complete" sounds like a defect — as if the designers ran out of time. To see why it is a design, zoom out from Starlark for a moment. Machines — and the languages they interpret — come on a ladder, and every rung up trades analysis away for expressiveness.

On the bottom rung sits the finite automaton: a fixed set of states, no memory beyond which state it is in. It is what a regular expression compiles to, and it is completely transparent — does it halt (always), can it ever match, are these two machines equivalent: all decidable. One rung up, the pushdown automaton adds a stack — enough to match nested brackets and parse programming languages — and already the fog rolls in: whether two grammars describe the same language is undecidable. At the top stands the Turing machine: unbounded memory, unbounded time. That rung is where the general-purpose languages live — Python, Groovy, and, on paper, Buck2's Starlark.

Why the loss is a gain

Take it as given that a Starlark evaluation always halts — a theorem in Bazel's dialect, an operational fact in Buck2's. What does that guarantee unlock?

Its evaluation is analysis. This is the big one, and it's the thread back to the whole build systems series. A build system needs to know the dependency graph a BUILD file describes. The file does get run — evaluation is execution — but it is execution of a special kind: guaranteed to finish, forbidden to touch the world outside the file. If the file were written in an unrestricted language, the only fully general way to find out what it does is to run it with no such guarantees. Because Starlark's evaluation is bounded, it doubles as a safe, predictable analysis step: the engine can evaluate a package definition to extract its targets — the declarations-to-graph mapping drawn in the specimen section — confident it will terminate, and cache the result.

It can be cached and reused safely. A terminating, side-effect-free evaluation is a pure function from inputs to a graph. Same inputs, same graph — so the result is cacheable, shareable, and content-addressable, exactly the property Skyframe and DICE depend on. A language that could loop forever could not offer that, because "the result of evaluating this file" might not exist.

It can be parallelized and sandboxed. Evaluations that are guaranteed to terminate and don't perform arbitrary I/O can be run concurrently across packages without fear of one wedging a core forever. Bounded computation is safe computation, in the very concrete sense that the build tool can run a lot of it at once and trust it to come back.

Be honest about the load-bearing walls, though. Two more properties share the weight, and they are precisely the ones both implementations kept: hermeticity — a Starlark file cannot read the filesystem, the clock, or the network; effects exist only through what the engine injects — and freezing — module globals become immutable once a file finishes loading, so parallel evaluation cannot race. Termination guarantees the answer exists; hermeticity and determinism guarantee it is the same answer everywhere. Buck2's dialect keeps safe caching and parallelism while permitting recursion, which is strong evidence that those shared properties, not the recursion ban, carry most of the load. What the recursion ban adds — and it is Bazel's deliberate stance — is that the termination half holds as a fact about the language rather than a fact about one runtime's fuel gauge.

Contrast this with the survey's cautionary example, Gradle, whose build scripts are full Groovy and Kotlin. Because that configuration can do anything, Gradle has to actually execute it to learn the graph — and then bolt on a "configuration cache" to avoid paying that cost twice. The configuration cache is the price of an unbounded language. Starlark declines to incur it by declining the power that creates it.

The general shape: the bounded fixed point

Starlark is one instance of a pattern that shows up wherever a system has to reason about programs rather than merely run them. The right primitive is rarely the most powerful one; it's the most powerful one that stays decidable.

• A DAG forbids cycles, so a topological order — and termination — always exists.
• A CRDT forbids the operations that wouldn't commute, so concurrent merges can't conflict.
• A regular expression (the real kind) forbids backreferences, so an automata-based engine (RE2, Rust's regex, Go's) can match it in linear time — the guarantee lives in the engine, not the syntax: a backtracking engine can still blow up on nested quantifiers alone.
• Starlark, in Bazel's dialect, forbids unbounded computation, so its programs can be analyzed, cached, and parallelized.

In each case the restriction isn't a compromise grudgingly accepted — it's the enabling condition. You give up the unbounded version precisely because the bounded version has a property you need more than you need the power. The art of designing these systems is finding the boundary: general enough to express what users actually need, bounded enough to keep the property that makes the system tractable.

Is bounded enough?

The fair objection: doesn't real build logic sometimes need a loop of unknown length, or recursion? In practice, remarkably rarely. The work a BUILD file does — declare targets, glob files, map over a known list of sources, compose rule calls — is naturally bounded; it's iterating over things that exist, not searching an open-ended space. When a genuinely complex transformation is needed, it lives in a rule implementation or a provider, structured so the engine can still treat the whole thing as a bounded, analyzable unit. The constraint pushes complexity to where it can be managed rather than letting it leak into the configuration layer where it would poison analyzability for everyone.

def collatz_steps(n):
    steps = 0
    while n != 1:          # ← trip count: unknown to mathematics
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1
    return steps

def collatz_steps(n, fuel):
    """Steps for n to reach 1 — within a budget declared up front."""
    steps = 0
    for _ in range(fuel):
        if n == 1:
            return steps
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1
    return -1  # out of fuel: "no verdict yet" is an answer too

Lessons

• Starlark, as specified and as Bazel enforces it, is deliberately not Turing-complete: no while loops (rejected at parse time by both implementations, with no flag to enable them) and no recursion (a dynamic error in Bazel, checked against declarations so the Y combinator can't sneak it back in).
• Buck2's starlark-rust takes the spec's explicit license and allows recursion, bounding it with fuel instead — a 50-frame call stack by default. There, "every evaluation halts" is a runtime backstop, not a language guarantee.
• The refusal has a pedigree: loops whose bound is fixed at entry compute exactly the primitive recursive functions — total, analyzable, and enough (Meyer & Ritchie, 1967). while — or recursion, the same door by another name — is precisely what tips a language over the cliff where Rice's theorem makes every question about behavior undecidable.
• The payoff of guaranteed termination: evaluating a build file is the analysis — a pure, always-finishing function from inputs to a graph — so the result is cacheable, shareable, and parallelizable.
• The properties both engines kept — bounded loops, hermeticity, frozen modules, deterministic evaluation — are what safe caching and parallelism actually ride on; the recursion ban is Bazel's stance on top, making termination a property of the language itself.
• The cost of an unbounded language is concrete: Gradle must run its Groovy/Kotlin scripts to learn the graph, then cache the execution.
• A total language never solves the halting problem — it refuses the programs that would pose it. The Collatz-length function is the test case: the while version is a parse error before any mathematics is consulted, and the fuel version is total by construction. Sound, not complete — and the guarantee composes: primitive recursive functions are closed under composition and the DAG glue preserves termination, so verified parts do make a verified whole, for this property.
• This is the bounded fixed point pattern: the right primitive is the most general one that stays decidable. DAGs, CRDTs, and regular expressions all make the same trade — the restriction is the feature.

Practice

References

1. Powell. “Mind Your Language: “The First Lesson”.” London Weekend Television, 1977. — Ali Nadim's “hopping to be unrolled” malapropism opens the episode; transcript
2. “The Starlark language.” Bazel docs. — · the Starlark spec, whose recursion rule is a dynamic error "an implementation may allow clients to disable"
3. “net.starlark.java.” Bazel source. — Parser.java (while rejection), StarlarkFunction.java (recursion check), StarlarkSemantics.java (ALLOW_RECURSION, "not exposed to Bazel")
4. “starlark-rust.” — Buck2's independent implementation; recursion allowed — DEFAULT_STACK_SIZE = 50 in eval/runtime/evaluator.rs (a depth cap is the proof it's legal); started by Damien Martin-Guillerez
5. “Starlark credits.” starlark-go README. — the designers and implementors, named — the Java team, and Alan Donovan & Jay Conrod's Go implementation with a scanner after Russ Cox
6. “Buck2 per-file-type dialects.” Buck2 source. — BUCK files get enable_def: false; .bzl gets the full language
7. “Turing completeness.” — and the halting problem for the theory
8. “The complexity of loop programs.” Meyer & Ritchie, Proc. ACM 1967. — bounded loops compute exactly the primitive recursive functions — the rung Starlark stands on (PDF at MIT)
9. Turner. “Total Functional Programming.” J.UCS, 2004. — the design school Starlark practices: every program terminates by construction (PDF)
10. “Rice's theorem.” — why everything above the cliff must be run to be known
11. Lagarias. “The 3x+1 Problem and its Generalizations.” Amer. Math. Monthly, 1985. — the Collatz survey where Erdős's "Mathematics may not be ready for such problems" is recorded; the conjecture — checked past 2⁷¹, proven for none of the rest — is the program a total language declines to accept
12. Tao. “Almost all orbits of the Collatz map attain almost bounded values.” Forum of Mathematics, Pi, 2022. — the partial result and its exact limits; Tao's proof overview explains the Syracuse map, the failed naive iteration, and the mixing argument
13. “Dhall.” — a config language on the same rung; the eBPF verifier is the same trade inside the kernel
14. Shapiro, Preguiça, Baquero & Zawirski. “Conflict-free Replicated Data Types.” SSS, 2011. — the bounded-by-design sibling, from the source (PDF) · DAGs as another

Mangalapilly, Y. J. (2026, June). A Language That Can't Loop Forever. Saṃhitā Notes. https://yesudeep.com/blog/a-language-that-cant-loop-forever/

@online{mangalapilly2026a,
  author  = {Yesudeep Jose Mangalapilly},
  title   = {A Language That Can't Loop Forever},
  journal = {Sa\d{m}hit\=a Notes},
  year    = {2026},
  month   = {June},
  url     = {https://yesudeep.com/blog/a-language-that-cant-loop-forever/},
  urldate = {2026-07-13},
}

Yesudeep Jose Mangalapilly. “A Language That Can't Loop Forever.” Saṃhitā Notes, 2026. https://yesudeep.com/blog/a-language-that-cant-loop-forever/.

TY  - ELEC
AU  - Mangalapilly, Yesudeep Jose
TI  - A Language That Can't Loop Forever
T2  - Saṃhitā Notes
PY  - 2026
UR  - https://yesudeep.com/blog/a-language-that-cant-loop-forever/
Y2  - 2026-07-13
ER  -