## ЛЕКЦИЯ 8.

ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ. ПРИМЕНЯЮЩИЕ ФУНКЦИОНАЛЫ

Содержание

  8.1 Внутреннее представление списков.
  8.1.1 Структура памяти.
  8.1.2 Представление списков через списочную ячейка.
  8.1.3 Представление списков через точечные пары.
  8.1.4 Списочная ячейка и базовые функции.
  8.1.5 Переменные и списки.
  8.1.6 EQ и EQUAL.
  8.1.7 Cборка мусора.
  8.2 Обработка списков без разрушения. Append.
  8.3 Разрушающие функции.
  8.3.1 NCONC.
  8.3.2 RPLACA, RPLACD.
  8.3.3 Использование разрушающих функций.
  8.4 Применяющие функционалы.
  8.4.1 APPLY.
  8.4.2 Cочетание apply, nconc, mapcar - mapcan.
  8.4.3 Функционал FUNCALL.

## 8.1 Внутреннее представление списков

## 8.1.1 Структура памяти

Каждый атом занимает ячейку.

Списки, являются совокупностью атомов, и связываются вместе специальными элементами памяти, называемыми списочными ячейками или cons-ячейки.
Каждая списочная ячейка состоит из двух частей, полей.
Первое поле - CAR, второе CDR

Поля типа списочная ячейка содержат указатели на другие ячейки, или nil.
Если обе ячейки содержат указатели на атомы, то можно записать проще

Этому случаю соответствует структура (a.b) которая называется точечной парой.

## 8.1.2 Представление списков через списочную ячейку.

Список из одного атома, представляется, как

NIL указывает на конец списка.
Вместо nil пишут - \.
Список получается как операция (cons 'a nil)
Список из двух элементов (b a)

Правое поле указывает на cdr списка (хвост).
Левое поле, на саr списка(голову).

Каждому элементу списка соответствует списочная ячейка.

Список (a b c d) будет представлен как :

Если список не одного уровня (a (b c) d), то каждому элементу списка соответствует списочная ячейка.
Причем саr поле второй списочной ячейки указывает на вложенный список.

## 8.1.3 Представление списков через точечные пары.

Любой список можно записать в точечной нотации.

(a) <=> (a.nil) |

(a b c) <=> (a.(b.(c.nil)))

Выражение представленное в точечной нотации можно привести к списочной если cdr поле является списком.

(a.(b c)) <=> (a b c)
(a.(b.c)) <=> (a b.c)

## 8.1.4 Списочная ячейка и базовые функции.

Результатом действия функции car будет значение левого поля первой списочной ячейки

* (сar '(a (b c) d)
a

Результатом действия функции cdr будет значение правого поля первой списочной ячейки.

* (сdr '(a (b c) d)
((b c) d)

CONS создает новую списочную ячейку, car поле которой указывает на первый элемент, а cdr на второй

(cons 'x '(a b c))

или

LIST

* (list 'a '(b c)) (a (b c))

этот список представляется

Получается следующим образом:
1. Создается списочная ячейка для каждого аргумента функции
2. В car поле ставится указатель на соответствующий элемент
3. В cdr поле ставится указатель на следующую списочную ячейку

## 8.1.5 Переменные и списки.

Рассмотрим выражение

(setq y '(a b c))

Переменная Y будет иметь значение '(a b c)

Использование переменной , в функции обеспечивает доступ к структуре

(setq x (cons 'd y))

CONS не изменяя структуры, увеличивает список.

Если в функции присвоения список задается явно, то под него отводятся новые списочные ячейки.т.е.

(setq z '(a b c))

Переменная z будет иметь значение '(a b c)

## 8.1.6 EQ и EQUAL.

EQ проверяет физическое равенство списков, и EQUAL -логическое, т.е. для EQ необходимо, чтобы списки имели одинаковую стpуктуpу, а для EQUAL одинаковые элементы. (Структура списка определяется списочными ячейками).

*(setq lis1 '(a b))

* (setq lis2 '(a b))

Другая структура списка

| * (setq lis3 lis1) * (equal lis1 lis2) t * (equal lis1 lis3) t
* (eql lis1 lis2)
nil
* (eql lis1 lis3)
t
* (eq lis1 lis2)
nil
* (eq lis1 lis3)
t

Однако для отдельного атома это не выполняется, т.е. новые ячейки не отводятся.

| * (setq m 'abc) * (setq n 'abc) * (eq m n) t

## 8.1.7 Cборка мусора

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

Например

(setq l1 '((a) b c)) (setq l1 (cdr l1)) |

Для повторного использования ставшей мусором памяти в лисп системах предусмотрен специальный сборщик мусора, (garbage collector) GC, который автоматически запускается когда в памяти остается мало места.

Сборщик мусора перебирает все ячейки и собирает ставшие мусором ячейки в область свободной памяти для использования.

## 8.2 Обработка списков без разрушения. Append.

Обычные функции производят операции над списками, не внося изменений в указатели списочных ячеек. В том случае когда, возникает такая необходимость, создается копия списочной ячейки с новым содержанием полей.

Пример, для функции APPEND рассмотрим следующую последовательность действий.

| * (setq first '(a b)) (a b) * (setq second '(c d)) (c d) * (setq both (append first second))
(a b c d)

Эти действия, показывает диаграмма

APPEND cоздает копии всех списочных ячеек для каждого элемента во всех аргументов, исключая последний аргумент, в то время как cons создает только одну списочную ячейку.
Если складывают два списка в 1000 и 1 элемент, то будет создано 1000 копий списочных ячеек, вместо того чтобы исправить один указатель.

## 8.3 Разрушающие функции

В лиспе есть несколько функций, которые изменяют содержимое указателей, вместо того чтобы создавать новые списочные ячейки. Эти функции называют разрушающими , т.к. указатель заменяется и исходная структура разрушается.

## 8.3.1 NCONC.

Функция nconc позволяет соединить два списка изменением указателя.

(setq new (nconc first second))

Список не копируется. Вместо этого nil в последней списочной ячейке меняется на указатель к первой списочной ячейке второго списка.

Как побочный эффект

* both
(a b c d)
* first
(a b c d) cписок first разрушен.

## 8.3.2 RPLACA, RPLACD

Другие две функции изменяют структуру своих аргументов.
rplaca -"replace the car" имеет два аргумента , причем первый должен быть списком. Функция заменяет car первого аргумента на второй. Т.е. указатель car первой списочной ячейки меняется на указатель ко второму аргументу.