The ALE Homepage
This page contains descriptions of the Attribute-Logic Engine (ALE), Version
3.2, a freeware logic programming and grammar parsing and generation system.
This includes information on obtaining the system, user's guide, graphical
interfaces, and grammars.
What's New
-
January, 2003: Bug fixed in SWI port of ALE 3.2.1 - compilation of grammar
source would fail in some circumstances.
-
December, 2001: ALE 3.2.1 is available. This
version patches ALE and its source-level debugger so that they work with
SICStus 3.8.6 and SWI 4.0.
-
June, 1999: ALE 3.2 is available. In this version:
-
ALE is faster (again), both at compile-time and run-time,
-
A new parsing compilation algorithm (Empty-First-Daughter closure),
which:
-
corrects a long-standing problem in ALE with combining empty categories
- EFD closure closes the phrase structure rules of a grammar under prefixes
of empty category daughters, so any permutation of empty categories can,
in principle, be combined to form a new empty category;
-
works around a problem that non-ISO-compatible Prologs, including SICStus
Prolog, have with asserted predicates that results in leftmost empty category
daughters not being able to combine with their own outputs;
-
allows parsers to establish a precondition that rules only need to be closed
with non-empty leftmost daughters at run-time - this allows ALE, at each
step in its right-to-left pass throught the string, to copy all of the
edges in the internal database back onto the heap before they can be used
again, and thus reduces edge copying to a constant 2 copies per edge for
non-empty edges (edges with different left and right nodes). Keeping a
copy of the chart on the heap also allows for more sophisticated indexing
strategies that would otherwise be overwhelmed by the cost of copying the
edge before matching. This puts to rest the misconception that Prolog-based
parsers are necessarily inefficient because of copying overhead.
-
Shallow cuts (if-then-else predicates) have been added to the definite
clause language
-
Faster extensionalisation code, particularly with grammars that
have few or no extensional types,
-
Faster subsumption checking code for chart edges,
-
ALE Source-level Debugger 3.0, which has been integrated with the
new SICStus 3.7 source-level debugger,
-
More compile-time error and warning messages,
-
Several bug corrections,
-
An updated user's manual,
-
An SWI Prolog port.
-
September, 1998: ALE 3.1 is available. In this version:
-
ALE is now substantially faster. Extensively revised code, making
better use of shallow cuts, first-argument indexing, and other tricks of
the Prolog trade,
-
A new, faster, term-expansion-based compiler. ALE now uses only
one zero-byte intermediate file to compile its intermediate code. Intermediate
code is saved for future use by saving the Prolog database itself,
-
ALE Source-level Debugger 2.0, which now supports semantic-head-driven
generation,
-
Lexicon compile/consult options (lex_compile/0, lex_consult/0).
Consulting the lexicon substantially reduces compilation time, with negligible
consequences at run-time for most grammars,
-
New commands to modify the lexicon incrementally (update_lex/1,
retract_lex/1). Also export_words/2, to write the words of a lexicon to
a stream,
-
New parsing commands to filter solutions through a description and
for batch parsing (rec/2,5, rec_best/2, rec_list/2,3),
-
Prolog character escapes can be used in conjunction with ALE,
-
Several bug corrections,
-
An updated user's manual,
-
An updated SWI Prolog port.
Contents
Overview
ALE 3.2, a freeware system written in Prolog by Bob
Carpenter, and Gerald Penn
integrates phrase structure parsing, semantic-head-driven generation and
constraint logic programming with typed feature structures as terms. This
generalizes both the feature structures of PATR-II and the terms of Prolog
II to allow type inheritance and appropriateness specifications for features
and values. Arbitrary constraints may be attached to types, and types may
be declared as having extensional structural identity conditions. Grammars
may also interleave unification steps with logic program goal calls (as
can be done in DCGs), thus allowing parsing to be interleaved with other
system components. ALE was developed with an eye toward Head-Driven
Phrase Structure Grammar (HPSG), but it can also execute PATR-II grammars,
definite clause grammars (DCGs), Prolog, Prolog-II, and LOGIN programs,
etc. With suitable coding, it can also execute several aspects of Lexical-Functional
Grammar (LFG).
The terms involved in ALE grammars and logic programs are specified
using a typed extension of Rounds-Kasper attribute-value logic, which includes
variables, full disjunction, inequations, and functional descriptions.
Programs are then compiled into low-level Prolog instructions corresponding
to the basic operations of the typed Rounds-Kapser logic. There is a strong
type discipline enforced on descriptions, allowing many errors to be detected
at compile-time.
The logic programming, parsing, and generating systems may be used independently
or together. Features of the logic programming system include negation,
disjunction and cuts. It has last call optimization, but does not perform
any argument indexing.
The phrase structure system employs a bottom-up, all-paths dynamic chart
parser. A general lexical rule component is provided, including procedural
attachment and general methods for orthographic transformations using pattern
matching or Prolog. Empty categories are permitted in the grammar. A mini-interpreter
is included for stepping through the parsing process. Both the phrase structure
and logic programming components of the system allow parametric macros
to be defined and freely employed in descriptions. The language allows
hooks to general Prolog routines, allowing the grammars and programs to
be embedded in Prolog, and thus also in C and Unix. Parser performance
is similar to that of the logic programming system.
The generation component also uses the phrase structure system plus
a user-defined semantics definite clause that identifies semantically relevant
information in feature structures. It uses an adaptation of the algorithm
presented in:
Shieber, S., van
Noord, G., Moore, R., and Pereira,
F. (1990). Semantic-head-driven
Generation.
Computational
Linguistics, 16.
This algorithm is very well suited to large-scale HPSG generation, since
it avoids the non-termination problems inherent to top-down processing
of lexicocentric theories, but at the same time, does not require the semantic
contribution of every daughter in a grammar rule to subsume some portion
of the semantic contribution of the mother, as, for example, is the case
with Earley-based strategies. Some example glue code is provided to show
how to attach two SICStus Prolog processes, one running a parser and one
running a generator, to build a simple machine translation with ALE.
The source-level debugger can be used to trace nearly every operation
in ALE's built-in parser, generator and definite clause resolver down to
the level of feature structure unification. Based upon the procedural box
model of control flow, it supports breakpoints, skipping, and leashing,
and is compatible with ALE's built-in chart interpreter for navigating
a parsing chart, as well as SICStus Prolog's own source-level debugger
for on-line debugging of Prolog hooks. When used with its XEmacs interface,
the buffer will indicate the current line being processed during execution.
In a future release, the ALE source-level debugger will be extended to
operations below the level of feature structure unification.
Documentation
Complete documentation for ALE 3.2.x (running to over 130 pages, with examples
of everything, programming advice, and sample grammars) is available in
postscript and LaTeX format in the general ALE release.
This document is also available in HTML format by clicking:
ALE 3.2 User's Guide, HTML Version (coming soon!)
ALE is based on the typed attribute-value logic and associated grammar
and constraint logic programming model developed in:
System Requirements
ALE was developed with SICStus Prolog 3.8.6, but only requires that if
the source-level debugger is used. For cyclic feature structures, at least
version 2.1#8 is required. ALE itself is rather compact and takes up about
300K when compiled. The size of grammar that can be compiled and string
that can be parsed will be determined by the size and structure of the
grammar itself.
The efficiency of the system depends on first-argument indexing, last-call
optimization, and for the chart parser, the indexing of dynamic clauses.
The system will be very slow if it is interpreted rather than compiled.
The ALE source-level debugger requires SICStus Prolog 3.8.6. Its XEmacs
interface requires XEmacs 20.3 or higher.
The SWI port of ALE can be run on SWI Prolog 4.0 or higher.
The Quinuts port of ALE 3.0 was the last port of ALE made to Quintus
Prolog. Its behaviour with cyclic feature structures is unpredictable;
and there are some hard restrictions on the number of variables in compiled
clauses that can make the development of grammars with large descriptions
in rules, lexical rules or the lexicon very difficult.
Obtaining ALE
ALE and its documentation are available on the GNU
Lesser General Public License. The components of the ALE system are
available at this address:
The contents of the directory are as follows; the grammars are described
in the ALE Grammars Section below.
-
ale.pl
-
The source code for ALE 3.2.1, for use with SICStus
Prolog 3.8.6.
-
ale.swi.pl
-
The SWI port of ALE 3.2.1, for use with SWI Prolog 4.0 or higher. To download
SWI Prolog, choose Unix
(version 4.0.11) or Windows
(version 4.0.9).
-
aleguide.ps.gz
-
User's guide in compressed postscript format for US letter paper
-
aleguideA4.ps.gz
-
User's guide in compressed postscript format for A4 paper
-
debugger.tar.gz
-
The ALE source-level debugger and XEmacs interface, for use with SICStus
3.8.6 and XEmacs 20.3 or higher.
-
glue.tar.gz
-
Example glue code files to attach two SICStus processes running ALE together
to build a simple machine translation system.
-
guide.tex
-
User's guide in LaTeX 2e format; also available online (soon) as ALE 3.2
User's Guide, HTML Version
-
figs.tar.gz
-
Some encapsulated postscript figures that you will need to latex guide.tex
yourself, along with the style file, epsf.sty
-
ale31.pl
-
The previous version of ALE (SICStus).
-
ale.qui.pl
-
The Quintus port of ALE 3.0.
-
ale31.swi.pl
-
The previous version of ALE, ported to SWI Prolog.
-
debugger20.tar.gz
-
The previous version of the source-level debugger and XEmacs interface,
for use with SICStus 3.0.6, and XEmacs 19.16 or higher.
ALE Grammars
Sample Grammars
The source code of the system is distributed with a number of sample grammars,
which are available at this address:
http://www.cs.toronto.edu/~gpenn/ale/files/grammars
The grammars, along with a description and their file names are as follows.
-
Metrical Phonology Syllabification Grammar (syllab.pl)
-
A small grammar for generating syllable structures of English words by
coding sonority contours, the maximal onset principle, and phonotactic
constraints via monostratal logical descriptions. (For more on constraint-based
phonology, see the Computational
Morphology and Phonology Page .)
-
Categorial Grammar with Cooper Storage (cg.pl)
-
A small unification categorial grammar with forward and backward slashes
illustrating the use of procedural attachments.
-
HPSG 2.0 (hpsg.pl)
-
A fairly comprehensive implementation of a Head-Driven
Phrase Structure Grammar for English, following (Pollard and Sag 1994:Chapters
1--5, 7, and 8). This grammar has changed one of its feature names as of
ALE 3.1, to work around a problem with SWI Prolog's operator parsing, and
now contains discontiguity declarations. For the purposes of benchmarking,
it behaves identically to the old hpsg.pl.
-
Sample Grammar from "Semantic-Head-Driven Generation" (gengram.pl)
-
The example grammar from the Computational Linguistics article of
Shieber et al., adapted to the logic of typed feature structures.
-
Zebra Puzzle (baby.pl)
-
Not a grammar per se, but rather a direct coding of a simplified version
of the Zebra Puzzle, a simple logic puzzle stated with constraints, for
illustrating the power of pure constraint resolution.
Third-Party User Interfaces
HDrug
The HDrug system, developed by Gertjan
van Noord, is a package for developing logic grammars implemented on
top of SICStus Prolog 3.0 or later, and Tcl/Tk. It has been tested on HP-UX,
Linux and Sun platforms. Information is available for it on the:
HDrug Homepage
HDrug has extensive features for performance evaluation, including plotting
of statistical information. It contains methods for viewing parses as they
are created, modifying them, and comparing them with other parses. It also
contains an on-line manual.
The HDrug release includes a number of utilities for grammar formalisms
other than ALE, including tree adjoining grammar, definite clause grammars,
categorial grammar, head-driven generation grammar, and extraposition grammars.
Also interesting is Gertjan's joint work with Gosse
Bouma on delayed evaluation for lexical rules in the context of an
HPSG grammar for Dutch.
The Pleuk Grammar Development Environment
For those using SICStus 2.1#9 running under X windows, the Pleuk grammar
development shell has been adapted for ALE. Pleuk is described in the following
technical report.
Calder, Jo (1993) Graphical Interaction with Constraint-Based Grammars.
In Proceedings of the First Conference of the Pacific Association for
Computational Linguistics (PACLING '93), Vancouver, BC, Canada. pps.
160--168.
Pleuk provides a graphical user interface, facilities for maintaining and
testing corpora, and an interactive, incremental derivation checker. Pleuk
is available free of charge from:
ftp://ftp.cogsci.ed.ac.uk/pub/pleuk
The file README contains instructions for downloading the system. Pleuk
has been ported to Sun SPARCs SunOS 4.* and HP-UX. For more information,
send e-mail to pleuk@cogsci.ed.ac.uk. Pleuk was developed by Jo
Calder and Chris Brew
of
the Human Communication Research Centre
(HCRC)
at the University of Edinburgh, Kevin Humphreys of the Centre for Cognitive
Science at the University of Edinburgh, and Mike Reape, of the Computer
Science Department, Trinity College, Dublin.
Emacs Interface
Olivier Laurens is distributing an Emacs-based interface to ALE. It is
described in a technical report (in compressed postscript format):
Laurens, Olivier (1995) An Emacs User Interface for ALE. Technical
Report CSS-IS TR 95-07, School of Computing Science, Simon Fraser University,
Burnaby, BC, Canada, June 1995. ftp://fas.sfu.ca/pub/cs/nl/emacs-ale/tr95-07.ps.Z
(20pps.)
It is also available free of charge for research purposes via ftp as a
compressed, tarred directory:
ftp://fas.sfu.ca/pub/cs/nl/emacs-ale/ale_emacs_1.tar.Z
Teaching Materials
Course on HPSG Grammars and Typed Feature Formalisms
December 11--14, 1995
Human Communication
Research Centre, University of Edinburgh
Course
Notes on HPSG in ALE, created by Colin Matheson, Centre
for Cognitive Science , University of
Edinburgh
Computational
Morphology: An Introduction to ALE-RA, created by Colin Matheson, Centre
for Cognitive Science, University of
Edinburgh. Based on the ALE-RA system, created by Tomaz Erjavec.
Mailing List and Feedback
Please send all bug reports to gpenn+@cmu.edu.
If you'd like to be put on the ALE mailing list and be informed of updates,
new grammars, and so on, send e-mail to Gerald Penn at gpenn+@cmu.edu.
If you would like to post to the ALE Mailing list, it can be found at:
+dist+~gpenn/dl/ale.dl@andrew.cmu.edu
You can alias this list to something more readable, or just click on the
address above to send a mail if your browser supports forms.
Please let us know if you have any comments, suggestions, or questions.
We'd be especially interested to hear what you are doing with ALE. As an
added bonus, if you would like, we can link your project into this page
so that other people can find out about it; just send us a description
and a URL if you have one.
ALE Users' Project Reports
Frederik Fouvry's report
on Dutch HPSG and his
thesis.
Ion Androutsopoulos'
thesis
on natural language interfaces to temporal databases, including prototype
source code.
About ALE
ALE was developed in the Computational Linguistics Program and the Language
Technologies Institute at Carnegie Mellon University by Bob
Carpenter and Gerald Penn.
The semantic-head-driven generator is based on a generator written for
ALE by Octav Popescu.
Gerald Penn, gpenn+@cmu.edu,
October 2003