flang the compiler proves your program cannot hang 0.6.2 GitHub Русский

Back to README · Documentation index

Known limits

Stated plainly, because a project with undrawn borders is not one you can rely on. The same line is drawn in docs/overview.ru.md; the full lists are in flang/SPEC.md §10 and the "Долги" sections of the contracts.

Three words that are not confused here. The distinctions matter and the words sound alike, so:

The three words are not prose decoration: they are exactly what the proof report (flang check --proof) and the assistant service answer with, and this page does not use one for another.

Extending what is proven is possible — conditions that fit linear arithmetic are decidable — but attaching a solver to the verification conditions is an open task, not a feature.

The language.

The category surface. Morphisms, composition, chains, identities, functors, bifunctors, isomorphisms, monoids, groups and monads are implemented; a monad also comes with the binding form в монаде. Set relations are said with two words: вложение is a subobject (an arrow that glues nothing together), пересечение is a pullback over the ambient set. The shape of both is proved by matching declarations; injectivity of an embedding is checked on the author's own values and, when the arrow glues, the message presents the counterexample; non-emptiness of a common part is confirmed by a witness. Universality of the common part stays the author's assumption, and the compiler draws no consequences from it (flang/cat/SETS.md). Union did NOT become a word: the coproduct is already in the language — it is тип … вариант … with exhaustive разбор. An arrow may carry a law: даёт names the function, закон carries the examples, and a broken law fails flang test naming both the arrow and the law. Isomorphism invertibility is checked wherever both arrows are named through даёт, and stays the author's assumption wherever at least one is not. The precondition (требует) is implemented, and the caller discharges it, as in Dafny: inside the body it is a known fact the kernel reasons from, at every call site it is an obligation refused by name when unmet, and at the program boundary (--args, examples) it is computed because there is nothing to prove there. Its cost is named in bytes: a program with no требует at all emits byte for byte as before, and a program with one grows by exactly the door — 334 bytes in Python, 349 in Java, 369 in Elixir, 387 in C#, 452 in Rust, 462 in Go, 477 in C and 1 654 in JavaScript (flang/SPEC.md, "Предусловия функции"). Natural transformations are specified in flang/cat/SPEC.md and are not implemented. Category names in a functor declaration are a note for the reader, not a checked claim. A list — and anything recursive, I/O included — cannot be declared a monad today: the endofunctor map is printed in place, so the parameter must occupy a whole field (flang/cat/MONAD.md).

Concurrency. The scheduler in the C runtime runs in two modes. The checking one is a single thread interleaving by seed: it produces byte for byte the same delivery log as the witness, and that is what it is for. The second is a worker pool, switched on by the workers field in the request and measured directly: on a program with parallel work the pool is 1.85–4.80 times faster already at one run per handoff, and on a program with NO parallelism it is 6.7 times slower while burning fifteen cores (measurements in docs/scheduler-benchmark.md). THREE targets emit processes — C, Elixir and JavaScript; the other five (Go, Rust, Python, Java, C#) REFUSE to emit a program with процесс at all, with FLANG_CONC_UNSUPPORTED, rather than emitting half of it. породить spawns instances of declared kinds at run time in the witness and in target C; the JavaScript and Elixir schedulers answer that action with a named error. The parent names the child, because a described action cannot return anything; a message addressee must still be a literal, so you can only speak to a spawned process through the message it was born with; there is no distribution. The seed grid checks a finite set of interleavings — a checked claim, not a proof — and it gives no freedom from deadlock. The machine was never idle for any of the measurements (load 125–734 with 256 cores, and 60–1250 on the pool runs), so every time figure in them is an upper bound; the figures that do not depend on load (interpreter steps, reductions, bytes) are given separately and repeat run to run.