Compact Representation of Lists

Appeared in Volume 6/3, August 1993

mcovingt@athena.cs.uga.edu
Michael A. Covington
7th June 1992

(1) Am I right in thinking that it is standard practice in Prolog implementations to represent lists more compactly than their functor-argument structure would normally call for, so that:

[a,b,c] 	
% equivalent to .(a,.(b,.(c,[])))

by omitting the pointers to '.' somehow?

(2) Can anybody tell me which particular implementations do or do not do this? pereira@alice.att.com
Fernando Pereira
8th June 1992

WAM-based implementations do this by using different tags to distinguish between (pointers to) list pairs and (pointers to) functor-argument records. Typically:X = [a|Y]

would be represented as

X: list pointer to C
...
C: a
C+1: <Y's representation>

would need

X: structure pointer to C
...
C: <representation of functor f of arity 2>
C+1: a
C+2: <Y's representation>