Re: Pointer elimination in C & other languages...

Prolog, like LISP, can be seen as handling nearly nothing but pointers. In
fact, Prolog's unification mechanism can require following an arbitrary
number of pointer links to reach the final object. This process is known
as dereferencing. In practice however all this is extremely well hidden
from the programmer. The compiler can use static (global) analysis to
determine which variables may be "unboxed", that is, simply passed around
in machine registers (not stored on the heap), or otherwise exactly how
many steps of dereferencing are required. This leads to incredible
performance increases, and currently the best Prolog compilers (Aquarius
and Parma) are competitive with (and sometimes out-perform) C compilers.


A typical hack used in Prolog compilers (and I assume LISP as well) is to
use tagged words to allow the garbage collector to know what it's looking
at. However, in many cases, this entails *no* overhead, for example,
assigning tag 0 to integers allows arithmetic operations to be performed
simply (with lesser precision however). Likewise, most RISC processors
have a "load word at address + offset" instruction, this is used by C
compilers to access the data held in structures, but in Prolog it can be
used to simply subtract the "pointer" tag from the address and therefore
no extra overhead is incurred.
__
Richard Meyer Net: rmeyer@prl.dec.com
                                                                                                      Tel: (33) (1) 47.14.28.65
Digital Equipment Corporation Fax: (33) (1) 47.14.28.99
Paris Research Laboratory
85, avenue Victor Hugo
92500 Rueil-Malmaison Cedex
FRANCE
--

Return to the comp.compilers page.
Search the comp.compilers archives again.