LINGUIST List 3.756

Thu 08 Oct 1992

Disc: Unification vs Constraint-Based Grammars

Editor for this issue: <>

Directory

1. Rich Hilliard, 3.751 Unification vs Constraint-Based Grammars
2. Joe Stemberger, Re: 3.751 Unification vs Constraint-Based Grammars
3. Eric Schiller, Re: 3.751 Unification vs Constraint-Based Grammars
4. "Henry S. Thompson", Re: 3.751 Unification vs Constraint-Based Grammars

I really don't keep up with the literature of the 'unification-based
theories' of grammar, but I wonder, could the terminology shift cited
by Avery Andrews be inspired by a 'paradigm shift' within Logic
Programming?

 The notion of unification, as I understand it, originated in
mathematical logic, with Herbrand, as early as the 1930s. J.A.
Robinson is responsible for the modern concept in the realm of
automatic theorem proving. This was the inspiration for Logic
Programming (e.g., Prolog) in the early 1970s.

 Let me presume that this model of Logic Programming is the metaphor,
and implementation model, for unification-based linguistic theories.
Recently, there's been work on an extension to Logic Programming
called 'Constraint Logic Programming.' The idea is to supplant the
unification mechanism of traditional Logic Programming languages with
a more general constraint satisfaction mechanism. Constraints date
back to at least the late 70s: Steele, Sussman, and Stallman at MIT
(reasoning about electronic circuits), and Borning at Xerox (doing
interactive graphics).

 The classic example of a constraint is:

	Farenheit = 9/5*Centigrade + 32;

Given either Farenheit or Centigrade, one can 'solve' for the other,
because of the knowledge we have about the operations, plus and times,
whereas unification will fail in such cases without special mechanisms
(read: kludges).

 The motivation for constraints in Logic Programming seems to be more
effective computation over domains outside of the 'Herbrand Universe'
of terms, like, numbers (as above), booleans, trees, lists, and other
axiomatisable data structures.

 So, it would be interesting to discuss the applicability of this
notion of constraint to grammatical representations [let me defer my
comments to a separate note].

 For anyone interested, here are two recent references on Constraint
Logic Programming:

J. Jaffar, et al., The CLP(R) Language and System. ACM Transactions on
	Programming Languages and Systems, 14(3), July 1992.

J. Cohen, Constraint Logic Programming Languages. Comm. ACM, 33(7),
	July 1990.

 Thanks to Avery Andrews for sparking this discussion! Allow me to
ask a broader question [for another time], What other elements of
recent grammatical theories are informed by Computer Science
metaphors? We all know the traditional, sacred role of automata
theory, but I said 'recent'.

 -- Rich Hilliard
 rhinmet.com

Message 2: Re: 3.751 Unification vs Constraint-Based Grammars

Avery Andrews recently wrote that something
>>>might be wrong-headed (maybe even an instance of the
>>>Postalian Best Theory fallacy).

What is the Postalian Best Theory fallacy?

---joe stemberger

Message 3: Re: 3.751 Unification vs Constraint-Based Grammars

I don't think the line between unification adn non-unification
approaches is so clear. Autolexical Syntax involves unification
on various individual dimension, but not in the interface. So I
don't know which camp I am in!

Eric Schiller
University of Chicago

Message 4: Re: 3.751 Unification vs Constraint-Based Grammars

I won't argue about whether 'constraint-based' is the right name, but
'unification' is certainly the wrong name, and it's a very good thing
if people are moving away from that terminology, as it perpetuates a
serious category error:

A GRAMMAR in most if not all of the formalisms you mention is
declarative -- it specifies, via some (typically
tree-well-formedness-based) formal definition, the grammatical
sentences of a language. In the beginning (LFG, GPSG, PATR), it did
this by a combination of bog-standard CF-PSG rewrite rules and feature
equality constraints. Unification, although often used to gloss a
procedurally-flavoured tutorial, had no place in the definition of the
grammar formalism as such.

A RECOGNISER or PARSER, on the other hand, for one of these
formalisms, might use unification to implement the enforcement of the
equality constraints. It must be said that some of the originators of
the theories involved contributed to the confusion themselves.

More recently (CUG, HPSG, later LFG), the range of constraint types
has increased well beyond simple equality, leading on the one hand to
the investigation of implementations using richer forms of unification
(with disjunction, negation, etc.), and in some cases to the point
where unification is simply not the right implementation model at all
(e.g. arbitrary relational constraints in HPSG), which has led to the
consideration of other tools from e.g. constraint logic programming.

Summary: Distinguishing grammars from implementations/parsers/recognisers
is a good thing; constraints are a component of grammars, unification
a technique employed in implementations. I'll leave it to the
proponents to suggest new cover terms to distinguish the soi-disant
constraint-based theories from GB and its descendants.

 Henry Thompson, Human Communication Research Centre, University of Edinburgh
 2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 31 650-4440
 Fax: (44) 31 650-4587 ARPA: htcogsci.ed.ac.uk JANET: htuk.ac.ed.cogsci
 UUCP: ...!uunet!mcsun!uknet!cogsci!ht