Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
   /*
    * Copyright The Sett Ltd, 2005 to 2014.
    *
    * Licensed under the Apache License, Version 2.0 (the "License");
    * you may not use this file except in compliance with the License.
    * You may obtain a copy of the License at
    *
    *     http://www.apache.org/licenses/LICENSE-2.0
    *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package com.thesett.aima.logic.fol.wam.compiler;
  
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Map;
  import java.util.Queue;
  import java.util.Set;
  import java.util.TreeMap;
  import java.util.TreeSet;
  
  import static com.thesett.aima.logic.fol.wam.compiler.WAMInstruction.REG_ADDR;
  import static com.thesett.aima.logic.fol.wam.compiler.WAMInstruction.STACK_ADDR;
WAMCompiled implements a compiler for the logical language, WAM, into a form suitable for passing to an com.thesett.aima.logic.fol.wam.machine.WAMMachine. The WAMMachine accepts sentences in the language that are compiled into a byte code form. The byte instructions used in the compiled language are enumerated as constants in the WAMInstruction class.

The compilation process is described in "Warren's Abstract Machine, A Tutorial Reconstruction, by Hassan Ait-Kaci" and is followed as closely as possible to the WAM compiler given there. The description of the L0 compilation process is very clear in the text but the WAM compilation is a little ambiguous. It does not fully describe the flattening process and presents some conflicting examples of register assignment. (The flattening process is essentially the same as for L0, except that each argument of the outermost functor is flattened/compiled independently). The register assignment process is harder to fathom, on page 22, the register assignment for p(Z, h(Z,W), f(W)) is presented with the following assignment given:

 A1 = Z
 A2 = h(A1,X4)
 A3 = f(X4)
 X4 = W
 
In figure 2.9 a compilation example is given, from which it can be seen that the assignment should be:
 A1 = Z (loaded from X4)
 A2 = h(X4,X5)
 A3 = f(X5)
 X4 = Z
 X5 = W
 

From figure 2.9 it was concluded that argument registers may only be assigned to functors. Functors can be created on the heap and assigned to argument registers directly. Argument registers for variables, should be loaded from a separate register assigned to the variable, that comes after the argument registers; so that a variable assignment can be copied into multiple arguments, where the same variable is presented multiple times in a predicate call. The register assignment process is carried out in two phases to do this, the first pass covers the argument registers and the arguments of the outermost functor, only assigning to functors, the second pass continues for higher numbered registers, starts again at the beginning of the arguments, and assigns to variables and functors (not already assigned) as for the L0 process.

A brief overview of the compilation process is:

  • Terms to be compiled are allocated registers, breadth first, enumerating from outermost functors down to innermost atoms or variables.
  • The outermost functor itself is treated specially, and is not allocated to a register. Its i arguments are allocated to registers, and are additionally associated with the first i argument registers. The outermost functor is the instigator of a call, in the case of queries, or the recipient of a call, in the case of programs.
  • Queries are 'flattened' by traversing each of their arguments in postfix order of their functors, then exploring the functors arguments.
  • Programs are 'flattened' by traversing each of their arguments breadth first, the same as for the original register allocation, then exploring the functors arguments.

Query terms are compiled into a sequence of instructions, that build up a representation of their argument terms, to be unified, on the heap, and assigning registers to refer to those terms on the heap, then calling the matching program for the query terms name and arity. Program terms are compiled into a sequence of instructions that, when run against the argument registers, attempt to unify all of the arguments with the heap.

The effect of flattening queries using a post fix ordering, is that the values of inner functors and variables are loaded into registers first, before their containing functor is executed, which writes the functor and its arguments onto the heap. Programs do not need to be expanded in this way, they simply match functors followed by their arguments against the heap, so a breadth first traversal is all that is needed.

Evaluating a flattened query consists of doing the following as different query tokens are encountered:

  1. For the outermost functor, process all arguments, then make a CALL (functor) to the matching program.
  2. For a register associated with an inner functor, push an STR onto the heap and copy that cell into the register. A put_struc (functor, register) instruction is created for this.
  3. For a variable in argument position i in the outermost functor, push a REF onto the heap that refers to itself, and copy that value into that variables register, as well as argument register i. A put_var (register, register) instruction is emitted for this.
  4. For a register argument of an inner functor, not previously seen, push a REF onto the heap that refers to itself, and copy that cell into the register. A set_var (register) instruction is emitted for this.
  5. For a variables in argument position i in the outermost functor, previously seen, copy its assigned register into its argument register. A put_val (register, register) instruction is emitted for this.
  6. For a register argument previously seen, push a new cell onto the heap and copy into it the register's value. A set_val (register) instruction is emitted for this.

Evaluating a flattened program consists of doing the following as different program tokens are encountered:

  1. For the outermost functor, process all arguments, then execute a PROCEED instruction to indicate success.
  2. For a register associated with an inner functor, load that register with a reference to the functor. A get_struc (functor, register) instruction is created for this.
  3. For a variable in argument position i in the outermost functor, copy its argument register into its assigned register. A get_var (register, register) instruction is emitted for this.
  4. For a register argument of an inner functor, not previously seen, bind that register to its argument. A unify_var (register) instruction is output for this.
  5. For a variable in argument position i in the outermost functor, unify its assigned register with the argument register. A get_val (register, register) instruction is emitted for this.
  6. For a register argument of an inner functor, previously seen, unify that register against the heap. A unify_val (register) instruction is emitted for this.

CRC Card
Responsibilities Collaborations
Transform WAM sentences into compiled byte code. com.thesett.aima.logic.fol.wam.machine.WAMMachine, WAMCompiledPredicate

Author(s):
Rupert Smith
 
 public class InstructionCompiler extends DefaultBuiltIn
 {
    
Used for debugging.
 
     /* private static final Logger log = Logger.getLogger(InstructionCompiler.class.getName()); */

    
