74191

Logic programming languages and tools. Programming languages versus logic programming

Лекция

Информатика, кибернетика и программирование

Properties: we cn ssign properties to individul entities for exmple fred would hve the property of being crnivore properties look like C function cll the nme of the property then the entity tht hs tht property is given in brckets e. Reltionships fcts: we cn ssign reltionships between entities for exmple fred ets met or wilm ets vegetbles reltionships in Prolog gin look like C function cll we give the reltionship nme first then in brckets the two entities tht re relted e. etswilmmet etswilmvegetbles. For exmple rule...

Английский

2015-01-22

33.5 KB

0 чел.

Lecture 10. Logic programming languages and tools. Part 2.1

10.1 Programming languages versus logic programming.

In a logic programming language, the programmer does not identify the computations or functions necessary to derive an answer. The great advantage of a declarative language is that the programmer only needs to supply the information that is known (facts and rules), and ask questions - not worry about the ways the rules must be applied to answer those questions. From a programmer’s perspective, this is a much more high-level approach to problem solving than in imperative or functional languages.

Drawbacks of logic programming:

  •  The query process can be quite slow and inefficient
  •  The programmer must supply sufficient facts
  •  Rules to allow the engine to answer the queries
  •  The programmer must understand how to phrase the facts, rules, and queries

10.2 Prolog

Prolog (PROgramming LOGic) (1972) was the first widespread formal logic language. It is a non-procedural, goal oriented language. Computation takes place by trying to infer the response to queries through accessing a database of facts and rules. The user supplies the facts, rules, and queries (expressed in predicate calculus), while the computer carries out resolution to try and infer the replies.

By far the dominant logic programming language is Prolog, so that is the language we will examine in some detail. Prolog is based predominantly on the Horn clause,

A :- B, C, D, ...

This tells us A is true if B is true and C is true and ... etc. It does not tell us the circumstances under which a is false.

In fact, in Prolog all the queries are expressed like yes/no questions, and the answers come back either as

  •  a simple “No” (meaning no way could be found to make the query true), or
  •  “Yes”, plus all the ways in which the query could be made true.

10.2.1 Core components

The basic elements of a Prolog program are:

1) Entities: terms, constants, atoms.

2) Variables: as with more traditional programming languages, we can declare a variety of variables in Prolog.

3) Properties: we can assign properties to individual entities, for example fred would have the property of being a carnivore properties look like a C function call - the name of the property then the entity that has that property is given in brackets, e.g. carnivore (fred), or food (vegetables).

4) Relationships (facts): we can assign relationships between entities, for example fred eats meat, or wilma eats vegetables relationships in Prolog again look like a C++ function call, we give the relationship name first, then in brackets the two entities that are related, e.g. eats(wilma,meat), eats(wilma,vegetables).

5) rules: we can establish rules that describe how one relationship or property is true if some other properties or conditions are true. For example, a rule could state that if someone eats meat and they eat vegetables then they are an omnivore.

Rules in Prolog have three parts:

  •  The result: this is the relationship or property which results from the rule, and goes on the left hand side of our rule, e.g. omnivore(Individual).

Note that the entity here will usually be a variable.

  •  The “if” symbol: symbol “:-” separates the result from the clauses.
  •  The clauses: the set of relationships and properties which determine if the rule is to be applied, this goes on the right hand side of the rule.

There are several logic symbols which can be used in the right hand side:

  •  The comma represents logical AND
  •  The semi-colon represents logical OR
  •  The word NOT in some ways functions like logical NOT

10.2.2 Creating a Prolog program

Creating a program in Prolog starts with creating the set of properties, relationships, and rules. Typically we will enter these into a text file ending with the extension “.pl” (e.g. “test_prog.pl”). Then start Prolog and load our database from the file. Next, begin issuing queries based on the loaded information. From this point on, everything you type is treated as a query, not a new fact or rule. For example, eats(fred,vegetables). is now asking whether or not Fred eats vegetables, not stating it as a new fact.

Syntax note: all statements of properties, relationships, rules, and queries must end with a period - the Prolog interpreter will not regard any of the above as completed until you enter a period.

Example: Create a file, called flint.pl, containing the following facts and rules:

eats(fred,meat).

eats(wilma,meat).

eats(betty,vegetables).

eats(wilma,vegetables).

eats(barney,meat).

eats(barney,vegetables).

carnivore(Individual) :-

eats(Individual,meat).

omnivore(Individual) :-eats(Individual,meat),eats(Individual,vegetables).

food(Thing) :- eats(Individual,Thing).

Once that is created, we can load the database of facts and rules from the file, then begin issuing queries and getting answers.

In the example below assume > is the prompt:

>['flint.pl'].

flint.pl compiled

Yes

>food(meat).

Yes

>carnivore(fred).

Yes

>food(dirt).

No

>omnivore(Individual).

Individual = wilma

Yes

10.2.3 How queries are answered

Suppose we are given the query “is fred an omnivore?”

omnivore(fred).

In trying to solve this query, Prolog does the following:

 search for all the relationships which match the goal, i.e. everything in our database that begins with omnivore(...)

 if we encounter a fact in our database that explicitly states omnivore(fred). then we can quit and return Yes as soon as we encountered it.

 if we encounter a rule of the form omnivore(...variable...) :- ... then we can say fred is an omnivore if we can substitute fred for the variable (throughout the rule) and still satisfy all the clauses on the right side of the rule.

In the case of our example, the rule with this form is

omnivore(Individual) :-

eats(Individual,meat), eats(Individual,vegetables).

and after substituting we want to check

