skip to content

A review gate counts a file's lines exactly but can only guess whether a function ever returns a negative number, so why?

level: middleimportance: must knowfreq 55%

answer

  1. text versus behaviour
  2. answerable without running it
  3. nontrivial means some yes, some no
  4. properties of the computed function
  5. Rice's theorem, not a tool defect

basics

~20 s

Line count is a syntactic property, readable from the text itself. Whether a function ever returns a negative number is a property of the function it computes, and Rice's theorem makes every nontrivial property of that kind undecidable.

solid answer

~40 s

The gate is running two incomparable kinds of check. Counting lines is *syntactic*: a property of the program text, answered exactly by parsing. Asking whether a function can ever return a negative number is *semantic*: a property of the input-to-output function the program computes. Rice's theorem says that every nontrivial semantic property of that kind is undecidable, where nontrivial just means some programs have it and some do not. No algorithm answers it correctly for all programs, at any budget. So the gate cannot compute the real answer and instead computes a decidable approximation of it, which is precisely where its false positives come from. The working test: if you can answer the question by reading the code without imagining it running, a tool can too.

go deeper

for a junior

Recall the split. Questions about what the code says can be answered exactly by a tool; questions about what the code does when it runs cannot be, in general.

for a middle

Explain what makes a property semantic — it concerns the input-to-output behaviour rather than the source — and why nontriviality has to be checked before undecidability follows.

for a senior

Show how the limit reaches your pipeline: which checks in your gate are exact, which are approximate, and how that split decides which ones may block a merge.

for a principal

Frame it as a policy question. Precision is bought by restricting what engineers may write or by making them assert facts, so this is a language and process decision rather than a tooling purchase.

## Two questions that look the same from outside A review gate runs dozens of checks in one pass and prints one list of findings, so every check looks alike. Underneath they fall into two populations that are not comparable. - A **syntactic** property is a property of the program *text*: how long a file is, whether a construct appears, how deeply blocks nest, whether a declared name is mentioned anywhere else in the file. A tool answers these by parsing the text and walking the resulting tree. The answer is exact and the cost is roughly the size of the file. - A **semantic** property is a property of the *function the program computes*: the relation between the inputs it is given and the outputs it produces, including the inputs on which it produces nothing at all. Whether a function can ever return a negative number, whether two implementations agree on every input, whether a result reaching a call site can be absent, whether a function is total — all semantic. One test separates them. Ask: could two programs that compute exactly the same input-to-output function receive different answers? For line count, yes — the same function can be written long or short — so line count is syntactic. For 'ever returns a negative number', no — that is fixed by the function itself — so it is semantic. ## What Rice's theorem states Rice's theorem is a statement about the second population only. Take any property of computed functions. Call it **nontrivial** when at least one program's function has the property and at least one program's function does not. Rice's theorem: for every nontrivial property of that kind, there is no algorithm that takes a program as input and decides correctly, for all programs, whether the function it computes has that property. Three words carry the weight. 1. **Property of the computed function.** Not of the source text, not of one particular run on one particular input. The standard argument reduces the halting problem to the property, which is why the limit here is the same limit. 2. **Nontrivial.** A property held by every program, or by none, is decidable — the correct procedure prints a constant. That is the only escape the theorem leaves on the semantic side. 3. **Undecidable, not merely expensive.** This is not a claim about time or memory. There is no procedure that gets it right everywhere, at any budget, on any machine. ## Why the gate behaves the way it does | Check the gate runs | Kind | Exact? | |---|---|---| | File exceeds five hundred lines | syntactic | Yes, by counting | | A declared name is never mentioned again | syntactic | Yes, by scanning | | Two implementations agree on every input | semantic | No | | A function can return a negative number | semantic | No | | A value reaching this call site can be absent | semantic | No | Because the exact answer to a row in the lower half does not exist, whoever built the check answered a *different*, decidable question near it. Typically the tool models a superset of the values that can flow into a site and reports the site whenever the bad value is somewhere in that superset. The model contains combinations the program never actually enters, so the report fires on situations that cannot occur. That is the finding the author is objecting to. It is not a defect in the tool; it is the price of any answer existing at all. ## Reading a finding correctly - Read every behavioural finding as **could not rule out**, never as **this happens**. - Judge such a check by how often its findings survive review, not by whether it is ever wrong. - Expect style and structure rules to be exact, and hold them to that standard. - Expect a behavioural rule to need annotations, a narrowed language, or a suppression path, and budget for that before you turn it on. - Never argue a gate into exactness. Argue instead about which direction it is allowed to be wrong in. ## Where the same limit shows up elsewhere The limit is not confined to linting. It is why an optimiser cannot remove every branch that can never run, why nobody ships a general checker that proves a refactored function equivalent to the original, why a taint rule over-warns on data that is sanitised through a path the model cannot follow, and why a coverage tool reports lines that the test suite could never have hit. Each of those tools is answering a behavioural question and each has chosen a direction to be wrong in. ## What this does not say Rice's theorem does not say that analysis is hopeless. It says exactness is unavailable for behavioural questions **in general** — for all programs, including adversarial ones. Real analyzers are useful because real code is not adversarial: most functions are short, loop over bounded structures, and touch few values that come from outside. An approximation that is coarse in theory is often exact on them. The theorem fixes the *shape* of the tool — one-sided error, escape hatches, a human able to assert what the tool cannot derive — not its usefulness.

  • Does Rice's theorem apply to a property of the source text, such as a function being longer than fifty lines?
    No. The theorem is about properties of the function a program computes, not about the program text. Textual and structural properties are decidable by parsing, and the reason is visible in the test: two programs with identical behaviour can easily disagree on length, which is exactly what disqualifies length as a property of the computed function.
  • If the exact question is undecidable, how is the gate useful at all?
    It answers a decidable question near the real one. It computes a superset or a subset of the program's possible behaviours and reports on that instead, accepting one class of wrong answer in order to eliminate the other. The usefulness comes from the error being one-sided and predictable, not from it being absent.

Counting the pages of a recipe is reading; knowing whether the dish ever comes out salty means cooking it. No amount of re-reading substitutes for the cooking.

saying these in an interview costs you the question

  • Claims a better tool would remove the approximation entirely
  • Calls unreachable-code detection a parsing problem
  • Thinks the limit only affects loops and recursion
  • Says bounded memory makes the analysis practical, ignoring state explosion
  • Treats every warning as a tool defect rather than an approximation