Holds a list of all predicates encountered in the current scope.
 
     protected Queue<SymbolKeypredicatesInScope = new LinkedList<SymbolKey>();

    
Holds the compiler output observer.
 
This is used to keep track of the number of permanent variables.
 
     protected int numPermanentVars;

    
This is used to keep track of the position of the cut level variable, for deep cuts, if there is one. -1 means no deep cut exists in the clause, and a value gte to zero means there is one, and references its slot.
 
     protected int cutLevelVarSlot = -1;

    
Keeps count of the current compiler scope, to keep symbols in each scope fresh.
 
     protected int scope = 0;

    
Holds the current nested compilation scope symbol table.
 
     private SymbolTable<IntegerStringObjectscopeTable;

    
Holds the instruction optimizer.
 
     private Optimizer optimizer;

    
Creates a new InstructionCompiler.

Parameters:
symbolTable The symbol table.
interner The machine to translate functor and variable names.
 
     protected InstructionCompiler(SymbolTable<IntegerStringObjectsymbolTableVariableAndFunctorInterner interner)
     {
         super(symbolTableinterner);
          = new WAMOptimizer(symbolTableinterner);
     }

    
 
     {
         this. = observer;
     }

    
 
     public void endScope() throws SourceCodeException
     {
         // Loop over all predicates in the current scope, found in the symbol table, and consume and compile them.
         for (SymbolKey predicateKey = .poll(); predicateKey != null;
                 predicateKey = .poll())
         {
             List<ClauseclauseList = (List<Clause>) .get(predicateKey.);
 
             // Used to keep track of where within the predicate the current clause is.
             int size = clauseList.size();
             int current = 0;
             boolean multipleClauses = size > 1;
 
             // Used to build up the compiled predicate in.
             WAMCompiledPredicate result = null;
 
             for (Iterator<Clauseiterator = clauseList.iterator(); iterator.hasNext(); iterator.remove())
             {
                 Clause clause = iterator.next();
 
                 if (result == null)
                 {
                     result = new WAMCompiledPredicate(clause.getHead().getName());
                 }
 
                 // Compile the single clause, adding it to the parent compiled predicate.
                 compileClause(clauseresultcurrent == 0, current >= (size - 1), multipleClausescurrent);
                 current++;
             }
 
             // Run the optimizer on the output.
             result = .apply(result);
 
             displayCompiledPredicate(result);
             .onCompilation(result);
 
             // Move up the low water mark on the predicates table.
             .setLowMark(predicateKey.);
         }
 
         // Clear up the symbol table, and bump the compilation scope up by one.
          = null;
         ++;
     }

    

Compiles a sentence into a binary form, that provides a Java interface into the compiled structure.

