I discuss how parsers can be used to create functions of time (f(t)) using FP components…
I think of a pipeline of parsers as a string of beads.
Each bead is a function, maybe programmed in an FP language.
People have generalized the term AST — abstract syntax tree — to mean the result of a parse (usually a tree data structure, remembering that trees can be serialized into streams of tokens).
I subdivide parsing into two parts
I use the term AST for (1). Abstract Syntax Tree.
I use the term CST for (2). Concrete Syntax Tree.
Likewise, a program can be subdivided into two parts:
History is but a function of time — f(t).
In general, history is not reversible (as far as we know).
But, pure FP (functional programming) expunges f(t) [1]from its notation, to appease its notation (and to allow transformations that would be impossible if f(t) were allowed (that's where the onus to expunge side-effects comes from)).
How, then, could history be expressed in FP???
Parsers walk input streams (aka trees) driven by reality. Parsers don't process abstractions (ASTs). Parsers walk realities (CSTs).
History is encoded in the backtrace of how a parser walked the CST. The actual input causes the parser to walk a (crooked?) path through the AST. The AST does not change, but the history of the walk is different with every different input.
Each step along the way can be expressed as an FP function.
Steps are FP, history is not FP[2].
Let us concoct a simple example:
function f(x) {
if (x == 5) {
printf ("5");
} else {
printf ("not 5");
}
}
What is the final output of the above function?
We can't know what the final output is without supplying a value for the parameter, x.
The function is like an AST — it expresses all possible outcomes.
When we supply a value for the parameter, x, then the function runs and produces one or the other outcome. The run is history. The run is like a CST. We can get a backtrace for the run. (A CST is like a backtrace).
Parsers — grammars in particular — give us a declarative way to talk about history.
Note that FP increasingly uses parser technology — pattern matching.
Pattern matching taken to the limit, is parsing.
Parsing deals with history and, hence, with f(t).
Note that a parsing engine is analogous to a PROLOG rule engine.
Programmers have used flags (mutable variables) for ages. We have discovered that flags cause accidental complexity and lack-of-debuggability.
Parsers are engines that subsume the use of flags. [Parsers give us a way to talk about flags in a declarative manner.]
Parsers are FP pattern matching taken to the limit.
FP uses relational engines and pattern matching.
FP could use relational engines and parsing engines.
[1] Side-effects are f(t). FP expunges side-effects. FP expunges time from its notation.
[2] FP does not allow f(t). f(t) is History. Hence, FP expunges History. History must be recorded using some other notation.