Re: "tweetable" "symbolic" hex COM loader

> Based on Cox' description of the Thompson construction (and dim  
> memories of the Dragon book), I bashed out a nondeterministic regex  
> machine in an evening.  (Thompson, naturally, takes a route[0] that  
> comes naturally to language implementers[1])  It initially seemed a  
> bit wasteful, for we extract the tree structure once while parsing,  
> flatten everything down to a list of VM ops, and then essentially  
> implicitly reconstruct the tree when following the epsilon  
> transitions.  So the next version wound up very similar to Doug  
> McIlroy's recent Haskell interpretation:

Which I haven't read, but it sounds like you might've also wound up 
similar to http://sebfisch.github.io/haskell-regexp/regexp-play.pdf
(which I haven't read either, but it represents a set of NFA states as
a regex tree with marks on the occupied states, apparently)

> However, upon reflection, Thompson's version actually shows masterful  
> use of lost edges[2].  Both McIlroy (16pp) and I had to come up with  
> a set of equations that effectively evaluated the transitive closure  
> while building the transition matrix, while Thompson (4pp) simply  
> relies upon the equivalence of the transitive closure and transitive  
> reduction, working with the latter so he can do almost everything  
> locally, implicitly, and in bounded space.  (In order to debug my  
> equations, I cross checked them against a transitive closure -- at  
> which point I realized that my constituent equations and tree folding  
> took some 20 odd lines, while the powerful global transitive closure  
> tool was only 3)

It's an impressive paper and I wish he'd had space to say how he
worked it out, thought of it as worth doing, etc.

It's possible to refine it to avoid epsilon-looping without keeping a
set of visited states: Thompson showed one way, which was kind of
messy and made NFAs of size exponential in the depth of regexes like
((a*)*)*. Here's a different way that does check for past visited
states, but only needs to remember one of them at a time:
https://github.com/darius/regexercise_solutions/blob/master/star_thompsonlike.py
(the similar code in accepts() and after() can be factored out, 
but it's less clear that way; relatedly, Thompson reports matches
only after a 1-character delay)

Or avoid building epsilon-loops in the first place:
https://github.com/darius/sketchbook/blob/master/regex/nfa_avoidloops.py
(I tried to do this in my Erlang regex library, Ergex, but I couldn't
figure out how at the time. Hopefully it's right this time.)

> -Dave
> 
> PS: anyone care to write the Javascript interpetation of Thompson's  
> version, in which the automaton runs as subroutine-threaded code,  
> JIT'ing new code[3] for each new state?  At least we're on larger  
> machines now, even inside a browser, so we don't have to self-modify  
> and throw away each state when swapping to a new one!
> 
> [1] Actually, he's rather hard core.  Anyone can write an interpreted  
> VM; many BitBLTs back in the day where compiled onto the stack,  
> specialized for each call; Thompson JITs code to evaluate an  
> arbitrary subset of states *for each input character*.

Unfortunately I found that if you keep your loop variables in
registers then his code would've been shorter without the jitting, and
approximately as fast (some things a bit faster, some a bit
slower). That is, his set-of-states is a sequence of CALL instructions
(in modern parlance) but it could as easily be a sequence of addresses
to call (subroutine vs. direct threading). Either way, the addresses
that go into that sequence point into code that was compiled just once
for the regex at the start.

His set isn't deduplicated, so it can blow up. Something I've thought
of doing, but haven't so far: deduplicate using more truly
self-modifying code, so the first time for the current input character
that one of the entry points is invoked, it patches itself to just
return, doing nothing, on subsequent invocations. (It has to queue an
unpatch into the agenda for the next next character.)

A really efficient modern NFA engine would probably skip these
shenanigans and work in terms of bitvectors, alas.

> [3] javascript turns out to be a congenial host for forth; I have a  
> simple version which I hope to post here once the exposition has been  
> clarified a bit, in which (as long as we're willing to --a la Ueli  
> Steck-- travel light, without overbyte), the following set of  

I'm looking forward to it. :)

Darius
-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss