Prolog/KR Version C-15
1. Introduction
1.1. The Language
Prolog/KR is an interactive programming system designed to
support programs manipulating symbols and structures, espe-
cially AI (Artificial Intelligence) programs embedding
knowledges (including control knowledges); KR stands for
Knowledge Representation. Prolog/KR is equipped with some of
the basic tools used in AI programs: backtracking, pattern
matching and data base manipulations. Moreover, manipulating
structures in Prolog is much simpler than in Lisp. A program-
mer can start at a point closer to the solution.
Prolog/KR accepts more than one assertions about one predi-
cate. Each assertion is considered to express some knowledges
(possibly including control knowledges) about the predicate.
At a certain point of computation, when more than one asser-
tion can be used, the system tries them one by one -- if some
inconsistency arises later, the system backtracks to the
latest choice point and tries the next assertion.
In representing knowledge, a procedural way and a declarative
way are often distinguished. This is however a matter of
degree. In Prolog/KR, both way can be used. Prolog/KR can be
used as a procedural language as Lisp by providing every con-
trols explicitly. In that case, no automatic backtracking
occurs, and thus every computation is deterministic. If no
controls are provided, on the other hand, automatic backtrack-
ing does its job, and the computation is non-deterministic.
In usual cases, programming is done in a mixture of these two
extremes.
1.2. Notational Conventions
Lower case letters are usually converted into upper case
letters on reading by the interpreter, i.e., there is no dis-
tinction between upper and lower case letters. Nevertheless,
they are distinguished in this manual. Symbols which consist
only of lower case letters denote meta symbols, while those
consist of upper case letters denote the symbol themselves
(they must be spelled as they appear in this manual). When
they are used in a mixture, it indicates that the word may be
abbreviated to a word consisting of only the upper case
letters.
Example: "PrettyPrint" may be spelled either "PP" or "PRETTY-
PRINT".
Meanings and functions of system defined predicates are
explained in the following form:
-1- Introduction
Prolog/KR Version C-15
........ ........
................................
is shown as a sequence of Prolog/KR variables,
possibly followed by "..." indicating repetition of the
preceding argument. Arguments are referred to by their names
enclosed in "<" and ">" in . Three distinct
prefixes are used for explanation:
* This argument may be used both for input and output.
< This argument must be an output variable. In other
words, a variable which has no value must be given as an
argument to receive a value from the predicate.
> This variable must be an input. Giving an unbound vari-
able is erroneous.
Note: These conventions on variable prefix are used only in
this manual. The system does not distinguish those three
kinds of variables.
Examples:
FOO *e1 *e2
FOO takes two arguments. If FOO is called with a
wrong number of arguments, an error is issued. Note
that this rule is applicable only to the system
defined predicates. A user defined predicate
"fail"s when it is supplied with a wrong number of
arguments.
BAR >e1 *e2
BAR also takes two arguments. must be either a
variable which already has some value, or non-
variable object. That is, is an input argument
which expects to receive some value, rather than to
return a value.
may be anything, i.e., a variable or an object.
Example:
(BAR (A B) *X)
and
(BAR (A B) (C D))
are legal, while
(BAR *X *Y)
is erroneous.
Note: Although the current version of the inter-
preter treats ">" and "*" equally, users are
Introduction -2-
Prolog/KR Version C-15
recommended to use ">" when the variable is supposed
to be an input, to increase the readability.
TOng Ý*e1¨
TONG takes zero or one argument. TONG may be abbre-
viated to TO.
POO Ý*e1¨...
POO takes any number of arguments (possibly zero).
ZOO (*e1 *e2)
ZOO's argument must be a list of two elements.
-3- Introduction
Prolog/KR Version C-15
2. Objects
The syntax of Prolog/KR objects is described in this section.
Unlike other Prolog systems, Prolog/KR's objects (including
programs) are expressed as lists or atoms. Thus, every object
except variables follows Lisp(Utilisp)'s syntax.
Although Prolog/KR supports all the Utilisp data types as its
objects, only the significant ones are described in this sec-
tion.
2.1. Variable
Variables are atoms (cf. 2.2.) which begin either with "*",
">" or "<", e.g.,
*X >X X are different variables.
Three kinds of prefixes are provided solely for readability.
The system does not distinguish those three kinds of vari-
ables.
Unlike most of other programming languages, variables are not
space holders. Instead, variables are thought to be standing
for some Prolog/KR objects. Variables are either undefined or
standing for some other objects. When a variable stands for
an object, it is called to be "instantiated" and it is
equivalent to that the object itself is there. Even if a
variable is matched against another variable, they are both
considered to be uninstantiated and they will be instantiated
to the same object at the same time in the future.
VAR *variable
Succeeds if has not been instantiated yet. If
has already been instantiated or is not a
variable at all, then it fails.
PREFIX >string ...
Changes the variable prefix to one of ,
, ... Only the first characters in the strings
are effective.
Example:
(PREFIX "@@" "*")
changes the variable prefix to one of "@" and "*". The
initial state of Prolog/KR is
(PREFIX "*" ">" "<")
There is another kind of variable called an anonymous vari-
able, which is just like a variable except that it has no
Objects -4-
Prolog/KR Version C-15
identity. An anonymous variables is written as
?
and each occurrence of anonymous variable stands for different
objects.
Examples:
(= (? ?) (A B)) succeeds
(= (* *) (A B)) fails
The anonymous variables are to be used where there is no
interest about the object.
Example:
(ASSERT (CAR (*CARPART . ?) *CARPART))
CAR is a predicate to return the first element of a list.
Since there is no interest about the rest of the list, "?" is
used.
2.2. Atom
An atom is either a symbol, a number or a string. Among
these, only symbols can be used as predicate names.
A symbol consists of a sequence of characters except special
characters:
" ", "(", ")", "Ý", "¨", ";", "/", """", "'"
Above special characters may be used in a symbol provided that
it is preceded by "/". Here is a summary of meanings of the
special characters:
" " delimiter
"(" beginning of a list
")" end of a list
"Ý" super left parenthesis
"¨" super right parenthesis
";" beginning of a comment (until the end of the line)
"/" escape character
"""" beginning and end of a string
"'" quoter of a pattern
Examples of symbols:
THESE ARE SYMBOLS. A.B 1+ /(A/)
Examples of numbers:
12345 3.14159 1.0E-5 -0
-5- Objects
Prolog/KR Version C-15
Examples of strings:
"123" "Strings must be surrounded by ""."
ATOM >x
Succeeds if is an atom. Otherwise, it fails.
2.3. List
Programs and structured data are expressed in lists. A list
is a sequence of objects (including lists) enclosed in
parentheses. Dotted notation is used to express the rest of a
list. For example, "(A . *X)" matches any list which begins
with "A". See the next section about the usage of the dotted
notations in pattern matchings.
Examples of lists:
(ASSERT (HUMAN TURING))
(LISTS MAY CONTAIN *VAR 123 "string" ...)
(THIS IS A DOTTED . PAIR)
2.4. Program
A Prolog/KR program consists of predicate calls and predicate
definitions and both are expressed in lists. A predicate
definition consists of one or more assertions. One chunk of
knowledge is called an assertion and is added to the system
using ASSERT:
(ASSERT (FALLIBLE *X) (HUMAN *X))Ý1¨
This assertion means:
*X is FALLIBLE if *X is HUMAN.
Procedurally, it is equivalent to:
To execute (FALLIBLE *X), execute (HUMAN *X).
When an assertion is added to the system, it is merged into a
proper position in the corresponding definition. The detail
is described in chapter 5.
____________________
Ý1¨ This is an example of a predicate call (as well as an
assertion) whose predicate name is ASSERT and whose arguments
are (FALLIBLE *X) and (HUMAN *X).
Objects -6-
Prolog/KR Version C-15
3. Pattern Matching
Pattern matching (usually called "unification" in Prolog) is
the basic mechanism of calling predicates in Prolog. Vari-
ables may occur anywhere in the caller and the callee, and
there is no distinction between their roles. Variables may
match any Prolog/KR objects including other variables or lists
which have variables as their elements.
Since variables may be instantiated to an object which con-
tains variables, it is possible to define a value partially
and postpone defining the rest until further computation
determines it. One of the most significant examples to demon-
strate this feature is APPEND which appends two lists:
(ASSERT (APPEND () *ANY *ANY))
(ASSERT (APPEND (*CAR . *CDR) *ANY (*CAR . *REST))
(APPEND *CDR *ANY *REST))
Under the above definition (see the chapter 5. to understand
what the above means), a predicate call,
(APPEND (A B) (C D) *X)
proceeds as follows:
(APPEND (A . (B)) (C D) (A . *REST_0001))
where *REST_0001 is determined by
(APPEND (B) (C D) *REST_0001)
(APPEND (B . ()) (C D) (B . *REST_0002))
where *REST_0002 is determined by
(APPEND () (C D) *REST_0002)
(APPEND () (C D) (C D))
The result of APPEND is first (A . *REST_0001); then (A B .
*REST_0002); and finally (A B C D).
Note that in the above example, dotted notations play impor-
tant roles. In the pattern "(*CAR . *CDR)", it is used to
decompose a list into its so-called car part and so-called cdr
part. In the pattern "(*CAR . *REST)", on the other hand, it
is used to do the reverse, that is, to compose a list from
*CAR and *REST. Note that *REST was not defined at the time
of the composition. Note also that if APPEND is used rever-
sally as (APPEND *X (C D) (A B C D)), the roles of the pat-
terns also are reversed.
MATCH *x *y
= *x *y
Tests if and can be matched. If the matching
succeeds, variables in and are instantiated
accordingly. Otherwise, MATCH (or =) fails.
CAUTION: If you execute (MATCH *X (F *X)), it succeeds
-7- Pattern Matching
Prolog/KR Version C-15
and results in instantiating *X to (F (F (F (F .....
EQ >x >y
Tests if and are the same objects (in the sense
of Lisp's EQ). It does not suffice that they are the
same patterns.
Examples:
(EQ A A) succeeds
(EQ (A B C) (A B C)) fails
(AND (= *X A) (EQ *X A)) succeeds
(EQ *X A) fails
3.1. Extended Features
3.1.1. Quoting Patterns
Sometimes it is desired that a certain pattern does not match
any variables.Ý2¨ The pattern should be quoted by "'" for that
purpose. The quoted pattern only matches patterns which are
equivalent.
Examples:
(= 'A *X) fails
(= 'A A) succeeds
(= A *X) succeeds
(= '(A B C) '(A B C)) succeeds
(= '(A B C) (A B *X)) fails
(= '*X *X) succeeds
(= '*X *ELSE) fails
____________________
Ý2¨ For example, a negative information is expressed with
FAIL:
(ASSERT (CAN PENGUIN WALK))
(ASSERT (CAN PENGUIN FLY) (FAIL))
(ASSERT (CAN HAWK FLY))
so that (CAN PENGUIN FLY) fails. But if you leave these
assertions as they are, even
(CAN *X FLY)
which is supposed to be a query to search for a flying object,
fails before reaching HAWK. To avoid this phenomenon, the
previous assertion must be changed to:
(ASSERT (CAN 'PENGUIN 'FLY) (FALSE))
so that (CAN *X FLY) does not match (CAN 'PENGUIN 'FLY) but
(CAN HAWK FLY).
Pattern Matching -8-
Prolog/KR Version C-15
(MEMBER A (*X B C)) succeeds
(MEMBER 'A (*X B C)) fails
Quote can be used as a escape character of an atom which
incidentally begins with one of the variable prefixes.
Note: predicates *, >, >=, < and <= should be used without
quotation:
(* 512 256 *X)
(> *X *Y)
3.1.2. Executing Predicates within a Pattern
A list which begins with "!" is executed during the pattern
matching unless the pattern is inside another pattern which
matched a variable. A variable with no names, usually "*", in
the rest of the pattern are first instantiated to the target
of the pattern matching, and then the pattern is executed.
For example, a pattern
(! MEMBER * (FOO BAR))
matches either FOO or BAR, for
(MEMBER * (FOO BAR))
is executed with * instantiated to the target of the matching.
Using this feature, a pattern which matches only a pattern
whose first element is a variable may be expressed as:
((! VAR *) . *ANY)
Only the first prefix defined by PREFIX (the default is "*")
is considered to be the variable to get the value, i.e. the
target of the pattern matching. Thus after executing (PREFIX
"@" "#"), "@" is the variable to be instantiated.
Note that no backtracking occurs after finishing the execu-
tion. Therefore,
(AND (= (! MEMBER * (FOO BAR)) *X)
(= *X BAR))
fails, for * (and thus *X) is bound to FOO once and for all.
Note: Variables instantiated during the execution of the pat-
tern may be unbound on exit. Particularly, the value of "*"
is, due to the obvious reason, local to the pattern, and hence
invisible from outside. For the value of "*" to be exported,
it must be copied to another variable, e.g.,
(! AND (VAR *) (= * *THE-VARIABLE))
-9- Pattern Matching
Prolog/KR Version C-15
Executable patterns can also be used to simulate "functions".
For example, a function FACT (factorial) is defined as:
(ASSERT (FACT *N
(! COND ((= *N 0) (= * 1))
((TRUE)
(TIMES *N (! FACT (! SUB1 *N *) *) *¨
Note the nesting of executable patterns. To show the
correspondence between "!"s and "*"s, a suffixed version
(although it is not allowed) of the same example follows:
(ASSERT (FACT *N
(!a COND ((= *N 0) (= *a 1))
((TRUE)
(TIMES *N (!b FACT (!c SUB1 *N *c) *b) *a¨
Suppose FACT is called by
(FACT 5 *F)
the following process takes place:
1. *N = 3
2. *a = *F
3. (TIMES 3 (!b FACT (!c SUB1 *N *c) *b) *F) is executed
4. (FACT (!c SUB1 3 *c) *b) is executed
5. (SUB1 3 *c) is executed
6. *c = 2
7. ....
8. *b = factorial(2) = 2
9. *F = 6
For more convincing usage of the executable pattern, confer
the description of SELECT.
Notes on ' and !: ' and ! are something like Lisp's QUOTE and
EVAL. ' prevents ! to be executed.
(ASSERT (P (! ADD1 1 *)))
asserts
(P 2)
To prevent ! to be executed at the time of the assertion, it
must be quoted as:
(ASSERT (P '(! ADD1 1 *)))
Similarly,
(ASSERT (P 'A))
is asserted as:
Pattern Matching -10-
Prolog/KR Version C-15
(P A)
rather than:
(P 'A)
To assert the latter, ' must be doubled:
(ASSERT (P ''A))
-11- Pattern Matching
Prolog/KR Version C-15
4. Interpreter
4.1. Top Level Loop
At the top level of the Prolog/KR system, the interpreter is
waiting for user's input. If a list is typed in, it is inter-
preted (executed) and, usually, the list is echoed back with
variables instantiated according to the result of the execu-
tion. For example, suppose
(PLUS 1 2 *)
is typed in, then
(PLUS 1 2 3)
is printed back by the interpreter. If the execution has
failed, "NIL" is printed instead. For example,
(PLUS 1 2 5)
results:
NIL
Since every inputs are executed, even the definitions of
predicates must be provided in the form of predicate calls
(cf. section 5). For example, FACT may be defined as:
(ASSERT (FACT 0 1))
(ASSERT (FACT *N *F)
(SUB1 *N *N1) (FACT *N1 *F1)
(TIMES *N *F1 *F))
In this case, the interpreter acknowledges simply with
"ASSERTED" instead of printing the whole assertion back.
For typing conventions, extra right parentheses are ignored.
Super parentheses "Ý" and "¨" are also available:
(PRINT (A (B¨
(PRINT ÝA (B¨)
LAST-INPUT *FORM
Returns the last input. LAST-INPUT is defined as the
same form as user defined predicates so that it can be
edited and re-executed. Note that the execution must be
done in the editor, since once you get out of the editor,
the last input becomes "(EDIT LAST-INPUT)".
LAST-RESULT *RESULT
Returns the last result typed out by the interpreter. To
see the detail of the result which had been abbreviated
to "?", type:
(GRIND (! LAST-RESULT *))
The Interpreter -12-
Prolog/KR Version C-15
Of course, this does not change LAST-RESULT.
TOP
Transfers the control to the top level loop.
PROLOG
Initiates the top level loop. Unlike TOP, which
transfers the control to the top level of the current
loop, PROLOG initiates a new loop, nested inside the old
one.
EPILOG
Exits from a loop initiated by PROLOG and returns to the
previous status.
4.1.1. Executing the OS Command
If a line begins with a symbol, not a list, then the line is
regarded as a OS command. Any OS command except command pro-
cedures and safe commands can be called.
Example:
:LIST FOO.VDATA(BAR)
lists the contents of FOO.VDATA(BAR). ":" in the above exam-
ple is a prompt of the top level.
Pressing the break key quits the execution of the OS command;
the control returns to the top level of Prolog/KR.
4.2. Error Handling
In case of errors, the interpreter automatically enters the
stepper, where the status of the execution can be examined. Q
command or "(TOP)" transfers the control to the top level.
The standard behavior on error described above can be changed
by defining a predicate ERROR, which is called on error.
ERROR >message >object
STANDARD-ERROR-HANDLER >message >object
Prints followed by