Programming and Program Design 2

Unit 7 – Logic Paradigm

Unit 7 – Logic Paradigm

10 hours |

Introduction

In this unit we meet our second example of a paradigm shift from the procedural imperative and object oriented paradigms to in this case the logic (declarative) paradigm. In this paradigm, programmers focus on the goals of a computation rather than the development of an algorithm to achieve these goals. In the course text, Gabbrielli and Martini give R. Kowalski's definition of an algorithm as:

Algorithm = Logic + Control

In the Imperative paradigm, for example a programmer focuses on both what is to be achieved (the logic involved) and the how the goals are to be achieved (control).

In the logic paradigm, programmers focus only on the logic, the what, that has to be achieved. The control (or how) part of an algorithm is left to the abstract machine. The technique we wish to consider here is referred to as resolution and involves the interpreter searching through the set of all possible solutions.

An Example

We commence this unit with two examples of problems, the n queen problem and a list problem, both of which are suitable candidates for solving via the logic paradigm.

Task
  1. Draw an 8x8 chess board. Place a queen (or it's representative) at the top left hand square of the board. Now draw a straight line through the squares that the queen could move to.
  2. Now place the queen in the middle of an 8x8 board and once again draw a straight line through the squares that the queen could move to.

In a game of chess a queen is allowed to move any number of spaces in either a horizontal, vertical or diagonal direction, provided its path is not blocked by another chess piece on the board. To see the range of moves that are available to the queen.

The n queen problem involves the following: Given N queens, from the game of chess, determine how many queens may be placed on an m x m board such that no queen may capture another queen in a single move.

Starting with a 1x1 board, then a 2x2 board, then a 3x3 board, … establish the maximum number of queens that may be placed on the board such that no queen may capture another queen in a single move.

The N Queen Problem Introduction

Task

Using your favourite search engine investigate the following:

  • Resolution
  • Constraint
  • Nondeterminism
  • Backtracking
  • The N queen problem

Compare the results that you obtained above with those found online. Did they use the same or similar approach to how you solved the problem?

Discussion

Using Studynet, discuss your findings with each other, in particular, the solutions that found the approach that you took and the approach taken by others online.

Task (Optional)

Read 12.1.1 A (list) Example in Chapter Twelve: The Logic Paradigm from the course text by Gabbrielli and Martini (from page 371 to page 744 inclusive).

Propositions Predicates and the Horn Clause

The development of the logic paradigm is said to have been driven by researchers in 'natural language processing', and 'automatic theorem proving'. The specifications for a logic problem are expressed using mathematical logic in terms of predicate and propositional logic and so in this session we review some of the concepts involved.

Task

Using the wiki state what the following mean to you:

  • Propositional logic. How do we combine propositions?
  • Propositional calculus
  • Predicate logic.
Task
Using the internet and the course text explain what is meant by a Horn Clause. What relationship, if any, does a Horn Clause have with the Logic Paradigm? What is meant by resolution, unification and instantiation? Examples?
Discussion

Present your findings on Studynet using the class discussion. Do you all agree?

A Programming Practical (Prolog)

Logic Programming is sometimes referred to as rule based programming. It was developed in the 1970s. Prolog (short for Programming Logic) was quickly recognised as the most popular logic programming language and this, it is said still holds true today.

We note that Prolog

  • does not store changeable data values (unlike the imperative or OO paradigms) and does not have executable statements
  • does not entertain a sequence of commands to change stored data vales from one state to another
  • works with the idea of a set of facts and rules for determining facts rather than on a sequence of executable commands
  • is derived from a form of mathematical logic and an associated concept of automatic proof
Task

Go to http://www.swi-prolog.org/ to download a copy of prolog for your particular platform (Windows, Linux, Mac OS).

I will be using Prolog for this practical session. Once you have obtained a copy of the program
Start SWI-Prolog.You should obtain a window similar to the one given below:

screen shot of Prolog

Task
  1. Work through the "Quick Introduction to Prolog found at http://www.cs.ccsu.edu/~markov/ccsu_courses/prolog.txt. Make a note of anything (if at all) that doesn't quite work out in the quick introduction.
  2. Alternatively work through the tutorials found at http://www.swi-prolog.org/
  3. Once you have completed the quick introduction in part i) proceed with the following:
    • Select New … from the File drop down menu
    • Type in < user.pl > under File name and select return
    • Type in the following (and be careful to include the full stops or your program will not compile):
      squiggle(a,b).
      squiggle(a,c).
      squiggle(b,d).
      squiggle(c,e).
  4. Save your program and enter the following into SWI-Prolog:
    1. ?- squiggle(a,c).
    2. ?- squiggle(a,d).
    3. ?- squiggle(d,a).
    4. ?- squiggle(d,e).
    5. ?- squiggle(a,e).
    6. ?- squiggle(a,f).
    7. ?- answer(a,c).
Discussion

Discuss your findings on Studynet. What did you find? Could you find a Prolog programme for the n queen problem?

Task (Recursion)
  1. Using a search engine of your own choosing can you find an example of Prolog code that illustrates recursion? Does it work in SWI-Prolog?
  2. Define a function that calculates factorials in Prolog where n! = n*(n-1)*(n-2)….3*2*1.
    Test your function with factorial(2, X). , factorial(3, X). , factorial(4, X). , and so forth.
  3. Use the trace predicate on your factorial function in finding the value of 4! type( trace(factorial/2).)
  4. 4. What does listing (factorial/2). produce?
  5. 5. Write a recursive function in Prolog that gives the nth Fibonacci number.
Task (Lists)

The fundamental data structure used when programming in Prolog is the list. Here we consider a selection of techniques employed with lists.

  1. The list format in prolog is the same as in Haskell. Square brackets with entries separated by commas. For example X = [1, 2, 3].

    Type in the following lists:

    1. L = [my, dog, has, many, fleas].
    2. M = [many, fleas, spoil, the, picnic].

      Now type in:

    3. member (dog, L).
    4. member(pic,M).
    5. prefix(Answer, L).
    6. suffix(Answer, L).
    7. suffix(Answer, L). prefix(Answer, L).

      Curious?

Discussion

Discuss your findings on Studynet.