Re: "tweetable" "symbolic" hex COM loader

>> ..., 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.  ...
>
> 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.

True.  But the basic similarities to a compiler (front-end parser ->  
postfix syntax tree -> codegen) make me think that the key insight  
was that all of these tools could be used equally well in generating  
code for a nondeterministic machine as for the common case of a  
deterministic one.  One of his suggestions to avoid epsilon-looping  
(screen it out in the syntax and declare victory) seems especially  
familiar in that context.

> 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.)


Per your direct-threaded idea, one could imaging having a fixed  
thread where inactive states were overwritten with noops ... but then  
the distinction between this approach and a bitvector gets thin indeed.

Submatches nearly force deduplication.  Deduplication implies picking  
a duplicate with which to continue; submatching implies picking the  
duplicate fitting the desired semantics (and backreferences, it would  
appear, push in the opposite direction, but I didn't bother with those)

-Dave

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