natural language toolkit logic peter wang updated by dan garrette dhgarrettegmail com c 20012023 nltk project url https www nltk org for license information see license txt an implementation of the hole semantics model following blackburn and bos representation and inference for natural language csli 2005 the semantic representations are built by the grammar hole fcfg this module contains driver code to read in sentences and parse them according to a hole semantics grammar after parsing the semantic representation is in the form of an underspecified representation that is not easy to read we use a plugging algorithm to convert that representation into firstorder logic formulas note that in this code there may be multiple types of trees being referred to 1 parse trees 2 the underspecified representation 3 firstorder logic formula trees 4 the search space when plugging search tree this class holds the brokendown components of a hole semantics i e it extracts the holes labels logic formula fragments and constraints out of a big conjunction of such as produced by the hole semantics grammar it then provides some operations on the semantics dealing with holes labels and finding legal ways to plug holes with labels constructor usr is a sem expression representing an underspecified representation structure usr a usr has the following special predicates alll v n existsl v n andl n n orl n n impl n n iffl n n predl v n v v where the brackets and star indicate zero or more repetitions leqn n holen labeln where l is the label of the node described by the predicate n is either a label or a hole and v is a variable return true if x is a node label or hole in this semantic representation extract holes labels formula fragments and constraints from the hole semantics underspecified representation usr the label is the first argument of the predicate return the set of labels which are not referenced directly as part of another formula fragment these will be the topmost labels for the subtree that they are part of return the hole that will be the top of the formula tree calculate and return all the legal pluggings mappings of labels to holes of this semantics given the constraints plug the nodes in queue with the labels in potentiallabels each element of queue is a tuple of the node to plug and the list of ancestor holes from the root of the graph to that node potentiallabels is a set of the labels which are still available for plugging plugacc is the incomplete mapping of holes to labels made on the current branch of the search tree so far record is a list of all the complete pluggings that we have found in total so far it is the only parameter that is destructively updated the node is a hole try to plug it the node is a label replace it in the queue by the holes and labels in the formula fragment named by that label try all possible ways of plugging a single hole see plugnodes for the meanings of the parameters add the current hole we re trying to plug into the list of ancestors try each potential label in this hole in turn is the label valid in this hole no more potential labels that must mean all the holes have been filled so we have found a legal plugging so remember it note that the queue might not be empty because there might be labels on there that point to formula fragments with no holes in them sanitycheckplugging will make sure all holes are filled recursively try to fill in the rest of the holes in the queue the label we just plugged into the hole could have holes of its own so at the end of the queue putting it on the end of the queue gives us a breadthfirst search so that all the holes at level i of the formula tree are filled before filling level i1 a depthfirst search would work as well since the trees must be finite but the bookkeeping would be harder return true if the label cannot be placed underneath the holes given by the set ancestors because it would violate the constraints imposed on it make sure that a given plugging is legal we recursively go through each node and make sure that no constraints are violated we also check that all holes have been filled return the firstorder logic formula tree for this underspecified representation using the plugging given this class represents a constraint of the form l n where l is a label and n is a node a label or a hole parse the sentence get the semantic feature from the top of the parse tree print the raw semantic representation skolemize away all quantifiers all variables become unique break the hole semantics representation down into its components i e holes labels formula fragments and constraints maybe show the details of the semantic representation find all the possible ways to plug the formulas together build fol formula trees using the pluggings print out the formulas in a textual format natural language toolkit logic peter wang updated by dan garrette dhgarrette gmail com c 2001 2023 nltk project url https www nltk org for license information see license txt an implementation of the hole semantics model following blackburn and bos representation and inference for natural language csli 2005 the semantic representations are built by the grammar hole fcfg this module contains driver code to read in sentences and parse them according to a hole semantics grammar after parsing the semantic representation is in the form of an underspecified representation that is not easy to read we use a plugging algorithm to convert that representation into first order logic formulas note that in this code there may be multiple types of trees being referred to 1 parse trees 2 the underspecified representation 3 first order logic formula trees 4 the search space when plugging search tree this class holds the broken down components of a hole semantics i e it extracts the holes labels logic formula fragments and constraints out of a big conjunction of such as produced by the hole semantics grammar it then provides some operations on the semantics dealing with holes labels and finding legal ways to plug holes with labels constructor usr is a sem expression representing an underspecified representation structure usr a usr has the following special predicates all l v n exists l v n and l n n or l n n imp l n n iff l n n pred l v n v v where the brackets and star indicate zero or more repetitions leq n n hole n label n where l is the label of the node described by the predicate n is either a label or a hole and v is a variable mapping of label formula fragment set of constraints return true if x is a node label or hole in this semantic representation extract holes labels formula fragments and constraints from the hole semantics underspecified representation usr the label is the first argument of the predicate return the set of labels which are not referenced directly as part of another formula fragment these will be the top most labels for the subtree that they are part of return the hole that will be the top of the formula tree it must be unique calculate and return all the legal pluggings mappings of labels to holes of this semantics given the constraints plug the nodes in queue with the labels in potential_labels each element of queue is a tuple of the node to plug and the list of ancestor holes from the root of the graph to that node potential_labels is a set of the labels which are still available for plugging plug_acc is the incomplete mapping of holes to labels made on the current branch of the search tree so far record is a list of all the complete pluggings that we have found in total so far it is the only parameter that is destructively updated the node is a hole try to plug it the node is a label replace it in the queue by the holes and labels in the formula fragment named by that label try all possible ways of plugging a single hole see _plug_nodes for the meanings of the parameters add the current hole we re trying to plug into the list of ancestors try each potential label in this hole in turn is the label valid in this hole no more potential labels that must mean all the holes have been filled so we have found a legal plugging so remember it note that the queue might not be empty because there might be labels on there that point to formula fragments with no holes in them _sanity_check_plugging will make sure all holes are filled recursively try to fill in the rest of the holes in the queue the label we just plugged into the hole could have holes of its own so at the end of the queue putting it on the end of the queue gives us a breadth first search so that all the holes at level i of the formula tree are filled before filling level i 1 a depth first search would work as well since the trees must be finite but the bookkeeping would be harder return true if the label cannot be placed underneath the holes given by the set ancestors because it would violate the constraints imposed on it make sure that a given plugging is legal we recursively go through each node and make sure that no constraints are violated we also check that all holes have been filled return the first order logic formula tree for this underspecified representation using the plugging given this class represents a constraint of the form l n where l is a label and n is a node a label or a hole parse the sentence get the semantic feature from the top of the parse tree print the raw semantic representation skolemize away all quantifiers all variables become unique break the hole semantics representation down into its components i e holes labels formula fragments and constraints maybe show the details of the semantic representation find all the possible ways to plug the formulas together build fol formula trees using the pluggings print out the formulas in a textual format
from functools import reduce

