Comment by rhelz | Hacker News Reader

Comment by rhelz | Hacker News Reader

We actually have a great tool to manage state, but nobody seems to have used it to its full potential: regular expressions.

Imagine your program is a big state machine, and inputs and other events are making it transition from one state to another, and when in a state the apropos actions are performed. On this view, your program just is a regular expression parser--the tokenized stream of input events is what it is parsing.

And what is a great, high-level way of describing a parsing state machine? Yup--a regular expression. When compiled, a regular expression is translated into a state machine. However, you can't really specify that an arbitrary procedure is called when it enters a state--it can only do limited actions, e.g. extract a substring.

If we could let the compiled state machine call arbitrary procedures when it enters a state, well, we'd have a new program-control-flow statement. A super-duper if/then/else.

Instead of writing state charts--absolutely the lowest level you can program a state machine at--we could specify the state machine in a very high-level, easier to understand and maintain way.

This would be, speaking as someone who has dealt with his share of state machines, quite confusing. The uncomfortable thing about regular expression implementation as automata is either (a) non-determinism (i.e. "being in many states at once" a la Glushkov or Thompson NFAs, not "non-determinism meaning something different might happen on any given execution") or (b) state explosion (in a DFA, to represent non-determinism).

This has a huge impact on trying to hook actions, call-backs, etc (your "arbitrary procedure") to NFA states as you're frequently making many overlapping entries to these states, many of which go nowhere. Trying to figure out which entries correspond to which other entries isn't easy.

There are very stylized automata that are used in parsing that do interesting things beyond the finite automata space (like pushing things onto a stack), but they don't correspond to regex per se - instead they are generated from a grammar.

re: nondeterministic implementations: Detecting and resolving nondeterminism is something every method of implementing state machines has to consider. Even when implementing a state machine by hand coding switch statements, you have to worry about whether or not you have inadvertently specified an indeterminism.

> interesting things beyond the finite automata space

State machines certainly can be glorified into LR parsers, or even into Turing machines by adding various bells and whistles. So sure, this idea shouldn't be limited to just regular expressions--we've got good methods of specifying even very complicated state handling.

I hope you saw the excellent comment on this thread where somebody talked about how Ken Thompson implemented paxos using yacc for state management. I've been around the block with state management too, but using yacc for state management is something that never occurred to me, and frankly, opens up a whole new world of possibilities.

BTW, it's also an answer to your point about the pitfalls of nondeterminism: yacc is a great example of how to specify a state machine while detecting, reporting, and resolving nondeterminism.

Perhaps this comment was meant as a joke, but this is exactly what lex does for regexps and yacc does for LALR(1) grammars. For the right job, they are both great.

I watched Ken Thompson write a Paxos implementation in yacc once.

> Perhaps this comment was meant as a joke

Nope, not a joke. As you say, this is just the application of parsing technology to a tokenized stream of input events.

its super-useful in creating state machines to do parsing---and it can be super-useful to create state machines for other things as well.

> I watched Ken Thompson write a Paxos implementation in yacc once.

In real time? dude, you gotta post video to youtube or post a "Tell HN" story about it.

It's not as exciting as it sounds. He wanted to play around with learning Paxos, which is a big state machine, and he used yacc to do it. I shared an office with him for a couple years in the early days of Go, and he was working on it while I was working on other things. I helped him track down at least one bug in the Go port of yacc that way. I think the grammar he was writing was completely regular, but yacc is nicer to use than lex.

Ken discussed yacc briefly in Coders at Work, which I quoted at https://research.swtch.com/yyerror:

Seibel: And are there development tools that just make you happy to program?

Thompson: I love yacc. I just love yacc. It just does exactly what you want done. Its complement, lex, is horrible. It does nothing you want done.

Seibel: Do you use it anyway or do you write your lexers by hand?

Thompson: I write my lexers by hand. Much easier.

> It's not as exciting as it sounds.

De Gustibus. Some of us are into that sort of thing. Thanks for the link.

> Thompson: I write my lexers by hand. Much easier.

LMAO. If you've been doing it since the 60's, I suppose you get the hang of it:

Ken Thompson, “Regular expression search algorithm,” Communications of the ACM 11(6) (June 1968), pp. 419–422

Regex with callbacks? Congrats, you’ve reinvented lex.

Wow, you are right. The first sentence of the abstract of Lesk & Schmidt's paper:

"Lex helps write programs whose control flow is directed by instances of regular expressions in the input stream."

Exactly what I was talking about. There's no reason to suck at state management, guys....

Well, actually, you store your part of your state in a theoretically unbounded random access memory device, or equivalently, a tape.

Yeah, but what if we didn't do that? I.e. when we are reading from memory, we treat it as part of the tokenized input stream, and whatever we are writing to memory is just the transformed output of the state machine.

This way, the contents of the memory wouldn't be state at all; they would just be, as it were, the scratchpad where sentences in the language accepted by the state machine, or output by the state machine, are found.

That's what regular expressions do for us: they are a compact way of specifying a language. Just a few characters--which is to say, just a few states--can specify a language which contains arbitrarily long strings.

But--even though the input and output streams can be very large, they no longer part of the state, and thus do not contribute to the exponential blowup of states.

Except the tape gets overwritten/looped over. What GP was referring to is event-sourcing the state in an append-only log and running finite state automata on this sequence.

Here is a java lib that apply regex to stream of Objects that could be used to achieve this purpose.

https://github.com/norswap/skelex

Thanks for the link, exactly the kind of thing I was talking about.

Reply on news.ycombinator.com