Question

*Explain the difference between procedural and nonprocedural languages. Use specific procedural
and nonprocedural languages of your choice to illustrate the difference.
*Explain what is backtracking in Prolog systems, and why backtracking is necessary.
*Explain resolution and unification in Prolog, and their relationship.

*Write Prolog programs for the following problems:
a) Reverse a list.
b) Find the length of a list.
c) Find the average of a list of numbers.

*Write Scheme programs for the following problems:
a) Reverse a list.
b) Find the length of a list.
c) Find the average of a list of numbers.

Answer 1

question no.1 -

procedural languages:

In procedural languages, the program code is written as a sequence of instructions. User has to specify “what to do” and also “how to do” (step by step procedure). These instructions are executed in the sequential order. These instructions are written to solve specific problems.

Examples of Procedural languages:
FORTRAN, COBOL, ALGOL, BASIC, C and Pascal.

The programs constructed using procedural language comprised of a sequence of statements, where the memory location values change according to the execution of the different statements in order to enter a new state. The procedural language syntax is given below:

statement1;
statement2;
————–

Example of procedural language (FORTRAN 90) :

 PROGRAM Triangle
     IMPLICIT NONE
     REAL :: a, b, c, Area
     PRINT *, 'Welcome, please enter the&
              &lengths of the 3 sides.'
     READ *, a, b, c
     PRINT *, 'Triangle''s area:  ', Area(a,b,c)
    END PROGRAM Triangle
    FUNCTION Area(x,y,z)
     IMPLICIT NONE
     REAL :: Area            ! function type
     REAL, INTENT( IN ) :: x, y, z
     REAL :: theta, height
     theta = ACOS((x**2+y**2-z**2)/(2.0*x*y))
     height = x*SIN(theta); Area = 0.5*y*height
    END FUNCTION Area

Non-Procedural Language:

In the non-procedural languages, the user has to specify only “what to do” and not “how to do”. It is also known as an applicative or functional language. It involves the development of the functions from other functions to construct more complex functions.

Examples of Non-Procedural languages:
SQL, PROLOG, LISP.

it can be applied to the initial data to arrive at the final result. Nonprocedural language syntax is shown below:

function_n(…. function2 (fucntion1 (data) ))

Example of procedural language (SQL) :

SELECT * FROM Customers
WHERE Country='Mexico';

PROCEDURAL LANGUAGE	NON-PROCEDURAL LANGUAGE
It is command-driven language.	It is a function-driven language
It works through the state of machine.	It works through the mathematical functions.
Its semantics are quite tough.	Its semantics are very simple.
It returns only restricted data types and allowed values.	It can return any datatype or value
Overall efficiency is very high.	Overall efficiency is low as compared to Procedural Language.
Size of the program written in Procedural language is large.	Size of the Non-Procedural language programs are small.
It is not suitable for time critical applications.	It is suitable for time critical applications.
Iterative loops and Recursive calls both are used in the Procedural languages.	Recursive calls are used in Non-Procedural languages.

Question no.2 -

Backtracking and its Importance :

first we have to understand the process and meaning of backtracking

Often, when solving real problems, you must pursue a path to its logical conclusion. If this conclusion does not give the answer you were looking for, you must choose an alternate path. For instance, you might have played maze games when you were a child. One sure way to find the end of the maze was to turn left at every fork in the maze until you hit a dead end. At that point you would back up to the last fork, and try the right-hand path, once again turning left at each branch encountered. By methodically trying each alternate path, you would eventually find the right path and win the game.

Visual Prolog uses this same backing-up-and-trying-again method, called backtracking, to find a solution to a given problem. As Visual Prolog begins to look for a solution to a problem (or goal), it might have to decide between two possible cases. It sets a marker at the branching spot (known as a backtracking point) and selects the first subgoal to pursue. If that subgoal fails (equivalent to reaching a dead end), Visual Prolog will backtrack to the back-tracking point and try an alternate subgoal.

Backtracking is basically a form of searching. In the context of Prolog, suppose that the Prolog interpreter is trying to satisfy a sequence of goals goal_1, goal_2. When the Prolog interpreter finds a set of variable bindings which allow goal_1 to be satisfied, it commits itself to those bindings, and then seeks to satisfy goal_2. Eventually one of two things happens: (a) goal_2 is satisfied and finished with; or (b) goal_2 cannot be satisfied. In either case, Prolog backtracks. That is, it "un-commits" itself to the variable bindings it made in satisfying goal_1 and goes looking for a different set of variable bindings that allow goal_1 to be satisfied. If it finds a second set of such bindings, it commits to them, and proceeds to try to satisfy goal_2 again, with the new bindings. In case (a), the Prolog interpreter is looking for extra solutions, while in case (b) it is still looking for the first solution. So backtracking may serve to find extra solutions to a problem, or to continue the search for a first solution, when a first set of assumptions (i.e. variable bindings) turns out not to lead to a solution.

