Communication between prolog and an external process

Abstract

An improved architecture for a list processing language interpreter/compiler is described to facilitate two-way communication between list processing programs and other external processes. The new architecture employs a table driven approach to translate arguments from the list processing language to arguments that other external processes expect. Additional capability for accessing list processing programs from external processes is also provided.

Claims

What is claimed is:

1. Method for communicating information in a computer system between a program written in a first computer programming language and having an external reference to a subprogram and a subprogram having parameters including a computer programming language structure having at least one level, being written in a second computer programming language and resolving the external reference, the system having a memory and a processor, comprising the steps of:

(a) building, using the processor of the computer system, in the memory of the computer system, prior to execution of the program, linkage information associating the external reference to a routine and a parameter descriptor list in the subprogram, for communicating between the program and the subprogram, the parameter descriptors in the parameter descriptor list specifying the data type of each parameter and for each level in the computer programming language structure indicating the opening of the level of the computer programming language structure, the data type of elements in the level of the structure and the closing of the level of the computer programming language structure;

(b) converting, using the processor of the computer system, each parameter for the external reference into the data type specified in the parameter descriptors in the linkage information; and

(c) communicating, using the processor of the computer system, during execution of the program, the converted parameters from step (b) from the program to the subprogram.

2. Method as recited in claim 1, the converting step further including the step of changing a Prolog data type into a Fortran, COBOL, C, PL/1 or 370/XA Assembler data type.

3. Apparatus for communicating information between a program written in a first computer programming language and having an external reference to a subprogram and a subprogram written in a second computer programming language resolving the external reference and having parameters including a computer programming language structure having at least one level, the apparatus having a memory and a processor, comprising:

(a) means for building, in the memory using the processor of the computer system prior to execution of the program, linkage information associating the external reference to a routine and a parameter descriptor list in the subprogram, for communicating between the program and the subprogram, the parameter descriptors in the parameter descriptor list specifying the data type of each parameter and for each level in the computer programming language structure indicating the opening of the level of the computer programming language structure, the data type of elements in the level of the structure and the closing of the level of the computer programming language structure;

(b) means for converting, using the processor of the computer system, each parameter for the external reference into a data type specified in the parameter descriptor list; and

(c) means for communicating, using the processor of the computer system, during execution of the program the converted parameters generated by the means for converting, from the program to the subprogram.

4. Apparatus as recited in claim 3, the converting means further including means for changing a Prolog data type into a Fortran, COBOL, or C data type.

5. Method as recited in claim 1, wherein the program is written in Prolog.

6. Method as recited in claim 5, wherein the subprogram is written in Fortran, COBOL, C, PL/1 or Assembler.

7. Method as recited in claim 1, the converting step further comprising the step of determining, using the processor of the computer system, whether the data type specified in each parameter descriptor is one of the set comprising binary, floating point, character and array data types.

8. Method as recited in claim 1, further comprising the steps of:

communicating, using the processor of the computer system, return data from the subprogram to the program; and

interpreting, using the processor of the computer system, the return data as representative of success or failure of a predicate;

thereby, enabling the subprogram to function as a predicate in the program.

9. Method as recited in claim 1, further comprising the steps of:

communicating, using the processor of the computer system, return data from the subprogram to the program; and

interpreting, using the processor of the computer system, the return data as a value;

thereby, enabling the subprogram to function as an expression in the program.

10. A method for operating a computer system, having a memory and a processor, to process Prolog programs having predicates and expressions, and having an external reference to a subprogram written in a first computer programming language other than Prolog, the external reference having an input and an output parameter, the input parameter being a computer programming language structure having at least one level, the program and subprogram in the memory, comprising the steps of:

reading, using the processor of the computer system, a predicate list in the memory in the subprogram to find an executable address, an input parameter descriptor list and an output parameter descriptor for the external reference, the input parameter descriptor list indicating the opening of each level of the structure, the data types of elements in the structure and the closing of each level of the structure;

converting each element of the structure, using the processor of the computer system, from a Prolog data type into a converted input parameter having a data type for the first computer programming language, according to one of a set of predetermined procedures designated by each input parameter descriptor;

