Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Design and Compilation Strategy
Design and Compilation Strategy
What this note covers
What this note covers
The survey lays out what's already there; this note lays out what we are building. The plan in one sentence: reuse the declarative DSL, but compile the rules to a local parser via instead of round-tripping through , and pair that with an Anton-style combinator core that all funnels into a single computable head.
Parse*
ParserCombinator
The note has six parts:
1
.The single head: one canonical wrapper that every combinator constructor produces, with for operator composition and a -style formatter.
ParserCombinator
SummaryBox
2
.Parse*
3
.Two-tier API: a declarative GrammarRules-compatible entry point that lowers to , and the bare combinator core for grammars that don't fit the declarative shape.
ParserCombinator
4
.Parser algebra: the small set of primitive combinators all higher-level constructs lower to.
5
.Compilation strategy: how a tree lowers to a typed first-order form and what makes of it.
ParserCombinator
6
.Worked targets: LaTeX math and TPTP - the two grammars that motivate the choice of primitives.
7
.Open questions: things deliberately left unresolved in v0.1.
Part 1 - The single ParserCombinator head
Part 1 - The single head
ParserCombinator
Every parser is a single computable object :
ParserCombinator[type,args,opts]
◼
type
Sequence
Choice
Many
Literal
◼
args
ParserCombinator
◼
The head is opaque to user code: you never write by hand. Instead you call one of the constructors (next section), each of which returns a of the appropriate type. The head exists for three reasons:
ParserCombinator[...]
Parse*
ParserCombinator
(1) Composition via UpValues. Because every parser is a , we can attach to that head and overload the WL operators that actually parse:
ParserCombinator
WL syntax | Lowers to | Combinator | |
p1|p2 | |||
p1~~p2 | |||
p.. | |||
p... | |||
Why these and not others:
◼
|
Alternatives
◼
~~
ParserCombinator
"foo"~~"bar"
~~
◼
..
...
◼
~
a~f~b
f[a,b]
(2) SubValue: call a parser as a function. Every also carries a SubValues rule: evaluates to . So a constructed parser is directly callable, the same way a or an is. For an uncompiled parser the SubValue routes to the interpreter; for one passed through it routes to the cached compiled function.
ParserCombinator
pc[input]
Parse[pc,input]
CompiledCodeFunction
InterpolatingFunction
ParserCompile
A sample composition:
In[1]:=
(*matchoneormoredigits,followedoptionallybyadot-and-fraction*)number=
[DigitCharacter]..~~Optional
["."]~~
[DigitCharacter]...;
 | ParseCharacter |
