text:
\documentclass[output=paper,biblatex,babelshorthands,newtxmath,draftmode,colorlinks,citecolor=brown]{langscibook}
\ChapterDOI{10.5281/zenodo.5599820}

\IfFileExists{../localcommands.tex}{%hack to check whether this is being compiled as part of a collection or standalone
  \usepackage{../nomemoize}
  \input{../localpackages}
  \input{../localcommands}
  \input{../locallangscifixes.tex}

  \togglepaper[2]
}{}

\title{The evolution of HPSG}
\author{Dan Flickinger\affiliation{Stanford University}\and Carl Pollard\affiliation{Ohio State Universitiy}\lastand Thomas Wasow\affiliation{Stanford University}}

\abstract{HPSG was developed to express insights from theoretical linguistics in a precise formalism that was computationally tractable.  It drew ideas from a wide variety of traditions in linguistics, logic, and computer science.  Its chief architects were Carl Pollard and Ivan Sag, and its most direct precursors were Generalized Phrase Structure Grammar and Head Grammar.  The theory has been applied in the construction of computational systems for the analysis of a variety of languages; a few of these systems have been used in practical applications.  This chapter sketches the history of the development and application of the theory.}

\begin{document}
\maketitle
\label{chap-evolution}

\section{Introduction}

From its inception in 1983, HPSG was intended to serve as a framework for the formulation and implementation of natural language grammars which are (i) linguistically motivated, (ii) formally explicit, and (iii) computationally tractable. These desiderata are reflective of HPSG's dual origins as an academic linguistic theory and as part of an industrial grammar implementation project with an eye toward potential practical applications. Here (i) means that the grammars are intended as scientific theories about the languages in question, and that the analyses the grammars give rise to are transparently relatable to the predictions (empirical consequences) of those theories. Thus HPSG shares the general concerns of the theoretical linguistics literature, including distinguishing between well-formed and ill-formed expressions and capturing linguistically significant generalizations.  (ii) means that the notation for the grammars and its interpretation have a precise grounding in logic, mathematics, and theoretical computer science, so that there is never any ambiguity about the intended meaning of a rule or principle of grammar, and so that grammars have determinate empirical consequences. (iii) means that the grammars can be translated into computer programs that can handle linguistic expressions embodying the full range of complex interacting phenomena that naturally occur in the target languages, and can do so with a tolerable cost in space and time resources.