Example: here is the definition of the built-in Prolog predicate member:

     member(X, [X | Rest]). % X is a member if its the first element
     member(X, [Y | Rest]) :-
     member(X, Rest).   % otherwise, check if X is in the Rest

You may not think of member as a backtracking predicate, but backtracking is built into Prolog, so in suitable circumstances, member will backtrack:

   ?- member(X, [a, b, c]).
   X = a ;
   X = b ;
   X = c ;
   false.

Here member backtracks to find every possible solution to the query given to it. Consider also:

   ?- member(X, [a, a, a]).
   X = a ;
   X = a ;
   X = a ;
   false.

Here member backtracks even though it keeps on finding the same answer. What about

   ?- member(a, [a, a, a]).
   true ;
   true ;
   true ;
   false.

This is because prolog has three ways of proving that a is a member of [a, a, a].

The term backtracking also applies to seeking several sets of variable bindings to satisfy a single goal.

In some circumstances, it may be desirable to inhibit backtracking, as when only a single solution is required. The Prolog cut goal allows this.

Question no.3 -

Resolution in prolog : Resolution is one kind of proof technique that works this way - (i) select two clauses that contain conflicting terms (ii) combine those two clauses and (iii) cancel out the conflicting terms.

In simple words resolution is inference mechanism. Let's say we have clauses m :- b. and t :- p, m, z. So from that we can infer t :- p, b, z. - that is called resolution. Means, when you resolve two clauses you get one new clause. Another easy example, we have two sentences (1) All women like shopping. (2) Olivia is a woman. Now we ask query 'Who likes shopping'. So, by resolving above sentences we can have one new sentence Olivia likes shopping

For example we have following statements,   (1) If it is a pleasant day you will do strawberry picking   (2) If you are doing strawberry picking you are happy.

Above statements can be written in propositional logic like this - (1) strawberry_picking ← pleasant (2) happy ← strawberry_picking

And again these statements can be written in CNF like this - (1) (strawberry_picking ∨~pleasant) ∧ (2) (happy ∨~strawberry_picking)

By resolving these two clauses and cancelling out the conflicting terms 'strawberry_picking' and '~strawberry_picking', we can have one new clause, (3) ~pleasant ∨ happy

Prolog execution is based on the Resolution proof method. Resolution is a technique of producing a new clause by resolving two clauses that contain a complimentary literal and Resolution produces proof by Refutation. "A clause is a formula consisting of a disjunction of literals and any formula can be converted into set of clause[B]". For example,

(1) q is true if p is true. i.e. q :- p or q ← p or you can write it other way around like - 'if p is true then q is true' i.e. p → q (in propositional logic). From this we can say, either q is true or p is not true and in CNF it is written as q ∨~p.

(2) q is true if p and z are true. i.e. q :- p, z or q ← p∧z. From this we can say, either p is true or p and z are not true and in CNF it is written as q ∨~(p∧z). But ~(p∧z) is equivalent to ~p∨~z. So, finally it is written as q ∨~p∨~z.

Prolog is based on the predicate logic and Predicate logic is an extension of Propositional logic with variables, functions, etc. Proposition is a statement that can be either true or false. Every propositional formula can be converted into an equivalent formula i.e. in CNF. Conjunctive Normal Form (CNF) is a particular way to write logical formulas.

Unification : Deduction in prolog is based on the Unification Let's understand these terminologies by examples rather than by definitions. Remember one thing, matching terms are unified and variables get instantiated. In other words, "Unification leads to Instantiation".  

Example 1: Let's see for below prolog program - how unification and instantiation take place after querying.

Facts :
likes(john, jane).
  likes(jane, john).
Query :
?- likes(john, X).
Answer : X = jane.

Here upon asking the query first prolog start to search matching terms in 'Facts' in top-down manner for 'likes' predicate with two arguments and it can match likes(john, ...) i.e. Unification. Then it looks for the value of X asked in query and it returns answer X = jane i.e. Instantiation - X is instantiated to 'jane'.

Example 2 : At the prolog query prompt, when you write below query,

?- owns(X, car(bmw)) = owns(Y, car(C)).
You will get Answer : X = Y, C = bmw.  

Here owns(X, car(bmw))  and owns(Y, car(C))  unifies -- because (i) predicate names 'owns' are same on both side (ii) number of arguments for that predicate, i.e. 2, are equal both side. (iii) 2nd argument with 'car' predicate inside the brackets are same both side and even in that predicate again number of arguments are same. So, here terms unify in which X=Y. So, Y is substituted with X -- i.e. written as {X | Y} and C is instantiated to bmw, -- written as {bmw | C} and this is called Unification with Instantiation.