storing, using the processor of the computer system, each converted input parameter in the memory accessible to the subprogram;

calling, using the processor of the computer system, the executable address for the external reference with the converted input parameters, thereby generating the output parameter:

converting, using the processor of the computer system, the output parameter, into a converted output parameter in a Prolog data type according to one of a set of predetermined procedures designated by the output parameter descriptor; and

storing, using the processor of the computer system, the converted output parameter in the memory accessible to the Prolog program.

11. Method as recited in claim 10, wherein the subprogram is written in Fortran, COBOL, C, PL/1 or Assembler.

12. Method as recited in claim 10, the converting step further comprising the step of determining, using the processor of the computer system, whether the data type specified in the input parameter descriptor is one of the set comprising binary, floating point, character and array data types.

13. Method as recited in claim 10, further comprising the steps of:

associating, using the processor of the computer system, the converted output parameter with a Prolog predicate; and

processing, using the processor of the computer system, the Prolog predicate as succeeding or failing responsive to the contents of the output parameter:

thereby, enabling the subprogram to function as a predicate in the Prolog program.

14. Method as recited in claim 10, further comprising the step of using the processor of the computer system to treat, the converted output parameter as a Prolog expression; thereby, enabling the subprogram to perform numerical calculations for the Prolog program.

Description

FIELD OF THE INVENTION

This invention generally relates to improvements in a list processor interpreter/compiler and more particularly to a technique for accessing information from an external program. Capability for obtaining information in a list processor language from an external program is also disclosed.

BACKGROUND OF THE INVENTION

This invention is one of a set of improvements that have been made to create IBM's Prolog for the 370. As the name implies, the compiler has been optimized for IBM's 370/XA environment. However, the invention will perform equally well in any other thirty-two bit architecture. So, for example, the invention could be practiced on an Intel 80X86 processor or a Motorola 680X0.

The first Prolog interpreter was developed in France by Phillipe Roussel in 1972. His early work was expanded upon and first found a home on an IBM S/370 via work done at the University of Waterloo, Canada. A good summary of the history and content of the Prolog language is contained in a report by David H. D. Warren, "Implementing Prolog", DAI Research Report No. 39 (May 1977).

In his paper, Mr. Warren describes the two basic parts of the Prolog language: logical statements known as Horn clauses and a control language used by the programmer in constructing a proof. Section 4.1 discloses the Prolog Syntax and Terminology that is basic to the understanding of this invention. The language originated in formal proofs. So, for example, P.rarw.Q & R & S is interpreted as, P if Q and R and S. A careful reading of section 4.1 will acquaint the uninitiated reader with an appreciation of the Prolog syntax and major commands.

The Prolog instructions include: get, put, unify, procedural, and indexing instructions. A good summary of the Prolog instruction set is found in another article by Mr. Warren entitled, AN ABSTRACT PROLOG INSTRUCTION SET, Technical Note 309, SRI Project 4776 (October 1983). Mr. Warren's article describes the classical Prolog syntax that is accepted as standard to all Prolog Compilers/Interpreters. Further clarification of the Prolog language is found in, A TUTORIAL ON THE WARREN ABSTRACT MACHINE FOR COMPUTATIONAL LOGIC, Gabriel et al., Argonne National Laboratory (June 1985).

The classical Prolog system is referred to as the Warren Abstract Machine (WAM) in honor of its inventor. The architecture of the WAM is disclosed in Mr. Warren's, An Abstract Prolog Instruction Set. The invention is an improvement on the WAM to address some of the problems that Mr. Warren failed to address.

A recent U.S. Pat. No. 4,546,432 to NEC, entitled Prolog Processing System, discusses an efficient method for managing the registers associated with the various Prolog stacks. However, the patent fails to disclose a method for increasing the Prolog address space and improving overall performance by more effectively managing pointers.

A recent IBM U.S. Pat. No. 4,736,321 describes a communication method between an interactive language processor workspace and external processes. The invention only pertains to APL rather than a list processing language described in the subject invention. Further, like the rest of the prior art, the subject patent fails to teach any method for obtaining information from within a list processing language from another program.

