Stately State Machines with Ragel
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Duggan, Ian
State machines are an important tool in computer programming, and Ragel is a wonderful tool for creating them. Come learn how to use Ragel to compose simple state machines into much more complicated versions useful for parsing and processing all manner of input. We'll progress simple regex-like machines to full-blown context-sensitive scanners capable of ripping-fast processing of protocols and language grammars.
 OK, guess we'll get started now. Welcome, everyone. This is a state-lead state machines with Rachel. Thanks for coming to my talk. I guess there's a couple to choose from. So I appreciate that. I'm a little jet lagged, so if I seem like I don't know what I'm talking about, that's probably why. Who here has heard of Rachel before? I worked with it just so I know who's going to go online. OK, damn it. OK, all right, we'll just get started. So the goals for this talk are to convince you that Rachel's worth trying if you haven't used it before, and to give you some intuition about how it works, and to show you how to set it up so that you can kind of do some basic parsing with it. Just a little bit about me. My name is Ian Duggan. I'm into kind of lots of different things. I play hockey several times a week. This is Storvy the Pig, where I come from North Carolina. Pig's mean hockey. I play guitar. I play bandro, mandolin, ukulele. I'm a fiddle, but it's got a ring of dust, and my cats actually appreciate that. Sometimes I fly. I've got a Cessna 120 that I fly out of Hayward, California. It's got a whopping 85 horsepower, but it's fun to put around the bay and evaluate that. I love my cats. A couple, you know, got to have cat pictures in a presentation, so here they are. This is Purrington, we call him Bufus. This is Minnie. She's a goofball. She likes to wear outfits. She doesn't care. She thinks they're fun. This cat likes being cozy. These ones are dopey. Jill. Minnie likes to sit in strange places. So I'm a software guy. I code things. I code the internet and the Googles. I'm a recovering technology entrepreneur. Been in and out of startup institutions for many years now. My current status is that I work for Twitch. I do online streaming social video games. Obviously, we're hiring. We have lots of Ruby. The whole front end is Ruby on Rails. The back end is getting redeveloped into Go for a lot of our services, because we need a performance. I've been using Ruby for quite some time now. I started on the 1.6 days. A friend of mine gave me a 1.6 book, and I was kind of playing around with it. I thought it was a pretty cool language. So I don't know when the transition happened, but I've just kind of stuck with it since. But enough about me. This talk is about Ragell. Ragell is this really cool tool. And it's used in a lot of sort of a high performance text parsing areas. And some people seem to have discovered it and are using it for stuff like that. And there's a lot of other use cases where people are kind of flooding with regular expressions, where I think Ragell can be really helpful. It's got a lot of features that allow you to do some kind of really cool tricks with it. And if you don't have it in your bat belt, I'm hoping that you'll add it today. As I mentioned, there are many projects that use Ragell. Mongrel, Unicorn, and Puma are kind of the ones that people know about the most. Zedshaw, I think, kind of popularized it about 10 years ago when he rewrote the Mongrel HTTP protocol parsing API with it. There's a really cool gem called Whitecork, which actually parses Ruby using Ragell. The MailGem, Redcloth, Hprokot, Kirk, and they all kind of make use of it. So just really quickly, what does Ragell look like before we jump into it? It's this DSL. You can kind of define some actions. And then you've got some ways of converting different terms into other terms. So that's kind of what it looks like. And we'll get into the details here shortly. So most people are familiar with regular expressions. Regular expressions are easy, for the most part. People understand them. It's kind of the basic stuff that we all understand. Matching, grouping, alternation, matching zero, one or more, n times, n times, et cetera. Ruby has really great tools for regular expressions, because it has a heritage from Perl, Zed and Ock, which relied heavily on this. So you can do fancy things like match stuff and in a block, match some more stuff and in a block replace something that's three regular expressions down. So you can get pretty fancy with them. But at some point, they can become irregular expressions. So if you've ever opened up a file and stared at something like this, then Rachel might be something worth considering for you. They have their place, but there are better tools. Sometimes you want more control. And I posit that this means you want some sort of automaton. So just a little bit about automatons. Like finite automata, they're basically these devices. They have states and transitions. Many people have probably seen these. You've got circles and arrows. And some input comes in causing a transition to another state. There are two basic types. There's a deterministic finite automata and non-deterministic finite automata. It's just an academic distinction. Deterministic means it can just be in one state at a time. Non-deterministic means you can be simultaneously in two different states. However, you could map those multiple states as super states and the single states and convert that into a deterministic finite automata. So in academia, they talk about this equivalence of regular expressions and a phase of TFA. So all this stuff that you're doing with crazy regular expressions, you can kind of do with these other tools. So you should choose the tool that kind of makes the job easiest for you at that point in time. So as a superset, these are all state machines. State machines are an important tool in computer programming. Ragell is a wonderful tool for creating them. And state machines are everywhere. And they're in your stoplight. You have green, the timer goes to yellow, goes to red, goes to green, goes to yellow, goes to red, goes to green, around and around forever. They run your CPU. If you imagine your computer, like every single bit that's in it, as kind of a definition of a state, then every piece of input causes it to transition to another state, your computer is one gigantic state machine. There's some kind of non-state machine stuff that happens on the edge when inputs come in asynchronously and stuff, but for the most part, you can take it a bit like that. It's a big working state machine. And there's other examples everywhere. So I watch it as vending machines. I've mentioned traffic lights already. Park code scanners. Pretty much any piece of machinery these days that isn't analog has any kind of computing domain so it's going to be a state machine or something. So I think they're the cat's meow. I think they're great for many reasons. They're simple to understand. And there's a great deal of research around finite automaton state machines. With the right approach, they can also produce code that is faster, easier to maintain, and more correct, and thus most secure. They're very specific about what inputs are accepted and what aren't. And it's harder to get it to parse something correctly than it is for it to admit something that doesn't parse, which could be very useful. If you're still not convinced, we should probably just spend some time looking at what they're. So let's go over some vocabulary. So state machines, they all have something called a start state. It's usually designated S0. This is as it sounds like the first state that those state machines start to. They also have on the other side an accept state or a final state. They can have multiples of these, just depending on what they are. When the machine transitions to this state, it is said to have accepted the string. So within a state machine, to go from state one to state two, in this case, when an H is received, you go from state one to state two. It's called a transition. It's usually an arrow in a diagram that's labeled with an arrow. Sorry, it's an arrow in a slit. There's a special kind of transition called an epsilon transition. This allows you to go from one state to another without taking any input. So this can be useful to wire like the up. You could take two state machines, stick them together, and basically it works like a concatenation, like you don't need input to go from one to the next. So with what we know so far, we've got a couple of simple state machines that we can build. Like if you think about a regular expression and how it's parsing things, this is kind of what it looks like. So A star will take any number of As and just kind of keep mapping on it as long as the first one was an A. The second machine just maps a single A and then you're done. This next one needs an A, and then as many As and as one after that point. So that's A plus. And from that, we can get more complicated. So this is a machine that will match zero or more hellos. So the start state is actually a final state, so that's acceptable. But once we've taken an H, we need an ELLO before we can get back to a final state again. So whenever this is in a final state, it's accepting the input. So you may be asking, what's the big deal? I mean, these just look like regular expressions. I've done this before. I don't really need this. So what is Rachel exactly? Rachel is a finite state machine compiler with output support for C, C plus plus, C sharp, objective C, D, Java, O, Camel, Go, and Ruby. So if you're doing stuff across projects, it's really useful. It also supports a generation of several different ways of working its way around the states. And it's really useful for building electrical analyzers and protocol definitions, et cetera. So I talked about state machine generation. So another unique feature of it is that with these states and with these transitions, you can attach arbitrary code at any point in time. So as you're moving around the state machine, you can pull things in and out of the input and jump around in the state machine. And these are the features of Rachel that make it really different than just a regular expression. The regular expression, you can match a string where you can't. With Rachel, you can match half the string, jump to the end of the string, do some stuff, jump to the beginning of the string, give it some more data, download something, upload it to YouTube, and come back. You can do that all inside Rachel if you want to. I'm not sure I would recommend that. So I'm actually wasn't sure how to pronounce it. I've been saying to Rachel forever. Rachel, there's a regal, there's Rajul, there's a bunch of different ways to do it. So you can get the answer from the horse's mouth, because Adrian Thurston had created it, actually, I guess sent an email. It's fine. And he said that it's actually Rajul, which is not at all, how I guessed. He said it was based on his R and L for regular language, and his nickname was Aj, even though he's Adrian or age. So maybe it's Rachel, maybe it's Rajul. If he's age, it would be Rajul, but he wrote Rajul. So I still don't know that. But the female, please let me know. So darn, I've been pronouncing it wrong for quite some time. So on a more basic level, Rachel is a DSL for creating these state machines. And it's especially useful, as I mentioned, for parsing protocols, data formats. It's incredibly powerful. It allows you to do this in sort of a EBNF kind of format. So you get this really declarative approach to parsing text as opposed to kind of while loops and for loops and function calls and returns. So let's just take a look at the DSL. I've got a better idea. So the general structure of a Rachel file it'll be written in the host language. So if you're in Ruby, it'll be mostly Ruby. And I'll have some sections in there which kind of call out pieces that are Rachel. So this is a machine which matches Fuba. You can name several machines and refer to them inside your file. There are definitions and instantiations. So this defines a piece of state machine that you can use and you can compose it into a bigger state machine. And to actually generate states, you need to have an instantiation of some sort. This is done with colon equals. And like any kind of programming system, you can include and import and do things like that. There's some slight semantic differences in terms of what those mean. So you can refer to the manual for more details. White space is ignored. Coddles are started with a pound just like in Ruby. There's different kinds of literals. There are string literals, regular expression literals, grouping literals. Got kind of standard escape characters that we're familiar with. And if you need to jump, if you're inside a Rachel section, you need to jump out to the host language. You've got to put it inside braces like this. Numbers can be specified as either integers or hexadecimal, which is useful because when you're parsing in Rachel, you're actually looking at the binary value. So if you're looking at an A, it's actually a capital A. It's actually 65. So you'd be aware of that. You know, it's got a couple of keywords. So these are kind of first section here. This is the stuff that is more like a regular expression. So this matches the word simple. So nothing too fancy there. We're going to have unix expressions similar to regular expressions. We have zero-linked matches. We have numerical literals, as I mentioned before. Like this is matching 42. So this would be the ASCII character represented by the number 42. And you can have regular expressions inside Rachel, which could be a little bit line-bending. But regular expressions actually compile down into state machines. So this is actually pretty obvious when you think about it. We have range expressions. So if we want to match A to Z, same as regular expression, A to Z. This is where we kind of start to jump out of what you can do in regular expression. Here you can kind of name something called secret code and refer to it in a different place inside the regular expression. So you can name it once and it will use it in five or six different places. And there are a bunch of sort of built-in character classes. Any ASCII extend, printable and control graph. So for basic stuff, you can just reach to one of these. You don't have to define it all in front of you. So at this point, we sort of have the basic building. Blocks for building were complicated machines. These are like levers, wedges, wheels, pulleys. These are like the simple machines that mankind has built. And on top of that, we built rocket ships and got to the boom. So that's what we're going to do next. Here's another cat picture. So when I was first learning about Ragell, I kind of heard it was useful. I wasn't quite sure why. I was reading through the user manual. That's like, if you really want to understand how it works, that's the best way to do it. There's a really good PDF online about that. But it has this really interesting thing where you can take a really complex machine and add it to another machine or subtract it or do an intersection or a difference or a union. And it will do the math to kind of add and subtract the state so that it does what you expect. This is kind of my blog when you see it in process. Compositional operators are the things I just mentioned, union, intersection, difference, strong difference, concatenation, things like that. And we'll go and check in detail in a second here. So a union, you would take, this string up top could be matching, this could have 1,000 states in it, and one on the bottom could have 1,000 states in it. The state machine will traverse both machines at the same time and enter a final state. But it does this by adding to get all the states and lining up the final results. Sorry, the final states inside it. I'm going to bug in my slide here, so my union example is a charm. We have an intersection. So that matches any string that would be in both machines. So this is an example of that. It's taken a machine on the left here and a machine on the right, and it merges them together into kind of one mega machine. So we can do a difference. So this would take any string, the first machine matches, minus any string in the second machine matches. This is the state machine that you get from that expression. So as you can see, it's pretty complicated. Coming up with that yourself would be a mess in trying to do that code. We'll probably do that. But it's actually pretty simple here in the DSL. You have a notion of a strong difference. This will match any string in the first machine. Sorry, any string of the first machine that does not have any string of the second machine has a substring. So one example would be I want to match any character except control character-turned-line feed. Character-turned-line feed is a compound string. So concatenation. And this is just taking the epsilon states out of one machine. Setting up epsilon states which come out of the final states of the first machine into the second machine creates a global machine. Concatenation example. And you have other things that relate to regular expressions like the play star. So this is A back, more basic repetition. We've got the optional operator, optional example. So this would admit any string that the machine doesn't match. Negation example. Sorry, I'll give you a second. Special form of character-level negation. If you just need to get negated on a single character, there's a special operator for that one. It's this. When you go through the work of putting these machines together and feeding them into Rachel, it does a kind of final process called state machine minimization, where it does some optimizations of the states within the state machine. And at any of them that are redundant, it can kind of subtract out. So you may initially have 1,000 states that you kind of added together that could subtract it down to like 250 equipment. So I mentioned before, like one of the powerful things you can do with Rachel is attach user actions to different parts inside the state machine. So this is some examples how you would do that. You can define an action statement inside the DSL and then attach them to the transitions. So there are different kinds of transitions. There are entering transitions, so I'm going into a state. You can attach there. You can attach to a finishing transition, which is coming out of state. You can attach to every single transition, or you can attach to just the leaving transition. And you would do this, you would choose based on kind of what you're doing which one of these you want to do. And the embedding operators can get really fancy. There's like two or three pages in the manual about how to do this. So if you need any details, just suggest you check there. One of the problems you can come up with is this notion of non-determinism. So you may have two machines that are stuck together, and you can't get out of the first state to match on the beginning of the second, or you can't get out of the first machine to match on the beginning of the second machine because they're matching the same characters. So an example would be this machine here. So the new line in white space will prevent the final new line from matching. So the solution is to exclude it from the beginning. There's also ambiguity problems. Like if you're trying to match, if you're trying to match like a C comment, for example, you might say, okay, match slash star, give me anything and then give me slash star. But you'll never match the slash star because you're matching on any. And you can do things like, okay, match on anything except slash star and kind of add things together like this, but that gets up late. Rachel fortunately gives us some tools that are easier to reason about, so you don't have to kind of do the suckling stuff. The way it does this is it allows you to set priorities on the states. So you could say that I want the transitions like going to the second machine to have higher priority. So one of the techniques it gives you is a special notation called guarded operations. And these are called guarding concatenations. So an example of the one we just looked at, how do I match, say, on a C comment? When you use this kind of colon greater, greater, this causes the slash star and this final machine to match more strongly. So I'm going to match on any as long as it's not a star slash and then it'll kind of come out of the machine. So we've got, there's a couple of different forms of that, whether like the right machine is stronger or the left machine is stronger. Or if you want a longer smash, but you don't want to kind of stay inside it. So one of the things that you, so that's kind of for simple matching, but a lot of times we're trying to build a scanner. We want to scan a file and we just want to recognize tokens in it, like one after another, after another, after another, have it keep going. So Rachel has a notion of a scanner and this will keep matching on the input and it will take the longest match that it can and recognize that time after time. So an example of that right here would be like, so if you're kind of like, this is like parsing headers. So right here we're saying a header, like within a header, I can match out a word, a space, or a new line, and this is what I'm going to do for each of those. So it's going to keep matching on word. There's a space that's going to ignore it. And then it's going to effort her which is actually kind of coming back to work on F call. So as I mentioned, it's really useful for protocol parsing. This is what ZXA did and that's what Puma uses it for. So if you want like a good detailed example, kind of like parse HTTP using Rachel Puma, I think is the best resource. And up to this point, we kind of been thinking sort of on the level of regular expressions, but on a lower level, these are just states and transitions and Rachel actually lets you kind of go down into what it calls the assembly language of state machines, which is just saying, I want these states, I want these transitions, I want these characters to go from one to the next. So you can also define those. So this is an example of parsing XMLC data body. So this actually defines three states, start one and two, and some of the transitions based on what it's matching to go from one state to the next. And you can use F call and F return to kind of set up function calls within Rachel, which is useful as well. When you start parsing stuff, the Rachel, you're probably going to reach for it. Like instead of running a scanner or Alexa, you're going to say, oh, maybe I can use Rachel. One of the problems with it is parsing recursive structures. Regular expressions are not good for that and Rachel's equivalent to a regular expression more or less. So how can you do that? The trick is to take advantage of these actions that you can embed and when you recognize within your pars that you are looking at a sort of a nested construct, you can, in your host language, set up like a stack and push a context to that and jump out and jump back and look at your stack when you need to. So because you've got these embedded actions, you can like step outside of what regular expressions allow. You can also implement look ahead. So the trick here is you would match on a couple of characters farther than you want and then you can call F hold, which will kind of back the parser up. So each time you call it backs it up one character. So internally, when you're working with Rachel, it has all these, it has these variables that you're going to interact with and they represent the state. So there's data, which is a buffer, which is where you kind of store your strength. So we'll see in a second here, like when you call Rachel, you basically set up data in a buffer. You set a variable called P, which points to the front of the data, PE, which points to the end. And then you just tell Rachel to go and it'll match on everything between P and PE. When more data comes in, you come and tack it on to the end, move P and PE and tell it to go again. So if you want to match one character at a time, you can just line up P and PE and it's kind of moving them all. And when you're inside a scanner, it actually uses some other variables TS and TE because it's, in order to do the scanning and do a longest match, it actually looks ahead and stores some state on its stack and backtracks what it needs to. So roughly, you know, you start at state zero, you feed it data. It runs the exact loop. The characters move through the state. You consume its P to PE data. And it's done, if your current state matches a final state, which gives you a list of them, it means you've admitted the string. For scanners, it's similar except it uses TS, TE and the stack. The way you extract a string, when you're... So this is like, as you're moving through the scanner, like you'll use this kind of slash mark that marks the beginning of something you're interested in. And this percent will say like, I'm leaving the transition. That's what I want to admit. So when I enter, I store where I was. So data P. And then when I leave, I store data P. I store from my mark to my PE. I pull that out and I store it into my things or A, for example. As I mentioned, there's a bunch of different post-language, languages and coding styles. One of the nice things you can do with Ragell is you can write a generic parser and just refer to all these actions by name. And you can have multiple other files that you would include. So I could have one definition of HTTP. And then my actions, I could have my actions defined in C and the actions defined in Java. And that's actually what Pima does. You can also prototype something in Ruby, get it working how you want, and then go convert it to C pretty easily, because you have both of your logic inside Ragell. So the director is that you need to put in your file or in a net, which sets up quite well the state. Data, which has all the states and transitions. And exec is actually, causes it to run that loop that I was describing. So this is an example of some of the code that it generates. So installing it on a Mac is really simple. Just brew install Ragell. And to generate the Ruby from a Ragell file, you just say Ragell-R for Ruby. Simple.rl would be the Ragell file in this example, and you give it the output. So this will build your Ruby file. We'll take a look at it in a second. And debugging these things, it's kind of hard to do visually, or it can't be hard to do visually. So Ragell actually lets you emit these out to a graphis.file, which you can then kind of make an SVG or a PNG out of and kind of look at all the states. So I'll show you in a second. So this is an example of calling it from Ruby. So this would parse the data. So we take the data, we have to unpack it into the binary format that I mentioned from characters. We set the EOF as a variable that Ragell uses to know when it gets to the end. Tokens is our variable where we're storing things. Calling it, calling it exact, and that's going to process everything that you put inside data. So somewhere in the actions, it's actually pulling things out and storing them, and the tokens are right here. So I created a tool here for kind of doing some visualization. I just want to pull it up and figure out how to get onto the screen. Can you see that? I actually can't see it, so I'm going to turn around here. That's done. I'll just mirror the displays, right? Where is my cursor? Okay. Where did it go? I want to still end over here. So this is actually a little app that I built in Vault, which is a pretty cool framework. You guys haven't used Vault, so you can go to check. But it allows me to experiment here and see what these graphs are. So normally to build these, I would have to run a couple of command line commands, but I just set it up in here so I can do stuff like this. So I've got examples of the different machines in here. So this is a machine that matches on a simple... I don't update. So this is an example of the state machines that are being created by this. So if I want to match on sim or PLD, it would look like that. Or if I want to zero more of those. Let's say I wanted one more of those. So I can kind of build these things up and play with it. I have the code for this referenced here. So this is a presentation. That's a guarantee. So if I want to create a new machine here, so I'll just call this the machine. Let's take a look at some examples here. Everybody see that? So this is an example of the machine... Well, it's like the machine I showed earlier where it was matching on... This is the machine I showed earlier. It's matching on zero more of those. So I've set up sort of a regional parser base here. I'll actually take a look at that. So in parser base, I have... I'm setting up some variables manually here. I have a way of feeding it data. I have a way of asking if I'm in a final state. I have a way of pulling out the current match. And I just sort of have it... I have a way of feeding data here which I'll show you in a second. But I just have this set up so that I can read from standard A and so I can use it for experimentation. So this is a hello... This is hello parser. This is what the file you work with looks like. And then we take a look at the generated file. Oops, sorry. Hello.rb. So this is the generated file. And Rachel is doing all this work for you. So this is setting up all the states up top here. This is a pretty simple state machine. So there's not much going on here. But this is the init that we saw. This is the perform method. And this is the exact that was buried inside of it. So it's setting up all the states. It's doing go-tos and jumps and matches and et cetera. So all this really nasty code which is heavily optimized. So that's why it's so fast. So this particular example here... So that's the result of this. And this is a pretty simple state machine. So I'm going to run this one out in a second. Okay. So... Okay. Okay. Okay. Okay. Okay. Okay. Okay. Okay. One small more. Let's try the next one. Oh, that's coming to that one as well. So I typed h. You can kind of see that it's in current state one now. p is at one and pe is at one. And we have one piece of data at h. I say e, l, l. Our final state here at the bottom is still false. So we're not in a final state. We press o. We've now entered a final state. So we've matched on hello. And I press h again and we're not matching. e, l, l. But if I press any other character, I'm going to step outside of what it knows. So I'm now in an error state. I'll never match again. So I'm going to do a basic example. I have some arg parsers defined here. So there's, I mentioned state charts and not using state charts. So I've one defined here using sort of standard approach. So this is the main part of my parser. And I'm just saying I want to match on an arg dash and flags or dash dash long opt. Long opt. I have defined as a bunch of alphas. So it would be a bunch of alphas as well. And what this is going to do is this parser is going to go around, around on a loop and when it sees some dash dash long opt, it's going to call saw long opt. So the Ruby code is actually pretty simple there. And these are the actions up here. So I call mark arg when it took out a mark just out of it. Oh really? Can't see no. How do I change the color? Yeah, it's going to do. How do I do that? What's that? You're going to get a lot of changes when you have a prediction to be working on this. Okay. Where's my system preferences? Accessibility? Accessibility? There you go. Is that more legible? Yeah. Okay. So what I'm doing here in the code is when an alpha is matched for its first time, I'm kind of marking the beginning of the argument, marking the beginning of the flags, marking the long arms. And then when I get to saw arg, which is what the scanner calls, I'll use that previously marked thing to kind of pull out what was there. Well, that's freaky. So now I'll see if the math should be in the way. So I can do dash A S D F. And see it. And I'll put in flags A S D F so that means I'm not showing that there. So now I can do like a long one. I can just say a long opt. So I matched on long opt. So that's just an example kind of doing basic argument parsing there. And then I have an example of this in the sort of state chart for as well. So state chart is a little bit more complicated. When you draw it out of paper, it's simple and you can actually do the dot biz visualization of this as well. But I start and I start state here. If I see a dash, I'll go to preflag. If I see a quote, I'll jump to quoted value. And if I see anything else, I'm going to kind of start a value arc. So as an example, this is what I'm calling. Valar is just kind of a word, quoted V, could be a quoted word. Flags would be this and like a long, long flag would be that. So the basic idea here is that you create some buffers and as you match or kind of go around in a circle in a state, I'll keep it pending to that buffer. And then when I leave the state, I'll admit what I want, looking up what I've stored. And sorry, the Ruby code for this again is very simple. Most of them is being done up inside the parser. So as an example, the same thing, but I can say, you know, ASDF and then Valar and I got a Valar. I can say quote, quote V and I got a quoted value. Space brings me back to start. I can say dash dash long equals, I got a long quote, quoted, and I got a quoted. So I have links to all those codes. So after the presentation, you guys want to like pull it up and kind of like dig through here to figure out what's going on. It's in there. Let me go back to the presentation here. I can find it in this color. In Invert. I can find it in this color. The presentation is closed. So while I'm looking for this, does anyone have any questions? I'm not familiar with what, so TreeTop is all in Ruby, right? Yeah, so TreeTop is, it may be similar, like presumably they may be doing kind of similar techniques under the covers. I'm not super familiar with how TreeTop does things, but this is like super highly optimized. Like for the C version, it can actually, actually one of the versions compiles it down into just jumps within a while. So like it'll go to the bottom, it'll go to, it'll go to, it'll go to, it'll go to, it's almost like optimized assembly. So I'd be surprised if it wasn't faster, but it probably really depends on these things. No, definitely. It allows you to, it allows you to do the chunking. So you can kind of think about your problem in smaller pieces and unit test those and then compose them together. So as I mentioned, the composition is, like it's two main things that make it really cool. The composition is one of them. Like that's kind of mind blowing. And then the fact that you've got these actions. So I can not be in a programming language and then suddenly be in a programming language. Okay. Right, right. Yeah, I mean, if you're, if there's treat up to other languages as well. Okay. Yeah, so if you, if you were writing an HTTP parser, you wanted it to work like, you know, quickly on J Ruby. So you wanted it down in Java and also like in C Ruby. So you wanted it down in C. This would be a good choice. Right. Yeah. So the question is like, how do you know this is using instance variables and kind of local variables. And so how would you like turn this into kind of like a composable unit? Yeah, so that's, that's actually kind of what I, what I tried to demonstrate here. So I created this regional parser base and I have, I have several parses which kind of inherit from it. The default is to use local variables, which obviously it's kind of painful. Part of the DSL, you probably can't see it again. So we invert this. Yeah. So this is, since I, it depends on where you put these, it depends on where you put like these things. So right, I put these inside this object that I've created. So when it, when it refers to app, it's going to be in the context of this object inside the context of this method. And you can remap what it does. So normally it'll just refer to P. I have a referring to app P because I set up the stuff up here. Oh, hey, there it is. So I showed the demos. That was it. So I've got these resources here. I have the slides up and I've got the, I got the playground code up there. I had some other features I wanted to add to it, but I kind of ran out of time. So I hope that was useful. Sorry if I drowned on. Yeah.
 OK, guess we'll get started now.  Welcome, everyone.  This is a state-lead state machines with Rachel.  Thanks for coming to my talk.  I guess there's a couple to choose from.  So I appreciate that.  I'm a little jet lagged, so if I seem like I don't know what  I'm talking about, that's probably why.  Who here has heard of Rachel before?  I worked with it just so I know who's going to go online.  OK, damn it.  OK, all right, we'll just get started.  So the goals for this talk are to convince you that Rachel's  worth trying if you haven't used it before, and to give you  some intuition about how it works, and to show you how to  set it up so that you can kind of do some basic parsing with  it.  Just a little bit about me.  My name is Ian Duggan.  I'm into kind of lots of different things.  I play hockey several times a week.  This is Storvy the Pig, where I come from North Carolina.  Pig's mean hockey.  I play guitar.  I play bandro, mandolin, ukulele.  I'm a fiddle, but it's got a ring of dust, and my cats  actually appreciate that.  Sometimes I fly.  I've got a Cessna 120 that I fly out of Hayward, California.  It's got a whopping 85 horsepower, but it's fun to put  around the bay and evaluate that.  I love my cats.  A couple, you know, got to have cat pictures in a  presentation, so here they are.  This is Purrington, we call him Bufus.  This is Minnie.  She's a goofball.  She likes to wear outfits.  She doesn't care.  She thinks they're fun.  This cat likes being cozy.  These ones are dopey.  Jill.  Minnie likes to sit in strange places.  So I'm a software guy.  I code things.  I code the internet and the Googles.  I'm a recovering technology entrepreneur.  Been in and out of startup institutions for many years  now.  My current status is that I work for Twitch.  I do online streaming social video games.  Obviously, we're hiring.  We have lots of Ruby.  The whole front end is Ruby on Rails.  The back end is getting redeveloped into Go for a lot  of our services, because we need a performance.  I've been using Ruby for quite some time now.  I started on the 1.6 days.  A friend of mine gave me a 1.6 book, and I was kind of  playing around with it.  I thought it was a pretty cool language.  So I don't know when the transition happened, but I've  just kind of stuck with it since.  But enough about me.  This talk is about Ragell.  Ragell is this really cool tool.  And it's used in a lot of sort of a high performance text  parsing areas.  And some people seem to have discovered it and are using it  for stuff like that.  And there's a lot of other use cases where people are kind of  flooding with regular expressions, where I think  Ragell can be really helpful.  It's got a lot of features that allow you to do some kind of  really cool tricks with it.  And if you don't have it in your bat belt, I'm hoping that  you'll add it today.  As I mentioned, there are many projects that use Ragell.  Mongrel, Unicorn, and Puma are kind of the ones that people  know about the most.  Zedshaw, I think, kind of popularized it about 10  years ago when he rewrote the Mongrel HTTP protocol  parsing API with it.  There's a really cool gem called Whitecork, which  actually parses Ruby using Ragell.  The MailGem, Redcloth, Hprokot, Kirk, and they all kind of  make use of it.  So just really quickly, what does Ragell look like before we  jump into it?  It's this DSL.  You can kind of define some actions.  And then you've got some ways of converting different  terms into other terms.  So that's kind of what it looks like.  And we'll get into the details here shortly.  So most people are familiar with regular expressions.  Regular expressions are easy, for the most part.  People understand them.  It's kind of the basic stuff that we all understand.  Matching, grouping, alternation, matching zero, one or  more, n times, n times, et cetera.  Ruby has really great tools for regular expressions, because  it has a heritage from Perl, Zed and Ock, which relied  heavily on this.  So you can do fancy things like match stuff and in a block,  match some more stuff and in a block replace something that's  three regular expressions down.  So you can get pretty fancy with them.  But at some point, they can become  irregular expressions.  So if you've ever opened up a file and stared at something  like this, then Rachel might be something worth  considering for you.  They have their place, but there are better tools.  Sometimes you want more control.  And I posit that this means you want some sort of automaton.  So just a little bit about automatons.  Like finite automata, they're basically these devices.  They have states and transitions.  Many people have probably seen these.  You've got circles and arrows.  And some input comes in causing a transition to another state.  There are two basic types.  There's a deterministic finite automata  and non-deterministic finite automata.  It's just an academic distinction.  Deterministic means it can just be in one state at a time.  Non-deterministic means you can be simultaneously  in two different states.  However, you could map those multiple states as super states  and the single states and convert that  into a deterministic finite automata.  So in academia, they talk about this equivalence  of regular expressions and a phase of TFA.  So all this stuff that you're doing with crazy regular  expressions, you can kind of do with these other tools.  So you should choose the tool that kind of makes the job  easiest for you at that point in time.  So as a superset, these are all state machines.  State machines are an important tool in computer programming.  Ragell is a wonderful tool for creating them.  And state machines are everywhere.  And they're in your stoplight.  You have green, the timer goes to yellow, goes to red,  goes to green, goes to yellow, goes to red,  goes to green, around and around forever.  They run your CPU.  If you imagine your computer, like every single bit that's  in it, as kind of a definition of a state,  then every piece of input causes it to transition  to another state, your computer is one gigantic state machine.  There's some kind of non-state machine stuff  that happens on the edge when inputs come in asynchronously  and stuff, but for the most part,  you can take it a bit like that.  It's a big working state machine.  And there's other examples everywhere.  So I watch it as vending machines.  I've mentioned traffic lights already.  Park code scanners.  Pretty much any piece of machinery these days that  isn't analog has any kind of computing domain  so it's going to be a state machine or something.  So I think they're the cat's meow.  I think they're great for many reasons.  They're simple to understand.  And there's a great deal of research around finite automaton  state machines.  With the right approach, they can also  produce code that is faster, easier to maintain, and more  correct, and thus most secure.  They're very specific about what inputs are accepted  and what aren't.  And it's harder to get it to parse something correctly  than it is for it to admit something that doesn't parse,  which could be very useful.  If you're still not convinced, we should probably just  spend some time looking at what they're.  So let's go over some vocabulary.  So state machines, they all have something  called a start state.  It's usually designated S0.  This is as it sounds like the first state  that those state machines start to.  They also have on the other side an accept state  or a final state.  They can have multiples of these, just  depending on what they are.  When the machine transitions to this state,  it is said to have accepted the string.  So within a state machine, to go from state one to state two,  in this case, when an H is received,  you go from state one to state two.  It's called a transition.  It's usually an arrow in a diagram that's  labeled with an arrow.  Sorry, it's an arrow in a slit.  There's a special kind of transition  called an epsilon transition.  This allows you to go from one state to another  without taking any input.  So this can be useful to wire like the up.  You could take two state machines, stick them together,  and basically it works like a concatenation,  like you don't need input to go from one to the next.  So with what we know so far, we've  got a couple of simple state machines that we can build.  Like if you think about a regular expression and how  it's parsing things, this is kind of what it looks like.  So A star will take any number of As  and just kind of keep mapping on it  as long as the first one was an A.  The second machine just maps a single A and then you're done.  This next one needs an A, and then as many As  and as one after that point.  So that's A plus.  And from that, we can get more complicated.  So this is a machine that will match zero or more hellos.  So the start state is actually a final state,  so that's acceptable.  But once we've taken an H, we need an ELLO  before we can get back to a final state again.  So whenever this is in a final state,  it's accepting the input.  So you may be asking, what's the big deal?  I mean, these just look like regular expressions.  I've done this before.  I don't really need this.  So what is Rachel exactly?  Rachel is a finite state machine compiler  with output support for C, C plus plus, C sharp,  objective C, D, Java, O, Camel, Go, and Ruby.  So if you're doing stuff across projects,  it's really useful.  It also supports a generation of several different ways  of working its way around the states.  And it's really useful for building electrical analyzers  and protocol definitions, et cetera.  So I talked about state machine generation.  So another unique feature of it is that with these states  and with these transitions, you can attach arbitrary code  at any point in time.  So as you're moving around the state machine,  you can pull things in and out of the input  and jump around in the state machine.  And these are the features of Rachel  that make it really different than just a regular expression.  The regular expression, you can match a string where you can't.  With Rachel, you can match half the string,  jump to the end of the string, do some stuff,  jump to the beginning of the string, give it some more data,  download something, upload it to YouTube, and come back.  You can do that all inside Rachel if you want to.  I'm not sure I would recommend that.  So I'm actually wasn't sure how to pronounce it.  I've been saying to Rachel forever.  Rachel, there's a regal, there's Rajul,  there's a bunch of different ways to do it.  So you can get the answer from the horse's mouth,  because Adrian Thurston had created it, actually,  I guess sent an email.  It's fine.  And he said that it's actually Rajul, which is not at all,  how I guessed.  He said it was based on his R and L for regular language,  and his nickname was Aj, even though he's Adrian or age.  So maybe it's Rachel, maybe it's Rajul.  If he's age, it would be Rajul, but he wrote Rajul.  So I still don't know that.  But the female, please let me know.  So darn, I've been pronouncing it wrong for quite some time.  So on a more basic level, Rachel is a DSL for creating  these state machines.  And it's especially useful, as I mentioned,  for parsing protocols, data formats.  It's incredibly powerful.  It allows you to do this in sort of a EBNF kind of format.  So you get this really declarative approach  to parsing text as opposed to kind of while loops  and for loops and function calls and returns.  So let's just take a look at the DSL.  I've got a better idea.  So the general structure of a Rachel file  it'll be written in the host language.  So if you're in Ruby, it'll be mostly Ruby.  And I'll have some sections in there  which kind of call out pieces that are Rachel.  So this is a machine which matches Fuba.  You can name several machines and refer to them inside your file.  There are definitions and instantiations.  So this defines a piece of state machine that you can use  and you can compose it into a bigger state machine.  And to actually generate states,  you need to have an instantiation of some sort.  This is done with colon equals.  And like any kind of programming system,  you can include and import and do things like that.  There's some slight semantic differences in terms  of what those mean.  So you can refer to the manual for more details.  White space is ignored.  Coddles are started with a pound just like in Ruby.  There's different kinds of literals.  There are string literals, regular expression literals,  grouping literals.  Got kind of standard escape characters  that we're familiar with.  And if you need to jump, if you're inside a Rachel section,  you need to jump out to the host language.  You've got to put it inside braces like this.  Numbers can be specified as either integers or hexadecimal,  which is useful because when you're parsing in Rachel,  you're actually looking at the binary value.  So if you're looking at an A, it's actually a capital A.  It's actually 65.  So you'd be aware of that.  You know, it's got a couple of keywords.  So these are kind of first section here.  This is the stuff that is more like a regular expression.  So this matches the word simple.  So nothing too fancy there.  We're going to have unix expressions  similar to regular expressions.  We have zero-linked matches.  We have numerical literals, as I mentioned before.  Like this is matching 42.  So this would be the ASCII character  represented by the number 42.  And you can have regular expressions inside Rachel,  which could be a little bit line-bending.  But regular expressions actually compile down  into state machines.  So this is actually pretty obvious when you think about it.  We have range expressions.  So if we want to match A to Z, same as regular expression, A to Z.  This is where we kind of start to jump out  of what you can do in regular expression.  Here you can kind of name something called secret code  and refer to it in a different place  inside the regular expression.  So you can name it once and it will use it in five or six  different places.  And there are a bunch of sort of built-in character classes.  Any ASCII extend, printable and control graph.  So for basic stuff, you can just reach to one of these.  You don't have to define it all in front of you.  So at this point, we sort of have the basic building.  Blocks for building were complicated machines.  These are like levers, wedges, wheels, pulleys.  These are like the simple machines  that mankind has built.  And on top of that, we built rocket ships and got to the boom.  So that's what we're going to do next.  Here's another cat picture.  So when I was first learning about Ragell,  I kind of heard it was useful.  I wasn't quite sure why.  I was reading through the user manual.  That's like, if you really want to understand how it works,  that's the best way to do it.  There's a really good PDF online about that.  But it has this really interesting thing  where you can take a really complex machine  and add it to another machine or subtract it  or do an intersection or a difference or a union.  And it will do the math to kind of add and subtract the state  so that it does what you expect.  This is kind of my blog when you see it in process.  Compositional operators are the things  I just mentioned, union, intersection, difference,  strong difference, concatenation, things like that.  And we'll go and check in detail in a second here.  So a union, you would take, this string up top  could be matching, this could have 1,000 states in it,  and one on the bottom could have 1,000 states in it.  The state machine will traverse both machines  at the same time and enter a final state.  But it does this by adding to get all the states  and lining up the final results.  Sorry, the final states inside it.  I'm going to bug in my slide here,  so my union example is a charm.  We have an intersection.  So that matches any string that would be in both machines.  So this is an example of that.  It's taken a machine on the left here and a machine  on the right, and it merges them together  into kind of one mega machine.  So we can do a difference.  So this would take any string, the first machine matches,  minus any string in the second machine matches.  This is the state machine that you get from that expression.  So as you can see, it's pretty complicated.  Coming up with that yourself would  be a mess in trying to do that code.  We'll probably do that.  But it's actually pretty simple here in the DSL.  You have a notion of a strong difference.  This will match any string in the first machine.  Sorry, any string of the first machine  that does not have any string of the second machine  has a substring.  So one example would be I want to match any character  except control character-turned-line feed.  Character-turned-line feed is a compound string.  So concatenation.  And this is just taking the epsilon states out of one machine.  Setting up epsilon states which come out  of the final states of the first machine  into the second machine creates a global machine.  Concatenation example.  And you have other things that relate to regular expressions  like the play star.  So this is A back, more basic repetition.  We've got the optional operator, optional example.  So this would admit any string that the machine doesn't match.  Negation example.  Sorry, I'll give you a second.  Special form of character-level negation.  If you just need to get negated on a single character,  there's a special operator for that one.  It's this.  When you go through the work of putting these machines together  and feeding them into Rachel, it does a kind of final process  called state machine minimization, where it does  some optimizations of the states within the state machine.  And at any of them that are redundant, it can kind of subtract out.  So you may initially have 1,000 states that you kind of added together  that could subtract it down to like 250 equipment.  So I mentioned before, like one of the powerful things you can do  with Rachel is attach user actions to different parts  inside the state machine.  So this is some examples how you would do that.  You can define an action statement inside the DSL  and then attach them to the transitions.  So there are different kinds of transitions.  There are entering transitions, so I'm going into a state.  You can attach there.  You can attach to a finishing transition, which is coming out of state.  You can attach to every single transition,  or you can attach to just the leaving transition.  And you would do this, you would choose based on kind of what you're doing  which one of these you want to do.  And the embedding operators can get really fancy.  There's like two or three pages in the manual about how to do this.  So if you need any details, just suggest you check there.  One of the problems you can come up with is this notion of non-determinism.  So you may have two machines that are stuck together,  and you can't get out of the first state to match on the beginning of the second,  or you can't get out of the first machine to match on the beginning of the second machine  because they're matching the same characters.  So an example would be this machine here.  So the new line in white space will prevent the final new line from matching.  So the solution is to exclude it from the beginning.  There's also ambiguity problems.  Like if you're trying to match, if you're trying to match like a C comment, for example,  you might say, okay, match slash star, give me anything and then give me slash star.  But you'll never match the slash star because you're matching on any.  And you can do things like, okay, match on anything except slash star  and kind of add things together like this, but that gets up late.  Rachel fortunately gives us some tools that are easier to reason about,  so you don't have to kind of do the suckling stuff.  The way it does this is it allows you to set priorities on the states.  So you could say that I want the transitions like going to the second machine  to have higher priority.  So one of the techniques it gives you is a special notation called guarded operations.  And these are called guarding concatenations.  So an example of the one we just looked at, how do I match, say, on a C comment?  When you use this kind of colon greater, greater, this causes the slash star  and this final machine to match more strongly.  So I'm going to match on any as long as it's not a star slash and then it'll kind of come out of the machine.  So we've got, there's a couple of different forms of that,  whether like the right machine is stronger or the left machine is stronger.  Or if you want a longer smash, but you don't want to kind of stay inside it.  So one of the things that you, so that's kind of for simple matching,  but a lot of times we're trying to build a scanner.  We want to scan a file and we just want to recognize tokens in it,  like one after another, after another, after another, have it keep going.  So Rachel has a notion of a scanner and this will keep matching on the input  and it will take the longest match that it can and recognize that time after time.  So an example of that right here would be like, so if you're kind of like, this is like parsing headers.  So right here we're saying a header, like within a header, I can match out a word, a space, or a new line,  and this is what I'm going to do for each of those.  So it's going to keep matching on word.  There's a space that's going to ignore it.  And then it's going to effort her which is actually kind of coming back to work on F call.  So as I mentioned, it's really useful for protocol parsing.  This is what ZXA did and that's what Puma uses it for.  So if you want like a good detailed example, kind of like parse HTTP using Rachel Puma, I think is the best resource.  And up to this point, we kind of been thinking sort of on the level of regular expressions,  but on a lower level, these are just states and transitions and Rachel actually lets you kind of go down  into what it calls the assembly language of state machines, which is just saying,  I want these states, I want these transitions, I want these characters to go from one to the next.  So you can also define those.  So this is an example of parsing XMLC data body.  So this actually defines three states, start one and two, and some of the transitions based on what it's matching to go from one state to the next.  And you can use F call and F return to kind of set up function calls within Rachel, which is useful as well.  When you start parsing stuff, the Rachel, you're probably going to reach for it.  Like instead of running a scanner or Alexa, you're going to say, oh, maybe I can use Rachel.  One of the problems with it is parsing recursive structures.  Regular expressions are not good for that and Rachel's equivalent to a regular expression more or less.  So how can you do that?  The trick is to take advantage of these actions that you can embed and when you recognize within your pars that you are looking at a sort of a nested construct,  you can, in your host language, set up like a stack and push a context to that and jump out and jump back and look at your stack when you need to.  So because you've got these embedded actions, you can like step outside of what regular expressions allow.  You can also implement look ahead.  So the trick here is you would match on a couple of characters farther than you want and then you can call F hold, which will kind of back the parser up.  So each time you call it backs it up one character.  So internally, when you're working with Rachel, it has all these, it has these variables that you're going to interact with and they represent the state.  So there's data, which is a buffer, which is where you kind of store your strength.  So we'll see in a second here, like when you call Rachel, you basically set up data in a buffer.  You set a variable called P, which points to the front of the data, PE, which points to the end.  And then you just tell Rachel to go and it'll match on everything between P and PE.  When more data comes in, you come and tack it on to the end, move P and PE and tell it to go again.  So if you want to match one character at a time, you can just line up P and PE and it's kind of moving them all.  And when you're inside a scanner, it actually uses some other variables TS and TE because it's, in order to do the scanning and do a longest match,  it actually looks ahead and stores some state on its stack and backtracks what it needs to.  So roughly, you know, you start at state zero, you feed it data.  It runs the exact loop. The characters move through the state. You consume its P to PE data.  And it's done, if your current state matches a final state, which gives you a list of them, it means you've admitted the string.  For scanners, it's similar except it uses TS, TE and the stack.  The way you extract a string, when you're...  So this is like, as you're moving through the scanner, like you'll use this kind of slash mark that marks the beginning of something you're interested in.  And this percent will say like, I'm leaving the transition. That's what I want to admit.  So when I enter, I store where I was. So data P. And then when I leave, I store data P.  I store from my mark to my PE. I pull that out and I store it into my things or A, for example.  As I mentioned, there's a bunch of different post-language, languages and coding styles.  One of the nice things you can do with Ragell is you can write a generic parser and just refer to all these actions by name.  And you can have multiple other files that you would include.  So I could have one definition of HTTP.  And then my actions, I could have my actions defined in C and the actions defined in Java.  And that's actually what Pima does.  You can also prototype something in Ruby, get it working how you want, and then go convert it to C pretty easily,  because you have both of your logic inside Ragell.  So the director is that you need to put in your file or in a net, which sets up quite well the state.  Data, which has all the states and transitions.  And exec is actually, causes it to run that loop that I was describing.  So this is an example of some of the code that it generates.  So installing it on a Mac is really simple.  Just brew install Ragell.  And to generate the Ruby from a Ragell file, you just say Ragell-R for Ruby.  Simple.rl would be the Ragell file in this example, and you give it the output.  So this will build your Ruby file.  We'll take a look at it in a second.  And debugging these things, it's kind of hard to do visually, or it can't be hard to do visually.  So Ragell actually lets you emit these out to a graphis.file, which you can then kind of make an SVG or a PNG out of  and kind of look at all the states.  So I'll show you in a second.  So this is an example of calling it from Ruby.  So this would parse the data.  So we take the data, we have to unpack it into the binary format that I mentioned from characters.  We set the EOF as a variable that Ragell uses to know when it gets to the end.  Tokens is our variable where we're storing things.  Calling it, calling it exact, and that's going to process everything that you put inside data.  So somewhere in the actions, it's actually pulling things out and storing them, and the tokens are right here.  So I created a tool here for kind of doing some visualization.  I just want to pull it up and figure out how to get onto the screen.  Can you see that?  I actually can't see it, so I'm going to turn around here.  That's done.  I'll just mirror the displays, right?  Where is my cursor?  Okay.  Where did it go?  I want to still end over here.  So this is actually a little app that I built in Vault,  which is a pretty cool framework.  You guys haven't used Vault, so you can go to check.  But it allows me to experiment here and see what these graphs are.  So normally to build these, I would have to run a couple of command line commands,  but I just set it up in here so I can do stuff like this.  So I've got examples of the different machines in here.  So this is a machine that matches on a simple...  I don't update.  So this is an example of the state machines that are being created by this.  So if I want to match on sim or PLD, it would look like that.  Or if I want to zero more of those.  Let's say I wanted one more of those.  So I can kind of build these things up and play with it.  I have the code for this referenced here.  So this is a presentation.  That's a guarantee.  So if I want to create a new machine here,  so I'll just call this the machine.  Let's take a look at some examples here.  Everybody see that?  So this is an example of the machine...  Well, it's like the machine I showed earlier where it was matching on...  This is the machine I showed earlier. It's matching on zero more of those.  So I've set up sort of a regional parser base here.  I'll actually take a look at that.  So in parser base, I have...  I'm setting up some variables manually here.  I have a way of feeding it data.  I have a way of asking if I'm in a final state.  I have a way of pulling out the current match.  And I just sort of have it...  I have a way of feeding data here which I'll show you in a second.  But I just have this set up so that I can read from standard A  and so I can use it for experimentation.  So this is a hello...  This is hello parser.  This is what the file you work with looks like.  And then we take a look at the generated file.  Oops, sorry.  Hello.rb.  So this is the generated file.  And Rachel is doing all this work for you.  So this is setting up all the states up top here.  This is a pretty simple state machine.  So there's not much going on here.  But this is the init that we saw.  This is the perform method.  And this is the exact that was buried inside of it.  So it's setting up all the states.  It's doing go-tos and jumps and matches and et cetera.  So all this really nasty code which is heavily optimized.  So that's why it's so fast.  So this particular example here...  So that's the result of this.  And this is a pretty simple state machine.  So I'm going to run this one out in a second.  Okay.  So...  Okay.  Okay.  Okay.  Okay.  Okay.  Okay.  Okay.  Okay.  One small more.  Let's try the next one.  Oh, that's coming to that one as well.  So I typed h.  You can kind of see that it's in current state one now.  p is at one and pe is at one.  And we have one piece of data at h.  I say e, l, l.  Our final state here at the bottom is still false.  So we're not in a final state.  We press o.  We've now entered a final state.  So we've matched on hello.  And I press h again and we're not matching.  e, l, l.  But if I press any other character,  I'm going to step outside of what it knows.  So I'm now in an error state.  I'll never match again.  So I'm going to do a basic example.  I have some arg parsers defined here.  So there's, I mentioned state charts and not using state charts.  So I've one defined here using sort of standard approach.  So this is the main part of my parser.  And I'm just saying I want to match on an arg dash and flags or dash dash long opt.  Long opt.  I have defined as a bunch of alphas.  So it would be a bunch of alphas as well.  And what this is going to do is this parser is going to go around,  around on a loop and when it sees some dash dash long opt,  it's going to call saw long opt.  So the Ruby code is actually pretty simple there.  And these are the actions up here.  So I call mark arg when it took out a mark just out of it.  Oh really? Can't see no.  How do I change the color?  Yeah, it's going to do.  How do I do that?  What's that?  You're going to get a lot of changes when you have a prediction to be working on this.  Okay.  Where's my system preferences?  Accessibility?  Accessibility?  There you go.  Is that more legible?  Yeah.  Okay.  So what I'm doing here in the code is when an alpha is matched for its first time,  I'm kind of marking the beginning of the argument,  marking the beginning of the flags, marking the long arms.  And then when I get to saw arg, which is what the scanner calls,  I'll use that previously marked thing to kind of pull out what was there.  Well, that's freaky.  So now I'll see if the math should be in the way.  So I can do dash A S D F.  And see it.  And I'll put in flags A S D F so that means I'm not showing that there.  So now I can do like a long one.  I can just say a long opt.  So I matched on long opt.  So that's just an example kind of doing basic argument parsing there.  And then I have an example of this in the sort of state chart for as well.  So state chart is a little bit more complicated.  When you draw it out of paper, it's simple and you can actually do the dot biz visualization of this as well.  But I start and I start state here.  If I see a dash, I'll go to preflag.  If I see a quote, I'll jump to quoted value.  And if I see anything else, I'm going to kind of start a value arc.  So as an example, this is what I'm calling.  Valar is just kind of a word, quoted V, could be a quoted word.  Flags would be this and like a long, long flag would be that.  So the basic idea here is that you create some buffers and as you match or kind of go around in a circle in a state,  I'll keep it pending to that buffer.  And then when I leave the state, I'll admit what I want, looking up what I've stored.  And sorry, the Ruby code for this again is very simple.  Most of them is being done up inside the parser.  So as an example, the same thing, but I can say, you know, ASDF and then Valar and I got a Valar.  I can say quote, quote V and I got a quoted value.  Space brings me back to start.  I can say dash dash long equals, I got a long quote, quoted, and I got a quoted.  So I have links to all those codes.  So after the presentation, you guys want to like pull it up and kind of like dig through here to figure out what's going on.  It's in there.  Let me go back to the presentation here.  I can find it in this color.  In Invert.  I can find it in this color.  The presentation is closed.  So while I'm looking for this, does anyone have any questions?  I'm not familiar with what, so TreeTop is all in Ruby, right?  Yeah, so TreeTop is, it may be similar, like presumably they may be doing kind of similar techniques under the covers.  I'm not super familiar with how TreeTop does things, but this is like super highly optimized.  Like for the C version, it can actually, actually one of the versions compiles it down into just jumps within a while.  So like it'll go to the bottom, it'll go to, it'll go to, it'll go to, it'll go to, it's almost like optimized assembly.  So I'd be surprised if it wasn't faster, but it probably really depends on these things.  No, definitely.  It allows you to, it allows you to do the chunking.  So you can kind of think about your problem in smaller pieces and unit test those and then compose them together.  So as I mentioned, the composition is, like it's two main things that make it really cool.  The composition is one of them.  Like that's kind of mind blowing.  And then the fact that you've got these actions.  So I can not be in a programming language and then suddenly be in a programming language.  Okay.  Right, right.  Yeah, I mean, if you're, if there's treat up to other languages as well.  Okay.  Yeah, so if you, if you were writing an HTTP parser, you wanted it to work like, you know, quickly on J Ruby.  So you wanted it down in Java and also like in C Ruby.  So you wanted it down in C.  This would be a good choice.  Right.  Yeah.  So the question is like, how do you know this is using instance variables and kind of local variables.  And so how would you like turn this into kind of like a composable unit?  Yeah, so that's, that's actually kind of what I, what I tried to demonstrate here.  So I created this regional parser base and I have, I have several parses which kind of inherit from it.  The default is to use local variables, which obviously it's kind of painful.  Part of the DSL, you probably can't see it again.  So we invert this.  Yeah.  So this is, since I, it depends on where you put these, it depends on where you put like these things.  So right, I put these inside this object that I've created.  So when it, when it refers to app, it's going to be in the context of this object inside the context of this method.  And you can remap what it does.  So normally it'll just refer to P. I have a referring to app P because I set up the stuff up here.  Oh, hey, there it is.  So I showed the demos.  That was it.  So I've got these resources here.  I have the slides up and I've got the, I got the playground code up there.  I had some other features I wanted to add to it, but I kind of ran out of time.  So I hope that was useful.  Sorry if I drowned on.  Yeah.
