Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 165
Текст из файла (страница 165)
Следовательно, если правило вевЬег используется как подцель в операторе цели, состоящем из многих подцелей, может возникнуть проблема. Она состоит в том. что если подцель вевЬег достигается, а следующая подцель — нет, то бектрекинг попытается повторно удовлетворить подцель вевЬег, продолжая предыдущее сопоставление. Однако, поскольку аргумент подпели вевЬег, являющийся списком, имеет только один экземпляр элемента, с которого он начинается, подцель вевЬег может снова не достигаться, что в конце концов приводит к отказу всей цели.
несмотря на любые дополнительные попытки снова удовлетворить подцель вевЬег. Решить эту проблему. снижающую эффективность программы, можно, добавив в первый оператор опрелеления подцели вевЬег правую часть, единственным элементом которой является оператор отсечения, как показано ниже: вевЬег(Е1евепс, [Е1евепс ) ]) Бек)рекинг теперь не будет пытаться снова удовлетворить подцель вевбег, а приведет к отказу всей подцепи.
Оператор отсечения полезен, в частности, в программных стратегиях на языке Рго)оя, которые называются порождай и проверяй (яепега(е апг) (еы). В этих программах цель состоит из подцелей, порождающих потенциальные решения, которые затем проверяются подцелями "проверки". Отвергнутые решения требуют выполнения бектрекинга лля подцелей, порождающих новые потенциальные решения.
В качестве примера программы, следующей стратегии "порождай и проверяй", рассмотрим пример, привеленный в работе С!ос)(з(п апд МеП[зй (1984): 15.7. Недостатки языка Рго1оВ 639 с)1чгс(е (1(1, Н2, геяц1г): — гя гпседег (йеяи1Г), Ргос1цсс1 1я Кеяи1Г * (Ч2, Ргос)цсГ2 1я (Кеяо1Г + 1) * (Ч2 Ргог)цсг1 е< Б1, Ргос)цсг2 > (ч1, ! Эта программа выполняет целое деление с использованием сложения и умножения. Поскольку большинство систем языка Рто!оя обеспечивают деление в качестве оператора, эта программа в действительности является бесполезной и предназначена лишь для иллюстрации простой программы в рамках стратегии "порождай и проверяй".
Предикат Ея Епгецег достигается, как только его параметры могут быть конкретизированы некоторым неотрицательным целым числом. Если его аргумент не конкретизирован. то предикат 1я 1пте9ег присваивает ему значение О. Если аргумент конкретизирован некоторым целым числом, то предикат 1я гпге9ег присваивает ему следующее целое число в порядке возрастания. Таким образом, в операторе г(1ч1с(е предикат гя 1псе9ег Является поРождающей подцелью. Он порождает элементы последовательности О, 1, 2, .... каждый раз. когда он удовлетворяется.
Все другие операторы в определении оператора с(1чзт1е предназначены для проверки подцелей — они проверяют, является ли значение, порожденное предикатом 1я 1пгеаег, частным от деления двух первых параметров (ч1 и (ч2. Цель оператора отсечения в качестве последней подцепи проста — он предотвращает дальнейший поиск альтернативных решений, как только будет найдено данное решение. Несмотря на то что предикат 1я 1п.едет может порождать огромное количество потенциальных решений, только одно нз них является настоящим, так что оператор отсечения предотвращает бесполезные попытки найти второе решение.
Использование оператора отсечения сравиивалось с использованием оператора безусловного перехода його в императивных языках (Чап Ешбеп, 1980). Несмотря на то что иногда он действительно нужен, его можно критиковать. Действительно, он зачастую используется для того, чтобы внести в логические программы поток управления, порождаемый стилем императивного программирования. Возможность вмешиваться в поток управления в программах на языке Рго)оа является недостатком, поскольку это явно наносит вред одному из важнейших преимуществ логического программирования, состоящему в том, что программы не определяют способ, которым должно быть найдено решение.
Они просто указывают, как должно выглядеть решение. Это позволяет более легко создавать и читать программы. Они не загромождены деталями, описывающими, как именно следует искать решения, и в частности, они не имеют точного порядка, в котором должны выполняться вычисления, для того чтобы получить решение. Таким образом, в то время как логическое программирование не требует указания направлений потока управления в программе.
язык Рго!оз часто использует их. в основном для повышения эффективности выполнения программ. 1$.7.2. Предлоложение о закрытом мире Природа резолюции в языке Рго1ой иногда приводит к ошибочным результатам. Истиной в языке Рго(ол считается только то, что может быть доказано с использованием его базы данных. Он не имеет никаких других сведений о мире, кроме знаний, хранящихся в его базе данных. Любой запрос считается ложным, если в базе данных недостаточно информации для того, чтобы доказать его абсолютно точно. Система языка Рго1ок может доказать, что данная цель является истинной, но она не может доказать, что данная цель Глава 15. Языки логического программирования является ложной. Она просто предполагает, что, поскольку она не может доказать истинность данной цели, эта цель должна быть ложной. По существу, система языка Рго)ок является системой "истина/отказ", а не "истина/ложь".
В действительности, замкнутый мнр предположений не должен быть совсем чуждым лля вас — юридическая система работает именно таким образом. Подозреваемый невиновен, пока не доказана его вина. Доказывать его невиновность не обязательно. Если суд не может доказать виновность некоего лица, он нлн она считается невиновным. Проблема замкнутого мира предположений связана с проблемой логического отрицания, обсуждаемой в следующем разделе. 15.У.З. Проблема логического отрицания Другая проблема языка Рго)ок заключается в трудностях, связанных с логическим отрицанием. Рассмотрим следующую базу данных, состоящую нз двух фактов н одного отношения: рагепг(Ь111, За)се). рагепг(Ь111, впе11еу). в1Ь11пц(Х, Х) : — (рагепс (М, Х), рагепс (М, Х) ) Теперь предположим, что мы ввели запрос в1ЫЕп~/ (Х, Х) .
Система языка Рго)об ответит Х = За)се Х = За)се Таким образом, система языка Рго)оя "думает", что Джек (За)ге) является братом (я1Ы1пд) самому себе. Это происходит потому, что система сначала конкретизирует переменную М значением Ь111, а переменную Х вЂ” значением 3 а)се лля тою, чтобы сделать первую подцель рагепс (м, х) истинной. Затем она снова начинает поиск с начала базы данных лля того, чтобы сопоставить вторую подцель рагепг (м, х), н обнаруживает совпадение, когда переменная М конкретнзнрована значением Ь111, а переменная Х— значением 3 а)се.
Поскольку две подцелн удовлетворяются независимо друг от друга. причем оба совпадения находятся в начале базы данных, возникает ответ, приведенный выше. Для того чтобы избежать этого, следует указать, что переменная Х находится в отношении вЕЫ1по с переменной Х, только если обе онн находятся в отношении рагепгв с одной н той же переменной и не совпадают друг с другом. К сожалению, непосредственно указать, что онн не равны между собой, в языке Рго!ок невозможно, что мы обсудим ниже. Наиболее точный метод может потребовать добавления в базу данных фактов для кажной пары атомов о том, что онн не совпаиют между собой.
Это приведет к тому, что база данных станет очень большой, поскольку негативной информации намного больше. чем позитивной. Например, у большинства людей количество дней, не являющихся нх днями рождения, на 364 больше, чем количество нх дней рождения. Простое альтернативное решение этой проблемы — указать в цели, что переменная Х не должна совпадать с переменной Х, как это сделано в следующем примере: в1Ыюд(Х, Х): — рагепг (М, Х), рагепс (М, Х), пот (х Х) . В других ситуациях решение не будет столь простым.
15.7. Недостатки языка Рго1оа Оператор поп в языке Рго)од уловлетворяется, если резолюция не может удовлетворить подцель х у. Следовательно, если оператор пос достигается, это не обязательно означает, что переменная Х не равна переменной т. Скорее это означает, что резолюция не может вывести из базы данных, что переменная Х равна переменной У. Таким образом, оператор поп в языке Рго)оя не эквивалентен логическому оператору отрицания, в котором отрицание означает, что истинность оператора можно доказать. Эта неэквивалентность может привести к проблеме, если мы имеем дело с целью в слелуюшем виде: поп(поп(вове доа1)). Если бы оператор поп в языке Рго1оя был истинным логическим оператором отрицания, она могла бы быть эквивалентной цели яоте ооа1. В некоторых случаях, однако, они не совпадают.
Снова рассмотрим правила вегпЬег: ветЬег(Е1евепп, [Е1етепс 1 ]). ветЬег(Е1евепс, [ 1 Е1яс]) : — ветЬег(Е1евепс, Езяс). Чтобы обнаружить один из элементов в заданном списке, можно использовать цель тетЬег(Х, [вагу, Егес(, ЬагЬ]). Эта цель привела бы к конкретизации переменной Х значением тету, которое затем было бы выведено на печать. Предположим, что мы используем цель поп(поп(тевЬег(Х, [вагу, ангес), ЬагЬ]))). Тогда имеет место следующая последовательность событий: вначале внутренняя цель достигается, конкретизируя переменную Х значением вегу. Затем система языка Рго!оя пытается удовлетворить следуюшую цель: поп(тетЬег(Х, [тагу, Йгес), ЬагЬ])). Это могло бы привести к отказу, поскольку цель тетЬег постигается. Если цель не достигается, переменная Х теряет конкретное значение, поскольку система языка Рго)оя всегда освобождает все переменные во всех недостижимых целях.
Далее, система языка Рго!ой пытается удовлетворить внешнюю цель пот, которая должна достигаться, поскольку не были достигнуты ее аргументы. В конце концов, мог бы быть напечатан результат. которым является переменная Х. Однако переменная Х в этот момент может не иметь конкретного значения, что и булет отмечено системой. В общем случае неконкретизированные переменные печатаются в виде строки цифр, которым предшествует знак подчеркивания. Таким образом, тот факт, что оператор языка Рго)оя не эквивалентен логическому оператору отрицания, может, по меньшей мере, вводить в заблуждение. Основной причиной, почему логический оператор отрицания не может быть неотьемлемой частью языка Рго!ой, является форма хорновского дизъюнкта: А:- В; л В- гз ...
гь В„ Если все высказывания В являются истинными, можно прийти к выводу, что высказывание А является истинным. Однако независимо от истинности или ложности любого или всех высказываний В„невозможно доказать, что высказывание А является ложным. Из позитивной логики можно получить только позитивную логику. Таким образом, использование хорновских дизъюнктов не допускает никаких негативных заключений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
