11.1 Introduction

In our discussion thus far, we have assumed that there is a one-to-one relationship between ground terms in our language and objects in the application area we are trying to describe. For example, we assumed a unique name for each person. In Arithmetic, we assumed a unique term for each number. This is often called an isomorphic representation because there is a one to one relationship between the ground terms in our language and objects in the world. This makes things conceptually simple, and it is a reasonable way to go in many circumstances. But not always.

In real life, we often find it convenient to use more than one term refer to the same real world object. For example, we sometimes have nicknames for the same person - Michael and Mike. And, in Elementary Arithmetic, we frequently use different terms to refer to the same number - 1+2, 2*1, and s(s(0)). This contradicts our assumption about isomorphic representation. However, we can deal with this by expanding our language to include evaluable functions and writing rules that define these functions.

11.2 Syntax

In order to allow for logic programs with nicknames, we partition the set of all symbols in our vocabulary into primitive symbols and evaluable symbols, and we partition the set of all function constants into primitive functions and evaluable functions.

A basic term is a term consisting entirely of primitive symbols, primitive functions, and variables. A basic term does not contain any evaluable constants or functions.

A semibasic term is either an evaluable constant or a compound term consisting of an evaluable function applied to basic terms.

An evaluable term is a term with any mix of opaque and evaluable constants and functions. Note that every basic term is also an evaluable term.

The Herbrand universe of our language is the set of all ground terms that cane be formed from the primitive constants and functions, i.e. it is the set of all ground basic terms.

A function rule is an expression of the form shown below. Each rule consists of (1) a semibasic term (called the head), (2) the := operator, and (3) an evaluable term (called the body).

Consider a language with object constants and function constants. To these, let us add a unary evaluable function constant foo. ...

The rule shown below is an example. In this case, we are defining the area of an object a to be the product of the height of a and the width of a.

As with rules defining views, function rules may contain variables to express information in a compact form. For example, we can write the following rule to generalize the preceding rule to all objects.

Safety. As with view definitions, there are some syntactic restrictions on function definitions. In particular, subgoals must be safe in that all variables in the second argument must be included in the first argument or must be used within positive subgoals of the rule containing the aggregate.

11.3 Semantics

The semantics of is based on the idea that every ground evaluable term t in our language is either undefined or has as value a ground primitive term value(t) defined as follows.

If t is a primitive object constant, then the value is t. If t is a term of form f(t1,...,tn) and f is a primitive function constant, then the value is f(value(t1),...,value(tn)). If t is a ground evaluable term and there is an instance of a rule with t as head and b as body, then its value is value(b). Otherwise, the value of t is undefined.

As an example, consider a language with a single object constant 0, a unary primitive function constant s, an evaluable constant 1, and two unary evaluable functions constants twoplus and pred.

The evaluable constants are defined as shown in the following rules. 1 is simply a nickname for s(0). twoplus maps a number into that number plus 2. pred is the inverse of s.

Given these definitions, we can determine the values of the terms in our language. See below for some representative examples.

11.4 Predefined Functions

In the chapter on queries, we saw that practical logic programming languages typically include predefined relations and relational operators. Such languages typically include predefined functions and functional operators as well.

Epilog is no exception. It includes predefined functions for arithmetic (e.g. plus, times, max, min), strings (e.g. concatenation), and lists (e.g. append, reverse, and length).

Using these predefined functions, we can write complex functional expressions, and we can use these expressions in defining additional functions. For example, the functional rule below defines the "positive" solution of a quadratic polynomial with coefficients A, B, and C using the predefined functions plus, minus, times, quotient and sqrt.

Epilog also includes aggregate operators countofall and setofall. For example, the first rule below uses the countofall operator to define a function numchildren that takes a person as argument and specifies the number of children of that person. Given a person X, the value is the number of people Y such that parent(art,Y). The second rule defines the set of all children of the person specified as its argument.

Suppose we have the dataset shown below.

Given this dataset and the definitions above

Note that countofall is not strictly necessary, as we can define countofall in terms of length and setofall, as illustrated by the alternative definition of numchildren shown below. However, countofall is extremely useful, and there are potential computational advantages to evaluating functional terms countofall; so it is predefined.

The choose operator provides a way to select about a random object from among all objects that possess a specified property. For example, the following rule defines guardian of a person as an arbitrary one of the person's parents.

Note that the first argument to choose can be a compound primitive term, not just a single variable. For example, the following definition defines duo to be a random pair of children of the person supplied as argument.

Epilog also includes a conditional operator, viz. if, which is used in writing conditional terms. This conditional operator can be used in a variety of ways.

The simplest type of conditional term is the familiar if-then-else expression, viz. if(condition,value1,value2). If the condition is true, then the value of this term is value1; otherwise, the value is value2. Although Epilog contains a function for computing absolute value (viz. abs), we can define an equivalent function absval as shown below.

If the last argument is omitted, this becomes a simple if-then statement, viz. if(condition,value). If the condition is true, then the value is value. Otherwise, the value is undefined.

It is also permissible to include multiple conditions and values, with or without an else value. The general form is if(condition1,value1,...,conditionk,valuen,value). If condition1, ..., conditionk-1 are all false and conditionk is true, the value is valuek. If none of the conditions are true, the value is value. If none of the conditions are true and the expression does not have an else value, then the value of the expression as a whole is undefined.

In logic programming languages that provide such predefined concepts, there are syntactic restrictions on their use. For example, the first argument of a countofall or countofall term must be a relational formula. The conditions in a conditional term must also be relational formulas and the values must be evaluable terms. Moreover, any free variables value must appear in the head of the rule or in the associated condition. Details are typically found in the documentation of systems that supply such built-in concepts.

11.5 Multiple Rules

Every functional definition we have seen thus far takes the form of a single rule. If there are multiple cases to consider, we can express the definition using the conditional operator if. The alternative is to define multiple cases in separate rules, just as we do in defining views.

As an example of using of multiple rules in defining a function, consider the definition of f in the preceding section. Rather than writing a single rule using if, we could write this definition using several simpler rules, one for each case. See below.

This definition is similar to the approach we use in writing view definitions with multiple cases. Many people prefer to deal with different cases in different rules. Also, the rules can be written in any order. Unfortunately, there are couple of issues with writing definitions this way.

The first problem is computational cost. In this case, the costs are the same. But this need not always be the case. Consider the problem of defining the x player's reward at the end of a variant of Tic Tac Toe in which the game does not end once a player gets a line. In this case, x gets 100 if there is a row of x's and no row of o's; it is 0 if there is a row of o's and no row of x's; and it is 50 otherwise. We can write this with a single rule as shown below.

Now compare this to the following definition, where we have written a separate rule for each of the four cases.

Many people find this version conceptually simpler than the former version because it treats each of the four distinct cases in a separate rule. Unfortunately, evaluating reward using these rules can more expensive than using the former rule. In the worst case, we have to evaluate row(x) and row(o) multiple times, while using the rule above, we evaluate each at most once. The computational benefit comes from knowing that once a condition in an if statement fails, it is assumed to be false for the remaining cases, whereas with multiple rules we need to check the conditions multiple times.

A second and more serious problem arises if different rules give different answers for the same case. Suppose we were to write the rules shown below instead of the rules above.

This works fine provided that there is no way for there to be a row of x's and a row of o's at the same time (as in ordinary Tic Tac Toe). However, in our case, there are problems if both players have a row. The first rule says that x receives 100; the second says that x received 0. Note that this cannot happen with the single rule definition.

If a programmer wishes to write multiple rules to define a function, he must ensure that the rows do not conflict in this way. Unfortunately, there is no simple syntactic test that determines whether this constraint is violated, and the programmer must ensure that it is the case for himself.