Compound terms and Lists in Prolog

Question

Why are compound terms preferable over lists in terms of performance? For example,

matrix(row(1,2,3),row(1,2,3),row(1,2,3))

is preferable over

[[1,2,3],[1,2,3],[1,2,3],[1,2,3]]

Answer 1

First, just to be clear: Lists are a kind of compound term.

To see what lists are, use write_canonical/1. For example, using GNU Prolog:

| ?- write_canonical([1,2,3]).  
'.'(1,'.'(2,'.'(3,[])))

Regarding representation in memory, I recommend Richard O'Keefe's book. The details differ between systems, but you can be pretty sure that to represent the term row(1,2,3) in memory, you need:

• one memory cell for the functor/arity
• 3 memory cells for the arguments

For the term .(1, .(2, .(3, []) in a straight-forward memory representation, you need:

• 3 memory cells for the three '.'/2 functors
• 3 memory cells for 1, 2, 3
• likely some more (such as for []).

From this, you already see that using lists takes at least roughly twice as much memory in this representation.

A few simple tests that you can carry out yourself will help you to see the difference in memory consumption of these representations for your system.