Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 153
Текст из файла (страница 153)
Специальная форма оператора многовариантного ветвления в языке Бс)зете называется СОМО. Оператор СОМО представляет собой незначительно обобшенный вариант математического условного выражения; он позволяет нескольким предикатам принимать истинные значения одновременно. Поскольку разные математические условные выражения имеют разное количество параметров, оператор СОМО не требует фиксированного количества фактических параметров. Каждый параметр оператора СОМО представляет собой пару выражений, первое из которых является предикатом. Общий вид оператора СОМО приведен ниже: ( СОМО (предикат 1 выражение (выоажение)) (предикат 2 выражение (выражение)) (предикат и выражение (выражение)! (ЕЕЯЕ выражение (выражение)) ) В некоторых реализациях языка Ьс)зеве выражение ЕЬЯЕ является необязательным.
Семантика оператора СОМО заключается в следующем. Предикаты параметров вычисляются по одному в каждый момент времени, начиная с первого параметра, пока какой-либо из предикатов не примет значение ((Т. Затем вычисляются выражения, следуюшие за первым предикатом, который оказался равным () Т, и его значение возврашается в качестве значения оператора СОМО.
Заметим, что в операторе СОМО атом ()Т можно использовать в качестве постоянного предиката, в этом случае выражения, слелуюшие за этим предикатом, вычисляются всегда, а в качестве значения оператора СОМО возврашается значение последнего такого выражения. Конечно, использовать атом ()Т в качестве предиката имеет смысл только для последнего параметра оператора СОМО. В этих ситуациях обычно используется специальная предикатная константа ЕЬЯЕ, означаюшая то же, что и атом ((Т. ) 4.5. Введение в язык бсЬеше Если ни один параметр оператора СО)(О не имеет преликата, принимающего значение () Т, то оператор СО() О возвращает пустой список ( ) .
Отметим схожесть межлу оператором СО))0 и многовариантным оператором ветвления с оператором "иначе" в конце, таким как оператор саве в языке Ада. 14.$.5. Пример функции не языке ЗсЬезие Этот раздел содержит несколько примеров определения функций в языке Бс)зете. Описываемые программы решают простые задачи обработки списков. Рассмотрим задачу определения принадлежности данного атома простому списку. Простой список — это список, не имеюший полсписков. Если функция называется щещЬег, то ее можно использовать слелуюшим образом: (щещЬег 'В '(А В С)) возвращает ()Т (щещЬег ' В ' (А С 0 Е) ) возвращают () С точки зрения циклов задача принадлежности заключается в простом сравнении данного атома и отдельных элементов данного списка по одному в каждый момент времени в определенном порядке, пока не будет найдено соответствие или в списке не останется элементов.
подлежащих сравнению. Подобный процесс можно выполнить с помошью рекурсии. Функция сравнивает данный атом с первым элементом списка, если они совпадают, возвращается значение () т. Если они не совпадают, те атом можно найти лишь в оставшейся части списка, так что функцию можно применить к самой себе с оставшейся частью списка в качестве параметра и вернуть результат этого рекурсивного вызова. Этот процесс содержит два способа рекурсии: либо при вызове список пуст, и тогда в качестве результата возврашается пустой список (], либо обнаруживается соответствуюший элемент списка, и возвращается значение () Т.
Три описанных случая должны быть обработаны в функции: пустой входной список, совпаление атома и первого элемента списка нли несовпадение атома с первым элементом списка, что приводит к рекурсивному вызову функции. Эти случаи являются параметрами оператора СОВО, при этом последний случай следует считать выбором по умолчанию, переход на который производится предикатом ееЯе.
Полная функция приведена ниже: (ОЕГ1ХЕ (щещЬег агщ 11з) (СОХО ((МОЕ) ? 115) ()) ((ЕОЗ асщ (САВ 1'з) ()Т) (ЕЕЯЕ (щещЬег агщ (СОК 11е))) Эта форма типична для простых функций обработки списков на языке Бсйеше. В таких функциях данные в списках обрабатываются поэлементно. Отдельные элементы можно получить с помошью функции САВ и процесса, применяюшегося рекурсивно к оставшейся части списка. Заметим, что проверка случая пустого списка должна предшествовать проверке на равенство атома и элементов, поскольку применение функции САК к пустому списку является ошибкой.
В следующем примере рассматривается задача эквивалентности двух заданных списков. Если оба списка простые, то эта задача решается относительно легко, хотя и с ис- Глава 14. Функциональные языки программирования пользованием незнакомых нам пока приемов. Предикатная функция для сравнения двух простых списков показана ниже: (РЕГ1(ЧЕ (ес(ца1в1жр 11в1 11в2) ( СО)ЧР ((НРЬЬТ 11в1) ()ЧУЬЬ'? 11в2)) ((ХРЬЬТ 11в2) '()) ((ЕО? (САН 11в1) (САЯ 11в2)) (ес(иа1в1мр (СРй 11в1) (СРЯ 11в2))) (ЕЬЯЕ ' ()) )) Первый случай, обрабатываемый первым параметром оператора СОКР, возникает. если список, являюшиЯся первым параметром, пуст.
Эта ситуация возникает при внешнем вызове, если список, являюшийся первым параметром, изначально был пуст. Поскольку рекурсивный вызов использует оставшиеся части списков в качестве двух параметров, первый список при таком вызове может быть пустым, если все элементы были >далены из него во время предыдуших рекурсивных вызовов.
Когда первый список пуст, следует проверить, не пуст ли второй список. Если да, то оба списка эквивалентны (либо изначально, либо первые элементы этих списков были равны между собой при всех предыдуших рекурсивных вызовах) н предикат НУЬЬ? корректно возврашает значение ((Т. Если второй список не пуст, то он больше, чем первый, и в качестве результата предиката )ЧРЬЬТ следует вернуть пустой список ( ) . Напомним, что любой непустой список, воз- врашаемыЯ предикатной функцией, интерпретируется как () Т.
Слелуюший случай относится к ситуации, когда второй список становится пустым, а первый список еше не пуст. Эта ситуация возникает, только если первыЯ список больше второго. При этом следует проверять только второй список, поскольку все ситуации, в которых первый список является пустым, обрабатываются в первом случае. Третий случай является рекурсивным шагом, на котором проверяется равенство соответствуюших элементов двух списков с помошью сравнения первых элементов двух непустых списков.
Если онн равны, то лва списка совпадают вплоть до этой точки, поэтому рекурсия применяется к оставшимся частям обоих списков. Это условие не выполняется, если обнаруживаются два отличаюшихся друг от друга атома. Когда это происходит, мы, очевидно, не должны продолжать сравнение, так что возникает случай по умолчанию, последний среди случаев оператора СО))Р, что приводит к возврату в качестве результата пустого списка ( ] н прекрашению дальнейших сравнениЯ. Заметим, что функция е~(ца1вппр ожидает в качестве параметров списки и неправильно работает, если один или оба параметра являются атомами.
Проблема сравнения двух списков обшего вида немного сложнее, чем только что описанная, поскольку подсписки полностью отслеживаются с помошью приведенного выше процесса сравнения. Именно в этой ситуации проявляется мошь рекурсии, поскольку подсписки имеют ту же форму, что н заданные списки. Каждый раз, когда соответствуюшие элементы двух заданных списков представляют собой списки, они разделяются на две пары, состояшие из первого элемента и остальной части списка. и к ним применяется рекурсия.
Это великолепныЯ пример полезности подхода разделяй-и- властвуй. Если соответствуюшие элементы двух заданных списков прелставляют собой атомы, они просто сравниваются с помошью функции ЕОЭ. 14.5. Введение в язык Всйаше 5Р7 Определение полной функции приводится ниже: (0ЕГ1((Е (ес(ца1 11в1 11в2) ( СО((0 (((хОТ (ЬТЯТ? 11в1)] (Е(]? 11в1 11в2)] ((НОТ (1,1ЯТ? 11в2)) ' ()) ((МОЬЬ? 11в1) (г]УЬЬ? 11в2)) ((ИОЬЬ? 11в2!) '() ((ег)ца1 (САВ 11в1) (САВ 11в2)) (ес)ца1 (СОВ 11в1) (СОВ 11в2)) [ЕЬЯЕ '()) )) Первые два случая оператора СО](0 обрабатывают ситуацию, когда какой-либо из параметров является атомом, а не списком. Третий и четвертый случаи предназначены для ситуаций, когда один или оба списка пусты. Эти случаи также предотвращают попытку извлечь первый элемент из пустого списка в последующих случаях.
Пятый случай оператора СО)(0 наиболее интересен. Предикатом является рекурсивный вызов с первыми элементами списков в качестве параметров. Если этот вызов возвращает значение ()Т, то рекурсия применяется снова к оставшимся частям списков. Это позволяет включать в оба списка подсписки любой глубины. Такое определение функции ес)ца1 работает на любой паре выражений, а не только на паре, состоящей из списков.
Функция ес(ца1 эквивалентна системной предикатной функции ЕООАЬ?. Заметим, что функция ЕООАЬ? должна использоваться только при необходимости (когда вид действительных параметров неизвестен), поскольку она работает намного медленнее, чем функции ЕО? и ЕОу?. Другой широко распространенной операцией обработки списков является создание нового списка, содержащего все элементы двух списков, заданных в качестве аргументов. Обычно эта операция реализуется в языке Яслеае как функция с именем аррепгд Она сводится к повторному использованию оператора СО)(0, чтобы поместить элементы списка, являющегося первым аргументом функции, в список, являющийся вторым аргументом.
Для пояснения действий функции аррепс] рассмотрим следующие примеры: (аррепс( '(А В] '(С 0 В)) возврашает (А В С 0 В) (аррепс( '((А В] С) '(О (Е Г))) возвращает ((А В) С 0 (Е Г]] Опрелеление функции аррепс) приведено ниже: (0ЕГ1](Е (аррепс( 11в1 11в2) ( СО)(0 ((](ОЬЬ? 1зв1) 11з2) (ЕЬЯЕ (СО((Я (САВ 11в1) (аррепс] (СОВ 11з1) 11в2])] )) Рассмотрим функцию ццевв языка Бсйеше, использующую функцию шешЬег, описанную в этом разделе.
Попробуем определить, что она делает перед тем, как прочитать ее описание, приведенное ниже. Предположим, что параметрами являются простые списки. (0ЕГ1МЕ (дпевв 11в1 11в2) ( СО](0 (()(ОЬЬ? 11в1) '()) ((шешЬег (САВ 11в1) 1з.в2) (СО](Я (САВ 11в1) (диеза (СОВ 11в1) 11в2) ) ) 596 Глава 14. Функциональные языки программирования (ЕОЯЕ (сцеяя (СОВ 11я1) 11я2)) )) Предполагается, что два параметра функции сцеяя представляют собой простые списки. Функция соева возвращает в качестве результата простой список. состоящий из общих элементов обоих списков.
Таким образом. если список параметров представляет собой множества, функция оцеяя вычисляет список, состоящий из элементов, принадлежащих пересечению этих двух множеств. Функция ' ЕТ позволяет временно связывать имена со значениями подвыражений. Она часто используется лля вынесения за скобки общих подвыражений из более сложных выражений.
Эти имена затеи используются при вычислении других выражений. Ее общий внл приведен ниже: (1ЕТ ( (имл 1 выражение 1) (имл 2 выраженле 2) (ныл и выражение и)) тело ) Семантика функции ОЕТ состоит в том, что вычисляются первые л выражений, а результирующие значения связываются с их ассоциированными именами. Затем вычисляются выражения. принадлежащие телу функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
