ДЕКЛАРАТИВНОЕ ПРОГРАММИРОВАНИЕ.docx

ДЕКЛАРАТИВНОЕ ПРОГРАММИРОВАНИЕ*

Выше мы утверждали, что формальная логика позволяет создать общий алгоритм решения задач, на основе которого можно построить систему декларативного программирования. В данном разделе мы исследуем это утверждение, создав сна- чала некоторый упрощенный алгоритм, а затем кратко обсудив возможности основанного на нем языка декларативного про- граммирования.

Логический вывод. Предположим, мы знаем, что лягушонок Кермит либо играет в спектакле, либо болен, и нам сказа- ли, что сейчас лягушонок Кермит не играет в спектакле. Тогда мы можем сделать вывод, что лягушонок Кермит, должно быть, болен. Это – пример дедуктивного рассуждения, которое называется резолюцией.

Чтобы лучше понять этот принцип, примем сначала соглашение представлять простые высказывания отдельными бук- вами, а отрицание высказывания – символом Ø. Например, мы можем представить высказывание "Кермит – принц" буквой А, а высказывание "Мисс Пигги – актриса" – буквой В. Тогда выражение

A  OR В

означает "Кермит – принц или мисс Пигги – актриса", а выражение

B  AND ØA

Означает: "Мисс Пигги – актриса, а Кермит – не принц". Для обозначения отношения "следует" мы будем использовать стрелку. Например, выражение

A ® B

означает: "Если Кермит – принц, то мисс Пигги – актриса".

В общем виде принцип резолюции утверждает, что из двух высказываний

Р OR Q и R OR ØQ

мы можем вывести высказывание

R OR Q.

В этом случае мы говорим, что два исходных высказывания сводятся к третьему, которое называется резольвентой. Важно подчеркнуть, что резольвента – это логическое следствие исходных высказываний. Если исходные высказывания ис- тинны, то резольвента также должна быть истинной. (Если Q – истинно, то R должно быть истинно, но если Q – ложно, то Р должно быть истинным. Следовательно, независимо от того, является Q истинным или ложным, либо Р, либо R должно быть истинным.)

Графически мы будем представлять резолюцию двух высказываний так, как показано на рис. 5.19, где мы написали ис- ходные высказывания и изобразили линии, соединяющие их со своей резольвентой. Заметим, что резолюцию можно приме- нять только к парам высказываний, которые выражаются в форме предложения, т.е. к высказываниям, элементарные компо- ненты которых можно соединять булевой операцией OR (ИЛИ). Таким образом, высказывание

P OR Q

выражено в форме предложения, в то время как для высказывания

P ® Q

это не так. Эта потенциальная проблема не очень серьезна. В математической логике существует теорема, утверждающая, что любое высказывание, записанное средствами логики предикатов первого порядка (системы для представления высказы- ваний, имеющей очень большие выразительные возможности), можно сформулировать в форме предложения. Мы не будем обсуждать здесь эту важную теорему, но для дальнейших ссылок заметим, что высказывание

P® Q

эквивалентно высказыванию в форме предложения

Q OR ØP.

Совокупность высказываний является противоречивой, если все они не могут быть истинными одновременно. Другими словами, такая совокупность высказываний состоит из противоречащих друг другу высказываний. Простой пример такой совокупности – объеди- нение высказывания Р и его отрицания ØP. Специалисты-логики доказали, что повторное применение резолюции – это систематический метод проверки непротиворечивости мно-

Рис. 5.19. Резолюция высказываний (P OR Q) и (R OR ØQ) с получением высказывания (Р OR R)

является противоречивой.

жества предложений. Если повторный метод резолюции приводит к пустому предложению (результату резолюции предложения Р с предложением ØP), то исходная совокупность высказываний является противоречивой. Например, на рис. 5.20 показано, что совокуп- ность высказываний

P OR Q   R OR ØQ     ØR    ØQ

Предположим, нам необходимо проверить, что из некоторой совокупности высказываний действительно следует выска- зывание Р. Высказывание Р эквивалентно отрицанию высказывания -P. Следовательно, чтобы показать, что из исходной со- вокупности высказываний следует высказывание Р, нам нужно лишь применять процедуру резолюции к исходным высказы- ваниям и высказыванию ØР до тех пор, пока мы не получим пустое предложение. Получив пустое предложение, мы можем прийти к выводу, что высказывание ØР противоречит исходным высказываниям, а значит, из исходных высказываний сле- дует высказывание Р.

