[mail and post]

There's no fundamental difference in the above two, other than in which of
the plausable matches will be selected. Both do backtrack, (and, for that
matter, will do so exactly an equal number of times for a non-match). There
are times when the first will backtrack much more than the second, and
times when the second will backtrack much more than the first.

All other things being equal, the first (the one you say is slow) will be
faster than the second, but this is due to some of Perl's internal
optimizations. In any case, knowledge of the likely data (and the
requirements of the task, of course) often make one better than the other.

|> Perhaps it's now too late, and we need to find a new term for what
|> we used to call regular expressions.

Perhaps it's best to differentiate between the calculus phrase ``regular
expression'', coined by Dr. Stephen Kleene in the 40s, and the use of the
same term in modern computer science. There are many situations in language
where the meanings of words have changed. Some examples:

  When I was growing up, ``How are you doing?'' was not a statement.

  A Japanese futon has no relationship to what is called a "futon" in
  American English.

  Tennis shoes are rarely used for tennis.

  The little eraser-head pointing devices on laptops are called mice.

Ah, well, I could go on forever. But basically, the term ``regular
expression'' has no implied meaning to most people that first come across
it in Perl or whatnot, so little confusion arises. It would have been nice
had some other word been used from the start (perhaps one giving more of a
hint as to what the thing is all about), but for the most part we're stuck
with history. I suppose you could start a crusade to use a different
phrase. How about 'whachamacallit'? :-)