WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 9 |

Выполнено достаточно строгое построение совершенно формальной математической системы, называемой “Элементарный ЛИСП”.

Составляющие этой формальной системы:

1) Множество символов, называемых S-выражениями.

2) Система функциональных обозначений для основных понятий, трубемых при программировании обрботки S-выражений.

3) Формальное представление функциональных обозначений в виде Sвыражений.

4) Универсальная функция (записанная в виде S-выражения), интерпретирующая обращение произвольной функции, записанной как S-выражение, к ее аргументам.

5) Система базовых функций, обеспечивающих техническую поддержку обработки S-выражений, и специальных функций, обеспечивающих управление вычислениями.

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

Выводы:

- Универсальная функция – это функция, которая может вычислять значение любой формы и представляет собой инетрпретатор в миниатюре.

- При реализации универсальной функции необходимо учитывать способ представления контекста и виды вычисляемых форм.

- Контекст удобно представлять с помощью ассоциативных списков.

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

6. Отображения и функционалы В этом параграфе мы рассмотрим следующие механизмы:

- отображения, - числа и строки, - безымянные определения функций, - фильтры и свертки (редукции).

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

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

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

- что представляет собой отображающая функция;

- как организовано данное, представляющее отображаемое множество;

- каким способом выделяются элементы отображаемого множества.

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

- где размещается множество всех полученных результатов;

- чем отличаются нужные результаты от полученных попутно;

- как строится итоговое данное из отобранных результатов.

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

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

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



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

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

Но во многих случаях знание природы информации дает более четкое понимание особенностей изучаемых механизмов. Программирование работы с числами и строками – привычная, хорошо освоенная область информационной обработки, удобная для оценки преимуществ использования функционалов. Опуская технические подробности, просто отметим, что числа и строки рассматриваются как самоопределимые атомы, смысл которых не требует никакого ассоциирования, он понятен просто по виду записи.

Например, натуральные числа записываются без особенностей и могут быть почти произвольной длины:

- Можно работать с дробными и вещественными числами:

8/12 ;= 2/3.Строки заключаются в обычные двойные кавычки:

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

Это относится и к операциям над числами и строками:

(+ 1 2 3 4 5 6) ;= (- 12 6 3) ;= (/ 3 5) ;= 3/Большинство операций над числами при префиксной записи естественно рассматривать как мультиоперации от произвольного числа аргументов.

(string-equal "строка 1" " строка1") ;= Nil (ATOM "a+b-c") ;= T (char "стр1" 4 ) ;= "1" Со строками можно при необходимости работать посимвольно, хотя они рассматриваются как атомы.

Любой список можно превратить в константу, поставив перед ним "'" апостроф. Это эквивалентно записи со специальной функцией "QUOTE". Для чисел и строк в этом нет необходимости, но это не запрещено ‘1 ;= ‘"abc" ;= "abc" Можно строить композиции функций. Ветвления представлены как результат специальной функции COND, использующей отличие от Nil в качестве значения “истина”. Числа и строки таким образом оказываются допустимыми представлениями значения “истина”.

(cond ((= 1 2) 1) ( 1 2) ) ; = Символ «;» - начало комментария.

Отказ от барьера между представлениями функций и значений дает возможность символьные выражения использовать как для изображения заданных значений, включая любые структуры над числами и строками, так и для определения функций, обрабатывающих любые данные.

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

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

Список - составное данное, первый элемент которого при записи программ выполняет роль функции, применяемой к остальным элементам, также представленным как символьные выражения:

Любой список можно превратить в константу, поставив перед ним "'" апостроф. Это эквивалентно записи со специальной функцией "QUOTE" :

Можно строить композиции функций:

Ветвления представлены как результат специальной функции COND:

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

Функционалы - общее понятие Рассмотрим технику использования функционалов и наметим, как от простых задач перейти к более сложным.

Пример 1. Для каждого числа из заданного списка получить следующее за ним число и все результаты собрать в список.

