Exploring the world of declarative programming

Photo by Stefan Cosma on Unsplash

Introduction

Most of us use imperative programming languages like C, Python, or Java at home. But the universe of programming languages is endless and there are languages where no imperative command has gone before. That which may sound impossible at the first glance is feasible with Prolog and other so called declarative languages. This article will demonstrate how to split a programming task between Python and Prolog.

In this article I do not want to teach Prolog. There are resources available for that. We will demonstrate how simple it is to solve a puzzle solely by describing the solution. After that it is up to the reader how far this idea will take them.

To proceed, you should have a basic understanding of Python. Installation of Prolog and the Python-Prolog bridge is accomplished using this command:

dnf install pl python3-pyswip

Our exploration uses SWI-Prolog, an actively developed Prolog which has the Fedora package name “pl”. The Python/SWI-Prolog bridge is pyswip.

If you are a bold adventurer you are welcome to follow me exploring the world of declarative programming.

Puzzle

The example problem for our exploration will be a puzzle similar to what you may have seen before.

How many triangles are there?

Getting started

Get started by opening a fresh text file with your favorite text editor. Copy all three text blocks in the sections below (Input, Process and Output) together into one file.

Input

This section sets up access to the Prolog interface and defines data for the problem. This is a simple case so it is fastest to write the data lines by hand. In larger problems you may get your input data from a file or from a database.

#!/usr/bin/python 
 
from pyswip import Prolog 
 
prolog = Prolog() 
prolog.assertz("line([a, e, k])") 
prolog.assertz("line([a, d, f, j])") 
prolog.assertz("line([a, c, g, i])") 
prolog.assertz("line([a, b, h])") 
prolog.assertz("line([b, c, d, e])") 
prolog.assertz("line([e, f, g, h])") 
prolog.assertz("line([h, i, j, k])")
  • The first line is the UNIX way to tell that this text file is a Python program.
    Don’t forget to make your file executable by using chmod +x yourfile.py .
  • The second line imports a Python module which is doing the Python/Prolog bridge.
  • The third line makes a Prolog instance available inside Python.
  • Next lines are puzzle related. They describe the picture you see above.
    Single small letters stand for concrete points.
    [a,e,k] is the Prolog way to describe a list of three points.
    line() declares that it is true that the list inside parentheses is a line .

The idea is to let Python do the work and to feed Prolog.

“Process”

This section title is quoted because nothing is actually processed here. This is simply the description (declaration) of the solution.

There is no single variable which gets a new value. Technically the processing is done in the section titled Output below where you find the command prolog.query().

prolog.assertz(""" 
triangle(A, B, C) :- 
  line(L1), 
  line(L2), 
  line(L3), 
  L1 \= L2, 
  member(A, L1), 
  member(B, L1), 
  member(A, L2), 
  member(C, L2), 
  member(B, L3), 
  member(C, L3), 
  A @< B,
  B @< C""") 

First of all: All capital letters and strings starting with a capital letter are Prolog variables!

The statements here are the description of what a triangle is and you can read this like:

  • If all lines after “:-“ are true, then triangle(A, B, C) is a triangle
  • There must exist three lines (L1 to L3).
  • Two lines must be different. “\=” means not equal in Prolog. We do not want to count a triangle where all three points are on the same line! So we check if at least two different lines are used.
  • member() is a Prolog predicate which is true if the first argument is inside the second argument which must be a list. In sum these six lines express that the three points must be pairwise on different lines.
  • The last two lines are only true if the three points are in alphabetical order. (“@<” compares terms in Prolog.) This is necessary, otherwise [a, h, k] and [a, k, h] would count as two triangles. Also, the case where a triangle contains the same point two or even three times is excluded by these final two lines.

As you can see, it is often not that obvious what defines a triangle. But for a computed approach you must be rather strict and rigorous.

Output

After the hard work in the process chapter the rest is easy. Just have Python ask Prolog to search for triangles and count them all.

total = 0 
for result in prolog.query("triangle(A, B, C)"): 
  print(result) 
  total += 1 
print("There are", total, "triangles.")

Run the program using this command in the directory containing yourfile.py :

./yourfile.py

The output shows the listing of each triangle found and the final count.

 {'A': 'a', 'B': 'e', 'C': 'f'}
 {'A': 'a', 'B': 'e', 'C': 'g'}
 {'A': 'a', 'B': 'e', 'C': 'h'}
 {'A': 'a', 'B': 'd', 'C': 'e'}
 {'A': 'a', 'B': 'j', 'C': 'k'}
 {'A': 'a', 'B': 'f', 'C': 'g'}
 {'A': 'a', 'B': 'f', 'C': 'h'}
 {'A': 'a', 'B': 'c', 'C': 'e'}
 {'A': 'a', 'B': 'i', 'C': 'k'}
 {'A': 'a', 'B': 'c', 'C': 'd'}
 {'A': 'a', 'B': 'i', 'C': 'j'}
 {'A': 'a', 'B': 'g', 'C': 'h'}
 {'A': 'a', 'B': 'b', 'C': 'e'}
 {'A': 'a', 'B': 'h', 'C': 'k'}
 {'A': 'a', 'B': 'b', 'C': 'd'}
 {'A': 'a', 'B': 'h', 'C': 'j'}
 {'A': 'a', 'B': 'b', 'C': 'c'}
 {'A': 'a', 'B': 'h', 'C': 'i'}
 {'A': 'd', 'B': 'e', 'C': 'f'}
 {'A': 'c', 'B': 'e', 'C': 'g'}
 {'A': 'b', 'B': 'e', 'C': 'h'}
 {'A': 'e', 'B': 'h', 'C': 'k'}
 {'A': 'f', 'B': 'h', 'C': 'j'}
 {'A': 'g', 'B': 'h', 'C': 'i'}
 There are 24 triangles.

