kites.logic
Class Decomposition

java.lang.Object
  extended by kites.logic.Decomposition

public class Decomposition
extends java.lang.Object

This class provides means for generating decompositions in two modes:

Decomposition for execution in program mode is performed at the same time as the rewrite and can therefore be found in ProgramRewrite. Non-deterministic decomposition is available in two different flavours: LO and RO. For a detailed description of execution modes and strategies please refer to my bachelor thesis.


Field Summary
static int M_NONDET
          Execution in non-deterministic mode
static int M_PROGRAM
          Execution in program mode
static int M_TRS
          Execution in term rewrite system mode
private  TRSFile rulelist
          The rulelist all decompositions are performed upon
static int S_LI
          Use LI decomposition
static int S_LO
          Use LO decomposition
static int S_RI
          Use RI decomposition
static int S_RO
          Use RO decomposition
 
Constructor Summary
Decomposition(TRSFile rulelist)
          Initialize the object with a rulelist
 
Method Summary
 java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> getDecomp(int type, int strategy, ASTNode instance)
          Find all possible nodes that can be rewritten and return them along with the rule that has to be used for performing the rewrite.
private  java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> liDecomp(ASTNode node)
          Find and perform a LI rewrite
private  java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> loDecomp(ASTNode node)
          Find and perform a LO rewrite
static java.util.HashMap<java.lang.String,ASTNode> match(ASTNode rule, ASTNode node)
          Checks whether two trees match.
private  java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> ndetDecomp(ASTNode node)
          This checks for all possible rewrites according to the non-deterministic decomposition rules.
private  java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> ndetLODecomp(ASTNode node, java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> matches)
          Calculate a leftmost-outermost decomposition for use with non-deterministic interpretation.
private  java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> ndetRODecomp(ASTNode node, java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> matches)
          Calculate a rightmost-outermost decomposition for use with non-deterministic interpretation.
private static java.util.HashMap<java.lang.String,ASTNode> realmatch(ASTNode rule, ASTNode node, java.util.HashMap<java.lang.String,ASTNode> map, java.util.HashMap<java.lang.String,ASTNode> nodeMap)
          The real implementation of the matching algorithm.
private  java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> riDecomp(ASTNode node)
          Find and perform a RI rewrite
private  java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> roDecomp(ASTNode node)
          Find and perform a RO rewrite
private  java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> trsDecomp(ASTNode node, java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> matches)
          Return possible rewrites in TRS mode - which is all possible rewrites.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

S_LO

public static final int S_LO
Use LO decomposition

See Also:
Constant Field Values

S_RO

public static final int S_RO
Use RO decomposition

See Also:
Constant Field Values

S_LI

public static final int S_LI
Use LI decomposition

See Also:
Constant Field Values

S_RI

public static final int S_RI
Use RI decomposition

See Also:
Constant Field Values

M_PROGRAM

public static final int M_PROGRAM
Execution in program mode

See Also:
Constant Field Values

M_NONDET

public static final int M_NONDET
Execution in non-deterministic mode

See Also:
Constant Field Values

M_TRS

public static final int M_TRS
Execution in term rewrite system mode

See Also:
Constant Field Values

rulelist

private TRSFile rulelist
The rulelist all decompositions are performed upon

Constructor Detail

Decomposition

public Decomposition(TRSFile rulelist)
Initialize the object with a rulelist

Parameters:
rulelist - The rulelist the decompositions shall be performed upon.
Method Detail

getDecomp

public java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> getDecomp(int type,
                                                                             int strategy,
                                                                             ASTNode instance)
                                                                      throws DecompositionException,
                                                                             SyntaxErrorException
Find all possible nodes that can be rewritten and return them along with the rule that has to be used for performing the rewrite.

Parameters:
type - The execution mode
instance - The instance to be rewritten
Returns:
Map of nodes and the rules which can be applied unto them
Throws:
DecompositionException - If a non-existing decomposition is to be used
SyntaxErrorException - If a syntax error in the RuleList or instance is encountered.

trsDecomp

private java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> trsDecomp(ASTNode node,
                                                                              java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> matches)
                                                                       throws SyntaxErrorException
Return possible rewrites in TRS mode - which is all possible rewrites.

Parameters:
node - The node to be checked. Initialize with root of tree.
matches - Map of possible rewrites that were already found. Initialize as empty.
Returns:
Map of nodes and the rules which can be applied unto them.
Throws:
SyntaxErrorException

