Учебник по Lisp (Материалы к экзамену и коллоквиумам 2013-го года), страница 4

Лисп рассматриваетпредставления функций как данные, поэтому функции могут быть какконстантными, так и переменными.Представления функции могут вычисляться и передаваться как параметрыили результаты других функций.Соответствие между именем функции и ее определением может быть изменено,подобно тому как меняется соответствие между именем переменной и еезначением.8) Ветвление (условное выражение) характеризуется тем, что ход процессазависит от некоторых условий. Условия следует сгруппировать в общийкомплект и соотнести с подходящими ветвями.

Такую организацию процессавычисления обеспечивает специальнаяфункция COND (condition). Ее аргументами являются двухэлементные списки,содержащие предикаты и соответствующие им выражения. Аргументов можетбыть любое число. Обрабатываются они по особой схеме: сначала вычисляютсяпервые элементы аргументов по порядку, пока не найдется предикат созначением “истина”.

Затем выбирается второй элемент этого аргумента ивычисляется его значение, которое и считается значением всего условноговыражения.(COND (p1 e1) (p2 e2) ... (pk ek) )|______|________|__________ предикаты для выбора ветви|______|____ ___|__________ ветви условного выраженияКаждый предикат pi или ветвь ei может быть любой формы: переменная,константа, вызов функции, композиция функций, условное выражение.22Обычное условное выражение (if Predicate Then Else) или (если Predicate то Thenиначе Else) может быть представлено с помощью функции COND следующимобразом:(COND (Predicate Then)(T Else))Или более наглядно:(COND (Predicate Then)(TElse ))Вычисление ряда форм в определении может быть обусловлено заранеезаданными предикатами.Пример:(COND ((EQ (CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x))) (T x) )Атом “T” представляет тождественную истину.

Значение всего условного выраженияполучается заменой первого элемента из значения переменной x на B в том случае, если(CAR x) совпадает с A.Объявленные здесь специальные функции QUOTE, COND LAMBDA и DEFUNсущественно отличаются от элементарных функций CAR, CDR, CONS, ATOM, EQправилом обработки аргументов. Обычные функции получают значения аргументов,предварительно вычисленные системой программирования по формулам фактическихпараметров функции.Специальные функции не требуют такой предварительной обработки параметров.Они сами могут выполнять все необходимое, используя представление фактическихпараметров в виде S-выражений.Рекурсивные функции: определение и исполнение9) Определения могут быть рекурсивны.Как правило рекурсивное применение функций должно быть определено в комплекте с нерекурсивными ветвями процесса.

Основное преназначение условных выражений рекурсивные определения функций.23Для примера рассмотрим функцию, выбирающую в списке самый левый атом:алг Левейший ( список x) арг xначесли Atom (x)то знач := xиначе знач := Левейший (Car (x))конНовая функция “Левейший” выбирает первый атом из любого данного.(DEFUN Левейший (x)(COND ((ATOM x) x)(T (Левейший (CAR x))) ))Если x является атомом, то он и является результатом, иначе функцию“Левейший” следует применить к первому элементу значения x, котороеполучается в результате вычисления формулы (CAR x).

На составных x будетвыполняться вторая ветвь, выбираемая по тождественно истинному значениювстроенной константы T.Определение функции “Левейший” рекурсивно. Эта функция действительноработает в терминах самой себя. Важно, что для любого S-выражения существуетнекоторое число применений функции CAR, после которого из этого Sвыражения выделится какой-нибудь атом, следовательно процесс вычисленияфункции всегда определен, детерминирован, завершится за конечное числошагов. Можно сказать, что для определенности рекурсивной функции следуетформулировать условие ее завершения.Введенные обозначения достаточны, чтобы пронаблюдать формированиезначений и преобразование форм в процессе исполнения функциональныхпрограмм.Рассмотрим вычисление формы:((DEFUN Левейший (LAMBDA (x)(COND ((ATOM x) x)(T (Левейший (CAR x))) )))(QUOTE ((A .

B) . C) )24)DEFUN дает имена обычным функциям, поэтому фактический параметр функции“Левейший” будет вычислен до того как начнет работать ее определение ипеременная “x” получит значение “((A . B) . C))”.x = ((A . B) . C))Таблица. Схема вывода результата формы с рекурсивной функцией.Вычисляемая формаОчередной шагРезультат и комментарииВход в рекурсию(Левейший (QUOTE ((A Выбор определения функции (COND ((ATOM x) x).

B) . C)))и(T (Левейший (CARx))) )Первый шаг рекурсииВыделениепараметров (QUOTE ((A . B) . C))функции(QUOTE ((A . B) . C))Вычислениеаргумента X = ((A . B) . C)функции(COND ((ATOM x) x)Перебор предикатов: выбор (ATOM x)(T(Левейший первого(CAR x))) )(ATOM x)Вычислениепервого Nil = “ложь”,предикатат.к. X – не атом.ПереходковторомупредикатуTВычислениевторого T = “истина” – константа.предикатаПереход к выделеннойветвиВторой шаг рекурсии(Левейший (CAR x))(CAR x)(COND ((ATOM x) x)выделениефункцииВычислениефункциипараметров (CAR x)аргумента X = (A . B)Рекурсивный переходредуцированномуаргументуПеребор предикатов: выбор (ATOM x)25к(T(Левейший первого(CAR x))) )(ATOM x)ВычислениепредикатаTВычислениепредиката(Левейший (CAR x))выделениефункцииВычислениефункциипервого Nil = “ложь”,т.к.

