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

Данные отображены в наборы специально организованных кодов, по которымможно преобразовывать и строить новые коды. Например, по коду команды можно выбратьхранимую в памяти подпрограмму, которая построит новые коды чисел или структурданных. В-третьих, коды из нулей и единиц отображаются в наборы точек, образующиебуквы или рисунки, которые можно вывести на печать или высветить на дисплее. Каждыйтакой шаг достаточно очевиден, но композиции отображений могут обладать весьмасложным поведением.Говорят, что отображение существует, если задана пара множеств и отображающая функция,для которой первое множество - область определения, а второе - область значения.

Приопределении отображений прежде всего должны быть ясны следующие вопросы:- что представляет собой отображающая функция;- как организовано данное, представляющее отображаемое множество;- каким способом выделяются элементы отображаемого множества.Это позволяет задать порядок перебора множества и метод передачи фактическихаргументов для вычисления отображающей функции.

При обходе структуры,представляющей множество, отображающая функция будет применена к каждому элементумножества, следовательно может быть выработана подобная структура множестварезультатов. Возможно, не все полученные результаты нужны, поэтому целесообразнопрояснить заранее еще ряд вопросов:- где размещается множество всех полученных результатов;1- чем отличаются нужные результаты от полученных попутно;- как строится итоговое данное из отобранных результатов.При функциональном стиле программирования ответ на каждый из таких вопросов можетбыть дан в виде отдельной функции, причем роль каждой функции в схеме реализацииотображения достаточно четко фиксирована.Схема реализации отображенияможет быть представлена в виде определения,формальными параметрами которого являются обозначения этих ролей.

Такое определениеназывается "функционал". Более точно, функционал может оперировать функциями вкачестве аргументов или результатов. Чтобы определить конкретное отображение спомощью функционала, надо в качестве фактических параметров задать функции,выполняющие конкретные роли, т.е. дающие ответы на вышеприведенные вопросы. Такиефункции могут быть достаточно общими, универсальными, полезными при определенииразных отображений, - они получают имена для многократного использования в разныхсистемах определений.

Но могут быть и частными, разовыми, нужными лишь в данномконкретном случае – тогда можно обойтись без имен, использовать тело определениянепосредственно в точке вызова функции как значение аргумента.Таким образом, определение отображения может быть декомпозировано на части (функции ифункционалы) разного назначения, типичного для многих схем информационной обработки.Это позволяет упрощать отладку систем определений, повышать коэффициент повторногоиспользования отлаженных функций. Не будет преувеличением утверждение, чтоотображения - эффективный механизм абстрагирования, моделирования, проектирования иформализации крупномасштабной обработки информации.

Возможности отображений винформатике значительно шире, чем освоено практическим программированием, но ихприменение требует дополнительных пояснений, которые и являются целью этой главы.Числа и строкиЛюбую информацию можно представить символьными выражениями.

В качестве основныхвидов символьных выражений выбраны списки и атомы. Атом - неделимое данное,представляющее информацию произвольной природы:Но во многих случаях знание природы информации дает более четкое пониманиеособенностей изучаемых механизмов. Программирование работы с числами и строками –привычная, хорошо освоенная область информационной обработки, удобная для оценкипреимуществ использования функционалов. Опуская технические подробности, простоотметим, что числа и строки рассматриваются как самоопределимые атомы, смысл которыхне требует никакого ассоциирования, он понятен просто по виду записи.Например, натуральные числа записываются без особенностей и могут быть почтипроизвольной длины:1-12398765432100000000000001234567892Можно работать с дробными и вещественными числами:8/123.1415926;= 2/3Строки заключаются в обычные двойные кавычки:"строка любой длины, из произвольных символов, включая все что угодно"Список - составное данное, первый элемент которого может рассматриваться как функция,применяемая к остальным элементам, также представленным как символьные выражения.Это относится и к операциям над числами и строками:(+ 1 2 3 4 5 6)(- 12 6 3)(/ 3 5);= 21;= 3;= 3/5Большинство операций над числами при префиксной записи естественно рассматривать какмультиоперации от произвольного числа аргументов.(string-equal "строка 1" " строка1")(ATOM "a+b-c")(char "стр1" 4 );= Nil;= T;= "1"Со строками можно при необходимости работать посимвольно, хотя они рассматриваютсякак атомы.Любой список можно превратить в константу, поставив перед ним "'" апостроф.

Этоэквивалентно записи со специальной функцией "QUOTE". Для чисел и строк в этом нетнеобходимости, но это не запрещено‘1‘"abc";= 1;= "abc"Можно строить композиции функций. Ветвления представлены как результат специальнойфункции COND, использующей отличие от Nil в качестве значения “истина”. Числа и строкитаким образом оказываются допустимыми представлениями значения “истина”.(cond ((= 1 2) 1)( 12)3);=2Символ «;» - начало комментария.Отказ от барьера между представлениями функций и значений дает возможность символьныевыражения использовать как для изображения заданных значений, включая любые структурынад числами и строками, так и для определения функций, обрабатывающих любые данные.(Напоминаем, что определение функции - данное.)Функционалы - это функции, которые используют в качестве аргументов или результатовдругие функции. При построении функционалов переменные могут выполнять роль именфункций, определения которых находятся во внешних формулах, использующихфункционалы.Сводка ранее пройденногоЛюбую информацию можно представить символьными выражениями.