from nltk.parse import load_parser
from nltk.sem.logic import (
    AllExpression,
    AndExpression,
    ApplicationExpression,
    ExistsExpression,
    IffExpression,
    ImpExpression,
    LambdaExpression,
    NegatedExpression,
    OrExpression,
)
from nltk.sem.skolemize import skolemize










class Constants:
    ALL = "ALL"
    EXISTS = "EXISTS"
    NOT = "NOT"
    AND = "AND"
    OR = "OR"
    IMP = "IMP"
    IFF = "IFF"
    PRED = "PRED"
    LEQ = "LEQ"
    HOLE = "HOLE"
    LABEL = "LABEL"

    MAP = {
        ALL: lambda v, e: AllExpression(v.variable, e),
        EXISTS: lambda v, e: ExistsExpression(v.variable, e),
        NOT: NegatedExpression,
        AND: AndExpression,
        OR: OrExpression,
        IMP: ImpExpression,
        IFF: IffExpression,
        PRED: ApplicationExpression,
    }


class HoleSemantics:
    

    def __init__(self, usr):
        
        self.holes = set()
        self.labels = set()
        self.fragments = {}  
        self.constraints = set()  
        self._break_down(usr)
        self.top_most_labels = self._find_top_most_labels()
        self.top_hole = self._find_top_hole()

    def is_node(self, x):
        
        return x in (self.labels | self.holes)

    def _break_down(self, usr):
        
        if isinstance(usr, AndExpression):
            self._break_down(usr.first)
            self._break_down(usr.second)
        elif isinstance(usr, ApplicationExpression):
            func, args = usr.uncurry()
            if func.variable.name == Constants.LEQ:
                self.constraints.add(Constraint(args[0], args[1]))
            elif func.variable.name == Constants.HOLE:
                self.holes.add(args[0])
            elif func.variable.name == Constants.LABEL:
                self.labels.add(args[0])
            else:
                label = args[0]
                assert label not in self.fragments
                self.fragments[label] = (func, args[1:])
        else:
            raise ValueError(usr.label())

    def _find_top_nodes(self, node_list):
        top_nodes = node_list.copy()
        for f in self.fragments.values():
            
            args = f[1]
            for arg in args:
                if arg in node_list:
                    top_nodes.discard(arg)
        return top_nodes

    def _find_top_most_labels(self):
        
        return self._find_top_nodes(self.labels)

    def _find_top_hole(self):
        
        top_holes = self._find_top_nodes(self.holes)
        assert len(top_holes) == 1  
        return top_holes.pop()

    def pluggings(self):
        
        record = []
        self._plug_nodes([(self.top_hole, [])], self.top_most_labels, {}, record)
        return record

    def _plug_nodes(self, queue, potential_labels, plug_acc, record):
        
        if queue != []:
            (node, ancestors) = queue[0]
            if node in self.holes:
                
                self._plug_hole(
                    node, ancestors, queue[1:], potential_labels, plug_acc, record
                )
            else:
                assert node in self.labels
                
                
                args = self.fragments[node][1]
                head = [(a, ancestors) for a in args if self.is_node(a)]
                self._plug_nodes(head + queue[1:], potential_labels, plug_acc, record)
        else:
            raise Exception("queue empty")

    def _plug_hole(self, hole, ancestors0, queue, potential_labels0, plug_acc0, record):
        
        
        assert hole not in ancestors0
        ancestors = [hole] + ancestors0

        
        for l in potential_labels0:
            
            if self._violates_constraints(l, ancestors):
                continue

            plug_acc = plug_acc0.copy()
            plug_acc[hole] = l
            potential_labels = potential_labels0.copy()
            potential_labels.remove(l)

            if len(potential_labels) == 0:
                
                
                
                
                
                
                
                self._sanity_check_plugging(plug_acc, self.top_hole, [])
                record.append(plug_acc)
            else:
                
                
                
                
                
                
                
                
                self._plug_nodes(
                    queue + [(l, ancestors)], potential_labels, plug_acc, record
                )

    def _violates_constraints(self, label, ancestors):
        
        for c in self.constraints:
            if c.lhs == label:
                if c.rhs not in ancestors:
                    return True
        return False

    def _sanity_check_plugging(self, plugging, node, ancestors):
        
        if node in self.holes:
            ancestors = [node] + ancestors
            label = plugging[node]
        else:
            label = node
        assert label in self.labels
        for c in self.constraints:
            if c.lhs == label:
                assert c.rhs in ancestors
        args = self.fragments[label][1]
        for arg in args:
            if self.is_node(arg):
                self._sanity_check_plugging(plugging, arg, [label] + ancestors)

    def formula_tree(self, plugging):
        
        return self._formula_tree(plugging, self.top_hole)

    def _formula_tree(self, plugging, node):
        if node in plugging:
            return self._formula_tree(plugging, plugging[node])
        elif node in self.fragments:
            pred, args = self.fragments[node]
            children = [self._formula_tree(plugging, arg) for arg in args]
            return reduce(Constants.MAP[pred.variable.name], children)
        else:
            return node