Stately_State_Machines_with_Ragel_0_71.png Stately_State_Machines_with_Ragel_72_371.png Stately_State_Machines_with_Ragel_372_1307.png Stately_State_Machines_with_Ragel_1308_2219.png Stately_State_Machines_with_Ragel_2220_2363.png Stately_State_Machines_with_Ragel_2364_2423.png Stately_State_Machines_with_Ragel_2424_2483.png Stately_State_Machines_with_Ragel_2484_3083.png Stately_State_Machines_with_Ragel_3084_3191.png Stately_State_Machines_with_Ragel_3192_4295.png Stately_State_Machines_with_Ragel_4296_6323.png Stately_State_Machines_with_Ragel_6324_8927.png Stately_State_Machines_with_Ragel_8928_9491.png Stately_State_Machines_with_Ragel_9492_10499.png Stately_State_Machines_with_Ragel_10500_13247.png Stately_State_Machines_with_Ragel_13248_19019.png Stately_State_Machines_with_Ragel_19020_21227.png Stately_State_Machines_with_Ragel_21228_25283.png Stately_State_Machines_with_Ragel_25284_25787.png Stately_State_Machines_with_Ragel_25788_27491.png Stately_State_Machines_with_Ragel_27492_28283.png Stately_State_Machines_with_Ragel_28284_29099.png Stately_State_Machines_with_Ragel_29100_29303.png Stately_State_Machines_with_Ragel_29304_30431.png Stately_State_Machines_with_Ragel_30432_31811.png Stately_State_Machines_with_Ragel_31812_35735.png Stately_State_Machines_with_Ragel_35736_37007.png Stately_State_Machines_with_Ragel_37008_37067.png Stately_State_Machines_with_Ragel_37068_38363.png Stately_State_Machines_with_Ragel_38364_40403.png Stately_State_Machines_with_Ragel_40404_41351.png Stately_State_Machines_with_Ragel_41352_43367.png Stately_State_Machines_with_Ragel_43368_43511.png Stately_State_Machines_with_Ragel_43512_44207.png Stately_State_Machines_with_Ragel_44208_44543.png Stately_State_Machines_with_Ragel_44544_46703.png Stately_State_Machines_with_Ragel_46704_46859.png Stately_State_Machines_with_Ragel_46860_46967.png Stately_State_Machines_with_Ragel_46968_47687.png Stately_State_Machines_with_Ragel_47688_48551.png Stately_State_Machines_with_Ragel_48552_48707.png Stately_State_Machines_with_Ragel_48708_51479.png Stately_State_Machines_with_Ragel_51480_52235.png Stately_State_Machines_with_Ragel_52236_52655.png Stately_State_Machines_with_Ragel_52656_54575.png Stately_State_Machines_with_Ragel_54576_54719.png Stately_State_Machines_with_Ragel_54720_55739.png Stately_State_Machines_with_Ragel_55740_57071.png Stately_State_Machines_with_Ragel_57072_57431.png Stately_State_Machines_with_Ragel_57432_57539.png Stately_State_Machines_with_Ragel_57540_58103.png Stately_State_Machines_with_Ragel_58104_61319.png Stately_State_Machines_with_Ragel_61320_61787.png Stately_State_Machines_with_Ragel_61788_62171.png Stately_State_Machines_with_Ragel_62172_62783.png Stately_State_Machines_with_Ragel_62784_62843.png Stately_State_Machines_with_Ragel_62844_63407.png Stately_State_Machines_with_Ragel_63408_63748.png