More DCGs

The code in this section includes extensions and bug-fixes to the Horn clause interpreter in Scheme and extensions to the DCG rule notation.

Specialized Predicates for the Horn interpreter

horn.scm includes code to manipulate specialized predicates. These predicates operate as "primitive" calls to the meta-language in which the interpreter is written. For example, the number? predicate is used to test whether an argument is a number in the Scheme underlying representation.

The specialized predicates are:

  1. number?
  2. atom?
  3. if
  4. word (see below explanation)
The important point is: we have a small interpreter for our language; it is easy to extend it when we need to - go ahead and extend it when needed!

In addition, simple tracing methods are implemented, which can be turned on and off using the functions:

  1. trace-goals
  2. untrace-goals
  3. trace-words
  4. untrace-words

Extended DCG Rules notations

The DCG rules notation is expanded with the following syntax: 
(rule (adjunct post noun ?agr ?x ?gap ?gap ?sem) ==>
  (:ex (the man) "visiting me" (the man) "visited by me")
  (:test (member ?infl (-ing passive)))
  (clause ?infl ?x ? ?v (gap (NP ?agr ? ?x)) (gap ()) ?sem))

(rule (opt-rel-pronoun ?case ?x ?int-subj (?type ?x)) ==>
  (:word ?rel-pro)
  (:test (word ?rel-pro rel-pro ?case ?type)))
The (:ex ....) notation is used to document rules. It shows examples. It is ignored in the translation into Horn clauses.

The (:word ...) can now appear in any position in the rules and more than one instance can appear in one rule.

The (:test ...) notation indicates calls to regular predicates - that do not "consume" words from the input sequence of words. Tests are used to filter the acceptable parses.

Hashtable-based Lexicon Implementation

When a few thousands words are added to the DCG, we hit performance issues when looking up words. To avoid this problem, the word lookup predicate is implemented in a special manner which looks up a word in a hashtable. The supporting code that populates the hashtable is provided in lexicon.scm.

CNF Normalization of Underspecified Logical Expressions

The code in normal.scm has been extended to normalize expressions that include "generalized quantifiers" such as ex, forall and more (see code in the function ->cnf).

Download

All the required code:
  1. utils.scm
  2. tell-ask.scm
  3. unify.scm
  4. normal.scm
  5. horn.scm
  6. dcg-rule.scm
  7. load.scm
Available grammars:
  1. grammar.scm: An midsize grammar based on Norvig (1991) Paradigms of AI Programming, Chapter 21.
  2. grammar.scm: example of sentences analyzed (or not) by the grammar.
  3. lexicon.scm: Code to manipulate a lexicon in an efficient manner.

Last modified July 10th, 2007