globalf5-240972240972 (850810), страница 7
Текст из файла (страница 7)
Включается и набор наиболееупотребимых базовых операций над такими данными. Если введенычисла, то введены и традиционные арифметические операции, ноформа их применения подчинена общим правилам:(+ 1 2 3 4) = 1039Л.В. ГородняяОсновы функционального программирования(LABEL НОД(LAMBDA (x y)(COND((< x y) (НОД y x))((= (остаток y x ) 0 ) x )(T (НОД (остаток y x) x ))) ) )Пример 2.6.
Алгоритм Евклида для нахождения наибольшегообщего делителя двух положительных целых чисел (остаток [x,y] — функция, вычисляющая остаток от деления x на y).Подробное изложение теории функций, определяемых рекурсивнымивыражениями, можно найти у многих математиков, например [19].По мнению Дж. Маккарти, даже математики, включая логиков, термин"функция" используют не вполне аккуратно, применяя его к формуламвида "x + y^2" с уверенностью, что читатель, слушатель или собеседникправильно поймет, о чем идет речь.
Автоматическая обработка данных,символизирующих функции, требует более точного различия междуфункциями и формами их применения. Для этих целей выработанасистема обозначений, известная как "лямбда-исчисление", которуюпредложил Алонсо Черч в работах по исследованию понятия "функция".Соответствующие рассуждения поясняются в книге по Lisp 1.5 [1] напростом примере (неофициальный перевод):"Допустим, F — выражение, представляющее функцию двухцелочисленных переменных.
Необходима возможность приписывать кпредставлению функции ее аргументы так, чтобы однозначно понимать,каким будет результат применения функции. Традиционная форма F [3,4] пригодна для функций, значение которых не зависит от порядкааргументов, например, если речь идет о сумме или произведении чисел:сумма [3, 4] = сумма [4, 3] = 7. Выражение "x + y^2 [3, 4]" неудовлетворяет такому требованию.
Из его записи не ясно, 13 или 19является его значением. Поэтому "x + y^2" лучше называть не функцией,а формой, которую можно превратить в функцию, если дать способточного определения соответствия между переменными, входящими вформу, и аргументами описываемой функции. Именно это ивыполняется с помощью так называемого "лямбда-конструктора".Любую форму E можно превратить в функцию, если объявить перечень40Л.В. ГородняяОсновы функционального программированияее формальных аргументов x1,x2,...,xk в виде лямбда-выражения(LAMBDA (x1 x2 ... xk) E). Аргументы такой функции следуетперечислять в том же порядке, в каком они перечислены в лямбдавыражении. Например, (LAMBDA (x y) (x + y^2) ) — может работать какфункция двух переменных и (LAMBDA (x y) (x + y^2) ) [3, 4] = 3 + 4^2 =19, а (LAMBDA (y x) (x + y^2) ) [3, 4] = 4 + 3^2 = 13.Переменные в лямбда-выражении называются номинальными илисвязанными, потому что их систематическая замена не меняет смыслафункции.
Таким образом, (LAMBDA (z t) (z + t^2) ) — это то же самое,что и (LAMBDA (x y) (x + y^2) ). Возможны выражения, в которых не всепеременные связаны. Например, в функции двух переменных (LAMBDA(z t) (z^N + t^N) ) переменная N не связана. Это так называемая"свободная" переменная.
Ее можно рассматривать как параметр. Еслизначение такого параметра не задано до попытки вычислить функцию,то значение функции должно быть не определено".Соответствие между именем функции и ее определением можно задатьс помощью более удобной специальной псевдо-функцииDEFUN,первый аргумент которой — имя функции, второй — список ееформальных параметров, третий — собственно тело определенияфункции. Формальным результатом DEFUN, как и LABEL, является еепервый аргумент, который также становится объектом другойкатегории, но теперь это имя новой функции, известной во всейдальнейшей программе.(DEFUN третий ; имя новой функции(x); параметры функции(CAR (CDR (CDR x ))) ; тело функции)Пример 2.7.Новая функция "третий" действует почти так же, как и ранееприведенное определение, но теперь можно функцию рассматриватькак глобальную и обращаться к ней в форме.(третий (QUOTE (A B C)) ) ; — применение новой функции41Л.В.
ГородняяОсновы функционального программированияВышеописанные лямбда-обозначения не вполне удобны дляименования рекурсивных функций, хотя это возможно. Названиефункции используется внутри рекурсивных определений, символизируяцелое определение. При определении функции "премьер" удобнееиспользовать специальную функцию DEFUN, связывающую названиефункции и с определяющей формой, и со списком переменных.(DEFUN премьер (x)(COND ((ATOM x) x)(T (премьер (CAR x)) )) )Собственно механизм связывания пока определен не был. ФункцияDEFUN использует лямбда-конструктор, чтобы представление функцииполучалось более естественно и использовалось как единаяконструкция. Фактически LABEL и DEFUN реализуют аналог тождества:премьер = (LAMBDA (x) (COND ((ATOM x) x)(T (премьер (CAR x)) ) ))Роль локального связывания имени и определения функции в Лиспевыполняет специальная функция LABEL. Если EF — определение, а NF— его имя, то (LABEL NF EF) — функция, знающая свое имя NF.
Вформе (DEFUN премьер (x) (COND((ATOM x) x) (T(премьер (CAR x))) )) используется x — связанное имяпеременной, а "премьер" — связанное имя функции, доступноепрограмме.Механизм конструирования определений функций на базе LABEL болеелогичен, чем DEFUN: наличие локального механизма формальнопригодно и для реализации глобальных связей — они просто должныбыть объявлены или расположены раньше всех локальных. Именно таки был формально определен реализационный базис чистого Лиспа дляраскрутки полной Лисп-системы.
Но на практике поначалу удобнеепользоваться функцией DEFUN, отдавая себе отчет в том, что это нечтовроде строительных лесов, помогающих создать более стройное здание.DEFUN совмещает работу LABEL и LAMBDA — сразу, как и вбольшинстве языков программирования, позволяет ввести и названиефункции, и имена ее арументов. Если LABEL строит именованную42Л.В. ГородняяОсновы функционального программированияфункцию для ее рекурсивного применения внутри текущего выражения,то DEFUN запоминает определение имени для вызова функции в любомместе программы.Как и любая форма, любое S-выражение, символьные представленияфункций могут быть значениями аргументов — функциональныеаргументы .Базис элементарного Лиспа образуют пять функций над Sвыражениями, CAR, CDR, CONS, ATOM, EQ, и четыре специальныхфункции, обеспечивающие управление программами и процессами иконструирование функциональных объектов QUOTE, COND, LAMBDA,LABEL.Точные границы применимости построений над таким базисом будутопределены в следующей лекции в форме определения универсальнойфункции EVAL, позволяющей вычислять значения выражений,представленных в виде списков, — правило интерпретации выражений.Формально для перехода к самостоятельным упражнениям нужнанесколько большая определенность по механизмам исполненияпрограмм, представленных S-выражениями:аргументы функций, как правило, вычисляются в порядке ихперечисления;композиции функций выполняются в порядке от самойвнутренней функции наружу до самой внешней;представление функции анализируется до того, как начинаютвычисляться аргументы, т.к.
в случае специальных функцийаргументы можно не вычислять;при вычислении лямбда-выражений связи между именамипеременных и их значениями, а также между именами функций иих определениями, накапливаются в так называемомассоциативном списке, пополняемом при вызове функции иосвобождаемом при выходе из нее.43Л.В. ГородняяОсновы функционального программированияУниверсальная функцияИзучается техника использования параметров и функций приорганизации обычных вычислений как альтернатива стандартнойпрограммотехнике, основанной на изменениях состояний памяти.Рассматриваются методы управления эффективностью и порядкомвычислений, организованных как применение функций к заданнымаргументам.
Оценивается сложность формирования результата взависимости от параметризации форм, задающих вычисления. Строитсяпростейшее определение универсальной функции, задающей границывычисления представленных списками определенных форм над Свыражениями.Общий подход к обработке символьных выражений ипредставлению программПриведенные ранее описания и правила записи функций и выраженийв этой лекции получат более строгое определение. Начнем ссинтаксического обобщения.
Представим результаты предыдущейлекции в виде простых БНФ (Формул Бекуса-Наура), позволяющихзадать грамматику представления функций и значений в виде системыправил. Каждое правило отдельному понятию сопоставляет ( : : = )варианты ( | ) его изображения:Синтаксис данных в Лиспе сводится к правилам представления атомови S-выражений, включая списки.атом ::= БУКВА конец_атомаЭто правило констатирует, что атомы начинаются с буквы.конец_атома ::= пусто| БУКВА конец_атома| цифра конец_атомаЭто правило констатирует, что после первой литеры в изображенииатома могут быть как буквы, так и цифры.В Лиспе атомы — это мельчайшие частицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
