Presentación
Vídeo
Transcripción
Extracto de la transcripción automática del vídeo realizada por YouTube.
- Thank you all for coming to Botany with Bytes. I realize that this is one of the more obscure topics on the Ruby Conference schedule, so I feel like you're absolutely the most adventurous crowd at RubyConf. Right on, good on you. Welcome. This is Botany with Bytes, I'm Lito Nicolai.
So this talk is very simulation and graphics focused. This talk uses the graphics gem. This is a very new gem, still in beta, authored by Ryan Davis, who just walked in here and left. He wrote this to be a very simple, very powerful graphics library. It's based on SDL.
Instead of a game library, where everything is drawn upside down and there's a lot of optimizations for game purposes, this is a visualizations library. So even though it does run very fast, it conforms to usual mathematical conventions, like having your up axis be up, things like that.
If you're interested in how I did any of these simulations, all of the code is done with this library, gem install dash dash pre, for the beta, graphics. And all of the code is on GitHub. I am lito_nico on Twitter, you can find all of my code on GitHub with the same name, lito_nico.
So imagine you are algae. Here're you, an alga. And we'll call you A for alga, that makes sense. And you are going to do what algae do, which is make more algae through a process called mitosis, which is a fancy way of saying cell division. Once you're done, you'll be the proud parent of a baby alga, which we'll call B, for baby.
This process will keep going. You'll keep splitting off, your little baby alga will grow up. So you'll have alga, baby, alga. And so on and so on and so on. Each alga will split, each baby will grow up, and I'm just going to start representing these things with letters so I don't have to keep drawing them.
Alga, alga, baby. Alga, baby, alga, it keeps going. Incidentally, this forms the Fibonacci sequence with the length of each generation, for the same reason breeding rabbits does. You have that same exponentiation effect. So this process was first described by Aristid Lindenmayer, who was a human and not a plant, he was a botanist and he called these systems of generation L-systems, after himself.
They're very simple. They consist of a start, like a single alga, and a set of rules, like one alga becomes an alga and a baby, a baby grows up into a full size alga. So let's talk about computers for a minute. You might recognize this as something that we come across in our day to day computer science lives as a rewriting system.
We know these from the game of life, which rewrites a grid. Each cell gets rewritten based on the structures around it. Or the famous Koch snowflake fractal. Each line gets rewritten with a line segment with a triangle and so on and so on. This is a string rewriting system.
So this is a pretty solid indication that this is a grammar. But what is a grammar? A grammar is what strings, or grids or lines or things, you can do it in any dimension you please, can you make with rules? Those rules can be of any form, whether it's the geometric Vs grid shapes mapped to these cells in the game of life, they can be like our L-systems, you have an alga that is splitting and a baby alga that's growing up.
And that is the definition of a grammar. I know that seems absurdly broad. I'm gonna flip that around to something we're a little more familiar with as programmers. What strings can you match with rules? Like here is a regular expression. What strings does it match? Bet you guys didn't know you were getting a pop quiz, right? (laughs) Don't even worry about it.
So when we talk about grammars, it'd be nice to be able to know where L-systems fit in here, and to organize grammars in a broader context. And to do that, we will use computers to organize our grammars. Now we know regular expressions fairly well, and to implement regular expressions, the only computer you need is a deterministic finite automaton.
It's a fancy name for saying a bunch of states and a bunch of transitions. You don't need any memory, you don't need a stack or a heap or any of that. Just leave that out. Your computer only has to be the states and the transitions between them. Now, with that computer, with all of the computers you can make in that structure, you get every regular expression ever.
You get all of the sets of strings that can be matched with a regular expression, and you call that the regular grammar. So this little box indicates all of the strings that can be matched with regular expressions, with all of the grammars you could make.
But we know from experience that there are grammars outside of those. Like if you have, like me, totally naively, tried to parse HTML with a regular expression, it doesn't happen, because there are structures that exist outside of this small area. There are also finite grammars, which are a subset of regular grammars.
We're going to ignore them. So HTML, you need a stack to parse. You need to keep track of which tags you're inside, because you could have self-similar structures inside those tags that you all parse them the same way, but you also have to remember how far down you've gone.
[ ... ]
Nota: se han omitido las otras 2.406 palabras de la transcripción completa para cumplir con las normas de «uso razonable» de YouTube.