typed-peg-0.3.0.0: CHANGELOG.md
# Changelog
## Unreleased
### Breaking. The environment no longer carries FIRST sets
An entry of a grammar's environment was a rule's nullability, its FIRST set
and its result type. It is now the result type:
```haskell
type CalcEnv =
'[ '("expr" , 'EnvEntry Expr) -- was 'EnvEntry ('MkTy 'False '["atom", "term", "unary"]) Expr
, '("term" , 'EnvEntry Expr)
, '("atom" , 'EnvEntry Expr)
]
```
`PExp` loses its `ty` index and is now `PExp s env a`; `Grammar` is
`Grammar s env a`. `PEG.Type.Ty`, `Nullable`, `First`, `TyOf`,
`PEG.Syntax.SeqTy`, `ChoiceTy`, `NTTy`, `NTGo`, `PEG.Grammar.Acyclic` and the
sorted-set families in `PEG.TyLevel` — `Union`, `Elem`, `ConsIfAbsent`, `If`,
`And`, `Or`, `SymEq` — are gone. A grammar written with `pegGrammar` needs no
change; one that writes its environment by hand needs the `'MkTy` component
deleted from each entry and the `ty` argument deleted from its signatures.
**Why.** The FIRST sets in the environment were the entire cost of compiling
a large grammar, and the measurement that says so is that *not computing them
was worth nothing*. A mode that kept the large environment but handed GHC
every rule's index as a literal, so that `SeqTy`, `ChoiceTy` and `Union` were
never reduced, ran no faster than one that reduced them all. What cost was
the environment being `O(N^2)` type nodes and each of the `2N` reference
constraints being solved against it: in the micro-benchmark, giving each entry
a payload that no type family ever reads takes `N = 64` from 0.77 s to 11.8 s
and exhausts 8 GB at `N = 96`.
**What it bought**, on a grammar of `N` mutually referring rules
(`bench-compile/`, `ghc -fno-code`):
| N | before | after | |
|---|---|---|---|
| 64, environment by hand | 15.15 s | 1.99 s | 7.6x |
| 64, through `pegGrammar` | 7.23 s | 1.19 s | 6.1x |
| 128, through `pegGrammar` | — | 5.28 s | |
The curve changed and not only the constant: doubling the grammar from 32 to
64 rules used to cost about 8x and now costs 3.3x, so what was cubic in the
number of rules is closer to quadratic. A 128-rule grammar through
`pegGrammar` now costs less than a 64-rule one did.
Two shapes that used to differ by 4.9x — a rule beginning with a non-terminal
against one beginning with a terminal — are now indistinguishable, which is
the check that the cost is gone rather than moved.
**Leaving the environment to inference now works.** `Grammar s _ a` with a
wildcard environment used to be unusable: GHC inferred entries full of
unreduced type-family applications and was past 24 GB of heap at `N = 16`.
There are none left to leave unreduced, and it is now within noise of writing
the environment out — 2.25 s at `N = 64`. A hand-written rule set need not
declare an environment at all.
**What this gives up.** Left recursion was a type error, checked on every
compilation by `Acyclic`. It is now checked once, by `PEG.Analysis`, when
`pegRules` or `pegGrammar` splices the grammar — which is where it was already
reported, with the rule and its cycle named, and which is the message you
actually saw. What is no longer checked at all:
- A `Rules` chain assembled by hand from `RCons`, with no quasi-quoter
involved. A rule that begins with itself compiles and loops.
- Left recursion that closes *across* two `pegRules` blocks spliced together.
A block is analysed open-world, since `RCons` lets two be combined, and
`Acyclic` used to be the backstop. Writing the grammar as a single
`pegGrammar` closes the gap: it is closed-world.
`Star` no longer demands a non-nullable operand, for the same reason; a
nullable repetition is reported by `PEG.Analysis`, and by nothing at all if
the `Star` is built by hand.
**What this makes simpler.** A combinator over expressions is now an ordinary
polymorphic function. What had to be written
```haskell
lexeme :: PExp s env ty a -> PExp s env (SeqTy ty ('MkTy 'True '[])) a
```
is `PExp s env a -> PExp s env a`, and composes without the caller having to
get a nesting of type families right. `examples/Patterns.hs` is where that
shows.
**And what now keeps the analysis honest.** While the FIRST sets were also in
the types, `PEG.Analysis` could not be quietly wrong: `Grammar` demands
`Rules s env env`, so GHC recomputed everything and rejected an environment
that did not match. It no longer does. The `typed-peg-analysis` test-suite
therefore checks the analysis against a separate statement of what its results
mean — nullability as a least fixpoint, and a FIRST set as the transitive
closure of the one-step head relation — over every grammar in `examples/` and
over 400 generated ones, and asserts that the generated corpus keeps
containing both left-recursive and left-recursion-free grammars so the
agreement cannot go vacuous.
### Grammar checking at splice time
The environment a grammar declares is no longer something only GHC can
compute. `PEG.Analysis` runs the same nullability and FIRST-set fixpoint in
ordinary Haskell, over the quasi-quoter's syntax tree.
*(Superseded above: the environment no longer states either, and
`PEG.Analysis` is the only thing that computes them.)*
Measurement first, because it redirected the work. On a synthetic grammar of
`N` rules with `2N` non-terminal occurrences (`bench-compile/`, `ghc -fno-code
-freduction-depth=0`):
| N | environment written by hand | same, FIRST sets emptied | same, indices handed to GHC as literals |
|---|---|---|---|
| 16 | 0.59 s | 0.55 s | 0.52 s |
| 32 | 1.80 s | 1.09 s | 1.43 s |
| 48 | 6.39 s | 1.97 s | 5.19 s |
| 64 | 18.25 s | 3.75 s | 14.99 s |
Left to inference, the same grammar runs out of memory rather than time: at
`N = 16` GHC was past 24 GB of heap and still climbing. It does derive
exactly the environment the examples write by hand — the entries it derives
are just full of unreduced type-family applications.
And, isolating the environment search alone — `N` entries, `2N` references:
| N | `Lookup` + `KnownMember` | witness, equality kept | witness, no equality |
|---|---|---|---|
| 32 | 0.55 s | 0.20 s | 0.18 s |
| 64 | 3.37 s | 0.86 s | 0.56 s |
Three quarters of it is the instance chain, and that quarter-to-three-quarters
split is the useful part: supplying the proof while keeping the `Lookup`
equality — so the reference still cannot name the wrong rule — collects most
of the win. On the real library, on the grammar above, it is worth **2.6x**
at `N = 64`: 16.60 s becomes 6.27 s.
So the cost that remains after the 0.2 work is mostly **not** the FIRST-set
arithmetic: computing it in advance and handing GHC the answer is worth 1.2x.
It is the environment — searched once per occurrence of every non-terminal,
over entries whose size is dominated by the FIRST sets they carry. Those are
two independent levers that compose: 2.6x for how a reference is resolved
(taken below) and 4.9x for what the entries carry (taken above — and the
1.2x turned out to be the whole of the arithmetic, so what the entries carry
cost nothing to compute and everything to have). `PEG.Analysis` computes the
whole environment for the 64-rule grammar in 6 ms.
### Added
- `PEG.Analysis`: nullability, FIRST sets and well-formedness computed at
splice time. It was then the value-level twin of `PEG.TyLevel`, which was
the specification; it is now the only implementation, and what checks it is
the `typed-peg-analysis` test-suite.
- `pegRules` now reports left recursion, a nullable repetition and a duplicate
rule **from the splice**, naming the rule and, for left recursion, the chain
of head references that closes the cycle. A block is analysed open-world,
since `RCons` lets two blocks be combined, so an unknown name is treated as
opaque rather than reported; `Acyclic` was then the backstop, and is now
gone, so a cycle closing across two blocks is caught by nothing. Write the
grammar as one `pegGrammar` to close that gap.
- `PEG.QQ.Syntax`: the DSL's syntax tree and parser, split out of `PEG.QQ` so
that the analysis and the translation can both consume it.
- **`pegGrammar`**, a quasi-quoter for a whole grammar. In expression
position it produces the `Grammar` value; in declaration position it also
declares the environment and the signature, so that a grammar of `n` rules
is `n` lines and nothing else:
```haskell
[pegGrammar|
%name arith
%start expr
expr :: Exp <- t:term ts:(o:[+-] u:term)* { foldl addOp t ts }
...
|]
```
Because it owns the whole grammar it knows each rule's position, so it emits
`ntw` and the membership proof rather than `nt` and a search — **2.1x** on the
64-rule grammar above. It also knows that a name no rule defines is an
error rather than a reference to somewhere else, so it says so at the
splice.
A rule's result type is the one thing the grammar does not determine, which
is what the `:: T` annotations are for. They are claims, not assertions:
`Grammar` demands `Rules s env env`, so GHC checks each against what the
rule body actually returns. *(At the time this also meant GHC recomputed
the FIRST sets and so could not be lied to about them; the entry above is
what changed that.)*
`examples/Arith.hs` and `examples/Layout.hs` are written this way now and
declare no environment at all. `pegRules` is unchanged and still the way to
write a rule set that is only part of a grammar; `examples/Compat.hs` and
`examples/Patterns.hs` keep using it.
- `PEG.Syntax.NTW` and `ntw`: a non-terminal reference that carries its own
`Member` proof instead of having `KnownMember` search for it. The `Lookup`
equality is kept, so `ty` and `a` still come from the environment and a
proof that names the wrong rule does not compile — this is not a weaker
claim than `NT`, only a cheaper one. Worth **2.6x** on a 64-rule grammar.
A splice knows each rule's position and can write the proof down; a
hand-written grammar has nothing to gain and should keep using `nt`.
- `bench-compile/`: a generator and a sweep script for the numbers above.
- A test-suite, `typed-peg-analysis`, that reads `examples/` and requires the
computed environment of each grammar to equal the one written there.
### Compile time of large grammars
Checking a grammar was **exponential in the size of its FIRST sets**. On a
chain of `n` mutually referring rules, GHC needed 0.7 s at `n = 8`, 12 s at
`n = 12`, and more than five minutes at `n = 15`; anything the size of a real
language front end never finished. The same grammars now check in
milliseconds-to-seconds and the curve is polynomial: `n = 12` takes 0.5 s,
`n = 30` 1.7 s, `n = 60` 14 s.
One limit is new rather than fixed: the union of two FIRST sets nests one
type-family reduction per element of the result, so a FIRST set of more than
about a hundred non-terminals now reports `Reduction stack overflow` instead
of being slow. `-freduction-depth=0` lifts it, and a union of two 128-element
sets then takes about 0.3 s.
### Fixed
- **`Union` and `ConsIfAbsent` were exponential.** `ConsIfAbsent x xs`
expanded to `If (Elem x xs) xs (x ': xs)`, naming `xs` three times. In
`Union (x ': xs) ys = ConsIfAbsent x (Union xs ys)` that `xs` is an
unreduced `Union`, so each step left GHC three copies of the pending
computation to reduce and each of those tripled again: `3^n` reductions for
a union of two `n`-element sets. Both families now dispatch on an
already-computed `Ordering` in a helper whose every right-hand side names
each argument — and in particular the recursive call — exactly once.
- **`Lookup` threaded the whole environment through its recursion** so that
the not-found case could list the available non-terminals. An environment
of `n` rules is `O(n^2)` type nodes, because every entry carries a FIRST
set, and there is one lookup per occurrence of every non-terminal. The
search now carries only the tail it has still to scan; the environment is
named once, in the branch that reports the error.
- **`Lookup` matched through `CmpSymbol` and a dispatch family**, two
type-family reductions per entry scanned. It now matches on a non-linear
pattern — the name appears twice in the clause — so GHC decides each entry
by syntactic equality and apartness, in one reduction. The trick is
`Data.Type.Map`'s, from `type-level-sets`. Worth 1.4x-1.6x on a large
grammar, since the search runs once per occurrence of every non-terminal.
- **`nt` and `PExp`'s `NT` made GHC search the environment several times per
occurrence.** Their constraint was
`KnownMember n env (TyOf (Lookup n env)) (ResOf (Lookup n env))`, and
resolving `KnownMember` walks `env` one instance at a time, re-normalising
every index at each step. Both now name the entry once, through a
`Lookup n env ~ 'EnvEntry ty a` equality, and pass the resulting rigid
types to `KnownMember`.
### Changed
- **Breaking. A FIRST set is now written in alphabetical order**, and a
declared environment that lists one in any other order is a type error
naming the first position that disagrees. Sortedness is what makes a set
have a single spelling, which is what lets `Union` be one merge pass.
Migration is mechanical: sort each `'[...]` in your `Env`, so
`'["term", "factor", "number"]` becomes `'["factor", "number", "term"]`.
- **Breaking.** `Member` and `KnownMember` lose their `Ty` index:
`Member s env a` and `KnownMember s env a`. Every index of a class is
carried along and re-normalised at each step of the instance chain that
walks the environment, and a `Ty` carries a FIRST set — so an index for it
made each step cost `O(|env|)`. Nothing needed it; `Here` binds the
entry's `ty` existentially, which is enough to pull a rule out of a rule
table.
- `PEG.Syntax` exports `NTGo`, the `Ty` of a reference to a non-terminal
whose own `Ty` is already known. `NTTy n env` is now defined as
`NTGo n (TyOf (Lookup n env))` and keeps working in signatures.
`SeqTy` and `ChoiceTy` are deliberately **unchanged**. They duplicate their
operands across their right-hand sides too, but measurement says that costs
nothing here, and writing them as type synonyms is what makes them reduce to a
`'MkTy` head while their operands are still abstract — which is what lets a
polymorphic combinator such as `lexeme` compose without its caller having to
get the nesting of `SeqTy` exactly right.
## 0.2.0.0 — 2026-09-04
This release is **not source-compatible with 0.1.0.0**: `PExp`, `Rules`,
`Grammar`, `Result` and `PState` all gain a leading stream type parameter, and
a rule whose result is a character-class repetition changes result type. See
*Changed* below for the migration.
### Added — parsing any stream, not just `String`
`PEG.Stream` introduces a `Stream` class, with instances for `String`, strict
and lazy `Data.Text.Text`, and strict and lazy `Data.ByteString.ByteString`.
A grammar written once runs over any of them.
The genericity reaches the *results*, not just the input: a character-class
repetition such as `cs:[a-zA-Z0-9_]+` now produces a **chunk of the input
stream** — a real `Text` slice — instead of unpacking into a `[Char]`. Two new
`PExp` constructors, `Span` and `Span1`, carry this; the quasi-quoter emits
them for `[...]*`, `[...]+`, `'c'*`, `'c'+`, `.*` and `.+`.
`ByteString` is read as Latin-1, exactly as `Data.ByteString.Char8` does: fast,
correct for ASCII, and wrong for multi-byte UTF-8. `PEG.Stream`'s Haddock
states this as a law rather than a footnote.
Only `unconsS` has no default, so a user instance is one method. It returns an
unboxed sum rather than `Maybe (Char, s)` on purpose — behind a class
dictionary the boxed version would allocate a `Just` and a pair for every
character, losing the zero-allocation terminal path.
### Changed
- **Breaking.** `PExp`, `Rules` and `Grammar` take a leading stream parameter:
`PExp s env ty a`, `Rules s env defs`, `Grammar s env ty a`. `Result` and
`PState` likewise: `Result s a`, `PState s`.
- **Breaking.** A rule whose result is a character-class repetition now has
result type `s`, so its `Env` synonym takes a parameter. Semantic actions
that fed such a result to something expecting a `String` need
`chunkToString`: `number <- ds:[0-9]+ { Lit (read (chunkToString ds)) }`.
- **Breaking.** The symbol variable in `PExp`'s `NT`, in `nt`, and in
`Rules`'s `RCons` is now named `n`; `s` is the stream. `nt @"name"` is
unaffected — the name is deliberately still the first quantified variable.
- `PEG.Semantics.Simple`'s unrelated `Stream` class is renamed
`SimpleStream`, to leave the name to `PEG.Stream`.
- `PState`'s input field is now strict.
A `Grammar` is monomorphic in its stream. Reusing one across stream types
needs a `forall s. Stream s => Grammar s env ty a` signature, which turns the
value into a function of a dictionary and so stops the compiled parser being
shared between calls. Give parsers a monomorphic top-level binding where that
matters; `PEG.Parse`'s Haddock spells this out.
### Performance
Measured on the benchmark suite, bytes allocated per input byte, against the
previous release of the evaluator:
| grammar | before (String) | String | Text | ByteString | megaparsec |
|---|---|---|---|---|---|
| arith | 990 | 943 | 1127 | 969 | 1239 |
| csv | 834 | 787 | 951 | 805 | 1035 |
| json | 459 | 404 | 583 | 452 | 782 |
| nested | 265 | 312 | 481 | 336 | 1283 |
| quoted `(!'"' .)*` | 162 | 209 | 320 | 250 | 128 |
`ByteString` is the cheapest column on five of the seven grammars and beats
megaparsec on six. `Text` costs more than `String` throughout — the same
result the earlier study found for megaparsec, and worth knowing before
reaching for it.
Two grammars regressed on `String` (`nested` +18%, the `(!'"' .)*` idiom
+29%). Both are dominated by single-character steps rather than bulk scans,
where `unconsS` is one indirect call that the previous direct cons-cell match
did not need. The five grammars that do any bulk scanning improved by 5-12%.
The `idents` and `quoted [^"]*` groups are not in the table because their
grammars changed: `ident` moved from `c:[a-zA-Z_] cs:[a-zA-Z0-9_]*` to
`&[a-zA-Z_] cs:[a-zA-Z0-9_]+` so that it returns a chunk rather than consing a
character onto one, and `Bench.Mega`'s `identP` moved to `takeWhile1P` to keep
the comparison like-for-like. On the new grammars typed-peg allocates 100
B/byte over `String` and 84 over `ByteString`, against megaparsec's 179.
### Performance
The evaluator was rewritten twice: once around a compilation step, once around
an unboxed step result. On the benchmark suite in `bench/` (see `cabal bench`),
measured against megaparsec 9.8 in the same run, typed-peg went from taking
2.1x-58x the time megaparsec takes to taking 0.95x-1.17x of it — and it now
allocates less than megaparsec on six of the seven grammars. The one grammar
where it still loses is the `(!'"' .)*` idiom, which scans every character
twice by construction; written as `[^"]*` it costs 1.23x-1.35x.
- A compiled step returns an unboxed sum, `(# (# #) | (# a, PState #) #)`,
rather than `Maybe (a, PState)`. The two are isomorphic, but the unboxed
sum travels in registers, so a step that succeeds no longer allocates a
`Just` *and* a pair on top of the new state, and a step that fails
allocates nothing at all. This makes `Seq` and `Map` — the two
constructors the quasi-quoter emits for every grammar item — completely
allocation-free, and cuts total allocation by a further 9–53%.
- String literals match in a single loop that builds one `PState`, rather
than one per character, whenever the grammar does not use layout.
- `PEG.Parse` now *compiles* a `Grammar` into a closure once, instead of
walking the `PExp` GADT and the rule list on every step. Resolving a
non-terminal is now one indirect call rather than a linear scan of the rule
environment. `parseWith opts g` is written so that partially applying it
yields the compiled parser; bind it to a name to reuse it.
- Character classes compile to a single `Sat` node holding a `PEG.CharSet`
(a 256-bit bitmap), instead of expanding into a chain of ordered choices.
Matching one character of `[a-zA-Z0-9_]` used to cost 63 parser steps.
- String literals compile to a single `Str` node instead of a chain of
`Seq`/`Map`/`Term`.
- The parser no longer builds a `[(Char, Int)]` copy of the input; the column
of the current character is carried in the state and updated incrementally.
- Terminals take a fast path that skips all interval arithmetic when the
ambient column relation is total (`anyR`), which is the case for every
grammar that does not use layout. The new `rdTotal` field of `RelD` records
this.
- `parse` returns the unconsumed suffix in `O(1)` instead of recomputing it
with two `length` calls and a `drop`.
- `Star` no longer builds a chain of selector thunks.
### Added
- Negated character classes in the quasi-quoter: `[^"]` matches any character
other than a quote. Previously the only way to write this was
`(!'"' .)`, which scans every character twice — once for the lookahead and
once for the dot. On the `quoted` benchmark the class form halves the
allocation.
- `PEG.CharSet`: compact character sets, re-exported from `PEG`.
- `PEG.Syntax.Sat` / `PEG.Syntax.Str` constructors, and the `sat`,
`charClass` and `notCharClass` smart constructors.
- `PEG.Parse.compileGrammar` and the `Step` and `Res` types, for callers that
want the compiled parser directly.
- `PEG.Indent.rdTotal`.
- A criterion benchmark suite comparing typed-peg with megaparsec
(`bench/`, run with `cabal bench`).
- `examples/Compat.hs`: a differential battery used to check that the
optimisation work did not change any observable behaviour.
### Changed
- **Breaking.** `PState` now holds the remaining input as a `String` plus the
current column and offset (`stInput`, `stCol`, `stOff`), rather than a
precomputed `[(Char, Int)]`. `PEG.Parse.Input`, `PEG.Parse.columns` and
`PEG.Parse.eval` are gone; use `compileGrammar` instead of `eval`.
- **Breaking.** `RelD` has a new `rdTotal` field.
- **Breaking.** `PEG.Parse.Step` now returns the unboxed sum `Res a` instead
of `Maybe (a, PState)`. This only affects code that called
`compileGrammar` directly; `parse` and `parseWith` are unchanged.
- **Breaking.** In a quasi-quoted grammar, a `^` immediately after `[` now
negates the class instead of standing for itself; write `[\^]` for a class
containing a caret.
- The `template-haskell` upper bound now admits the version shipped with
GHC 9.10 (`< 2.24`).
## 0.1.0.0 — 2026-08-28
### Added
- Initial release.
- Type-safe PEG parser combinators with compile-time left-recursion detection
via type families (`PEG.Grammar`).
- FIRST-set and nullability information tracked at the type level (`PEG.Type`,
`PEG.TyLevel`).
- Indentation-sensitive parsing primitives (`PEG.Indent`).
- Quasi-quoter `pegRules` for writing grammars in a concrete DSL (`PEG.QQ`).
- Simple semantics interpreter (`PEG.Semantics.Simple`).