Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 103
Текст из файла (страница 103)
В случае оюибки переход на ЕИО ИЕИЕ!ИЕ (Р05(0) 5РЯИ("01") Рй05(0)) : Г(ВАО) Проверяет строку на наличие тогь«о нулей и единиц 5РАИ вЂ” строка из нупеи и единиц Р05(О) — первая позиция, РК05(0) — последняя 5И = 5!УЕ(ИЕИЕ!ИЕ) ИЕИЕ!ИЕ РО5(0) ОКЯММАК . РЯС!ИОКОМЕ Р05(5И) .5(ОК) Г(ИОТОК) Строка проверяется на соответствие траикатике через РО5(5И) Если сравнение не проюло.
переход в последнюю позицию Если успеюно, печатается ответ. Совпавюая часть присваивается РА(!ИойОМЕ ООТРОТ="МАТСИ " РА! 1ИОКОМГ й ООР) 5И = 5И - 1 :(ИЕХТ) ООТРОТ = "!МРКОРЕК !КРОТ " ИЕЬЕ!ИЕ (ЕООР) 5ТЯКТ ЕООР ИЕХТ ОК ИОТОК ВЯО ЕИО Ввод: Вывод: 11011 МАТСН: 11011 11011101 МАТСН: 11011 11211 !МРЙОРЕЛ )ИРЬТ; 11211 Ссылка. Г). Е. Ог!Вито!б "А Ь)з(огу а1 бзе ЯИОВО! ргодгагппцпд !апдоаде", АСМ Нтвгогу ОГРгодгагпттпд Салдиадев Сои уегелсе, Еаз Апде1ез, СА (диле 1978) (я)ОРЕхтИ Иобсев (13)8 (Аидов( 19?8)), 275-308.
Пример выполнения Здесь запятая, разделяющая предикаты, является логической операцией И Кто есть для истинности всего отношения все предикаты должны быть истинными). 372 Глава 8, управление последовательностью действий Перезапись элементов Переэипись элементов является ограниченной формой операции сопоставления с образцом, которая широко применяется в языках программирования.
Пусть заданы стРока а>аз, а„и пРавило пеРезаписи а =з )1, если а = ап тогда говоРЯт, что строка а, ... а, ~!) ., а.представляет перезипись элементов строки а1а~ .. а.. Сопоставление запроса языка Рго!ой с правилом в базе данных является формой перезаписи (с подстановкой; см. раздел 8А.З). Перезапись элементов уже рассматривалась нами в разделе 3 3.1 в связи с НФБ- грамматиками и синтаксическим разбором. Генерирование вывода цепочки в языке с заданной НФБ-грамматикой является просто формой процесса перезаписи. Например, если задана грамматика А — ~ОВ)1  — ~ ОА можно сгенерировать цепочку 001 посредством следующего вывода: А=~ ОВ ОВ ~ ООА ООА =~ 001 Используется правило А а ОВ Используется правило  — а ОА Используется правило А — > 1 В языке МБ перезапись элементов используется как форма определения функции.
Например, функция вычисления факториала в языке М!. может быть определена довольно просто: тип тастоюа11п, шт) - 11 и-1 Хьвп 1 в1зв п*тас1сюа11п-1); Здесь область определения функции РасОогаа1 состоит из двух частей: при и = 1 возвращается значение 1, при всех остальных положительных целых возврашаемое значение задается выражением п*1001ог1 а11п - 1). Два варианта разделяются оператором 10. Эту функцию можно рассматривать как две отдельные функции— константа 1 для множества (1) и значение п*уасХогза1 (п - 1) для всех остальных целых чисел (то есть (и ! и > 1) ). Вместо того чтобы использовать оператор 11 для разделения области определения, можно использовать перезапись элементов для указания каждого отдельного случая в определении функции: тип гасы!)- 1 ! тас1Й 1п1) = я." тасс!я -!) Здесь каждая подобласть определения отделяется символом ).
Язык М!. заменяет вызов функции на соответствухагдее определение. Сила языка Рго1ой заключается в построении отношений, которые могут быть логически выведены из известного набора фактов. Эти отношения могут быть построены из других отношений, как, например, Вгапсрагепс01 (дед или бабка): Вгаппрагеп10ПХ, у) — РагептОПХ. 7), Рагеп10П7. у). Эта запись обозначает, что отношение Вгапх)рагеп101 определяется (что обозначается символом -) как два отношения Рагеп101 таких, что существует некоторый объект 7, являющийся родителем У, но для него самого родителем является Х.
Таким образом, выполнение Вгапх)рагеп101(Х, Магу> приведет к тому, что Х будет либо 8111, либо Апп, а выполнение Вгапдрагеп10(1У. Лорп) приведет к ошибке, поскольку в нашей базе данных не содержится соответствующего факта. 8.4. Последовательность вычисления неарифметических выражений 373 Вкачестведругогопримерарассмотримфункцию1еп9(йязыкаМ! опаявляется композицией перезаписи элементов и более обшей операции сравнения с образцом: уцп 1епОСП(п11)- О 1 1епйтн(а;:у) = 1ч1епйтщу): п!1 обозначает пустой список, а:: — операцию конкатенации списка. То есть а:: Пх с. 01 = !а.Ь. с, 01.
В дашюм случае, сели область определения функции 1епОСМв пустой список, тогда значение будет равно О. Иначе если область является списком, состоящим хотя бы из одного элемента (а), тогда значение функции будет равно 1 плюс длина остатка списка. Язык М! автоматически сопоставляет аргумент функции 1епОСП и присваивает голову списка переменной а, а хвост — переменой у. Эта возможность становится очень важной, когда речь заходит о полиморфизм е в языке М 1. !Раздел 7.3).
8.4.3. Унификация База данных языка !Хго)ой состоит из фиктов, таких как Ра гепГОПЯпп. Зовя), и привил, таких как ОгапцрагепСОПХ. у).- РагепСОП Х. 2). Рагеп(0((2, у) Выражение, содержащее одну или более переменных, например 6гапбрагепСОС ( Х,,) ойп ), называется зипрогом и представляет собой неизвестное отношение. ! Более точное описание такого запроса мы дадим в разделе 8А.5 при обсуждении прин- пипа резолюции, управляющего выполнением программы на языке Рго108.) Основной особенностью языка Рго108 является использование операции сравнения с образцом для выяснения, разрешается ли запрос каким-либо фактом из базы данных или факт может быть выведен путем применения правил, содержащихся в базе данных, к другим фактам и правилам.
В языке Рго!ой используется операция унификиции — подстановки переменных в о~ношения — для определения (путем сравнения с образцом), имеется ли для данного запроса корректная подстановка, согласующаяся с правилами и фактами базы данных. Рассмотрим приведенное выше отношение РагепГОП Допустим, мы хотим разрешить запрос: Расеи(ОП Х. Магу) - Рагепгоу(Золп, у). В данном случае отношение-факт РагепООт(ООПП, Иагу) является решением для обеих частей запроса. Говорят, что экзелтляр Рагеп(0т(Оойп, Иагу) унифицирует Рагеп10!(Х, Иагу) и РагепСОт(Лойп.
у) подстановкой Оояп вместо Х, и Иагу вместо у, поскольку оба эти отношения после соответствующей подстановки выдают этот факт. Об унификапии можно рассуждать как о расширении общего свойства подстановки. Подстановка. Подстановка является одним из первых принципов, которые изучаются в программировании.
Подстановка — это основной принцип, лежащий в основе передачи параметров и создания макрорасширений. Например, рассмотрим макрос языка С': ()пеппе нунасго(А,В,С) рюпгу("Вшагу ХОХОХО 1з Жц)п". А, В. С. 4*(А)г2*(В)+(С)) рг1п(Г печатает выходнуто строку. Функция печатает свой первый строковый аргумент, используя встроенные коды для определения, в какое место выходной строки поместить значения последующих аргументов. Последовательность символов ХС обозначает, по нвло печатать следующий аргумент в списке квк целый.
Символы Хп обозначают конец строки. 374 Глава В. Управление последовательностью действий Данная строка означает, что когда в программе на языке С используется купи с го(,, ), первый фактический параметр пуаэсга заменяет параметр А, второй фактический параметр заменяет параметр В, третий — С Тоесть записыпупхзсга(1. О. 1) равносильна следующей; рг?пгг("В~лагу ХОХО ХО В ФО)п", 1 О. 1, 4*(1)ь2*(ОРЦ1)) Поскольку стра ковьш параметр функции рг? пг У также является подстановкой, то предыдущая запись равносильна следующей: ршпгГ("Вхпагу 101 14 5)п") Подставляемые параметры не обязательно должны быть целыми числами.
Любил строка может быть подставлена в макрорасширение вместо А, В н С. Таким образам, макрос луп?эрго(Х е У,772, Мучэг+ 3) эквивалентен следующей записи: рг~пгг("В~лагу ХОХОЖО м ХО)п". Х+У. 7!2. Мучат + 3. 4 * (Х + У) + 2 * (7!2) + Г Учаг + 3И Важно помнить, что мы подставляем произвольное выражение вместо одной переменной в определении макроса. Давайте расширим эту задачу до двух следующих макроподстановок: пупасго(Х ч У,7/2. ?), пупасго(?. ?, Мучаг + 3): Символы? представляют неизвестные подстановки. Возможно ли, чтобы оба эти макрооператора представляли одинаковые вычисления? Это и есть основной принцип, лежащий в основе унификации. Если мы примем, что 0 представляет Мучаг + 3 в первом макрорасширении, а А и В представляют Х + У и 7/2 соответственно — во втором, тогда аба макрооператора будут представлять одинаковые вычисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
