CS计算机代考程序代写 database algorithm interpreter Java concurrency Fortran prolog data structure compiler assembly Logic Programming

Logic Programming
March 17, 2021
COM S 342 Principles of Programming Languages @ Iowa State University 1

COM S 342 Principles of Programming Languages @ Iowa State University 2

?- loves(X, tom). mary
?- loves(mary, Y). tom
?- loves(mary, jane).
fCaOlMseS 342 Principles of Programming Languages @ Iowa State University 3

What is Logic Programming
There are many (overlapping) perspectives on logic programming: 􏰉 A very high level programming language
􏰉 An interpretation of declarative specifications
􏰉 Non-procedural programming
􏰉 Algorithms minus control 􏰉 Computations as deduction 􏰉 Theorem proving
COM S 342 Principles of Programming Languages @ Iowa State University 4

A Very High Level Language
􏰉 A good programming language should not encumber the programmer with non-essential details.
􏰉 The development of programming languages has been toward freeing the programmer of more and more of the details
􏰉 ASSEMBLY LANGUAGE: symbolic encoding of data and instructions.
􏰉 FORTRAN: allocation of variables to memory locations, register saving, etc.
􏰉 ML: explicit variable type declarations
􏰉 JAVA: Platform specifics
􏰉 Logic Programming Languages are a class of languages which attempt to free us from having to worry about many aspects of explicit control.
COM S 342 Principles of Programming Languages @ Iowa State University 5

An Interpretation of Declarative Specifications
􏰉 Logical statement: Forall X and Y, X is the father of Y if X is a parent of Y and the gender of X is male.
􏰉 Prolog code: father(X,Y) :-
parent(X,Y), gender(X,male).
􏰉 Interpret it in two slightly different ways:
􏰉 declaratively – which must be true if a father relationship holds.
􏰉 procedurally: what to do to establish that a father relationship holds.
COM S 342 Principles of Programming Languages @ Iowa State University 6

Non-procedural Programming
􏰉 A non – procedural language one in which one specifies WHAT needs to be computed but not HOW it is to be done.
􏰉 it specifies a state with constraints, objects and relations: 􏰉 the set of objects involved in the computation
􏰉 the relationships which hold between them
􏰉 the constraints which must hold for the problem to be solved
􏰉 the language interpreter or compiler will decide HOW to satisfy the constraints.
COM S 342 Principles of Programming Languages @ Iowa State University 7

Algorithms Minus Control
􏰉 Nikolas Wirth (architect of Pascal) used the following slogan as the title of a book: Algorithms + Data Structures = Programs
􏰉 Bob Kowalski offers a similar one to express the central theme of logic programming: Algorithms = Logic + Control
􏰉 We can view the LOGIC component as: a specification of the essential logical constraints of a particular problem
􏰉 CONTROL component as: advice to an evaluation machine (e.g. an interpreter or compiler) on how to go about satisfying the constraints)
COM S 342 Principles of Programming Languages @ Iowa State University 8

Computation as Deduction
􏰉 Computation is related to logical proofs and is not restricted to functional (Church) or imperative (Turing/Von Neumann) computation models.
􏰉 inductive reasoning: particular cases to general cases – inductive reasonable and proof
􏰉 deductive reasoning:
All men are mortal. (First premise) Socrates is a man. (Second premise) Therefore, Socrates is mortal. (Conclusion)
􏰉 It uses the language of logic to express data and programs, e.g., Forall X and Y, X is the father of Y if X is a parent of Y and the gender of X is male.
􏰉 Current logic programming languages use first order logic (FOL)
􏰉 Propositions, e.g., A is father of B, predicates, e.g., parent (X Y), and quantifier symbols such as ∃ and ∀ on objects (more in discrete maths books).
COM S 342 Principles of Programming Languages @ Iowa State University 9

Theorem Proving
􏰉 Logic programming uses the notion of an automatic theorem prover as an interpreter.
􏰉 The theorem prover derives a desired solution from an initial set of axioms.
􏰉 Note that the proof must be a ”constructive” one so that more than a true/false answer can be obtained, e.g., the answer to exists x such that x = sqrt(16) should be x = 4 or x = -4 rather than true
COM S 342 Principles of Programming Languages @ Iowa State University 10