if eats(fred,meat) AND eats(fred,vegetables).

Thus we have two new goals to try to satisfy to check out this rule, and we begin searching the database for facts and rules beginning with eats(...), trying to substitute “fred” and “meat” into the rules to continue the query.

If we cannot prove eats(fred,meat) then that clause fails, and hence the rule fails as well, so we must continue on checking for other facts/rules defining omnivores. As soon as we satisfy one of the facts or rules that prove fred is an omnivore we can stop and return “Yes”. If we go through all our facts and rules and cannot prove fred is an omnivore then we return “no”.

Another example. Suppose our database is:

rainy(yesterday).

rainy(today).

cloudy(Day) :- rainy(Day).

Again, let us make the query:

cloudy(today).

In this case, the first applicable rule (i.e. that has cloudy as a head and one parameter) is:

cloudy(Day) :- rainy(Day).

Because Day is a variable, and we are looking for the specific value today, we can instantiate the variable Day with the value today, giving us the rule:

cloudy(today) :- rainy(today).

From this point the process continues by trying to satisfy subgoal rainy(today) and succeed because of the applicable fact in the database.

1 http://www.seas.gwu.edu/~bell/csci210/lectures/lp.pdf


 

А также другие работы, которые могут Вас заинтересовать

28872. Судебная реформа 1864 года 151 KB
  Основной задачей этой курсовой работы является изучение судебной реформы 1864 года которая считается самой буржуазной и последовательной реформой Х1Х века в России. В ходе реформы судопроизводства в России предполагались изменения в разных его областях: в организации судебной системы например введение суда присяжных в профессиональном статусе судей институт мировых судей пожизненное избрание в процедуре вынесения приговора €œдвухэтапного€ формирования приговора присяжными и судей и т. Исторические предпосылки судебной реформы...
28873. Судебная реформа 1864 года и ее основные итоги 87 KB
  Вместо множества судов существовавших для обслуживания различных сословий учреждались единые для всех сословий общегражданские суды. Основными звеньями общих судебных установлений были окружные суды судебные палаты и Правительствующий сенат. Окружные суды образовывались обычно на территории нескольких уездов с учетом численности населения и объема работы. Замахнувшись на множественность судов создавшихся для обслуживания дворян купцов ремесленников крестьян и других сословий власти не решились полностью...
28874. Основные тенденции мирового развития в XVIIIв. 23.5 KB
  XVIII век вошел в историю как век просвещенного абсолютизма. Политика абсолютизма в ряде европейских стран выражающаяся в уничтожении сверху и в преобразовании наиболее устаревших феодальных институтов. Однако главным в политике просвещенного абсолютизма стало провозглашение принципа одно право для всех что отразилось в создании равного для всех гражданского права. Проведение политики просвещенного абсолютизма в определенной мере явилось отражением идей Просветителей.
28875. «Смутное время» в России. Эволюция государственности в XVII в. 37.5 KB
  Смутное время в России. На какоето время государство оказалось ничьим и это привело к кризису послужившему началом так называемого Смутного Времени. Многие из богатых людей в это время отпускают на волю свою челядь чтобы не кормить ее и это увеличивает толпы бездомных и голодных. В это время в Польше против царя Бориса выступил молодой человек который назвал себя царевичем Дмитрием сыном Ивана Грозного и заявил о своем намерении идти на Москву добывать себе прародительский престол.
28876. Внешняя политика России XVI–XVII веков. 28 KB
  Внешняя политика России XVIXVII веков. позволили России проводить активную внешнюю политику. предопределило включение в состав России всего Среднего Поволжья с его многонациональным населением. В1556 году русскими войсками была взята Астрахань и к России присоединились нижневолжские земли.
28877. Пётр I Вели́кий 33.5 KB
  Одним из главных достижений Петра стало решение поставленной в XVI веке задачи: расширение территорий России в Прибалтийском регионе после победы в Великой Северной войне что позволило ему принять в 1721 году титул первого императора Российской империи. Военная реформа Петра I и реформы органов управления. Военная реформа была первоочередным преобразовательным делом Петра. Заслугой Петра является создание регулярной российской армии.
28878. Внешняя политика Петра I. Провозглашение России империей 31.5 KB
  Провозглашение России империей. Разрешение этих задач было необходимо для обеспечения внешней безопасности России на юге и на западе. Ее преобладание тяжело сказывалось на государствах близких к Балтийскому морю: на Дании Польше России. У России Ингрию и Карелию.
28879. Эпоха дворцовых переворотов и укрепление позиций дворянства 31.5 KB
  В отечественной истории являлось эпохой дворцовых переворотов напрямую связанных с реформами Петра I. Меньшиков Толстой и другие под прикрытием гвардии добилась провозглашения вдовы Петра Екатерины I 1725 1727 гг. В период царствования малолетнего Петра II 17271730 гг. На трон была провозглашена племянница Петра I вдовствующая герцогиня Курляндская Анна Ивановна 17301740 гг.
28880. Внутренняя политика эпохи «просвещенного абсолютизма» Екатерины II 29 KB
  Созыв Комиссии был обусловлен необходимостью кодификации законов т. В дебатах депутатов Уложенной комиссии находит выражение острая борьба трех основных направлений по проблемам модернизации общественного устройства России: консерваторов умеренных и реформаторов. Третья наиболее последовательная и радикальная группа не имея возможности выступать открыто сформировалась за пределами Уложенной комиссии. под предлогом начавшейся русскотурецкой войны Екатерина прервала заседания Комиссии чтобы больше их не возобновлять.