MULISP2
.docFile: MULISP3.LES (c) 09/16/92 CпЭТУ
CLRSCRN
В предыдущем уроке Вы ознакомились с базовыми функциями ЛИСПа. Те-
перь мы продолжим обсуждение различных возможностей использования языка.
В этом уроке много информативного материала и совсем немного задач,
которые Вам придется решать. Однако Вы должны внимательно изучить предла-
гаемую Вам информацию - она Вам очень пригодится при программировании на
muLISPе.
CONTINUE
В muLISPе используются простые объекты трех типов: символы, числа
и точечные пары.
muLISP предоставляет Вам множество функций для распознавания, срав-
нения, комбинирования и обработки этих примитивных типов объектов. Это
позволяет программисту создавать сложные структуры данных для моделирова-
ния с помощью компьютера реальных проблемных областей. Начнем обсуждение
muLISPа с описания базовых типов объектов.
Вы уже знакомы с атомами и списками. Атомы можно подразделить на
строки, числа и символы, а списки представляют собой подмножество струк-
тур более общего вида, называемых двоичными деревьями, которые строятся
из точечных пар.
CONTINUE
Обсудим сначала тип объектов, называемый символом. С символом в
muLISPе связываются 4 системных свойства:
1. Печатное имя символа
2. Текущее значение
3. Список свойств
4. Определение функции
CONTINUE
Функция-распознаватель SYMBOLP возвращает значение T, если значение
ее единственного аргумента - символ; в противном случае она возвращает
значение NIL. Например:
$ (SYMBOLP 'XYZ)
$ (SYMBOLP 41)
$ (SYMBOLP '(DOG CAT COW))
Во время этой паузы проверьте, является ли символом пустой список,
(). Чтобы вернуться в среду урока, наберите обращение (RETURN) и нажмите
на клавишу ввода.
BREAK
CLRSCRN
Как Вы уже знаете, функция-компаратор EQL используется для того,
чтобы определить совпадение двух символов. Например:
$ (EQL 'APPLE (CAR '(APPLE ORANGE LEMON)))
CONTINUE
Поскольку пробелы, круглые скобки и некоторые другие знаки имеют в
muLISPе особый смысл, то при включении этих знаков в печатное имя символа
нужно использовать строку, то есть ограничить с двух сторон печатное имя
символа кавычками. Например:
$ "This is a (single) symbol!"
Обычно сами кавычки не изображаются при выводе символа. (Замечание:
в случае, если значение управляющей переменной PRIN1 есть NIL, печатные
имена символов, содержащих особые знаки, автоматически заключаются в ка-
вычки.) Пустая строка, изображаемая как "", - это тоже символ. Посмотрите:
$ (SYMBOLP "")
CONTINUE
Сам знак "кавычки" может быть включен в печатное имя символа с по-
мощью обратной косой черты, которая помещается перед знаком "кавычки".
Например:
$ "She said, \"I am learning muLISP.\""
Если Вы используйте двойные кавычки в печатном имени символа, то
следите внимательно за балансом этих кавычек. После знака "кавычки" ин-
терпретатор будет каждый новый знак считать очередным знаком печатного
имени символа, и так до тех пор, пока не встретится закрывающий знак "ка-
вычки".
Во время этой паузы посмотрите, что случится, если Вы не закроете
"кавычки" и нажмете на клавишу ввода. Чтобы вернутся в среду урока, Вам
нужно будет ввести знак "кавычки", поэтому Вы увидите подсказку в виде
знака доллара.
BREAK
CLRSCRN
Следующий тип простых объектов muLISPа - это числа. Числа, в свою
очередь, подразделяются на целые и действительные. Целые представляют со-
бой последовательность цифр, перед которой может стоять знак минус.
Поскольку значением числа является само это число, то нет надобности
употреблять знак апострофа перед числом.
$ 41
$ -75
Функция-компаратор EQL используется для проверки двух чисел на ра-
венство:
$ (EQL 3 4)
$ (EQL 0 -0)
CONTINUE
Действительные числа можно вводить одним из двух способов: с исполь-
зованием десятичной точки или косой черты (слеша), то есть в виде рацио-
нальной дроби. По умолчанию при выводе действительные числа изображаются
с десятичной точкой.
$ 3/4
$ -0.34
$ (EQL 0.4 2/5)
CONTINUE
Если значение управляющей переменной *POINT* есть NIL, muLISP изоб-
ражает действительные числа с использованием косой черты. Заметьте, что
действительные числа автоматически округляются, а в том случае, когда
знаменатель равен единице, числа изображаются как целые.
$ (SETQ *POINT* NIL)
$ -5/7
$ 0.33333333
$ 12/9
$ 5/1
CONTINUE
Если значением управляющей переменной *POINT* является ноль или по-
ложительное число, muLISP изображает числа с использованием десятичной
точки с числом десятичных разрядов, равным значению POINT:
$ (SETQ *POINT* 3)
$ 2/3
$ (SETQ *POINT* 7)
$ 2/3
CONTINUE
Функция-распознаватель INTEGERP возвращает значение T, если ее аргу-
ментом является целое число, и NIL в противном случае. Например:
$ (INTEGERP 100)
$ (INTEGERP 'FIVE)
$ (SETQ PRIMES '(2 3 5 7 11))
$ (INTEGERP (CAR PRIMES))
CONTINUE
Функция-распознаватель NUMBERP возаращает значение T, если ее аргу-
ментом является число (целое или действительное), и NIL в противном слу-
чае. Например:
$ (NUMBERP 100)
$ (NUMBERP 457.23)
$ (NUMBERP -23/7)
Во время паузы воспользуйтесь функциями NUMBERP и SYMBOLP, чтобы уз-
нать, является ли числом или символом последовательность цифр, заключен-
ная в кавычки, например, "137".
BREAK
Приведенные ниже два теста показывают, что "137" рассматривается как
символ, а не как число:
$ (NUMBERP "137")
$ (SYMBOLP "137")
CONTINUE
И символы и числа являются атомами, что означает невозможность раз-
делить их на составляющие части.
Примитивная функция-распознаватель ATOM возвращает значение T, если
ее аргументом является атом (то есть символ или число); в противном слу-
чае она возвращает значение NIL. Например:
$ (ATOM 'APPLE)
$ (ATOM 123)
$ (ATOM '(DOG CAT COW))
$ (ATOM '())
CONTINUE
Иногда Вам может потребоваться воспользоваться символом как таковым,
а не его значением. В muLISPе знак апострофа используется для подавления
оценивания символа. Например:
$ (SETQ FOO 1492)
$ FOO
$ 'FOO
Заметьте, что знак апострофа отличается от "обратного апострофа",
знака ` ("accent grave"), который встречается среди знаков клавиатуры не-
которых терминалов.
Во время паузы используйте функцию SETQ и знак апострофа для того,
чтобы возвратить переменой FOO значение, совпадающее с ней самой (то есть
сделайте эту переменную автоматически заключаемой в кавычки).
BREAK
Восстановление значения FOO можно сделать так:
$ (SETQ FOO 'FOO)
$ FOO
CONTINUE
Третий примитивный тип объектов данных muLISPа - это cons-ячейка,
или точечная пара. Это объект, который состоит из двух ссылок на другие
объекты. Само название "cons" происходит от названия функции-конструктора
CONS, с которой Вы уже ознакомились.
При запоминаи в памяти компьютера месторасположение элемента данных
отмечается с помощью понятия "адрес" (ADDRESS). Содержимое памяти может
время от времени меняться.
Предположим, что мы хотим запомнить в памяти точечную пару, состоя-
щую из ссылки на символ BILBO и на значение его возраста - число 31. Мы
можем запомнить символ BILBO в ячейке памяти с адресом 7, а его возраст
31 - в ячейке памяти с адресом 2, а в ячейке с адресом 4 мы начнем запо-
минание точечной пары, которая состоит из двух ссылок (адресов) 7 и 2:
Адрес: 1 2 3 4 5 6 7
+-----+-----+-----+-----+-----+-----+-----+---
Coдержимое:| | 31 | | 7 | 2 | |BILBO|
+-----+-----+-----+-----+-----+-----+-----+---
CONTINUE
muLISP поддерживает автоматическое размещение данных в памяти компь-
ютера. Представление точечной пары в виде разделенного пополам прямоу-
гольника с двумя ссылками как раз и отражает тот факт, что фактические
значения адресов нас совершенно не интересуют.
+-----+-----+
| . | . |
+-/---+---\-+
/ \
/ \
BILBO 31
CONTINUE
Можно еще упростить изображение точечной пары, используя вот такое
представление:
.
/ \
/ \
BILBO 31
Поскольку у точечной пары ровно две ссылки, то ее можно считать дво-
ичным деревом.
CONTINUE
Хотя представление в виде двочного дерева более наглядно, при прог-
раммировании используется линейная запись. Одна из возможной нотации дре-
вовидных структур называется "точечной записью". Для представления точеч-
ной пары используется следующая конструкция: открывающая круглая скобка,
ссылка на первый элемент, точка, ссылка на второй элемент и закрывающая
круглая скобка. Например: точечная пара
.
/ \
/ \
BILBO 31
представляется в точечной записи (DOT notation) как:
(BILBO . 31)
CONTINUE
Первый (левый) элемент точечной пары называется CAR. Второй (правый)
элемент точечной пары называется CDR этой точечной пары. Элементами то-
чечной пары могут быть любые объекты ЛИСПа, в том числе и точечные пары.
Например:
.
/ \
/ \
. 31
/ \
/ \
BILBO BAGGINS
Эквивалентное представление такой структуры с использованием точеч-
ной нотации:
((BILBO . BAGGINS) . 31)
CONTINUE
Давайте добавим в наше двоичное дерево факт, заключающийся в том,
что BILBO - это хоббит:
.
/ \
/ \
. HOBBIT
/ \
/ \
. 31
/ \
/ \
BILBO BAGGINS
Прежде чем продолжить наши рассуждения, подумайте, как изобразить
полученное двоичное дерево в виде точечной записи.
CONTINUE
Проверьте сделанную Вами запись дерева в точечной нотации:
(((BILBO . BAGGINS) . 31) . HOBBIT)
Другой пример представления информации в виде двоичного дерева:
((BILBO . BAGGINS) . (31 . HOBBIT))
Нарисуйте соответствующее этой точечной записи двоичное дерево на
листе бумаги и поднесите рисунок поближе к экрану, чтобы я мог хорошенько
его разглядеть:
_____
/ \
>| O.O |<
| \=/ |
\___/
CONTINUE
Что-то мои глаза видят не слишком хорошо. Вы должны были бы изобра-
зить следующее:
.
/ \
/ \
/ \
. .
/ \ / \
/ \ / \
BILBO BAGGINS 31 HOBBIT
Теперь Вам должно быть понятно, что с помощью точечных пар Вы можете
представить любое двоичное дерево.
CONTINUE
Иногда более естественно представлять структуру из точечных пар не в
виде двоичного дерева с большим числом уровней, а в виде списка (LIST),
состоящего из элементов данных. Например, элементы некоторого множества
часто описываются с помощью списка.
muLISP представляет список в виде последовательности точечных пар, в
которой левая часть (CAR) каждой точечной пары указывает на очередной
элемент списка, а правая часть точечной пары (CDR) содержит ссылку на
следующую точечную пару. Последним элементом связанного списка является
точечная пара, у которой CDR содержит пустую сслылку NIL. Например:
.
/ \
/ \
object1 .
/ \
/ \
object2 .
.
.
/ \
/ \
objectN NIL
CONTINUE
Повернем это двоичное дерево на 45 градусов против часовой стрелки,
и тогда Вам будет легче рассматривать представление списка:
.--------.--- . . . ---.----- NIL
| | |
| | |
object1 object2 objectN
На языке ЛИСП такая конструкция очень легко изображается в виде
списка элементов:
(object1 object2 ... objectN)
что в точечной записи может быть представлено как:
(object1 . (object2 . ... (objectN . NIL) ...))
CONTINUE
В muLISPе используется представление в виде списка, если это возмож-
но, и с применением точечной записи, в тех случаях, когда в ней возникает
необходимость. Структура
.
/ \
/ \
object1 .
/ \
/ \
object2 .
.
.
/ \
/ \
objectN atom
в которой <atom> не имеет значения NIL, может быть представлена в линей-
ной записи как:
(item1 item2 - - - itemN . atom)
CONTINUE
Процедура чтения muLISP воспринимает списки, изображение в виде то-
чечной записи и смешанное изображение. Некоторые элементы списка, в свою
очередь, могут представлять собой списки или последовательности с исполь-
зованием точечной записи. Приведенные примеры покажут, как воспринимаются
такие записи в muLISPе:
$ '(DOG . (CAT . (COW . PIG)))
$ '((AGE . 34) . (HOBBIES . (SWIMMING . THINKING)))
CONTINUE
Во время данного урока мы описали примитивные объекты данных
muLISPа : символы, числа и точечные пары. Повторим главные положения уро-
ка, которые Вы должны запомнить:
1. Символы: Каждый символ имеет ассоциированные с ним печатное имя,
значение, список свойств и определение функции. Символы, в именах которых
содержатся специальные знаки, могут быть введены с помощью строк, заклю-
ченных в кавычки. SETQ - это наиболее часто используемая функция для
присваивания значения символу.
2. Числа: Число - это положительное или отрицательное рациональное
число. Функция NUMBERP используется как распознаватель. Она принимает
значение Т, если ее аргумент является числом. Числа подразделяются на це-
лые и дробные. Функция INTEGERP используется для распознавания целых
чисел.
3. Точечные пары: точечные пары используется для создания двоичных
деревьев, которые могут представляться с помощью списков, точечной нота-
ции или смешанной нотации.
CONTINUE
А теперь выполните задание:
1. Изобразите список
(A (B (C)) (D))
в точечной нотации и убедитесь с помощью обращения к интерпрета-
тору, что Вы не ошиблись.
Нарисуйте представление этого списка в памяти и покажите препода-
вателю.
2. Ознакомьтесь со справочной системой muLISP'а. Найдите функции, ко-
торые меняют цвет фона и цвет символов на экране. Попробуйте по-
добрать сочетание цветов, которое Вам нравится.
3. Выберите две дополнительных функции обработки списков и покажите
на 3-х примерах для каждой из этих функций особенности их действия.
CONTINUE
$ (RDS)