c  go  java  js  lua  py  vbs  rkt  scm  pro  

Prolog Clocksin, W. F., & Mellish, C. S. (1984). Programming in Prolog, 2nd ed. Berlin: Springer-Verlag.. , for programming in logic, is a logic language that can be used to concisely specify the logic of a solution. Datalog is a subset of Prolog.

Technically, the main differences are that Datalog does not support terms (i.e., arbitrary list structures) and user-defined operator precedence for dynamic parsing, etc.

Datalog is so named because of the close correspondence to relational databases, especially in the declarative nature of queries that can be posed to the database. In fact, a Datalog program is often referred to as a database.

Here is the Prolog code.
prints([]):- nl. prints([X|Rest]):- print(X), prints(Rest). boy("Red"). boy("Green"). go:- prints(['Combinations of 2 objects with replacement:\n']), nl, boy(B1), boy(B2), prints([B1,' ',B2,'\n']), fail. :- solve(go).
Here is the output of the Prolog code.
Combinations of 2 objects with replacement:\n Red Red\n Red Green\n Green Red\n Green Green\n

Note:

• The rules boy("Red") and boy("Blue") are facts.
• The "go:-" introduces a query.
• The upper case identifiers B1 and B2 are logical variables that can be assigned a value only once.
• The condition boy(B1) unifies logical variable B1 with, first "Red", then, on backtracking to find additional solutions, "Blue".
• The fail predicate causes backtracking in order to find more solutions.

Here is the Prolog code.
prints([]):- nl. prints([X|Rest]):- print(X), prints(Rest). boy("Red"). boy("Green"). go:- prints(['Permutations of 2 objects:\n']), boy(B1), boy(B2), B1 \== B2, prints([B1,' ',B2,'\n']), fail. :- solve(go).
Here is the output of the Prolog code.
Permutations of 2 objects:\n Red Green\n Green Red\n

Note that the variables B1 and B2 must be instantiated to values before the inequality check

can be used to insure that they do not have the same value.

• 1. There are 3 boys and 3 girls.
• 2. One girl is dressed in red, one in green, one in blue.
• 3. One boy is dressed in red, one in green, one in blue.
• 4. The boy in red danced with the girl in green.
• 5. No boy danced with a girl who was dressed in the same color.
• 6. Which boy danced with the girl dressed in red?

Adapted from Martin Gardner (1978, p. 92-93). For puzzle purposes, it is assumed that boys dance only with girls (and girls with boys).

As Gardner states,

Most people do not find it easy to follow the reasoning in the solution to this problem.

Gardner's approach, which is the only reasonable one when doing the problem manually, is to create a matrix (or matrices) that represent all possible cases for the problem and to eliminate cases that do not meet the requirements specified by the rules.

The approach here is to encode the rules specified by the problem into Datalog logic rules and let Datalog determine the answers. The development of a logic specification and solution to this problem is also, in microcosm, a good example of the entire programming process.

The dif predicate will be used for two values (atomic, number, etc.) that succeeds if the values are different.

Otherwise, the predicate fails and backtracking to the next possible solution is initiated.

One way to solve the puzzle using Datalog is as follows. The condition

• 1. There are 3 boys and 3 girls.

is handled by numbering the boys 1, 2, and 3, and the girls 1, 2, and 3.

Boy 1 danced with girl 1.
Boy 2 danced with girl 2.
Boy 3 danced with girl 3.

The goal is to find out the color of the attire worn by each.

Since we are interested in the colors of the attire worn by the boys and girls, the following logical variables are introduced.

• The colors of the attire worn by the 3 girls are G1, G2, and G3.
• The colors of the attire worn by the 3 boys are B1, B2, and B3.

The condition for the colors for

• 2. One girl is dressed in red, one in green, one in blue.

can be expressed as the following facts.

A unique permutation can be insured with the following conditions using the girl predicate.

The condition for the colors for

• 3. One boy is dressed in red, one in green, one in blue.

can be expressed as the following facts.

A unique permutation can be insured with the following conditions using the boy predicate.

The condition

• 4. The boy in red danced with the girl in green.

can be expressed as follows, picking the second pair.

The condition

• 5. No boy danced with a girl who was dressed in the same color.

can be expressed as follows.

The question

• 6. Which boy danced with the girl dressed in red?

can be expressed as a Datalog query that uses all of the previous conditions and outputs any solutions found that meet the conditions. This might be done as follows.

Here is the final program. Note that within reason there as a great deal of flexibility as to the order of the predicates since we are dealing with finite domains. Machine efficiency can be impacted, however, by the order of the constraints. Here is the Prolog code.
prints([]):- nl. prints([X|Rest]):- print(X), prints(Rest). girl("Red"). girl("Green"). girl("Blue"). boy("Red"). boy("Green"). boy("Blue"). dif(X, Y):- X \== Y. go:- % The boy in red danced with the girl in green B2 = "Red", G2 = "Green", % boy B1 danced with the girl G1 dressed in red, find B1 G1 = "Red", % all girls have a different color girl(G1), girl(G2), dif(G2, G1), girl(G3), dif(G3, G1), dif(G3, G2), % all boys have a different color boy(B1), boy(B2), dif(B2, B1), boy(B3), dif(B3, B1), dif(B3, B2), % no boy danced with the girl of the same color dif(B1, G1), dif(B2, G2), dif(B3, G3), prints(['The boy in ',B1,' danced with the girl in ',G1,'.\n']), fail. :- solve(go).
Here is the output of the Prolog code.
The boy in Blue danced with the girl in Red.\n

The primary global perspective is that, for example, since boy(B2) is often used just to insure that logical variable B2 does, indeed, have a value, once that is (globally) established, that check is no longer needed.

Another aspect of machine efficiency is that, sometimes, moving conditions earlier (or later) can effectively prune more of the search space, thus resulting in better performance. In the extreme cases, such ordering can make the difference between finding or not finding answers (due to computational time and/or space limits). However, the increased machine efficiency must be traded off against the decreased human efficiency in both creating and understanding the program.