NETB131 Programming Project

NETB131 Programming Project
Programming language Prolog
An overview

Plamen Georgiev Barzakov, F39984

1. History and Special Features

The name Prolog is chosen by Philippe Roussel as an abbreviation for "PROgramming LOGique". It is created in 1972 by him and Alain Colmerauer, colaborating with Rober Kowalski of the University of Edinburgh. Kowalski contributed the theoretical framework on which Prolog is founded while Colmerauer's research at that time provided means to formalize the language itself. The first Prolog interpreters was not as fast as Lisp systems but this changed in mid 1970's when David H.D. Warren and his colleagues developed an efficient implementation of Prolog. The compiler, which was almost entirely written in Prolog, translated Prolog clauses into instructions of abstract machine that is now known as Warren Abstract Machine (WAM). However, the Western computer science and artificial intelligence community was still ignorant or, at best, indifferent to logic programming. Prolog is a programming language with precise operational meaning that borrows its basic concepts from logic programming. The Prolog programs are instructions for execution on a computer. These instructions can almost always be read as logical statements and, most important, the result of a computation of a Prolog program is a logical consequence of the axioms in it. Note, that effective Prolog programming requires an understanding of the theory of logic programming.

2. "Hello World" Program

hello :- display('Hello World!') , nl .

3. Fundamental Data Types (integer, floating point, string) and Assignment Operator Definitions:

Simple types are implementation dependant in Prolog, however most implementations provide these simple types:

boolean - true, fail

integer - integers

real - floating point numbers

variable - variables

atom - character sequences

The assignment operator creates a copy of its right operand and assigns it to the left operand. If the right operand contains a variable then the value of that variable is copied, not a reference to the variable. If the right operand contains an empty variable an exception is thrown.

Examples:

            A := [B], B=c.             The variable A will have the value [B]
            B=[b], A := [a|B].        A will be the list [a, b]
            B=a, B := [x|B].           B will have the value [x | a]

4. Basic Control Flow (conditional and loop statements)

A Prolog program is constructed from a number of clauses, the general form of which is

There are three forms of clauses based on this general pattern:

facts (hypotheses, unit clauses) <head>.
Example:
```
      father( john, mary ).
```

rules (conditions, inferences) <head> :- <body>.
Example:

      sister( X, Y ) :-
      female( X ),
      parents( X, Ma, Pa ),
      parents( Y, Ma, Pa ).

questions (goals) ?- <body>.
Example:
```
      ?- sister( alice, victoria ).
```

Horn clauses: Prolog allows at most one atomic expression (predication) in the head of a clause, but any number in the body.

- Conjunction (^, and) is expressed by separating predications with ','.
- Disjunction (V, or) is expressed by multiple clauses.
- A goal is essentially a headless clause, but the symbol ?- is more suggestive of a question than a leading :- would be.
Interpreted environment -- A user enters clauses into the Prolog environment and they are interpreted.
- If asked for confirmation of a fact such as
```
  ?- sister( alice, victoria ).
```
  the system responds yes or no.
- Closed world assumption -- no means the goal could not be proved on the basis of the rules and facts provided.
- If a goal contains variable(s), the system responds with one possible set of bindings. The user enters ';' to prompt for another solution (set of bindings).

Prolog loops:

Using the 'member' predicate we can abbreviate

 	X=1;X=2;X=3....

and so we can solve simple word problems by writing searches: What digit has a square of 9?

 	member(X,[1,2,3,4,5,6,7,8,9,0]), X*X =:= 9.

What digit has a square of 3?

 	member(X,[1,2,3,4,5,6,7,8,9,0]), X^2 =:= 3.

How about looking for a solution of an equation:

 	member(X,[1,2,3,4,5,6,7,8,9,0]), X^2-11*X+28=:=0.

You can also search for two digits:

  	member(X,[1,2,3,4,5,6,7,8,9,0]),member(Y,[1,2,3,4,5,6,7,8,9,0]), X^2+Y^2 =:= 10 *X+1.

Task: Input an integer number n and output the sum: 1+2²+3²+...+n². Use input validation for n to be positive.

  	% s(N,SN) - given a positive non zero integer number N, SN=1+2+...+N

  	s(1,1).

  	s(N,SN ) :-  N > 1, N1 is N-1, s(N1, SN1), SN is SN1 + N ^ 2.

  	s(N, _ ) :-  N < 1, print('Error in s1'), nl, fail.

5. Functions - syntax, writing and using functions, example
Prolog does not provide for a function type therefore, functions must be defined as relations. That is, both the arguments to the function and the result of the function must be parameters to the relation. This means that composition of two functions cannot be constructed. As an example, here is the factorial function defined as relation in Prolog. Note that the definition requires two rules, one for the base case and one for the inductive case.

Example:

          fac(0,1).
            fac(N,F) :- N > 0, M is N - 1,
            fac(M,Fm), F is N * Fm.

The second rule states that if N > 0, M = N - 1, Fm is (N-1)!, and F = N * Fm, then Fis N!. Notice how `is' is used. In this example it resemblesan assignment operator however, it may not be used
to reassign a variable to a new value. In the logical sense, the order of the clauses in the body of a rule are irrelevant however, the order may matter in a practical sense. M must not be a variable in the recursive call otherwise an infinite loop will result. Much of the clumsiness of this definition comes from the fact that fac is defined as a relation and thus it cannotbe used in an expression. Relations are commonly defined using multiple rules and the order of the rules may determine the result. In this case the rule order is irrelevant since, for each value of N only one rule is applicable.

6. Arrays - syntax, definition, example

In Prolog the distinction between programs and data are blurred. Facts and rules are used as data and data is often passed in the arguments to the predicates. Lists are the most common data structure in Prolog. They are much like the array in that they are a sequential list of elements, and much like the stack in that you can only access the list of elements sequentially, that is, from one end only and not in random order. In addition to lists Prolog permits arbitrary patterns as data. The patterns can be used to represent tuples. Prolog does not provide an array type. But arrays may be represented as a list and multidimensional arrays as a list(s) of lists. An alternate representation is to represent an array as a set of facts in a the database.

Here is the syntax of an array in Prolog:

                                                   REPRESENTATION
TYPE                             [ comma separated sequence of items ]           sequence of items
list                                   pattern

A list is designated in Prolog by square brackets ([ ]+). An example of a list is

[dog,cat,mouse]

This says that the list contains the elements dog, {\tt cat, and mouse, in that order. Elements in a Prolog list are ordered, even though there are no indexes. Records or tuples are represented as patterns.

Example:

book(author(aaby,anthony),title(lab_manual),data(1991))

The elements of a tuple are accessed by pattern matching.

Example:

book(Title,Author,Publisher,Date).
author(LastName,FirstName,MI).
publisher(Company,City).

book(T,A,publisher(C,rome),Date

7. Prolog Compilers

    Poplog
    Open Prolog
    Ciao Prolog
    GNU Prolog

8. Projects and Software in Prolog

    LPA Prolog for Windows - World class Prolog tools for Windows and the Web
    Amzi! Prolog + Logic Server - Embeddable, extendable Prolog for programmers to build high-performance rule-based systems.

9. Standard
ISO/IEC JTC1/SC22/WG17 is the international standardization working group for the programming language Prolog.

10. References

[1] Wikipedia
[2] Prolog Tutorial
[3] Computing Science 370
[4] Prolog Tutorial by James Power