(DEFUN PUT-IN-RIGHT-SUBTREE (ITEM TREE)
(MAKE-NODE
(ITEM-IN-NODE TREE)
(LEFT-SUBTREE)
(ADD-ITEM ITEM (RIGHT-SUBTREE TREE))))
Каждый из них создает копии узла дерева, минуя элемент, который был добавлен к релевантному поддереву. Теперь, когда определена готовая функция ORDERP или когда она была заменена другим предикатом, можно осуществить тест всей программы сортировки. Около десятка или несколько десятков чисел пройдут сортировку с небольшой задержкой пока объектный список не будет размещен в алфавитном порядке и не будет произведено сбора ненужных данных. При использовании функций CAR, CADR и CADDR вместо ITEM-IN-MODE и т.д., и записи определения функции PUT-IN-LEFT-SUBTREE в месте ее вызова, и возможно даже при использовании более коротких имен переменных и функций, значительно сэкономились бы время и память при создании программ, приведенных выше. Даже на микрокомпьютере огромные потери чистоты результата обычно превышают сбережения ресурсов (экономию средств).
В языке LISP нет встроенной функции, обеспечивающей упорядочивание слов по алфавиту. Однако, существует функция EXPLODE, которая рзбивает слово на составляющие буквы, а другая функция ORDINAL переводит любую букву в цифровой код. Таким образом можно использовать следующее определение ORDERP:
(DEFUN ORDERP (A B)
(ORDERP1 (EXPLODE A) (EXPLODE B)))
(DEFUN ORDERP1 (AL BL) (COND
((NULL AL) T)
((NULL BL) NIL)
(EQ (CAR AL) (CAR BL))
(ORDERP1 (CDR AL) (CDR BL)))
(T (LESSP (ORDINAL (CAR AL))
(ORDINAL (CAR BL))))))
Функция ORDERP просто раскладывает два своих аргумента на два списка символов и передает результат функции ORDERP1.
При упорядочивании в алфавитном порядке функция ORDERP1 размещает сначала короткие, а затем длинные слова, начинающиеся с одинаковых букв. Она также разбирается со списками, имеющими идентичные начальные строки символов. Когда функция находит различия в данных двух входных списках, она переводит буквы в числа, используя ORDINAL, а затем сравнивает их с помощью LESSP. Т.о., созданная сортировка зависит от последовательности сгенерированных функцией ORDINAL кодов; по крайней мере, для букв - это то же упорядочивание по алфавиту.
23.4 Произвольная точность арифметики.
Существует точка зрения, что при выполнении основных вычислений функции LISP PLUS, TIMES и т.д. работают с числами и любые ограничения в количестве цифр во встречающихся числах были бы нежелательной уступкой ограничениям возможностей компьютера. Поэтому, была разработана такая арифметика, единственным ограничением которой стало время получения результатов. В языке LISP обычная арифметика имеет дело только с 16-разрядными (битовыми) числами, т.е. числами в интервале от -32768 до 32767. Функция, разработанная здесь, показывает, как можно достичь арифметики без ограничений с помощью уже существующих в данной версии LISP средств. Чтобы продемонстрировать это, рассмотрим большие возможности двух функций. В этой программе большие числа будут представлены в виде списковых структур, содержащих малые числа. Возможно, более очевидным представлением этого будет хранение больших чисел в виде списков цифр, так миллион можно хранить в виде списка (1 0 0 0 0 0 0). Эта схема отличается от простого представления по трем причинам:
(а) Малые числа, которые расцениваются как цифры длинной арифметической программы, находятся в интервале от 0 до 99, а не от 0 до 9. Такая группировка удваивает скорость вычислений и не представляет никаких трудностей с точки зрения создания алгоритмов.
(б) Последние значащие цифры чисел хранятся в начале списка больших чисел, т.к. это упрощает выполнение операций 'выполнить и занять'.
(в) Числа в интервале от 0 до 99 представлены списковой структурой без каких-либо ограничений. Это незначительно экономит память, но значительно избавляет от недоразумений. Числа до 9999 будут занимать одну ячейку CONS, например число 1789 будет хранится как (89 . 17), а больше 9999 - как аналогичные структуры с точкой. Так, запись числа 1000000 заканчивается как список (000 . 1).
С точки зрения использования при отладке рассмотрим следующие функции; первой функцией записывается та функция, которая печатает большие числа в обычном виде:
(DEFUN BIG-PRINT (N) (COND
((NUMBERP N) (PRINC N))
(T (BIG-PRINT (CDR N))
(PRINT-TWO-DIGITS (CAR N)) )))
(DEFUN PRINT-TWO-DIGITS (N)
(PRINC (QUOTIENT N 10))
(PRINC (REMAINDER N 10)))
Функция PRINT-TWO-DIGITS необходима, чтобы убедиться, что каждое число сруктуры данных печатается как два символа. При вызове функцией BIG-PRINT функции PRINC для изображения на экране этих чисел могут быть утеряны некоторые нули из истинного выражения.
Следующей рассмотрим функцию сложения больших чисел. Как и все обычные функции LISP, эта функция начинает проверку с простых случаев, т.е. тех, при которых входные данные функции не являются числами повышенной точности:
(DEFUN BIG-PLUS (A B)
(COND
((NUMBERP A) (SMALL-PLUS-BIG A B))
((NUMBERP B) (SMALL-PLUS-BIG B A))
(T (JOIN-DIGIT
(PLUS (CAR A ) (CAR B))
(BIG-PLUS (CDR A) (CDR B))))))
Функция BIG-NUMBER будет использоваться для перевода основного числа в LISP В число с большим представлением, SMALL-PLUS-BIG - для сложения большого и малого чисел и JOIN-DIGIT располагает цифру впереди большого числа, выполняя при этом все необходимые переносы. Итак, учитывая все сказанное, можно записать:
(DEFUN BIG-NUMBER (N)
(COND
((LESSP N 100) N)
(T (CONS
(REMAINDER N 100)
(BIG-NUMBER (QUOTIENT N 100))))))
(DEFUN SMALL-PLUS-BIG (A B)
(COND
(NUMBERP B) (BIG-NUMBER (PLUS A B)))
(T (JOIN-DIGIT
(PLUS A (CAR B))
(CDR B)))))
Заметим, что функция SMALL-PLUS-BIG составлена так, что может работать со вторым аргументом, который является малым числом. Радует тот факт, чт ее можно записать, используя функцию JOIN-DIGIT, которая нужна, чтобы записать функцию BIG-PLUS. Саму функцию JOIN-DIGIT, оказывается, легко можно определить с помощью уже созданных функций:
(DEFUN JOIN-DIGIT (N A)
(COND
((LESSP N 100) (CONS N A))
(T (CONS
(REMAINDER N 100)
(SMALL-PLUS-BIG (QUOTIENT N 100) A)))))
Если нет переноса, то функция JOIN-DIGIT ведет себя как CONS. В противном случае она осуществляет перенос.
Это завершает определения, связанные со сложением больших чисел. Умножение выполняется аналогично: первым рассматривается случай, когда один из аргументов - малое число. Обратите внимание, что в этой программе малые числа принадлежат интервалу (0, 99) и поэтому, чтобы получить результат двух цифр, можно использовать обычную функцию LISP TIMES. Если бы мы попытались сгруппировать цифры, например по четыре в структуре, то это был бы уже другой случай.
(DEFUN BIG-TIMES (A B)
(COND
((NUMBERP A) (SMALL-TIMES-BIG A B))
((NUMBERP B) (SMALL-TIMES-BIG B A))
(T...)))
Последнее предложение записыывается после того, как записана функция SMALL-TIMES-BIG.
(DEFUN SMALL-TIMES-BIG (A B)
(COND
((NUMBERP B) (BIG-NUMBER (TIMES A B)))
(T (JOIN-DIGIT
(TIMES A (CAR B))
(SMALL-TIMES-BIG A (CDR))))))
Как и функция SMALL-PLUS-BIG эта функция начинает работу с теста: является ли второй аргумент большим числом как это должно. Если нет, то результат может быть получен обычной функцией LISP - TIMES, И функция BIG-NUMBER переводит его в стандартный вид большого числа. В противном случае,ведущая цифра результата получается путем умножения ведущей цифры B на A, и результат помещается впереди результата умножения более высокого порядка B на A. Полное определение функции BIG-TIMES может быть получено после завершения последнего предложения, включив код, который проделывает аналогичные действия с целыми аргументами A и B:
(BIG-PLUS
(SMALL-TIMES-BIG (CAR B) A)
(CONS O (BIG-TIMES A (CDR B))))
Здесь форма записи (CONS O X) используется для выстраивания в ряд цифр в ответ на сложение. Все функции в этой программе определены одна через другую, и обращение к любой из них может задействовать почти всю программу. Тест проходит легко, т.к. большинство функций ведут себя очень просто при условии, что они имеют небольшие аргументы, а эти основные шаги программы можно проверить в первую очередь. Для вывода результата на экран в удобном для чтения виде используется функция BIG-PRINT.
(DEFUN BIG-POWER-OF-2 (N)
(PRINT (LIST 2 'TO 'THE 'POWER N 'IS))
(BIG-PRINT (BIG-EXPT 2 N))
'DONE)
Результат, полученный функцией BIG-POWER-OF-2 выводится на экран с помощью функции BIG-PRINT: он не содержит значения, которое можно передать обратно для печати обычному оператору вычисления LISP. Как показано выше, слово DONE (готово) перемещено назад, так, чтобы по крайней мере, предикат был показан. Функция BIG-EXPT увеличивает число до множества. Она выполняет повторно возведение в квадрат аргумента, - и это значительно увеличивает скорость, - чем выполнение простого умножения N раз.
(DEFUN BIG-EXPT (A N)
(COND
((EQUAL N 0) 1)
(T (SUBFUNCTION-FOR-BIG-EXPT A
(BIG-EXPT A (QUOTIENT N 2))
(REMAINDER N 2)))))
(DEFUN SUBFUNCTION-FOR-BIG-EXPT (A APOWER NREM)
(COND
((EQUAL NREM 0) (BIG-TIMES APOWER APOWER))
(T (BIG-TIMES
(BIG-TIMES A APOWER)
APOWER))))
23.5 Программа"красивой печати"
Если функция LISP - PRINT используется для вывода на экран большой части структуры LISP, например, определение функции, результат нелегко прочитать. Несмотря на то, что скобки в LISP делают структуру выражения однозначной, неформатный вывод не помогает читателю подобрать скобки и разобраться в структуре. Программа красивой печати - это программа, которую можно использовать вместо PRINT и которая распределяет вывод на несколько строк, используя абзац для представления в более удобночитаемом виде. Программа предварительной печати, использованная здесь, располагает двумя способами вывода списков. Для совсем коротких списков, которые занимают одну строку, используется обычный формат вывода (а):
(функция аргумент1 аргумент2...аргументn),
однако для больших структур программа производит разбиение строк и оформление абзацев (в):
(функция
аргумент1
аргумент2
.
.
.
аргументn)
Упрощенная версия этой программы входит в широко распространенную версию LISP под именем SPRINT. Эта программа занимает большее место в памяти, но она более гладко работает с выражениями в кавычках и обращается к различным функциям (типа SETQ и DEFUN), которые требуют специальной обработки. Программа красивой печати начинает работу над списком с подсчета количества позиций, необходимого для вывода списка в формате (а). Если подсчет покажет, что список может быть напечатан на одной строке, программа выводит этот список в одну строку. В противном случае, происходит обращение к циклу, который осуществляет вывод в формате (в). Заметьте, что аргументы в формате (в) также выводятся на печать с помощью этой программы, используя формат (а) или (в).
Первой необходимой функцией в данной программе является функция, которая будет измерять ширину отпечатанных списков. Нет необходимости вычислять точную длину списков, которые не помещаются на одной строке, и поэтому, в качестве аргумента данная функция принимает заданную ширину W и вычитает напечатанную ширину другого аргумента из W; если результаат отрицательный, осуществляется выход из программы. Встроенная функция LISP - CHPRS возвращает количество символов в идентификаторе LISP и образует основу для следующего:
(DEFUN WIDTH-OF-NUMBER (N)
(COND
((MINUSP N)
(ADD1 (WIDTH-OF-NUMBER (MINUS N))))
((LESSP N 10) 1)
(T (ADD1 (WIDTH-OF-NUMBER (QUOTIENT N 10))))))
(DEFUN WIDTH-OF-ATOM (X)
(COND ((NUMBERP X) (WIDTH -OF-NUMBER X)) (T CHARS
X))))
(DEFUN SUBTRACT-WIDTH (X W)
(COND
((ATOM X) (DIFFERENCE W (WIDTH-OF-ATOM)))
((QUOTEP X)
(SUBTRACT-WIDTH-OF-LIST (CADR X) (SUB1 W)))
(T (SUBTRACT-WIDTH-OF-LIST X (SUB1 W)))))
(DEFUN SUBTRACT-WIDTH-OF-LIST (X W)
(LOOP
(UNTIL (OR (NULL X) (MINUSP W)) W)
(UNTIL
(ATOM X)
(DIFFERENCE W (PLUS 2 (WIDTH-OF-ATOM X))))
(SETQ W (SUBTRACT-WIDTH (CAR X) (SUB1 W)))
(SETQ X (CDR X))))
(DEFUN WILL-FIT (X W)
(NOT (MINUSP (SUBTRACT-WIDTH X W))))
Первые две приведенные функции тесно связаны с расширением функции CHARS для создания функции (WIDTH-OF-ATOM, которая может измерять как символьные, так и числовые атомы. Функция SUBTRACT-WIDTH распознает 3 вида аргументов. WIDTH-OF-ATOM справляется с любым атомом. Выражения, заключенные в кавычки, открываются с помощью функции QUOTEP, которую мы рассмотрим позже, а соответствующие списки передаются подфункции SUBTRACT-WIDH-OF-LIST. Она обрабатывает в цикле аргумент, уменьшая W вычитанием ширины найденных подсписков и лишних чисел, что позволяет позже напечатать пробелы между подсписками.
Выход происходит при отрицательном значении W или по нахождению конца списка. Если список заканчивается ненулевым атомом, W Должен округляться до точки. Сейчас мы можем познакомиться с основной функцией программы "красивой печати". Функция SUPERPRINT имеет два аргумента. Первый аргумент - список, который будет напечатан, второй - левый отступ страницы при печати. Большая часть работы функции SUPERPRINT выполняется SUPERPRIN. Когда функция SUPERPRIN вызывает сама себя, т ее второй аргумент увеличивается, и, поэтому, вложенные подсписки размещаются все дальше вправо. Переменная LINELENGTH используется для определения позиции правого края страницы при печати:
(DEFUN SUPERPRINT (X (LEFTMARGIN . 0))
(SUPERPRIN X LEFTMARGIN)
(PRINT)
X)
(DEFUN SUPERPRIN (X LEFTMARGIN (SUPER))
(COND
((ATOM X) (PRIN X))
((QUOTEP X)
(PRINC (CHARACTER 39))
(SUPERPRIN (CADR X) (ADD1 LEFTMARGIN)))
(WILL-FIT X (DIFFERENCE LINELENGTH LEFTMARGIN))
(SUPER-SUB X (PLUS LEFTMARGIN 3)))
(T (SETQ SUPER T)
(SUPER-SUB X (PLUS LEFTMARGIN 3)))))
Две вещи, которые выполняет SUPERPRIN, стоит отметить. Она обнаруживает выражения, заключенные в кавычки (снова используя QUOTEP) и печатает их с кавычками впереди. Внутренний код кавычек для ОС ОНИКС - 39, поэтому, (PRINC (CHARACTER 39)) выводит кавычки на экран. Другим способом получения точно такого же результата может быть представление кавычек с символом перехода, как в случае (PRINC '!'). И еще SUPERPRIN устанавливает флаг SUPER, который будет инструктировать подфункцию SUPER-SUB О том, какой формат печати (а) или (в) ей нужно использовать. А SUPER-SUB, в свою очередь, использует 2 флага. SEPCHPR используется для печати '(' перед первым обрабатываемым подсписком, и для печати пробелов (или строк) перед всеми остальными. SPECIAL используется для уменьшения числа пустых строк, печатаемых в различных функциях, обычно имеющих в качестве первого аргумента атом. Если большой COND, находящийся в середине цикла, игнорируется, то можно видеть, что SUPER-SUB представляет прямой просмотр списка X, вызывая SUPERPRIN при каждом подсписке, как показано ниже:
(DEFUN SUPER-SUB (X LEFTMARGIN (SEPCHAR) (SPECIAL))
(COND
((CHARP (CARX))
(SETQ SPECIAL (GET (CAR X) 'SPECIAL))))
(LOOP
(UNTIL (NULL X) (PRINC RPAR))
(UNTIL (ATOM X) (PRINC BLANK PERIOD BLANK X RPAR))
(COND
((NULL SEPCHAR) (PRINC LPAR) (SETQ SEPCHAR T))
(SPECIAL
(PRINC BLANK)
(COND
((MINUS (SETQ SPECIAL (SUB1 SPECIAL)))
(SETQ SPECIAL NIL))))
((NULL SUPER) (PRINC BLANK))
(T (PRINT) (SPACES LEFTMARGIN)
(SUPERPRIN (CAR X) LEFTMARGIN)
(SETQ X (CDR X))))
С использованием специальных характеристик можно ознакомиться в программе функции SUPERPRINT, приведенной выше. Они (хар-ки) представлены в формате, определенном SUPERPRINT. Обратите внимание, что формат DEFUN всегда следующий:
(DFUN имя аргументы
...), а не
(DEFUN
имя
аргументы
...)
Подпрограмма SUPER-SUB работает таким образом, что если функциясодержала число, хранящееся как специальная характеристика, то это число сдерживает некоторые прерывания строк. Начало списка функций, работающих таким образом, следующее:
(PUT 'SETQ 'SPECIAL '0) (PUT 'DEFUN 'SPECIAL '1) (PUT 'T 'SPECIAL '0) (PUT 'LAMBDA 'SPECIAL '0)
Единственными неопределенными функциями остались SPACES (печатает последовательность пробелов) и QUOTEP, которая определяет используются ли кавычки для вывода списка на экран, т.е. является ли список списком вида (QUOTE что-либо). Обе эти функции работают достаточно просто.
(DEFUN SPACES (N)
(LOOP
(UNTIL (MINUSP (SETQ N (SUB1 N))))
(PRINC BLANK)))
(DEFUN QUOTEP (X)
(AND
(NOT (ATOM X))
(EQ (CAR X) 'QUOTE)
(NOT (ATOM (CDR X)))
(NULL (CDDR X))))
(SETQ LINELENGTH '60)
Это завершает программу красивой печати. После включения ее LISP, вызов функций (SETQ SPRINT SUPERPRINT) заменит форматер, снабженный системой этой улучшенной версией, и функции CHARCOUNT и XTAB могут быть исключены.
.сс
[an error occurred while processing this directive]