Остается решить всего одну проблему, и мы будем готовы к применению процедуры резолюции в реальной программ-

ной среде. Предположим, что имеются два высказывания:

(Маша находится в X) ® (Машин ягненок находится в X),

где X означает произвольное местоположение и еще одно высказывание

Рис. 5.20. Резолюция высказываний (Р OR Q), (R OR ØQ), ØR и ØQ

В форме предложения эти высказывания принимают следующий вид:

(Машин ягненок находится в X) OR Ø(Маша находится в X)

и

(Маша находится дома).

На первый взгляд может показаться, что эти предложения не имеют компонентов, которые можно подвергнуть резолюции.

Однако компоненты (Маша находится дома) и Ø (Маша находится в X) почти противоречат друг другу. Задача за- ключается в том, чтобы установить истинность высказывания (Маша находится в X), которое является высказыванием о местонахождении вообще и о доме в частности.

Таким образом, частный случай первого высказывания имеет вид

(Машин ягненок находится дома) OR Ø(Маша находится дома)

который может быть сведен путем резолюции с высказыванием

(Маша находится дома)

к высказыванию вида

(Машин ягненок находится дома)

Процесс присваивания значений переменным (например, присвоение значения "дом" переменной X), который делает возможным выполнение резолюции, называется унификацией. Это процесс, который позволяет применять общие высказы- вания к частным приложениям в дедуктивной системе.

Язык Prolog. Prolog (PROgramming in LOGic – программирование в логике) – это декларативный язык программирова- ния, базовый алгоритм решения задач которого основан на методе повторной резолюции. Программа на языке Prolog состоит из совокупности исходных высказываний, с помощью которых базовый алгоритм выполняет свои дедуктивные рассуждения. Компоненты, из которых состоят эти высказывания, называются предикатами. Предикат состоит из идентификатора преди- ката, за которым в скобках следуют аргументы предиката. Отдельный предикат представляет собой некоторый факт в отно- шении его аргументов, а идентификатор предиката обычно выбирается так, чтобы отразить его семантику. Таким образом, если мы хотим выразить тот факт, что Билл – отец Мери, мы можем использовать следующую предикатную форму:

parent(bill,   mary).

Обратите внимание, что аргументы в этом предикате начинаются со строчных букв, даже если речь идет об именах соб- ственных. Это происходит потому, что язык Prolog различает константы и переменные и требует, чтобы константы начина- лись со строчных букв, а переменные – с прописных.

Операторы в языке Prolog являются либо фактами, либо правилами. Каждый из операторов заканчивается точкой. Факт состоит из отдельного предиката. Например, тот факт, что черепаха (turtle) двигается быстрее улитки (snail), выражается оператором языка Prolog следующего вида:

faster(turtle,snail).

А тот факт, что кролик (rabbit) бегает быстрее черепахи, выражается оператором

faster(rabbit,turtle).

Правило в языке Prolog – это оператор импликации (следования). Вместо записи оператора в виде X ® Y программист на языке Prolog пишет "Y, если X", используя вместо слова "если" символы : –. Таким образом, правило "из того, что X бы- стрее (faster) Y, a Y быстрее Z, следует, что X быстрее Z" может быть выражено специалистом-логиком в следующем виде:

(faster(X,Y) AND faster (Y,Z)) ® faster(X,Z)

На языке Prolog это же правило выражается следующим образом:

faster(X,Z) :- faster(X,Y), faster(Y,Z).

Запятая, разделяющая термы faster(X,Y) и faster(Y,Z), представляет оператор конъюнкции AND (И). Такие правила легко могут быть преобразованы программным обеспечением языка Prolog в форму предложения.

Учтите, что система языка Prolog ничего не знает о значении предикатов в программе, она просто манипулирует выска- зываниями, формально применяя правило резолюции. Таким образом, описание всех относящихся к делу свойств предика- тов в терминах фактов и правил входит в обязанности программиста. В этом смысле факты в языке Prolog обычно использу- ются для конкретизации примеров предиката, а правила – для описания общих принципов. Этому подходу соответствуют предыдущие операторы, относящиеся к предикату faster. Два факта описывают конкретные примеры свойства "двигаться

