News for hackers. Stuff that matters.
Re:The Algebra of Algebraic data types by eru on Thursday June 25, 2015 @03:46AM (#9776476)
(Formal) differentiation also makes sense for grammars, and in particular gives rise to an interesting way to match regular expressions.
Re:The Algebra of Algebraic data types by mafribe on Thursday June 25, 2015 @04:53AM (#9776683)
The paper introducing this concept is [1] but was long forgotten. Recently the use of derivations to implement regular expressions has become popular again, see e.g. [2].

[1] J. A. Brzozowski's, "Derivatives of Regular Expressions", https://dl.acm.org/citation.cfm?id=321249

[2] https://www.cl.cam.ac.uk/~so294/documents/jfp09.pdf

Re:The Algebra of Algebraic data types by sjolsen on Thursday June 25, 2015 @05:02AM (#9776699)
>Recently the use of derivations to implement regular expressions has become popular again

And they're not limited to regular languages; with the right computational tricks (lazy evaluation, coinduction, whatever you want to call it), it can be used with context-free languages in general: http://matt.might.net/papers/might2011derivatives.pdf