3 ms·

Have you got an article where you talk a bit about point #3 - "a mathematical dialect of regular expressions". The words all make sense, but I cannot picture it

by smcl 7y ago

Have you got an article where you talk a bit about point #3 - "a mathematical dialect of regular expressions". The words all make sense, but I cannot picture it :-). Your Oil posts always appear up on lobste.rs shortly after they're posted and I thoroughly enjoy them, but I must have missed a few!

carapace 7y ago
I don't know if this is relevant to what Chubot's doing but Brzozowski’s Derivatives of Regular Expressions are pretty mathy. (Disclosure, I wrote this) http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expres...
- chubot 7y ago
  That's cool -- I have a big page of notes on derivatives and have thought about replacing my usage of re2c with them (re2c being automata-based). One benefit of that is aesthetic -- re2c is a 30K line piece of C code itself. The other benefit is practical -- it would be nice to "hoist" it up to the Oil language level, so shell users can use efficiently compiled regexes. And I filed this issue to try derivatives awhile ago: https://github.com/oilshell/oil/issues/197 https://github.com/oilshell/oil/issues/197 There is a possible performance win, but I'm not sure if it makes sense. If you see anything interesting there I'd love to chat about it! (contact info in profile) ----- What I mean by "math" is either automata-based methods or derivatives. In contrast, Perl-style backtracking engines aren't math. To me, the "magic" of "regular languages" is that they give you non-determinism for free. The equivalence between NFAs and DFAs isn't obvious, and it's useful in practice. I've taken advantage of this free nondeterminism in my huge shell lexer. (See my other reply for details)
  - carapace 7y ago
    I'm enamored of dRE (as I call it) but pragmatically it seems to me you could stick with re2c. I think it's interesting to generalize dRE to general control-flow (not just parsing.) Are you aware of Abstract State Machines? https://en.wikipedia.org/wiki/Abstract_state_machine https://en.wikipedia.org/wiki/Abstract_state_machine
chubot 7y ago
I've discussed related topics but haven't had the chance to address it directly. I'm glad someone is paying attention :) Concretely, the first two links in this post show (old versions of) frontend/lex.py and osh-lex.re2c.h. TODO for me: put up the latest versions, as well as the huge C file with state machines that re2c eventually generates. When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html http://www.oilshell.org/blog/2017/12/17.html It works like this: ( ) frontend/lex.py (a bunch of Python regexes, has some "metaprogramming") -> (+) frontend/lex_gen.py -> ( ) osh-lex.re2c.h (re2c input file) -> (+) re2c -> ( ) osh-lex.h (state machines in C, i.e. DFA as a big switch/goto) where the (+) nodes are compilers, and the ( ) are source code files. The reason I call this "a mathematical dialect" is because the same regular expressions run under Python's re engine (a backtracking engine) and as native code via re2c, an automata-based compiler. If you scroll toward the bottom of this doc there's a useful table: Regex Theory and Practice http://www.oilshell.org/share/05-31-pres.html http://www.oilshell.org/share/05-31-pres.html One side is "Perl-style regexes", which Python's engine is based on. The other side is "regular languages". Regular expressions were always mathematical, but the name got taken over by programmers to mean something different, so I call them "regular languages" or this "mathematical dialect". These articles explain the difference, https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ but they're very long and a lot of people still don't understand the difference. https://news.ycombinator.com/item?id=20311630 https://news.ycombinator.com/item?id=20311630 (which is understandable since it mainly comes up in performance corner cases, and when you want to compile regexes, which most people don't do) I should write about this, but the lexer is one of the more solid pieces of the project. That is, it's "done" for now, and I need help with all the other parts, so I prioritize writing about those parts!!! More lexing posts: http://www.oilshell.org/blog/tags.html?tag=lexing#lexing http://www.oilshell.org/blog/tags.html?tag=lexing#lexing

by smcl 7y ago

carapace 7y ago

I don't know if this is relevant to what Chubot's doing but Brzozowski’s Derivatives of Regular Expressions are pretty mathy. (Disclosure, I wrote this) http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expres...

chubot 7y ago
That's cool -- I have a big page of notes on derivatives and have thought about replacing my usage of re2c with them (re2c being automata-based). One benefit of that is aesthetic -- re2c is a 30K line piece of C code itself. The other benefit is practical -- it would be nice to "hoist" it up to the Oil language level, so shell users can use efficiently compiled regexes. And I filed this issue to try derivatives awhile ago: https://github.com/oilshell/oil/issues/197 https://github.com/oilshell/oil/issues/197 There is a possible performance win, but I'm not sure if it makes sense. If you see anything interesting there I'd love to chat about it! (contact info in profile) ----- What I mean by "math" is either automata-based methods or derivatives. In contrast, Perl-style backtracking engines aren't math. To me, the "magic" of "regular languages" is that they give you non-determinism for free. The equivalence between NFAs and DFAs isn't obvious, and it's useful in practice. I've taken advantage of this free nondeterminism in my huge shell lexer. (See my other reply for details)
- carapace 7y ago
  I'm enamored of dRE (as I call it) but pragmatically it seems to me you could stick with re2c. I think it's interesting to generalize dRE to general control-flow (not just parsing.) Are you aware of Abstract State Machines? https://en.wikipedia.org/wiki/Abstract_state_machine https://en.wikipedia.org/wiki/Abstract_state_machine

chubot 7y ago

I've discussed related topics but haven't had the chance to address it directly. I'm glad someone is paying attention :) Concretely, the first two links in this post show (old versions of) frontend/lex.py and osh-lex.re2c.h. TODO for me: put up the latest versions, as well as the huge C file with state machines that re2c eventually generates. When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html http://www.oilshell.org/blog/2017/12/17.html It works like this: ( ) frontend/lex.py (a bunch of Python regexes, has some "metaprogramming") -> (+) frontend/lex_gen.py -> ( ) osh-lex.re2c.h (re2c input file) -> (+) re2c -> ( ) osh-lex.h (state machines in C, i.e. DFA as a big switch/goto) where the (+) nodes are compilers, and the ( ) are source code files. The reason I call this "a mathematical dialect" is because the same regular expressions run under Python's re engine (a backtracking engine) and as native code via re2c, an automata-based compiler. If you scroll toward the bottom of this doc there's a useful table: Regex Theory and Practice http://www.oilshell.org/share/05-31-pres.html http://www.oilshell.org/share/05-31-pres.html One side is "Perl-style regexes", which Python's engine is based on. The other side is "regular languages". Regular expressions were always mathematical, but the name got taken over by programmers to mean something different, so I call them "regular languages" or this "mathematical dialect". These articles explain the difference, https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ but they're very long and a lot of people still don't understand the difference. https://news.ycombinator.com/item?id=20311630 https://news.ycombinator.com/item?id=20311630 (which is understandable since it mainly comes up in performance corner cases, and when you want to compile regexes, which most people don't do) I should write about this, but the lexer is one of the more solid pieces of the project. That is, it's "done" for now, and I need help with all the other parts, so I prioritize writing about those parts!!! More lexing posts: http://www.oilshell.org/blog/tags.html?tag=lexing#lexing http://www.oilshell.org/blog/tags.html?tag=lexing#lexing