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.

Overview
Documentation
System Requirements
Obtaining ALE
ALE Grammars
Third-Party Interfaces
Teaching Materials
Mailing List and Feedback
User Project Reports
About ALE

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:

Bob Carpenter

The Logic of Typed Feature Structures

Cambridge University Press

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:

http://www.cs.toronto.edu/~gpenn/ale/files/

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
aleguide.ps.gz
aleguideA4.ps.gz
debugger.tar.gz
glue.tar.gz
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
ale31.pl
ale.qui.pl
ale31.swi.pl
debugger20.tar.gz

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)
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

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.