В компьютерном программировании CAR ( car) / k ɑːr / ⓘ иCDR(cdr) ( / ˈ k ʌ d ər / ⓘ или / ˈ k ʊ d ər / ⓘ ) — примитивные операции надcons-ячейками (или «неатомарныеS-выражения»), введенные вязык программирования Лисп. Cons-ячейка состоит из двухуказателей; операцияcarизвлекает первый указатель, аcdr— второй.
Таким образом, выражение оценивается как , и оценивается как .(car (cons x y))x(cdr (cons x y))y
Когда cons-ячейки используются для реализации односвязных списков (а не деревьев и других более сложных структур ), операция car возвращает первый элемент списка, а cdr — остальную часть списка. По этой причине операциям иногда присваиваются имена first and rest или head and Tail .
Первоначально Lisp был реализован на компьютере IBM 704 в конце 1950-х годов.
Популярное объяснение, что CAR и CDR означают «Содержимое регистра адреса» и «Содержимое декрементного регистра» [1], не совсем соответствует архитектуре IBM 704; IBM 704 не имеет адресного регистра, доступного программисту, а три регистра модификации адреса в IBM называются «индексными регистрами».
704 и его преемники имеют длину слова 36 бит и адресное пространство 15 бит . Эти компьютеры имели два формата инструкций , один из которых, тип A, имел короткий 3-битный префикс кода операции и два 15-битных поля , разделенные 3-битным тегом. Первое 15-битное поле представляло собой адрес операнда, а второе содержало декремент или счетчик. Тег указывает один из трех индексных регистров . Индексирование на 704 было вычитающим процессом, поэтому значение, загружаемое в индексный регистр, называлось «декрементом». [2] : с. 8 Аппаратное обеспечение 704 имело специальные инструкции для доступа к полям адреса и уменьшения в слове. [2] : с. 26 В результате было эффективно использовать эти два поля для хранения в одном слове двух указателей, необходимых для списка. [3] : Введение.
Таким образом, «АВТОМОБИЛЬ» — это «Содержимое адресной части Реестра». Термин «регистр» в этом контексте относится к «ячейке памяти». [4] [5]
Предшественники [6] [7] Lisp включали функции:
car(«содержимое адресной части номера реестра»),cdr(«содержимое декрементной части номера регистра»),cpr(«содержимое префиксной части номера регистра») иctr(«содержимое теговой части номера регистра»),каждый из которых принимал адрес машины в качестве аргумента, загружал соответствующее слово из памяти и извлекал соответствующие биты.
Макрос ассемблера 704 для был: [8] [9] [10]car
LXD JLOC 4 # C( Декремент JLOC ) → C( C ) # Загружает декремент местоположения JLOC в индексный регистр C CLA 0 , 4 # C( 0 - C( C ) ) → C( AC ) # Регистр AC получает начальный адрес списка PAX 0 , 4 # C( Адрес AC ) → C( C ) # Загружает адрес AC в индексный регистр C PXD 0 , 4 # C( C ) → C( Уменьшение AC ) # Очищает AC и загружает индексный регистр C в декремент AC. Макрос ассемблера 704 для cdrбыл: [8] [9] [10]
LXD JLOC 4 # C( Декремент JLOC ) → C( C ) # Загружает декремент местоположения JLOC в индексный регистр C CLA 0 , 4 # C( 0 - C( C ) ) → C( AC ) # Регистр AC получает начальный адрес списка PDX 0 , 4 # C( Декремент AC ) → C( C ) # Загружает декремент AC в индексный регистр C PXD 0 , 4 # C( C ) → C( Декремент AC ) # Очищает AC и загружает индексный регистр C в декремент AC. Машинное слово можно было собрать с помощью cons , который принимал четыре аргумента ( a , d , p , t ).
Части префикса и тега были исключены на ранних этапах разработки Лиспа, оставив CAR, CDR и CONS с двумя аргументами. [3]
Составам и можно давать короткие и более или менее произносимые названия одной и той же формы car. cdrВ Лиспе (cadr '(1 2 3))это эквивалент (car (cdr '(1 2 3))); его значение 2. Точно так же (caar '((1 2) (3 4)))(произносится / ˈ k eɪ ɑːr / ) то же самое, что и (car (car '((1 2) (3 4)))); его значение 1. Большинство Lisp, например Common Lisp и Scheme , систематически определяют все варианты двух-четырех композиций carи cdr.
Многие языки (особенно функциональные языки и языки, находящиеся под влиянием функциональной парадигмы ) используют односвязный список в качестве базовой структуры данных и предоставляют примитивы или функции, аналогичные carи cdr. Они называются по-разному firstи rest, headи и tailт. д. Однако в Лиспе cons-ячейка используется не только для построения связанных списков, но также для построения парных и вложенных парных структур, т. е. cdrcons-ячейка не обязательно должна быть списком. В этом случае большинство других языков предоставляют разные примитивы, поскольку они обычно отличают парные структуры от списочных структур либо по типу, либо по семантике. В частности, в типизированных языках списки, пары и деревья будут иметь разные функции доступа с разными сигнатурами типов: например, в Haskellcar и cdrстановятся fstи sndпри работе с парным типом. Точные аналоги carand cdrпоэтому редки в других языках. Clojure использует firstвместо carи nextили restвместо cdr. Logo , с другой стороны, использует firstвместо carи butfirstвместо cdr.