Ragel State Charts | Hacker News Reader

Ragel State Charts

zedshaw.com

67 pointsraju30 comments

In my experience SMC ("state machine compiler", tres original no?) is better-suited than ragel for working with state machines that're easily specified as "state charts".

The difference is that ragel is oriented around consuming a stream-of-chars: the generated state machine expects to be consuming chars as input.

You can pick up on this in the writeup even though Zed's not pointing it out: he first has to define his messages as chars (eg: 'done' == 'D'), then he specifies his states + transitions in terms of those definitions.

SMC instead generates methods for each 'message' and it's the enveloping program's responsibility to call the correct method to update the state.

This is cleaner for simpler state machines.

None of this is intended as a knock on ragel, btw: it's a very solid piece of software, and for more-complicated state machines should be the go-to choice.

SMC also seems more robust. If you look in the examples section of the manual, they describe an "FSM" that can identify palindromes on the alphabet { '0', '1', 'c' }, where 'c' indicates the center. This is not a regular language -- SMC has a stack.

<http://www.cs.brown.edu/~sk/Publications/Talks/SwineBeforePe...; is a fun talk that describes an implementation of state machines in Scheme macros. With a good compiler, those tail calls will be translated to local branches!

Correction: ragel is not bound to chars. It can consume integral numbers of any size up to long. The numbers do not need to be in arrays. They can be embedded in structures.

That's useful, thanks.

Also thanks for this: http://news.ycombinator.com/item?id=134834

It's a wonderfully useful statement, and gets at what I was trying to get at much better than I could.

I stand by SMC being a better fit for simple finite state machines (eg: the kind best specified using state charts); typical uses I've put SMC towards are for ensuring consistency of internal state in complicated UI elements and similar tasks...for which there's no real 'regular language' that needs parsing (or, at least: no real gain to be had in setting up a regular language of input-events when state charts will do).

I'm guessing you're the thurston behind ragel: thank you for making ragel, for making it available, and for making it so well; it is an extremely high-quality piece of work.

Make blog post. Post entry to HN. :)

Honestly the smc programmers manual http://smc.sourceforge.net/SmcManual.htm is probably good enough. Its quite light; even with a blog post one would still have to extrapolate from the author's application to how one would apply the tool to one's own problem domain.

But +1 for SMC; used it quite a few times already, in many cases in new product versions replacing legacy code where the original insisted to implement a partially-identified state machine "by hand" (and invariably ended up tripping over all sorts of unforeseen and edge cases).

I've also found that merely the exercise of thinking in terms of FSM definition, often helps to simplify the problem (for example by identifying that there may actually be multiple independent/"orthogonal" FSMs present, instead of one monolithic one).

In the article, Zed says, "it’s just that nobody learns about state machines unless they take an obscure compiler design class. Very few universities teach state machines as a method of specifying the logic for a program."

My background is as a EE, and I work in hardware. I can't imagine not knowing about state machine design. Is Zed's statement accurate for those with a pure software focus?

I'm studying CS (in switzerland) and we've learned about state machines during a mathetmatics lecture in the second semester. that's it. since I didn't take the compiler class, this was the only lecture in which state machines were covered.

I personally think it's important to know about state machines. at least once in a lifetime you are going to write a DSL or parse specific input, and these are use cases were the application of state machines is pretty useful.

oh and by the way: Zed has written a nice tutorial about finite state machines, called "A Painless Introduction To Finite State Machines" and located at http://lamsonproject.org/docs/introduction_to_finite_state_m... . it's worth reading it if you're interested in the subject!

I would think that anyone who gets a degree from a reputable CS program would have to take a class in compiler design, so I wouldn't call such classes "obscure". Of course

(a) just because you covered it in a class doesn't mean you remember it five years later

(b) lots of people rise through the ranks of IT without formal CS training

(d) a lot of people buy into the "school is worthless" line so hard that even when something as practical as state machines are paraded in front of them they don't notice

(Granted, the education system might have some responsibility there, but personally I recall examples being made. There's only so hard the profs can make the point that this stuff actually matters.)

Mine as well. State machines early on. However, immediately went into computer programming but that stuck with me.

If a person reads GoF carefully, they talk about it there. Also, UML has a whole state machine concept segment and Uncle Bob wrote a package years ago to handle state machines.

I wonder if programmers rely too much on RE for problems that would be best handled by FSM.

Excellent article, excellent software.

RE and FSM are equivalent. There are no problems handled better by regular expression than by FSM. Of course, this is for a very narrow definition of problem. And, by most accounts, a narrow definition of FSM. SCM calls its systems FSMs even though they have stacks. Sure, the number of programmer defined states is finite, but the number of system states is infinite. Also, what do you mean by better? :)

So, for an un-specious response: FSMs are well suited to stream processing, while REs do well with block processing. (And are generally implemented by compilation into FSMs, anyway.) FSMs also do well as program logic/control structures, often clarifying the underlying system.

Well, equivalent in there is a direct transformation from one to the other, but in the sense of a programmer's approach, not really equivalent.

