Programming Language Concept

Just another Binusian blog site

Session 13 : Logic Programming Languages



  • 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 results are stated (not detailed procedures for 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


  • 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


  • 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 is B / 17 + C

  • Not the same as an assignment statement!

The following is illegal:

Sum is Sum + 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


Email will not be published

Website example

Your Comment: