Why Can't Integers Become Principal Functors?

Appeared in Volume 6/3, August 1993

chik@icot.or.jp
Takashi Chikayama
14th January 1993

Thank you very much to those who responded to my question posted in a recent article. Here is a summary of the responses.

My original question was: Can somebody explain why integers cannot be the principal functor of non-atomic functors? Are there any theoretical reasons? Any implementational difficulties? Or is it just for compatibility with previous implementations?

I've received mail replies from:

Pascal Brisset (brisset@ecrc.de)
Walter G. Wilson (walter@watson.ibm.com)
Brad Miller (miller@cs.rochester.edu)
Peter Ludemann (ludemann@imi.kdsi.com)
and Peter Van Roy (vanroy@prl.dec.com) responded in network news.

What I meant to ask about was allowing terms like "1(a)" but without any arithmetical interpretation. Some of the responses clarified this point.

Walter G. Wilson writes:
=..(1(b),1.b.nil) can allow any interpretation, including the one that maps the head of the second argument to one.

IBM Prolog2 for OS/2 does a lot of these nice things.

On the other hand, Peter Ludemann writes:
IBM Prolog and Prolog-III (I think) allow arbitrary terms as principal functors. The cost in implementation is fairly large in return for a quite small improvement of the programming language. There is no loss of speed (at least in IBM Prolog).

My response was: In implementations where functor information (the principal functor and the arity) is encoded in an identifier, the principal functors are recorded only in the system tables for functors and not in each functor data structure. Thus, allowing integer principal functors would increase the complexity of the system tables only, which would not be large.

and Ludemann agreed:
you're assuming that functors would be extended only to integers and not arbitrary functors, so I think your point is correct.

Besides arithmetical built-in predicates and I/O syntax issues, integers are nothing more than atoms. A big difference in the performance viewpoint is that integers are created much more often than symbolic atoms, as arithmetics are much more common than calls to the built-in predicate "name". However, this won't be an obstacle in allowing integers as principal functors.

If we can treat integers the same as symbolic atoms (in the language specification level, but not necessarily at the implementation level), the Prolog language can become simpler and closer to the Horn logic.

In my opinion, allowing arbitrary terms as principal functors is a completely different issue. It is a change to the semantics of Prolog. Allowing integers as principal functors is, in a sense, making the semantics smaller. The kernel part of the semantics (excluding arithmetics and I/O) will be simpler if integers are not treated differently.

Peter Van Roy also writes:
There is no fundamental reason why not.

Various conjectures were put forward to explain why many Prolog systems don't allow integers as principal functors. They all echoed Van Roy's conjecture:
Maybe it was done because it was imagined it would make it easier to implement arithmetic efficiently.

In summary: there are no theoretical nor implementational reasons to disallow integers as principal functors.