быстрее", а правило – некое общее свойство. Заметим, что факт "кролик двигается быстрее улитки", хотя и не высказан явно, является следствием двух фактов, объединенных в соответствии с существующим правилом.

Большинство реализаций языка Prolog разработано для интерактивного применения. В этом смысле задача программи- ста – разработать совокупность фактов и правил, которые образуют множество исходных высказываний, используемых за- тем в дедуктивной системе. Установив такую совокупность высказываний, можно ввести с клавиатуры предложение (назы- ваемое в терминологии языка Prolog целью), которое система должна проверить. Как только перед дедуктивной системой языка Prolog будет поставлена некоторая цель, она применит операцию резолюции, пытаясь найти подтверждение того, что указанная цель следует из исходных высказываний. С помощью нашего набора высказываний, описывающих отношение faster, приведенные ниже предложения

faster(turtle, snail). faster(rabbit, turtle). faster(rabbit, snail).

будут подтверждены, поскольку каждое из них является логическим следствием исходных высказываний. Первые два факта идентичны фактам, приведенным в исходных высказываниях, а третий является результатом дедукции.

Более интересные результаты получаются, если в задачах используются не константы, а переменные. В этих случаях программа на языке Prolog пытается вывести цель из исходных высказываний, отслеживая требуемые унификации. Затем, если цель достигнута, программа указывает эти унификации. Например, рассмотрим цель

faster(W, snail).

В результате программа сообщает

faster(turtle, snail).

Действительно, это – следствие исходных высказываний, которое согласуется с поставленной целью с помощью уни- фикации. Далее, если мы попросим программу сообщить нам больше фактов, она найдет и выведет на печать следующее следствие:

faster(rabbit, snail).

И наоборот, мы можем попросить программу найти примеры животных, которые более медлительны, чем кролик, поставив программе цель

faster(rabbit, W). Поэтому, если мы поставим задачу faster{V, W),

то программа в конце концов найдет все отношения faster, которые могут быть выведены из исходных высказываний. Таким образом, единственная программа на языке Prolog может быть использована для подтверждения, что одно конкретное животное быстрее другого; для поиска всех тех животных, которые быстрее указанного животного; для поиска животных, которые медленнее указанного животного; а также для поиска всех отношений "быстрее/медленнее" между животными. По- добная гибкость просто захватывает воображение специалистов в области компьютерных наук.

Вопросы для самопроверки

1.  Какие из высказываний R, S, T, U и V являются логическим следствием совокупности высказываний (ØR OR T OR S), (ØS OR V), (ØV OR R), (U OR S), (T OR ØU) и (S OR V)?

2.  Является ли следующая совокупность высказываний непротиворечивой? Обоснуйте свой ответ. Р OR Q OR R; ØR OR Q; R OR ØP; ØQ.

3.  Предположим, что программа на языке Prolog состоит из операторов, выражающих отношение "экономнее" (thriftier):

thriftier(carol, john). thriftier(bill, sue). thriftier(sue, carol).

thriftier(X,Z) :- thriftier(x, Y), thriftier(Y,Z).

Перечислите результаты, которые можно получить для каждой из следующих целей: а) thriftier (sue, V);

б) thriftier(U, carol);

в) thriftier(U, V).

Упражнения

(Упражнения, отмеченные звездочкой, относятся к разделам для дополнительного чтения.)

1.  Что означает высказывание "язык программирования является машинно-независимым"?

2.  Переведите следующую программу с псевдокода на машинный язык, описанный в приложении В.

x ← 0;

while (х ≠ З) do

(x ← x+1)

3.  Переведите приведенный ниже оператор на машинный язык, описанный в приложении В, предполагая, что перемен- ные Length, Width и Halfway представлены как числа с плавающей точкой:

Halfway ← Length + Width

4.   Переведите следующий оператор языка высокого уровня на машинный язык, описанный в приложении В, предпола- гая, что числа W, X, Y и Z представлены в двоичном коде и занимают в основной памяти один байт:

if(X equals 0)

then Z ← Y + W

else Z ← Y + X

5.   Для чего при трансляции операторов необходимо указывать тип данных, связанный с переменными в задаче 4? По- чему многие языки высокого уровня требуют от программистов указывать тип каждой переменной в начале программы?