As mentioned above, none of the prior art teaches a technique for providing two-way communication between a list processing language and an external process.

SUMMARY OF THE INVENTION

According to the invention, improvements in a Prolog compiler/interpreter are accomplished by adding two-way communication between a list processing language and an external process. The invention provides a set of tables containing translation information for converting Prolog arguments into arguments acceptable to other programming languages. Further, the invention provides a table-driven architecture for accessing Prolog information from other programming languages.

Data structures are employed in the conversion of data arguments from Prolog to other languages. The data structures and other processing described herein provide capability heretobefore unknown in Prolog.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing and other objects, aspects and advantages of the invention will be better understood from the following detailed description of the preferred embodiment of the invention with reference to the accompanying drawings, in which:

FIG. 1 shows a prior art Prolog record representing an object;

FIG. 2 depicts a Prolog word of type pointer in accordance with the present invention;

FIG. 3 depicts a Prolog word of type descriptor in accordance with the present invention;

FIG. 4 is a flowchart of a classical prior art approach to Prolog object processing;

FIG. 5 is a flowchart of Prolog object processing in accordance with the present invention;

FIG. 6 depicts a Prolog representation of a free variable in accordance with the present invention;

FIG. 7 depicts a Prolog constant in accordance with the present invention;

FIG. 8 depicts a Prolog skeleton in accordance with the present invention;

FIG. 9 illustrates a prior art Prolog get.sub.-- constant instruction;

FIG. 10 illustrates a Prolog get.sub.-- constant instruction in accordance with the present invention;

FIG. 11 shows a prior art Prolog put.sub.-- constant instruction;

FIG. 12 shows a Prolog put.sub.-- constant instruction in accordance with the present invention;

FIGS. 13A-13C are a flowchart depicting the logic of instruction processing in accordance with the present invention;

FIG. 14 is an illustration of a data structure employed in interrupt processing in accordance with the present invention;

FIGS. 15A-15F are a block diagrams showing the logic associated with adding interrupt processing to Prolog in accordance with the subject invention;

FIG. 16 is a correlation table of data types in various languages in accordance with the present invention;

FIG. 17 is a source listing of a C program in accordance with the present invention;

FIG. 18 is a source listing of the Prolog Proargs in accordance with the present invention;

FIG. 19 is an assembler source listing of the binary descriptor formats in accordance with the present invention;

FIG. 20 is a fortran source listing of the main program in accordance with the present invention;

FIG. 21 is a fortran source listing of a sample function in accordance with the present invention;

FIG. 22 illustrates the Prolog declaration of the fortran function STUPID in accordance with the present invention;

FIG. 23 is a listing of the execution of the fortran function STUPID in accordance with the present invention;

FIG. 24 is an example of descriptor declarations in accordance with the present invention;

FIG. 25 is an example of a descriptor file in accordance with the present invention;

FIG. 26 is an example of expressions in accordance with the present invention;

FIG. 27 is an example of a C program in accordance with the present invention;

FIG. 28 is an example of the Prolog to C include file in accordance with the present invention;

FIG. 29 is an example of the C code required in the C main program in accordance with the present invention;

FIG. 30 is a listing of the C text file for the CPLINK function in accordance with the present invention;

FIG. 31 is a listing of the C version of STUPID in accordance with the present invention;

FIG. 32 is a listing of the C execution of STUPID in accordance with the present invention;

FIG. 33 is an example of a Fortran to Prolog interface in accordance with the present invention;

FIG. 34 is an example of a C to Prolog interface in accordance with the present invention;

FIG. 35 is an example of a COBOL to Prolog interface in accordance with the present invention;

FIGS. 36A-36C are a flowchart showing the logic of the Prolog communication to external processes in accordance with the subject invention; and

FIGS. 37A-37C are a flowchart showing the logic of the external process communication to Prolog in accordance with the subject invention.

DETAILED DESCRIPTION OF THE INVENTION

Basic Prolog Architecture

Prolog is architected around four basic processes: 1) Recursive procedure calls, 2) Unification, 3) Backtracking, and 4) Cut Operation. Recursion requires proper stack management to function effectively. Unification is a powerful data handling method that encompasses both comparison and assignment instructions found in conventional programming languages. Unification is dependent on efficient data structure processing. This implies a dependency on pointers which means that any improvement in pointer management translates into enhanced execution.

