Mimir:Draft2 Chapter5

From Openitware
Jump to: navigation, search

Back to Table of Contents


Chapter TODOs

  • fill in content
  • summary
  • exercises
  • key terms

Chapter 5: Logic Programming

"If you want to gather honey, don't kick over the beehive."

The Logic Paradigm

Logic programming is a programming paradigm based on formal logic. A program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, Answer set programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

Datalog

Datalog is a truly declarative logic programming language that syntactically is a subset of Prolog. It is often used as a query language for deductive databases.Datalog has found new application in data integration, information extraction, networking, program analysis, security, and cloud computing.Unlike in Prolog, statements of a Datalog program can be stated in any order. Furthermore, Datalog queries on finite sets are guaranteed to terminate, so Datalog does not have Prolog's cut operator. This makes Datalog a truly declarative language.Query evaluation with Datalog is based on first order logic.Some widely used database systems include ideas and algorithms developed for Datalog.

Answer Set Programming

Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming.In a more general sense, ASP includes all applications of answer sets to knowledge representation[1][2] and the use of Prolog-style query evaluation for solving problems arising in these applications.

The language we will focus on for example is "Prolog".

Prolog

Introduction

Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of relations, represented as facts and rules.The language was first conceived by a group around Alain Colmerauer in Marseille, France, in the early 1970s and the first Prolog system was developed in 1972 by Colmerauer with Philippe Roussel.

The language has been used for theorem proving,[8] expert systems,[9] as well as its original intended field of use, natural language processing.[10][11] Modern Prolog environments support creating graphical user interfaces, as well as administrative and networked applications.

Prolog Syntax

A program, or database, in Prolog consists of one or more predicates; each predicate consists of one or more clauses. A clause is a base clause if it is unconditionally true, that is, it has no "if part. <program> ::= <predicate> | <program><predicate>

<predicate> ::= <clause> | <predicate><clause>

<clause> ::= <base clause> | <nonbase clause>

Two clauses belong to the same predicate if they have the same functor (name) and the same arity (number of arguments). Thus, mother(jane) and mother(jane, jim) are different predicates. <base clause> ::= <structure> .

<nonbase clause> ::= <structure> :- <structures> .

<structures> ::= <structure> | <structure> , <structures>

A structure is a functor followed by zero or more arguments; the arguments are enclosed in parentheses and separated by commas. There must be no space between the functor and the opening parenthesis! If there are no arguments, the parentheses are omitted. <structure> ::= <name> | <name> ( <arguments> )

<arguments> ::= <argument> | <argument> , <arguments>


Data Types

Prolog's single data type is the term. Terms are either atoms, numbers, variables or compound terms.

  • An atom is a general-purpose name with no inherent meaning. Examples of atoms include x, blue, 'Taco', and 'some atom'.
  • Numbers can be floats or integers.
  • Variables are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. Variables closely resemble variables in logic in that they are placeholders for arbitrary terms.
  • A compound term is composed of an atom called a "functor" and a number of "arguments", which are again terms. Compound terms are ordinarily written as a functor followed by a comma-separated list of argument terms, which is contained in parentheses. The number of arguments is called the term's arity. An atom can be regarded as a compound term with arity zero.

Execution

Execution of a Prolog program is initiated by the user's posting of a single goal, called the query. Logically, the Prolog engine tries to find a resolution refutation of the negated query. The resolution method used by Prolog is called SLD resolution. If the negated query can be refuted, it follows that the query, with the appropriate variable bindings in place, is a logical consequence of the program. In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded.

Programming in Prolog

In Prolog, loading code is referred to as consulting. Prolog can be used interactively by entering queries at the Prolog prompt ?-. If there is no solution, Prolog writes no. If a solution exists then it is printed. If there are multiple solutions to the query, then these can be requested by entering a semi-colon ;. There are guidelines on good programming practice to improve code efficiency, readability and maintability.

Summary

A quick summary of the chapter should go here

Key Terms

A list of key terms should go here. This should be created using some sort of glossary type plugin.

Problem Sets

A list of practice problems