6.  Назовите и опишите четыре существующие парадигмы программирования.

7.  Предположим, что функция f получает два числа в качестве параметров и возвращает меньшее из них в качестве ре- зультата. Если переменные w, х, у и z представляют собой числа, то какой результат будет возвращен этой функцией при вычислении выражения f(f(w,х),f(y,z))?

8.   Предположим, что f – это функция, возвращающая в качестве результата строку, в которой все символы из входной строки переставлены в обратном порядке, а g – это функция, осуществляющая конкатенацию двух входных строк. Если х – строка "abcd", что вернет функция g(f(х),х)?

9.   Предположим, что вы собираетесь написать объектно-ориентированную программу для ведения своих финансовых записей. Какие данные нужно хранить в объекте, представляющем ваш текущий счет в банке? На какие сообщения должен реагировать этот объект? Какие еще объекты следует использовать в программе?

10.  Опишите отличия, существующие между машинным языком и языком ассемблера.

11.  Разработайте язык ассемблера для машины, описанной в приложении В.

12.   Некий Джон Программер утверждает, что возможность объявления констант в программе является излишней, по- скольку вместо них можно использовать переменные. Например, в разделе 5.2 можно описать переменную AirportAlt, а потом присвоить ей нужное значение в начале программы. Почему это решение хуже, чем вариант с использованием кон- станты?

13.  Опишите отличия, существующие между операторами объявления и выполняемыми операторами.

14.  Объясните разницу между литералом, константой и переменной.

15.  Что такое приоритет оператора?

16.  Что такое структурное программирование?

17.  Чем отличается смысл символа равенства в операторе

if(X = 5) then (...)

от смысла этого же символа в следующем операторе присваивания?

X = Z + Y

18.  Начертите блок-схему структуры, выраженной следующими операторами языков C++ и Java:

for(x = 0; х < 8; ++х)

{…}

19.  Начертите блок-схему структуры, выраженной следующими операторами языков С, C++ и Java:

switch(suit)

{  case "clubs": bid(l): break;

case "diamonds": bid(2): break; case "hearts": bid(3): break; case "spades": bid(4): break;

}

20.  Если вы знакомы с нотной записью, проанализируйте принятый принцип записи нот с точки зрения языка програм- мирования. Что здесь является управляющими структурами? Какой предусмотрен синтаксис для вставки комментариев? Ка- кие музыкальные обозначения похожи на операторы for, представленные на рис. 5.8?

21.  Перепишите следующий фрагмент программы, используя один оператор case вместо серии вложенных операторов

if-then-else. if (W = 5)

then (Z ← 7)

else (if (W = 6)

then (Y ← 7)

else (if (W = 7)

then (X ← 7) ) )

22.  Выразите приведенную ниже запутанную последовательность операторов с помощью единственного оператора if- then-else.

if X > 5 then goto 80 X = X + 1

goto 90

80 X = X + 2

90 ...

23.  Опишите отличия между транслятором и интерпретатором.

24.  Предположим, что переменная X в программе описана как переменная типа integer. Какая ошибка будет обнару- жена транслятором при выполнении следующего оператора?

X ← 2.5

25.  Что означает выражение "язык программирования со строгой типизацией"?

26.  Почему большой массив не всегда можно передать в вызываемую процедуру по значению?

27.  Предположим, что процедура modify определена следующим образом:

procedure modify(Y) Y ← 7;

напечатать значение переменной Y;

Если параметры передаются по значению, что будет напечатано при выполнении следующего фрагмента программы?

Что будет напечатано, если параметры передаются по ссылке?

X ← 5;

apply modify to X;

напечатать значение переменной X;

28.  Предположим, что процедура modify определена следующим образом:

procedure modify(Y) Y ← 9;

напечатать значение переменной X;

напечатать значение переменной Y;

Допустим также, что X – это глобальная переменная. Если параметры передаются по значению, что будет напечатано при выполнении следующего фрагмента программы? Что будет напечатано, если параметры передаются по ссылке?

X ← 5;

apply modify to X;

напечатать значение переменной X;

