Lists, Operators and Arithmetic

• Here we study:

  • Lists
  • Operations on lists

Representing of Lists (3.1)

• List is a usual structure as any structure is Prolog
• Head and tails of a list
• .(Head, Tail): is the representation of the list is Prolog
• Nested Lists: Hobbies 1, 2 and L
• Tail = [b, c] and L = .(a, Tail) OR L = [a | Tail]
• The difference between sets and lists that the order of items in the list matter and in set doesn’t matte
• Membership Operation:

• Concatenation Operation:

  • using the inverse parameters: the power set of a concatenation

  • months example:

    • before and after specific moth
    • months after and before specific month
• Sub List
• Permutation

3.3 Operator Notation

• The difference between:

  • Infix Operators: xfx, xfy and yfx
  • Prefix Operators: fx and fy
  • Postfix: xf and yf
• Directives: act as operator definition
• No operation on data is associated with an operator

3.4 Arithmetic

• The is operator
• Comparison operators:

>=, =<, =:=, =\=

Syntax and Meaning of Prolog Programs

• Chapter Objectives:

  • Prolog syntax and semantics
  • Simple data objects (atoms, numbers and variables)
  • Structured objects
  • Matching as the fundamental operation on objects
  • Declarative meaning of a program
  • Procedural meaning of a program
  • Relation between declarative and procedural meaning of a program

  • Altering the procedural meaning by reordering clauses and goals

  (Section 2.1) Data Objects

• The Prolog system recognizes the type of an object in the program by its syntactic from

• Objects types in Prolog:

• Variables start with upper-case letters and atoms start with lower-case

(Section 2.1.1) Atoms and Numbers

• If we want to define a variable with upper-case we can write it between quotes ‘Var’
• Integer range: -16383 à 16383

• Reason of not including real numbers (widely) in Prolog:

  • To make the program neat
  • The numerical error

(Section 2.1.2) Variables

• They could start with uppercase letter or _ character

• Anonymous variable is used is cases like this:

  • Haschild(X) :- parent(X, Y) à haschild :- parent(X, _)
• The lexical scope of variable name is one clause, but not in constants

(Section 2.1.3) Structures (Structured objects)

• Structures are objects that have several components the components could be structures

• date(day, month, year):

  • Here date is called functor
  • And day, month and year are called structure argument
• All Prolog objects are terms
• All structured objects can be pictured as trees
• In composite structures the root is called principle functor of the term

• The functions is defined by the following:

  • Name, as atom
  • Arity, number of arguments

(Section 2.2) Matching

• Rules to decide whether two terms S and T match:

  • If S and T are constants the match if they have the same value
  • If S is variable and T is anything they match, then S is instantiated to T

  • If S and T are structure, they match if:

    • S and T have the same principle functor
    • All their corresponding components

(Section 2.3) Declarative meaning of Prolog programs

• The declarative meaning of programs determines whether a given goal is true, and in which variables
• Instance of clause C means that the clause C with each of its variables substituted by term
• Variant of clause C is such instance of C where each variable is substituted by variable

• A goal G is true if and only if:

  • There is a clause C in the program such that

  • C has instance I, that satisfies:

    • Head of I is identical to G
    • All the goals in the body of I are true

(Section 2.4 Procedural Meaning)

• To make the program faster order the goal conditions in order to be the mostly true then the false

(Section 2.6) Order of Clauses and Goals

• P :- p, infinite loop
• Matching in Prolog corresponds to what is called unification in logic

(Section 2.7) Remarks on Relations between Prolog and Logic

The best way to describe Prolog programs theoretically is in math logic

An Overview of Prolog

• Chapter Objectives:

  • Reviews Prolog basic mechanisms through examples

  • Many important concepts are also introduced

  (Section 1.1) Defining Family Relations

• Ways of Asking for Goals:

  • Parent(Ahmed, Mohammed)
  • Parent(X, Mohammed)
  • Parent(Ahmed, X)
  • Parent(X, Y)

  • Composite Query (Gets the Grandfather):

    • Parent(Y, Jim), Parent(X, Y)
• Constant variables and called atoms and general variables are called variables

• Rules has:

  • A conditional part (the R.H.S of the rule)
  • A conclusion part (the L.H.S of the rule) Also called the head of a clause
  • Offspring(Y, X) :- parent(X, Y)
• If you will use an existing predicate to get a result (parent, offspring) then the result should be mentioned in the Facts part

(Section 1.2) extending the program

• When designing a Prolog program you should design it on a graph:

  • The nodes are the objects (arguments of relation)

  • The edges (Arcs) correspond to binary relation

    • The arcs oriented so as to point from the 1^st argument to the 2^nd one
  • Unary relations are indicated by making the corresponding objects with the name of the relation
  • The dashed arcs corresponds to facts that are resulted from existing relations

• Prolog comments are

  • Multiple Lines: /*The commented Code*/
  • Single Line: %
• Add nondeterm keyword to use X and Y symbols (that get any true result of the relation)

• Some important notes about this section:

  • Prolog clauses are: facts, rules and questions

  • Facts declare things that are always, unconditionally true

    • Facts are the clauses with empty body

  • Rules declare things that are depending on a given condition

    • Rules have head and non-empty body

  • Question is the user asking for what things are true and other false

    • Questions have the body

  • The Prolog clauses consist of head and body:

    • Body: is the list of goals separated by commas (conjunction)

  (Section 1.3) A Recursive Rule Definition

• Sometimes it’s convenient to consider the whole set of clauses about the same relation. Such a set of clauses is called Procedure

  (Section 1.4) How Prolog Answers Questions

• A question to Prolog is always a sequence of one or more goals
• To satisfy a goal means to demonstrate that the goal logically follows from the facts and rules in the program

• Prolog interpretation in mathematical terms:

  • Prolog accepts facts and rules as a set of axioms, and the user’s question as a conjectured theorem; then it tries to prove that theorem
• Instead of starting with simple facts given in the program, Prolog starts with the goal and using rules substitutes the current goals with new goals, until new goals happen to be simple facts

• The execution trace of a Prolog has a form of a tree. The nodes are the goals (the satisfied goals) the arcs between nodes are clauses that transform the program from one goals to another. The top goal is satisfied when a path is found from the root node (top goal) to a leaf node labeled ‘yes’. A leaf node labeled ‘yes’ is a simple fact. The execution of prolog program is the searching for such paths. During searching Prolog could encounter a unsuccessful branch then automatically it backtracks to the previous node and try to apply alternative clause at that node

  (Section 1.5) Declarative and Procedural Meaning of Programs

• Meaning of Prolog programs:

  • Declarative meaning:

    • It concerned only with the relations defined by the program
    • The declarative meaning determines what will be the output of the program

  • Procedural meaning:

    • It determines how the output obtained; thus, how are the relations actually evaluated by the Prolog system

• Thus, the programmer should concentrate mainly about the declarative meaning and avoid being distracted by the executional details

  Summary

• Prolog programming consists of defining relations and querying about relations
• A program consists of clauses. There are three types: facts, rules and questions
• A relations can be satisfied by facts, simply stating n-tuples of objects that satisfy the relation, or by stating rules about the relation
• A procedure is a set of clauses about the same relation

• The following concepts was introduced in this chapter:

• Clause, fact, rule and question
• Head and body of a clause
• Recursive rule, recursive definition
• Procedure
• Atom, variable
• Instantiation of a variable
• Goal
• Goal is satisfied
• Goal is unsatisfied
• Backtracking
• Declarative meaning and procedural meaning