Работа в Word
<<  Список знакомых Работа со списками в Word  >>
Внутреннее представление списков
Внутреннее представление списков
Лисповская память состоит из списочных ячеек Значение представляется
Лисповская память состоит из списочных ячеек Значение представляется
Лисповская память состоит из списочных ячеек
Лисповская память состоит из списочных ячеек
Указатели между ячейками образуют как бы цепочку, по которой можно из
Указатели между ячейками образуют как бы цепочку, по которой можно из
Графически списочная ячейка представляется прямоугольником (рис
Графически списочная ячейка представляется прямоугольником (рис
Значение представляется указателем
Значение представляется указателем
Побочным эффектом функции присваивания SETQ является замещение
Побочным эффектом функции присваивания SETQ является замещение
Графически ссылку на пустой список изображают в виде перечеркнутого
Графически ссылку на пустой список изображают в виде перечеркнутого
CAR и CDR выбирают поле указателя
CAR и CDR выбирают поле указателя
CONS создает ячейку и возвращает на нее указатель
CONS создает ячейку и возвращает на нее указатель
Заметим, что применение функции CONS не изменило структуры списков,
Заметим, что применение функции CONS не изменило структуры списков,
У списков могут быть общие части
У списков могут быть общие части
Если элементами списка являются не атомы, а подсписки, то на месте
Если элементами списка являются не атомы, а подсписки, то на месте
Логически идентичные атомы содержатся в системе один раз, однако
Логически идентичные атомы содержатся в системе один раз, однако
_(car список1) (B С) _(cddr список1) (B С) являются логически
_(car список1) (B С) _(cddr список1) (B С) являются логически
Однако список (В С), как видно из следующего рис
Однако список (В С), как видно из следующего рис
Эту структуру можно создать с помощью следующей последовательности
Эту структуру можно создать с помощью следующей последовательности
Таким образом, в зависимости от способа построения логическая и
Таким образом, в зависимости от способа построения логическая и
Логическое и физическое равенство
Логическое и физическое равенство
Точечная пара соответствует списочной ячейке
Точечная пара соответствует списочной ячейке
На рис
На рис
Название точечной пары происходит из использованной в ее записи
Название точечной пары происходит из использованной в ее записи
_(саr '(а
_(саr '(а
Варианты точечной и списочной записей
Варианты точечной и списочной записей
Приведем пример: (a b(c d) e) (а
Приведем пример: (a b(c d) e) (а
_'(а
_'(а
Использование точечных пар в программировании на Лиспе в общем-то
Использование точечных пар в программировании на Лиспе в общем-то
Управление памятью и сборка мусора
Управление памятью и сборка мусора
Если списку СПИСОКЗ _(setq списокЗ) '((это станет мусором) cdr часть))
Если списку СПИСОКЗ _(setq списокЗ) '((это станет мусором) cdr часть))
Внутреннее представление списков
Внутреннее представление списков
Для повторного использования ставшей мусором памяти в Лисп-системах
Для повторного использования ставшей мусором памяти в Лисп-системах
Вычисления, изменяющие и не изменяющие структуру
Вычисления, изменяющие и не изменяющие структуру
RPLACA и RPLACD изменяют содержимое полей
RPLACA и RPLACD изменяют содержимое полей
Обе функции возвращают в качестве результата указатель на измененную
Обе функции возвращают в качестве результата указатель на измененную
Функция RPLACD выполняется так же, как RPLACA, с той разницей, что
Функция RPLACD выполняется так же, как RPLACA, с той разницей, что
Используя функцию RPLACD, можно, например, определить функцию КРУГ,
Используя функцию RPLACD, можно, например, определить функцию КРУГ,
Упражнения Нарисуйте следующие списки при помощи списочных ячеек и
Упражнения Нарисуйте следующие списки при помощи списочных ячеек и
Вычислите значения следующих выражений: (rplacd '(а) 'Ь) (rplaca '(а)
Вычислите значения следующих выражений: (rplacd '(а) 'Ь) (rplaca '(а)

Презентация на тему: «Внутреннее представление списков». Автор: Irene V. Grigorieva. Файл: «Внутреннее представление списков.ppt». Размер zip-архива: 160 КБ.

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

содержание презентации «Внутреннее представление списков.ppt»
СлайдТекст
1 Внутреннее представление списков

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

2 Лисповская память состоит из списочных ячеек Значение представляется

Лисповская память состоит из списочных ячеек Значение представляется

указателем CAR и CDR выбирают поле указателя CONS создает ячейку и возвращает на нее указатель У списков могут быть общие части Логическое и физическое равенство не одно и то же Точечная пара соответствует списочной ячейке Варианты точечной и списочной записей Управление памятью и сборка мусора Вычисления, изменяющие и не изменяющие структуру RPLACA и RPLACD изменяют содержимое полей ? Изменение структуры может ускорить вычисления

3 Лисповская память состоит из списочных ячеек

Лисповская память состоит из списочных ячеек

Оперативная память машины, на которой работает Лисп-система, логически разбивается на маленькие области, которые называются списочными ячейками. Списочная ячейка состоит из двух частей, полей CAR и CDR. Каждое из полей содержит указатель. Указатель может ссылаться на другую списочную ячейку или на некоторый другой лисповский объект, как, например, атом.

4 Указатели между ячейками образуют как бы цепочку, по которой можно из

Указатели между ячейками образуют как бы цепочку, по которой можно из

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

5 Графически списочная ячейка представляется прямоугольником (рис

Графически списочная ячейка представляется прямоугольником (рис

), разделенным на части (поля) CAR и CDR. Указатель изображается в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении другой ячейки или атоме, на которые ссылается указатель.

6 Значение представляется указателем

Значение представляется указателем

Указателем списка является указатель на первую ячейку списка. На ячейку могут указывать не только поля CAR и CDR других ячеек, но и используемый в качестве переменной символ, указатель из которого ссылается на объект, являющийся значением символа. Указатель на значение хранится вместе с символом в качестве его системного свойства.

7 Побочным эффектом функции присваивания SETQ является замещение

Побочным эффектом функции присваивания SETQ является замещение

указателя в поле значения символа. Например, следующий вызов: _(setq список '(а Ь с)) (А В С) создает в качестве побочного эффекта изображенную на рис. штриховую стрелку.

8 Графически ссылку на пустой список изображают в виде перечеркнутого

Графически ссылку на пустой список изображают в виде перечеркнутого

поля. Указатели из полей CAR ячеек списка ссылаются на структуры, являющиеся элементами списка, в данном случае на атомы А, В и С.

9 CAR и CDR выбирают поле указателя

CAR и CDR выбирают поле указателя

_(саг список) А _(cdr список) (В С)

10 CONS создает ячейку и возвращает на нее указатель

CONS создает ячейку и возвращает на нее указатель

Допустим, что у нас есть два списка: _(setq голова'(Ь с)) (В С) _(setqхвост '(a b с)) (А В С) Вызов функции _(cons голова хвост) ((В С) А В С) строит новый список из ранее построенных списков ГОЛОВА и ХВОСТ так, как это показано на рис.

11 Заметим, что применение функции CONS не изменило структуры списков,

Заметим, что применение функции CONS не изменило структуры списков,

являющихся аргументами, и не изменило значений переменных ГОЛОВА и ХВОСТ.

12 У списков могут быть общие части

У списков могут быть общие части

На одну ячейку может указывать одна или более стрелок из списочных ячеек, однако из каждого поля ячейки может исходить лишь одна стрелка. Если на некоторую ячейку есть несколько указателей, то эта ячейка будет описывать общее подвыражение. Например, в списке (кто-то приходит кто-то уходит) символ КТО-ТО является общим подвыражением, на которое ссылаются указатели из поля CAR из первой и из третьей ячейки списка.

13 Если элементами списка являются не атомы, а подсписки, то на месте

Если элементами списка являются не атомы, а подсписки, то на месте

атомов будут находится первые ячейки подсписков. Например, построенная вызовом _(setq список '((Ь с) a b с) ((В С) А В С) структура изображена на рис.

14 Логически идентичные атомы содержатся в системе один раз, однако

Логически идентичные атомы содержатся в системе один раз, однако

логически идентичные списки могут быть представлены различными списочными ячейками. Например, значения вызовов

15 _(car список1) (B С) _(cddr список1) (B С) являются логически

_(car список1) (B С) _(cddr список1) (B С) являются логически

одинаковым списком (В С), хотя они и представлены различными cписочными ячейками: _(equal (car список1) (cddr список1)) Т

16 Однако список (В С), как видно из следующего рис

Однако список (В С), как видно из следующего рис

, может состоять и из тех же ячеек.

17 Эту структуру можно создать с помощью следующей последовательности

Эту структуру можно создать с помощью следующей последовательности

вызовов: _(setq bс ‘(b c)) (В С) _(setq abc (cons 'a bc)) (ABC) _(setq список2 (cons bc abc)) ((В С)А В C) _Список2 ((В С)А В C)

18 Таким образом, в зависимости от способа построения логическая и

Таким образом, в зависимости от способа построения логическая и

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

19 Логическое и физическое равенство

Логическое и физическое равенство

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

20 Точечная пара соответствует списочной ячейке

Точечная пара соответствует списочной ячейке

Определяя базовую функцию CONS, мы предполагали, что ее вторым аргументом является список. Это ограничение не является необходимым, так как при помощи списочной ячейки можно было бы, например, результат вызова (cons 'а 'Ь) представить в виде структуры, изображенной на рис.

21 На рис

На рис

показан не список, а более общее символьное выражение, так называемая точечная пара. Для сравнения на следующем рис. мы изобразили список (А В).

22 Название точечной пары происходит из использованной в ее записи

Название точечной пары происходит из использованной в ее записи

точечной нотации, в которой для разделения полей CAR и CDR используется выделенная пробелами точка: _(cons 'а 'b) (А . В) Выражение слева от точки (атом, список или другая точечная пара) соответствует значению поля CAR списочной ячейки, а выражение справа от точки - значению поля CDR. Базовые функции CAR и CDR действуют совершенно симметрично:

23 _(саr '(а

_(саr '(а

b)) ; обратите внимание на А ; пробелы, выделяющие точку _(cdr '(а . (b . с))) (В . С) Точечная нотация позволяет расширить класс объектов, изображаемых с помощью списков.

24 Варианты точечной и списочной записей

Варианты точечной и списочной записей

Любой список можно записать в точечной нотации. Преобразование можно осуществить (на всех уровнях списка) следующим образом: (al a2 ... aN) ? (al . (a2 . ...(aN . NIL)...))

25 Приведем пример: (a b(c d) e) (а

Приведем пример: (a b(c d) e) (а

(b . ((с . (d . NIL)) . (e . NIL)))) Признаком списка здесь служит NIL в поле CDR последнего элемента списка, символизирующий его окончание. Транслятор может привести записанное в точечной нотации выражение частично или полностью к списочной нотации. (al . (а2 аЗ)) ? (al a2 аЗ) (al . (а2 . аЗ)) ? (al a2 . аЗ) (al a2 . NIL) ? (al a2 . ())

26 _'(а

_'(а

(b .(с .(d))) (А В С D) _'((а Ь) .(Ь с)) ((А В) В С) . nil) (А) . (Ь .с)) (А В . С) _'((((nil .а) .b) . с) . d) ((((NIL . A) . В). С) . D)

27 Использование точечных пар в программировании на Лиспе в общем-то

Использование точечных пар в программировании на Лиспе в общем-то

излишне. Точечные пары применяются в теории. Часто с их помощью обозначают список заранее неизвестной длины в виде (голова . хвост) Точечные пары используются совместно с некоторыми типами данных и с ассоциативными списками.

28 Управление памятью и сборка мусора

Управление памятью и сборка мусора

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

29 Если списку СПИСОКЗ _(setq списокЗ) '((это станет мусором) cdr часть))

Если списку СПИСОКЗ _(setq списокЗ) '((это станет мусором) cdr часть))

(ЭТО СТАНЕТ МУСОРОМ) CDR ЧАСТЬ) присвоить новое значение _(setq списокЗ (cdr списокЗ)) (CDR ЧАСТЬ) то CAR-часть отделяется, поскольку указатель из атома СПИСОКЗ начинает ссылаться так, как это изображено на рисунке при помощи штриховой стрелки. Теперь уже нельзя через символы и указатели добраться до четырех списочных ячеек. Говорят, что эти ячейки стали мусором.

30 Внутреннее представление списков
31 Для повторного использования ставшей мусором памяти в Лисп-системах

Для повторного использования ставшей мусором памяти в Лисп-системах

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

32 Вычисления, изменяющие и не изменяющие структуру

Вычисления, изменяющие и не изменяющие структуру

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

33 RPLACA и RPLACD изменяют содержимое полей

RPLACA и RPLACD изменяют содержимое полей

Основными функциями, изменяющими физическую структуру списков, являются RPLACA (replace CAR) и RPLACD (replace CDR) которые уничтожают прежние и записывают новые значения в поля CAR и CDR списочной ячейки: (RPLACA ячейка значение-поля) (RPLACD ячейка значение-поля)

34 Обе функции возвращают в качестве результата указатель на измененную

Обе функции возвращают в качестве результата указатель на измененную

списочную ячейку. _(setq поезд ‘(паровоз1 А В C)) (ПАР0ВОЗ1 A B C) _(rplaca поезд 'паровоз2) (ПАР0В032 А В С) _поезд (ПАР0В032 A B C) _(грlаса (cdr поезд) 'тендер) (ТЕНДЕР В С) _поезд (ПАР0В032 ТЕНДЕР В С)

35 Функция RPLACD выполняется так же, как RPLACA, с той разницей, что

Функция RPLACD выполняется так же, как RPLACA, с той разницей, что

меняется значение поля CDR: _(rplacd поезд '(к l m)) (ПАР0В032 К L M) _поезд (ПАР0В032 К L М)

36 Используя функцию RPLACD, можно, например, определить функцию КРУГ,

Используя функцию RPLACD, можно, например, определить функцию КРУГ,

превращающую произвольный список в кольцо: _(defun круг (х) (делай-круг х х)) КРУГ _(defun делай-круг (х у) (cond ((null x) x) ((nail (cdr x)) (rplacd x у)) (t (делай-круг (cdr x) у)))) ДЕЛАИ-КРУГ (круг '(а b с))

37 Упражнения Нарисуйте следующие списки при помощи списочных ячеек и

Упражнения Нарисуйте следующие списки при помощи списочных ячеек и

стрелок: (а) (а (Ь (с) d)) (nil (Ь . с) . d) Почему значением (eq '(a b) '(a b)) будет NIL? Каковы будут значения выражений (RPLACA х х) и (RPLACD х х), если х = '(а Ь) х = '(а) и оба аргумента состоят из различных ячеек? Как изменятся значения, если аргументы будут физически идентичны?

38 Вычислите значения следующих выражений: (rplacd '(а) 'Ь) (rplaca '(а)

Вычислите значения следующих выражений: (rplacd '(а) 'Ь) (rplaca '(а)

'Ь) (rplacd (cddr '(а Ь х)) 'с) (rplacd '(nil) nil) (rplacd '(nil) '(nil)) Что делает следующая псевдофункция: (defun бесполезная (х) (cond ((null x) x) (t (rplacd х (бесполезная (cdr x))))))

«Внутреннее представление списков»
http://900igr.net/prezentacija/informatika/vnutrennee-predstavlenie-spiskov-190582.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Работа в Word > Внутреннее представление списков