Лекции в ворде (1086314), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

$ (if (eq (* 2 3) 6) 'true 'false)

T ;true

$(if (eq (+ 2 3) 6) 'true 'false)

NIL ;false

(COND (p1 a1),(p2 a2),...,(pN aN))

Здесь pi – предикат; аi – s-выражение. Эта функция выполняется следующим образом:

• Последовательно слева направо вычисляются предикаты pi до тех пор, пока не будет получена истина.

• Вычисляется аi выражение, соответствующее этому истинному предикату, и это значение

• Если среди pi нет истинного предиката, то значение COND – NIL.

• Если истинному предикату pi соответствует пустое тело аi выражения, то COND возвращает значение предиката.

• Если предикату соответствует несколько выражений, то при его истинности выражения вычисляются слева направо и результатом функции COND будет значение последнего выражения последовательности (неявный PROGN).

Пример:

$ (setq num -3)

-3

$ (setq sign (cond ((plusp num) 'positive)

((minusp num) 'negative)

((zerop num) 'zero)

('nonnumber) ) )

NEGATIVE

• LOOP [form1,form2,...,formN]

(LOOP форма1 ... формаN) повторно вычисляет формы в последовательном порядке до тех пор, пока не встретится неявный COND с предикатом, не равным NIL. Затем LOOP вычисляет тело неявного COND и возвращает результат.

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

Пример:

$(setq num 5)

5

$ (loop ((zerop num)) ;неявный СОND – условие завершения цикла

(prin1 num) ;вывод без перевода на новую строку

(spaces 2) ; два пробела

(print (*num num)) ; вывод квадрата числа и перевод

(decq num) ) ; курсора на новую строку. decq –

;встроенная функция. Уменьшает

; значение аргумента на 1

*Результаты вычислений*

5 25

4 16

3 9

2 4

1 1

T

Упражнения

1. Определить функцию ПАРЫ(lst), разбивающую список (a b c d ...) на пары ((a b) (c d)...). В определении использовать условную конструкцию cond.

2.Определить рекурсивную функцию произв(n, m), вычисляющую произведение двух положительных чисел суммированием n раз множимого m. В определении использовать условную конструкцию if: если n=1, то произведение=m, иначе произв((n-1), m)

1. Определить рекурсивную функцию power1(x n), вычисляющую n-ю степень числа х. В определении возведение в степень представляется умножением числа х на себя n раз: если n=1, то результат=х, иначе результат=х*power1((n-1),x).

2. Определить итеративную (с использованием циклической конструкции loop) функцию. power(x n), вычисляющую n-ю степень числа.

Тема 6. Внутреннее представление списков

Оперативная память машины, на которой работает Лисп-система, логически разбивается на маленькие области, называемые списочными ячейками (memory cell, list cell, cons cell или просто cons). Списочная ячейка состоит из двух частей – полей car и cdr. Каждое из полей содержит указатель. Указатель может ссылаться на другую списочную ячейку или на другой лисповский объект, например, на атом. Каждый определенный атом записан в определенном месте памяти машины лишь один раз.

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

Указатели между ячейками образуют цепочку, по которой можно из предыдущей ячейки попасть в следующую и так до атомарных объектов. Указателем списка является указатель на самую первую ячейку списка. На ячейку могут указывать не только поля CAR и CDR других ячеек, но и используемый в качестве переменной символ. Указатель символа ссылается на объект, который является значением символа. Указатель га значение хранится вместе с символом в качестве его системного свойства. Кроме значения системными свойствами могут быть определение функции, последовательность знаков, задающая внешний вид переменной (print name), выражение, определяющее пространство, в которое входит имя, -выражение и список свойств (property list)

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

Пример

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

(A B C)

В этом примере в качестве побочного эффекта функции setq является представление символа 'список' как указателя списка (штриховая стрелка). Перечеркнутое поле обозначает пустую ссылку, т е указатель ссылается на атом NIL.

Из этого рисунка становится понятным, что CAR и CDR выбирают поле указателя

Выясним, какой эффект создается при использовании функции CONS. Пусть создано два списка:

$ (setq голова '(b c))

(B C)

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

(A B C)

Объединим эти два списка с помощью функции CONS:

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

((В С) А В С)

CONS создает новую списочную ячейку. Содержимым левого поля станет значение первого аргумента вызова, а второго – значение второго аргумента. Ћ! Одна новая списочная ячейка может связать две большие структуры в одну новую. Это эффективно для создания структур и их представления в памяти.

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

Если элементами списка будут подсписка, а не атомы, то на месте атомов будут находиться первые ячейки подсписков:

$ (setq список1 '((b c) a b c)

((D C) A B C)

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

$ (car список1)

(B C)

$ (cddr список2)

(B C)

является логически одинаковым списком (В С), хотя и представлены различными списочными ячейками:

$ (equal (car список1)(cddr список1))

Т

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

$ (setq bc '( b c))

(D C)

$ (setq abc '(a b c))

(A B C)

$ (setq список2 (cons bc abc))

((B C) A B C)

$ список2

((B C) A B C)

Логически одинаковые списочные структуры список1 и список2 физически не одинаковы. Поэтому

$ (eq список1 список2)

NIL.

Ћ! Другой способ представления списочной ячейки – точечная пара.

Точечной паре соответствуют следующие эквивалентные записи и структура, приведенная на следующем рисунке: '(a . b) и (cons 'a 'b)

Для сравнения структура для списка (А В) будет выглядеть иначе:

В точечной нотации точкой выделяются поля car и cdr. Точка в точечной паре выделяется с двух сторон пробелами.

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

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

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

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

Результат отражен на следующем рисунке а). Теперь присвоим списку СПИСОК3 новое значение (рис. б):

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

(CDR ЧАСТЬ)

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

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

$ (cons 'a (list 'b))

(A B)

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

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

На структуры уже существующих выражений можно оказывать изменяющее воздействие. Функции, выполняющие такие действия,. Называют деструктивными. С помощью этих функций можно разрушить структуру и склеить ее по-новому. К числу таких функций относят RPLACA (replace car) и RPLACD (replace cdr). Эти функции изменяют физическую структуру списков, уничтожая прежние и записывая новые значения поля car и cdr списочной ячейки. Формат функций:

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

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

Пример.

$ (setq поезд '(паровоз1 A B C))

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

$ (rplaca поезд 'паровоз2)

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

$ (rplaca (cdr поезд) 'тендер)

(ТЕНДЕР В С)

$ (rplacd поезд '(k l m))

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

• Ускорение вычислений лисповских функций с помощью деструкторов.

Свойства функций-деструкторов могут повысить эффективность некоторых лисповских функций. Покажем на примере, как деструктивные свойства функции setq повышает эффективность функции append:

$ (setq начало '(a b))

Характеристики

Список файлов лекций