There are certainly more elegant ways to display this output but the point is:
Python should do the output handling for Prolog.

If you are a star programmer you can make the output look like this:

***************************
* There are 24 triangles. *
***************************

Conclusion

Splitting a programming task between Python and Prolog makes it easy to keep the Prolog part pure and monotonic, which is good for logic reasoning. It is also easy to make the input and output handling with Python.

Be aware that Prolog is a bit more complicated and can do much more than what I explained here. You can find a really good and modern introduction here: The Power of Prolog.

Classrooms FAQs and Guides For Developers Using Software

8 Comments

  1. Bruno

    Nice, short and refreshing. Thank you
    (there is a typo in “than” instead of “then triangle…”, in bold)

  2. I don’t like Python much but this was definitely interesting. Thank you!

  3. Joe

    This was a nice excuse to learn about Prolog! Just a note that for anyone installing pyswip with pip on Fedora 33 runs into this issue: https://github.com/yuce/pyswip/issues/49 . Installing with dnf as recommended by the article is probably easier.

  4. Jens Petersen

    I succeeded to do this in swipl (without any python).
    I just put all your assertz’s in a file triangles.pl,
    then load it with

    swipl -l triangles.pl

    ,
    and in the repl enter

    triangle(A,B,C), print(A), print(B), print(C), nl, fail.

    to print out the results.

    I would like to mention the datalog language (which is in Fedora) and its modern variant souffle too in this context.

    • Dave Sherratt

      If doing it entirely in Prolog, all those “assertz/1″s can be avoided. My version is as follows.

      /* Set up the lines */

      line([a, e, k]).
      line([a, d, f, j]).
      line([a, c, g, i]).
      line([a, b, h]).
      line([b, c, d, e]).
      line([e, f, g, h]).
      line([h, i, j, k]).

      /* Define a triangle */

      triangle(A, B, C) :-
      line(L1),
      line(L2),
      line(L3),
      L1 \= L2,
      member(A, L1),
      member(B, L1),
      member(B, L2),
      member(C, L2),
      member(C, L3),
      member(A, L3),
      A @< B,
      B @< C.

      /* Generate and print all triangles and count them */

      :- assertz( no_triangles( 0 ) ) .

      triangles :-
      triangle( A , B , C ) ,
      format( ‘A = ~w , B = ~w , C = ~w .~n’ , [ A , B , C ] ) ,
      retract( no_triangles( N ) ) ,
      Np1 #= N + 1 ,
      assertz( no_triangles( Np1 ) ) ,
      fail .

      triangles :-
      no_triangles( N ) ,
      format( ‘There are ~w triangles.~n’ , N ) .

      The clunky last clauses, viz “:- assertz/1” and “triangles/1” have been added to print all the solutions and count the number of triangles, for which I did need “assertz/1”.

      • Dave Sherratt

        A less clunky way of generating and printing all triangles and counting them, uses “setof/3”, and is given below. However, it does entail more lines of code.

        /* Generate and print all triangles and count them */

        triangles( triangle( A , B , C ) ) :-
        triangle( A , B , C ) .

        print_triangle( triangle( A , B , C ) ) :-
        format( ‘A = ~w , B = ~w , C = ~w .~n’ , [ A , B , C ] ) .

        print_triangles( [ T | Ts ] ) :-
        print_triangle( T ) ,
        print_triangles( Ts ) .
        print_triangles( [] ) .

        triangles :-
        setof( T , triangles( T ) , Ts ) ,
        length( Ts , Count ) ,
        format( ‘There are ~w triangles as follows.~n’ , Count ) ,
        print_triangles( Ts ) .

  5. Jan Tack

    I am very happy that fedora magazine dedicates an article to Prolog. The language is old, but can solve certain problems better and more elegantly than any other language.

    All those who want to get their hands dirty and their heads burning will find 99 exercises here, which become more challenging from time to time and build on each other:

    https://sites.google.com/site/prologsite/prolog-problems

Comments are Closed

The opinions expressed on this website are those of each author, not of the author's employer or of Red Hat. Fedora Magazine aspires to publish all content under a Creative Commons license but may not be able to do so in all cases. You are responsible for ensuring that you have the necessary permission to reuse any work on this site. The Fedora logo is a trademark of Red Hat, Inc. Terms and Conditions