Эти свойства дают возможность оперировать такими аргументами, как:
(ADD (CIRCLE 200) (BOX 100 200) (BOX 300 100))
Чтобы соединить эту возможность с функцией GSUPER, необходимо обеспечить работу некоторых функций на уровне пользователя для соединения, перемещения и окраски прямоугольников и окружностей. Это затрачивает большую часть их энергии, проверяя, чтобы аргументы были обозначены как картинки, затем они строят структуры данных, необходимые для DRAW:
(DEFUN ADD (A B)
(COND
((PICP A) (COND
((PICP B)
(MKPIC (LIST 'ADD (CDR A) (CDR B))))
(T A)))
((PICP B) B)
(T (LIST A B))))
(DEFUN SHIFT (P X Y)
(COND
((PICP P) (MKPIC (LIST 'SHIFT (CDR P) X F)))
(T P)))
(DEFUN CIRCLE (A) (MKPIC (LIST 'CIRCLE A)))
(DEFUN BOX (A B) (MKPIC (LIST 'BOX A B)))
(DEFUN MKPIC (X) (CONS 'PIC X))
(DEFUN WHITE (X) (COLOUR X 3))
(DEFUN YELLOW (X) (COLOUR X 2))
(DEFUN RED (X) (COLOUR X 1))
(DEFUN BLACK (X) (COLOUR X 0))
(DEFUN COLOUR (X N)
(COND
((PICP X) (MKPIC (LIST 'COLOUR (CDR X) N)))
(T X)))
В качестве демонстрации только что приведенного графического языка, попробуйте:
(MODE 4)
(GSUPER)
(DEFUN SPIDER (N) (COND
((MINUSP N) NIL)
(T (ADD (CIRCLE N)
(SPIDER (DIFFERENCE N 20))))))
(SETQ WEB (SRIDER 120))
(ADD (YELLOW WEB) (RED (SHIFT WEB 30 40)))
'FIN
Значительная дополнительная память и вычислительные возможности графического расширения LISP в таком виде может привести к его росту в совершенно независимый язык для использовния в инженерном и художественном деле.
23.10 Языки программирования синтаксического анализа.
Программа синтаксического анализа (анализатор) - это программа, которая считывает строку символов и разрабатывает правило, по которому их можно сгруппировать. Результат, как правило, будет древовидной структуры. Компьютеры используют анализаторы для перевода программ из того вида, в котором они напечатаны, в другой, используемый для внутренней обработки. Приведенный здесь простой анализатор может оперировать арифметичскими выражениями, которые используют операторы +,-,* и /. Он распознает скобки и выдает в качестве результата префиксальные разветвленные структуры, аналогичные обсуждавшимся в разделе 23.2. При описании его работы было бы полезно иметь точное определение класса выражений, которые распознаются. Правила, использованные здесь следующие: 'выражение' - один или несколько термов, разделенные между собой знаками + или -. 'Терм' - список 'факторов', разделенных между собой знаками * или /. 'Фактор' - 'символ' или 'выражение', заключенное в скобки. Программисты пишут правила такого рода в сжатом виде:
<выражение> = <терм> ! <выражение> + <терм>
! <выражение> - <терм>
<терм> = <фактор> ! <терм> * <фактор>
! <терм> / <фактор>
<фактор> = <символ> ! (<выражение>),
где вертикальную черту (!) следует читать как 'или'.
Анализатор может быть разработан с учетом этих правил и записан как функция. Таким образом, следующая процедура выражает идею, что выражение начинается с терма и может быть продолжено, присоединяя термы до тех пор, пока не встретится знак + или -. Функции NEXTSYM предстоит объявить переменную CURSYM, которая будет следующим термом в вводимом тексте и возвращать текущий терм как его результат:
(DEFUN EXPRESSION ((TREE))
(SETQ TREE (TERM))
(LOOP
(WHILE (OR (EQ CURSYM '+) (EQ CURSYM '-)) TREE)
(SETQ TREE (LIST (NEXTSYM) TREE (TERM)))))
Последняя строка ВЫРАЖЕНИЯ зависит от СПИСКА, располагающего свои аргументы слева направо таким образом, что NEXTSYM читает предыдущий знак + или - прежде чем происходит обращение к функции TERM, которая обрабатывает следующий операнд. К такой практике следует относиться осторожно, т.к. некоторые версии LISP оставляют за собой право располагать аргумент в таком порядке, который представляется наиболее удобным. Функция, которая считывает термы и факторы, по типу аналогична:
(DEFUN TERM ((TREE))
(SETQ TREE (FACTOR))
(LOOP
(WHILE (OR (EQ CURSYM '*) (EQ CURSYM '/)) TREE)
(SETQ TREE (LIST (NEXTSYM) TREE (FACTOR)))))
(DEFUN FACTOR ((TREE))
(COND
((EQ CURSYM LPAR)
(NEXTSYM)
(SETQ TREE (EXPRESSION))
(NEXTSYM)
TREE)
(T (NEXTSYM))))
Если память не учитывалась, ФАКТОР должен проверить, что символ, следующий за считанным выражением, является правой скобкой; в противном случае, она генерирует ошибку. Как записано здесь, она рассматривает символы оператора как операнды и игнорирует любой символ, стоящий на месте правой скобки. NEXTSYM должна считать символ и записать его в CURSYM, возвращая предыдущее значение CURSYM. Полный анализатор должен будет считывать многосимвольные слова и различать имена и числа. Для простоты фрагмент, представленный здесь, обрабатывает каждый символ при вводе, исключая пробелы, как отдельный символ. Заметьте, что смысл этого в том, что символы, которые должны быть числами, например 6, считываются как идентификаторы, и поэтому, LISP не может производить непосредственно над ними арифметические действия:
(DEFUN NEXTSYM ((PREV))
(SETQ PREV CURSYM)
(LOOP
(SETQ CURSYM (GETCHAR))
(PRINC CURSYM)
(WHILE (EQ CURSYM BLANK) PREV)))
Функция EXPRESSION является основной входной точкой для этого анализатора, но для его работы CURSYM должен быть задан как первый символ вводимой строки. Это может осуществить функция драйвера PARSER:
(DEFUN PARSER ((CURSYM)) (NEXTSYM) (EXPRESSION))
PARSER можно проверить следующим образом:
(PARSER) 2+(A-B)*(4/X+7)
Этот анализатор сильно отличается от тех, которые обрабатывают готовые языки программирования. Однако, при грубой оценке размера этого фрагмента, он может быть преобразован в такой, который считывает языки типа АЛГОЛ, ПАСКАЛЬ и преобразовывает их в структуры, которые LISP использует для представления программ. Пожалуй, самая неприятная часть написания программы - та, в которой происходит соединение последовательности символов для составления слов и чисел: следует активно использовать CHARACTER, IMPLODE, ORDINAL и другие. Пишущие анализаторы, которые хорошо работают после обнаружения синтаксических ошибок при вводе, трудны. При использовании маленького интерактивного компьютера было бы лучше реагировать на ошибки вызовом ERROR, чтобы выйти из процесса анализа.
23.11 Создание машинного кода
Одной из первых неожиданностей, поджидавших разработчиков языка LISP, была возможность написания компилятора LISP на самом языке LISP. Этот язык и сейчас еще остается примером, на котором можно продемонстрировать идею компиляции. Компилятор, описанный здесь, обрабатывает простые арифметические выражения, чтобы получить сборный код 6502, который будет производить описанные восьмиразрядные вычисления. Полученный код будет не очень эффективным, но программа - очень короткой!
Чтобы понять смысл этого кода, необходимо иметь представление о машинном коде, который нужно создать, и знать синтаксис использованного ассемблера. Коды операций, которые могут быть получены с помощью этого компилятора, следующие: LDA, STA, PHA, PLA, ADC, SBC, AND и ORA. Вводом в компилятор будут древовидные структуры типа (+ (& А 8) (-2 В)).
В том случае, когда аргумент - атомное выражение, CG печатает строку текста:
LDA # аргумент , если аргумент - число; или LDA аргумент , в противном случае.
В противном случае принимается, что CG имеет бинарный оператор, к которому он обращается. Он вызывает себя как рекурсивную функцию для загрузки первого операнда в накопитель 6502. Он сохраняет это значение в стеке, используя PHA, пока вычисляется второй операнд. Затем он перемешивает регистры и заканчивает работу печатью инструкции, код операции которой зависит от обрабатываемого выражения. PUT и GET используются для того, чтобы установить связь, например, между оператором & и кодом операции 6502 AND:
(DEFUN CG (X)
(COND
((NUMBER X ) (PRINTC 'LDA BLANK '# BLANK X))
((ATOM X) (PRINTC 'LDA BLANK X))
(T (CG (CADR X))
(PRINTC 'PHA)
(CG (CADR X))
(PRINTC 'STA BLANK 'TEMP)
(PRINTC 'PLA)
(PRINTC (GET (CAR X) 'OPCODE) BLANK 'TEMP))))
(PUT '+'OPCODE 'ADC)
(PUT '-'OPCODE 'SBC)
(PUT '&'OPCODE 'AND)
(PUT '!'OPCODE 'ORA)
Те, кто знаком с ассемблером 6502, быстро определять, что этот компилятор генерирует неправильные коды, не устанавливает или не очищает флаг переноса перед выполнением операций сложения или вычитания. Расширить его для исправления этого и для уменьшения числа избыточных проталкиваний в стек и выталкиваний элементов из стека предоставляется читателю. Создав компилятор, способный распознавать по имени операторы, такие как COND и LOOP, он может быть расширен до полного языка программирования. Совершенный оптимизирующий компилятор LISP можно найти в работе Грисса и Герна (Griss and Hearn), приведенной в библиографии, его версии использовались при создания кода для ряда машин - от микро до больших универсальных.
23.12 Лабиринты и темницы.
Возможность LISP работать со словами и сложными структурами делает его естественным языком для программирования запутанных лабиринтов в приключенческих играх. В схеме данной игры приведена возможная организация темницы, отражено движение, сбор и сброс. Она не включает магию, специальных условий для некоторых действий или счет. Включение одного из названных требует дополнительного программирования, включая дополнительные элементы, которые необходимо занести в список характеристик. Приключение начинается по вызову READLINE для заполнения буфера ввода с клавиатуры. Затем печатается заголовок и игрок оказывается на стартовой позиции в лабиринте с "пустыми руками". После этого программа в цикле выполняет ваши команды до тех пор, пока вы не достигните конца (или середины) лабиринта.
(DEFUN ADVENTURE NIL
(READLINE)
(PRINTC '(WELCOME TO MAZE))
(SETQ LOCATION 'START)
(SETQ CARRYING NIL)
(LOOP
(DISPLAY-POSITION)
(UNTIL (EQ LOCATION 'FINISH) 'CONGRATULATIONS)
(MAKE-MOVE (READLINE))))
При изображении позиции необходимо сообщить информацию, описывающую местоположение с указанием что выполняется, какие следующие объекты можно увидеть и в каком направлении возможно движение. Большая часть этой информации может быть связана с местоположением при использовании PUT и GET. Выходы имеют имена, которые соответствуют направлениям (например СЕВЕР), там же хранится имя места, к которому ведет определенное напрвление. DISPLAY-POZITION разбивает все структуры данных, используя MAPC для просмотра включенных списков.
(DEFUN DISPLAY-POSITION NIL
(PRINT)
(PRINC 'AT: BLANK)
(LPRI (GET LOCATION 'DESCRIPTION))
(MAPC
'(LAMBDA (ITEM)
(LPRI (LIST 'YOU 'ARE 'CARRYING ITEM)))
CARRYING)
(MAPC
'(LAMBDA (ITEM) (LPRI (LIST 'YOU 'SEE ITEM)))
(GET LOCATION 'OBJECTS))
(PRINC 'EXITS:)
(MAPC
'(LAMBDA (DIR)
(COND ((GET LOCATION DIR) (PRINC BLANK DIR))))
'(NORTH SOUTH EAST WEST UP DOWN))
(PRINT))
(DEFUN LPRI (L)
(LOOP
(WHILE L (PRINT))
(PRINC (CAR L) BLANK)
(SETQ L (CDR L))))
Эта игра-лабиринт воспринимает только однословные команды. MAKE-MOVE проверяет является ли это слово именем выполняемого объекта, именем следующего объекта или направлением, в котором можно двигаться из данного местоположения:
(DEFUN MAKE-MOVE (WORD)
(COND
((MEMBER WORD CARRYING) (DROP WORD))
((MEMBER WORD (GET LOCATION 'OBJECTS))
(PICK-UP WORD))
((AND
(GET LOCATION WORD)
(CHARP (GET LOCATION WORD)))
(MOVE-TO WORD))
(T (LPRI (LIST WORD 'NOT 'UNDERSTOOD)))))
DROP и PICK-UP написаны просто. DROP удаляет пропущенный объект из списка элементов, которые выполняются и хранит его как другой элемент, существующий в текущем местоположении. PICK-UP работает наоборот. Оба печатают сообщение, подтверждающее выполненное:
(DEFUN DROP (WORD)
(SETQ CARRYING (DELETE WORD CARRYING))
(PUT LOCATION 'OBJECTS
(CONS WORD (GET LOCATION 'OBJECTS)))
(LPRI (LIST 'DROPPED WORD)))
(DEFUN PICK-UP (WORD)
(PUT LOCATION 'OBJECTS
(DELETE WORD (GET LOCATION 'OBJECTS)))
(SETQ CARRYING (CONS WORD CARRYING))
(LPRI (LIST 'GOT WORD)))
(DEFUN MOVE-TO (DIRECTION) (SETQ LOCATION (GET LOCATION WORD)))
Помимо сервисных фунций DELETE, MEMBER и EQUAL, характеристики которых даны в Приложении В, остается требование к лабиринту. Вот один очень маленький лабиринт. У него только одно ответвление, поэтому в нем почти невозможно запутаться. Сначала идет описание комнат в лабиринте:
(PUT 'START 'DESCIPTION '(THE ENTRY TO MAZE)) (PUT 'HALL 'DESCRIPTION '(A FINE GOTHIC HALLWAY)) (PUT 'TWIST 'DESCRIPTION '(A TWISTY RASSAGE)) (PUT 'DEAD 'DESCRIPTION '(DEAD END)) (PUT 'CAVE 'DESCRIPTION '(ALADDINS CAVE)) (PUT 'FINISH 'DESCRIPTION '(CASTLE SPLENDID))
А теперь проходы, соединяющие эти комнаты:
(PUT 'START 'NORTH 'HALL) (PUT 'HALL 'EAST 'TWIST) (PUT 'TWIST 'UP 'CAVE) (PUT 'CAVE 'EAST 'DEAD) (PUT 'CAVE 'WEST 'FINISH) (PUT 'HALL 'SOUTH 'START) (PUT 'CAVE 'DOWN 'TWIST) (PUT 'DEAD 'DOWN 'CAVE)
В заключении необходимо найти предметы, разбросанные по темнице:
(PUT 'START 'OBJECTS '(LANTERN LASERGUN)) (PUT 'TWIST 'OBJESTS '(KEYS MAP)) (PUT 'CAVE 'OBJECTS '(TREASURE))
Даже без введения магии эта программа может перерасти в захватывающую игру, используя функцию выбора случайного лабиринта с несколькими десятками комнат в нем. Следуя традиции, сложившейся в более ранних приключенческих играх, все они должны иметь в качестве описания
(A MAZE OF TWISTY PASSAGES - ALL ALIKE - лабиринт извилистых похожих друг на друга ходов),
таким образом, задание по нахождению пути к выходу из лабиринта становится захватывающим.
ПРИЛОЖЕНИЕ А
Список функций, реализованных в языке LISP Acornsoft
В этом приложении приводится список идентификаторов, первоначально допустимых в язык LISP. Этот список можно дополнить, используя оператор DEFUN для функций или SETQ для пременных. Т.к пользователь может добавлять и удалять функции и затем сохранить копию окончательной системы, этот список следует рассматривать как описание сути всего того, что можно сделать. В любой сохраненной версии языка LISP функция OBLIST используется для получения окончательного и текущего списка допустимых имен. Версии языка LISP должны включать все эти функции, а дальнейшие разработки будут предоставлять еще большие возможности.
Для каждого идентификатора, приведенного здесь, существует заголовок, который определяет относится этот идентификатор к функции или переменной, и дает указание по употреблению аргумента в случае функции. Слова Subr, Fsubr и Expr употребляются для обозначения:
Subr: Встроенная функция по нормальной обработке аргумента.
Fsubr: Встроенная функция по специальной обработке аргумента, например, аргументы обрабатываются слева направо, или иногда вычисляются не все аргументы функции.
Expr: Функция, определенная в LISP, а не в машинных кодах.
****************************************************************
-127-
ADD1 Subr
(ADD1 число)
Функция ADD1 наращивает аргумент, который должен быть числовым. Не удается записать арифметическое переполнение, если результат выходит за пределы допустимых значений (т.е. если вводимое число - максимальное допустимое в LISP целое число 32767). (ADD1) точно соответствует (PLUX x 1), но ее использование может привести к незначительному уменьшению программы. См. также SUB1.
AND Fsubr
(AND предикат предикат)
Функция AND может содержать любое количество аргументов. Принимает значение Т тогда и только тогда, когда все аргументы ненулевые. Если хотя бы один из аргументов функции AND равен 0, то и значение AND становится равным 0 (представление "ложь" в языке LISP). AND не обязательно вычисляет все аргументы. Она проходит через весь список, вычисляя один за другим пока:
(а) значение аргумента = 0, значение функции AND = 0;
(б) исчерпан список аргументов, в этом случае AND принимает значение Т.
Например:
(AND (NUMBER N)
(GREATERP N 0)
(LESSP N 7))
принимает значение Т, когда переменная N принимает значение от 0 до 7.
См. также OR, NOT, T и NIL.
ADVAL Subr
(ADVAL число)
Если аргумент положительный, эта функция принимает информацию ободном из компьютерных аналогов цифрового преобразователя. Аргументы 1,2,3 и 4 обязывают функцию принимать значение с соответствующего преобразователя. Если аргумент = 0, полученное значение показывает, где горит кнопка: на игровом манипуляторе или пульте, подключенном к машине. Если нажата левая кнопка, то наименьший значащий бит - первый, а если правая кнопка - 2-ой бит. Маленькие отрицательные аргументы функции означают получение информации о различных очередях внутри компьютера. Среди них наиболее полезным является ADVAL -1, который доставляет число символов, ожидающих ввода из буфера клавиатуры.
APPLY Subr
(APPLY функция список аргументов)
Первый аргумент функции APPLY должен быть указатель-код (полученный как значение одной из встроенных функций LISP) или выражение-лямбда, как то, которое хранится как введение определения, используя DEFUN. Второй аргумент - список аргументов для передачи данной функции. APPLY используется как функция, которая вызывается сама, является результатом каких-либо вычислений, или тогда, когда вычисляется количество или определяется вид аргументов функции. Функция TRACE из приложения B иллюстрирует использование APPLY при типичном назначении. Приведенный здесь пример показывает как работает функция APPLY.
(APPLY CONS '(A B)) отражает результат применения функции CONS к двум аргументам A И B и эквивалентно (CONS ' A ' B). См. оператор EVAL.
ASSOC Subr
(ASSOC - ключ список связей)
Список связей - это список пар точек вида ((к1 . v1)(k2 . v2)...), где ключи к1,к2...- идентификаторы и соответствующие им значения v1,v2... - произвольные структуры данных LISP. ASSOC просматривает такой список, отыскивая в нем первый пример заданного ключа. Если функция находит такую пару, то она принимает значения ключевой части пары, в противном случае функция становится равной нулю. Т.о., (ASSOC ' B '((A .1)(B .2)(C .3))) имеет значение (В .2).
ATOM Subr
(ATOM аргумент)
Функция ATOM приобретает значение Т, если ее аргументом является какой-либо атом, т.е. если это идентификатор, число или точка входа части машинного кода. В противном случае, т.е. если аргумент - списковая структура, ATOM принимает значение ноль. Т.о.,
(ATOM 'IDENTIFIER) -> T,
(ATOM CAR) ->T
(т.к. значение CAR - входная точка машинного кода в языке LISP, которое обеспечивает функцию CAR),
(ATOM (CONS что-либо что-либо)) -> ноль,
(ATOM '(некоторый список)) -> ноль
См.также SUBR, FSUBR, NUMBER, LISTP.
.сс
[an error occurred while processing this directive]