8.7.2 NaiveClosure.ozf: Inferential Closure

The primary engine of our naïve parser is the computation of the inferential closure of an initial set of literals under application of a set of inference rules. There is nothing specific to parsing here and the question is then: how can we usefully abstract the notion of inference rule?

For our present purpose it suffices to model an inference rule as a function which takes a premise as argument and returns a list, possibly empty, of conclusions. Function Closure takes as inputs a list of Literals and a list of Rules where each element of the latter is a function as just described. Closure returns the corresponding inferential closure in the form of a list of literals.

The literals of the inferential closure are incrementally accumulated in a bag called Inferred. Notice also that we import agenda and bag functionality from the course library identified by URI x-ozlib://oz-kurs/Abstract.ozf.

<NaiveClosure.oz>=
functor 
export Closure
import 
   LIB(newAgendaFromList : NewAgendaFromList
       newBag            : NewBag)
   at 'x-ozlib://oz-kurs/Abstract.ozf' 
define 
   fun {Closure Literals Rules}
      Agenda   = {NewAgendaFromList Literals}
      Inferred = {NewBag}
   in 
      for break:Break do 
         if {Agenda.isEmpty} then {Break}
         else Lit = {Agenda.get} in 
            for Rule in Rules do 
               for Conc in {Rule Lit} do 
                  if {Not {Inferred.member Conc}} then 
                     {Inferred.put Conc}
                     {Agenda.put Conc}
                  end 
               end 
            end 
         end 
      end 
      {Inferred.toList}
   end 
end

The code above illustrate another aspect of the syntax of functors. So far, we had seen import specification of the form:

import LIB at 'x-ozlib://oz-kurs/Abstract.ozf'

We can be more precise, and state precisely what we wish to import from module LIB:

import 
   LIB(newAgendaFromList newBag) at 'x-ozlib://oz-kurs/Abstract.ozf'

which says that we intend to use only features newAgendaFromList and newBag from module LIB. An advantage of being so specific is that the compiler will produce an error if we attempt to use another feature of LIB. Why is this useful? Because it catches many typos, for example in the following code:

{LIB.newAgendaFrmList L}

where I typed Frm instead of From. For further convenience, we can also write:

import 
   LIB(newAgendaFromList : NewAgendaFromList
       newBag            : NewBag)
   at 'x-ozlib://oz-kurs/Abstract.ozf'

where we additionally introduce variables for some or all features. Thus we can use NewBag instead of LIB.newBag.


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.3.99 (20050412)