### Session 13 : Logic Programming Languages

## Introduction

- Programs in logic languages are expressed in a form of symbolic logic
- Use a logical inferencing process to produce results
*Declarative*rather that*procedural*:

Only specification of

resultsare stated (not detailedproceduresfor producing them)

## Overview of Logic Programming

- Declarative semantics

There is a simple way to determine the meaning of each statement

Simpler than the semantics of imperative languages

- Programming is nonprocedural

Programs do not state now a result is to be computed, but rather the form of the result

## Example: Sorting a List

- Describe the characteristics of a sorted list, not the process of rearranging a list

sort(old_list, new_list) Ì permute (old_list, new_list) Ç sorted (new_list)

sorted (list) Ì “j such that 1£ j < n, list(j) £ list (j+1)

## The Origins of Prolog

- University of Aix-Marseille (Calmerauer & Roussel)

Natural language processing

- University of Edinburgh (Kowalski)

Automated theorem proving

## Inferencing Process of Prolog

- Queries are called goals
- If a goal is a compound proposition, each of the facts is a subgoal
- To prove a goal is true, must find a chain of inference rules and/or facts. For goal Q:

P2 :- P1

P3 :- P2

…

Q :- Pn

- Process of proving a subgoal called matching, satisfying, or resolution

## Approaches

*Matching*is the process of proving a proposition- Proving a subgoal is called
*satisfying*the subgoal *Bottom-up resolution, forward chaining**Top-down resolution, backward chaining*- Prolog implementations use backward chaining

## Subgoal Strategies

- When goal has more than one subgoal, can use either

Depth-first search: find a complete proof for the first subgoal before working on others

Breadth-first search: work on all subgoals in parallel

- Prolog uses depth-first search

Can be done with fewer computer resources

## Backtracking

- With a goal with multiple subgoals, if fail to show truth of one of subgoals, reconsider previous subgoal to find an alternative solution:
*backtracking* - Begin search where previous search left off
- Can take lots of time and space because may find all possible proofs to every subgoal

## Simple Arithmetic

- Prolog supports integer variables and integer arithmetic
**is**operator: takes an arithmetic expression as right operand and variable as left operand

A

isB / 17 + C

- Not the same as an assignment statement!

The following is illegal:

Sum

isSum + Number.

## Deficiencies of Prolog

- Resolution order control

In a pure logic programming environment, the order of attempted matches is nondeterministic and all matches would be attempted concurrently

- The closed-world assumption

The only knowledge is what is in the database

- The negation problem

Anything not stated in the database is assumed to be false

- Intrinsic limitations

It is easy to state a sort process in logic, but difficult to actually do—it doesn’t know how to sort

## Applications of Logic Programming

- Relational database management systems
- Expert systems
- Natural language processing