Browse Prior Art Database

Radix Partitioned Trees for Prolog Local/Axiom Environments

IP.com Disclosure Number: IPCOM000041098D
Original Publication Date: 1987-Aug-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Cohen, ME: AUTHOR

Abstract

This article describes a technique for improving the access time for local variables in a prolog interpreter.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 1

Radix Partitioned Trees for Prolog Local/Axiom Environments

This article describes a technique for improving the access time for local variables in a prolog interpreter.

Radix partitioned trees search (RPTS) routines can be applied to the problem of storing the local environment in a prolog interpreter. The local environment consists of information about variable bindings.

There are two different types of variable bindings that can exist. A variable in the current environment can be bound to a constant in the previous environment or a variable in the previous environment can be bound to a constant in the present environment. The variable can be used as a key with a sign bit either on or off depending on the type of binding. The data field for each entry into the tree would be the object to which the variable is bound.

The RPTS method disclosed herein replaces the conventional method of placing the binding information on a stack. The access time for the stack method grows linearly with respect to the number of bindings while the RPTS method grows logarithmically. The RPTS method also provides a very natural and efficient way to separate the two different kinds of bindings.

The performance in this area of the prolog interpreter is very critical as it accounts for more than one third of the CPU time spent running the standard benchmark for performance. It is clear that any performance improvement in this area will be noticed in the overall performance of the interpr...