Lambda the Ultimate

http://www.let.uu.nl/~Richard.Moot/personal/prolog.html

Putting this book online means that the starting point for a lot of other great online material is available:

1. Covington's untyped feature structures: GULP 3.1, an extension of Prolog for unification-based grammar (PDF, Postscript, Prolog Source) Preprocessor for handling feature structures, such as case:nom..number:plural, in Prolog programs.
2. Robin Cooper's "Prolog and Natural Language Semantics" [1, 2]
3. A First and Second Course in Computational Semantics

You can go quite far in modelling natural language and building useful natural language applications with the ideas in these books.

Another great (easy to understand, but not online) Prolog natural language book is:

Matthews, Clive (1998) An Introduction to Natural Language Processing Through Prolog. Longmans.

One chapter analyzes several non-trivial English grammatical constructions in Prolog. He suggests getting a comprehensive book on transformational grammar and code up the grammatical constructions in Prolog. I can't find the book he recommends, but here's a review of my current favorite, comprehensive grammar:

http://www-writing.berkeley.edu/TESL-EJ/ej12/r7.html

According to my understanding, that's what Colmeraurer in France originally designed it for.

There might be better technologies, but if you want to write programs that model language I'd recommend Prolog and this online book, because there's the real danger that you'll get so caught up in a search for the ultimate tool or grammatical formalism that you'll never get any work done.

In the '80's Pereira and Schieber wrote several great papers and little systems using Prolog, like a cool geography question answerer Chat-80 that I got to run pretty easily on SWI-Prolog (eliminate the statistics calls on the mainline).

Typed feature structure unification like that found in HPSG seems to be a better programming language (the list of grammatical phenomenon that it handles in the example sentence list in the distribution is amazing), but you'll have to buy proprietary Lisp to use Stanford's HPSG.....I wasted many an hour trying to get it working with command line based clisp ...maybe the situation has changed...other systems require proprietary SICSTUS prolog....

Here is a programming-language way to think about unification grammars: Grammars are type systems that specify which expressions are well-formed and which are not. For example, "Alice slept Bill" is not grammatical, for perhaps the same reason "sleep(alice, bill)" would not be grammatical if alice and bill are of type "person" and sleep is of type "person -> bool". Unification is useful in modeling natural language grammars, then, for the same reason it is useful in designing programming language type systems. Search is useful in natural language parsers for the same reason type inference is useful in programming language compilers.

One might expect from the above intuition that other aspects of PL type systems may also be applicable to NL grammars. For example, subtyping and intersection types may help us understand how "frauen" in German ('women' plural) can appear as the object of both accusative and dative verbs. (Agreement issues quickly get complicated as you consider say conjunction, e.g., English "and".)

Well, Prolog does unification, of course, but it doesn't have a powerful type system.

So the real question is whther you use Prolog because it is a good all around langugae, or because it has features that resemble features of the object language.

Carpenter chose Prolog to implement typed feature structure ALE and at the same time wrote papers that discussed a lower level, more efficient virtual machine implementation.

Efficient virtual machine implementations like WAM for prolog always seem to come a long time after the initial language definition, cf ML, first there was ML and then efficient CAML.

I guess you could call implementations like the object language ALE in the untyped meta-language Prolog "proto-type implementations" as opposed to efficient "production implementations" like Prolog implemented with the WAM virtual machine.

One advantage of using untyped Prolog over typed Mercury as a meta-language is portability. You can run ALE on many different Prologs, I experimented with on free SWI-Prolog. Also the definition of Prolog is pretty stable and unchanging (Mercury?) which reduces implementation maintenance. Since there are so many open questions in the area of type systems, strong statically typed languages like Haskell are research languages in a constant state of flux, e.g. when you read the circa 1995 research on modular monadic semantics it's all in Gofer with its type system, when you read research circa 2000 it uses Haskell98 type extensions. Untyped meta-languages are probably safer until some consensus on type systems forms.

In the posting above I said "untyped" when I meant "weakly typed."

My understanding: The stronger the type checking is, the *earlier* (compile-time static checking vs. run-time dynamic checking vs. no checking at all) and *more extensive* (not just in data types but in functions and parametrized types also) it is. (i.e. stronger = early and often).

Anyone know of a nice, complete set of definitions?

Benjamin Pierce quote:

"Type systems describe approximations of program behaviors, concentrating on the shapes of the values passed between different parts of the program." (see From prior LTU posting)

What's cool about the examples you give is that they go beyond "approximations of program behavior." They seem to be "exact specifications of program behaviour."

Supposedly dynamic languages like Lisp and Perl are popular because they are not strongly typed and it easier to break and remold abstractions. But if type systems every get to point where they are highly expressive languages for building (and for taking apart and rebuilding) abstractions (like the linguistic abstractions you describe) it seems like they might be a lot more popular and even supercede popular dynamic languages in popularity. Hudak's Haskell music DSL is also a useful type based language for building abstractions in a specific domain: music. [See also Javore (Java version) and also check out jMusic]

It depends on what you mean by "program behaviour": As someone studying semantics, I am used to thinking that program behaviour includes whether a sentence is true or not. Type systems of the sort I described only tell you whether "Alice loves Bob" is well-formed; they don't tell you whether it is true...