Derivatives of Regular Expressions (2007)
lambda-the-ultimate.org
lambda-the-ultimate.org
There's a pretty variant of this idea introduced in 1995 by Valentin Antimirov called partial derivatives of regular expressions. His idea was to replace the single derivative with a set of partial derivatives that add up to the whole derivative. This simplifies the derivative algorithm quite a bit, and makes it possible to write amazingly concise and efficient regular expression matchers.
E.g., here's an implementation of a regular expression compiler that uses Antimirov derivatives to take a regexp and build a table-driven matcher in about 50 lines of code:
http://semantic-domain.blogspot.com/2013/11/antimirov-deriva...
Here's something like your code in Python: https://github.com/darius/regexercise_solutions/blob/master/... and transformed into Thompson's algorithm: https://github.com/darius/regexercise_solutions/blob/master/...
(I've never read Antimirov's paper past the first page or two; I wrote these things while digging into Thompson.)
https://news.ycombinator.com/item?id=18434228
I don't know what an Antimirov derivative is, will check it out ... Thanks for the links to code!
FWIW I drafted a lot of variations while messing with this: https://github.com/darius/sketchbook/tree/master/regex (some of this code is incorrect) and https://github.com/darius/sketchbook/tree/master/lex.
http://maveric.uwaterloo.ca/reports/1964_JACM_Brzozowski.pdf
http://www.oilshell.org/archive/Thompson-1968.pdf
One thing that I just learned that is SUPER WEIRD is that Thompson's paper contains the word "derivative" but it doesn't contain the words NFA, DFA, or even "state" !!!
First paragraph:
In the terms of Brzozowski [1], this algorithm con- tinually takes the left derivative of the given regular expression with respect to the text to be searched.
From: https://research.swtch.com/yaccalive
Thompson learned regular expressions from Brzozowski himself while both were at Berkeley, and he credits the method in the 1968 paper. The now-standard framing of Thompson's paper as an NFA construction and the addition of caching states to produce a DFA were both introduced later, by Aho and Ullman in their various textbooks. Like many primary sources, the original is different from the textbook presentations of it. (I myself am also guilty of this particular misrepresentation.)
However, figure 5 in Thompson's paper is CLEARLY an NFA for the regex a(b|c)d.
What's the connection between derivatives and NFAs? I don't understand why Thompson says his method is derivative-based and not NFA-based.
(The 2007 "Re-examined" paper linked here comments upon the Thompson line in section 6. They qualify Thompson's statement a bit, but I don't understand it fully. )
(This came up on lobste.rs after a discussion of Thompson's construction: https://lobste.rs/s/fq8uil/aho_corasick#c_4xkm7z)
Consider the regex A: Aa | ϵ, where ϵ denotes the empty string. What strings does it generate?
To solve, rewrite it as A = Aa + ϵ, then find its Taylor series and you're done:
A = ϵ / (ϵ - a) = ϵ + a + aa + aaa + ...
Edit: I meant "A: Aa | ε" instead of "A"
Huh? This is the exactly what I also just said, in response to the different claim you made above, which was that the production is merely "A" rather that "A: Aa" or "A: ε". If you're claiming they are somehow equal (which they clearly are not... one is a symbol and the other is a rule mapping that symbol to a sentential form) then I'm confused how you think A and a* were any less equal to begin with...
A-Aa=e
A(1-a)=e
A=e/(1-a) not e/(e-a)
As an aside, why do I think of regexps as a kind of "baby" programming language? Because:
- They can be converted to NFAs or DFAs. These NFAs and DFAs resemble assembly languages. The "assembly language" for NFA is actually quite exotic. Reminds me of compilation.
- NFAs can be understood as a kind of Virtual Machine. DFAs are like a subset of a physical machine.
- Just In Time compilation was first applied to regexps before anything else. This was done by Ken Thompson.
- The interpreter->compiler algorithm in RPython (the program that is used to produce PyPy) works quite well on regexps. This essentially automates the work that Ken Thompson did.
It seems to: http://matt.might.net/articles/parsing-with-derivatives/
I was actually thinking of differentiating whole programs. But still interesting.
> [...] We present a program transformation taking programs to their derivatives, which is fully static and automatic, supports first-class functions, and produces derivatives amenable to standard optimization.
The programming language follows a context-free grammar (CFG), which has been written in Backus-Naur Form (BNF). It is technically nonsensical to say "the programming language is BNF". It's like if I were to say "English is a Roman language" because we happen to use the Roman letters for our orthography. Just a technical nitpick.
> BNF is a more expressive language than regexp
The context-free languages are more expressive than the regular languages. BNF is a notation for writing a context-free grammar, and regular expressions are a notation for writing regular languages. (Again, a nitpick of terminology.)
One of the projects for the class I mentioned in another comment was actually implementing a stack-based virtual machine for regular expressions!
That discussion covers some of the same ground as the Taylor series idea elsewhere in thus discussion. It doesn't get as far as inventing the zipper concept.
They are state machines that can be in a lot of states at once; that's all. There is a debasement of the term NFA, popularized by Friedl, that "NFA" means "any thingy that implements regex that isn't a DFA". This isn't true and should not be promulgated.
I think you're being pedantic.
In this case, instead of the distinction between "virtual" and "physical" we have, considerably less pretentiously, an "state id" vs a "set of state ids" (in case of actual NFA implementation, said set might well be represented by a bit-vector whether a general purpose register or a SIMD register).
Making tortured analogies to JVMs and virtual machines doesn't actually help explain anything about what's going on. It certainly fails to provide the insight that you might get from comparing the whole "id vs set-of-ids" (one can instantly intuit the risk of an exponential blowout in NFA->DFA conversion, which does in fact exist).
An NFA implementation can be "virtual" in the sense of "virtual memory" being virtual. It is a pretense of a practically unbounded set of states while really being bounded like any other practical implementation. It grows on demand and can handle many practical inputs while possibly hitting its implementation limits on a worst-case input.
My whole comment was about tenuous but interesting analogies, and whether they can lead to somewhere interesting.
It's not a dreadful way of implementing regex as it can do things a straightforward bitset NFA implementation can't.
To be fair, I think your original post does stand, but I guess I am a bit pedantic about the terminology after spending a little bit of time on regex implementation.
In fact, a number of strategies in regex implementation turned out to generalize to broader areas. The bitwise automata are helpful elsewhere, as are many of the strategies one might use to make them fast. The 4 Russians technique ( https://en.wikipedia.org/wiki/Method_of_Four_Russians ) has also cropped up all over the place.
Citation for this? I'd be surprised if Thompson was first. Runtime optimization was long the domain of Lisp programmers. Blurring the distinction between compile-time and run-time is one of PG's things that "made Lisp different".
https://eli.thegreenplace.net/2013/11/05/how-to-jit-an-intro... references a paper by Aycock, which says McCarthy was first, in his original Lisp paper, nearly a decade before Thompson.
I'm not sure about implementing per se, but you can extend some notion of differentiation to richer programming languages: https://www.sciencedirect.com/science/article/pii/S030439750...
The differential of a term does give you some information about how a term behaves under reduction, so I guess the answer is "maybe" - sounds like a fun project to work on. :)
More generally, there are models of linear logic built on a notion of differentiation (mentioned in the same paper as above), which might translate to a compilation of linear lambda calculus/classical processes/pi calculus/etc.
The Prolog version is pretty much just an encoding of the rules. This is an implementation of a two-symbol alphabet {01} (without "compaction" IIRC):
% Brzozowski's Derivatives of Regular Expressions
:- use_module(library(ordsets)).
:- use_module(library(tabling)).
dre(_, [], []).
dre(_, [""], []).
dre(0, ["1"], []).
dre(0, ["0"], [""]).
dre(1, ["0"], []).
dre(1, ["1"], [""]).
dre(C, kstar(R), cons(Rd, R)) :- dre(C, R, Rd).
dre(C, not_(R), not_(Rd) ) :- dre(C, R, Rd).
dre(C, and(R, S), and(Rd, Sd)) :- dre(C, R, Rd), dre(C, S, Sd).
dre(C, or(R, S), or(Rd, Sd)) :- dre(C, R, Rd), dre(C, S, Sd).
dre(C, cons(R, S), cons(Rd, S) ) :- nully(R, [] ), dre(C, R, Rd).
dre(C, cons(R, S), or(cons(Rd, S), Sd)) :- nully(R, [""]), dre(C, R, Rd), dre(C, S, Sd).
nully([], []).
nully([""], [""]).
nully([_], []).
nully(kstar(_), [""]).
nully(not_(R), [""]) :- nully(R, []).
nully(not_(R), []) :- nully(R, [""]).
nully( and(R, S), N) :- nully(R, Rn), nully(S, Sn), ord_intersect(Rn, Sn, N).
nully(cons(R, S), N) :- nully(R, Rn), nully(S, Sn), ord_intersect(Rn, Sn, N).
nully( or(R, S), N) :- nully(R, Rn), nully(S, Sn), ord_union(Rn, Sn, N).
Actually, now that I think about it, the entire class was strangely centered around taking derivatives of regular expressions…
The paper we read described how instead of deriving by a single character, one could also derive by sets of characters. I then improvised the range approach by myself - it was very cool being able to handle unicode!
http://www.kylheku.com/cgit/txr/tree/regex.c
The derivatives implementation starts with the appearance of the function reg_expand_nongreedy.
Wow, I see that in reg_derivative where it handles compound forms, I'm testing for some vanishingly improbable internal-error cases upfront: presence of uncompiled character classes. Fixed that.
Russ Cox likes regexes with derivatives -- they are a "win-win". He doesn't like parsing with derivatives because of the computational complexity. Linked from that article:
https://research.swtch.com/yaccalive
Your link doesn't really convince me they addressed the concerns ... There seems to be some hedging in the language, like that it seems to be efficient in practice; and that it should eventually be efficient in theory too.
Warning: mysql_connect() [function.mysql-connect]: Unknown MySQL server host 'mysql' (1) in /home/ltu/www/includes/database.mysql.inc on line 31 Unknown MySQL server host 'mysql' (1)