4 ms·

Mongrel 2 Routing And The Magnetic Bikeshed

43 points by mattyb 16y ago

silentbicycle 16y ago
The Lua pattern-matching code he mentions is here (http://www.lua.org/source/5.1/lstrlib.c.html#match http://www.lua.org/source/5.1/lstrlib.c.html#match). You can browse the overall source (http://www.lua.org/source/5.1/ http://www.lua.org/source/5.1/) online, too. The Lua standard string library includes a minimalistic regex implementation - it doesn't have full REs because the implementation would probably be larger than the rest of Lua (!). For situations where you're better off with a real parser and not just REs, LPEG (http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html) is available as a library. It's a bit different from both REs and LL(k) / LALR(k) parser generators (it's a PEG variant), but works quite well in my experience - while designed with parsing in mind, it scales down quite nicely to typical RE string stuff.
- deleted 16y ago
  [deleted]
drivingmenuts 16y ago
I love this line: "I find the average programmer's lack of understanding of the TST data structure and its variants maddening." The average programmer is a coal-shoveler, moving data from a hopper to furnace all day long. Most of the programmers I have met haven't had to do a binary tree since college and wouldn't know a ternary tree if it was growing in their garden. As for parsers ... yeah, not even. I imagine they're not terribly difficult to write, but I don't know anyone who's even remotely interested in it.
- augustl 16y ago
  If there was a book explaining not only the basics but also the purpose of and why I should care about binary trees, TSTs, bitwise operations etc., I'd buy it. Twice! I am a self taught web app programmer and I'm having a hard time wrapping my mind around these kinds of things.
  - scott_s 16y ago
    Look at the textbooks used in data structure courses at various schools.
    - deleted 16y ago
      [deleted]
  - stcredzero 16y ago
    The post gives you a hint as to why: it can make you a more powerful programmer by giving you access to more powerful tools in certain specific contexts.
  - jerf 16y ago
    I think the perfect complement to a self-taught web programmer is something like SICP. (Google knows what that acronym is.) I'm actually not necessarily an "SICP lover", I don't think it's perfect, I just think it's pretty much the perfect complement to a self-taught web programmer.
  - silentbicycle 16y ago
    Okasaki's _Purely Functional Data Structures_ and CLRS (http://www.google.com/#q=0262032937&fp=1 http://www.google.com/#q=0262032937&fp=1) are a great start. Also: Learn OCaml. Data structures will make so much sense.
- barrkel 16y ago
  Parsers: the trouble is, once you've learned how to consume and dispatch actions based on recursive data (this is the essence of parsing, and in many ways is also the essence of Lisp) you start seeing it as a potentially more optimal - in both design and algorithmic complexity - solution to all sorts of problems. I could make the argument that navigating a trie while consuming the search string is an exercise in parsing over a grammar defined by the trie structure. The grammar is regular though, without cycles in the trie.
- mkramlich 16y ago
  Most programmers never have the need to know about a ternary tree. We can often get by thinking at most in terms of lists, sets, tuples, dictionaries, arrays, etc.
  - silentbicycle 16y ago
    Skiplists are at a sweet spot, too - simple and easy to remember, but in the same ballpark as red-black trees. (not functional/persistent, though)
amalcon 16y ago
So long as he's apparently requesting this sort of thing, why not use a Patricia trie instead of a TST? Typical use-cases would probably yield a lot of single-child nodes in a TST, which a Patricia trie would eliminate. There would probably be a good amount of memory savings, and the only additional code complexity would be a strcmp() (edit: which doesn't increase the algorithmic complexity, since you'd be doing those comparisons anyway). Using a TST is probably fine; it just looks like this problem cries out for a Patricia trie.
deleted 16y ago
[deleted]

43 points by mattyb 16y ago

The Lua pattern-matching code he mentions is here (http://www.lua.org/source/5.1/lstrlib.c.html#match http://www.lua.org/source/5.1/lstrlib.c.html#match). You can browse the overall source (http://www.lua.org/source/5.1/ http://www.lua.org/source/5.1/) online, too. The Lua standard string library includes a minimalistic regex implementation - it doesn't have full REs because the implementation would probably be larger than the rest of Lua (!). For situations where you're better off with a real parser and not just REs, LPEG (http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html) is available as a library. It's a bit different from both REs and LL(k) / LALR(k) parser generators (it's a PEG variant), but works quite well in my experience - while designed with parsing in mind, it scales down quite nicely to typical RE string stuff.

deleted 16y ago
[deleted]

drivingmenuts 16y ago

I love this line: "I find the average programmer's lack of understanding of the TST data structure and its variants maddening." The average programmer is a coal-shoveler, moving data from a hopper to furnace all day long. Most of the programmers I have met haven't had to do a binary tree since college and wouldn't know a ternary tree if it was growing in their garden. As for parsers ... yeah, not even. I imagine they're not terribly difficult to write, but I don't know anyone who's even remotely interested in it.

augustl 16y ago
If there was a book explaining not only the basics but also the purpose of and why I should care about binary trees, TSTs, bitwise operations etc., I'd buy it. Twice! I am a self taught web app programmer and I'm having a hard time wrapping my mind around these kinds of things.
- scott_s 16y ago
  Look at the textbooks used in data structure courses at various schools.
  - deleted 16y ago
    [deleted]
- stcredzero 16y ago
  The post gives you a hint as to why: it can make you a more powerful programmer by giving you access to more powerful tools in certain specific contexts.
- jerf 16y ago
  I think the perfect complement to a self-taught web programmer is something like SICP. (Google knows what that acronym is.) I'm actually not necessarily an "SICP lover", I don't think it's perfect, I just think it's pretty much the perfect complement to a self-taught web programmer.
- silentbicycle 16y ago
  Okasaki's _Purely Functional Data Structures_ and CLRS (http://www.google.com/#q=0262032937&fp=1 http://www.google.com/#q=0262032937&fp=1) are a great start. Also: Learn OCaml. Data structures will make so much sense.
barrkel 16y ago
Parsers: the trouble is, once you've learned how to consume and dispatch actions based on recursive data (this is the essence of parsing, and in many ways is also the essence of Lisp) you start seeing it as a potentially more optimal - in both design and algorithmic complexity - solution to all sorts of problems. I could make the argument that navigating a trie while consuming the search string is an exercise in parsing over a grammar defined by the trie structure. The grammar is regular though, without cycles in the trie.
mkramlich 16y ago
Most programmers never have the need to know about a ternary tree. We can often get by thinking at most in terms of lists, sets, tuples, dictionaries, arrays, etc.
- silentbicycle 16y ago
  Skiplists are at a sweet spot, too - simple and easy to remember, but in the same ballpark as red-black trees. (not functional/persistent, though)

amalcon 16y ago

So long as he's apparently requesting this sort of thing, why not use a Patricia trie instead of a TST? Typical use-cases would probably yield a lot of single-child nodes in a TST, which a Patricia trie would eliminate. There would probably be a good amount of memory savings, and the only additional code complexity would be a strcmp() (edit: which doesn't increase the algorithmic complexity, since you'd be doing those comparisons anyway). Using a TST is probably fine; it just looks like this problem cries out for a Patricia trie.

deleted 16y ago

[deleted]