Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 102
Текст из файла (страница 102)
Структурная теорема: а — преобразования; б — модифицированная программа 8.4. Последовательность вычисления неарифметических выражений В предыдущем разделе обсуждалась последовательность выполнения действий при вычислении арифметических выражений. Однако в языках присутствуют и другие форматы выражений. В такие языки, как Рго!оя и МЕ, разработанные для обработки символьных данных, вюгючены другие формы вычисления выражений. 368 Глава 8. Управление последовательностью действий 8.4.1.
Обзор языка Рго!од В отличие от других языков, описанных в этой книге, Рго!о8 не является универсальным языком программирования, но зато он ориентирован на решение задач с использованием исчисления предикатов. Целью разработки языка Рго!о8 было предоставить возможность задания спецификаций решения и позволить компьютеру вывести из них последовательность выполнения для этого решения, а не задание алгоритма решения задачи, как в большинстве изученных нами языков.
Например, если информация об авиарейсах представлена в следукнцей форме; Ы тдш(непер рейса, пункт отправления, пункт назначения, вреия отправления. время прибытия> тогда все рейсы из Лос-Анджелеса в Балтимор можно задать либо в виде прямых рейсов через оператор Г)яды(номер рейса, Лос-Андмелес. Балтииор. вреия отправления, вреия прибытия) либо в виде рейсов с промежуточной посадкой Г)тйьв (попер рейса,. рос-Анднепес Х, время отправления,. вреня прибытия,). Г)тйы (номер рейса,.
Х. Баптииор. вреня отправления,. вреня прибытия,). вреня отправления, ч- время прибытия, 30 Это означает, что вы определяете город Х, в который можно попасть рейсом из Лос-Анджелеса и откуда можно улететь в Балтимор, причем самолет в Балтимор вылетает по крайней мере через 30 минут после прилета рейса из Лос-Анджелеса, чтобы осталось время на пересадку. Здесь не задан никакой алгоритм, заданы только условия для получения правильного решения.
Если мы сможем задать подобный набор условий, язык сформирует последовательность действий, необходимую для выбора подходящего рейса. История. Разработка языка Рго! ой началась в 1970 г. Аланом Кулмероэ и Филиппом Русселом (А!ап Сов! шегапег ап8 Р)пйрре Воцззс!). Они хотели создать язык, который мог бы делать логические закл)очения на основе заданного текста. Е!азвание Рго!ой является сокращением от нРКО8гашп))пй ш 1ОС)с». Этот язык был разработан в Марселе(Фраттция) в 1972 г.
Принцип резолюции Ковальского (Котка)з)(!), сотрудника Эдинбургского университета (раздел 8А.5), казался подходящей моделью, на основе которой можно было разработать механизм логических выводов. С ограничением резолюции па дизъюнкты Хорна унификация (раздел 8А.З) привела к эффективной системе, где неустранимый недетермипизм обрабатывался с помощью процесса отката, который мог быть легко реализован. Алгоритм резолюции позволял создать выполняемую последовательность, необходимую для реализации спецификаций, подобных приведенному выше отттоп~евию 1) т 9))1. Первая реализация языка Рго!ой с использованием компилятора Вирта 1Ю!гс!)) АЕСО1-'тйт была закончена в 1972 г., а основы современного языка были заложены в 1973 г.
Использование языка Рго!ой постепенно распространялось среди тех, кто занимался логическим про)раммированием, в основном благодаря личным контактам, а не через коммерциализацию продукта. В настоящее время существует несколько различных, но довольно похожих между собой версий. Хотя стандарта языка Рго)ой не существует, однако версия, разработанная в Эдинбургском университете, стала наиболее широко используемым вариантом. Недостаток разработок эффективных приложений Рго!ой сдерживал его распространение вплоть до 1980 г.
8.4. Последовательность вычисления неарифметических выражений 369 Краткий обзор языка. Программа на языке Рго!ой состоит из набора фактов, определенных отношений между объектами данных (фактами) и набором правил (образцами отношений между объектами базы данных). Эти факты и правила вводятся в базу данных через операцию сопви11. Для работы программы пользователь должен ввести запрос — набор термов, которые все должны быть истинны.
Факты и правила из базы данных используются для определения того, какие подстановки для переменных в запросе (называемые утаит)тикацией) согласуются с информацией в базе данных. Язык Рго!ой, как интерпретатор, приглашает ттолыоватсля вводить информацию. Пользователь набирает запрос или имя функции.
Выводится значение (иститта— уев, ил и лозсь — по) этого запроса, а также возможные значения переменных запроса, присвоение которых делает запрос истинным (то есть унифицирует запрос). Если ввести символ «;», тогда отображается следующий набор значений переменных, унифицирующий запрос, и так до тех пор, пока не исчерпается весь набор возможных подстановок, после чего Рго!ой печатает по и ждет следующего запроса. Возврат каретки воспринимается как прекращение поиска дополнительных решений. Хотя выполнение программы на языке Рго!о8 основывается на спецификации предикатов, оно напоминает выполнение программ на ацпликативных языках Е!БР или М!.. Разработка правил языка Рго!ой требует того же рекурсивного мышления, что и разработка программ на этих аппликативных языках.
Язык Рго!ой имеет простые синтаксис и семантику. Поскольку оп ищет отношения между некоторыми рядами объектов, основными структурами данных являются переменная и список. Правило ведет себя подобно процедуре, за исключением того, что концепция унификации более сложна, чем относительно простой процесс подстановки параметров в выражения (см. раздел 8.4 3). 8.4.2. Сопоставление с образцом В таких языках, как Рег(, Рго!ой и МЕ, ключевой операцией является операция сопоставления с образцом. В этом случае операция выдает положительный результат путем сопоставления и присваивания набора переменных заранее определенному шаблону.
Образцом этой операции является распознавание деревьев синтаксического разбора в НФБ-грамматиках, описанных в разделе 3.3.1. Например, следующая грамматика распознает палиндромы нечетной длины на алфавите, состоящем из 0 и 1: А -т ОАО ! 1А1 ! О ! 1 Правильная строка 00100 распознается следующим образом: Я, сопсставпяется с центров 1 А, сопоставляется с ОА,О Я, сопос|авпяется с ОА,О Из этих трех присваиваний А~ значения 1, Ат значения ОА.О и Ат значения ОАтО мы можем сконструировать полное дерево синтаксического разбора этой строки (рис. 8.10). Мы уже обсуждали операцию сравнения с образцом с помощью регулярных выражений Рог! в разделе 33.3.
5ХОВОЕ4 — это язык, разработанный для прямого моделирования этой возможности, как показано в обзоре языка 8.4. Обратите внимание на то, что приве- 370 Глава 8. Управление последовательностью действий денная программа состоит всего из 9 операторов, и вряд ли на любом из суще- ствующих языков можно было бы написать программу, решающую ту же самую задачу и состоящую из такого небольшого и в то же время мощного набора опе- раторов. Аа А1 1 Рис. 8.10. Сопоставление с образцом в лемке ЯЫОВОьа Рагепт000олп. Магу) РагептОГбоаап. Магу) Рагепт011В~)1 ,3олп) Рагепт011апп, оопп) Джон — родитель Мери Сюзанна — родитель Мери Билл — родитель Джона Анна — родительДжона Для нахождения родителя Мери нужно просто написать отношение Рагепс01( Х, Магу), а Рго1ой попытается определить значение Х из известного набора фактов, находящихся в базе данных, и сделает вывод, что Х может быть либо Джон, либо Сюзанна.
Если мы хотим узнать обоих родителей Мери, то нужен более сильный оператор. Мы можем разрабатывать предикаты, включающие несколько фактов из базы данных. Итак, если мы хотим узнать двух различных родителей Мери, то нужно записать: РагепСОГ1Х, Магу). РагепГОГ(т, Магу). поыХ - т). Также 3)чОВОЕ4 обладает еще одним интересным свойством. Его реализация не зависит от конкретной машинной архитектуры. Она разработана для виртуальной машины обработки строк (как показано на рис.
2.4 в разделе 2.2.2). Все, что требуется для запуска ЕЖОВОЕ, — это реализовать операции обработки строк виртуальной машины в виде макросов имеющегося компьютера. Благодаря этому БЫОВОЕ4 был одним из первых языков, который: !) был доступен на любом компъютере; 2) в любой реализации имел абсолютно одинаковую семантику. Если в языке Б)з)ОВОЕ4 для выполнения операции сравнения с образцом используется замещение строк, то в языке Рго!ой в качестве механизма сопоставления используется понятие отношения как множества п-кортежей. Из известных экземпляров этих отношений (называемых фактами) можно вывести другие экземпляры. Например, можно рассмотреть отношение Ра епт01 (Родитель), для которого известны следующие факты: 8.4.
Последовательность вычисления неарифметических выражений 371 Обзор языка 8.4. 8)ь(ОВО(.4 Воэможности. Сопоставление с образцом на основе НФБ-грамматик. Полностью динамический язык, включая обьявления, типы, распределение памяти, даже точки входа и выхода из процедуры. Реализация использует виртуальные макрокоманды обработки строк — простой перезаписью макрокоманддля любого существующего компьютера.
История. Разработка началась в 1962 г Ральфом Гри своп ьдом (В в!1 Ог!Виго!О), Иваном Полонским (!цап Ро!опзйу) и Дэвидом Фарбером (Оамо РагЬег), сотрудниками лаборатории АТЯТ Вео Еаоз. Их целью было создание языка обработки строк для работы с формулами и анализа графиков. В 1950 г. Ингве (Упдце) из М!Т разработал язык СОМ 1Т для обработки естественных языков на основе правил НФБ, однако группа из Ве!! Еаоз сочла СОМ!Т слишком ограниченным для своих целей.
Изначально язык назывался ЯСЕ? (ЯугпЬойс Сотри1а1юп 1 апдиаде 7), затем его название сменилось на ЯЕХ! (61ппд Ехргеззюп !п1егрге1ег), которое по понятным причинам было осуждено в 60-е гг., и, наконец, он стал называться ЯИОВОЕ (61пыд Опеп1еб зутВООс Еапдиаде) — искусственно созданный акроним, лишенный интуитивно понятнога смысла. Было разработано несколько версий языка ЯИОВОŠ— ЯИОВОЕ, ЯИОВОЕ2, ЯИОВОЕЭ и ЯИОВОЕ4. Последний пользовался успехом в 70-е гг. Пример. Найти среди вводимых строк палиндром, составленный иэ 0 и 1, максимальной нечетной длины: ОКЯИИАК = О ! ! ( О ОКЯИИАК О ! ! айдиндй ! Ус~анавливает в качестве образца НФБ-траииатику ИЕНМИЕ - Тй1М(!ИРОТ) : Г(ЕИО) Получас~ сгедуощую строку без завершающих пробелов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