But when you write ?- owns(X, car(bmw)) = likes(Y, car(C)). then prolog will return 'false' since it can not match the 'owns' and 'likes' predicates.

Question no. 3 (a) - Reverse a list

domains
    list=integer*
predicates
    reverse_list(list,list)
    reverse(list,list,list)
clauses
    
    reverse_list(Inputlist,Outputlist):-
    reverse(Inputlist,[],Outputlist).    
    reverse([],Outputlist,Outputlist).    

    reverse([Head|Tail],List1,List2):-
        reverse(Tail,[Head|List1],List2).


Output :

Goal: reverse_list([1,2,
3],X)                   
X=[3,2,1] 

Question no. 3 (b) - Find the length of a list

domains

    list=symbol*
predicates

    len(list)
    findlen(list,integer)

clauses

    len(X):-
        findlen(X,Count),
        write("\nLength Of List : "),
        write(Count).
        
    findlen([],X):-
        X=0.
    
    findlen([X|Tail],Count):-
        findlen(Tail,Prev),
        Count = Prev + 1.
        
OUT PUT
=======
Goal: len([a,b,c,d,e])

Length Of List : 5

Yes

Question no.3(c) - Find the average of the list of a number

domains

list=symbol*

predicates

sum( List, Integer ), length( List, Integer),

clauses

avg( List, Avg ):-
sum( x, Count ),
length( x, Count ),
( Length > 0
-> Avg is Sum / Length
; Avg is 0
)

OUT PUT :

L = [1, 2, 3, 4, 5],
Ave = 3

Question no.3(a) - scheme program for reverse a list

Reverse the order of elements in list L. Again, input is a single list. This is a shallow notion. I.e., if a list contains a list, then the sublist is unchanged; it simply appears in a different place.
Example: (reverse '(1 2 3 4 5) => (5 4 3 2 1)
Hint: To do this in linear time, create a helper function that takes 2 arguments, the list to be reversed, and the reversed list

(define (reverse2 lst)
  (if (null? lst) ()
    (append (reverse2 (cdr lst)) (list (car lst)))))

(define (append l1 l2)
  (if (null? l1) l2
      (cons (car l1) (append (cdr l1) l2))))

Using substitution model for (reverse2 (list 1 2 3 4))

;; (reverse2 (list 1 2 3 4))
;; (append (reverse2 (list 2 3 4)) (list 1))
;; (append (append (reverse2 (list 3 4)) (list 2)) (list 1))
;; (append (append (append (reverse2 (list 4)) (list 3)) (list 2)) (list 1))
;; (append (append (append (append (reverse2 ()) (list 4)) (list 3)) (list 2)) (list 1))
;; (append (append (append (append () (list 4)) (list 3)) (list 2)) (list 1))   
;; (append (append (append (list 4) (list 3)) (list 2)) (list 1))   
;; (append (append (list 4 3) (list 2)) (list 1))   
;; (append (list 4 3 2) (list 1))   
;; (list 4 3 2 1)

Question no.3(b) - scheme program for find the length of a list

(define (all-lengths lists)
(if (null? lists)
'()
(cons (length (car lists))
(all-lengths (cdr lists)))))

(define (all-equal? head lengths)
(if (null? lengths)
true
(and (= head (car lengths))
(all-equal? head (cdr lengths)))))

(define (list-counter? lists)
(let ((lengths (all-lengths lists)))
(all-equal? (car lengths) (cdr lengths))))

so we are dividing the problem in two steps, first create a new list with the lengths of each sublist - that's what all-lengths does. Then, compare the first element in a list with the rest of the elements, and see if they're all equal - that's what all-equal? does. Finally, list-counter? wraps it all together, calling both of the previous procedures with the right parameters.

Or even simpler (and shorter), by using list procedures (higher-order procedures):

(define (list-counter? lists)
(apply = (map length lists)))

For understanding the second solution, observe that all-lengths and all-equal?
represent special cases of more general procedures. When we need to create a new
list with the result of applying a procedure to each of the elements of another
list, we use map. And when we need to apply a procedure (= in this case) to all
of the elements of a list at the same time, we use apply.

Question no.3(c) - scheme program for Find the average of a list of numbers.

(define (average xs)
(let loop ((xs xs)
(sum 0)
(len 0))
(if (empty? xs)
(/ sum len)
(loop (cdr xs)
(+ sum (car xs))
(+ len 1)))))

(average '(10 60 3 55 15 45 40)

OUTPUT :

;; 32 4/7

Our average procedure also throws an error when an empty list is given

(average '())
;; error /: division by zero

Alternatively, we could write average using a named let expression. Also O(n).