М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
 Скачать 0.92 Mb.
|
1.6.Примеры рефал-функцийЗавершая описание базисного Рефала, отметим, что программирование на нём имеет ряд характерных особенностей, присущих функциональному программированию. Центральную роль в нём играют функции: в виде функции оформляются все содержательные действия программируемого алгоритма, а нужная последовательность этих действий достигается вызовом функций в определённом порядке, т.е. суперпозицией этих функций. Вместо традиционных циклов императивных языков программирования в Рефале применяется более мощное средство – рекурсия. Другая характерная особенность языка Рефал – отсутствие оператора присваивания. Роль рефал-переменных в корне отлична от их роли в традиционных императивных языках программирования. Переменные могут получить значения только в процессе синтаксического отождествления, и эти значения могут быть использованы только в пределах одного рефал-предложения. Рассмотрим теперь несколько рефал-функций разной степени сложности. Пример 1: Вернёмся к определению функции ChangeAllPlus, приведённому в конце раздела 1.3: ChangeAllPlus e1 '+' e2 = e1 = e1 Функция реализует замену во входной цепочке символов всех знаков + на знаки -. Поскольку по умолчанию используется левое согласование, то в случае, когда применимо первое предложение (в обрабатываемой цепочке символов есть знак +), переменная е1 получит самое короткое возможное значение, и знак + в него входить не будет. Поэтому целесообразно оставить внутри функциональных скобок рекурсивного вызова лишь переменную е2 – только её значение может содержать знаки +, подлежащие замене. Таким образом, получаем следующее определение функции: * Функция ChangeAllPlus заменяет в цепочке символов * все символы сложения на символы вычитания, * например: 'A+B+C' будет преобразовано в 'A-B-C' ChangeAllPlus e1 '+' e2 = e1 '-' e1 = e1 Так определённая функция выполняет преобразование цепочки символов более эффективно, т.к. на каждом шаге работы рефал-машины синтаксическое отождествление применяется ко всё более короткой цепочке символов. Например, при вычислении функционального вызова на первом шаге работы рефал-машины к нему применимо первое предложение функции ChangeAllPlus, так как выражение 'AX+BY+CZ' отождествимо с образцом e1 '+' e2 при e1 ↔ 'AX', e2 ↔ 'BY+CZ'. После применения этого предложения в поле зрения рефал-машины появится выражение 'АX-' Поскольку это выражение содержит только один функциональный терм, он будет ведущим, и к входящему в него выражению 'BY+CZ' на втором шаге работы рефал-машины будет вновь применено первое предложение функции ChangeAllPlus, но уже при значениях переменных e1 ↔ 'BY', e2 ↔ 'CZ'. Поле зрения после выполнения этого шага примет вид: 'АX-BY-' На третьем шаге работы рефал-машины единственный (и ведущий) функциональный терм заменится на выражение 'CZ', поскольку применимым будет только второе предложение функции при е1 ↔ 'CZ' (в аргументе функционального терма нет символа +). В поле зрения останется выражение 'AX-ВY-СZ', которое уже не содержит функциональных термов и является результатом вычисления исходного функционального вызова Пример 2: функция Palindrom, которая проверяет, является ли входная цепочка символов палиндромом. Палиндромом является цепочка символов, читаемая одинаково как справа налево, так и слева направо, например, «авва», «шалаш», строка «а роза упала на лапу азора», если в ней убрать пробелы. Функция содержит 4 предложения и, по сути, является предикатом (логической функцией) – в зависимости от результата проверки она вырабатывает цепочку литер 'yes' или 'no'. * Функция Palindrom, проверяющая, является ли * входная строка палиндромом Palindrom s1 e2 s1 = s1 = 'yes' = 'yes' e1 = 'no' Эта функция рекурсивна: если входная цепочка символов начинается и кончается одним и тем же символом s1, то процесс проверки продолжается для е2 – оставшейся части цепочки. Рекурсивным является только первое предложение функции Palindrom. Следующие два предложения служат для завершения рекурсии. Если цепочка символов состоит из единственного символа (второе предложение функции), то она является палиндромом (это предложение срабатывает в случае, когда исходная цепочка-палиндром состояла из нечётного количества символов). Пустое выражение также считается палиндромом (третье предложение функции, оно срабатывает, если исходная цепочка-палиндром состояла из чётного количества символов). Если же ни одно из первых трёх предложений функции Palindrom не может быть применено, то исходное выражение не является палиндромом – это фиксируется в последнем предложении функции. Заметим, что последнее предложение функции Palindrom (любое выражение заменить на 'no') применимо всегда, поэтому оно не может быть переставлено с другими предложениями. В то же время первые три предложения могут быть поставлены в любом порядке, поскольку их области применимости не пересекаются: образец первого предложения может сопоставиться только с цепочками, состоящими не менее чем из двух символов. Рассмотрим пошаговую работу рефал-машины при вычислении функционального обращения На втором шаге также применится первое предложение функции, переменные получат следующие значения: s1 ↔ 'а', e2 ↔ 'л', а содержимое поля зрения примет вид: На третьем шаге первое предложение уже не может быть применено, применится второе предложение, значение переменной: s1 ↔ 'л'. В результате применения этого предложения функциональный терм На четвёртом шаге произойдёт останов рефал-машины, поскольку в поле зрения больше нет функциональных термов. Оставшаяся в поле зрения цепочка 'yes' – результат вычисления исходного функционального вызова Пример 3: функция DelRepSymb, удаляющая в исходной цепочке символов повторные вхождения каждого символа, т.е. из нескольких вхождений одного символа она должна оставить только одно. Тем самым, в результирующей цепочке все символы попарно различны. * Функция DelRepSymb удаляет повторные вхождения * символов, оставляя только первое вхождение * каждого символа. * Например, 'abaacebf' будет преобразовано в 'abcef' DelRepSymb e1 sA e2 sA e3 = e1 e1 = e1 Функция рекурсивна и завершает свою работу только тогда, когда первое, рекурсивное предложение не применимо, т.е когда в обрабатываемом выражении не осталось одинаковых символов. Причём каждое применение первого предложения удаляет из обрабатываемого выражения одно повторное вхождение символа. Также, как и в примере 1, при построении рекурсивного предложения используется тот факт, что значение переменной е1 не может содержать символов, входящих в выражение более одного раза (поскольку по умолчанию согласование левое), а значит, е1 можно не включать в аргумент рекурсивного вызова. В то же время, в этом аргументе, в его начале содержится sA – именно это обеспечивает сохранение в результирующей цепочке символов первого вхождения каждого символа. В аргументе рекурсивного вызова также стоят переменные е2 и е3, в значениях которых могут быть повторные вхождения как sA, так и других символов. Заметим, что поскольку второе предложение функции применимо всегда, оно помещено последним. Рассмотрим работу рефал-машины при вычислении функционального вызова На втором шаге также применяется первое предложение функции, при этом значения переменных: e1 ↔ пусто, sA ↔ 'a', e2 ↔ 'b', e3 ↔ 'cebf'. Содержимое поля зрения после выполнения второго шага: На третьем шаге опять применяется первое предложение, на этот раз значения переменных: e1 ↔ 'a', sA ↔ 'b', e2 ↔ 'ce', e3 ↔ 'f', и итоговое поле зрения: 'a' На четвёртом шаге первое предложение уже не может быть применено, поскольку в аргументе функции все символы попарно различны. Применяется второе, заключительное предложение функции DelRepSymb, и в поле зрения остаётся выражение 'abcef' без функциональных термов. Эта строка и является результатом вычисления исходного функционального вызова. Другим возможным вариантом удаления повторных вхождений символов является такое определение функции: * Функция DelRepSymb2 удаляет повторные вхождения * символов, оставляя только последнее вхождение * каждого символа * Например, 'abaacebf' будет преобразовано в 'acebf' DelRepSymb2 e1 sA e2 sA e3 = e1 e1 = e1 В этом варианте при удалении повторных символов в рекурсивном вызове сохраняется второе их вхождение в цепочку, тем самым в итоге остаётся только последнее вхождение каждого символа, и результатом вычисления функционального вызова Пример 4: функция, осуществляющая зеркальное отображение исходной цепочки символов, т.е. изменение порядка символов в ней на противоположный: например, из цепочки 'abcde' получается цепочка 'edcba'. * Функция RevString зеркально * отображает (реверсирует) цепочку символов RevString s1 e2 = = Основное преобразование делает первое предложение функции, оно расщепляет цепочку на первый символ s1 и остаток е2, и помещает s1 в конец цепочки, получающейся в результате реверсирования е2. Второе предложение (пусто заменить на пусто) служит для завершения рекурсии. Предложения можно поменять местами, поскольку области их применимости не пересекаются. Рассмотрим вычисление функционального обращения Функция RevString зеркально отображает выражения, состоящие только из символов-литер. Для реверсирования выражений, в которых есть структурные скобки, потребуется написать более сложную функцию. Пример 5: функция, зеркально отображающая произвольное рефал-выражение на всех его уровнях. К примеру, зеркальным отображением выражения 'a'('b'('cd'))('ef') будет выражение ('fe')(('dc')'b')'a'. * Функция RevExp зеркально отображает * структурированное выражение на всех его уровнях RevExp s1 e2 = (e1) e2 = = Первое предложение функции RevExp срабатывает в том случае, если в начале выражения стоит символ – этот символ s1 переносится в конец, а остаток выражения е2 зеркально отображается рекурсивным вызовом RevExp. Второе предложение содержит 2 рекурсивных вызова: один нужен для реверсирования содержимого структурного терма, а другой – для реверсирования остатка выражения. Третье предложение функции RevExp завершает рекурсию. Рассмотрим пошаговую работу рефал-машины при вычислении функционального вызова Шаг 1. Ведущий функциональный терм: Применяется первое предложение функции RevExp. При этом значения переменных: s1 ↔ 'a', е2 ↔ ('b'('cd'))('ef'). Подставляя эти значения в правую часть применяемого предложения, получаем в поле зрения выражение Шаг 2. Ведущий функциональный терм – Применяется второе предложение функции (т.к. аргумент этого терма начинается со структурной скобки), значения переменных: е1 ↔ 'b'('cd'), е2 ↔ ('ef'). Подстановка этих значений в правую часть применяемого предложения и замена ею ведущего терма даёт следующее выражение в поле зрения: Шаг 3. Ведущий функциональный терм – Применимо второе предложение функции, значения переменных: е1 ↔ 'ef', е2 ↔ пусто. Ведущий терм заменяется на Шаг 4. Ведущий функциональный терм – Применимо третье предложение функции RevExp, и ведущий терм заменяется на пустое выражение. Содержимое поля зрения рефал-машины после выполнения шага: ( Шаг 5. Ведущий функциональный терм – Применяется первое предложение функции со значениями переменных s1 ↔ 'e', е2 ↔ 'f'. Терм заменяется на ( Шаг 6. Ведущий функциональный терм – Применимо первое предложение, значения переменных: s1 ↔ 'f', е2 ↔ пусто. Замена терма на ( Шаг 7. Ведущий функциональный терм: Применяется третье предложение функции, и ведущий функциональный терм заменяется на пустое выражение. В поле зрения рефал-машины появляется выражение ('fe')( Шаг 8. Ведущий функциональный терм: Применимо первое предложение функции RevExp, значения переменных: s1 ↔ 'b' и е2 ↔ ('cd'). Терм заменяется на Шаг 9. Ведущий функциональный терм: Применяется второе предложение функции со значениями переменных e1 ↔ 'cd', е2 ↔ пусто. Замена терма на ('fe')( Шаг 10. Ведущий функциональный терм – Применимо третье предложение: пусто заменить на пусто, и содержимое поля зрения рефал-машины: ('fe')(( Шаг 11. Ведущий функциональный терм: Применяется первое предложение функции, значения переменных: s1 ↔ 'c', е2 ↔ 'd'. Замена терма на Шаг 12. Ведущий функциональный терм: Применимо первое предложение со значениями переменных s1 ↔ 'd', е2 ↔ пусто. Терм заменяется на Шаг 13. Ведущий функциональный терм: Применимо третье предложение функции, и содержимое поля зрения рефал-машины после выполнения шага: ('fe')(('dc')'b')'a' Шаг 14. Поскольку в поле зрения не осталось функциональных термов, то рефал-машина останавливается с результатом 'a'('b'('cd'))('ef'). |