Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 158

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 158)

являюшихся ее параметрами н прелставляюшими собой множества. Напишите на языке 5спеше функцию с двумя параметрами. атомом и списком. возврашаюшую список, из которого удален заданный атоль независимо от глубины его нахождения в списке. Возврашаемый список не лолжен иметь на месте удачен- ного атома никакого элемента. Найдите опрелеления функций ЕЧА(. и АРР).У языка Бсйегле и объясните, как они действуют. Обратитесь к любой книге по программированию на языке (.(ЯР и определите, какие аргументы обосновывают включение свойств функции РНОО в язык (.(ЯР.

Функциональный язык мог бы использовать структуру данных. отличную от списка, например, последовательность символов. Какие языковые конструкции должен был бы иметь такой язык вместо элементарных функций СА](, СО]( и СОНЯ языка Яс)зеве? 9. Какие действия выполняет слелующая функция, написанная на языке Ясйегле? (с)ейапе (у я 11я! (сопс) ((пц11? 11я) ' () ) ((ес(иа1? я (саг 11я)) 11я) (е1яе (у я (сс(г 11я] ) ) 1й. Какие действия выполняет следующая функция, написанная на языке Яс(гегле? (с)ейапе (х 11я) (сопс) ((пи11? 11я) О ) ((пос (11яс? (саг 11я])] (сопс( ( (ес(? (саг 11я) п11) (х (сс]г 11я) ) ) (е1яе (+ 1 (х (сс(г 11я) ) ) ) ) (е1яе (+ (х саг 11я) ) (х (сс(г 11я) ) ) ) )) 614 Глава 14. Функциональные языки программирования ()бберт ((овагвсаи (ЙйеФЬеа(зй) Роберт Ковальски из Эдинбургского университета (Мпыегзйу о( Еб)поогрн) — исследователь в области искусственного интеллекта.

Ковальски вместе с Аленом Колмерье (А)еп Соапегаоег) и Филиппом Русселем (Рбййрре (топазе)) из Марсельского университета (Оппгвгзйу о( А(хМагзей)е) разработали первый язык логического программирования — Рго)од. Феоды ель этой главы — ввести понятия логического программирования и языков логи- Ц ческого программирования, а также кратко описать некое подмножество языка Рго1оя. Вначале рассмотрим исчисление предикатов, являюшееся основой языков логического программирования.

Затем обсудим, как его можно использовать в системах автоматического доказательства теорем. Потом сделаем общий обзор логического программирования. Далее в обширном разделе вводятся основы языка программирования Рго!оя, включая арифметику, обработку списков и использование отслеживающих инструментов, которые можно применять при отладке программ, а также лля иллюстрации работы системы языка Рго1оя.

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

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

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

15.2. Краткое введение в исчисление лредикатов Прежде чем мы смо;кем обсудить логическое программирование, кратко исследуем се основу, т.е, формальную логику. Это не первая наша встреча с формальной логикой; она интенсивно использовалась в аксиоьгатической семантике. описанной в главе 3. Высказывание (ргороз)г(оп) — логическое утверждение. которое может быть истинным или ложным.

Оно состоит из объектов н отношений между ними. Формальная логика была разработана зля того. чтобы создать метод описания таких высказываний с целью проверки их истинности. Символьную логику (зушЬо11с 1оя(с) можно использовать для решения трех основных задач формальной логики: выражения высказываний, выражения отношений между высказываниями и описания способов вывода новых высказываний из других высказываний, считаюшихся истинными. 616 Глава 15. Языки логического программирования Между формальной логикой и математикой существует тесная связь.

Действительно, многое в математике можно описать в терминах логики. Основные аксиомы теории чисел и теории множеств представляют собой начальное множество высказываниЯ, считающихся истинными. Теоремы являются лополнительными высказываниями, которые могут быть выведены из начального множества высказываний.

Конкретный вид символьной логики. использующийся в логическом программировании, называется исчислением преднкатов (ргесйсаге са!сц!цз). Его мы кратко рассмотрим в следующих подразделах. Наша цель — заложить основу для обсуждения логического программирования и языка логического программирования Рго!оя. 15.2.1. Высказывания Обьекты в высказываниях логического программирования прелставляются простыми термами, являющимися либо константами. либо переменными. Константа — это символ, представляюгций некий объект. Переменная — это символ, который может представлять разные объекты в разное время.

хотя в некотором смысле она намного ближе к математическому пониманию переменной, чем к переменным в императивных языках программирования. Простейшие высказывания. называемые атомарными высказываниями (а)ош!с ргорояйоп), состоят из составных тернов. Составной терм (сошроцпб )епп) — это элемент математического отношения, формально записанного в виде математической функции. Напомним. что в главе !4 было дано определение математической функции как отображения, которое можно представить либо как выражение, либо как таблицу, либо как список кортежей. Таким образом.

составные термы — это элементы определения функции в виде таблицы, Составной терм состоит из двух частей: функтора (Йпс(ог), представляющего собой функциональный символ. называющий отношение. и упорядоченного списка параметров. Составной терм с одним параметром представляет собой кортеж из одного элемента, с двумя параметрами — кортеж из двух элементов и так далее. Например, мы можем иметь два выражения: человек(Джек) любит(Боб, стейк) Эти выражения утверждают. что (Джек ) — это кортеж из одного элемента, принадлежащий отношению с именем "человек". и что (Боб, стейк) — зто кортеж из двух элементов, принадлежащих отношению с именем "любит".

Добавим к двум высказываниям, указанным выше, следующее высказывание человек(Фред) Тогда отношение "человек" может иметь два разных элемента (Джек) и (Фред1. Все простые термы в этом высказывании — человек, любит, Боб и стейк— константы. Заметим. что эти высказывания не имеют внутренней семантики.

Они могут означать все, что мы захотим. Например, второй пример из приведенных выше, может означать, что некто по имени Боб любит стейк, или что стейк любит Боба, или что Боб в некотором смысле похож на стейк. Высказывания можно формулировать двумя способами; в первом из них высказывание считается истинным. а во втором истинность высказывания требуется установить. 617 15.2. Краткое вввдвнне в исчисление преднкатов Иными словами, высказывания можно формулировать либо как факты, либо как запросы. Высказывания в примерах, привеленных выше, могут быть и теми, и другими.

Составные высказывания имеют несколько атомарных высказываний, связанных между собой логическим коннектором, или оператором, так же, как составные логические выражения конструируются в императивных языках. Названия, символы и смысл коннекторов в логическом исчислении предикатов представлены в следующей таблице Название Сичвол Причер Сжыст отрицание конъюнкция дизьюнкция тождественность импликация а~зЬэс лаз Ьэс( Оператор имеет наивысший приоритет.

Операторы гт, н и - =обладают более высоким приоритетом, чем операторы э и с. Таким образом, второй пример из приведенных выше эквивалентен выражению (а гт ( Ь) ) э с( В высказывании могут содержаться и переменные, но при зтом к ним всегда приписываются специальные символы, называемые кванторами. В исчислении предикатов есть два квантора, показанных ниже, где Х вЂ” переменная, а Р— высказывание; Название Причер Смыст квантор всеобщности ЧХР Для всех переменных Х высказывание Р истинно квантор существования лХР Существует значение переменной Х, при котором высказывание Р истинно Точка между Х и Р просто отлеляет переменную от высказывания.

Характеристики

Список файлов книги