| ParseLiteral |
| ParseCharacter |
UpValues mean each operator picks the right combinator without the user ever typing .
ParserCombinator[...]
(3) A canonical, inspectable representation. Every parser is a tree of nodes, so the compiler, the pretty-printer, and the diagnostic machinery all walk one expression shape. There is no separate "compiled form" data type at the user-visible level - adds a entry to the wrapper's options and otherwise leaves the tree alone. The presence of is the canonical "is this compiled?" marker; no separate flag is needed.
ParserCombinator
ParserCompile[p]
"Code"->CompiledCodeFunction[...]
"Code"
"Compiled"->True
(4) A nice summary box. carries a formatter modelled on / / . Always-visible: combinator type, arity, compile status. Expanded: the structural sketch, the option association, an icon hinting at the combinator family (a sequence of glyphs for , a fork for , a star for , a brace for , etc.). Concretely:
ParserCombinator
BoxForm`ArrangeSummaryBox
FiniteFieldElement
PAdicNumber
Quantity
Sequence
Choice
Many
Between
ParserCombinator
── Type: Sequence
── Arity: 3
── Compiled: False
── Structure: Literal["the weather in "] ~~ Capture["city", Restricted["City", "USA"]] ~~ Literal["."]
── Options: <|"Memoize" -> False, "TrackPosition" -> True|>
── Type: Sequence
── Arity: 3
── Compiled: False
── Structure: Literal["the weather in "] ~~ Capture["city", Restricted["City", "USA"]] ~~ Literal["."]
── Options: <|"Memoize" -> False, "TrackPosition" -> True|>
The summary box is the same convention used by every modern WL computable object - users get a one-line glance plus an opener, not an opaque blob.
Part 2 - Parse* constructors
Part 2 - constructors
Parse*
Following the naming convention, every constructor is a function with a prefix that returns a . The full table (v0.1 plan):
Parse*
ParserCombinator
Constructor | Returns ParserCombinator[...] | What it matches | |
ParseLiteral[s] | Literal | the exact string / token s | |
ParseCharacter[pat] | Character | a single character matching pat [a,b] Alternatives | |
ParseToken[type] | Token | a tagged Token[type,_,_] | |
ParseSucceed[val] | Succeed | always succeed with val | |
ParseFail[msg] | Fail | always fail with msg | |
ParseSequence[p1,p2,...] | Sequence | each pi | |
ParseChoice[p1,p2,...] | Choice | first pi | |
ParseMany[p] | Many | zero or more p | |
ParseSome[p] | Some | one or more p | |
ParseOptional[p] | Optional | zero or one p | |
ParseBetween[open,p,close] | Between | open p close p | |
ParseSepBy[p,sep] | SepBy | zero or more p sep | |
ParseSepBy1[p,sep] | SepBy1 | one or more p sep | |
ParseChainLeft[p,op,init] | ChainLeft | left-associative operator chain | |
ParseChainRight[p,op,init] | ChainRight | right-associative operator chain | |
ParseLookahead[p] | Lookahead | succeed iff p | |
ParseNotFollowedBy[p] | NotFollowedBy | succeed iff p | |
ParseTry[p] | Try | backtrack on failure even after consuming | |
ParseAction[p,f] | Action | apply f p | |
ParseCapture[name,p] | Capture | tag p name GrammarRules | |
ParseRecursive[name,body] | Recursive | a named recursive parser body |
The constructors are just builders - they do not run the parser; they only produce the value. Running is (interpretive) or (compiled).
ParserCombinator
Parse[parser,input]
ParserCompile[parser][input]
Worked sample composition
Worked sample composition
The same number-parser, three equivalent ways:
In[2]:=
(*operatorform-shortest,idiomaticfornewcode*)number=
[DigitCharacter]..~~Optional
["."]~~
[DigitCharacter]...;(*explicitconstructorform-whattheUpValueslowerto*)number=
[DigitCharacter],
["."],
[DigitCharacter];(*mixed-dropintotheoperatorformwhereverreadable,fallbacktoexplicitcallswhenithelps*)number=
[DigitCharacter]..,
["."]~~
[DigitCharacter]...;
| ParseCharacter |
| ParseLiteral |
| ParseCharacter |
 | ParseSequence |
| ParseSome |
| ParseCharacter |
| ParseOptional |
| ParseSequence |
| ParseLiteral |
| ParseMany |
| ParseCharacter |
| ParseSequence |
| ParseCharacter |
| ParseOptional |
| ParseLiteral |
| ParseCharacter |
All three return the same expression. Composability is a single-axis story - whatever you write, it lowers into one canonical tree.
ParserCombinator
Part 3 - Two-tier API
Part 3 - Two-tier API
Tier 1 - the declarative path (GrammarRules-compatible)
Tier 1 - the declarative path (-compatible)
GrammarRules
The built-in takes a list of slot-templates paired with actions and returns an inert symbolic form. Today the only way to evaluate a object is to deploy it as a cloud object and call against the deployment; the declaration itself is just data:
GrammarRules
GrammarApply
In[3]:=
GrammarRules[{"the weather in <city:Restricted[\"City\", \"USA\"]>"city,"convert <amount:Number> <from:Restricted[\"Currency\"]> to <to:Restricted[\"Currency\"]>"CurrencyConvert[Quantity[amount,from],to]}]
Out[3]=
GrammarRules[{the weather in <city:Restricted["City", "USA"]>city,convert <amount:Number> <from:Restricted["Currency"]> to <to:Restricted["Currency"]>CurrencyConvert[Quantity[amount,from],to]}]
WolframParser
In[4]:=
(*"just parse"-JIT-compilethegrammar,cacheit,parsetheinput*)
[grammar,"the weather in NYC"](*explicitcompile-getbackaparserholdingthecompiledcode*)parser=
[grammar];parser["the weather in NYC"]
 | Parse |
| ParserCompile |
Out[4@1]=
Parse[grammar,the weather in NYC]
Out[4@2]=
ParserCompile[grammar][the weather in NYC]
The compile step is the local analogue of : it materialises a callable parser. The cloud path returns a ; the local path returns a with a entry added to its options. The presence of is what marks the parser as compiled - both and the SubValues route compiled parsers through that function.
CloudObject
ParserCombinator
"Code"->CompiledCodeFunction[...]
"Code"
Parse
The slot vocabulary is identical to the built-in one - , , - and is honoured. The differences are confined to where compilation happens, not what a grammar means.
<name>
<name:Type>
<name:Restricted[Type,constraints]>
Tier 2 - the combinator core
Tier 2 - the combinator core
For grammars where the slot-template DSL is too coarse - LaTeX environments, TPTP formula bodies, expression grammars with operator precedence, anything that needs backtracking control or lookahead - the constructors (with optional operator overloads) are the entry point. The example in Part 2 is the shape.
Parse*
How the tiers connect
How the tiers connect
GrammarRules[...]
ParserCombinator
GrammarRules[{"the weather in <city:Restricted[\"City\"]>" -> city}]
│ lower
▼
ParserCombinator[Action,
{ParserCombinator[Sequence, {
ParserCombinator[Literal, "the weather in ", <||>],
ParserCombinator[Capture, {"city", Interpreter["City"]}, <||>]
}, <||>],
city &},
<||>]
│ ParserCompile
▼
ParserCombinator[Action, {...}, <|"Code" -> CompiledCodeFunction[...]|>]
│ lower
▼
ParserCombinator[Action,
{ParserCombinator[Sequence, {
ParserCombinator[Literal, "the weather in ", <||>],
ParserCombinator[Capture, {"city", Interpreter["City"]}, <||>]
}, <||>],
city &},
<||>]
│ ParserCompile
▼
ParserCombinator[Action, {...}, <|"Code" -> CompiledCodeFunction[...]|>]
Adding to either tier benefits the other: a new combinator becomes available as a lowering target for new slot syntaxes; a new slot syntax just extends the lowering.
Part 4 - The parser algebra
Part 4 - The parser algebra
Concretely, a parser is a function of two arguments - the input and a starting position - that returns one of:
The combinators are defined by structural equations:
ParseSequence[p1, p2] (in, pos)
= let r1 = p1 (in, pos);
if r1 is ParseFailure, return r1;
let (v1, pos1) = r1.value;
let r2 = p2 (in, pos1);
if r2 is ParseFailure, return r2;
let (v2, pos2) = r2.value;
return ParseSuccess[{v1, v2}, pos2].
ParseChoice[p1, p2] (in, pos)
= let r1 = p1 (in, pos);
if r1 is ParseSuccess, return r1;
let r2 = p2 (in, pos);
if r2 is ParseSuccess, return r2;
return ParseFailure[max(r1.pos, r2.pos), r1.expected ++ r2.expected].
ParseMany[p] (in, pos)
= let acc = {}, cur = pos;
loop:
let r = p (in, cur);
if r is ParseFailure, return ParseSuccess[acc, cur];
let (v, next) = r.value;
acc := acc ++ {v}, cur := next;
goto loop.
ParseLookahead[p] (in, pos)
= let r = p (in, pos);
if r is ParseSuccess, return ParseSuccess[Null, pos]; (* position unchanged *)
return r.
ParseNotFollowedBy[p] (in, pos)
= let r = p (in, pos);
if r is ParseSuccess, return ParseFailure[pos, "not " ++ name(p)];
return ParseSuccess[Null, pos].
= let r1 = p1 (in, pos);
if r1 is ParseFailure, return r1;
let (v1, pos1) = r1.value;
let r2 = p2 (in, pos1);
if r2 is ParseFailure, return r2;
let (v2, pos2) = r2.value;
return ParseSuccess[{v1, v2}, pos2].
ParseChoice[p1, p2] (in, pos)
= let r1 = p1 (in, pos);
if r1 is ParseSuccess, return r1;
let r2 = p2 (in, pos);
if r2 is ParseSuccess, return r2;
return ParseFailure[max(r1.pos, r2.pos), r1.expected ++ r2.expected].
ParseMany[p] (in, pos)
= let acc = {}, cur = pos;
loop:
let r = p (in, cur);
if r is ParseFailure, return ParseSuccess[acc, cur];
let (v, next) = r.value;
acc := acc ++ {v}, cur := next;
goto loop.
ParseLookahead[p] (in, pos)
= let r = p (in, pos);
if r is ParseSuccess, return ParseSuccess[Null, pos]; (* position unchanged *)
return r.
ParseNotFollowedBy[p] (in, pos)
= let r = p (in, pos);
if r is ParseSuccess, return ParseFailure[pos, "not " ++ name(p)];
return ParseSuccess[Null, pos].
Two design choices worth flagging
Two design choices worth flagging
Part 5 - The compilation strategy
Part 5 - The compilation strategy
Why FunctionCompile is the right hammer
Why FunctionCompile is the right hammer
◼
No C dependency. The compiler is part of the kernel. A user installing the paclet does not also install a toolchain.
The lowering pipeline
The lowering pipeline
ParserCombinator[...] expression (high-level, untyped, structural)
│ Phase 1: normalisation
▼
canonical ParserCombinator tree (every node is a primitive combinator)
│ Phase 2: typing
▼
typed ParserCombinator tree (each node tagged with its result type)
│ Phase 3: result-encoding choice
▼
result-encoded tree (results unified to one Typed[...] tag)
│ Phase 4: codegen
▼
FunctionCompile-ready function spec (a function (in, pos) -> Typed[...])
│ Phase 5: FunctionCompile
▼
ParserCombinator with "Code" -> CompiledCodeFunction in its options
│ Phase 1: normalisation
▼
canonical ParserCombinator tree (every node is a primitive combinator)
│ Phase 2: typing
▼
typed ParserCombinator tree (each node tagged with its result type)
│ Phase 3: result-encoding choice
▼
result-encoded tree (results unified to one Typed[...] tag)
│ Phase 4: codegen
▼
FunctionCompile-ready function spec (a function (in, pos) -> Typed[...])
│ Phase 5: FunctionCompile
▼
ParserCombinator with "Code" -> CompiledCodeFunction in its options
A few decisions in detail:
What the compile does not buy us
What the compile does not buy us
Honest accounting: FunctionCompile is not a magic 100× speedup for parsing.
◼
String access still bounces through UTF-8 decoding for any non-ASCII grammar. This is unavoidable without a separate tokenisation step.
◼
Heap-allocating result construction (building an output AST) does not compile to anything faster than the interpreted path; we minimise it by lowering "structural" results to packed forms where possible.
A realistic expectation is 3-10× over the interpreted path on lexer-heavy grammars (LaTeX math, JSON, TPTP), and a smaller factor on grammars dominated by AST construction.
Part 6 - Worked targets
Part 6 - Worked targets
The choice of primitives above is motivated by two concrete targets. This section walks through how each maps onto the algebra, with enough detail to validate the design.
Target A - LaTeX math
Target A - LaTeX math
math = expr;
expr = ParseAction[
term ~~ (ParseChoice[ParseLiteral["+"], ParseLiteral["-"]] ~~ term)...,
Function[{first, rest}, FoldOperator[first, rest]]
];
term = ParseAction[
factor ~~ (ParseChoice[ParseLiteral["*"], ParseLiteral["/"]] ~~ factor)...,
FoldOperator
];
factor = group | command | atom;
group = ParseBetween[ParseLiteral["{"], expr, ParseLiteral["}"]];
command = ParseAction[
ParseLiteral["\\"] ~~ ParseSome[ParseCharacter[LetterCharacter]] ~~
Optional[bracketedArg] ~~ ParseMany[bracedArg],
buildCommand
];
bracedArg = ParseBetween[ParseLiteral["{"], expr, ParseLiteral["}"]];
bracketedArg = ParseBetween[ParseLiteral["["], expr, ParseLiteral["]"]];
atom = number | identifier | bigOperator;
bigOperator = ParseAction[
(ParseLiteral["\\sum"] | ParseLiteral["\\int"] | ParseLiteral["\\prod"]) ~~
Optional[ParseLiteral["_"] ~~ group] ~~ Optional[ParseLiteral["^"] ~~ group],
buildBigOperator
];
expr = ParseAction[
term ~~ (ParseChoice[ParseLiteral["+"], ParseLiteral["-"]] ~~ term)...,
Function[{first, rest}, FoldOperator[first, rest]]
];
term = ParseAction[
factor ~~ (ParseChoice[ParseLiteral["*"], ParseLiteral["/"]] ~~ factor)...,
FoldOperator
];
factor = group | command | atom;
group = ParseBetween[ParseLiteral["{"], expr, ParseLiteral["}"]];
command = ParseAction[
ParseLiteral["\\"] ~~ ParseSome[ParseCharacter[LetterCharacter]] ~~
Optional[bracketedArg] ~~ ParseMany[bracedArg],
buildCommand
];
bracedArg = ParseBetween[ParseLiteral["{"], expr, ParseLiteral["}"]];
bracketedArg = ParseBetween[ParseLiteral["["], expr, ParseLiteral["]"]];
atom = number | identifier | bigOperator;
bigOperator = ParseAction[
(ParseLiteral["\\sum"] | ParseLiteral["\\int"] | ParseLiteral["\\prod"]) ~~
Optional[ParseLiteral["_"] ~~ group] ~~ Optional[ParseLiteral["^"] ~~ group],
buildBigOperator
];
What this grammar gets right that the current built-ins don't:
Target B - TPTP
Target B - TPTP
fof(commutativity_of_plus, axiom,
! [X, Y]: (plus(X, Y) = plus(Y, X))).
fof(some_property, conjecture,
? [X]: (greater(X, zero) & even(X))).
! [X, Y]: (plus(X, Y) = plus(Y, X))).
fof(some_property, conjecture,
? [X]: (greater(X, zero) & even(X))).
The grammar is BNF, publicly specified, and of moderate size (~100 productions for full TFF/THF). The combinators that matter:
A skeleton (non-evaluating prose - mutually recursive):
tptpFile = formula...;
formula = (ParseLiteral["fof"] | ParseLiteral["cnf"] | ParseLiteral["tff"] | ParseLiteral["thf"]) ~~
ParseBetween[ParseLiteral["("], formulaBody, ParseLiteral[")"]] ~~
ParseLiteral["."];
formulaBody = name ~~ ParseLiteral[","] ~~ role ~~ ParseLiteral[","] ~~ logicFormula;
logicFormula = quantified | binary | unit;
quantified = (ParseLiteral["!"] | ParseLiteral["?"]) ~~ varList ~~ ParseLiteral[":"] ~~ logicFormula;
binary = unit ~~ (ParseLiteral["&"] | ParseLiteral["|"] |
ParseLiteral["=>"] | ParseLiteral["<=>"]) ~~ logicFormula;
unit = atom | ParseBetween[ParseLiteral["("], logicFormula, ParseLiteral[")"]] | ParseLiteral["~"] ~~ unit;
atom = predicate ~~ Optional[ParseBetween[ParseLiteral["("], ParseSepBy[term, ParseLiteral[","]], ParseLiteral[")"]]];
term = variable | functionApp | constant;
formula = (ParseLiteral["fof"] | ParseLiteral["cnf"] | ParseLiteral["tff"] | ParseLiteral["thf"]) ~~
ParseBetween[ParseLiteral["("], formulaBody, ParseLiteral[")"]] ~~
ParseLiteral["."];
formulaBody = name ~~ ParseLiteral[","] ~~ role ~~ ParseLiteral[","] ~~ logicFormula;
logicFormula = quantified | binary | unit;
quantified = (ParseLiteral["!"] | ParseLiteral["?"]) ~~ varList ~~ ParseLiteral[":"] ~~ logicFormula;
binary = unit ~~ (ParseLiteral["&"] | ParseLiteral["|"] |
ParseLiteral["=>"] | ParseLiteral["<=>"]) ~~ logicFormula;
unit = atom | ParseBetween[ParseLiteral["("], logicFormula, ParseLiteral[")"]] | ParseLiteral["~"] ~~ unit;
atom = predicate ~~ Optional[ParseBetween[ParseLiteral["("], ParseSepBy[term, ParseLiteral[","]], ParseLiteral[")"]]];
term = variable | functionApp | constant;
The grammar is straightforward parser-combinator material; the productions above lower to FunctionCompile-able forms by the standard pipeline. The motivation for including TPTP as a target is dual:
1
.It validates the scale of the grammar - if the combinator algebra cannot express a 100-production grammar cleanly, the algebra is wrong.
2
.It validates the integration story - the parser returns a structured AST that can be transformed (skolemisation, clausification) by other WL code, which is the use case that drives a lot of automated-reasoning work in the Wolfram ecosystem.
What the targets imply about the algebra
What the targets imply about the algebra
Part 7 - Open questions
Part 7 - Open questions
A list of things explicitly not decided in v0.1:
2
.Streaming input. The current design assumes the input is in memory (string or list). Streaming (parse-while-reading) is an open question - relevant for large TPTP corpora and for editor integration.
3
.Error recovery. A parse failure currently aborts the whole parse. Some grammars (editors, IDE tools) want to continue past a syntax error and collect multiple errors. This is a separate research problem (panic-mode recovery, FOLLOW-set recovery) and is deferred.
Each of these will be answered by implementation experience against the targets above. The job of the v0.1 release is to ship the survey and this design, get the structure into the working directory, and start filling in the combinator primitives one at a time.
What ships in v0.1
What ships in v0.1
◼
A placeholder kernel.
What lands next (v0.2):
The PEG-VM backend
The PEG-VM backend
The consequences are decisive:
◼
It is fast - 1-2 orders of magnitude over the interpreter (≈55× on LaTeX, ≈500× on TPTP in informal benchmarks), because the recogniser is a tight native integer loop.
Still open: packrat memoisation (the VM has no memo table yet), richer failure diagnostics for the PEG-VM, and a non-ASCII class table.