.цв
23. ПРИМЕРЫ ПРИМЕНЕНИЯ LISP.
.ов
23.1 Введение.
Следующие одиннадцать разделов демонстрируют работу LISP на значительном количестве определений функций LISP. Образцы приведенных программ достаточно коротки - они занимают всего одну-две страницы даже при использовании "красивой печати". Данные примеры показывают не только разнообразие применений компактных фрагментов LISP, но и способность их служить ценным дополнением к среде программирования (например, редактор LISP, представленный в главе 23.8). Большинство этих примеров должны, однако, рассматриваться как демонстрация определенных идей с неполной реализацией. Так, например, игры должны быть существенно дополнены и усовершенствованы, прежде чем их можно будет действительно использовать.
Несмотря на то, что примеры, представленны как отдельные программы, многие из них могут рассматриваться как составные блоки для создания более объемных программ LISP. Например, прогрмма синтаксического анализа и программа блока вычислений могут работать совместно как калькулятор, принимающий обычные входные данные. Аналогично, программа "красивой печати" может быть использована с расширенным редактором, а программы графики - с игровыми программами и т.д.
Каждый из приведенных примеров, поэтому, следует рассматривать не как строго завершенную структуру, а как скелетный материал для создания новых программ LISP. Соответственно, недостатки этих программ следует считать побудительными причинами для создания новых усовершенствованных модулей. Таким образом, с помощью этих примеров вы получтие достаточно полную библиотеку полезных средств LISP.
23.2 Обработка арифметических выражений.
LISP, очевидно, может использоваться непосредственно как калькулятор. Обычный цикл чтение-EVAL-печать обрабатывает выражение типа
(PLUS (TIMES 2 3) 7)
без использования каких-либо программных средств. В данном разделе рассматривается нетрадиционный подход к обработке арифметических выражений. В рассматриваемый примере приводятся выражения, представленные в обычном LISP, за тем исключением, что они содержат операторы, представленные символами +, - и * вместо соответствующих идентификаторов LISP PLUS, DIFFERENCE и TIMES. При этом необходимо обращение к функции EVALUATE, например можно вычислять произвольные арифметические выражения типа:
(EVALUATE '(+ (* 2 3) 7))
Обычно часто употребляется такой путь написания функций LISP, при котором проверяются тривиальные случаи, а более сложные - передаются функциям, определяющимся позже. Приведем простейший пример такой обработки, где выражение является просто числом:
(DEFUN EVALUATE (EXPRESSION) (COND
((NUMBER EXPRESSION) EXPRESSION)
(T (EVALUATE-COMPOUND-EXPRESSION
(OPERATOR-PART EXPRESSION)
(ARG-1-PART EXPRESSION)
(ARG-2-PART EXPRESSION)))))
Это определение требует функции, которая еще не определена, для выделения оператора и каждого из двух операндов из выражения. Эта функция в дальнейшем должна обрабатывать сложное выражение. Несмотря на то, что эти функции еще не существуют, EVALUATE может быть проверена при работе с аргументами типа:
(EVALUATE '3)
Она сделает заключение, что 3 является числом и возвратит его без изменения. Если на этой стадии EVALUATE вызывается со сложным аргументом, LISP выдаст сообщение об ошибке, вызванной отсутствием определения одной из текущих функций. Для простоты в данной программе подразумевается, что все операторы имеют точно два аргумента. Достаточно просто выделить требуемую часть для выражений, представленных списками LISP:
(DEFUN OPERATOR-PART (EXPRESSION)
(CAR EXPRESSION))
(DEFUN ARG-1-PART (EXPRESSION)
(CADR EXPRESSION))
(DEFUN ARG-2-PART (EXPRESSION)
(CADDR EXPRESSION))
Эти части могут быть сразу же проверены, например с помощью:
(ARG-1-PART '(+ (* 3 4) 7))
Заметьте, что функция, которая должна обрабатывать сложные выражения, еще не определена. Необходимо проделать две операции: нужно определить, какая арифметическая операция выполняется в настоящее время и затем проделать ее. LISP позволяет достаточно просто разделить эти шаги с помощью функции, содержащей некоторые еще не определенные операторы:
(DEFUN EVALUATE-COMPOUND-EXPRESSION
(OPERATOR ARG1 ARG2)
(PERFORM-ARITHMETIC
OPERATOR
(EVALUATE ARG1)
(EVALUATE ARG2)))
PERFORM-ARITHMETIC тогда должна получить оператор, т.е. один из атомов +, - или * в качестве своего первого аргумента, а числа- в качестве второго и третьго аргументов.
Для данного определения требуется завершающая функция блока вычислений, которая будет проверять первый аргумент, чтобы выяснить, какую опреацию необходимо произвести и затем используется стандартная встроенная арифметическая функция LISP для выполнения работы следующим образом:
(DEFUN PERFORM-ARITHMETIC (OPERATOR ARG1 ARG2)
(COND
((EQ OPERATOR '+) (PLUS ARG1 ARG2))
((EQ OPERATOR '-) (DIFFERENCE ARG1 ARG2))
((EQ OPERATOR '*) (TIMES ARG1 ARG2))
(T (ERROR (LIST OPERATOR 'UNKNOWN)))))
Определение, представленное здесь, работает только с тремя операторами, но будет несложно расширить его для того, чтобы оно работало для большего числа операторов. Если на месте, где должен находится оператор, функция обнаружит неизвестный символ, то будет выдано сообщение, используя функцию ERROR.
Если необходимо произвести последовательность арифметических операций, то нет необходимости записывать все определения, а можно использовать оператор LISP LOOP.
(LOOP
(PRINT (EVALUATE (READ))) )
Этот оператор позволяет считать выражения, найти их значения, используя функцию EVALUATE и напечатать результат, используя функцию PRINT. Из цикла можно выйти только или поставив ошибочную запись либо нажав клавишу РЕД либо ввести недопустимое выражение (например слово вместо числа). В каждом из этих случаев LISP отреагирует печатью неправильной обратной трассировки. При желании пользователь может изобрести для себя такой программный ход, при котором можно выйти из цикла, скажем, после введения слова QUIT вместо выражения.
По сути, блок вычислений, приведенный здесь, выглядит довольно искусственно - три строки программы LISP:
(DEFUN + (A B) (PLUS A B)) (DEFUN - (A B) (DIFFERENCE A B)) (DEFUN * (A B) (TIMES A B))
должны были бы расширить язык LISP таким образом, чтобы префиксальная форма арифметических выражений, рассмотренная выше, могла бы обрабатываться непосредственно средствами LISP. Обычно тщательный выбор структуры данных позволяет средствами LISP решать задачи, для которых на первый взгляд необходимо создавать специальные новые структуры. Аналогия между поведением EVALUATE и самим языком LISP может быть достигнута с помощью такого расширения EVALUATE, при котором она может работать с тестами типа "=" и ">", с условными выражениями, которые могут представляться с помощью списков как например
(IF условное выражение-если оно истинно-если оно ложно)
и простыми переменными. Все эти расширения являются достаточно простыми, несмотря на то, что обрботка переменных и функций, определяемых пользователем, требуют тщательности. Результат этого расширения быстро становится интерпретатором для нового языка, подобного LISP - по этой причине, если имена и структуры были выбраны правильно, оно может стать новой версией LISP, созданной при помощи самого языка LISP.
23.3 Сортировка.
Программа сортировки, приведенная здесь, рассматривает список атомов и печатает его в алфавитном порядке. Простым использованием этой программы может служить пример:
(SORT (OBLIST))
В данном примере получается упорядоченный список функций LISP. Эта программа может быть также использована применительно к спискам слов, служащих индексами, к заголовкам в каталогах записи (с небольшими изменениями, отражающими сортировку, основанную не на сравнении по алфавиту, а по номеру), а также к счету в компьютерных играх.
Метод, использующийся при сортировке, называется поиском по древовидной структуре ('tree sort'). Этот метод весьма удобен для организации LISP, и также является эффективным для упорядочивания изначально хаотичных списков. Некоторые другие известные методы сортировки работают быстрее, если элементы списка, подлежащие сортировке, расположены изначально почти в верном порядке. Работа древовидной сортировки происходит в два этапа. На первом этапе происходит относительное упорядочивание элементов, при этом организуется такая структура, к которой может быть быстро добавлен новый элемент. На втором этапе происходит преобразование этой структуры, в результате поиска печатаются элементы в новом порядке. Промежуточная структура называется деревом, оно состоит из ряда узлов. Каждый узел дерева характеризуется тремя параметрами: одним из элементов, подлежащим сортировке и парой поддеревьев, известных как левое и правое поддерево. Узел, имеющий пустые правое и левое поддеревья, называется листком. Большинство программ, производящих сортировку, не нуждаются в детальном рассмотрении конкретных комбинаций ячеек LISP, предназначенных для создания узлов дерева - рассмотрения этих деталей можно избежать определением древовидных функций типа:
(DEFUN MAKE-NODE (VAL LEFT RIGHT)
(LIST LEFT VAL RIGHT))
(DEFUN LEFT-SBTREE (TREE)
(CAR TREE))
(DEFUN RIGHT-SUBTREE (TREE)
(CADDR TREE))
(DEFUN ITEM-IN-NODE (TREE)
(CADR TREE))
Данные определения соответствуют тому рассмотрению, что узлы хранятся как показано на рис.
Если поддерево не рассматривается, то соответствующее поле может быть заполнено нулем.
Основная идея употреления деревьев заключается в том, что оно может быть организовано таким образом, что все слова, хранящиеся в левом поддереве, следуют валфавитном порядке перед словом, отражающем название узла, а все остальные из правого поддерева идут после него.
Согласно представлению, данному выше, когда дерево печатается в языке LISP, слова, содержащиеся в нем, появляются в алфавитном порядке. Однако, в этом выводе будет также очень много скобок. Список элементов дерева может быть изображен следующим образом:
(DEFUN PRINT-TREE (TREE) (COND
((NULL TREE) NIL)
(T (PRINT-TREE (LEFT-SUBTREE TREE))
(PRINT (ITEM-IN-NODE TREE))
(PRINT-TREE (RIGHT-SUBTREE TREE)))))
Заметим, что сразу становится удобно читать это определение, когда используются длинные имена и функция типа LEFT-SUBTREE, а не CAR. Особенно это очевидно при использовании программы "красивой печати". Теперь можно проверить функцию PRINT-TREE с помощью функции MAKE-NODE, чтобы построить "вручную" некоторое дерево, например:
(PRINT-TREE
(MAKE-NODE 'SOCRATES
(MAKE-NODE 'ARCHIMEDES NIL NIL)
(NIL))
Интересным случаем использования древовидной структуры является случай построения дерева из элементов, подлежащих сортировке.
Гораздо удобнее начать построение дерева с пустого, добавляя по одному элементу. Это приводит к следующему определению функции SORT:
(DEFUN SORT (ITEM-LIST (TREE))
(LOOP
(UNTIL (NULL ITEM-LIST) (PRINT-TREE TREE))
(SETQ TREE (ADD-ITEM (CAR ITEM-LIST) TREE))
(SETQ ITEM-LIST (CDR ITEM-LIST))))
В данном примере функция ADD-ITEM еще не определена, но она должна принять слово и дерево и передать новое дерево, полученное слиянием нового слова со старыми. Слова, встречающися в алфавите раньше, включаются в левую часть дерева, а те, что встречаются позже - в правую часть. Это же происходит в простом случае добавления элемента к пустому дереву:
(DEFUN ADD-ITEM (ITEM TREE) (COND
((NULL TREE) (MAKE-NODE ITEM NIL NIL))
((ORDERP ITEM (ITEM-IN-NODE TREE))
(PUT-IN-LEFT-SUBTREE ITEM TREE ))
(T (PUT-IN-RIGHT-SUBTREE ITEM TREE))))
Помня, что ITEM-IN-NODE обрабатывает слово, хранящееся в верхней части дерева, ADD-ITEM использует тест ORDERP для проверки, принадлежит ли новый элемент левой или правой части дерева. Определение ORDERP, производящей сортировку по алфавиту, показано ниже. Если LESSP использовать вместо ORDERP, функция будет сортировать числа в порядке убывания. GREATERP произведет сортировку в порядке возрастания.
Для завершения программы необходимы определения PUT-IN-LEFT-SUBTREE и PUT-IN-RIGHT-SUBTREE, являющиеся очень простыми:
(DEFUN PUT-IN-LEFT-SUBTREE (ITEM TREE)
(MAKE-NODE
(ITEM-IN-NODE TREE)
(ADD-ITEM ITEM (LEFT-SUBTREE TREE))
(RIGHT-SUBTREE TREE)))
.сс
[an error occurred while processing this directive]