WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 9 |

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

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

Учитывая это, было бы удобнее вспомогательные определения вкладывать непосредственно в определения целевых функций и обходиться при этом вообще без имен. Конструктор функций lambda обеспечивает такой стиль построения определений. Этот конструктор любое выражение expr превращает в функцию с заданным списком аргументов (x1... xK) в форме так называемых lambda-выражений:

( lambda (x1... xK) expr ) Имени такая функций не имеет, поэтому может быть применена лишь непосредственно.

Defun использует этот конструктор, но, кроме того, дает функциям имена.

Пример 9. Определение функций duble и sqwure из примеров 4 и без использования имен и вспомогательных функций:

(defun sqware (xl) (map-el (lambda (x) (* x x)) xl)) (defun duble (xl) (map-el (lambda (x) (cons x x)) xl)) Любую систему взаимосвязанных функций можно преобразовать к одной функции, используя вызовы безымянных функций.

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

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

Пример 10. Декартово произведение хочется получить определением вида:

(defun decart (x y) (map-el #'(lambda (i) (map-el #'(lambda (j) (list i j)) y) ) x) ) Но результат вызова (decart '(a s d) '( e r t)) дает (((A E) (A R) (A T)) ((S E) (S R) (S T)) ((D E) (D R) (D T))) вместо ожидаемого ((A E) (A R) (A T) (S E) (S R) (S T) (D E) (D R) (D T)) Дело в том, что функционал map-el, как и map-comp (пример 7), собирает результаты отображающей функции в общий список с помощью операции cons так, что каждый результат функции образует отдельный элемент.

А по смыслу задачи требуется, чтобы список был одноуровневым.

Посмотрим, что получится, если вместо cons при сборе результатов воспользоваться функцией append.

Пример 11. Пусть дан список списков. Нужно их все сцепить в один общий список.

(defun list-ap (ll) (cond (ll (append (car ll) (list-ap (cdr ll) ) ) ) ) ) (list-ap '((1 2)(3 (4)))) ; = (1 2 3 (4)) Тогда по аналогии можно построить определение фукнционала map-ap:

(defun map-ap (fn ll) (cond (ll (append (fn (car ll) ) (map-ap fn (cdr ll) ) ) ) ) ) (map-ap 'cdr '((1 2 3 4) (2 4 6 8) ( 3 6 9 12))) ; = (2 3 4 4 6 8 6 9 12) Следовательно, интересующая нас форма результата может быть получена:

(defun decart (x y) (map-ap #'(lambda (i) (map-el #'(lambda (j) (list i j)) y) ) x) ) (decart '(a s d) '( e r t)) ; = ((A E) (A R) (A T) (S E) (S R) (S T) (D E) (D R) (D T)) Соединение результатов отображения с помощью append обладает еще одним полезным свойством: при таком сцеплении исчезают вхождения пустых списков в результат. А в Лиспе пустой список используется как ложное значение, следовательно такая схема отображения пригодна для организации фильтров. Фильтр отличается от обычного отображения тем, что окончательно собирает не все результаты, а лишь удовлетворяющие заданному предикату.

Пример 12. Построить список голов непустых списков можно следующим образом:

(defun heads (xl) (map-ap #'(lambda (x)(cond (x (cons (car x) NIL)))) ; временно голова размещается в список, ; чтобы потом списки сцепить xl ) ) (heads '((1 2) () (3 4) () (5 6)) ) ; = (1 3 5) Рассмотрим еще один типичный вариант применения функционалов. Представим, что нас интересуют некие интегральные характеристики результатов, полученных при отображении, например, сумма полученных чисел, наименьшее или наибольшее из них и т.п. В таком случае говорят о свертке результата или его редукции. Редукция заключается в сведении множества элементов к одному элементу, в вычислении которого задействованы все элементы множества.

Пример 13. Подсчитать сумму элементов заданного списка.

(defun sum-el ( xl) (cond ((null xl) 0) (xl (+ (car xl) (sum-el (cdr xl) ) ) ) ) ) (sum-el '(1 2 3 4 ) ) ; = Перестроим определение, чтобы вместо "+" можно было использовать произвольную бинарную функцию:

(defun red-el (fn xl) (cond ((null xl) 0) (xl (fn (car xl) (red-el fn (cdr xl) ) )))) (red-el '+ '(1 2 3 4 ) ) ; = В какой-то мере map-ap ведет себя как свертка - она сцепляет результаты без сохранения границ между ними.

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

Выводы:

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

- Функционалы обеспечивают гибкость отображений.

- Определение функции может совсем не зависить от конкретных имен.

- С помощью функционалов можно управлять выбором формы результатов.

- Параметром функционала может быть любая функция, преобразующая элементы структуры.

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

- Встроенные в Clisp функционалы приспособлены к покомпонентной обработке произвольного числа параметров.

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



7. Имена и контексты - Определения функций. Псевдо-функции.

- Именование значений и подвыражений - Переменные и константы.

- Функции и данные.

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

Задача: Пусть множества представлены с помощью списков. Для начала рассмотрим простые множества, элементами которых могут быть только атомы. Надо реализовать объединение (UNION) и пересечение (INTERSECTION) множеств.

Предварительный анализ задачи:

Функции UNION и INTERSECTION применяют к множествам, каждое множество представлено в виде списка атомов. Заметим, что обе функции рекурсивны и используют вспомогательную функцию, выясняющую входит ли атом в список (MEMBER).

Работу этих функций можно выразить следующим образом:

MEMBER – это функция двух аргументов, первый аргумент “А” - атом, а второй аргумент – список “Х”. Функция вырабатывает значение “Т”, если “А” входит в список “Х”.

Алгоритм:

Определение тела функции состоит из трех ветвей:

- Если второй аргумент – пустой список, то значение функции Nil, т.е. атом в списке не найден.

- Иначе если атом “А” совпадает с “головой” второго аргумента, то значение функции T, т.е. атом имеется в списке.

- Иначе продолжаем поиск в “хвосте” списке, т.е. рекурсивно применяем исходную функцию к редуцированному второму аргументу.

алг member ( атом a, список x) арг a, x нач если пусто (a) то знач := Nil инес равно (a, голова (x) ) то знач := T иначе знач := member (a, хвост (x)) кон UNION – это функция двух аргументов, оба аргумента “X” и “Y” - списки, представляющие множества. Функция вырабатывает новый список, в который входят все атомы из списков “Х” и “Y”.

Алгоритм:

Определение тела функции состоит из трех ветвей:

- Если первый аргумент – пустой список, то значением является второй аргумент, т.е. можно ничего не строить.

- Иначе если “голова” первого аргумента входит во второй аргумент, то достаточно объединить хвост первого аргумента со вторым аргументом, т.е.

рекурсивно применяем исходную функцию, редуцируя первый аргумент.

- Иначе “голову” первого аргумента присоединяем к результату объединения редуцированного первого аргумента со вторым аргументом.

алг UNION (список x,y) арг x, y нач если пусто (x) то знач := y инес member ( голова (x), y ) то знач := UNION (хвост (x), y) иначе знач := cons (голова (x), UNION (хвост (x), y)) кон INTERSECTION – это функция двух аргументов, оба аргумента “X” и “Y” - списки, представляющие множества. Функция вырабатывает новый список, в который входят атомы списка “Х”, входящие в список “Y”.

Алгоритм:

Определение тела функции состоит из трех ветвей:

- Если первый аргумент – пустой список, то и пересечение - пустой список.

- Иначе если “голова” первого аргумента входит во второй аргумент, то “голову” первого аргумента присоединяем к результату пересечения редуцированного первого аргумента со вторым аргументом.

- Иначе применяем пересечение к редуцированному первому аргументу со вторым аргументом.

алг INTERSECTION (список x,y) арг x, y нач если пусто (x) то знач := Nil инес member ( голова (x), y ) то знач := cons (голова (x), INTERSECTION (хвост (x), y)) иначе знач := INTERSECTION (хвост (x), y) кон Определяя эти функции на Лиспе, мы используем специальную псевдо-функцию DEFUN. Программа выглядит так:

(DEFUN MEMBER (A X) ;определение проверки входит ли атом в список (COND ((NULL X) Nil) ((EQ A (CAR X)) T) (T (MEMBER A (CDR X)) ) ) ) (DEFUN UNION (X Y) ;определение объединения двух множеств (COND ((NULL X) Y) ((MEMBER (CAR X) Y) (UNION (CDR X) Y) ) (T (CONS (CAR X) (UNION (CDR X) Y))) )) ) )) (DEFUN INTERSECTION (X Y) ;определение пересечения двух множеств (COND ((NULL X) NIL) ((MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECTION (CDR X) Y)) ) (T (INTERSECTION (CDR X) Y)) )) (INTERSECTION '(A1 A2 A3) '(Al A3 A5)) ;тест на пересечение двух множеств (UNION '(X Y Z) '(U V W X)) ;тест на объединение двух множеств Эта программа предлагает Лисп-системе вычислить пять различных форм. Первые три формы сводятся к применению псевдо-функции DEFUN. Значение четвертой формы - (AA3). Значение пятой формы - (Y Z C B D X). Анализ пути, по которому выполняется рекурсия, показывает, почему элементы множества появляются именно в таком порядке.

Псевдо-функция - это функция, которая выполняется ради ее воздействия на систему, тогда как обычная функция - ради ее значения. DEFUN заставляет функции стать определенными и допустимыми в системе равноправно со встроенными функциями. Ее значение - имя определяемой функции, в данном случае - MEMBER, UNION, INTERSECTION. Можно сказать более точно, что полная область значения псевдо-функции DEFUN включает в себя некоторые доступные ей части системы, обеспечивающие хранение информации о функциональных объектах, а формальное ее значение – атом, символизирующий определение функции.

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





1) Программа состоит из последовательности вычисляемых форм. Если форма список, то ее первый элемент интерпретируется как функция. Остальные элементы списка – аргументы для этой функции. Они вычисляются с помощью EVAL, а функция применяется к ним с помощью APPLY и полученное значение выводится как результат программы.

2) Нет особого формата для записи программ. Границы строк игнорируются. Формат программы, включая идентификацию, выбран просто для удобства чтения.

3) Любое число пробелов и концов строк можно разместить в любой точке программы, но не внутри атома.

4) Не используются (QUOTE T), (QUOTE NIL). Вместо них используется T, NIL, что влечет соответствующее изменение определения EVAL.

