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

В результате вычислений в памяти могут возникать структуры, на которые потом нельзя сослаться. Это происходит в тех случаях, когда вычисленная структура не сохраняется с помощью SETQ или когда теряется ссылка на старое значение в результате побочного эффекта нового вызова SETQ или другой функции. Если, например, изображенному на рис.8 списку СПИСОК3

 

_(setq список3 ’((это станет мусором) cdr часть))

((ЭТО СТАНЕТ МУСОРОМ) CDR ЧАСТЬ)

присвоить новое значение

 

_(setq список3 (cdr список3))

(CDR ЧАСТЬ)

то CAR-часть как бы отделяется, поскольку указатель из атома СПИСОК3 начинает ссылаться так, как это изображено на рисунке при помощи штриховой стрелки. Теперь уже нельзя через символы и указатели добраться до четырех списочных ячеек. Говорят, что эти ячейки стали мусором.

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

 

_(cons ’a (list ’b))

(A B)

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

 

 

СПИСОК3

 

CDR ЧАСТЬ

 

 

ЭТО СТАНЕТ МУСОРОМ

 

 

Рис.8

 

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

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

 

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

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

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

Такие функции называют структуро-разрушающими (destructive), поскольку с их помощью можно разорвать структуру и склеить ее по-новому.

 

 

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

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

 

(RPLACA ячейка значение-поля); поле CAR

(RPLACD ячейка значение-поля); поле CDR

Первым аргументом является указатель на списочную ячейку, вторым – записываемое в нее новое значение поля CAR или CDR. Обе функции возвращают в качестве результата указатель на измененную списочную ячейку.

 

_(setq поезд ’(паровоз1 А В С))

(ПАРОВОЗ1 А В С)

_(rplaca поезд ’паровоз2)

(ПАРОВОЗ2 А В С)

_поезд

(ПАРОВОЗ2 А В С)

_(rplaca (cdr поезд) ’тендер)

(ТЕНДЕР В С)

_поезд

(ПАРОВОЗ2 ТЕНДЕР В С)

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

 

_(rplacd поезд ’(k l m))

(ПАРОВОЗ2 K L M)

_поезд

(ПАРОВОЗ2 K L M)

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

 

_(defun круг (х) (делай-круг х х))

КРУГ

_(defun делай-круг (x y)

(cond ((null x) x)

((null (cdr x)) (rplacd x y))

(t (делай-круг (cdr x) y))))

ДЕЛАЙ-КРУГ

_(круг ’(a b c))

(A B C A B C ….

Печатая это значение, интерпретатор зациклится.

В Коммон Лиспе поля списочной ячейки являются ячейками памяти, поэтому значения в них можно менять и с помощью обобщенной функции присваивания SETF. Функции RPLACA и RPLACD можно представить через функцию SETF следующим образом:

 

_поезд

(ПАРОВОЗ2 K L M)

_(setf (car поезд) ’паровоз3)

ПАРОВОЗ3

_поезд

(ПАРОВОЗ3 K L M)

_(setf (fourth поезд)’тормозной-вагон)

ТОРМОЗНОЙ_ВАГОН

_поезд

(ПАРОВОЗ3 K L ТОРМОЗНОЙ-ВАГОН)

_(setf (cdr поезд) nil)

NIL

_поезд

(ПАРОВОЗ3)