29.  Иногда фактический параметр передается в процедуру путем создания его копии, предназначенной для использова- ния в процедуре (как если бы параметр передавался по значению), но после выполнения процедуры значение копии при- сваивается фактическому параметру перед тем, как будет продолжено выполнение вызывающей процедуры. В таких случаях говорят, что параметр передается по значению-результату. Что будет напечатано фрагментом программы из упражнения 28, если параметры передаются по значению-результату?

30.  Какая неоднозначность кроется в следующем операторе?

X ← 3 + 2 * 5

31.   Предположим, что небольшая компания имеет пять сотрудников и планирует увеличить их число до шести. Ниже приведены фрагменты из двух эквивалентных программ (используемых компанией), которые нужно изменить, чтобы ото- бразить изменение количества сотрудников. Обе программы написаны на языке, напоминающем Pascal. Укажите, какие из- менения следует произвести в каждой программе. Какие осложнения возникают в первой программе и не возникают при использовании констант во второй программе?

Программа 1

.

.

.

DailySalary := TotalSal / 5; AvgSalary := TotalSal / 5; DailySales := TotalSales / 5; AvgSales := TotalSales / 5;

.

.

.

Программа 2

.

.

.

сonst

NumEmpl = 5;

DayWk= 5;

.

.

.

DailySalary: = TotalSal / DayWk; AvgSalary := TotalSal / NumEpml; DailySales := TotalSales / DayWk; AvgSales := TotalSales / NumEmpl;

.

.

.

32.  Нарисуйте синтаксическую диаграмму, представляющую структуру оператора while из псевдокода, описанного в главе 4.

33.  Разработайте совокупность синтаксических диаграмм для описания синтаксиса телефонных номеров, написанных в формате (044) 555-1234.

34.  Разработайте совокупность синтаксических диаграмм для описания простого предложения на английском языке.

35.  Напишите предложение, описывающее структуру строки, в соответствии с приведенной ниже синтаксической диа- граммой. Затем нарисуйте дерево синтаксического анализа строки ххyхх.

36.   Добавьте синтаксические диаграммы к диаграммам из вопроса 4 в разделе 5.4, чтобы получить совокупность диа- грамм, определяющих структуру Танец, которая может быть структурой Ча-ча-ча или Вальс, где Вальс состоит из од- ной или более копий типа

вперед по_диагонали каданс

или

назад по_диагонали каданс.

37.  Нарисуйте дерево синтаксического анализа приведенного ниже выражения, используя синтаксические диаграммы,

представленные на рис. 5.14.

х * у + у / х

38.  Какую оптимизацию кода может выполнить генератор кода при создании машинного кода для следующего операто-

ра?

if (X = 5)    then (Z ← X + 2)    else (Z ← X + 4)

39.  Упростите следующий фрагмент программы:

Y ← 5;if (Y = 7)    then (Z ← 8)    else (Z ← 9)

40.  Упростите следующий фрагмент программы:

while(X ≠ to 5) do    (X ← 5)

*41. Нарисуйте диаграмму (подобную диаграмме, показанной на рис. 5.20), представляющую последовательность опе-

раций резолюции, необходимых для того, чтобы показать, что совокупность высказываний (Q OR ØR), (T OR R), ØP, (P OR ØT) и (R OR ØP) противоречива.

42*. Является ли совокупность высказываний ØR, (T OR R), (P OR ØQ), (Q OR ØT) и (R OR ØP) противоречи- вой? Обоснуйте свой ответ.

43*. К каким выводам может прийти программа на языке Prolog, если поставить ей цель

bigger(X, Lassie).

Исходными высказываниями являются следующие:

bigger(rex, lessie).bigger(fido, rex).bigger(spot, rex).bigger(X,Z) :- bigger(X,Y), bigger(Y,Z).

44*. К каким выводам придет программа на языке Prolog, если поставить ей цель

eq(X, У.) .

Исходными высказываниями являются следующие:

qrteq(a b).qrteq(b, с).qrteq(c, a).qrteq(U, W :- qrteq(U, V), qrteq(V, W).eq(X, У) :- qrteq(X, Y), qrteq(Y, X).

45*. Какие проблемы могут возникнуть при выполнении машиной следующего фрагмента программы (описанной в разделе 1.7), в которой числа хранятся в 8-битовом формате с плавающей точкой?

X ← 0.01;while(X ≠ 1.00) do (вывести значение переменной X; X ← X + 0.01)

Скачано с www.znanio.ru