В компьютерном программировании CAR ( car) / k ɑːr / иCDR(cdr) (/ ˈ k ʌ d ər / или/ ˈ k ʊ d ər / ) — примитивные операции надcons-ячейками (или «неатомарнымиS-выражениями»), введенные вязык программирования Lisp. Cons-ячейка состоит из двухуказателей;carизвлекает первый указатель, аcdrизвлекает второй.
Таким образом, выражение оценивается как , а оценивается как .(car (cons x y))x(cdr (cons x y))y
Когда cons-ячейки используются для реализации односвязных списков (а не деревьев и других более сложных структур ), операция car возвращает первый элемент списка, а cdr возвращает остальную часть списка. По этой причине операции иногда называют first и rest или head и tail .
Первоначально Lisp был реализован на компьютере IBM 704 в конце 1950-х годов.
Популярное объяснение, что CAR и CDR означают «Содержимое регистра адреса» и «Содержимое регистра декремента» [1] , не совсем соответствует архитектуре IBM 704; IBM 704 не имеет доступного программисту регистра адреса, а три регистра модификации адреса в IBM называются «индексными регистрами».
704 и его последователи имели 36-битную длину слова и 15-битное адресное пространство . Эти компьютеры имели два формата инструкций , один из которых, Type A, имел короткий 3-битный префикс кода операции и два 15-битных поля, разделенных 3-битным тегом. Первое 15-битное поле было адресом операнда, а второе содержало декремент или счетчик. Тег указывал один из трех индексных регистров . Индексирование было вычитательным процессом на 704, поэтому значение, которое должно было быть загружено в индексный регистр, называлось «декрементом». [2] : стр. 8 Аппаратное обеспечение 704 имело специальные инструкции для доступа к полям адреса и декремента в слове. [2] : стр. 26 В результате было эффективно использовать эти два поля для хранения в одном слове двух указателей, необходимых для списка. [3] : Введение.
Таким образом, «CAR» — это «Содержимое адресной части регистра». Термин «регистр» в данном контексте относится к «ячейке памяти». [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 ).
Префикс и тег были отброшены на ранних стадиях разработки Lisp, остались CAR, CDR и CONS с двумя аргументами. [3]
Композициямcar и cdrможно давать короткие и более или менее произносимые имена той же формы. В Lisp эквивалентно (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и т. д. Однако в Lisp ячейка cons используется не только для построения связанных списков, но и для построения парных и вложенных парных структур, т. е. cdrячейка cons не обязательно должна быть списком. В этом случае большинство других языков предоставляют другие примитивы, поскольку они обычно отличают парные структуры от списочных структур либо типизированно, либо семантически. В частности, в типизированных языках списки, пары и деревья будут иметь разные функции доступа с разными сигнатурами типов: например, в Haskellcar и cdrстановятся fstи sndпри работе с парным типом. Таким образом, точные аналоги carи cdrредки в других языках. Clojure использует firstвместо carи nextили restвместо cdr. Logo , с другой стороны, использует firstвместо carи butfirstвместо cdr.