Introduction: How to Build a Talking Robot - Computational Linguistics and Talking Robots - page 8

This alternative is at the bottom of the distinction between a sign-oriented
and an agent-oriented approach. Truth-Conditional Semantics is sign-oriented
because it models meaning as a direct relation between a sign and a possible
world, which includes the agent(s). SCG'84 and the later stages of DBS are
agent-oriented because they treat the model as part of the agent.
Another problem with the Montague-style fragment of SCG'84 was Catego-
rial Grammar. Designed by Lesniewski (1929) and Ajdukiewicz (1935), the
combinatorics are coded into the lexical categories, using only two rules in
a nondeterministic bottom-up derivation order (cf. FoCL'99, Sects. 7.4, 7.5).
Categorial Grammar is elegant and simple intuitively, but the rule applications
are based completely on trial and error. This is so inefficient computationally
that it frustrated our attempt to program the SCG'84 fragment in LISP. 16
The experience confirmed the more general insight that a rigorous formal-
ization is only a necessary, but not a sufficient, condition for ensuring a reason-
able implementation as a well-designed computer program. What is needed in
addition is the declarative specification of the interfaces, the components, the
functional flow, and the motor driving the derivation, as well as a general idea
of how natural language communication works.
Our solution to the computational inefficiency of Categorial Grammar is
a strictly time-linear derivation order. The algorithm of DBS, called LA-
grammar, parses an input language surface one word form after the other, from
beginning to end. This means theoretically and technically that the derivation
order of LA-grammar is left-to-right (left-associative, time-linear), based on
computing possible continuations . The hierarchical systems of Phrase Struc-
ture Grammar and Categorial Grammar, in contrast, compute possible substi-
tutions 17 in a top-down or bottom-up derivation order.
LA-grammar was first implemented in LISP. 18 The program, published in
NEWCAT'86, demonstrated the time-linear analysis of 221 constructions of
German and 114 constructions of English, and was re-implemented by read-
ers in South America, Switzerland, and other locations. 19 Later, an algebraic
definition 20 was distilled from the NEWCAT'86 source code.
16 Even today, no implementation of a Categorial Grammar exists for any fragment of a natural language
with nontrivial data coverage. Such an implementation would be most useful for working with this
formal theory. Without it, Categorial Grammars have found no direct practical applications in their
long history.
17 A notable exception is the time-linear system of Kempson et al. (2001). See also Lee (2002).
18 Thanks to Stanley Peters and the CSLI for the 1984-1986 stay at Stanford University. By generously
providing the then newest technology, the CSLI made programming the first left-associative parser
possible, initially in Maclisp on a DEC Tops-20 mainframe, then in Interlisp-D on Xerox Star 8010
Dandelion and Dandetiger workstations, and finally in Common Lisp on an HP 9000 machine.
19 These efforts became known because one little function had been omitted accidentally in the NEW-
CAT'86 source code publication, causing several of the re-programmers to write and ask for it.