Yes, REs are transformed to FSM, but the problem-solving approach provided by skills in writing FSM is different, and according to the article, often better.

Funny you should say that, my background is also as an EE and I also can't imagine not knowing about state machine design. Yet just this week I had a junior guy tell me he's never seen the concept in software, outside of a testing harness for a hardware fsm.

My CS experience was that it was something that everyone studied, but only in a fairly abstract context, and I don't remember coming away with the notion that you'd ever actually use it for except parsing.

Your professors/program didn't serve you well, then. State machines are heavily used in computer games and for programming simple devices.

Also, compiler design classes are not obscure. Mine helped me land a job... working on a compiler.

Additionally, I find state machines in many business domains. Everything that some kind of "ticket" object (be it customer support or defect tracking) will (or should!) have state machines, with rules of varying complexity, to escalate the status of these tickets.

Zed seems to have a freaky ability not only to implement high quality code himself, but to find high quality code written by others, absorb it, and then explain it. Strikes me as the qualities that make a successful angel investor.

I don't get it, although others seem to agree with you. What does one have to do with the other?

The ability to recognize talented programmers and programs is pretty rare. This is why software projects with founders that can write usually succeed, because the responsibility of selling good code usually falls on the programmer (think Linux, Arc, Rails, etc).

Having the ability to see good code allows an investor to find the hidden gems-- excellent programs that no one knows about because they aren't promoted. I'd be willing to bet that there is a goldmine of ideas implemented in already existing code, just waiting to be discovered.

Thanks, that clears it up a bit.

I'm not sure I agree though, for two reasons.

First, the projects you mentioned are great projects, but they're not something an angel investor would be interested in.

Second, most startups - or at least web startups - do not fail for lack of technical expertise. The product might be an unusable mess, or it might solve entirely the wrong problem, or it might be marketed in completely the wrong way, or there might simply not be enough demand for it. I'm sure there are cases where a startup fails for technical reasons, but I'm willing to bet real money that in the vast majority of cases investors and founders don't say "man, if only the programmers were a tiny bit better, we could've made it". (even when they do say it, chances are that wasn't the real problem)

You're correct, they're most definitely not projects that an investor would invest in. However, if I am going to invest in someone, I want to know they can code. I want to look at programs they wrote while they were in college, or working a job. If I see a novel solution, my confidence in my investee goes way up.

Tons of people have great ideas, but their success is going to be determined by how well they can code. When you say that startups don't fail because of a lack of technical expertise, you're right in a limited sense. Startups of decent calibur will not fail because the founders don't know closures, continuations, design patterns, etc; they'll still be able to build products. They just wont have the vision to know the full range of products they are capable of building. If that's the case, you'll only last as long as it takes for a better hacker to enter the market. Experts Exchange being overtaken by Stack Overflow is a perfect example. Same idea, but because actual hackers are running Stack Overflow, it's trouncing Experts Exchange, with no signs of slowing down.

What makes you think Stack Overflow has any technical advantage over Experts Exchange? And, what makes you think their growth rates are at all correlated?

As far as I can tell Stack Overflow is a perfect example of a site where technical talent is almost irrelevant. Just like this site. We're not here because this site is written in Arc. We're here because of the community.

If not technical in terms of CPU cycles, technical in terms of design. For one, I don't have to scroll all the way to the bottom of Stack Overflow to see the answers to a question. Stack Overflow also loads far faster, and has unobtrusive ads. These are things that hackers understand are important, and the suits have a difficult time understanding.

I think you're still missing tsally's point. He pointed out those projects because they required the original implementer to advocate them. His point was not that they would make good investments, but that they probably would not succeed on technical merit alone; they required someone who understand their technical contribution to advertise them to others.

I think your second point is off, too. Your argument is that startups usually fail for non-technical reasons, and I agree. But that's what tsally was trying to say: it's a rare person who can smell-out good technical work, understand it, and realize it's contribution. This is the sort of person you'd want to have as an adviser when it comes time to determine a business model or how to advertise.

All of this sounds super fancy, but it’s really based on solid research done on state machines over the years. Adrian simply took all the best research and built a sweet little domain language for state machines.

This is why research and open source are important. And kudos to Adrian.

Erlang encourages this style through its OTP library; all of the default OTP behaviors include state machines as part of their operations, or make it so easy that they might as well. (gen_fsm is, as the name implies, a finite-state-machine, and it's trivial to use pattern matching to use a piece of the state in gen_event or gen_server to do the same thing). It doesn't sound like it has the full range of awesome that Ragel state charts do, but it has a lot of the value. It definitely gives you a lot of confidence that nobody can trick your server into doing something unexpected with weird input unless you do something very wrong yourself.

I'll just state here that this is also what powers _why's excellent Hpricot HTML parser.

Back in my last job, I implemented a Java libconfig clone using Ragel. It was the most fun I ever had at that company.

That's awesome.

this is an awesome article... nice job, Zed. I want to try it.

Reply on news.ycombinator.com