The two principal architects of HPSG were Carl Pollard\aimention{Carl Pollard} and Ivan
Sag\aimention{Ivan Sag}, but a great many other people made important contributions to its
development.  Many, but by no means all, are cited in the chronology presented in the following
sections.  There are today a number of groups of HPSG researchers around the world, in many cases
involved in building HPSG-based computational systems.  While the number of practitioners is
relatively small, it is a very active community that holds annual meetings and publishes quite
extensively.\footnote{See \url{https://hpsg.hu-berlin.de/HPSG-Bib/} for a list of HPSG
    publications.} Hence, although Pollard no longer works on HPSG and Sag died in 2013, the theory
is very much alive, and still evolving.

\section{Precursors}

HPSG arose between 1983 and 1985 from the complex interaction between two lines of research in
theoretical linguistics: (i) work on context-free Generative Grammar (CFG) initiated in the late
1970s by Gerald Gazdar and Geoffrey Pullum, soon joined by Ivan Sag, Ewan Klein, Tom Wasow, and
others, resulting in the framework referred to as Generalized Phrase Structure Grammar (GPSG:
\citealt*{GKPS85a}); and (ii) Carl Pollard's Stanford dissertation research, under Sag and Wasow's
supervision, on Generalized Context-Free Grammar, and more specifically Head Grammar (HG:
\citealt{Pollard84a-u}).

\subsection{Generalized Phrase Structure Grammar}

In\indexgpsgstart the earliest versions of Generative Grammar \citep{Chomsky57a}, the focus was on motivating
transformations to express generalizations about classes of sentences.  In the 1960s, as generative
linguists began to attend more explicitly to meaning, a division arose between those advocating
using the machinery of transformations to capture semantic generalizations and those advocating the
use of other types of formal devices.  This division became quite heated, and was subsequently
dubbed ``the linguistic wars'' (see \citealt[Chapter 5]{Newmeyer:1980}; \citealt{Harris93a}).  Much
of the work in theoretical syntax and semantics during the 1970s explored ways to constrain the
power of transformations (see especially \citealt{Chomsky73a} and \citealt{ChomLas1977}), and
non-transformational approaches to the analysis of meaning (see especially \citealt{Montague74a-ed}
and \citealt{Dowty79a}).

These developments led a few linguists to begin questioning the central role transformations had
played in syntactic research of the preceding two decades (notably, \citealt{Bresnan78a}).  This
questioning of \isi{Transformational Grammar} (TG) culminated in a series of papers by Gerald Gazdar,
which (in those pre-internet days) were widely distributed as paper manuscripts.  The project that
they laid out was succinctly summarized in one of Gazdar's later publications as follows:

\begin{quote}
Consider eliminating the transformational component of a generative grammar. \citep[\page 155]{Gazdar81a}
\end{quote}

\noindent
The framework that emerged became known as Generalized Phrase Structure Grammar\indexgpsg; a good account of its development is Ted Briscoe's interview of Gazdar in November 2000.\footnote{\url{https://nlp.fi.muni.cz/~xjakub/briscoe-gazdar/}, 2021-01-15.}

GPSG developed in response to several criticisms leveled against transformational grammar. First, TG
was highly underformalized, to the extent that it was unclear what its claims---and the empirical
consequences of those claims---amounted to; CFG, by comparison, was a simple and explicit
mathematical formalism. Second, given the TG architecture of a context-free base together with a set
of transformations, the claimed necessity of transformations was standardly justified on the basis
of arguments that CFGs were insufficiently expressive to serve as a general foundation for natural
language (NL) grammar; but \citet{PG82a-u} showed all such arguments presented up to that time to be
logically flawed or else based on false empirical claims. And third, closely related to the previous
point, they showed that transformational grammarians had been insufficiently resourceful in
exploiting what expressive power CFGs \emph{did} possess, especially through the use of complex
categories bearing features whose values might themselves bear features of their own.  For example,
coordinate\is{coordination} constructions and unbounded\is{unbounded dependency} dependency
constructions had long served as prime exemplars of the need for transformations, but
\citet{Gazdar81a} was able to show that both kinds of constructions, as well as interactions between
them, did in fact yield straightforward analyses within the framework of a CFG.

Gazdar and Pullum's early work in this vein was quickly embraced by Sag and Wasow at Stanford
University, both formally inclined former students of Chomsky's, who saw it as the logical
conclusion of a trend in Chomskyan syntax toward constraining the transformational component. That
trend, in turn, was a response, at least in part, to (i) the demonstration by \citet{PR73a-u} that
\citegen{Chomsky65a} Standard Theory, when precisely formalized, was totally unconstrained, in the
sense of generating all recursively enumerable languages; and (ii) the insight of
\citet{Emonds76a-u} that most of the transformations proposed up to that time were
``structure-preserving'' in the sense that the trees they produced were isomorphic to ones that were
base-generated. Besides directly addressing these issues of excess power and structure preservation,
the hypothesis that NLs were context-free also had the advantage that CFGs were well-known by
computer scientists to have decidable recognition problems and efficient parsing algorithms, facts
which seemed to have some promise of bearing on questions of the psychological plausibility and
computational tractability of the grammars in question.

Aside from serving as a framework for theoretical linguistic research, GPSG also provided the
theoretical underpinnings for a natural language processing (NLP) project established in 1981 by
Egon Loebner at Hewlett-Packard Laboratories in Palo Alto. This project, which led in due course to
the first computer implementation of HPSG, is described below.%
\indexgpsgend

\subsection{Head Grammar}
\label{evolution:sec-head-grammar}

Pollard, with a background in pure mathematics, \ili{Chinese} historical phonology, and
1930s--1950s-style American structural linguistics, arrived at Stanford in 1979 with the intention
of getting a PhD in \ili{Chinese} linguistics, but was soon won over to theoretical syntax by Wasow
and Sag. He had no exposure to Chomskyan linguistics, but was immediately attracted to the emerging
nontransformational approaches, especially the early GPSG papers and the contemporaneous forms of CG
in \citet{Bach79a,Bach80a} and \citeauthor{Dowty82a-u} \citeyearpar{Dowty82a-u,Dowty82b}, in part
because of their formal simplicity and rigor, but also because the formalism of CFG was (and is)
easy to read as a more technically precise rendering of structuralist ideas about syntax (as
presented, e.g., in \citealt{Bloomfield33a-u} and \citealt{Hockett1958}).

Although \citet{PG82a-u} successfully refuted all published arguments to date that CFGs were
inadequate for analyzing NLs, by the following year, Stuart Shieber had developed an argument
(published in \citealt{Shieber85a}), which was (and remains) generally accepted as correct, that
there could not be a CFG that accounted for the cross-serial dependencies in Swiss
German\il{German!Swiss}; and Chris Culy showed, in his Stanford M.A. thesis (cf.\
\citealt{Culy85a}), that the presence of reduplicative compounding in \ili{Bambara} precluded a CF
analysis of that language. At the same time, Bach and Dowty (independently) had been experimenting
with generalizations of traditional A-B (Ajdukiewicz-Bar Hillel) CG which allowed for modes of
combining strings (such as \isi{reduplication}, \isi{wrapping}, \isi{insertion},
\isi{cliticization}, and the like) in addition to the usual \isi{concatenation}. This latter
development was closely related to a wider interest among nontransformational linguists of the time
in the notion of discontinuous\is{discontinuous constituent} constituency, and also had an obvious affinity to
\citegen{Hockett54a} item-and-process conception of linguistic structure, albeit at the level of
words and phrases rather than morphemes. One of the principal aims of Pollard's dissertation work
was to provide a general framework for syntactic (and semantic) analysis that went beyond---but not
too far beyond---the limits of CFG in a way that took such developments into account.

\enlargethispage{5pt}
Among the generalizations of CFG that Pollard studied, special attention was given to HGs, which
differ from CFGs in two respects: (i) the role of strings was taken over by headed strings,
essentially strings with a designation of one of its words as its head; and (ii) besides
concatenation, headed strings can also be combined by inserting one string directly to the left or
right of another string's head. An appendix of his dissertation \citep[Appendix~1]{Pollard84a-u}
provided an analysis of discontinuous constituency in \ili{Dutch}, and that analysis also works for
Swiss German\il{German!Swiss}. In another appendix, Pollard used a generalization of the \isi{CKY
  algorithm} to prove that the head languages (HLs, the languages analyzed by HGs) shared with CFLs
the property of deterministic polynomial time recognition complexity, but of order $n^{7}$,
subsequently reduced by \citet*{Kasamietal1989} to $n^{6}$, as compared with order $n^{3}$ for
CFLs. For additional formal properties of HGs, see \citet{Roach1987}. \citet{VijayWeir1994} proved
that HGs had the same weak generative capacities as three other grammar formalisms -- Combinatory
Categorial Grammar \citep{Steedman87a-u,Steedman90a-u}, Lexicalized Tree-Adjoining Grammar
\citep{Shabes90}, and Linear Indexed Grammar \citep{Gazdar88a-u} -- and the corresponding class of
languages became known as \emph{\isi{mildly context sensitive}}.

Although the handling of linearization in HG seems not to have been pursued further within the HPSG
framework, the ideas that (i) linearization had to involve data structures richer than strings of
phoneme strings, and (ii) the way these structures were linearized had to involve operations other
than mere concatenation, were implicit in subsequent HPSG work, starting with \citegen[\page
169]{ps} \isi{Constituent Order Principle} (which was really more of a promissory note than an
actual principle).  These and related ideas would become more fully fleshed out a decade later
within the linearization grammar\is{linearization-based HPSG} avatar of HPSG developed by \citet{Reape90a},
\citet{Reape92a}, \citet{Kathol95a,Kathol2000a}, and
\citet{Mueller95c,Babel,Mueller99a,Mueller2004b}. (See also
\crossrefchapterw[Section~\ref{sec-domains}]{order} on linearization approaches in HPSG.) On the
other hand, two other innovations of HG, both related to the system of syntactic features, were
incorporated into HPSG, and indeed should probably be considered the defining characteristics of
that framework, namely the list-valued \subcat and \slasch features, discussed below.

\section{The HP NL project}

Work on GPSG culminated in the \citeyear{GKPS85a} book \emph{Generalized Phrase Structure Grammar}\indexgpsg
by Gazdar, Klein, Pullum, and Sag.  During the writing of that book, Sag taught a course on the
theory, with participation of his co-authors.  The course was attended not only by Stanford students
and faculty, but also by linguists from throughout the area around Stanford, including the Berkeley
and Santa Cruz campuses of the University of California, as well as people from nearby industrial
labs.  One of the attendees at this course was Anne Paulson\aimention{Anne Paulson}, a programmer
from Hewlett-Packard (HP) Laboratories in nearby Palo Alto, who had some background in linguistics
from her undergraduate education at Brown University.  Paulson told her supervisor at HP Labs, Egon
Loebner\aimention{Egon Loebner}, that she thought the theory could be implemented and might be
turned into something useful. Loebner, a multi-lingual polymathic engineer, had no background in
linguistics, but he was intrigued, and invited Sag to meet and discuss setting up a natural language
processing project at HP. Sag brought along Gazdar, Pullum, and Wasow. This led to the creation of
the project that eventually gave rise to HPSG.  Gazdar, who would be returning to England relatively
soon, declined the invitation to be part of the new project, but Pullum, who had taken a position at
the University of California at Santa Cruz (about an hour's drive from Palo Alto), accepted.  So the
project began with Sag, Pullum, and Wasow hired on a part-time basis to work with Paulson and two
other HP programmers, John Lamping\aimention{John Lamping} and Jonathan King\aimention{Jonathan
  King}, to implement a GPSG of \ili{English} at HP Labs.  J. Mark Gawron\aimention{J. Mark Gawron},
a linguistics graduate student from Berkeley who had attended Sag's course, was very soon added to
the team.

The initial stages consisted of the linguists and programmers coming up with a notation that would serve the purposes of both.  Once this was accomplished, the linguists set to work writing a grammar of \ili{English} in Lisp to run on the \mbox{DEC-20} mainframe computer that they all worked on.   The first publication coming out of this project was a 1982 Association for Computational Linguistics paper.  The paper's conclusion begins:
\begin{quote}
What we have outlined is a natural language system that is a direct implementation of a linguistic theory.  We have argued that in this case the linguistic theory has the special appeal of computational tractability (promoted by its context-freeness), and that the system as a whole offers the hope of a happy marriage of linguistic theory, mathematical logic, and advanced computer applications. \citep[\page 80]{Gaw:Kin:Lam:82}
\end{quote}
This goal was carried over into HPSG.

It should be mentioned that the HP group was by no means alone in these concerns.  The early 1980s
was a period of rapid growth in computational linguistics (due at least in part to the rapid growth
in the power and accessibility of computers).  In the immediate vicinity of Stanford and HP Labs,
there were at least two other groups working on developing natural language systems that were both
computationally tractable and linguistically motivated.  One such group was at the Xerox Palo Alto
Research Center, where Ron Kaplan\aimention{Ron Kaplan} and Joan Bresnan\aimention{Joan Bresnan} (in
collaboration with a number of other researchers, notably Martin Kay\aimention{Martin Kay}) were
developing Lexical Functional Grammar\indexlfg;\footnote{For a comparison of HPSG and LFG see
  \crossrefchapterp{lfg}. A handbook of LFG parallel to this handbook is in preparation
  \citep{LFGhandbook}.}  the other was at SRI International, where a large subset of SRI's
artificial intelligence researchers  (including Barbara Grosz\aimention{Barbara Grosz}, Jerry
Hobbs\aimention{Jerry Hobbs}, Bob Moore\aimention{Bob Moore}, Hans Uszkoreit\aimention{Hans
  Uszkoreit}, Fernando Pereira\aimention{Fernando Pereira}, and Stuart Shieber\aimention{Stuart
  Shieber}) worked on natural language.  Thanks to the founding of the Center for the Study of
Language and Information (CSLI) at Stanford in the early 1980s, there was a great deal of
interaction among these three research groups.  Although some aspects of the work being done at the
three non-Stanford sites were proprietary, most of the research was basic enough that there was a
fairly free flow of ideas among the three groups about building linguistically motivated natural
language systems.

Other projects seeking to develop theories combining computational tractability with linguistic
motivation were also underway outside of the immediate vicinity of Stanford, notably at the
Universities of Pennsylvania and Edinburgh.  Aravind Joshi and his students were working on Tree
Adjoining Grammars \citep*{JLT75a-u,Joshi87a-u}, while Mark Steedman and others were developing
Combinatory Categorial Grammar \citep{Steedman87a-u,Steedman90a-u}.

During the first few years of the HP NL project, several Stanford students were hired as part-time
help.  One was Pollard, who was writing his doctoral dissertation under Sag's supervision.  Ideas
from his thesis work played a major role in the transition from GPSG to HPSG.  Two other students
who became very important to the project were Dan Flickinger\aimention{Dan Flickinger}, a doctoral
student in linguistics, and Derek Proudian\aimention{Derek Proudian}, who was working on an
individually-designed undergraduate major when he first began at HP and later became a master's
student in computer science.  Both Flickinger and Proudian became full-time HP employees after
finishing their degrees.  Over the years, a number of other HP employees also worked on the project
and made substantial contributions.  They included Susan Brennan\aimention{Susan Brennan}, Lewis
Creary\aimention{Lewis Creary}, Marilyn Friedman\aimention{Marilyn Friedman} (now
Walker\aimention{Marilyn Walker}), Dave Goddeau\aimention{Dave Goddeau}, Brett
Kessler\aimention{Brett Kessler}, Joachim Laubsch\aimention{Joachim Laubsch}, and John
Nerbonne\aimention{John Nerbonne}.  Brennan, Walker, Kessler, and Nerbonne all later went on to
academic careers at major universities, doing research dealing with natural language processing.

The HP NL project lasted until the early 1990s.  By then, a fairly large and robust grammar of
\ili{English} had been implemented.  The period around 1990 combined an economic recession with what
has sometimes been termed an ``AI winter'' -- that is, a period in which enthusiasm and hence
funding for artificial intelligence research was at a particularly low ebb.  Since NLP was
considered a branch of AI, support for it waned.  Hence, it was not surprising that the leadership
of HP Labs decided to terminate the project.  Flickinger and Proudian came to an agreement with HP
that allowed them to use the NLP technology developed by the project to launch a new start-up
company, which they named \isi{Eloquent Software}.  They were, however, unable to secure the capital
necessary to turn the existing system into a product, so the company never got off the ground.

\section{The emergence of HPSG}

A few important features of GPSG that were later carried over into HPSG are worth mentioning
here. First, GPSG borrowed from Montague the idea that each phrase structure rule was to be paired
with a semantic rule providing a recipe for computing the meaning of the mother from the meanings of
its daughters \citep[\page 156]{Gazdar81a}; this design feature was shared with contemporaneous
forms of Categorial Grammar (CG) being studied by such linguists as Emmon Bach
\citep{Bach79a,Bach80a} and David Dowty \citep{Dowty82a-u,Dowty82b}.  Second, the specific inventory
of features employed in GPSG for making fine-grained categorial distinctions (such as case,
agreement, verb inflectional form, and the like), was largely preserved, though the technical
implementation of morphosyntactic features in HPSG was somewhat different. And third, the \slasch
feature, which originated in \citegen{Gazdar81a} derived categories (e.g. S/NP), and which was used
to keep track of unbounded\is{unbounded dependency} dependencies, was generalized in HPSG to allow
for multiple unbounded dependencies (as in the notorious violins-and-sonatas example in
(\ref{ex-violins}) below). As will be discussed, this \slasch feature bears a superficial---and
misleading---resemblance to the Categorial Grammar connectives written as `/' and
`\textbackslash'. On the other hand, a centrally important architectural feature of GPSG absent from
HPSG (and from HG) was the device of metarules\is{metarule}, higher-order rules used to generate the
full set of context-free phrase structure rules (PSRs) from an initial inventory of basic
PSRs. Among the metarules were ones used to introduce non-null \slasch values and propagate them
upward through trees to a position where they were discharged by combination with a matching
constituent called a \isi{filler} (analogous to a \emph{wh}-moved expression in TG).

A note is in order about the sometimes confusing use of the names \emph{Head Grammar} (\emph{HG})
and \emph{HPSG}. Strictly speaking, HG was a specific subtype of generalized CFG developed in
Pollard's dissertation work, but the term \emph{HG} did not appear in academic linguistic
publications with the exception of the \citet{PollardSag1983} WCCFL paper, which introduced the
distinction between head features and binding features (the latter were incorporated into GPSG under
the name \emph{foot features}). In the summer of 1982, Pollard had started working part time on the
HP NL project; and the term \emph{HPSG} was first employed (by Pullum) in reference to an extensive
reworking by Pollard and Paulson of the then-current HP GPSG implementation, incorporating some of
the main features of Pollard's dissertation work in progress, carried out over the summer of 1983,
while much of the HP NLP team (including Pullum and Sag) was away at the LSA Institute in Los
Angeles.  The implication of the name change was that whatever this new system was, it was no longer
GPSG.

Once this first HPSG implementation was in place, the NLP work at HP was considered to be within the
framework of HPSG, rather than GPSG. After Pollard completed his dissertation, he continued to refer
to \emph{HG} in invited talks as late as autumn 1984; but his talk at the (December~1984) LSA
Binding Theory Symposium used \emph{HPSG} instead, and after that, the term \emph{HG} was supplanted
by \emph{HPSG} (except in publications by non-linguists about formal language theory). One
additional complication is that until the \citet*{GKPS85a} volume appeared, GPSG and HPSG were
developing side by side, with considerable interaction.  Pollard, together with Flickinger, Wasow,
Nerbonne, and others, did HPSG; Gazdar and Klein did GPSG; and Sag and Pullum worked both sides of
the street.

HPSG papers, about both theory and implementation, began to appear in 1985, starting with Pollard's
WCCFL paper \emph{Phrase structure grammar without metarules} \citep{Pollard85a-u}, and his paper at
the Categorial Grammar conference in Tucson \citep{Pollard88a}, comparing and contrasting HPSG with
then-current versions of Categorial Grammar due to Bach, Dowty, and Steedman. These were followed by
a trio of ACL papers documenting the current state of the HPSG implementation at HP Labs:
\citet{creary-pollard:1985:ACL}, \citet*{FPW85a}, and \citet{PP85}. Of those three, the most
significant in terms of its influence on the subsequent development of the HPSG framework was the
second, which showed how the lexicon could be (and in fact was) organized using multiple-inheritance
knowledge representation; Flickinger's Stanford dissertation \citep{Flickinger87} was an in-depth
exploration of that idea.

\section{Early HPSG}
\label{evolution:sec-early-hpsg}

Setting aside implementation details, early HPSG can be characterized by the following architectural features:

\paragraph*{Elimination of metarules} Although metarules\is{metarule} were a central feature of GPSG, they were also problematic: \citet{UszPet1982} had shown  that if metarules were allowed to apply to their own outputs, then the resulting grammars were no longer guaranteed to generate CFLs; indeed, such grammars could generate all recursively enumerable languages. And so, in GPSG, the closure of a set of base phrase structure rules (PSRs) under a set of metarules was defined in such a way that no metarule could apply to a PSR whose own derivation involved an application of that metarule. This definition was intended to ensure that the closure of a finite set of PSRs remained finite, and therefore still constituted a CFG.

So, for example, the metarule STM1 was used in GPSG to convert a PSR into another PSR, one of whose daughters is [+NULL] (informally speaking, a ``trace''), and feature cooccurrence restrictions\is{feature cooccurrence restriction} (FCRs) guaranteed that such daughters would bear a \slasch value, and that this \slasch value would also appear on the mother. Unfortunately, the \isi{finite closure} definition described above does not preclude the possibility of derived PSRs whose mother carries multiple, in fact unboundedly many
\slasch values (e.g. NP/NP, (NP/NP)/NP, etc.). And this in turn leads to an infinite set of PSRs, outside the realm of CF-ness (see \citealt{Ristad86}).  Of course, one could rein in this excess power by imposing another FCR that disallows categories of the form (X/Y)/Z; but then there is no way to analyze sentences containing a constituent with two undischarged unbounded dependencies, such as the VP complement of \emph{easy} in the following example:

\ea
\label{ex-violins}
Violins this finely crafted, even the most challenging sonatas are easy to [play \_ on \_]. (adapted from \citealt[\page 169]{ps2})
\z

\noindent
GPSG avoided this problem by not analyzing such examples. In HPSG \citep{Pollard85a-u}, by contrast, such examples were analyzed straightforwardly by replacing GPSG's category-valued \slasch feature with one whose values were lists (or sets) of categories. This approach still gave rise to an infinite set of rules, but since maintaining context-freeness was no longer at stake, this was not seen as problematic. The infinitude of rules in HPSG arose not through a violation of finite closure (since there were no longer any metarules at all), but because each of the handful of schematic PSRs (see below) could be directly instantiated in an infinite number of ways, given that the presence of list-valued
features gave rise to an infinite set of categories.

\paragraph*{Lexical rules} GPSG, generalizing a suggestion of \citet{Flickinger1983}, constrained metarules to apply only to PSRs that introduced a lexical head. \citet{Pollard85a-u} took this idea a step further, noting that many proposed metarules could be reformulated as lexical rules that (among other effects) operated on the subcategorization frames (encoded by the \subcat feature discussed below) of lexical entries. The idea of capturing some linguistic generalizations by means of rules internal to the lexicon had been explored by generative grammarians since \citet{Jackendoff75a}; and lexical rules of essentially the kind Pollard proposed were employed by \citet{Bach83}, \citet{Dowty78a}, and others working in Categorial Grammar. Examples of constructions handled by metarules in GPSG but in HPSG by lexical rules included sentential \isi{extraposition}, subject extraction\is{extraction!subject}, and the \isi{passive}. \citet*{FPW85a} argued for an architecture for the lexicon that combined lexical rules with multiple inheritance using a frame-based knowledge representation system \citep{Minsky1975}, on the basis of both overall grammar simplicity and efficient, easily modifiable implementation.

\paragraph*{CG-like treatment of subcategorization} GPSG\label{page-subcategorization-start} treated subcategorization using an integer-valued feature called \subcat that in effect indexed each lexical item with the rule that introduced and provided its subcategorization frame; e.g. \emph{weep} was listed in the lexicon with \subcat value 1 while \emph{devour} was listed with \subcat value 2, and then PSRs of roughly the form in (\mex{1}) guaranteed that lexical heads would have the right kinds of complements.
\ea
\begin{tabular}[t]{l}
          VP $\rightarrow$ V[\subcat 1] \\
          VP $\rightarrow$ V[\subcat 2] NP
\end{tabular}
\z

\noindent
In HPSG, by contrast, the
\subcat feature directly characterized the grammatical arguments selected by a head (not just the
complements, but the subject too) as a list of categories, so that e.g.~\emph{weep} was listed as
V[\subcat \liste{ NP }] but \emph{devour} as V[\subcat \liste{ NP, NP }] (where the first occurrence of NP refers to the object and the second to the subject). This treatment of argument selection was inspired by Categorial Grammar, where the same verbs would have been categorized as NP{\textbackslash}S and (NP{\textbackslash}S)/NP respectively;\footnote{We adhere to the Lambek convention for functor categories, so that expressions seeking to combine with an A on the left to form a B are written ``A{\textbackslash}B'' (not ``B{\textbackslash}A'').} the main differences are that (i) the CG treatment also encodes the directionality of the argument relative to the head, and (ii) in HPSG, all the arguments appear on one list, while in CG they are ``picked up'' one at a time, with as many
connectives (/ or \textbackslash) as there are arguments. In particular, as in the CG of \citet{Dowty82b}, the subject was defined as the last argument, except that in HPSG, ``last'' now referred to the rightmost position on the \subcat list, not to the most deeply embedded connective. In HPSG, this
ordering of the categories on the \subcat list was related not just to CG, but also to the traditional grammatical notion of \isi{obliqueness}, and also to the accessibility hierarchy of \citet{KC77a}.  See \citet[Section 4]{MWArgSt} for a more detailed discussion of these developments from GPSG to HPSG.\label{page-subcategorization-end}

\paragraph*{Schematic rules} Unlike CFG but like CG, HPSG had only a handful of schematic rules. For example, in \citet{Pollard85a-u}, a substantial chunk of \ili{English} ``local'' grammar (i.e.~leaving aside unbounded dependencies) was handled by three rules: (i) a rule (used for subject-auxiliary inversion) that forms a sentence from an inverted (+\textsc{inv}) lexical head and all its arguments; (ii) a rule that forms a phrase from a head with \subcat list of length > 1 together with all its non-subject arguments; and (iii) a rule that forms a sentence from a head with a \subcat value of length one together with its single (subject) argument.

\paragraph*{List- (or set-) valued \slasch feature} The list-valued \slasch was introduced in \citet{Pollard85a-u} to handle multiple unbounded dependencies, instead of the GPSG category-valued \slasch (which in turn originated as the \emph{derived categories} of  \citet{Gazdar81a}, e.g.~S/NP). In spite of the notational similarity, though, the PSG \slasch is not an analog of the CG slashes / and \textbackslash \ (though HPSG's \subcat is, as explained above). In fact, HPSG's \slasch has no analog in the kinds of CGs being developed by Montague semanticists such as \citet{Bach79a,Bach80a} and \citet{Dowty82a-u} in the late 1970s and early 1980s, which followed the CGs of \citet{Bar-Hillel54-u} in having only rules for eliminating (or canceling) slashes as in (\mex{1}):

\ea
\begin{tabular}[t]{ccc}
A A{\textbackslash}B  & &     B/A A \\ \cline{1-1} \cline{3-3}
B & & B
\end{tabular}
\z

\noindent
To find an analog to HPSG's \slasch in CG, we have to turn to the kinds of CGs invented by \citet{Lambek1958}, which unfortunately were not yet well-known to linguists (though that would soon change, starting with Lambek's appearance at the 1985 Categorial Grammar conference in Tucson). What sets apart grammars
of this kind (and their elaborations by \citet{Moortgat89a-u}, \citet{OBW88a-ed}, \citet{Morrill94a-u}, and many others), is the existence of rules for hypothetical proof (not given here), which allow a hypothesized category occurrence introduced into a tree (thought of as a proof) to be discharged.

In the Gentzen\addref style of natural deduction (see \citealt{Pollard:2013}), hypothesized categories are written to the left of the symbol $\vdash$ (turnstile), so that the two slash elimination rules above take the following form, where $\Gamma$ and $\Delta$ are lists of categories, and comma represents list concatenation as in (\mex{1}):

\ea
\begin{tabular}[t]{ccc}
$\Gamma$ $\vdash$ A \ \ $\Delta$ $\vdash$ A{\textbackslash}B  & &     $\Gamma$ $\vdash$ B/A \ \ $\Delta$ $\vdash$ A \\ \cline{1-1} \cline{3-3}
$\Gamma$,$\Delta$ $\vdash$ B & & $\Gamma$,$\Delta$ $\vdash$ B
\end{tabular}
\z

\noindent
These rules serve to propagate hypotheses (analogous to linguists' traces) downward through the proof tree (downward because logicians' trees are
upside down with the conclusion, or ``root'', at the bottom). In HPSG notation, these same rules can be written as one rule (since \subcat is
nondirectional) in (\mex{1}):

\ea
\begin{tabular}[t]{c}
B[\subcat \liste{\ldots, A}, \slasch $\Gamma$] \ \ A[\slasch $\Delta$] \\ \cline{1-1}
B[\subcat \liste{\ldots}][\slasch $\Gamma$,$\Delta$]
\end{tabular}
\z

This in turn is a special case of an HPSG principle first known as the Binding Inheritance Principle (BIP) and later as the \isi{Nonlocal Feature Principle} (binding features included \slasch as well as the features \textsc{que}
and \textsc{rel} used for tracking undischarged interrogative and relative pronouns). The original statement of the BIP \citep{Pollard:1986} treated \slasch as set- rather than list-valued:

\begin{quote}
The value of a binding feature on the mother is the union of the values of that feature on the daughters. \citep{Pollard:1986}
\end{quote}

\noindent
For example, the doubly-gapped VP in the violins-and-sonatas example in (\ref{ex-violins}) is analyzed in HPSG roughly  as
is shown in Figure~\ref{fig-play-on}
\begin{figure}
\centerfit{%
\begin{forest}
sm edges
[{V[\subcat \sliste{ NP }, \slasch \sliste{ NP, NP }]}
  [{V[\subcat \sliste{ PP, NP, NP }]} [play]]
  [{NP[\slasch \sliste{ NP }]} [t]]
  [{PP[\slasch \sliste{ NP }]}
    [{P[\subcat \sliste{ NP }]} [on]]
    [{NP[\slasch \sliste{ NP }]} [t]]]]
\end{forest}
}
\caption{\label{fig-play-on}\emph{play on} as part of \emph{Violins this finely crafted, even the most challenging sonatas are easy to play on.}}
\end{figure}
and essentially the same way in Lambek-style CG:

\ea
\begin{tabular}[t]{ccccccc}
\multicolumn{2}{c}\emph{play} & \emph{t} & & \emph{on} & \ \ \ \ \ \ \emph{t} & \\
\multicolumn{2}{c}{$\vdash$ ((NP{\textbackslash}S)/PP)/NP} & NP $\vdash$ NP & & $\vdash$ PP/NP & \multicolumn{2}{c}{NP $\vdash$ NP} \\ \cline{1-3} \cline{5-7}
 & \multicolumn{2}{c}{NP $\vdash$ (NP{\textbackslash}S)/PP} & & \multicolumn{3}{c}{NP $\vdash$ PP} \\ \cline{2-6}
\multicolumn{7}{c}{NP,NP $\vdash$ (NP{\textbackslash}S)}
\end{tabular}
\z

\noindent
Aside from the binary branching of the \citeauthor{Lambek1958} analysis, the main difference is that HPSG traces of
the form A[\slasch \liste{ A }] correspond
to Lambek axioms of the form A $\vdash$ A, which is the standard mechanism for introducing hypotheses in Gentzen-style natural deduction.

An overview and elaboration of early HPSG is provided by the two books \citet{ps} and
\citet{ps2}. Confusingly, the former is called \textit{Information-Based Syntax and Semantics,
  Volume 1: Fundamentals}, and the second simply \textit{Head-Driven Phrase Structure Grammar} (not
\textit{Information-Based Syntax and Semantics, Volume 2}). The reason for the title change had to
do with a change in the underlying mathematical theory of feature structures. In the first book,
following work in theoretical computer science by \citet{RoundsKasper1986} and
\citet{MoshierRounds1987}, feature structures were treated as data structures that supplied partial
information about the linguistic objects being theorized about; this perspective in turn was based
on \citegen{Scott1982} mathematical theory of computation in terms of what he called information
systems. Subsequently, Paul King\aimention{Paul King} persuaded Pollard and Sag that it was more
straightforward to distinguish between feature\is{feature structure} structures, thought of as formal models of the
linguistic objects, and feature\is{feature structure description} descriptions or formulas of feature logic,
which provided partial information about them, as described in his Manchester dissertation
\citep{King89}.  Although the formal issues involved in distinguishing between the two approaches
are of interest in their own right, they seem not to have had a lasting effect on how theoretical
linguists used HPSG, nor on how computational linguists implemented it. As for subject matter,
\citet{ps} was limited to the most basic notions, including syntactic features and categories
(including the distinction between head features and binding features); subcategorization and the
distinction between arguments and adjuncts (the latter of which necessitated one more rule schema
beyond the three proposed by \citealt{Pollard85a-u}); basic principles of grammar (especially the
Head Feature Principle\is{principle!Head Feature} and the Subcategorization Principle\is{principle!Subcategorization}); the \isi{obliqueness} order
and constituent ordering\is{constituent!ordering}; and the organization of the \isi{lexicon} by
means of a \isi{multiple inheritance} hierarchy and lexical rules\is{lexical rule}. \citet{ps2} used
HPSG to analyze a wide range of phenomena, primarily in \ili{English}, that had figured prominently
in the syntactic literature of the 1960s--1980s, including \isi{agreement},
expletive\is{pronoun!expletive} pronoun constructions, \isi{raising}, \isi{control}, filler-gap
  constructions\is{unbounded dependency} (including island\is{island constraint} constraints and parasitic\is{gap!parasitic} gaps); so-called
\isi{Binding Theory} (the distribution of reflexive pronouns, non-reflexive pronouns, and
non-pronominal NPs), and \isi{scope!of quantificational NPs}. These topics are also handled in
respective chapters of this handbook
\parencites{chapters/agreement}{chapters/control-raising}{chapters/udc}{chapters/islands}{chapters/binding}[Section~\ref{sec-scope-in-hpsg}]{chapters/semantics}.

\section{Theoretical developments}
\label{evolution:sec-theoretical-developments}

Three decades of vigorous work since \cite{ps} developing the theoretical framework of HPSG receive detailed discussion throughout the present volume, but we highlight here two significant stages in that development.  The first is in Chapter 9 of \citew{ps2}, where a pair of major revisions to the framework presented in the first eight chapters are adopted, changing the analysis of valence and of unbounded dependencies.  Following \citet{Borsley87a,Borsley88b-u,Borsley89,Borsley90a}, Pollard and Sag moved to distinguish subjects from complements, and further to distinguish subjects from specifiers, thus replacing the single \subcat attribute with \subj, \spr, and \comps.  This formal distinction between subjects and complements enabled an improved analysis of unbounded dependencies, eliminating traces altogether by introducing three lexical rules for the extraction of subjects, complements, and adjuncts respectively.   It is this revised analysis of valence constraints that came to be viewed as part of the standard HPSG framework, though issues of valence representation cross-linguistically remain a matter of robust debate.

The second notable stage of development was the introduction of a type hierarchy of \emph{constructions}\is{construction} as descriptions of phrasal feature structures, employed first by \citet{Sag97a} in a richly detailed analysis of a wide variety of \isi{relative clause} phenomena in \ili{English}.  This extension from the lexicon of the use of descriptions of typed feature structures organized in hierarchies to syntactic rules preserved the ability to express general principles holding for rule schemata while also enabling expression of idiosyncratic properties of phrases.  In \crossrefchaptert{properties}, the version of the framework with this extended use of types is termed \term{Constructional HPSG}, including further elaboration by \citet{GSag2000a-u} to a comprehensive analysis of interrogatives\is{interrogative} in \ili{English}.

\section{The LinGO project}

\largerpage
In the early 1990s, a consortium of research centers in Germany secured funding from the \ili{German} government for a large project in spoken language \isi{machine translation}, called \verbmobil \citep{Wahlster2000a-ed}, which aimed to combine a variety of methods and frameworks in a single implemented state-of-the-art demonstrator system.  Grammars of \ili{German} and \ili{English} were to be implemented in HPSG, to be used both for parsing and for generation in the translation of human-human dialogues, with a \ili{German} grammar initially implemented by Pollard\aimention{Carl Pollard} and Tibor Kiss\aimention{Tibor Kiss} at IBM in Heidelberg, later replaced by one developed by Stefan Müller and Walter Kasper at the \ili{German} AI Research Center (DFKI), coordinator for the \verbmobil project.  The DFKI contracted in 1993 with Sag\aimention{Ivan Sag} at CSLI to design and implement the \ili{English} grammar, with Flickinger\aimention{Dan Flickinger} brought over from HP Labs to help lead the effort, forming a new research group at CSLI initially called ERGO (for \ili{English} Resource Grammar Online), later generalized to the name LinGO (Linguistic Grammars Online).  Early LinGO members included Wasow\aimention{Tom Wasow} and linguistics graduate student Rob Malouf\aimention{Rob Malouf}, who authored the initial implementation of the \ili{English} Resource Grammar (ERG)\is{English Resource Grammar (ERG)}, along with four other linguistics graduate students, Emily Bender\aimention{Emily Bender}, Kathryn Campbell-Kibler\aimention{Kathryn Campbell-Kibler}, Tony Davis\aimention{Tony Davis}, and Susanne Riehemann\aimention{Susanne Riehemann}.

During the first of the two four-year phases of the \verbmobil project, the focus was on designing and implementing core syntactic and semantic analyses, initially using the DISCO/PAGE platform \citep{DISCO94} developed at the DFKI, and largely informed by the framework presented in \citet{ps2}.  However, a more computationally useful semantic formalism emerged, called Minimal Recursion Semantics\indexmrs (MRS: \citealt*{CFPS2005a}), which Ann Copestake, formerly of the European \isi{ACQUILEX} project, helped to design.  Copestake also expanded the LKB\indexlkb system \citep{Copestake2002a} which had been used in ACQUILEX, to serve as the grammar development environment for the LinGO project, including both a parser and a generator for typed feature structure grammars.

\largerpage
The second four years of the \verbmobil project emphasized development of the generation capabilities of the ERG, along with steady expansion of linguistic coverage, and elaboration of the MRS framework.  LinGO contributors in this phase included Sag, Wasow, Flickinger, Malouf, Copestake, Riehemann, and Bender, along with a regular visitor and steady contributor from the DFKI, Stephan Oepen\aimention{Stephan Oepen}.  \verbmobil had meanwhile added \ili{Japanese} alongside \ili{German} \citep{MK2000a} and \ili{English} \citep*{FCS2000a} for more translation pairs, giving rise to another relatively broad-coverage HPSG grammar, Jacy, authored by Melanie Siegel at the DFKI \citep{Siegel2000a}.  Work continued at the DFKI, of course, on the \ili{German} HPSG grammar, written by Stefan Müller, adapted from his earlier Babel grammars \citep{Mueller99a}, and with semantics contributed by Walter Kasper.

Before the end of \verbmobil funding in 2000, the LinGO project had already begun to diversify into
other application and research areas using the ERG, including over the next several years work on
\isi{augmented/adaptive communication}, multiword\is{multiword expression} expressions, and hybrid
processing with statistical methods\is{statistics}, variously funded by the National Science Foundation, the \ili{Scottish} government, and industrial partners including IBM and NTT.  At the turn of the millennium, Flickinger joined the software start-up boom, co-founding \isi{YY Software} funded through substantial venture capital to use the ERG for automated response to customer emails for e-commerce companies.  YY produced the first commercially viable software system using an HPSG implementation, processing email content in \ili{English} with the ERG and the PET parser \citep{callmeier00} which had been developed by Ulrich Callmeier at the DFKI, as well as in \ili{Japanese} with Jacy, further developed by Siegel\aimention{Melanie Siegel} and by Bender\aimention{Emily Bender}.  While technically capable, the product was not commercially successful enough to enable YY to survive the bursting of the dot-com bubble, and it closed down in 2003.  Flickinger returned to the LinGO project with a considerably more robust ERG, and soon picked up the translation application thread again, this time using the ERG for generation in the LOGON \ili{Norwegian}--\ili{English} \isi{machine translation} project \citep{Lon:Oep:Ber:04} based in Oslo.

\section{Research and teaching networks}

The first international conference on HPSG was held in 1993 in Columbus, Ohio, in conjunction with the Linguistic Society of America's Summer Institute.  The conference has been convened every year since then, with locations in Europe, Asia, and North America.  Two of these annual meetings have been held jointly with the annual Lexical Functional Grammar conference, in 2000 in Berkeley and in 2016 in Warsaw.  Proceedings of these conferences since 2000 are available on-line from CSLI Publications.\footnote{\url{http://csli-publications.stanford.edu/HPSG/}, 2021-01-15.}  Since 2003, HPSG researchers in Europe have frequently held a regional workshop in Bremen, Berlin, Frankfurt, or Paris, annually since 2012, to foster informal discussion of current work in HPSG.  These follow in the footsteps of European HPSG workshops starting with one on \ili{German} grammar, held in Saarbrücken in 1991, and including others in Edinburgh and Copenhagen in 1994, and in Tübingen in 1995.

In 1994, the HPSG mailing list was initiated,\footnote{Its archives can be found at \url{https://hpsg.hu-berlin.de/HPSG/MailingList}.} and from 1996 to 1998, the electronic newsletter, the HPSG Gazette,\footnote{\url{http://www.sfs.uni-tuebingen.de/~gazette}, 2021-01-15.} was distributed through the list, with its function then taken over by the HPSG mailing list.

Courses introducing HPSG to students became part of the curriculum during the late 1980s and early
1990s at universities in Osaka, Paris, Saarbrücken, Seoul, and Tübingen, along with Stanford
and OSU.  Additional courses came to be offered in Bochum, Bremen, Pittsburgh, Göttingen,
Heidelberg, Jena, Leuven, Potsdam, Seattle, Berlin, Essex, Buffalo, and Austin.  Summer courses and workshops on HPSG have also been offered since the early 1990s at the LSA Summer Institute in the U.S., including a course by Sag and Pollard on binding and control in 1991 in Santa Cruz, and at the European Summer School in Logic, Language and Information (ESSLLI), including a course by Pollard in Saarbrücken in 1991 on HPSG, a workshop in Colchester in 1992 on HPSG, a workshop in Prague in 1996 on \ili{Romance} (along with two HPSG-related student papers at the first-ever ESSLLI student session), and courses in 1998 in Saarbrücken on \ili{Germanic} syntax, grammar engineering, and unification-based formalisms, in 2001 on HPSG syntax, in 2003 on linearization grammars, and more since.  Also in 2001, a \ili{Scandinavian} summer school on constraint-based grammar was held in Trondheim.

%Several HPSG textbooks have been published, including at least \citet{Borsley91a,Borsley96a-u}, \citet{SagW99a-u}, \citet*{SWB2003a}, \citet{MuellerLehrbuch1,MuellerGTBuch2,MuellerGT-Eng1}, \citet{Kim2016a-u}, and \citet{Levine2017a-u}.
Several HPSG textbooks have been published, including at least \citet{Borsley91a,Borsley96a-u}, \citet{SagW99a-u}, \citet*{SWB2003a}, \citet{MuellerLehrbuch1,MuellerGTBuch2,MuellerGT-Eng4}, \citet{Kim2016a-u}, and \citet{Levine2017a-u}.

\section{Implementations and applications of HPSG}

The first implementation of a grammar in the HPSG framework emerged in the Hewlett-Packard Labs natural language project, for \ili{English}, with a lexical \isi{type hierarchy} \citep*{FPW85a}, a set of grammar rules that provided coverage of core syntactic phenomena including unbounded\is{unbounded dependency} dependencies and \isi{coordination}, and a semantic component called \isi{Natural Language Logic} \citep{LaubNerb1991}.  The corresponding parser for this grammar was implemented in Lisp \citep{PP85}, as part of a system called \isi{HP-NL} \citep{NerProud1987} which provided a natural language interface for \isi{querying relational databases}.  The grammar and parser were shelved when HP Labs terminated their natural language project in 1991, leading Sag and Flickinger to begin the LinGO project and development of the \ili{English} Resource Grammar at Stanford.

By this time, grammars in HPSG were being implemented in university research groups for several other languages, using a variety of parsers and engineering platforms for processing typed feature structure grammars.  Early platforms included the DFKI's DISCO system \citep{DISCO94} with a parser and graphical development tools, which evolved to the PAGE system; the ALE system \citep{Franz:90,CP96}, which evolved in Tübingen to TRALE \citep*{MPR2002a-u,Penn2004a-u}; and Ann Copestake's LKB\indexlkb \citep{Copestake2002a} which grew out of the ACQUILEX project.  Other early systems included ALEP within the Eurotra project \citep{SimpGron1994}, ConTroll at Tübingen \citep{GoetzMeurers1997}, CUF at IMS in Stuttgart \citep{DD93a-u}, CL-ONE at Edinburgh \citep{Manandhar1994}, TFS also at IMS \citep{Emele94a-u}, ProFIT at the University of Saarland \citep{Erbach95a}, Babel at Humboldt University in Berlin \citep{Babel}, and HDrug at Groningen \citep{NB97b-u}.

Relatively early broad-coverage grammar implementations in HPSG, in addition to the {English Resource Grammar}\is{English Resource Grammar (ERG)} at Stanford \citep{erg}, included one for \ili{German} at the DFKI \citep{MK2000a} and one for \ili{Japanese} (Jacy: \citealt{Siegel2000a}), all used in the \verbmobil machine translation project; a separate \ili{German} grammar \citep{Babel,Mueller99a}; a \ili{Dutch} grammar in Groningen \citep*{BvNM2001a-u}; and a separate \ili{Japanese} grammar in Tokyo \citep{MNT2005a-u}.  Moderately large HPSG grammars were also developed during this period for \ili{Korean} \citep{KY2003a-u} and for \ili{Polish} \citep*{myk:etal:02}.

In 1999, research groups at the DFKI, Stanford, and Tokyo set up a consortium called DELPH-IN
(Initiative for Deep Linguistic Processing in HPSG), to foster broader development of both grammars
and platform components, described in \citet*{OFTU2002a-ed}.  Over the next two decades, substantial
DELPH-IN grammars were developed for \ili{Norwegian} \citep{HH2004a-u}, \ili{Portuguese}
\citep{BrancoCosta2010}, and \ili{Spanish} \citep{MARIMON10.602}, along with moderate-coverage
grammars for \ili{Bulgarian} \citep{Osenova2011}, \ili{Greek} \citep{KN2005a-u}, \ili{Hausa}
\citep{Crysmann2012a-u}, \ili{Hebrew} \citep*{AHMW2015a-u}, \ili{Indonesian} \citep{MBS2015a-u},
\ili{Mandarin Chinese} \citep{FSB2015a-u}, \ili{Thai}, and \ili{Wambaya} \citep{Bender2008b-u}, all
described at \url{http://delph-in.net}.  Several of these grammars are based on the \isi{Grammar
  Matrix} \citep*{BFO2002a-u}, a starter kit generalized from the ERG and Jacy for rapid prototyping
of HPSG grammars, along with a much larger set of coursework
grammars.\footnote{\url{http://moin.delph-in.net/MatrixTop}, 2021-01-15.}  Out of this work has
grown the linguistically rich Grammar Matrix customization system \citep*{BDFPS2010a-u}, a set of
libraries of phenomena enabling a grammar developer to complete a questionnaire about
characteristics of a language to obtain a more effectively customized starting grammar.

Broad-coverage grammars developed in the \isi{TRALE} system \citep{MPR2002a-u,Penn2004a-u} include
\ili{German} \citep{MuellerLehrbuch1}, \ili{Danish} \citep{MOeDanish}, and \ili{Persian}
\citep{MuellerPersian}. Other TRALE grammars include \ili{Mandarin Chinese} \citep{ML2013a},
\ili{Georgian} \citep{Abzianidze2011a-u}, \ili{Maltese} \citep{MuellerMalteseSketch}, \ili{English}
\citep{MuellerLFGphrasal}, and \ili{Yiddish} \citep{MOe2011a}. Development of grammars in TRALE is
supported by the \isi{Grammix} system \citep{MuellerGrammix}; \citet{MuellerCoreGram} provides a
summary of this family of grammar implementations.

These grammars and systems have been used in a wide variety of applications, primarily as vehicles
for research in computational linguistics, but also for some commercial software products.  Research
applications already mentioned include \isi{database query} (HP Labs) and \isi{machine translation}
(\verbmobil and LOGON), with additional applications developed for use in \isi{anthology search}
\citep*{Sch:Kie:Spu:11}, \isi{grammar tutoring} in \ili{Norwegian} \citep*{Hellanetal:13},
\isi{ontology acquisition} \citep{Herb:Cope:06}, virtual \isi{robot control} \citep{packard2014uw},
visual \isi{question answering} \citep{DBLP:journals/corr/KuhnleC17}, and \isi{logic instruction}
\citep{Flickinger:17}, among many others.  Commercial applications include e-commerce\is{application!e-commerce customer
  email response} customer
  email response (for YY Software), and grammar\is{application!grammar correction} correction in education (for \isi{Redbird
  Advanced Learning}, now part of \isi{McGraw-Hill Education}: \citealt*{suppes2014teach}).  See
\crossrefchaptert{cl} for further discussion.

For most practical applications, some approximate solution to the challenge of \isi{parse selection}
(\isi{disambiguation}) must be provided, so developers of several of the DELPH-IN grammars,
including the ERG, follow the approach of \citet*{OFTM2004a-u}, which uses a manually-annotated
\isi{treebank} of sentences parsed by a grammar to train a \isi{statistical model} which is applied
at run-time to identify the most likely analysis for each parsed sentence.  These treebanks can also
serve as repositories of the analyses intended by the grammarian for the sentences of a corpus, and
some resources, notably the \isi{Alpino Treebank} \citep*{BvNM2001a-u}, include analyses which the
grammar may not yet be able to produce automatically.

\section{Prospects}

As we noted early in this chapter, HPSG's origins are rooted in the desire simultaneously to address
the theoretical concerns of linguists and the practical issues involved in building a useful natural
language processing system.  In the decades since the birth of HPSG, the mainstream of work in both
theoretical linguistics and NLP developed in ways that could not have been anticipated at the time.
NLP is now dominated by statistical methods, with almost all practical applications making use of
machine learning technologies.  It is hard to see any influence of research by linguists in most NLP
systems, though periodic workshops have helped to keep the conversation going.\footnote{For example,
  one on ``Building Linguistically Generalizable NLP Systems'' at the 2017 EMNLP conference in
  Copenhagen, and one on ``Relevance of Linguistic Structure in Neural NLP'' at the 2018 ACL
  conference in Melbourne.}  Mainstream grammatical theory, on the other hand, is now dominated by
the Minimalist Program\is{Minimalism} (MP), which is too vaguely formulated for a rigorous comparison with
HPSG.\footnote{Most work in MP is presented without precise definitions of the technical apparatus,
  but Edward Stabler and his collaborators have written a number of papers aimed at formalizing
  MP. See in particular \citet{CollStab2016}. \citet{Torr2019a-u} describes a large-scale
  implemented fragment in the framework of Minimalist Grammar. See \citew[177--180]{MuellerGT-Eng4}
  for a comparison of this fragment with HPSG. As Müller points out, many of the implementation
  techniques employed can be found in HPSG grammars, \eg discontinuous constituents and the
  \slasch-based approach to nonlocal dependencies.}   Concern with computational implementation
plays virtually no role in MP research; see \citet{MuellerGT-Eng1} for a discussion.

It might seem, therefore, that HPSG is further from the mainstream of both fields than it was at its inception, raising questions about how realistic the objectives of HPSG are.  We believe, however, that there are grounds for optimism.

With regard to implementations, there is no incompatibility between the use of HPSG and the machine learning methods of mainstream NLP.  Indeed, as noted above, HPSG-based systems that have been put to practical use have necessarily included components induced via statistical methods from annotated corpora.  Without such components, the systems cannot deal with the full variety of forms encountered in usage data.  On the other hand, existing NLP systems that rely solely on machine learning from corpora do not exhibit anything that can reasonably be called understanding of natural language.  Current technologies for machine translation, automatic summarization, and various other linguistic tasks fall far short of what humans do on these tasks, and are useful primarily as tools to speed up the tasks for the humans carrying them out.  Many NLP researchers are beginning to recognize that developing software that can plausibly be said to understand language will require representations of linguistic structure and meaning like those that are the stock in trade of linguists.  See \citet*{Bender2015LayersOI} for more discussion on sentence meaning.

\largerpage
Evidence for a renewed interest in linguistics among NLP researchers is the fact that major technology companies with natural language groups have recently begun (or in some cases, resumed) hiring linguists, and increasing numbers of new linguistics PhDs have taken jobs in the software industry.

In the domain of theoretical linguistics, it is arguable that the distance between HPSG and the mainstream of grammatical research (that is, MP) has narrowed, given that both crucially incorporate ideas from Categorial Grammar (see \citealt{RetStab2004}, \citealt{BE95a}, and \citealt{MuellerUnifying} for comparisons between MP and CG, for a general comparison of MP and HPSG see also \crossrefchapteralt{minimalism}). Rather than trying to make that argument, however, we will point to connections that HPSG has made with other work in theoretical linguistics.  Perhaps the most obvious of these is the work of Peter Culicover and Ray Jackendoff on what they call {\em{\isi{Simpler Syntax}}}.  Their influential 2005 book with that title \citep{CJ2005a} argues for a theory of grammar that differs little in its architecture and motivations from HPSG.

More interesting are the connections that have been forged between research in HPSG and work in Construction Grammar\indexcxg (CxG).  \citet[\page 36]{Fillmore88a} characterizes the notion  of \emph{construction} as ``any syntactic pattern which is assigned one or more conventional functions in a language, together with whatever is linguistically conventionalized about its contribution to the meaning or use of structures containing it.''  Among the examples that construction grammarians have described at length are \emph{the Xer, the Yer} (as in \emph{the older I get, the longer I sleep}), \emph{X let alone Y} (as in \emph{I barely got up in time to eat lunch, let alone cook breakfast}), and \emph{What's X doing Y?} (as in \emph{What's this scratch doing in the table?}).  As noted above and in \crossrefchaptert[\page \pageref{page-HPSG-always-was-constructional}, \pageref{cxg:page-HPSG-inheritance}]{cxg}, HPSG has incorporated the notion of construction since at least the late 1990s.

Nevertheless,\label{page-sbcg-start} work that labels itself CxG tends to look very different from HPSG.  This is in part because of the difference in their origins: many proponents of CxG come from the tradition of \isi{Cognitive Grammar} or typological studies, whereas HPSG's roots are in computational concerns. Hence, most of the CxG literature is not precise\is{formalization} enough to allow a straightforward comparison with HPSG, though the variants called Embodied Construction Grammar and Fluid Construction Grammar have more in common with HPSG; see \cites{MuellerFCG}[Sections~10.6.3--10.6.4]{MuellerGT-Eng4} for a comparison.  In the last years of his life, Ivan Sag sought to unify CxG and HPSG through collaboration with construction grammarians from the University of California, Berkeley, particularly Charles Fillmore\aimention{Charles Fillmore}, Paul Kay\aimention{Paul Kay}, and Laura Michaelis\aimention{Laura Michaelis}.  They developed a theory called \emph{Sign-Based Construction Grammar} (SBCG), which would combine the insights of CxG with the explicitness of HPSG.  \citet[\page 70]{Sag2012a} wrote, ``To readers steeped in HPSG theory, SBCG will no doubt seem like a minor variant of constructional HPSG.''  Indeed, despite the name change, the main feature of SBCG that differs from HPSG is that it posits an inheritance hierarchy of constructs, which includes feature structure descriptions for such partially lexicalized multi-word expressions as \emph{Ved X's way PP}, instantiated in such VPs as \textit{ad-libbed his way through a largely secret meeting}.  While\label{evolution:page-sbcg-vs-lingo} this is a non-trivial extension to HPSG, there is no fundamental change to the technical machinery.  In fact, it has been a part of the LinGO implementation for many years.

\largerpage
That said, there is one important theoretical issue that divides HPSG and SBCG from much other work in CxG.  That issue is \isi{locality}.  To constrain the formal power of the theory, and to facilitate computational tractability, SBCG adopts what \citet[\page 150]{Sag2012a} calls ``Constructional Localism'' and describes it as follows:  ``Constructions license mother-daughter configurations without reference to embedding or embedded contexts.''  That is, like phrase structure rules, constructions must be characterized in terms of a mother node and its immediate daughters.  At first glance, this seems to rule out analyses of many of the examples of constructions provided in the CxG literature.  But  \citet[\page 150]{Sag2012a} goes on to say, ``Constructional Localism does not preclude an account of nonlocal dependencies in grammar, it simply requires that all such dependencies be locally encoded in signs in such a way that information about a distal element can be accessed locally at a higher level of structure.''

\citet[\page 35]{Fillmore88a} wrote:
\begin{quote}
Construction grammars differ from phrase-structure grammars which use \emph{complex symbols} and
allow the \emph{transmission of information} between lower and higher structural units, in that we
allow the direct representation of the required properties of subordinate constituents.  (Should it
turn out that there are completely general principles for predicting the kinds of information that
get transmitted upwards or downwards, this may not be a real difference.) \hfill\citep[\page 35]{Fillmore88a}
\end{quote}
SBCG is committed to the position alluded to in the parenthetical sentence in this quote, namely, that general principles of information transmission within sentences make it possible to insist on Constructional Localism.   See \crossrefchaptert{cxg} for a much more detailed discussion, and \citet{VanEynde2015a} for a review of the 2012 SBCG book.\label{page-sbcg-end}

Finally, another point of convergence between work in HPSG and other work in both theoretical
linguistics and NLP is the increasing importance of corpus and experimental data. In the early years
of the HP NL project, the methodology was the same as that employed in almost all work in
theoretical syntax and semantics: the grammar was based entirely on examples invented by the
researchers.  At one point during the decade of the HP NL project, Flickinger, Pullum, and Wasow
compiled a list of sentences intended to exemplify many of the sentence types that they hoped the
system would eventually be able to analyze.  That list, 1328 sentences long, continues to be useful
as a test suite for the ERG, and is also used by various other NLP groups.  But it does not come
close to covering the variety of sentence forms that are found in corpora of speech and various
written genres.  As the goals of the HPSG implementations have broadened from database query to
dealing with ``language in the wild'', the use of corpora to test such systems and motivate
extensions to them has increased.  This parallels a development in other areas of linguistics, which
have also increasingly made use of large on-line corpora as sources of data and tests of their
theories.  This is a trend that we expect will continue.

Experimental data has been particularly important in the exploration of whether well-known
constraints on phenomena like extraction or ellipsis are really due to the grammar of natural
languages or the convergence of frequency, discourse factors, and aspects of human sentence
processing. \citet{HS2010a-u}, \citet{CD2019a-u}, and \citet{CP2020a-u}, for
example, have argued that many so-called island constraints are not grammatical in
nature. Similarly, \citet{SAHM2019a-u} claim that some parallelism
effects in \isi{Right Node Raising} are not grammatical in nature. Both lines of research lead to a
reduction of what grammars are responsible for and question the traditional division of labor
between the grammatical system, properties of the discourse within which utterances are embedded,
and processing considerations. We expect work along these lines to continue in the future (see also
\crossrefchapterw{processing} for the relation between HPSG and work in sentence processing).

In short, there are signs of convergence between work on HPSG and work in other areas, and it seems
plausible to think that the market for HPSG research will grow in the future.

\section*{\acknowledgmentsUS}

The work on this chapter by Flickinger was generously supported by a fellowship at the Oslo Center for Advanced Study at the \ili{Norwegian} Academy of Science and Letters.  The authors also thank several reviewers for their insightful and detailed comments on drafts of the chapter, including Emily M. Bender, Robert Borsley, Danièle Godard, Jean-Pierre Koenig and Stefan Müller.

{\sloppy
\printbibliography[heading=subbibliography,notkeyword=this]
}
\end{document}

%      <!-- Local IspellDict: en_US-w_accents -->

max_stars_repo_name: langsci/hpsg-handbook


text:
\documentclass[a4paper,11pt]{amsart}
\usepackage[utf8]{inputenc}\usepackage[T1]{fontenc}

\title{Deep Banana Eater -- A Deep Q-Network reinforcement learning agent}
\author{Julian Wergieluk}\address{}\email{julian.wergieluk@risklab.com}
\input{preamble}
\input{commands}

\usepackage[url=false,backend=biber]{biblatex}
\addbibresource{literature.bib}

\begin{document}

\maketitle

\begin{abstract}
This short note provides a concise description of the model architecture and
learning algorithms of the agent developed in this project. We also report learning
performance of the agent and provide a list of possible future model improvements.
\end{abstract}
\renewcommand*{\thefootnote}{}\footnote{\today{}}

\section{Description of the learning algorithm}

%Requirement: The report clearly describes the learning algorithm, along with the chosen hyperparameters. It also describes the model architectures for any neural networks.

The algorithm used to solve the problem posed in this project closely resembles
the algorithm proposed in \cite{mnih2015humanlevel}.

The agent is trained over a given number of episodes labeled with $n = 1,\cdots, 1800$.
Each episode is divided into turns $t = 1,\cdots, 300$.
The state space $\mathcal S$ of the environment is continuous and given by
$\mathcal S = \mathbb R^{37}$, whereas the action space $\mathcal A = \left\{
0,1,2,3 \right\}$ is discrete and independent of the current environment state
(i.e.\ all four actions are available irrespective of the current state). The state-action value
function $Q_{\theta}: \mathcal S \times \mathcal A \mapsto \mathbb R$ maps a
state-action pair to an estimated expected discounted cumulative reward
generated by an agent following a greedy policy $\pi_{\theta}$ derived from $Q_{\theta}$.
The parameter vector $\theta$ determining the state-action value function
$Q_{\theta}$ takes values in a finite-dimensional vector space $\mathbb R^{p}$.

We count the turns across the episodes of a training session using the variable $T =
300(n-1) + t$. At each turn $T$ during the training time the agent chooses an
action using an $\varepsilon$-greedy policy derived from $Q_{\theta(T)}$ and
$\varepsilon = \varepsilon(T) = \operatorname{exp}\left( -T \lambda \right)$ with
constant decay rate $\lambda = 0.00002$ (see Figure \ref{fig:epsilon}).

Also, at each turn $t<300$, the experience tuple $\left( S_{t}, A_{t}, R_{t+1}, S_{t+1}
\right)$ is saved to the replay buffer. If the turn number $t$ is divisible by
$4$ and the replay buffer contains more than $B=128$ saved tuples, the $Q$
function parameters $\theta$ are updated as follows: The algorithm
samples $B$ experience tuples (without replacements) from the replay buffer, and
for each tuple $(S_0, A_0, R_1, S_1)$ the following loss value
$L_\theta(S_0, A_0, R_1, S_1)$ is calculated
\begin{align*}
L_\theta(S_0, A_0, R_1, S_1) &= \left[
        R_1 + \gamma \operatorname{max_{a\in\mathcal A}} Q_{\theta}(S_1, a) -
        Q_{\theta}(S_0, A_0)
    \right]^2.
\end{align*}
Assume that for each $(s, a) \in \mathcal S \times \mathcal A$ the function
$\theta \mapsto Q_{\theta}(s,a)$ is differentiable. It follows that the
function $\theta\mapsto L_\theta(S_0, A_0, R_1, S_1)$ is also differentiable.
We can calculate the (total) derivative $\frac{d L}{d\theta}$ and use the ADAM
optimizer to update the parameter vector $\theta$ with the aim of minimizing
the loss $L_{\theta}$. We perform this minimization step for each experience
tuple in the sampled experience batch.

To ensure the validity of the minimization step, we use a deep neural network
with two fully connected layers to represent the function Q. The parameter
vector $\theta$ contains the weight and bias parameters of that neural network.

The neural network architecture is as follows:

\verbatiminput{qnet.txt}

\begin{table}
%\centering
\caption{List of hyperparameters and their values}
\begin{tabular}{|l|l|l|}
    \hline
Hyperparameter & Value \\
    \hline \hline
    Learning rate of the ADAM optimizer & 0.0005 \\
    Q-network update frequency & every 4 turns \\
    Replay buffer size & 100,000 \\
    Batch size & 128  \\
    Discount factor ($\gamma$) & 0.99 \\
    $\varepsilon$ & Decays from $1$ to $0$ with \\
    & the decay rate $\lambda = 0.00002$. \\
    \hline
\end{tabular}
\label{tab:hyperparameters}
\end{table}

\section{Training analysis}

Despite its simplicity, the agent described in this report is able to solve the
environment after completing less than $1000$ episodes. In fact, in a training
session depicted in Figure \ref{fig:avg-scores} the agent surpasses the average
cumulative score of $13$ around episode $900$ and reaches the average
cumulative reward of almost $16$ at the end of the training session.

\begin{figure}[tb]
    \centering
    \includegraphics[width=\textwidth]{{avg-scores}.png}
    \caption{Rolling window average of the cumulative reward for each episode
    in a training session consisting of $1800$ episodes. The threshold average
    cumulative reward of $13$ is reached around episode $900$.}
    \label{fig:avg-scores}
\end{figure}

\begin{figure}[tb]
    \centering
    \includegraphics[width=\textwidth]{{epsilon}.pdf}
    \caption{Decay of the $\varepsilon$ parameter as function the
    training episode number.}
    \label{fig:epsilon}
\end{figure}

\section{Ideas for future work}

The training performance of the agent could be improved by implementing some or
all of the ``rainbow'' improvements summarized in \cite{hessel2018rainbow}.  In
particular, the prioritized experience replay is easy to implement and would
likely lower the number of training episodes needed to reach the threshold of
13 reward points.

%\nocite{meucci2009review, goodman2007}
\printbibliography

\end{document}

% vim: spelllang=en_us:spell:

ext: tex


text:
\section{Part 8 Simulator}

Because of time constraints, I was not able to achieve anything with part 8.


text:
\subsection{Q-functions}

We can't use value functions, so we use Q-values instead.

\(Q(s,a)\) is the value of taking action \(a\) in state \(s\).

\(Q(s,a)=R_{s,a}+\gamma E_{s'}[max_{a'}Q(s',a')]\).

assigned to every action/state combination), to real. h on q tables, q-values

max_stars_repo_name: adamdboult/nodeHomePage

max_issues_repo_name: adamdboult/nodeHomePage

max_forks_repo_name: adamdboult/nodeHomePage


text:
\section{CUDA Rewrite}
The globs run on host memory. We tried to make it all CUDA (i.e. all arrays of the globs lying in device memory), but we could not get it to work. A problem with making it all CUDA is that it is very memory heavy, which might not be prefferable, but as this project was on optimizing only for the small test sample with focus on speed performance and less focus on memory efficiency, we argued that this could be more effecient. This should hovewer have been one of the last things to focus on, after having a running CUDA implementation, thus also making it possible to benchmark versus a glob lying on host memory.

The whole initialization of the globs is translated to CUDA kernels and works. This is placed in the \texttt{InitKernels.cu.h} file. The \texttt{updateParms} part of the sequential loop (before \texttt{rollback}) also runs on CUDA. Both these are parallelized to the outer most parallel loop (that is, until the main sequential loop) with degree of parallelism $outer$.  All loops are distributed across kernels of their specific parallelism degree.

\texttt{InitKernels.cu.h} contains several kernels, all with a maximum parallelization degree based on their loops, that is, between $outer\cdot numT$ for \texttt{initGritTimeline} to $outer\cdot numX \cdot numY$ for \texttt{setPayoff}. \texttt{updateParams} is parallel in $outer\cdot numX \cdot numY$ dimensions.

The kernels for \texttt{rollback} are placed in file \texttt{CoreKernels.cu.h}, but unfortunately contains some bugs. We tried to include them one by one, running the rest sequentially, without success due and time did not allow us to further debug it. But all kernels are created and some of them might even work.

Had time allowed it, we would have also liked to improve the \texttt{TRIDAG\_SOLVER} used as tridag kernel in \texttt{rollback}. Here, shared memory is limited and could be optimized e.g. maybe reusing \textit{mat\_sh} for \textit{lin\_sh}, as \textit{lin\_sh} is only used after the last use of \textit{mat\_sh} (so it is pretty straight forward). Also, it would be a point of optimization if $uu$ could be put in shared/tiled memory as it is firstly written to and then accessed in the previous index (which must be read from memory).