globalf5-240972240972 (850810), страница 6
Текст из файла (страница 6)
изменение переменныхлегко моделируется переопределением функций без аргументов.Поэтому признаем сразу, что значение переменной можно объявитьспециальной функцией SET.(SET 'PI 3.1415926)6) Обычно в системы программирования встраивают наиболее часто32Л.В. ГородняяОсновы функционального программированияиспользуемые константы. Некоторые атомы изначально имеютопределенный смысл, например,базовые функции, представлениепустого списка NIL и тождественно истинная константа TВ зависимости от контекста одни и те же объекты могут играть рольпеременных или констант, причем значения и того, и другого могутбыть произвольной сложности. Если объект играет роль константы, тодля объявления константы достаточно заблокировать его вычисление,то есть как бы взять его в кавычки (quotation), отмечающие буквальноиспользуемые фразы, не требующие обработки.
Для такой блокировкивводится специальная функция QUOTE, предохраняющая свойединственный аргумент от вычисления.(QUOTE A);константа атом A(QUOTE (A B C) );константа список (A B C)(ATOM (QUOTE A));= T — аргумент предиката - атом A(ATOM (QUOTE (A B C))) ; = Nil — аргумент предиката - список (A B C)(ATOM A);— значение не определеноОно зависит от вхождения переменной A, а ее значение зависит отконтекста и должно быть определено или задано до попытки выяснить,атом ли это.Можно сказать, что функция QUOTE выполняет в древовиднойструктуре программы роль помеченного контейнера.
С ее помощьюлюбое выражение может быть заключено в контейнер, а контейнерпомечен указанием, что вычислять его содержимое не следует. Потом,при выполнении функции QUOTE, пометка и контейнер исчезают, ивыражение может обрабатываться по общей схеме. Например:(третий (QUOTE (A B C))) — применение функции "третий" кзначению, не требующему вычисления.7) Некоторые определения функций могут быть хорошо определены наодних аргументах, но зацикливаться на других, подобно традиционномуопределению факториала при попытке применить его к отрицательнымчислам.
Результат может выглядеть как исчезновение свободной памятиили слишком долгий счет без видимого прогресса. Такие функцииназывают частичными. Их определения должны включать в себяветвления для проверки аргументов на принадлежность фактической33Л.В. ГородняяОсновы функционального программированияобласти определения функции — динамический контроль. Точнее,вычисление ряда форм в определении может быть обусловлено заранеезаданными предикатами .Ветвление(условное выражение) характеризуется тем, что ходпроцесса зависит от некоторых предикатов (условий), причем условияследует сгруппировать в общий комплект и соотнести с подходящимиветвями.
Такую организацию процесса вычисления обеспечиваетспециальная функция COND (condition), аргументами которой являютсядвухэлементные списки, содержащие предикаты и соответствующие имвыражения. Аргументов может быть сколько угодно, а обрабатываютсяони по особой схеме: сначала вычисляются первые элементыаргументов по порядку, пока не найдется предикат со значением"истина". Затем выбирается второй элемент этого аргумента, ивычисляется его значение, которое и считается значением всегоусловного выражения .(COND (p1 e1) (p2 e2) ...
(pk ek) )pi - предикаты для выбора ветви,ei - ветви условного выраженияКаждый предикатpi или ветвь ei может быть любой формы:переменная, константа, вызов функции, композиция функций, условноевыражение.Обычное условное выражение (if Predicate Then Else) или(если Predicate то Then иначе Else) может бытьпредставлено с помощью функции COND следующим образом:(COND (Predicate Then)(T Else))Разумеется, можно повышать наглядность подбором геометрии текста:(COND(Predicate Then)(T Else))34Л.В. ГородняяОсновы функционального программирования(COND((EQ (CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x)) )(T x))Пример 2.2.АтомT представляет тождественную истину.
Значение всегоусловного выражения получается путем замены первого элемента иззначения переменной x на B в том случае, если (CAR x) совпадает сAСодержательно функции QUOTE, COND, LAMBDA образуют базовыйкомплект средств управления программами и процессами,поддерживающий стиль программирования, идеологически близкийструктурному программированию [18].Такие специальные функции QUOTE, COND, LAMBDA существенноотличаются от элементарных функций CAR, CDR, CONS, ATOM, EQправилом обработки аргументов. Обычные функции получают значенияаргументов,предварительновычисленныесистемойпрограммирования по формулам фактических параметров функции.Специальные функции не требуют такой предварительной обработкипараметров. Они сами могут выполнять все необходимое, используяпредставление фактических параметров в виде S-выражений.Рекурсивные функции: определение и исполнение8) Определения могут быть рекурсивными.На практике такие определения обычно имеют глобальные имена,задаваемые с помощью функции DEFUN, о которой еще будет речь вконце этой лекции.
Сейчас теоретически можно ограничитьсяконструктором локальных функций LABEL, которую мы вводим здесьдля учебных целей (в системе GNU Clisp его нет, но для него прощеопределение интерпретатора, которое будем строить в следующейлекции).35Л.В. ГородняяОсновы функционального программированияКак правило, рекурсивные вызовы функций должны быть заданы вкомплекте с нерекурсивными ветвями процесса.
Основное применениеусловных выражений — рекурсивные определения функций .(LABEL премьер;имя локальной функции(LAMBDA (x);определение функции(COND ((ATOM x) x)(T (премьер (CAR x)))) ) )Пример 2.3.Новая функция "премьер" выбирает первый атом из любого данного.Если x является атомом, то он является результатом, иначе функцию"премьер" следует применить к первому элементу значения x, котороеполучается в результате вычисления формулы (CAR x).
На составныхx будет выполняться вторая ветвь, выбираемая по тождественноистинному значению встроенной константы T.Определение функции "премьер" рекурсивно. Эта функциядействительно работает в терминах самой себя. Важно, что для любогоS-выражения существует некоторое число применений функции CAR,после которого из этого S-выражения выделится какой-нибудь атом,следовательно, процесс вычисления функции всегда определен,детерминирован и завершится за конечное число шагов. Можно сказать,что для определенности рекурсивной функции следует формулироватьусловие ее завершения.Введенные обозначения достаточны, чтобы проследить заформированием значений и преобразованием форм в процессеисполнения функциональных программ.
Рассмотрим вычислениеформы:((LABEL премьер(LAMBDA (x)(COND ((ATOM x) x)(T (премьер (CAR x)))) ) ) ; объявлена локальная функция "премьер"(QUOTE ((A . B) . C) ) ; дан аргумент локальной функции) ; завершено выражение с локальной функцией36Л.В. ГородняяОсновы функционального программированияLABEL вырабатывает представление функции, которое тут же можетбыть применено к аргументу. При этом LABEL дает имена обычнымфункциям, поэтому фактический параметр функции "премьер" будетвычислен до того, как начнет работать ее определение, и переменная xполучит значение ((A . B) .
C)).x = ((A . B) . C))Таблица 2.5. Схема вывода результата формы с рекурсивной функциейВычисляемая формаОчередной шаг Результат и комментарииВход в рекурсиюВыбор(COND ((ATOM x) x)(премьер (QUOTEопределения (T (премьер (CAR((A . B) .
C)))x))) )функции иПервый шаг рекурсиивыделение(QUOTE ((A . B) .параметровC))функцииВычисление(QUOTE ((A . B) .аргументаx = ((A . B) . C)C))функции(COND ((ATOM x)x) Перебор(ATOM x)(T (премьер (CAR x))) )(ATOM x)предикатов:выбор первогоВычислениепервогопредикатаNIL = "ложь", т.к. x — неатом. Переход ко второмупредикатуВычислениеT = "истина" —Tвторогоконстанта. Переход кпредикатавыделенной ветвиВторой шаг рекурсиивыделение(премьер (CAR x)) параметров(CAR x)функции37Л.В. ГородняяОсновы функционального программированияx = (A . B).(CAR x)ВычислениеаргументафункцииРекурсивный переход кредуцированномуаргументу(COND ((ATOM x) x) Перебор(T (премьер (CARпредикатов:(ATOM x)x))) )выбор первогоВычислениеNIL = "ложь", т.к. x — не(ATOM x)предикатаатом.
Переход ко второмупервогопредикатуВычислениеT = "истина" —Tвторогоконстанта. Переход копредикатавторой ветвиТретий шаг рекурсиивыделение(премьер (CAR x)) параметров(CAR x)функцииx = A.(CAR x)ВычислениеаргументафункцииРекурсивный переход кредуцированномуаргументу(COND ((ATOM x) x) Перебор(T (премьер (CARпредикатов:(ATOM x)x))) )выбор первого(ATOM x)ВычислениепервогопредикатаT — т.к. x теперь атом.Переход к первой ветвиAВычисление38Л.В.
ГородняяxОсновы функционального программированиязначенийпеременнойЗначение функцииполучено и вычислениезавершеноВыход из рекурсииУсловные выражения не менее удобны и для численных расчетов:(LABEL Абс(LAMBDA (x)(COND((< x 0 ) (- x))(T x)) ) )Пример 2.4. Абсолютное значение числа(LABEL Факториал(LAMBDA (N)(COND((= N 0 ) 1 )(T ( * N (Факториал (- N 1 ))) )) ) )Пример 2.5. Факториал неотрицательного числаЭто определение не завершается на отрицательных аргументах.Функция, определенная лишь для некоторых значений аргументовестественной области определения, называется частичной функцией.Работа с числами, строками и другими элементарными типами данныхобычно строится как включение в язык и систему так называемыхсамоопределимых данных, выглядящих достаточно естественно, чтобыих смысл не требовал особых пояснений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
