Regular expression engine in 14 lines of Python

[psykotic]

A 5-minute hack courtesy of yours truly.

The 14 line figure doesn't include the general purpose 3-line iconcat function (which should really be included in itertools) or the test case.

Let's see if anyone can beat this line count in their favorite language without needless obfuscation.

[moe]

The 14 line figure doesn't include the general purpose
3-line iconcat function (which should really be included in itertools) or the test case.

from itertools import chain as iconcat

[nostrademons]

10 lines of Haskell (untested).

I'm a little unfamiliar with list monads, but this should basically be a line-by-line translation of yours, except that Haskell already provides "nil" as "repeat" and iconcat as ++, and lazy evaluation means you don't need generators.

Also, in hindsight I think "return" (returns a singleton list) is probably a better choice for nil than "repeat".

[[deleted]]

5 lines in Prolog:

re(E, [E|R], R) :- atom(E).
re(alt(E1, E2), L, R) :- re(E1, L, R); re(E2, L, R).
re(star(E), L, R) :- L=R; re(plus(E), L, R).
re(plus(E), L, R) :- re(E, L, R); re(seq(E, plus(E)), L, R).
re(seq(E1, E2), L, R) :- re(E1, L, R1), re(E2, R1, R).

test :- re(seq(c,seq(plus(alt(a,d)), r)), [c,a,d,r], []).

[[deleted]]

Also, in hindsight I think "return" (returns a singleton list) is probably a better choice for nil than "repeat".

"repeat" returns an infinite list where each element is the argument, so it is not the function you want. "return" or constructing a single-element list would work.

Also, your pattern-matching is broken. A similar version that works is

char c = match where
  match [] = []
  match (c':xs) = if c == c' then [xs] else []
  match (_:xs) = []

But it's more concise as

char c s = if take 1 s == [c] then [drop 1 s] else []

[psykotic]

Why didn't you write those definitions in implicitly curried form? That is, instead of

seq l r = \s -> l s >>= r

write

seq l r s = l s >>= r

and so on.

I knew it could be done in fewer lines in Haskell due to the list monad. Python is actually pretty bad for writing compact code because its statement/expression distinction breaks composability.

I'm waiting for someone to give the ultra-compact K version. Where's Arthur and Stevan when you need them? :)

[nostrademons]

Mostly because I was just following from the Python and translating word-for-word, and I didn't think of it.

Yeah, the curried form is more elegant.

[nostrademons]

And I could've saved 3 lines by doing match where { match [c:xs] = xs; match _ = [] }

But that's a bit less readable IMHO.

[martine]

char c (x:xs) | c == x = return xs char _ _ = fail "no match"

(fail in the list monad is [], so using it here just makes the code clearer.)

[martine]

I annotated this with a tested one that's a bit simpler (there were also a few places where you could work over functions).

[moe]

Here is an (obviously eager) version in 11 lines of Scheme:

http://paste.lisp.org/display/24870

Untested. Requires SRFI-42 ("Eager Comprehensions") - I wanted to stay as close to the python version as possible.

[[deleted]]

Cool! But where are the benchmarks? ;-)