ndetDecomp

private java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> ndetDecomp(ASTNode node)
                                                                        throws SyntaxErrorException
This checks for all possible rewrites according to the non-deterministic decomposition rules. Such a decomposition consists of all outermost rewrite possibilities.

Parameters:
node - The tree to be checked
Returns:
the mapping of nodes to rules that can be applied to them
Throws:
SyntaxErrorException

ndetLODecomp

private java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> ndetLODecomp(ASTNode node,
                                                                                 java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> matches)
                                                                          throws SyntaxErrorException
Calculate a leftmost-outermost decomposition for use with non-deterministic interpretation.

Parameters:
node - The tree to be checked
matches - A set of pre-existing matches
Returns:
the mapping of nodes to rules that can be applied to them
Throws:
SyntaxErrorException

ndetRODecomp

private java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> ndetRODecomp(ASTNode node,
                                                                                 java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> matches)
                                                                          throws SyntaxErrorException
Calculate a rightmost-outermost decomposition for use with non-deterministic interpretation.

Parameters:
node - The tree to be checked
matches - A set of pre-existing matches
Returns:
the mapping of nodes to rules that can be applied to them
Throws:
SyntaxErrorException

match

public static java.util.HashMap<java.lang.String,ASTNode> match(ASTNode rule,
                                                                ASTNode node)
                                                         throws SyntaxErrorException,
                                                                NoRewritePossibleException
Checks whether two trees match. A match is achieved if they are structurally equal and the symbols used match each other. The only exception are Variables which match everything including subtrees. Nevertheless, we carry a list of variable assignments around to check that we only assign them once and only one value (i. e. tree). It is perfectly possible to check for unifiability with this, as we also check the variables in the node tree as well. BUT: If you need a correct assignment of variables, the node tree HAS TO BE A GROUND TERM! This is not checked by this routine, so make sure of it yourself or variables WILL be assigned other variables as values!

Parameters:
rule - The rule (or tree 1)
node - The tree (or tree 2)
Returns:
true if both trees match, false otherwise
Throws:
SyntaxErrorException - on encountering an error in the tree
NoRewritePossibleException - when the trees do not match

realmatch

private static java.util.HashMap<java.lang.String,ASTNode> realmatch(ASTNode rule,
                                                                     ASTNode node,
                                                                     java.util.HashMap<java.lang.String,ASTNode> map,
                                                                     java.util.HashMap<java.lang.String,ASTNode> nodeMap)
                                                              throws SyntaxErrorException,
                                                                     NoRewritePossibleException
The real implementation of the matching algorithm. For more information see match

Parameters:
rule - the one tree (normally not ground)
node - the other tree (best if ground)
map - The mapping of variables of the rule parameter to values
nodeMap - The mapping of variables of the node parameter to values
Returns:
The mapping of variables of the rule parameter to values
Throws:
SyntaxErrorException - when an error in the tree was encountered
NoRewritePossibleException - when the trees do not match
See Also:
match(ASTNode, ASTNode)

liDecomp

private java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> liDecomp(ASTNode node)
                                                                      throws SyntaxErrorException
Find and perform a LI rewrite

Parameters:
node - The node to be checked (and possibly be rewritten) - Initialize with root node.
Returns:
The node can be rewritten
Throws:
SyntaxErrorException
NoChildrenException

loDecomp

private java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> loDecomp(ASTNode node)
                                                                      throws SyntaxErrorException
Find and perform a LO rewrite

Parameters:
node - The node to be checked (and possibly be rewritten) - Initialize with root node.
Returns:
The node that can be rewritten
Throws:
SyntaxErrorException
NoChildrenException

roDecomp

private java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> roDecomp(ASTNode node)
                                                                      throws SyntaxErrorException
Find and perform a RO rewrite

Parameters:
node - The node to be checked (and possibly be rewritten) - Initialize with root node.
Returns:
The node that can be rewritten
Throws:
SyntaxErrorException
NoChildrenException

riDecomp

private java.util.LinkedHashMap<ASTNode,java.util.LinkedList<Rule>> riDecomp(ASTNode node)
                                                                      throws SyntaxErrorException
Find and perform a RI rewrite

Parameters:
node - The node to be checked (and possibly be rewritten) - Initialize with root node.
Returns:
The node that can be rewritten
Throws:
SyntaxErrorException
NoChildrenException