The clausal sentence may be a query, or a program statement. If it is a query, it is compiled immediately. If it is a clause, it is retained against the predicate which it forms part of, and compiled on the endScope() method is invoked.

 
     public void compile(Sentence<Clausesentencethrows SourceCodeException
     {
         /*log.fine("public WAMCompiledClause compile(Sentence<Term> sentence = " + sentence + "): called");*/
 
         // Extract the clause to compile from the parsed sentence.
         Clause clause = sentence.getT();
 
         // Classify the sentence to compile by the different sentence types in the language.
         if (clause.isQuery())
         {
             compileQuery(clause);
         }
         else
         {
             // Initialise a nested symbol table for the current compilation scope, if it has not already been.
             if ( == null)
             {
                  = .enterScope();
             }
 
             // Check in the symbol table, if a compiled predicate with name matching the program clause exists, and if
             // not create it.
             SymbolKey predicateKey = .getSymbolKey(clause.getHead().getName());
             List<ClauseclauseList = (List<Clause>) .get(predicateKey.);
 
             if (clauseList == null)
             {
                 clauseList = new LinkedList<Clause>();
                 .put(predicateKey.clauseList);
                 .offer(predicateKey);
             }
 
             // Add the clause to compile to its parent predicate for compilation at the end of the current scope.
             clauseList.add(clause);
         }
     }

    
Compiles a program clause, and adds its instructions to a compiled predicate.

Parameters:
clause The source clause to compile.
compiledPredicate The predicate to add instructions to.
isFirst true iff the clause is the first in the predicate.
isLast true iff the clause is the last in the predicate.
multipleClauses true iff the predicate contains >1 clause.
clauseNumber The position of the clause within the predicate.
Throws:
com.thesett.common.parsing.SourceCodeException If there is an error in the source code preventing its compilation.
 
     private void compileClause(Clause clauseWAMCompiledPredicate compiledPredicateboolean isFirstboolean isLast,
         boolean multipleClausesint clauseNumberthrows SourceCodeException
     {
         // Used to build up the compiled clause in.
         WAMCompiledClause result = new WAMCompiledClause(compiledPredicate);
 
         // Check if the clause to compile is a fact (no body).
         boolean isFact = clause.getBody() == null;
 
         // Check if the clause to compile is a chain rule, (one called body).
         boolean isChainRule = (clause.getBody() != null) && (clause.getBody().length == 1);
 
         // Used to keep track of registers as they are seen during compilation. The first time a variable is seen,
         // a variable is written onto the heap, subsequent times its value. The first time a functor is seen,
         // its structure is written onto the heap, subsequent times it is compared with.
          = new TreeSet<Integer>();
 
         // This is used to keep track of the next temporary register available to allocate.
          = findMaxArgumentsInClause(clause);
 
         // This is used to keep track of the number of permanent variables.
          = 0;
 
         // This is used to keep track of the allocation slot for the cut level variable, when needed. -1 means it is
         // not needed, so it is initialized to this.
          = -1;
 
         // These are used to generate pre and post instructions for the clause, for example, for the creation and
         // clean-up of stack frames.
         SizeableLinkedList<WAMInstructionpreFixInstructions = new SizeableLinkedList<WAMInstruction>();
         SizeableLinkedList<WAMInstructionpostFixInstructions = new SizeableLinkedList<WAMInstruction>();
 
         // Find all the free non-anonymous variables in the clause.
         Set<VariablefreeVars = TermUtils.findFreeNonAnonymousVariables(clause);
         Set<IntegerfreeVarNames = new TreeSet<Integer>();
 
         for (Variable var : freeVars)
         {
             freeVarNames.add(var.getName());
         }
 
         // Allocate permanent variables for a program clause. Program clauses only use permanent variables when really
         // needed to preserve variables across calls.
         allocatePermanentProgramRegisters(clause);
 
         // Gather information about the counts and positions of occurrence of variables and constants within the clause.
         gatherPositionAndOccurrenceInfo(clause);
 
         // Labels the entry point to each choice point.
         FunctorName fn = .getFunctorFunctorName(clause.getHead());
         WAMLabel entryLabel = new WAMLabel(fnclauseNumber);
 
         // Label for the entry point to the next choice point, to backtrack to.
         WAMLabel retryLabel = new WAMLabel(fnclauseNumber + 1);
 
         // Create choice point instructions for the clause, depending on its position within the containing predicate.
         // The choice point instructions are only created when a predicate is built from multiple clauses, as otherwise
         // there are no choices to be made.
         if (isFirst && !isLast && multipleClauses)
         {
             // try me else.
             preFixInstructions.add(new WAMInstruction(entryLabel..,
                     retryLabel));
         }
         else if (!isFirst && !isLast && multipleClauses)
         {
             // retry me else.
             preFixInstructions.add(new WAMInstruction(entryLabel..,
                     retryLabel));
         }
         else if (isLast && multipleClauses)
         {
             // trust me.
             preFixInstructions.add(new WAMInstruction(entryLabel..));
         }
 
         // Generate the prefix code for the clause.
         // Rules may chain multiple, so require stack frames to preserve registers across calls.
         // Facts are always leafs so can use the global continuation point register to return from calls.
         // Chain rules only make one call, so also do not need a stack frame.
         if (!(isFact || isChainRule))
         {
             // Allocate a stack frame at the start of the clause.
             /*log.fine("ALLOCATE " + numPermanentVars);*/
             preFixInstructions.add(new WAMInstruction(..));
         }
 
         // Deep cuts require the current choice point to be kept in a permanent variable, so that it can be recovered
         // once deeper choice points or environments have been reached.
         if ( >= 0)
         {
             /*log.fine("GET_LEVEL "+ cutLevelVarSlot);*/
             preFixInstructions.add(new WAMInstruction(..,
                     (byte));
         }
 
         result.addInstructions(preFixInstructions);
 
         // Compile the clause head.
         Functor expression = clause.getHead();
 
         SizeableLinkedList<WAMInstructioninstructions = compileHead(expression);
         result.addInstructions(expressioninstructions);
 
         // Compile all of the conjunctive parts of the body of the clause, if there are any.
         if (!isFact)
         {
             Functor[] expressions = clause.getBody();
 
             for (int i = 0; i < expressions.lengthi++)
             {
                 expression = expressions[i];
 
                 boolean isLastBody = i == (expressions.length - 1);
                 boolean isFirstBody = i == 0;
 
                 Integer permVarsRemaining =
                     (Integer.get(expression.getSymbolKey(), .);
 
                 // Select a non-default built-in implementation to compile the functor with, if it is a built-in.
                 BuiltIn builtIn;
 
                 if (expression instanceof BuiltIn)
                 {
                     builtIn = (BuiltInexpression;
                 }
                 else
                 {
                     builtIn = this;
                 }
 
                 // The 'isFirstBody' parameter is only set to true, when this is the first functor of a rule.
                 instructions = builtIn.compileBodyArguments(expressioni == 0, fni);
                 result.addInstructions(expressioninstructions);
 
                 // Call the body. The number of permanent variables remaining is specified for environment trimming.
                 instructions =
                     builtIn.compileBodyCall(expressionisFirstBodyisLastBodyisChainRulepermVarsRemaining);
                 result.addInstructions(expressioninstructions);
             }
         }
 
         // Generate the postfix code for the clause. Rules may chain, so require stack frames.
         // Facts are always leafs so can use the global continuation point register to return from calls.
         if (isFact)
         {
             /*log.fine("PROCEED");*/
             postFixInstructions.add(new WAMInstruction(..));
         }
 
         result.addInstructions(postFixInstructions);
     }

    
Compiles a clause as a query. The clause should have no head, only a body.

Parameters:
clause The clause to compile as a query.
Throws:
com.thesett.common.parsing.SourceCodeException If there is an error in the source code preventing its compilation.
 
     private void compileQuery(Clause clausethrows SourceCodeException
     {
         // Used to build up the compiled result in.
         WAMCompiledQuery result;
 
         // A mapping from top stack frame slots to interned variable names is built up in this.
         // This is used to track the stack positions that variables in a query are assigned to.
         Map<ByteIntegervarNames = new TreeMap<ByteInteger>();
 
         // Used to keep track of registers as they are seen during compilation. The first time a variable is seen,
         // a variable is written onto the heap, subsequent times its value. The first time a functor is seen,
         // its structure is written onto the heap, subsequent times it is compared with.
          = new TreeSet<Integer>();
 
         // This is used to keep track of the next temporary register available to allocate.
          = findMaxArgumentsInClause(clause);
 
         // This is used to keep track of the number of permanent variables.
          = 0;
 
         // This is used to keep track of the allocation slot for the cut level variable, when needed. -1 means it is
         // not needed, so it is initialized to this.
          = -1;
 
         // These are used to generate pre and post instructions for the clause, for example, for the creation and
         // clean-up of stack frames.
         SizeableLinkedList<WAMInstructionpreFixInstructions = new SizeableLinkedList<WAMInstruction>();
         SizeableLinkedList<WAMInstructionpostFixInstructions = new SizeableLinkedList<WAMInstruction>();
 
         // Find all the free non-anonymous variables in the clause.
         Set<VariablefreeVars = TermUtils.findFreeNonAnonymousVariables(clause);
         Set<IntegerfreeVarNames = new TreeSet<Integer>();
 
         for (Variable var : freeVars)
         {
             freeVarNames.add(var.getName());
         }
 
         // Allocate permanent variables for a query. In queries all variables are permanent so that they are preserved
         // on the stack upon completion of the query.
         allocatePermanentQueryRegisters(clausevarNames);
 
         // Gather information about the counts and positions of occurrence of variables and constants within the clause.
         gatherPositionAndOccurrenceInfo(clause);
 
         result = new WAMCompiledQuery(varNamesfreeVarNames);
 
         // Generate the prefix code for the clause. Queries require a stack frames to hold their environment.
         /*log.fine("ALLOCATE " + numPermanentVars);*/
         preFixInstructions.add(new WAMInstruction(..,
                 (byte) ( & 0xff)));
 
         // Deep cuts require the current choice point to be kept in a permanent variable, so that it can be recovered
         // once deeper choice points or environments have been reached.
         if ( >= 0)
         {
             /*log.fine("GET_LEVEL "+ cutLevelVarSlot);*/
             preFixInstructions.add(new WAMInstruction(..,
                     (byte));
         }
 
         result.addInstructions(preFixInstructions);
 
         // Compile all of the conjunctive parts of the body of the clause, if there are any.
         Functor[] expressions = clause.getBody();
 
         // The current query does not have a name, so invent one for it.
         FunctorName fn = new FunctorName("tq", 0);
 
         for (int i = 0; i < expressions.lengthi++)
         {
             Functor expression = expressions[i];
             boolean isFirstBody = i == 0;
 
             // Select a non-default built-in implementation to compile the functor with, if it is a built-in.
             BuiltIn builtIn;
 
             if (expression instanceof BuiltIn)
             {
                 builtIn = (BuiltInexpression;
             }
             else
             {
                 builtIn = this;
             }
 
             // The 'isFirstBody' parameter is only set to true, when this is the first functor of a rule, which it
             // never is for a query.
             SizeableLinkedList<WAMInstructioninstructions = builtIn.compileBodyArguments(expressionfalsefni);
             result.addInstructions(expressioninstructions);
 
             // Queries are never chain rules, and as all permanent variables are preserved, bodies are never called
             // as last calls.
             instructions = builtIn.compileBodyCall(expressionisFirstBodyfalsefalse);
             result.addInstructions(expressioninstructions);
         }
 
         // Generate the postfix code for the clause.
         /*log.fine("DEALLOCATE");*/
         postFixInstructions.add(new WAMInstruction(..));
         postFixInstructions.add(new WAMInstruction(..));
 
         result.addInstructions(postFixInstructions);
 
         // Run the optimizer on the output.
         result = .apply(result);
 
         displayCompiledQuery(result);
 
         .onQueryCompilation(result);
     }

    
Examines all top-level functors within a clause, including any head and body, and determines which functor has the highest number of arguments.

Parameters:
clause The clause to determine the highest number of arguments within.
Returns:
The highest number of arguments within any top-level functor in the clause.
 
     private int findMaxArgumentsInClause(Clause clause)
     {
         int result = 0;
 
         Functor head = clause.getHead();
 
         if (head != null)
         {
             result = head.getArity();
         }
 
         Functor[] body = clause.getBody();
 
         if (body != null)
         {
             for (int i = 0; i < body.lengthi++)
             {
                 int arity = body[i].getArity();
                 result = (arity > result) ? arity : result;
             }
         }
 
         return result;
     }

    
Compiles the head of a clause into an instruction listing in WAM.

Parameters:
expression The clause head to compile.
Returns:
A listing of the instructions for the clause head in the WAM instruction set.
 
     private SizeableLinkedList<WAMInstructioncompileHead(Functor expression)
     {
         // Used to build up the results in.
         SizeableLinkedList<WAMInstructioninstructions = new SizeableLinkedList<WAMInstruction>();
 
         // Allocate argument registers on the body, to all functors as outermost arguments.
         // Allocate temporary registers on the body, to all terms not already allocated.
         allocateArgumentRegisters(expression);
         allocateTemporaryRegisters(expression);
 
         // Program instructions are generated in the same order as the registers are assigned, the postfix
         // ordering used for queries is not needed.
         QueueBasedSearchMethod<TermTermoutInSearch = new BreadthFirstSearch<TermTerm>();
         outInSearch.reset();
         outInSearch.addStartState(expression);
 
         Iterator<TermtreeWalker = Searches.allSolutions(outInSearch);
 
         // Skip the outermost functor.
         treeWalker.next();
 
         // Allocate argument registers on the body, to all functors as outermost arguments.
         // Allocate temporary registers on the body, to all terms not already allocated.
 
         // Keep track of processing of the arguments to the outermost functor as get_val and get_var instructions
         // need to be output for variables encountered in the arguments only.
         int numOutermostArgs = expression.getArity();
 
         for (int j = 0; treeWalker.hasNext(); j++)
         {
             Term nextTerm = treeWalker.next();
 
             /*log.fine("nextTerm = " + nextTerm);*/
 
             // For each functor encountered: get_struc.
             if (nextTerm.isFunctor())
             {
                 Functor nextFunctor = (FunctornextTerm;
                 int allocation =
                     (Integer.get(nextFunctor.getSymbolKey(), .);
 
                 byte addrMode = (byte) ((allocation & 0xff00) >> 8);
                 byte address = (byte) (allocation & 0xff);
 
                 // Ouput a get_struc instruction, except on the outermost functor.
                 /*log.fine("GET_STRUC " + interner.getFunctorName(nextFunctor) + "/" + nextFunctor.getArity() +
                     ((addrMode == REG_ADDR) ? ", X" : ", Y") + address);*/
 
                 WAMInstruction instruction =
                     new WAMInstruction(..addrModeaddress,
                         .getFunctorFunctorName(nextFunctor), nextFunctor);
                 instructions.add(instruction);
 
                 // For each argument of the functor.
                 int numArgs = nextFunctor.getArity();
 
                 for (int i = 0; i < numArgsi++)
                 {
                     Term nextArg = nextFunctor.getArgument(i);
                     allocation = (Integer.get(nextArg.getSymbolKey(), .);
                     addrMode = (byte) ((allocation & 0xff00) >> 8);
                     address = (byte) (allocation & 0xff);
 
                     /*log.fine("nextArg = " + nextArg);*/
 
                     // If it is register not seen before: unify_var.
                     // If it is register seen before: unify_val.
                     if (!.contains(allocation))
                     {
                         /*log.fine("UNIFY_VAR " + ((addrMode == REG_ADDR) ? "X" : "Y") + address);*/
 
                         .add(allocation);
 
                         instruction =
                             new WAMInstruction(..addrModeaddressnextArg);
 
                         // Record the way in which this variable was introduced into the clause.
                         .put(nextArg.getSymbolKey(), .,
                             .);
                     }
                     else
                     {
                         // Check if the variable is 'local' and use a local instruction on the first occurrence.
                         VarIntroduction introduction =
                             (VarIntroduction.get(nextArg.getSymbolKey(),
                                 .);
 
                         if (isLocalVariable(introductionaddrMode))
                         {
                             /*log.fine("UNIFY_LOCAL_VAL " + ((addrMode == REG_ADDR) ? "X" : "Y") +
                                 address);*/
 
                             instruction =
                                 new WAMInstruction(..addrModeaddress,
                                     nextArg);
 
                             .put(nextArg.getSymbolKey(), .null);
                         }
                         else
                         {
                             /*log.fine("UNIFY_VAL " + ((addrMode == REG_ADDR) ? "X" : "Y") + address);*/
 
                             instruction =
                                 new WAMInstruction(..addrModeaddress,
                                     nextArg);
                         }
                     }
 
                     instructions.add(instruction);
                 }
             }
             else if (j < numOutermostArgs)
             {
                 Variable nextVar = (VariablenextTerm;
                 int allocation = (Integer.get(nextVar.getSymbolKey(), .);
                 byte addrMode = (byte) ((allocation & 0xff00) >> 8);
                 byte address = (byte) (allocation & 0xff);
 
                 WAMInstruction instruction;
 
                 // If it is register not seen before: get_var.
                 // If it is register seen before: get_val.
                 if (!.contains(allocation))
                 {
                     /*log.fine("GET_VAR " + ((addrMode == REG_ADDR) ? "X" : "Y") + address + ", A" + j);*/
 
                     .add(allocation);
 
                     instruction =
                         new WAMInstruction(..addrModeaddress,
                             (byte) (j & 0xff));
 
                     // Record the way in which this variable was introduced into the clause.
                     .put(nextVar.getSymbolKey(), ..);
                 }
                 else
                 {
                     /*log.fine("GET_VAL " + ((addrMode == REG_ADDR) ? "X" : "Y") + address + ", A" + j);*/
 
                     instruction =
                         new WAMInstruction(..addrModeaddress,
                             (byte) (j & 0xff));
                 }
 
                 instructions.add(instruction);
             }
         }
 
         return instructions;
     }

    
Allocates stack slots where needed to the variables in a program clause. The algorithm here is fairly complex.

A clause head and first body functor are taken together as the first unit, subsequent clause body functors are taken as subsequent units. A variable appearing in more than one unit is said to be permanent, and must be stored on the stack, rather than a register, otherwise the register that it occupies may be overwritten by calls to subsequent units. These variables are called permanent, which really means that they are local variables on the call stack.

In addition to working out which variables are permanent, the variables are also ordered by reverse position of last body of occurrence, and assigned to allocation slots in this order. The number of permanent variables remaining at each body call is also calculated and recorded against the body functor in the symbol table using column SymbolTableKeys.SYMKEY_PERM_VARS_REMAINING. This allocation ordering of the variables and the count of the number remaining are used to implement environment trimming.

Parameters:
clause The clause to allocate registers for.
 
     private void allocatePermanentProgramRegisters(Clause clause)
     {
         // A bag to hold variable occurrence counts in.
         Map<VariableIntegervariableCountBag = new HashMap<VariableInteger>();
 
         // A mapping from variables to the body number in which they appear last.
         Map<VariableIntegerlastBodyMap = new HashMap<VariableInteger>();
 
         // Holds the variable that are in the head and first clause body argument.
         Set<VariablefirstGroupVariables = new HashSet<Variable>();
 
         // Get the occurrence counts of variables in all clauses after the initial head and first body grouping.
         // In the same pass, pick out which body variables last occur in.
         if ((clause.getBody() != null))
         {
             for (int i = clause.getBody().length - 1; i >= 1; i--)
             {
                 Set<VariablegroupVariables = TermUtils.findFreeVariables(clause.getBody()[i]);
 
                 // Add all their counts to the bag and update their last occurrence positions.
                 for (Variable variable : groupVariables)
                 {
                     Integer count = variableCountBag.get(variable);
                     variableCountBag.put(variable, (count == null) ? 1 : (count + 1));
 
                     if (!lastBodyMap.containsKey(variable))
                     {
                         lastBodyMap.put(variablei);
                     }
 
                     // If the cut level variable is seen, automatically add it to the first group variables,
                     // so that it will be counted as a permanent variable, and assigned a stack slot. This
                     // will only occur for deep cuts, that is where the cut comes after the first group.
                     if (variable instanceof Cut.CutLevelVariable)
                     {
                         firstGroupVariables.add(variable);
                     }
                 }
             }
         }
 
         // Get the set of variables in the head and first clause body argument.
         if (clause.getHead() != null)
         {
             Set<VariableheadVariables = TermUtils.findFreeVariables(clause.getHead());
             firstGroupVariables.addAll(headVariables);
         }
 
         if ((clause.getBody() != null) && (clause.getBody().length > 0))
         {
             Set<VariablefirstArgVariables = TermUtils.findFreeVariables(clause.getBody()[0]);
             firstGroupVariables.addAll(firstArgVariables);
         }
 
         // Add their counts to the bag, and set their last positions of occurrence as required.
         for (Variable variable : firstGroupVariables)
         {
             Integer count = variableCountBag.get(variable);
             variableCountBag.put(variable, (count == null) ? 1 : (count + 1));
 
             if (!lastBodyMap.containsKey(variable))
             {
                 lastBodyMap.put(variable, 0);
             }
         }
 
         // Sort the variables by reverse position of last occurrence.
         List<Map.Entry<VariableInteger>> lastBodyList =
             new ArrayList<Map.Entry<VariableInteger>>(lastBodyMap.entrySet());
         Collections.sort(lastBodyListnew Comparator<Map.Entry<VariableInteger>>()
             {
                 public int compare(Map.Entry<VariableIntegero1Map.Entry<VariableIntegero2)
                 {
                     return o2.getValue().compareTo(o1.getValue());
                 }
             });
 
         // Holds counts of permanent variable last appearances against the body in which they last occur.
         int[] permVarsRemainingCount = new int[(clause.getBody() != null) ? clause.getBody().length : 0];
 
         // Search the count bag for all variable occurrences greater than one, and assign them to stack slots.
         // The variables are examined by reverse position of last occurrence, to ensure that later variables
         // are assigned to lower permanent allocation slots for environment trimming purposes.
         for (Map.Entry<VariableIntegerentry : lastBodyList)
         {
             Variable variable = entry.getKey();
             Integer count = variableCountBag.get(variable);
             int body = entry.getValue();
 
             if ((count != null) && (count > 1))
             {
                 /*log.fine("Variable " + variable + " is permanent, count = " + count);*/
 
                 int allocation = (++ & (0xff)) | (. << 8);
                 .put(variable.getSymbolKey(), .allocation);
 
                 // Check if the variable is the cut level variable, and cache its stack slot in 'cutLevelVarSlot', so that
                 // the clause compiler knows which variable to use for the get_level instruction.
                 if (variable instanceof Cut.CutLevelVariable)
                 {
                     //cutLevelVarSlot = allocation;
                      =  - 1;
                     /*log.fine("cutLevelVarSlot = " + cutLevelVarSlot);*/
                 }
 
                 permVarsRemainingCount[body]++;
             }
         }
 
         // Roll up the permanent variable remaining counts from the counts of last position of occurrence and
         // store the count of permanent variables remaining against the body.
         int permVarsRemaining = 0;
 
         for (int i = permVarsRemainingCount.length - 1; i >= 0; i--)
         {
                 permVarsRemaining);
             permVarsRemaining += permVarsRemainingCount[i];
         }
     }

    
Allocates stack slots to all free variables in a query clause.

At the end of processing a query its variable bindings are usually printed. For this reason all free variables in a query are marked as permanent variables on the call stack, to ensure that they are preserved.

Parameters:
clause The clause to allocate registers for.
varNames A map of permanent variables to variable names to record the allocations in.
 
     private void allocatePermanentQueryRegisters(Clause clauseMap<ByteIntegervarNames)
     {
         // Allocate local variable slots for all variables in a query.
         QueryRegisterAllocatingVisitor allocatingVisitor =
             new QueryRegisterAllocatingVisitor(varNamesnull);
 
         PositionalTermTraverser positionalTraverser = new PositionalTermTraverserImpl();
         positionalTraverser.setContextChangeVisitor(allocatingVisitor);
 
         TermWalker walker =
             new TermWalker(new DepthFirstBacktrackingSearch<TermTerm>(), positionalTraverserallocatingVisitor);
 
         walker.walk(clause);
     }

    
Gather information about variable counts and positions of occurrence of constants and variable within a clause.

Parameters:
clause The clause to check the variable occurrence and position of occurrence within.
 
     private void gatherPositionAndOccurrenceInfo(Clause clause)
     {
         PositionalTermTraverser positionalTraverser = new PositionalTermTraverserImpl();
         PositionAndOccurrenceVisitor positionAndOccurrenceVisitor =
             new PositionAndOccurrenceVisitor(positionalTraverser);
         positionalTraverser.setContextChangeVisitor(positionAndOccurrenceVisitor);
 
         TermWalker walker =
             new TermWalker(new DepthFirstBacktrackingSearch<TermTerm>(), positionalTraverser,
                 positionAndOccurrenceVisitor);
 
         walker.walk(clause);
     }

    
Pretty prints a compiled predicate.

Parameters:
predicate The compiled predicate to pretty print.
 
     private void displayCompiledPredicate(WAMCompiledPredicate predicate)
     {
         // Pretty print the clause.
         StringBuffer result = new StringBuffer();
 
         WAMCompiledTermsPrintingVisitor displayVisitor =
             new WAMCompiledPredicatePrintingVisitor(result);
 
         TermWalkers.positionalWalker(displayVisitor).walk(predicate);
 
         /*log.fine(result.toString());*/
     }

    
Pretty prints a compiled query.

Parameters:
query The compiled query to pretty print.
 
     private void displayCompiledQuery(WAMCompiledQuery query)
     {
         // Pretty print the clause.
         StringBuffer result = new StringBuffer();
 
         WAMCompiledTermsPrintingVisitor displayVisitor =
             new WAMCompiledQueryPrintingVisitor(result);
 
         TermWalkers.positionalWalker(displayVisitor).walk(query);
        /*log.fine(result.toString());*/
    }

    
QueryRegisterAllocatingVisitor visits named variables in a query, and if they are not already allocated to a permanent stack slot, allocates them one. All named variables in queries are stack allocated, so that they are preserved on the stack at the end of the query. Anonymous variables in queries are singletons, and not included in the query results, so can be temporary.
    {
        
The symbol table.
        private final SymbolTable<IntegerStringObjectsymbolTable;

        
Holds a map of permanent variables to variable names to record the allocations in.
        private final Map<ByteIntegervarNames;

        
Creates a query variable allocator.

Parameters:
symbolTable The symbol table.
varNames A map of permanent variables to variable names to record the allocations in.
delegate The term visitor that this delegates to.
        public QueryRegisterAllocatingVisitor(SymbolTable<IntegerStringObjectsymbolTable,
            Map<ByteIntegervarNamesAllTermsVisitor delegate)
        {
            super(delegate);
            this. = symbolTable;
            this. = varNames;
        }

        

Allocates unallocated variables to stack slots.

        public void visit(Variable variable)
        {
            if (.get(variable.getSymbolKey(), .) == null)
            {
                if (variable.isAnonymous())
                {
                    /*log.fine("Query variable " + variable + " is temporary.");*/
                    int allocation = (++ & (0xff)) | ( << 8);
                    .put(variable.getSymbolKey(), .allocation);
                    .put((byteallocationvariable.getName());
                }
                else
                {
                    /*log.fine("Query variable " + variable + " is permanent.");*/
                    int allocation = (++ & (0xff)) | (. << 8);
                    .put(variable.getSymbolKey(), .allocation);
                    .put((byteallocationvariable.getName());
                }
            }
            super.visit(variable);
        }
    }
New to GrepCode? Check out our FAQ X