Re: "tweetable" "symbolic" hex COM loader

>> The global assembler label is a remarkably powerful tool.  I  =

>> wonder, though, if
>> it might be a bit too powerful; perhaps the Forth approach (two  =

>> separate
>> stack-based mechanisms for backward and forward jumps, plus an  =

>> updatable symbol
>> table for calls to earlier-defined routines, giving each symbol a  =

>> scope from
>> its own definition until the next definition of the same name) is  =

>> actually
>> better.
>
> Good point.  This time I went with the decision for global labels  =

> in order to maximize straight-line code; taking the second pass  =

> means there's no requirement for dispatching[3].  MIXAL apparently  =

> makes a "single" pass by backpatching, so it's single pass over the  =

> input but random access in the output; given enough stack one can  =

> also claim  to make a "single" recursive pass, reading on the way  =

> down and writing on the way back up, but that's still fairly close  =

> to two monotonic passes.  One great temptation to use the power of  =

> the global labels is that other tools (such as a stack-based  =

> control-structure preprocessor) can then simply be streaming  =

> transformers.


Having been inspired by Darius' https://github.com/darius/regexercise  =

and http://swtch.com/~rsc/regexp/regexp2.html , I was recently  =

reminded of this latter (streaming transformer) principle.

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:
> The construction method descends from Ken Thompson=92s classic construc-
> tion.(1968) The present method differs from the earlier  =

> construction and deriva-
> tives thereof (Aho et al., 1986; Thompson, 2000) in dispensing with  =

> epsilon moves.
> Epsilon moves do not appear as either transitory or permanent  =

> artifacts of the
> construction process. There is no separate transitive-closure  =

> calculation to remove
> them, and no capability to simulate them. Only the tiny function bp  =

> remains as a
> Cheshire grin of epsilons past.

as even in an eager language, one can simply unfold the regex string  =

to a parse tree, fold that down to an NFA, and finally refold against  =

the input strings.

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)

-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!

[0] Ken Thompson, "Regular Expression Search Algorithm", CACM v11 no6  =

1968
which finishes with the observation that:
> It is also easy to
> incorporate new operators in the regular expression rou-
> tine. Examples include: not, exclusive or, intersection, etc.


Exclusive or would seem to give one the "quantum" equivalent of a  =

search, in that it would be possible for two otherwise matching  =

searches to interfere destructively, thereby failing.  I guess it  =

would be one way to stress-test how disjoint one's patterns actually  =

are: if the test suites passed with exclusive-or substituted for  =

inclusive, one could be confident that any ambiguities were lurking  =

elsewhere.  (or at least, that the patterns are triply ambiguous!)

[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*.

[2] [FoRK] hard edges, soft edges, lost edges
http://www.xent.com/pipermail/fork/Week-of-Mon-20101122/058148.html

[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  =

definitions brings us quickly up the direct route, from the  =

dictionary and two stacks mentioned above to subroutines (':' and  =

';'), alternation ('IF', 'THEN'), repetition ('REPEAT','AGAIN'), and  =

even rudimentary objects/closures ('CREATE','DOES>').
' DO: , LABEL : [/] LIT DO: , LABEL [/] ' [/] ,
: ; LIT NEXT , [/] ' [/] , IMM
: REF> HERE HERE , ;
: <DEF HERE !~     ;
: IF LIT JZ , REF> ; IMM
: THEN <DEF        ; IMM
: REPEAT R> HERE >R >R       ; IMM
: AGAIN LIT JMP , R> R> , >R ; IMM
: CREATE LIT NEXT , LABEL                                      ;
: DOES> LIT LIT , REF> LIT DOES! , LIT NEXT , LIT DOES: , <DEF ; IMM



-- =

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