Backtracking provides restoration of a previous computational environment. Backtracking is similar to the program context save and restore that transpires when an interrupt is processed by a typical operating system. Backtracking requires the efficient management of data structures in order to maintain Prolog system integrity and performance. Backtracking is generally implemented by maintaining a list of current changes. The execution of backtrack is to undo these changes. A similar function to the Prolog backtrack operation in a relational database environment is the "rollback" of a relational data base. The Cut operator commits Prolog processing to all computations performed up to the occurrence of the Cut operator.

A Prolog system is divided into a plurality of data areas. The first is the code area. This area is a read-only area containing the program's instructions and literals. The three major writable data areas of the machine are the local stack, global or heap stack and the trail stack. These three stacks are used as storage areas for the global and local variables and for Prolog system restoration. The global variables are long term variables that are defined by the user and remain active until processing is completed or backtracking and/or garbage collection retrieves the space for Prolog. The local variables are used as temporary storage cells to communicate information from one goal to another. Space can readily be recovered from the local stack when a goal completes and no alternatives remain. Stack manipulation requires efficient management of pointers.

The other writable area is a Last-In First-Out (LIFO) stack called the Trail. The trail is used to store the addresses of variable cells which require resetting to UNDEF when backtracking occurs. The trail grows in size in proportion to the number of goals. Trail size is diminished by backtracking. Registers are used to manage the various stack pointers unique to each of the stacks. Mr. Warren's report discusses the classical Prolog system management of the various stacks and their associated register pointers.

Garbage Collection

Garbage collection is the process whereby stack space is compacted, remapped and returned to the Prolog system to facilitate further processing.

Modern Prolog interpreters and compilers trace their origins to Mr. Warren's original work and to the improvements he has introduced incorporated into a classical standard for a Prolog system.

Instruction Set

Mr. Warren's report discusses the instructions and their syntax and illustrates the assembled code generated from Prolog statements. The description of the preferred embodiment diverges from the incompletely optimized code disclosed in Mr. Warren's report. As highlighted in the report, the Warren Prolog compiler required indirect addressing to acquire information. Thus a separate register must be used as an index register and the information from the instruction is used as an offset. The offset is added to the index register to obtain the effective address.

Prolog instructions are used to implement Prolog programs. Generally there is not a one to one correspondence of instructions and Prolog symbols in a classical Prolog Abstract Machine. A typical Prolog instruction consists of an operation code (opcode) with a plurality of operands. The opcode correlates the type of Prolog symbol with the context in which it occurs. The opcode occupies eight bits or one byte. The operands include small integers, offsets, and addresses. These operands in turn correspond to the various Prolog symbols. Depending on the specific Prolog implementation, operands might occupy a nibble, byte, word or double-word.

Data Objects

Referring to FIG. 1, a prior art Prolog data object is shown. It is represented by a tag field 10 and an address 20. The typical data object occupies thirty-two bits. The tag field distinguishes the type of the term, and must be at least two bits and more commonly eight bits or one byte. The main types are references, lists, structures, lists, skeletons, atoms, and integers. The eight bit tag field leaves only twenty-four bits of addressability. Thus, for example, in the 370/XA environment, full advantage of the thirty-one bit address space is not possible.

As opposed to Fortran, PL/1, COBOL, C and the like, that know about data, variables and assignment of values to the variables, Lisp and Prolog know about data, variables and binding. Variables are either free (no value) or bound (or instanciated). But once a variable in Prolog is instanciated, the variable cannot be re-instanciated, unless the variable is un-bound (by backtracking).

This powerful difference is exploited by Prolog's pattern matching. For example, in an operation of A=B where A and B are Prolog objects (possibly variables) tries to unify A and B. If A and B are variables, then the 2 variables become equivalent, and the unification succeeds. If A or B is a variable, then the variable becomes bound (instanciated to the other value), and the unification succeeds. If both A and B are data they are pattern matched to find them equal, possibly unifying recursively variables inside A and/or B. If that occurs, then the unification succeeds, otherwise it fails and a backtrack occurs.

