Method and system for eliminating operation codes from intermediate prolog instructions

• US 5,274,820 A
• Filed: 08/19/1992
• Issued: 12/28/1993
• Est. Priority Date: 08/14/1989
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gillet, Marc J. L.
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/932,906
• Time in Patent Office: 496 Days
• Field of Search: 395/700, 395/650, 395/375
• US Class Current: 717/139
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 9/3016 Decoding the operand specifier, e.g. specifier format
• CPC Class Codes: G06F 9/4496 Unification in logic programming

Abstract

An improved architecture for a Prolog interpreter is described. Implicit arguments are substituted for classical explicit arguments. The implicit arguments are supported by preassigned register allocation managed by the interpreter. The interpreter also exploits improved Prolog Object processing in which the first bit of the Prolog object word is used as a flag to indicate whether the object word is a type pointer or type descriptor. Significant improvements in interpreter execution result from the usage of these techniques.

Claims

1. A method for operating a computer system, having a processor and a memory, to process Prolog programs having predicates comprising the steps of:

(a) encoding, using the processor of the computer system, a predicate into a set of instructions stored in the memory of the computer system including a simplified instruction consisting of an address of an object and having preceding instructions;

(b) determining, using the processor of the computer system, an implied operation code for the simplified instruction from the preceding instructions by using a finite state automata having modes for read, write, built and arg to track the preceding instructions and select the implied operation code as unify constant in read and write modes, put constant in built mode and get constant in arg mode; and

(c) executing, using the processor of the computer system, the implied operation code using the address of the object as a parameter.

2. The method of claim 1 wherein the step of determining an implied operation code further includes using a finite state automata to track the context.

3. The method of claim 1, wherein the step of determining an implied operation code further includes using a finite state automata having modes for read, write, built and arg to track the context.

4. The method of claim 1, wherein the memory includes a plurality of Prolog registers, the step of encoding further including:

storing at least one unify_-- stack instruction and an associated argument, the unify_-- stack instruction having no Prolog register specified; and

storing at least one pop_-- structure F instruction, the pop_-- structure F instruction having no Prolog register specified;

whereby, the unify_-- stack and pop_-- structure F instructions are used in place of unify_-- variable and get_-- structure instructions having Prolog registers specified and the number of Prolog register references in the set of instructions stored for the predicate is reduced.

5. The method of claim 4, wherein the memory contains a stack, further comprising the steps of:

executing the unify_-- stack instruction by storing its associated argument on a stack; and

executing the pop_-- structure F instruction by popping a word from the stack;

thereby, reducing the number of Prolog register references in the set of instructions executed for the predicate.

6. The method of claim 1, wherein the step of encoding further includes storing the address of the object with a first bit equal to zero and storing all non-simplified instructions with a first bit equal to one, thereby making the simplified instruction distinguishable from non-simplified instructions.

7. A computer system, having a processor and a memory, for processing Prolog programs having predicates comprising:

(a) means for encoding, using the processor of the computer system, a predicate into a set of instructions stored in the memory of the computer system including a simplified instruction consisting of an address of an object and having preceding instructions;

(b) means for determining, using the processor of the computer system, an implied operation code for the simplified instruction from the preceding instructions using a finite state automata having modes for read, write, built and arg to track the preceding instructions and select the implied operation code as unify constant in read and write modes, put constant in built mode and get constant in arg mode; and

(c) means for executing, using the processor of the computer system, the implied operation code using the address of the object as a parameter.

8. The system of claim 7 wherein the means for determining an implied operation code further includes a finite state automata for tracking the context.

9. The system of claim 7, wherein the means for determining an implied operation code further includes a finite state automata having modes for read, write, built and arg to track the context.

10. The system of claim 7, wherein the memory includes a plurality of Prolog registers, the means for encoding further including:

means for storing at least one unify_-- stack instruction and an associated argument, the unify_-- stack instruction having no Prolog register specified; and

means for storing at least one pop_-- structure F instruction, the pop_-- structure F instruction having no Prolog register specified;

whereby, the unify_-- stack and pop_-- structure F instructions are used in place of unify_-- variable and get_-- structure instructions having Prolog registers specified and the number of Prolog register references in the set of instructions stored for the predicate is reduced.

11. The system of claim 10, wherein the memory contains a stack, further comprising:

means for executing the unify_-- stack instruction by storing its associated argument on a stack; and

means for executing the pop_-- structure F instruction by popping a word from the stack;

whereby, the number of explicit register references in the set of instructions executed for the predicate is reduced.

12. The system of claim 7 wherein the means for encoding further includes means for storing the address of the object with a first bit equal to zero, and means for storing all non-simplified instructions with a first bit equal to one, thereby making the simplified instruction distinguishable from non-simplified instructions.