В качестве основных видов символьныхвыражений выбраны списки и атомы. Атом - неделимое данное, представляющее информацию произвольнойприроды:Список - составное данное, первый элемент которого при записи программ выполняет роль функции,применяемой к остальным элементам, также представленным как символьные выражения:Любой список можно превратить в константу, поставив перед ним "'" апостроф.

Это эквивалентно записи соспециальной функцией "QUOTE" :Можно строить композиции функций:Ветвления представлены как результат специальной функции COND:Отказ от барьера между представлениями функций и значений даетвозможность символьные выражения использовать как для изображения заданных значений, так и дляопределения функций, обрабатывающих любые данные.

(Напоминаем, что определение функции - данное.)Функционалы - это функции, которые используют в качестве аргументов или результатов другие функции. Припостроении функционалов переменные могут выполнять роль имен функций, определения которых находятсяво внешних формулах, использующих функционалы.Функционалы - общее понятиеРассмотрим технику использования функционалов и наметим, как от простыхзадач перейти к более сложным.Пример 1.

Для каждого числа из заданного списка получить следующееза ним число и все результаты собрать в список.(defun next (xl); Следующие числа:(cond; пока список не пуст(xl (cons (1+ (car xl)); прибавляем 1 к его голове(next (cdr xl)); и переходим к остальным,)) )); собирая результаты в список4(next '(1 2 5 )); = (2 3 6 )Пример 2. Построить список из "голов" элементов списка(defun 1st (xl)(cond(xl (cons (caar xl)(1st (cdr xl)))) )); "головы" элементов = CAR; пока список не пуст; выбираем CAR от его головы; и переходим к остальным,; собирая результаты в список(1st '((один два )(one two )(1 2 )) ); = (один one 1)Пример 3.

Выяснить длины элементов списка(defun lens (xl);(cond(xl (cons (length (car xl))(lens (cdr xl)))) ))Длины элементов; Пока список не пуст; вычисляем длину его головы; и переходим к остальным,; собирая результаты в список(lens '((1 2 ) () (a b c d ) (1 (a b c d ) 3 )) ); = (2 0 4 3 )Внешние отличия в записи этих трех функций малосущественны, что позволяетввести более общую функцию map-el, в определении которой имена "car", "1+"и "lenth" могут быть заданы как значения параметра fn:(defun map-el (fn xl) ; Поэлементное преобразование XL; с помощью функции FN(cond; Пока XL не пуст(xl (cons (fn (car xl) ); применяем FN как функцию голове XL1(map-el fn (cdr xl)))))); и переходим к остальным,; собирая результаты в список1Примечание: На Clisp это определение выглядит не столь лаконично, онотребует встроенной функции funcall:5Эффект функций next, 1st и lens можно получить выражениями:(map-el #'1+ xl)(map-el #'car xl); Следующие числа:; "головы" элементов = CAR#’ x ;= (FUNCTION x) - сокращенное обозначение функции-значения(map-el #'length xl); Длины элементов(map-el #'1+'(1 2 5 )); = (2 3 6 )(map-el #'car '((один два )(one two )(1 2 )) ) ; = (один one 1)(map-el #'length '((1 2 ) () (a b c d ) (1 (a b c d ) 3 )) ); = (2 0 4 3 )соответственно.Эти определения функций формально эквивалентны ранее приведенным – онисохраняют отношение между аргументами и результатами.Все три примера можно решить с помощью таких определяющих выражений:(defun next(defun 1stэлементов =(defun lens(xl) (map-el #'1+ xl )); Очередные числа:(xl) (map-el #'car xl )); "головы"CAR(xl) (map-el #'length xl )) ; Длины элементовПараметром функционала может быть любая вспомогательная функция.Пример 4.

Пусть дана вспомогательная функция sqw, возводящая числа в квадрат(defun sqw (x) (* x x))(sqw 3); Возведение числа в квадрат; = 9Построить список квадратов чисел, используя функцию sqw:(defun map-el (fn xl)(cond(xl (cons (funcall fn (car xl) ); применяем первый аргумент как функцию; к первому элементу второго аргумента(map-el fn (cdr xl) )) ) ) )16(defun sqware (xl) ;; Возведение списка чисел в квадрат(cond; Пока аргумент не пуст,(xl (cons (sqw (car xl)); применяем sqw к его голове(sqware (cdr xl)) ; и переходим к остальным,)) )); собирая результаты в список(sqware '(1 2 5 7 )); = (1 4 25 49 )Можно использовать map-el:(defun sqware (xl) (map-el #'sqw xl))Ниже приведено определение функции sqware- без вспомогательной функции,выполняющее умножение непосредственно. Оно влечет двойное вычисление(CAR xl), т.е. такая техника не вполне эффективна:(defun sqware- (xl)(cond(xl (cons (* (car xl) (car xl) ); квадрат головы; вычислять приходится дважды(sqware- (cdr xl)))) ))Пример 5.

Пусть дана вспомогательная функция tuple,превращающая любое данное в пару:(defun(tuple(tuple(tupletuple (x) (cons x x))3); = (3 . 3)'a); = (a . a)'(Ха)); = ((Ха) . (Ха)) = ((Ха) Ха) - это одно и то же!Чтобы преобразовать элементы списка с помощью такой функции, пишем сразу:(defun duble (xl) (map-el #'tuple xl)); дублирование элементов(duble '(1 (a) ())); = ((1 . 1) ((a) a) (()))Немногим сложнее организовать покомпонентную обработку двух списков.Пример 6. Построить ассоциативный список, т.е.