This explains why the Prolog instruction, X=1, is a notation that binds X to 1 if X is an unbound variable, or checks that X is equal to 1 if X is Bound. A=B is internally performed by the Prolog system placing a pointer to A into B. B=C is accomplished by storing a pointer to B into C. C=hello is completed by putting the address of the atom "hello" into C. To obtain the value of B, the value of the two pointers must be resolved. The use of pointers permeates these steps as it likewise permeates Prolog processing. Thus, any improvement that can be made to pointer processing translates into significant improvements to Prolog execution.

FIG. 4 depicts the logic associated with pointer processing in accordance with the prior art. FIG. 5 depicts the logic associated with pointer processing in accordance with the subject invention. These figures are discussed in detail below.

Referring to FIG. 1, a prior art classical Prolog object word is shown. The first byte of information contains the tag field 10. The remaining bytes of information containing the address tag 20. The tag field 10 is an integer value that translates into various types of Prolog objects such as: pointer, free variable, constant (atom, integer, . . . ), or skeleton (Prolog list). The constant employs the address tag 20 as a pointer to the associated descriptor of the constant. The address tag 20 can contain an immediate data instead of an address. Small integers which fit into the space of the address tag 20 are usually represented this way.

The skeleton utilizes the address tag 20 as a pointer to the descriptor of the skeleton. This architecture is limited by the reduced size of the address tag 20 based on the one byte tag field 10. Thus, instead of exploiting a thirty-one bit address space, only twenty-four bit addressing is available. Some implementations of Prolog use a tag field of less than one byte, but none use a single bit because the tag field in classical Prolog must convey numbers ranging from one to sixteen. The one byte architecture is the most prevalent approach since most existing computers have instructions to fetch one byte, but very few computers have instructions to fetch 3 to 5 bits.

INVENTION ARCHITECTURE

Prolog objects are "tagged words" of one of the following types:

1) pointer to another tagged word;

2) free variable;

3) small integer;

4) associated to a Prolog object stored in the global stack (which implied the address field points to an object descriptor in the global stack); and

5) associated to a Prolog object stored in the code area (which implies the address field points to an object descriptor in the code area).

The Prolog system of the invention replaces every object of type "free variable" by an object of type pointer whose address field points to itself. It is easy to distinguish a pointer from a free variable, because a pointer never points to itself.

The processing of the subject invention requires a little more setup work in order to initialize the address field, and dereferencing processing requires an additional test. However, the most common set of instructions in Prolog, copying, is optimized.

In a classical Prolog system, to copy an object, the system is required to:

(a) check it is a free variable;

(b) yes, then the object is a pointer to the free variable; and

(c) no, then the copy is the object.

Employing this approach, the copy is always a simple copy.

Put a copy of the type of the object of categories (4 & 5) at the beginning of the object descriptor. This addition does not matter in the code area because it is static code and to add this byte to the objects of the global stack makes it possible to linearly browse the global stack, making garbage collection compaction easier. In each tagged object, except small integer, the address part of the object points to another pointer or to a tagged word.

The next step is to suppress the type small integer and to use only the type integer. The drawback is that a small integer is represented by only one pointer. This problem can be solved for very small integers by creating a table of them in constants area.

Now for each tagged object, the address part is a valid pointer pointing to another pointer or to a tagged word. Each tagged object is either:

1) of tag pointer; or

2) of another tag, which can be recovered using the value pointed to by the address field.

The tag field is no longer necessary because it can be recovered through the object descriptor. We need only to be able to distinguish between an object of type pointer, which will point to a pointer, and an object of type free variable which points to an object descriptor. This is accomplished by setting the high order bit of the object descriptor and by restricting the address space to 31 bits as described in detail below. The high order bit is used because it is the easiest to test on an MVS/XA machine, and it is not used in addressing. One skilled in the art will recognize that the low order bit could be substituted without undue experimentation.