class Constraint:
    

    def __init__(self, lhs, rhs):
        self.lhs = lhs
        self.rhs = rhs

    def __eq__(self, other):
        if self.__class__ == other.__class__:
            return self.lhs == other.lhs and self.rhs == other.rhs
        else:
            return False

    def __ne__(self, other):
        return not (self == other)

    def __hash__(self):
        return hash(repr(self))

    def __repr__(self):
        return f"({self.lhs} < {self.rhs})"


def hole_readings(sentence, grammar_filename=None, verbose=False):
    if not grammar_filename:
        grammar_filename = "grammars/sample_grammars/hole.fcfg"

    if verbose:
        print("Reading grammar file", grammar_filename)

    parser = load_parser(grammar_filename)

    
    tokens = sentence.split()
    trees = list(parser.parse(tokens))
    if verbose:
        print("Got %d different parses" % len(trees))

    all_readings = []
    for tree in trees:
        
        sem = tree.label()["SEM"].simplify()

        
        if verbose:
            print("Raw:       ", sem)

        
        while isinstance(sem, LambdaExpression):
            sem = sem.term
        skolemized = skolemize(sem)

        if verbose:
            print("Skolemized:", skolemized)

        
        
        hole_sem = HoleSemantics(skolemized)

        
        if verbose:
            print("Holes:       ", hole_sem.holes)
            print("Labels:      ", hole_sem.labels)
            print("Constraints: ", hole_sem.constraints)
            print("Top hole:    ", hole_sem.top_hole)
            print("Top labels:  ", hole_sem.top_most_labels)
            print("Fragments:")
            for l, f in hole_sem.fragments.items():
                print(f"\t{l}: {f}")

        
        pluggings = hole_sem.pluggings()

        
        readings = list(map(hole_sem.formula_tree, pluggings))

        
        if verbose:
            for i, r in enumerate(readings):
                print()
                print("%d. %s" % (i, r))
            print()

        all_readings.extend(readings)

    return all_readings


if __name__ == "__main__":
    for r in hole_readings("a dog barks"):
        print(r)
    print()
    for r in hole_readings("every girl chases a dog"):
        print(r)