Инструменты пользователя

Инструменты сайта


examination:flp:question36

Отличие между точечной и списочной нотациями в РС – Лиспе.

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

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

(nil cons 'a 'b)

представить в виде структуры, изображённой на рисунке.

  На рисунке показан не список, а более общее символьное выражение, так называемая точечная пара. Для сравнения на рисунке мы изобразили список (a b).

  Название точечной пары происходит из использованной в её записи точечной нотации, в которой для разделения полей first и rest используется выделенная пробелами точка:

(nil cons 'a 'b)

(a . b)   Выражение слева от точки (атом, список или другая точечная пара) соответствует значению поля first списочной ячейки, а выражение справа от точки - значению поля rest. Базовые функции first и rest действуют совершенно симметрично:

('(a . b) first) ; обратите внимание на пробелы, выделяющие точку

a

('(a . (b . c)) rest)

(b . c)   Точечная нотация позволяет расширить класс объектов, изображаемых с помощью списков. Ситуацию можно было бы сравнить с началом использования дробей или комплексных чисел в арифметике.

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

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

(a1 a2 … an) ≡ (a1 . (a2 . … (an . nil) … ))

  Приведём пример:

(a	b	(c	d)	e)
≡
(a	.	(b	.	((c	.	(d	.	nil))	.	(e	.	nil))))

  Признаком списка здесь служит nil в поле rest последнего элемента списка, символизирующий его окончание.   Транслятор может привести записанное в точечной нотации выражение частично или полностью к списочной нотации. Приведение возможно лишь тогда, когда поле rest точечной пары является списком или парой. В этом случае можно опустить точку и скобки вокруг выражения, являющегося значением поля rest:

(a1 . (a2 a3)) ≡ (a1 a2 a3) (a1 . (a2 . a3)) ≡ (a1 a2 . a3) (a1 a2 . nil) ≡ (a1 a2 . ())≡ (a1 a2)   Точка останется в выражении лишь в случае, если в правой части пары находится атом, отличный от nil. Убедиться в том, что произведённые интерпретатором преобразования верны, можно, нарисовав структуры, соответствующие исходной записи и приведённому виду:

>'(a  . (b  . (c  . (d))))
(a  b c d)
>'((a b)  . (b  c))
((a b)  b c)
>'(a  . nil)
(a)
>'(a  . (b  . c))
(a  b . c)
>'((((nil . a)  . b)  . c)  . d)
((((nil . a)  . b)  . c)  . d)

  Использование точечных пар в программировании на Лиспе в общем-то излишне. С их помощью в принципе можно несколько сократить объём необходимой памяти. Например структура данных

(a b c)

записанная в виде списка, требует трёх ячеек, хотя те же данные можно представить в виде

(a b . c)

требующем двух ячеек. Более компактное представление может несколько сократить и объём вычислений за счёт меньшего количества обращений в память.   Точечные пары применяются в теории, книгах и справочниках по Лиспу. Часто с их помощью обозначают список заранее неизвестной длины в виде:

(голова . хвост)

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

examination/flp/question36.txt · Последние изменения: 2014/01/15 08:17 (внешнее изменение)