Hardware support for high-level LISP functions

Abstract

The efficient execution of the LISP programming language is an important concern because of its use as a systems language for applications in Artificial Intelligence. Many architectures especially tailored for LISP have been designed and built. These architectures provide support for primitive list operations such as ear and edr at the machine level but no direct support for high-level LISP functions such as get, memq, nth, etc. Measurements were made on several LISP programs to determine the percent execution time (excluding input/output and garbage collection) spent in a targeted set of high-level LISP functions. The monitored functions were functions such as get and length whose execution times are somehow dependent upon the number of elements in their top-level list argument. The total targeted-function usage in the measured programs ranged from 15% to 75%. In every program except one, a single high-level function accounted for over 10% of the measured execution time. An architecture is proposed which provides constant time access to top-level list elements. The ALISP architecture uses content-addressable memory (CAM) as a LISP object cache. An ALISP list node residing in CAM consists of car, cdr-tag, and cdr-num fields. The car field contains the traditional LISP atom or pointer value. The cdr-tag field is used as a common tag for all of the nodes in the cdr-chain (top-level list nodes). The cdr-num field contains the position of the node in the cdr-chain with the last node of the cdr-chain given a cdr-num of zero and the first node assigned a cdr-num value equal to the number of top-level nodes minus one. A search by the CAM on the cdr-tag and cdr-num fields provides constant time access to any node in the cdr-chain. The searching capability of the CAM and the ALISP node format provide constant time execution for the functions get, memq, nth, and length. The CAM makes the ALISP architecture well suited for many LISP applications which require a powerful search capability. A simulation of the ALISP architecture on a problem involving theorem proving by resolution in the propositional calculus demonstrated a speedup of between 200% to 400% over conventional architectures. The architecture is well matched to Very Large Scale Integration (VLSI) and Wafer Scale Integration (WSI) because it is memory intensive.