5 ms·

I would add "build a toy regex engine" to the list. A couple of years ago I implemented a toy regex engine from scratch (building NFAs then turning them into D

by simias 6y ago

I would add "build a toy regex engine" to the list. A couple of years ago I implemented a toy regex engine from scratch (building NFAs then turning them into DFAs). I thought it was an enlightening experience because it showed me that the core principles behind regular languages are fairly simple, although you could spend years optimizing and improving your implementation. How do you deal with unicode? How do you modify your implementation to know how many characters you can skip if you don't have a match in order to avoid testing every single position in a file? It demystified the concept of a regex engine for me while at the same time making me realize how impressive the advanced, ultra optimized engines we use and take for granted are.

schoen 6y ago
I really enjoyed taking Ullman's Automata course on Coursera. I found it was great for better appreciating topics like * searching * implementation of automata in electronic circuits * challenges of formal specifications for things like protocols and grammars, as well as for verifying their correctness; implementation strategies for applying these specifications * computability and complexity * programming language theory * history of computer science * LANGSEC arguments in addition to having an austere mathematical beauty.
- theshank 6y ago
  Thank you for sharing this one. I was looking for a course like this! BTW this course is now offered on edx.
  - schoen 6y ago
    Oh, thanks for the update! It looks like the new version is at https://www.edx.org/course/automata-theory https://www.edx.org/course/automata-theory Definitely recommended if you like somewhat dry and mathematical stuff with deep relevance to many areas of computer science. :-)
- psibi 6y ago
  Somehow I found the course very dry (as compared to other coursera course like Dan Grossman's PL course).
  - schoen 6y ago
    I agree that it was quite dry, but the intellectual content was great.
chubot 6y ago
Yeah the "optimize for years" part is interesting... Supposedly the derivatives technique (re-popularized by a 2009 paper) will build a more optimal DFA directly, rather than building the NFA first, converting to DFA, and then optimizing the DFA. I put a bunch of links and quotes about that here, including nascent implementations: http://www.oilshell.org/blog/2020/07/ideas-questions.html http://www.oilshell.org/blog/2020/07/ideas-questions.html Also related: http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html About Unicode, this derivatives project (with video linked in the post) appears to be motivated by Unicode support (though I don't recall exactly why, something about derivatives makes it easier?). https://github.com/MichaelPaddon/epsilon https://github.com/MichaelPaddon/epsilon https://github.com/MichaelPaddon/epsilon/blob/master/epsilon/ucd.py https://github.com/MichaelPaddon/epsilon/blob/master/epsilon... If anyone wants to write a glob engine for https://www.oilshell.org/ https://www.oilshell.org/ let me know :) Right now we use libc but there are a couple reasons why we might have our own (globstar and extended globs) Trivia: extended globs in bash give globs the power of regular expressions, e.g. [[ abcXabcXXabcabc == +(abc|X) ]] ; echo $? 0 where +(abc|X) is equivalent to (abc|X)+ in "normal" regex syntax, and == is very confusingly the fnmatch() operator.
- profquail 6y ago
  I wrote an implementation of this several years back. If you’re interested in the code: https://github.com/jack-pappas/facio/tree/master/Reggie https://github.com/jack-pappas/facio/tree/master/Reggie The derivatives approach makes Unicode support easier since its able to keep the symbols sets for each transition edge (in the DFA) more compact by virtue of supporting negation. If you add in aggressive term-normalization, hash-consing, and an efficient dense-set implementation (all of which I’ve done in my implementation), the derivatives approach can be extremely fast, even when generating the DFA for something like the lexer of a full programming language (in my case, F#).
  - chubot 6y ago
    Very cool! And thanks for the reminder about Unicode. I think supporting union and intersection is also somewhat unique to the derivatives method, and also related? (Although I think there are really 2 derivatives methods: Brzozowski and Antimirov) What happens if you don't do the optimizations? Does the DFA blow up in size, meaning the compile time is large? Or does it make for a slower runtime? I would expect most DFAs to run at about the same speed, unless they are really huge... I'd be interested in any rough ideas about performance, e.g. how fast a realistic lexer+parser is, maybe in lines/ms. It does look like the code is pretty short -- a large part of it is an AVL tree library I guess for hash consing? I'm interested in any downsides of the derivatives technique vs. the NFA->DFA method. I feel like regex compile time shouldn't matter for many applications, and most DFAs will run in the same speed, which only leaves runtime memory usage (or code size for generating F# code like you appear to be doing).
KMag 6y ago
Have a look at RE2 and Russ Cox's paper [0]. I found it particularly elegant the use of a small LRU cache to effectively lazily convert portions of the NFA to a DFA. A fast regex engine is pretty easy to implement, as long as you don't need extensions, particularly backreferences. [0] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
abhgh 6y ago
I agree with this ... I coded a Thompson NFA [1] out of interest a few years ago; definitely recommended as an exercise. [1] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
deleted 6y ago
[deleted]
ignoramous 6y ago
See also this Elevator game: https://play.elevatorsaga.com/ https://play.elevatorsaga.com/

by simias 6y ago

schoen 6y ago

I really enjoyed taking Ullman's Automata course on Coursera. I found it was great for better appreciating topics like * searching * implementation of automata in electronic circuits * challenges of formal specifications for things like protocols and grammars, as well as for verifying their correctness; implementation strategies for applying these specifications * computability and complexity * programming language theory * history of computer science * LANGSEC arguments in addition to having an austere mathematical beauty.

theshank 6y ago
Thank you for sharing this one. I was looking for a course like this! BTW this course is now offered on edx.
- schoen 6y ago
  Oh, thanks for the update! It looks like the new version is at https://www.edx.org/course/automata-theory https://www.edx.org/course/automata-theory Definitely recommended if you like somewhat dry and mathematical stuff with deep relevance to many areas of computer science. :-)
psibi 6y ago
Somehow I found the course very dry (as compared to other coursera course like Dan Grossman's PL course).
- schoen 6y ago
  I agree that it was quite dry, but the intellectual content was great.

chubot 6y ago

Yeah the "optimize for years" part is interesting... Supposedly the derivatives technique (re-popularized by a 2009 paper) will build a more optimal DFA directly, rather than building the NFA first, converting to DFA, and then optimizing the DFA. I put a bunch of links and quotes about that here, including nascent implementations: http://www.oilshell.org/blog/2020/07/ideas-questions.html http://www.oilshell.org/blog/2020/07/ideas-questions.html Also related: http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html About Unicode, this derivatives project (with video linked in the post) appears to be motivated by Unicode support (though I don't recall exactly why, something about derivatives makes it easier?). https://github.com/MichaelPaddon/epsilon https://github.com/MichaelPaddon/epsilon https://github.com/MichaelPaddon/epsilon/blob/master/epsilon/ucd.py https://github.com/MichaelPaddon/epsilon/blob/master/epsilon... If anyone wants to write a glob engine for https://www.oilshell.org/ https://www.oilshell.org/ let me know :) Right now we use libc but there are a couple reasons why we might have our own (globstar and extended globs) Trivia: extended globs in bash give globs the power of regular expressions, e.g. [[ abcXabcXXabcabc == +(abc|X) ]] ; echo $? 0 where +(abc|X) is equivalent to (abc|X)+ in "normal" regex syntax, and == is very confusingly the fnmatch() operator.

profquail 6y ago
I wrote an implementation of this several years back. If you’re interested in the code: https://github.com/jack-pappas/facio/tree/master/Reggie https://github.com/jack-pappas/facio/tree/master/Reggie The derivatives approach makes Unicode support easier since its able to keep the symbols sets for each transition edge (in the DFA) more compact by virtue of supporting negation. If you add in aggressive term-normalization, hash-consing, and an efficient dense-set implementation (all of which I’ve done in my implementation), the derivatives approach can be extremely fast, even when generating the DFA for something like the lexer of a full programming language (in my case, F#).
- chubot 6y ago
  Very cool! And thanks for the reminder about Unicode. I think supporting union and intersection is also somewhat unique to the derivatives method, and also related? (Although I think there are really 2 derivatives methods: Brzozowski and Antimirov) What happens if you don't do the optimizations? Does the DFA blow up in size, meaning the compile time is large? Or does it make for a slower runtime? I would expect most DFAs to run at about the same speed, unless they are really huge... I'd be interested in any rough ideas about performance, e.g. how fast a realistic lexer+parser is, maybe in lines/ms. It does look like the code is pretty short -- a large part of it is an AVL tree library I guess for hash consing? I'm interested in any downsides of the derivatives technique vs. the NFA->DFA method. I feel like regex compile time shouldn't matter for many applications, and most DFAs will run in the same speed, which only leaves runtime memory usage (or code size for generating F# code like you appear to be doing).

KMag 6y ago

Have a look at RE2 and Russ Cox's paper [0]. I found it particularly elegant the use of a small LRU cache to effectively lazily convert portions of the NFA to a DFA. A fast regex engine is pretty easy to implement, as long as you don't need extensions, particularly backreferences. [0] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

abhgh 6y ago

I agree with this ... I coded a Thompson NFA [1] out of interest a few years ago; definitely recommended as an exercise. [1] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

deleted 6y ago

[deleted]

ignoramous 6y ago

See also this Elevator game: https://play.elevatorsaga.com/ https://play.elevatorsaga.com/