Previous | Table of Contents | Next |
We started out with only variables, constants, and integers as terms and then added lists to our collection of terms. In this section, we expand our set of terms even more.
6.3.4.1. Numeric Terms and Arithmetic Relations
We have seen that every integer is a term. Most Prologs also allow any real number to be a term; the standard input/output representation of real numbers is used, for instance 3.1416 or 1.86e5.
The standard arithmetic relational operators are all indeed relations, so they fit naturally into Prolog as infix predicates like the = predicate. Expressions such as X < 54 and 3 >= Y are valid goals and can appear in queries or clause bodies anywhere any other predicate call can. The less than or equal to operator is written as =< rather than <=, in order to avoid confusion with another operator.
We cannot mix arithmetic relations and uninstantiated variables indiscriminately, however. If Prolog encounters a call to one of these relations, and there are free variables in either of the arguments, it gives a runtime error. The problem here is similar to that with negated equalities. When processing X < 54, Prolog could remember that X is supposed to be less than 54 and use that information when processing future statements involving X, but this leads to slower and more complex processing, so such features are available only in constraint logic programming languages so far. Thus only instantiated variables can appear in arithmetic relations. This is no more of a restriction than in functional languages, where (because there are no logical variables) everything must be instantiated.
6.3.4.2. Arithmetic Operators and is
The standard arithmetic operators are also available. +, , and * have the expected meaning; / is real division (treating the operands as real numbers), // is integer division returning the integer quotient, and mod is the modulo operation (the remainder after division). These cannot be used effectively in predicate arguments. Instead, a special binary infix predicate, is, is used for computing with the arithmetic operators.
The goal Fahrenheit = 77, Celsius is (Fahrenheit - 32) * (5/9) succeeds with Celsius instantiated to the appropriate value, 25. The variable on the left of is can be instantiated; the goal succeeds with no substitution if it is instantiated to the correct value already or fails if it is instantiated to some other value. The whole goal gives a runtime error if any of the variables on the right-hand side of the is are uninstantiated at the time Prolog processes it.
As an example, consider the following predicate for generating a list of all the natural numbers between M and N:
% all_numbers_between(M, N, List): List is all numbers between % M and N, inclusive. all_numbers_between(M, N, []) :- M > N, !. all_numbers_between(M, N, [M|Rest]) :- M1 is M+1, all_numbers_between(M1, N, Rest).
We make the design decision that if M is greater than N, List is simply the empty list. Otherwise, List is M, along with the list of all numbers between M+1 and N. This predicate is used in a longer example that appears in section 6.5, Examples, a prime number finder using Eratosthenes sieve method.
Note that we could not simply pass M+1 as an argument to all_numbers_between. The operators only really make sense when used on the right-hand side of is, for reasons that will become apparent later.
6.3.4.3. Function Symbols
Lists are the basic data structure of Prolog; they are useful because of their flexible length. In many situations, we want to group a known number of values into a record-like data structure. For these situations, Prolog provides a notation that is internally represented more efficiently than a list.
For instance, the expression sq(e,2) is a valid term. This looks like a predicate call, but it can be used wherever any other term can be usedfor instance, in the goal Square = sq(e,2) or empty(Board, sq(e,2)). We may choose this term to represent, for instance, the square at column e and row 2 of a chessboard.
sq, in this example, is referred to as a function symbol. This is a historical phrase from predicate logic that notes the resemblance between this form of term and the application of a function but does not imply that some defined function is being called when we use it. We can build up arbitrarily large terms from constants using function symbols. For instance, the term move(sq(e,2),sq(e,4)) is a term whose outermost function symbol is move; that outermost symbol has two arguments, namely sq(e,2) and sq(e,4).
The advantages of using function symbols over lists are space efficiency and readability. We could also choose the representation [e,2] for the square at column e and row 2, but this would be represented with a pointer to the e term, a pointer to the 2 term, and a pointer to the empty list. The representation of sq(e,2), in contrast, takes only two pointers. Moreover, if we notice the term sq(e,2) in program code or debugging output, it is easier to recognize what it is supposed to represent.
We can move back and forth between lists and function symbols by using the =.. binary infix predicate. The query X =.. [sq,e,2] succeeds with the substitution X = sq(e,2). This predicate goes the other way too; the query sq(e,2) =.. Y succeeds with Y = [sq,e,2]! The only instantiation pattern that is not permitted is for both sides to be completely uninstantiated. The decomposition of the function-symbol term only applies to the top level, so for instance, the query move(sq(e,2),sq(e,4)) =.. Y succeeds with the substitution Y = [move,sq(e,2),sq(e,4)].
Now for a surprise. Enter the query X = .(a,.(b,[])). You should get back the substitution X = [a,b]. Yes, lists are actually represented using a hidden function symbol (namely .). It is just that list terms are never output, and rarely input, using the dot-prefix notation. Thus function symbols are used in the basic representation of all complex terms in Prolog, although lists are more universally useful than any other kind of function symbol terms.
Previous | Table of Contents | Next |