(defun next (xl) ; Следующие числа:

(cond ; пока список не пуст (xl (cons (1+ (car xl)) ; прибавляем 1 к его голове (next (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список (next '(1 2 5 )) ; = (2 3 6 ) Пример 2. Построить список из "голов" элементов списка (defun 1st (xl) ; "головы" элементов = CAR (cond ; пока список не пуст (xl (cons (caar xl) ; выбираем CAR от его головы (1st (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список (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 как функцию голове XL (map-el fn (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список Примечание: На Clisp это определение выглядит не столь лаконично, оно требует встроенной функции funcall:

Эффект функций 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 (xl) (map-el #'1+ xl )) ; Очередные числа:

(defun 1st (xl) (map-el #'car xl )) ; "головы" элементов = CAR (defun lens (xl) (map-el #'length xl )) ; Длины элементов Параметром функционала может быть любая вспомогательная функция.

Пример 4. Пусть дана вспомогательная функция sqw, возводящая числа в квадрат (defun sqw (x) (* x x)) ; Возведение числа в квадрат (sqw 3) ; = Построить список квадратов чисел, используя функцию sqw:

(defun map-el (fn xl) (cond (xl (cons (funcall fn (car xl) ) ; применяем первый аргумент как функцию ; к первому элементу второго аргумента (map-el fn (cdr xl) ) ) ) ) ) (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 (x) (cons x x)) (tuple 3) ; = (3. 3) (tuple 'a) ; = (a. a) (tuple '(Ха)) ; = ((Ха). (Ха)) = ((Ха) Ха) - это одно и то же! Чтобы преобразовать элементы списка с помощью такой функции, пишем сразу:

(defun duble (xl) (map-el #'tuple xl)) ; дублирование элементов (duble '(1 (a) ())) ; = ((1. 1) ((a) a) (())) Немногим сложнее организовать покомпонентную обработку двух списков.

Пример 6. Построить ассоциативный список, т.е. список пар из имен и соответствующих им значений, по заданным спискам имен и их значений:

(defun pairl (al vl) ; Ассоциативный список (cond ; Пока AL не пуст, (al (cons (cons (car al) (car vl)) ; пары из “голов”.

(pairl (cdr al) (cdr vl)) ; Если VL исчерпается, ; то CDR будет давать NIL ) ) ) ) (pair '(один два two three) '(1 2 два три)) ; = ((один. 1)(два. 2)(two два )(three три )) Пример 7. Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn:

(defun map-comp (fn al vl) ; fn покомпонентно применить ; к соотвественным элементам AL и VL (cond (xl (cons (fn (car al) (car vl)) ; Вызов данного FN как функции (map-comp (cdr al) (cdr vl)) ) ) ) ) Теперь покомпонентные действия над векторами, представленными с помощью списков, полностью в наших руках. Вот списки и сумм, и произведений, и пар, и результатов проверки на совпадение:

(map-comp #'+ '(1 2 3) '(4 6 9)) ; = (5 8 12 ) Суммы (map-comp #'* '(1 2 3) '(4 6 9)) ; = (4 12 27 ) Произведения (map-comp #'cons '(1 2 3) '(4 6 9)) ; = ((1. 4)(2. 6)(3. 9)) Пары (map-comp #'eq '(4 2 3 ) '(4 6 9)) ; = (T NIL NIL ) Сравнения Достаточно уяснить, что надо делать с элементами списка, остальное делает отображающий функционал map-comp.

Пример 8. Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого.

(defun mapf (fl el) (cond ; Пока первый аргумент не пуст, (fl (cons ((car fl) el ) ; применяем очередную функцию ; ко второму аргументу (mapf (cdr fl) el) ; и переходим к остальным функциям, ) ) ) ) ; собирая их результаты в общий список (mapf '(length car cdr) '(a b c d )) ; = (4 a (b c d )) Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов.

Естественно, и серии, и последовательности представляются списками.

Безымянные функции Определения в примерах 4 и 5 не вполне удобны по следующим причинам:

В определениях целевых функций duble и sqwure встречаются имена специально определенных вспомогательных функций.

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

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 9 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.