Лабораторная работа №4

Оперативная память, в которой работает Лисп-система, логически разбивается на маленькие области. Эти области называются списочными ячейками. Списочная ячейка состоит из двух частей – полей СAR и CDR. Каждое из полей содержит указатель. Указатель может ссылаться на другую списочную ячейку. Указателем списка является указатель на первую ячейку списка. На ячейку могут указывать не только поля СAR и CDR, но и используемый в качестве переменной символ. Например, следующий вызов создает списочную структуру:

$(setq список ‘(a b c))]

CONS - это неатомный объект данных , который указывает на два других объекта данных. CONS создает ячейку и возвращает на нее указатель. Допустим, что у нас есть два списка:

$(setq голова ‘(b c)) и

$(setq хвост ‘(a b c).

Вызов функции

$(cons голова хвост)

строит список из ранее построенных списков ГОЛОВА и ХВОСТ:

Каждый CONS имеет только 2 "ветви", поэтому такие диаграммы называются бинарными деревьями. Вместо бинарных деревьев чаще используют представление в виде точечной пары . Например : (cons ‘a ‘b) соответствует точечная пара (A . B). Левый элемент CONS - это CAR от CONS, правый - CDR от CONS.

В результате вычислений в памяти могут возникнуть структуры, на которые нельзя сослаться. Это происходит тогда, когда вычисленная структура не сохраняется с помощью setq или когда теряется ссылка на старое значение. Говорят, что эти ячейки стали мусором. Мусор возникает и тогда, когда результат вычисления не связывается с какой-нибудь переменной. Например, значение вызова

$(cons ‘a (list ‘b))

(A B)

лишь печатается, после чего соответствующая ему структура остается в памяти мусором.

В Лиспе с символом можно связать именованные свойства. Свойства символа записываются в хранимый вместе с символом список свойств. Формат списка свойств имеет вид:

(имя₁ значение₁ имя₂ значение₂... имя_n значение_n).

Назначение свойств символу может осуществляться с помощью функций присваивания SETQ или определения функции DEFUN. Эти же функции используются для изменения значений свойств. Для чтения свойств символа используется функция GET:

(get символ свойство)

Присваивание свойства или изменение значения существующего свойства осуществляется с помощью функции PUTPROP:

(putprop символ свойство значение)

Удаление свойства:

(remprop символ свойство)

Чтение списка свойств:

(symbol-plist символ)

Примеры:

$(put ‘ягода-рябины ‘вкус ‘кислый)

КИСЛЫЙ

$(put ‘ягода-рябины ‘цвет ‘красный)

КРАСНЫЙ

$(put ‘ягода-рябины ‘вес ‘((2 г)))

((2 Г))

$symbol-plist ‘ягода-рябины)

((ВЕС (2 Г)) (ВКУС . КИСЛЫЙ) (ЦВЕТ . КРАСНЫЙ))

$(remprop ‘ягода-рябины ‘вкус)

ВКУС

$(get ‘ягода-рябины ‘вкус)

NIL

Ассоциативный список (а-список) – это структура данных, основанная на списках и точечных парах. Для работы с а-списком имеются встроенные функции. Ассоциативный список состоит из точечных пар, поэтому его называют списком пар:

((a₁ . d₁)(a₂ . d₂) ... (a_n . d_n)).

Первый элемент пары (CAR) называют ключом (key), а второй (CDR) – связанным с ключом данным (datum). С помощью а-списка можно объединять разнотипные данные, поименованные ключами компоненты данных. Таким образом можно легко создавать базы данных, из которых информация просто и быстро выбирается, модифицируется. Для работы с а-списками используются следующие функции. Перед использованием обрабатывающих а-список функций необходимо его инициализировать, например функцией setq.

(assoc ключ а-список ) – ищет пару, соответствующую ключу.

(putassoc ключ данные а-список) – изменяет а-список.

(rassoc данные а-список) – ищет по данным значение ключа (обратная функция assoc).

(acons ключ данные а-список) – добавляет точечную пару в начало а-списка.

Пример. Создать словарь.

$(setq словарь ‘((один . one)))

(ОДИН . ONE)

$(putassoc ‘два ‘two словарь)

(ДВА . TWO)

$словарь

((ОДИН . ONE)(ДВА . TWO))

$(assoc ‘два словарь)

(ДВА . TWO)

$(rassoc ‘two словарь)

(ДВА . TWO)

$(acons ‘нуль ‘zero словарь)

((НУЛЬ . ZERO)(ОДИН . ONE)(ДВА . TWO))

Задание к выполнению работы.

1. Создать список столиц государств.

2. Показать возможность добавления и удаления элементов списка.

3. Создать список, содержащий свойства воды как химического соединения.

4. Добавить к созданным свойствам воды свойство состояния

(жидкость).

5. Ввести новый список, определяющий свойства льда. Этот список

должен включать свойства воды и новое свойство - температуру.

6. Добавить к полученному списку свойство льда - цвет в начало

списка.

7. Использовать функции доступа к полям списка по ключу и по

значению данных.

Приложение 1

Краткое введение в систему muLISP.

Интерпретатор содержится в файле mulisp.com .

После загрузки программы на экран выводится таблица:

1 = Other generic MS-DOS computer

2 = IBM PC or "look-alike" computers

3 = ANSI.SYS screen or VT-100 Terminal

4 = TI Professional Computer

5 = Zenith Z-100 Computer or VT-52 Terminal

6 = Hewlett-Packard HP-150 Computer

7 = Hewlett-Packard HP-110 Computer

8 = NEC Advanced Personal Computer or ADM-3A Terminal

Please enter your computer type number

Если здесь не указан тип вашей ЭВМ, выберите тип "2".

После запуска на экран выдается приглашение к диалогу в виде "$". Когда пользователь заканчивает ввод какого-либо выражения или вызов функции, то интерпретатор вычисляет и выдает значение этого выражения:

$ (+ 2 3)

5

$ (* (+ 1 2)(+ 3 4))

21

Для блокировки вычисления выражения используется апостроф ('):

$ '(+ 2 3)

(+ 2 3)

$ ( CAR '(+ 2 3))

+

Для трассировки функций перед их запуском необходимо ввести команду

(rds ‘debug)

(trace <список имен функций, входящих в состав выполняемой функции>),