A Short History
1965 Efficient theorem provers. Resolution (Alan Robinson)
1969 Theorem Proving for problem solving. (Cordell Green)
1969 PLANNER, theorem proving as programming (Carl Hewett) 1970 Micro – Planner, an implementation (Sussman, Charniak and Winograd)
1970 Prolog, an implementation (Alain Colmerauer)
1972 Book: Logic for Problem Solving. (Kowalski)
1977 DEC – 10 Prolog, an efficient interpreter/compiler (Warren and Pereira)
1982 Japan’s 5th Generation Computer Project
1985 Datalog and deductive databases
1995 Prolog interpreter embedded in NT
COM S 342 Principles of Programming Languages @ Iowa State University 11

PROLOG is the FORTRAN of Logic Programming
􏰉 Prolog is the only widely used logic programming language.
􏰉 As a Logic Programming language, it has a number of advantages: simple, small, fast, easy to write good compilers for it.
􏰉 Disadvantages
􏰉 It has a fixed control strategy.
􏰉 It has a strong procedural aspect
􏰉 limited support parallelism or concurrency or multi-threading.
􏰉 Datalog: is a subset of Prolog, fully declarative
COM S 342 Principles of Programming Languages @ Iowa State University 12

Prolog Programming
􏰉 Step 1: presenting knowledge: predicate logic
􏰉 fact: proposition that’s unconditional true
􏰉 rule: proposition that’s conditional true; dependent on other
propositions
􏰉 a fact or a rule is a statement or clause in Prolog.
􏰉 Step 2: ”execute a program”: make inference from a database of facts and rules.
COM S 342 Principles of Programming Languages @ Iowa State University 13

COM S 342 Principles of Programming Languages @ Iowa State University 14

COM S 342 Principles of Programming Languages @ Iowa State University 15

COM S 342 Principles of Programming Languages @ Iowa State University 16

COM S 342 Principles of Programming Languages @ Iowa State University 17

COM S 342 Principles of Programming Languages @ Iowa State University 18

COM S 342 Principles of Programming Languages @ Iowa State University 19

COM S 342 Principles of Programming Languages @ Iowa State University 20

?-reach(a, X) b, c
COM S 342 Principles of Programming Languages @ Iowa State University 21

COM S 342 Principles of Programming Languages @ Iowa State University 22

COM S 342 Principles of Programming Languages @ Iowa State University 23

COM S 342 Principles of Programming Languages @ Iowa State University 24

COM S 342 Principles of Programming Languages @ Iowa State University 25

COM S 342 Principles of Programming Languages @ Iowa State University 26

COM S 342 Principles of Programming Languages @ Iowa State University 27

Swi-prolog Programming
􏰉 Install on mac: brew install swi-prolog
􏰉 Install on different machines: https://www.swi-prolog.org/build/ 􏰉 edit your program in any aditor and save it as test.pl
􏰉 run the program using: swipl -s test.pl
􏰉 stop running the program: halt.
􏰉 frequently used command link
Demo: case sensitive
COM S 342 Principles of Programming Languages @ Iowa State University 28

COM S 342 Principles of Programming Languages @ Iowa State University 29

COM S 342 Principles of Programming Languages @ Iowa State University 30

Recall, term can be constant, variable, functor.
COM S 342 Principles of Programming Languages @ Iowa State University 31

Soln: [W􏰊X,Y􏰊g(Z),Z􏰊h(x)]MGU Or, [W 􏰊 X, Y 􏰊 g(h(x)), Z 􏰊 h(x)] MGU
COM S 342 Principles of Programming Languages @ Iowa State University 32

COM S 342 Principles of Programming Languages @ Iowa State University 33

COM S 342 Principles of Programming Languages @ Iowa State University 34

COM S 342 Principles of Programming Languages @ Iowa State University 35

COM S 342 Principles of Programming Languages @ Iowa State University 36

COM S 342 Principles of Programming Languages @ Iowa State University 37

COM S 342 Principles of Programming Languages @ Iowa State University 38

COM S 342 Principles of Programming Languages @ Iowa State University 39

COM S 342 Principles of Programming Languages @ Iowa State University 40

COM S 342 Principles of Programming Languages @ Iowa State University 41

Example: search on graphs
COM S 342 Principles of Programming Languages @ Iowa State University 42

Example: write a parser with Prolog
COM S 342 Principles of Programming Languages @ Iowa State University 43

Example: write a parser with Prolog
COM S 342 Principles of Programming Languages @ Iowa State University 44

Logic Programming
􏰉 numbers: max
􏰉 list: append, reverse 􏰉 constraint problems
􏰉 language parsing
􏰉 graph search problems
COM S 342 Principles of Programming Languages @ Iowa State University 45