5) Атомы должны начинаться с букв, чтобы легко отличаться от чисел.

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

7) Точечные пары могут появляться как элементы списка, и списки могут быть элементами точечных пар.

Например:

((A. B) X (C. (E F D))) - есть допустимое S-выражение.

Оно может быть записано как ((A. B). ( X. ((C. (E. ( F. (D. Nil))) ). Nil))) или ((A. B) X (C E F D)) 8) Форма типа (A B C. D) есть сокращение для (A. ( B. ( C. D) )). Любая другая расстановка запятых или точек на одном уровне есть ошибка, например, (A. B C) или (A B. C D) не соответствуют никакой структуре данных. (Реализационное расширение списочной записи. “. D” здесь означает, что вместо Nil, по умолчанию завершающего список, в данной структуре размещен атом “D”) 9) Набор основных функций обеспечен системой. Другие функции могут быть введены программистом. Любая функция может использоваться в определении другой функции с учетом иерархии построений.

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

Пример:

(LOAD 'TEST.LSP) При наборе форм в диалоге интерпретатор сам напечатает результаты, а при загрузке программы их файла надо позаботиться о выводе результатов программы с помощью псевдофункции PRINT.

Пример:

(PRINT (INTERSECTION '(A1 A2 A3) '(Al A3 A5)) ) (PRINT (UNION '(X Y Z) '(U V W X)) ) (PRINT (UNION (READ) '(1 2 3 4)) ) ; объединение вводимого списка со списком '(1 2 3 4) Именование значений и подвыражений Переменная - это символ, который используется для представления аргумента функции.

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

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

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

Проиллюстрируем это рассуждение на примере. Предположим, интерпретатор получает следующее S-выражение:

((LAMBDA (X Y) (CONS X Y)) 'A 'B) Функция:

(LAMBDA (X Y) (CONS X Y)) Аргументы: (A B) EVAL передает эти аргументы функции APPLY. (См. 6).

(apply #’(LAMBDA (X Y) (CONS X Y)) ‘(A B) Nil ) APPLY свяжет переменные и передаст функцию и удлинненный а-список EVAL для вычисления.

(eval ‘(CONS X Y) ‘ ((X. A) (Y B) Nil)) EVAL вычисляет переменные и сразу передает их функции CONS, строящий из них бинарный узел.

(Cons ‘A ’B) = (A. B) Можно добиться большей прозрачности сложных определений функций, используя иерархию контекстов и средства именования выражений. Специальная функция Let сопоставляет локальным переменным независимые выражения. С ее помощью можно вынести из сложного определения любые совпадающие подвыражения.

Пример:

(defun UNION- (x y) (let ( (a-x (CAR x)) (d-x (CDR x)) ) (COND ((NULL x) y) ((MEMBER a-x y) (UNION d-x y) ) (T (CONS a-x (UNION d-x y)) ) ) )) Обычно переменная считается связанной в области действия лямбда-конструктора функции, который связывает переменную внутри тела определения функции методом размещения пары из имени и значения в начале ассоциативного списка (а-списка). В том случае, когда переменная всегда имеет определенное значение независимо от текущего состояния а-списка, она будет называться константой. Такую неизменяемую связь можно установить, размещая пару (a. v) в конец a-списка. Но в реальных системах это организовано с помощью так называемого списка свойств атома, являющегося представлением переменной. Каждый атом имеет свой список свойств (property list - р-список), доступный через хэш-таблицу идентификаторов, что работает эффективнее, чем a-список. С каждым атомом связана специальная структура данных, в которой размещается имя атома, его значение, определение функции, представляемой этим же атомом, и список произвольных свойств, помеченных индикаторами. При вычислении переменных EVAL исследует эту структуру до поиска в асписке. Такое устройство констант не позволяет им служить переменными в а-списке.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 9 |










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

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