X – не атом.Переходковторомупредикатувторого T = “истина” – константа.Переход ко второй ветвиТретий шаг рекурсии(CAR x)параметров (CAR x)аргумента X = AРекурсивный переход кредуцированномуаргументуПеребор предикатов: выбор (ATOM x)(COND ((ATOM x) x)(T(Левейший первого(CAR x))) )(ATOM x)Вычислениепервого T – т.к. X теперь атомпредикатаПреход к первой ветвиВычислениезначенийAXпеременнойЗначениефункцииполученои вычисление завершеноВыход из рекурсииНекоторые определения функций могут быть хорошо определены на однихаргументах, но зацикливаться на других, подобно традиционному определениюфакториала при попытке его применить к отрицательным числам. Результат можетвыглядеть как исчезновение свободной памяти или слишком долгий счет безвидимого прогресса.

Такие функции называют частичными. Их определениядолжны включать в себя ветвления для проверки аргументов на принадлежностьфактической области определения функции - динамический контроль. Условныевыражения не менее удобны и для численных расчетов.Пример 1. Абсолютное значение числа.(Запись на алгоритмической нотации)алг АБС( цел x) арг xначесли (x < 0)то знач := - xиначе знач := xкон26(Лисп-программа)(DEFUN Абс (LAMBDA (x)(COND ((< x 0 ) (- x))(T x))))Пример 2. Факториал неотрицательного числа.(Запись на алгоритмической нотации)алг ФАКТОРИАЛ ( цел N) арг Nначесли (N = 0)то знач := 1иначе знач := N * ФАКТОРИАЛ (N - 1)кон(Лисп-программа)(DEFUN Факториал (LAMBDA (N)(COND ((= N 0 ) 1 )(T ( * N (Факториал (- N 1 ))) ) )))Это определение не завершается на отрицательных аргументах.Включается и набор наиболее употребимых базовых операций над такимиданными.

Если введены числа, то введены и традиционные арифметическиеоперации, но форма их применения подчинена общим правилам:(+ 1 2 3 4) = 10Функция, которая определена лишь для некоторых значений аргументовестественной области определения, называется частичной функцией.Пример 3. Алгоритм Евклида для нахождения наибольшего общего делителя двухположительных целых чисел при условии, что определена функция “Остаток”.(Запись на алгоритмической нотации)алг НОД ( цел x, y) арг xначесли (x < y)то знач := НОД ( y, x)инес Остаток (y, x) = 0то знач := x27иначе знач := НОД (Остаток (y, x), x)коностаток [x, y] - функция, вычисляющая остаток отделения x на y.(Лисп-программа)(DEFUN НОД (LAMBDA (x y)(COND ((< x y) (НОД y x))((= (остаток y x ) 0 ) x )(T (НОД (остаток y x) x )) )))Как и любое S-выражение, символьные представления функций могут бытьзначениями аргументов - функциональные аргументы.Базис элементарного Лиспа образуют пять функций над S-выражениями CAR,CDR, CONS, ATOM, EQ и четыре специальных функции, обеспечивающиеуправление программами и процессами и конструирование функциональныхобъектов QUOTE, COND, LAMBDA, DEFUN.Далее мы построим определение универсальной функции EVAL, позволяющейвычислять значения выражений, представленных в виде списков, - правилоинтерпретации выражений.Формально для перехода к практике нужна несколько большая определенность помеханизмам исполнения программ, представленных S-выражениями:аргументы функций как правило вычисляются в порядке ихперечисления,композиции функций выполняются в порядке от самой внутреннейфункции наружу до самой внешней,представление функции анализируется до того как начинаютвычисляться аргументы, т.к.