The invention employs two kinds of object words illustrated in FIGS. 2 and 3. FIG. 2 shows an object of type pointer in accordance with the invention. The first bit 30 of the thirty-two bit word is a type field. The type field differentiates between object words of type pointer and type descriptor. If the bit is non-zero, then the type is descriptor. The next thirty-one bits of information 40 are the address of the Prolog object. Thus, the full address space of the 370/XA environment is exploited.

FIG. 3 represents a Prolog object word of type descriptor in accordance with the invention. The first bit 50 is set to one to indicate the descriptor type. The next seven bits are used in the classical Prolog approach as a tag field 60. The remaining twenty-four bits 70 vary based on the tag field's 60 value. Some examples are provided later to clarify the usage of the implementation of the various objects.

One of ordinary skill in compiler technology will readily comprehend the advantages gained through this architecture. A simple bit test will suffice to differentiate a Prolog object word of type pointer from any other object. Then, the address is already in executable form. This contrasts with the prior art technology where the tag field occupied eight bits.

An initial COMPARE operation was necessary to determine the type of the Prolog object word. Then, another AND operation was necessary to remove the tag field leaving only the twenty-four bits for an effective address. Thus, the full thirty-one bit address space could not be exploited, and additional processing overhead was associated with each pointer object. Since the pointer object is essential to Prolog processing, and one of the most commonly used objects, optimization of compiled and interpreted Prolog code was severly diminished.

The invention significantly reduces the overhead associated with Prolog pointer object processing. A simple test of the object word is completely determinate of the pointer's address. Thus, no further processing is necessary before the address is available for execution. The masked compare and the AND operation to strip the tag field is completely eliminated.

FIG. 4 is a flowchart showing an example of classical Prolog object processing. The example dereferences a Prolog object contained in register R.

Processing commences at function block 100 where the tag field contained in register R is loaded into the user-specified register X.

Then, in function block 102, the register X is tested to determine if it is a pointer or other type of object. If it is a pointer, then load register R with the twenty-four bit address in R and load the word of information at the address in R as the effective address of the pointer.

Alternately, if the test of the type indicates a variable, then a branch is made at 106 to a routine to process a Prolog variable. If the test of the type indicates an atom, then a branch is made at 108 to a routine to process a Prolog atom. If the test of the type indicates a skeleton, then a branch is made at 110 to process a Prolog skeleton.

FIG. 5 is a flowchart of the detailed logic associated with Prolog object processing in accordance with the subject invention. Function block 120 loads the word pointed to by register R into register X. Then, decision block 122 tests for a negative number in register X. If X is positive, then Prolog executes the statement "If X=R then goto out-var" in function block 124. The branch to "out-var" means that X contains a variable, so the information is processed as a variable at 126. Otherwise, the contents of register X are copied into register R at function block 128 and processing is complete.

If register X was initially negative, then at function block 130 the high order byte of X is loaded into the low order byte of register X and the high order three bytes are shifted out. Then, in function block 135, the type is tested to determine if it is an atom or a skeleton. If it is an atom, control is passed to an atom Prolog object processor at 140. If it is a skeleton, then control is passed to a skeleton Prolog object processor at 150.

FIG. 6 is a representation of a free variable in a Prolog object word in accordance with the present invention. Since a free variable in Prolog is actually a location in memory, the object is effectively an address. Thus, 200 is set to zero and the remaining thirty-one bits 210 are the effective address of the variable. This implies that a test of the Prolog object word will indicate that the object is an address and the information at the address can be processed as variable information. A substantial sayings in processing overhead is accomplished. Further, the effective storage area for variables is increased dramatically.

FIG. 7 is an example of a constant in a Prolog object word in accordance with the invention. The particular constant is a Prolog atom. Thus, the first bit 300 is set to zero to indicate the object is a pointer, and the remaining thirty-one bits 310 are an address to the data structure associated with the atom.

The data structure is stored in memory as shown at 311, 312, 313 and 314. The first bit 311 indicates that the object word is not an address. Thus, the next byte of information 312 is a tag field processed to determine the type of Prolog constant. In this case an atom. The bytes following (313 and 314) the tag field 312 vary depending on the type of Prolog constant. Even in a non-pointer object, processing advantage is available through exploitation of the Prolog object architecture in accordance with the invention.

