# Prolog

Essay by EssaySwap ContributorUniversity, Bachelor's February 2008

What is prolog? Prolog is a descriptive language because a program describes the problem rather than the steps taken to solve the problem. This allows the program to concentrate on the problem rather than the machineÃÂ¢ÃÂÃÂs solution to the problem. The description of a problem also describes the procedures for solving the problem. Prolog is also a procedural language, when you describe the relationship between objects, you can also define an executable procedure.

The logical aspect of the language makes it possible to describe a program most simply, the procedural side of prolog makes it possible to write practical applications. ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ Characteristics of logic programming: Like predicate calculus, prolog defines a way to make logical assertions and to prove theorems based on those assertions. In prolog problems are described in terms of ÃÂ¢ÃÂÃÂFactsÃÂ¢ÃÂÃÂ and ÃÂ¢ÃÂÃÂRulesÃÂ¢ÃÂÃÂ, where facts are statements that are simply true and analogous to logical assertions; Rules are similar to theorem proofs.

In prolog facts are accessed and rules are set into action by asking questions.

Prolog facts are expressed as clauses and a collection of related clauses is called a predicate, a predicate provides a consistent way of grouping similar facts. Clauses are stored in the database in the same order in which you enter them and it will retrieve this clauses in the same order, therefore the ordering of clauses in the database is as significant as the facts themselves. This order can ensure that your program executes properly.

Note that prolog contains a database very similar to a relational database, this database is where facts and rules are stored, the above description of organized facts storage is one similarity, also the database is composed of rows called instances in where facts are stored, each row contains an individual fact, an instance consists of one or more columns, called attributes, all instances in the same relation(table) have the same number of attributes each related clause has the same number of arguments, and like the columns of a table related arguments in each clause hold the same type of information. ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ My implementation in comparison with an implementation in a procedural(functional or imperative) language: In any of the above mentioned conventional languages, a program is a collection of procedures that are executed in a specific order, in prolog is a collection of facts and rules, different than functional and imperative languages, you are not concern with the details of program execution, because prolog defines the order in which they are executed.

In conventional languages it is possible to assign new values to variables, prolog is less specific, prolog can ÃÂ¢ÃÂÃÂun-instantiateÃÂ¢ÃÂÃÂ a variable if further processing proves the previous instantiation to be incorrect, it then ÃÂ¢ÃÂÃÂbacktracksÃÂ¢ÃÂÃÂ (backs up) to look for another possible value for the variable, this process is called backtracking.

All routines written in conventional programming languages are deterministic (no backtracking), because these languages do not operate on the concepts of matching, unification, and backtracking.

ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ ÃÂÃ Implementation Deterministic predicates do not backtrack, they are executed only once and do not produce alternate solutions.

Non-deterministic predicates backtrack and produce alternate solutions if necessary.

Tokenization the process of finding tokens in a list of characters. It converts them the list of characters to alist of tokens, which then parsed to the syntax and semantics analyzer. The process in which compilers, interpreters and command processor separate a string and posses methods of deriving the meaning of these statements. Tokenization and syntax analysis when taken together are referred to as parsing.

A token is the smallest meaningful object in a language, such as a word. Atoms, integers, operators, and variables are tokens in prolog. These tokens can be used to build clauses.

Tokenizer is a recursive predicate that act upon the head of the list and passes the tail to the next iteration. Each iteratrion looks at the head of the list to determine wether it encountered a tokena space or the end of the list.

Given a context free grammar, it is possible to define a set of predicates that encode the logic of the grammar.

-Parsing in context free grammar may be implemented by creating.

-One predicate for each non-terminal in the grammar.

-This predicates will take as an argument a list of items representing a possible instance of the non-terminal.

-Each predicate is programmed by using two clauses for each alternative form of the corresponding non-terminal.