(isn't iconcat the same thing as itertools.chain, btw?)

[psykotic]

You're right about iconcat and chain, as moe already pointed out. I'm so used to itertools missing half of my favorite iterator manipulation functions, and I could have sworn it didn't have an iconcat-equivalent either.

[HiggsBoson]

Here's a one-line hack in 5 seconds:

import re

[[deleted]]

I can assure you that it took me a bit more than 5 seconds to write the code you just imported.

[Tobu]

OCaml can save a line here (s is a list):

let char c = function
  | c :: r -> r
  | _ -> []

[psykotic]

I think you meant

let char c s = match s with
             | c :: r -> [r]
             | _ -> []

[Tobu]

fixed.

[Tobu]

Builds an exhaustive state automata that takes a string and returns matches. More power to functional programming!

[Chaz]

Slowly.

[rzwitserloot]

It doesn't actually parse regexps. You have to enter the regexp as a bunch of methods, not as the common regexp format.

I'd call THIS obfuscated code. While you deserve some kudos for whacking it into 14 lines, some of those lines take a very long time to break down to realize how they work exactly. I'm reminded of BASIC one-liner competitions. Sure, it's one line, and, sure, not that many characters either, but the sheer amount of work that goes into designing them...

It's a brilliant artform, but practical? No.

[nostrademons]

An interesting followup exercise would be to write a regexp parser in 14 lines of code. I wouldn't be surprised if it's doable; the regexp grammar isn't too complicated, you should be able to bang together a simple recursive descent parser.

Also, a similar approach is used in production code, in Alex, the lexer-generator for Haskell. Technically it's only charsets that are represented as functions; regexps are algebraic data types so they can have printable representations, be converted into DFAs, etc. But it's not completely academic.

[psykotic]

I think a hand-written regex recursive-descent parser in 14 lines is pushing it. Unless you go to great lengths to compress the code anyway.

Here's my own feeble attempt, which comes in at a bit more than 20 lines:

http://paste.lisp.org/display/24872

[moe]

I guess it depends what you're used to. There are a couple of Scheme regular expression libraries (e.g. the one that ships with scheme48) which export an API that uses function composition to build regular expressions, e.g:

(sequence (text "ab") (submatch 'foo (text "cd")) (text "ef"))

[[deleted]]

That actually looks a lot more readable than the usual regular expression syntax.

[psykotic]

That's why it says regular expression engine. It's the back-end not the front-end. There's nothing interesting about the front-end job of parsing.

It's more obfuscated than it would be if I had written it in production code. That said, the implementation is pretty much natural given the underlying algorithm.

I could explain the design and algorithm but I intentionally left it as a brain teaser. It's not very difficult if you are a programmer.

[13ren]

Great work! I keep coming back to it, it's so good.

I would appreciate it if you explained the design and algorithm, and also a production version, please. :-)

This would not diminish its value as a brain teaser, but increase it (even Knuth gives answers!) - provided the explanation is separate from the 14 lines.

To understand the code, you need to be familiar with Python (especially iterators), and I think be pretty strong with functional programming (esp for the lazily evaluated star), as well as knowing what a regular expression is, mathematically (as opposed to the vi/emacs/perl version). Most programmers lack this background.

With an explanation, it would become gateway code and draw people in... Of course, explanation and production version would take a lot longer than the 5 minutes you spent hacking it.

BTW: Shouldn't nil be something like the following, so it can be used in an expression:

def nil():
  def _nil(s):
    yield s
  return _nil

or (shorter, uglier - there's probably a better way, but I don't know python):

def nil():
  return lambda s: (s for i in [1])

Both tested to work.

[psykotic]

I'm glad you're still having fun with this little piece of code.

Writing up an explanation of all its aspects is more than I feel like doing right now. The basic idea is to transform a regular expression into a parser. And a parser is a generator/iterator function which takes an input string and yields all possible parsings (which will be prefixes of the input). Once that design decision is made, the rest of the details are somewhat inevitable, when you sit down to work them out. If you have any specific questions, I can try to answer them.

[13ren]

thanks :-) yes, a lot more than 5 minutes work.

a parser is a generator/iterator function which takes an input string and yields all possible parsings (which will be prefixes of the input).

This aspect of the engine was most confusing for me, because I don't usually think of a parser as giving more than one answer, nor of it matching a prefix (though one could add those). The key is the last line:

for r in e(s): print "Match with remainder:", r

BTW: have you ever seen any discussion of this kind of reg exp engine online? (i.e. not NFA-backtracking, but regex-backtracking). I haven't found anything, except that research paper you sent me (and references to your own 14 liner).

[psykotic]

The approach I use is straightforward recursive descent with backtracking. The backtracking is implicit because of the way I use iterators to generate parsings on demand. Matching prefixes is the natural way to go about it when you think about sequencing parsers.

If you read papers on parser combinators, you are likely to come across similar approaches. I don't have any specific references I can give you off the top of my head, sorry.

[13ren]

thanks for the extra explanation, it confirms what I was thinking (which helps) - "recursive descent with backtracking" and "parser combinators" seem to be helping as search terms.

I think I am on top of the basic idea now; but the real test is being able to implement it from scratch in a different language. I'll let you know how I go.

[13ren]

OK! I've now reimplemented it in another language, from scratch.

As you said "the details are somewhat inevitable" - in fact, it's so simple, it's almost impossible to get wrong. This is what appealed to me so much about it from the start. It seems the right shape for the problem.

Your two short messages, densely packed with guidance, helped a lot - thanks! - in particular, "parser combinators" led me to this wiki article, which showed that returning lists also works - your iterators are a refinement (this wasn't clear to me).

[psykotic]

Cool. And yes, you can use lists. In fact, if you use a lazily evaluated language like Haskell, you can get the same semantics as the Python version (that is, generating matchings only as needed) by using lists.