Lambda the Ultimate

(I may have posted this before, but so long ago that I suspect the audience has changed!)

Except when you're really being boiled the part that feels hottub warm and cozy lasts longer.

Saying that the language is ready, ie. no more changes should be introduced, at any given point of the evolution of the language is the same as to say that van Rossum cannot make the correct decisions on language design. But saying that the language is ready is the same as to say that van Rossum indeed can make correct decisions on language design, since he has done so with the improvement of the previous versions and the original version too. Herein lies the paradox. (This is about Python, of course).

Notionally, a regex is an organization of assertions that either succeed or fail.

But Olin Shivers sez (in the above-referenced document):

In principle, a regexp doesn't specify a matching algorithm, it specifies a *set of strings*.

Historically speaking, who's right?

From a CS pov I'd say that the distinction between regular expressions (as a declerative specification of a regular language) and finite automata (that recognize regular languages) is quite fundamental. You actually prove the connection.

(BTW: notice that Perl-like regexes are more powerful than what is called regrexes in CS, for example they support backtracking).

Notice that this is pre-history. Regular expressions in programming languages are not really regular languages for quite awhile, so the history is more involved.

Regular languages have many interesting properties (closures etc.)

To connect this to programming languages: Regular languages are often used to specify the tokens found during the lexing phase (the job of the lexical analyzer), for example recognizing numbers, white space etc. Context free languages are usually used to specify the grammer (which is handled by the parser, that builds the abstract syntax tree). Since programming languages are often not really context free, context information is usually handled as part of the semantic analysis of the program, which is done by analyzing the syntax tree. This is usually much simpler than using a context-sensitive grammer.

I tried to make this as simple as possible, hope I didn't make to many wrong claims along the way...

There are more powerful regular expression packages available than Perl's, based on finite state machines and math.

Try Xerox's:

http://www.xrce.xerox.com/competencies/content-analysis/fsCompiler/home.en.html

Or ATT's:

http://www.research.att.com/sw/tools/fsm/

And yes you can be mathematically rigorous about relating regular expression matching to finite state machine theory. See for instance this link and author:

http://www.cs.sunysb.edu/~algorith/implement/watson/implement.shtml

You can even use regular expressions to do parsing of languages more complex than regular and context free languages like Tree Adjoining Grammars.....used to parse natural languages...

http://www.geocities.com/SoHo/Square/3472/complingrefs.html#tree

See the following book especially:

http://www.bcs.org.uk/siggroup/nalatran/mtreview/mtr-9/mtr-9-7.htm

We can have some Chomsky linguistic bashing, if you like (no politics though, please!)

But are you thinking of Chomsky's early work, or his more recent views?

(BTW, I don't know enough about politics to even begin to address his politics, so no worries on that issue from me. :)

Rather than directly criticizing Chomsky let me say what kind of linguistics I prefer:

I find theories like Ronald Langacker's "Cognitive Grammar" (originally called "Space Grammar" but George Lakoff convinced him to change it for marketing reasons -- heh) much more compelling. Langacker's main work in Cognitive Grammar is published in two large volumes called

Charles Fillmore, Paul Kay, and Adele Goldberg (yes, THAT Adele Goldberg!) have done some work which is essentially compatible with Langacker's stuff, which they call "Construction Grammar."

George Lakoff has also done a lot of work on this sort of linguistics.

The basic idea is that "grammatical correctness" -- which is what Chomsky is all about; those grammars are all bout deciding whether a string is "grammatical" -- is epiphenomenal.

A grammar is nothing but a list of constructions, where a construction is a form-meaning pairing. Some of the forms are more abstract than others. Forms can be embedded within forms, in which case meanings are combined in particular ways.

There are no grammatical rules whatsoever except for the above -- and "grammatical" means nothing more nor less than "parsable as a construction or combination of constructions" -- where "combination" here refers to both juxtaposition/embedding of form *and* blending of meaning.

The blending of meaning aspect is particularly interesting because meaning-construction by simple componential assemblage is understood to be a dengenerate case; the basic process of which that is a degenerate instance is very flexible and contextually sensitive (Mark Turner and Gilles Fauconnier have done some very interesting work on this "blending" phenomenon as a general piece of cognitive equipment).

Chomsky didn't have much to say about meaning construction and what he did say was mostly about establishing correct reference for pronouns and other matters of what he called Logical Form.

Construction/cognitive grammarians like the above tend to be very interested in language as an embodied product of a big wet brain, rather than as an abstract mathematical system of symbols. They tend to be interested in the roles that imagistic and gestalt phenomena play in language understanding, and they reject Chomsky-style isolation of language from general cognitive mechanisms. They tend to posit very little in the way of special mental equipment which is just for language and nothing else, preferring to look at language in terms of specialized, focused usage of abilities that we also display in non-linguistic contexts.

I'm aware there are many other approaches to language besides the straight Chomsky-style and the Cognitive/Construction Grammar theorists, but those are the only ones I'm familiar with so I'm contrasting the two of them. I got to know Chomsky's stuff at first and then moved on to the latter, several years ago when I went on a big linguistics binge.

Let me end by saying I am definitely not a professional linguist and am just giving my impressions as a layman who's taken an interest in these things.