Prolog

Prolog is a general purpose logic programming language that was developed in the 1970's for use in Artificial Intelligence, especially in the area of Natural Language Processing. Although many interpreters, compilers and software development environments exist for it, most dialects conform to a standardised version called Edinburgh Prolog. We will assume that the reader is familiar with Edinburgh Prolog, and use it as our prototyping language (in what follows by Prolog we mean Edinburgh Prolog). Interested readers will find a good introduction to Prolog in [Clocksin and Mellish 84].

There are many advantages in the use of Prolog, including its:

• simple form: A Prolog program is a list of clauses, each clause being a fact or a rule. Facts are predicate structures of the form:

  $fact\_name(t_{1}, ..., t_{n}).$ where $n \geq 0$, and each t_i is a term defined as

  • a constant or
  • a variable or
  • a function symbol containing zero or more terms as arguments.

  Rules are of the form

  $a \;$ :- $\; b,c, \; ... \; ,d.$

  where

  • ` a,b,c,...,d' are predicates structures,

  • `a' is called the head of the rule,

  • ` b,c,...,d.' is called the tail of the rule,

  • `:-' is read as `follows from'.

  A group of clauses which share the same head predicate is called a procedure.

• `dual' semantics: Prolog programs can be interpreted in two ways:

  • declaratively: each clause can be interpreted as a logic formula, generally a fact or a rule. Our typical rule $a \;$ :- $\; b,c, \; ... \; ,d.$ corresponds to the logical formula:

    $(b \land c \land ... \land d) \Implies a$

    where all variables in the rule are universally quantified.

  • procedurally: each clause can be read as a goal oriented procedure, which asserts `to solve the head, solve all the predicates in the tail'. The head predicate is akin to a procedure's heading, whereas the predicates in the tail can be interpreted as procedure calls. One consequence of the goal-oriented interpretation of Prolog's clauses is that a VDM post-condition can be modelled as a set of Prolog goals to be achieved.

• high level data structures: Prolog's term and list data structures can be easily adapted to implement VDM data structures.

• backtracking: Prolog's backtracking mechanism is a form of control which resembles naive search. The search is for instances of a goal predicate's variables which make a goal succeed. Later we will see how backtracking can be used to prototype existentially quantified conditions in VDM operations.

The first two advantages pointed out above just apply to PureProlog, a subset of Prolog which does not contain any side effects. Of course, as a programming language Prolog contains expressions which cannot readily be given a logical interpretation, such as read and writeprocedures. The language has various other disadvantages of which the user should be aware:

• Prolog is not a strongly typed language, and in fact variables in predicates are not type-restricted in any way. This means that there is a danger of procedures being called with unsuitable parameter values. With a strongly typed language (Pascal, for example) if a procedure is called with too many or the wrong type of argument values, the implementation would automatically flag a type mismatch at or before run-time, and the user would be aware of and could pin-point the error. In Prolog the run-time behaviour in this case would be unpredictable, and the error would be difficult to detect and fix.

• Prolog has no (standard) module mechanism. This means data type encapsulation and information hiding are not supported.

• Prolog does not support functional evaluation, except in some special circumstances such as numerical evaluations. This means that every functional expression in a VDM condition must be translated into a Prolog procedure which has an extra slot for an output value. This extra slot contains a dummy parameter which carries the function value to the next evaluation. For example, consider the following VDM expression:

  $S \Inter \Dom M$

  where S is a set, and M a map. Both functions `$\cap$' and `dom' must be implemented as Prolog procedures. If we let these procedures be called `dom_map' and `intersect_set', then this expression translates to the Prolog predicates:

       dom_map(M,  DomM), intersect_set(S,DomM,  Result)  
       /* post-condition: Result = S intersect dom(M) */
  

  `DomM' is the dummy parameter carrying the result of the first function evaluation to the next evaluation.

• Prolog is case sensitive in that all variables have to start with a capital letter, and all predicate, function and constant names start with a lower case letter.