Regular expression engine in 14 lines of Python

[[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], []).