What does 'without function symbols' mean?

This from a David Warren book:

All programs without function symbols are terminating, and many simple programs now have
a natural programmers’ semantics.

I don’t know Datalog, I know that this is one of the things you can’t do in Datalog that makes it guarantee to terminate.

Can somebody give me a Dummies level explanation with an example of a program with and without a function symbol?

In more conventional Prolog speak, a function symbol is a compound term. Datalog and tabled Prolog guarantee termination, provided the number of possible terms is finite. If we allow for compounds, we can nest them at will (e.g., a list) and produce arbitrary many possible terms.

I always consider this a bit limited description in the Prolog world. There is also an infinite number of integers given unbounded integers (which XSB does not have) and an infinite number of atoms if the atom length is unlimited. So, you can create a non-terminating computation by enumerating all integers or creating infinite sequences of new atoms.


Ah, yes - this does seem limited - Thinking about the difference between bignums and fixed sized ints seems splitting hairs a bit.
And even SWI-Prolog’s bignums are finite - GMP won’t make an int that requires more than 4 GB to represent.
And every ‘real’ program must be finite - eventually one runs out of RAM + Disk + Cloud that somebody will pay for.

1 Like

Is this a DATLOG program ? It seems Yes, but non terminating program.

p :- p.