FIG. 8 is an example of a skeleton in a Prolog object in accordance with the invention. A skeleton is represented as a pointer to a data structure containing information pertinent to the particular skeleton. Thus, the first bit 400 of the skeleton is set to zero to indicate that an address is contained in the remaining thirty-one bits 410. The address is used as a pointer to the data structure associated with the skeleton 411, 412, 414, 416, and 418.

The first bit of the data structure 411 is set to one to indicate that the next seven bits 412 are a tag field value. In this case the value indicates that the data structure is a skeleton. The remaining information 414, 416 and 418 is a classical Prolog skeleton data structure.

Implicit Arguments

In classical implementations of Prolog, such as the Prolog interpreter/compiler of Mr. Warren described earlier, instructions require the explicit recitation of a plurality of fields as illustrated in FIG. 9. So, for example, the code for the second argument of a (*,hello) instruction is get.sub.-- constant hello, A2 and is encoded as shown in FIG. 9.

The fields of the second argument of the instruction include code.sub.-- op 500, a reference to the register that is used for the operation 510, and an index to the constant 520. Each of the fields must be separately parsed to verify the correct information was provided. Also, an index field, like 520, requires the value contained in the index field be added to the appropriate offset register to obtain the address of the constant. These operations are time consuming and account for much of the degradation of execution speed associated with an interpreter.

The invention simplifies the instruction format as shown in FIG. 10. The only information required in the instruction is the address of the constant 550. The instructions are differentiated from objects as described above by testing the first bit (sign bit).

If the word of information is negative (one bit), then an instruction is present. If the word of information is positive (zero bit), then a pointer to a Prolog object is present. Thus, in our example, the second argument of the instruction is encoded as a word of information whose first bit is set to zero and the additional thirty-one bits of information are a pointer containing the address of the constant "hello".

The interpreter has all the information necessary to carry out the get.sub.-- constant instruction without any further preliminary processing. The register used for the get.sub.-- constant is implicity assigned by the interpreter based on current allocation of the registers. There is no explicit assignment of the register by the instruction.

The register field in the instruction can be omitted from the Wam generated code for d(U*V,X,(DU*V)+(U*DV)):

    ______________________________________
    get.sub.-- structure `*`/2,A1
                         % d(*/2(
    unify.sub.-- variable A1
                         % U,
    unify.sub.-- variable Y1
                         % V),
    get.sub.-- variable Y2,A2
                         % X,
    get.sub.-- structure `+`/2,A3
                         % +/2(
    unify.sub.-- variable A4
                         % SS1,
    unify.sub.-- variable A5
                         % SS2),
    get.sub.-- structure `*`/2,A4
                         % SS1 = */2(
    unify.sub.-- variable A3
                         % DU,
    unify.sub.-- value Y1
                         % V),
    get.sub.-- structure `*`/2,A5
                         % SS2 = */2(
    unify.sub.-- value A1
                         % U,
    unify.sub.-- variable Y3
                         % DU)
    ______________________________________

    ______________________________________
    get.sub.-- structure `*`/2,A1
                         % d(*/2(
    unify.sub.-- variable A1
                         % U,
    unify.sub.-- variable Y1
                         % V),
    get.sub.-- variable Y2,A2
                         % X,
    get.sub.-- structure `+`/2,A3
                         % +/2(
    unify.sub.-- stack   %
    unify.sub.-- stack   %
    get.sub.-- structure `*`/2
                         % = */2(
    unify.sub.-- value A1
                         % U,
    unify.sub.-- variable Y3
                         % DU)
    pop.sub.-- structure `*`/2
                         % = */2(
    unify.sub.-- variable A3
                         % DU,
    unify.sub.-- value Y1
                         % V),
    ______________________________________

• Inventors
  Rouquie, Gilbert J. A.;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Dec-28-1993
• Current US Classes:
  717/139
  719/310
• Application #
  938302
• International Classes
  G06F 009/44
• Field of Search
  395/700 395/650
• Examiner
  Kriess; Kevin A.
• Agent
  Stephens; L. Keith, Knight; G. Marlin
• US Patent References:
  4546432
  4736321
  4787035
  4949255