АВТОМОБИЛЬ и CDR
В компьютерном программировании CAR ( car) / k ɑːr / и CDR ( cdr) ( / ˈ k ʌ d er / или / ˈ k ʊ d er / ) — примитивные операции над cons -ячейками (или «неатомарные S-выражения »), представленные в языке программирования Lisp . 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] в Лисп включены функции:
car(«содержимое адресной части номера реестра»),cdr(«содержимое декрементной части номера регистра»),cpr(«содержимое префиксной части номера регистра») иctr(«содержимое теговой части номера регистра»),
каждый из которых принимал адрес машины в качестве аргумента, загружал соответствующее слово из памяти и извлекал соответствующие биты.
704 макроса
[ редактировать ] 704 ассемблера Макрос для car был: [8] [9] [10]
LXD JLOC 4 # C( Decrement of JLOC ) → C( C ) # Loads the Decrement of location JLOC into Index Register C
CLA 0,4 # C( 0 - C( C ) ) → C( AC ) # The AC register receives the start address of the list
PAX 0,4 # C( Address of AC ) → C( C ) # Loads the Address of AC into Index Register C
PXD 0,4 # C( C ) → C( Decrement of AC ) # Clears AC and loads Index Register C into the Decrement of AC
Макрос ассемблера 704 для cdr был: [8] [9] [10]
LXD JLOC 4 # C( Decrement of JLOC ) → C( C ) # Loads the Decrement of location JLOC into Index Register C
CLA 0,4 # C( 0 - C( C ) ) → C( AC ) # The AC register receives the start address of the list
PDX 0,4 # C( Decrement of AC ) → C( C ) # Loads the Decrement of AC into Index Register C
PXD 0,4 # C( C ) → C( Decrement of AC ) # Clears AC and loads Index Register C into the Decrement of 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 используется не только для построения связанных списков, но и для построения парных и вложенных парных структур, т.е. cdr минус-ячейки не обязательно должны быть списком. В этом случае большинство других языков предоставляют разные примитивы, поскольку они обычно отличают парные структуры от списочных структур либо по типу, либо по семантике. В частности, в типизированных языках списки, пары и деревья будут иметь разные функции доступа с разными сигнатурами типов: в Haskell например, car и cdr становиться fst и snd при работе с парным типом. Точные аналоги car и cdr поэтому редки в других языках. Clojure Использование first вместо car и next или rest вместо cdr. Логотип , с другой стороны, использует first вместо car и butfirst вместо cdr.
Ссылки
[ редактировать ]- ^ См., например, Митчелл, Джон К. (2003), Концепции языков программирования , Cambridge University Press, стр. 28–29, ISBN 9781139433488 , Раздел 3.4, Инновации в разработке Lisp . В ссылке идентифицируется IBM 704 и правильно объясняются адрес и декрементная часть cons-ячейки, но затем в объяснении Маккарти опускается «часть».
- ^ Перейти обратно: а б 704 - электронная машина обработки данных http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf
- ^ Перейти обратно: а б Маккарти, Джон (12 февраля 1979 г.). «История Лиспа» .
- ^ Маккарти (1960 , стр. 26–27) обсуждает регистры в свободном списке и при сборке мусора.
- ^ Маккарти, Джон; Абрахамс, Пол В.; Эдвардс, Дэниел Дж.; Харт, Тимоти П.; Левин, Майкл И. (1985), Руководство программиста LISP 1.5 (второе изд.), Кембридж, Массачусетс: MIT Press, ISBN 978-0-262-13011-0 , стр. 36, описывает cons-ячейки как слова с 15-битными полями «адрес» и «уменьшение».
- ^ Язык обработки списков, скомпилированный на Фортране
- ^ Язык обработки списков, скомпилированный на Фортране; HTML-транскрипция
- ^ Перейти обратно: а б Отрывки из LISP-СТРАНИЦ NILS - http://t3x.dyndns.org/LISP/QA/carcdr.html.
- ^ Перейти обратно: а б Памятка 6 лаборатории MIT AI Lab https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf
- ^ Перейти обратно: а б КОДИРОВАНИЕ ДЛЯ КОМПЬЮТЕРА MIT-IBM 704 http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf
- Примечания
- Рассел, Стив . «Написание и отладка программ» (PDF) . РЛЭ и Вычислительный центр Массачусетского технологического института. Публикации CSAIL и цифровой архив (памятка). AI Памятка , нет. 6. Кембридж , Массачусетс: Лаборатория искусственного интеллекта Массачусетского технологического института . OCLC 35415961 . Архивировано из оригинала (PDF) 6 июля 2017 г. Проверено 20 июля 2017 г.
- Фаасе, Франс (10 января 2006 г.). «Происхождение CAR и CDR в LISP» .
- Грэм, Пол (1996). ANSI Common Lisp . Прентис Холл. ISBN 978-0-13-370875-2 .
- Барски, Конрад (2010). Land of Lisp: научитесь программировать на Lisp, по одной игре за раз! . Сан-Франциско, Калифорния: ISBN No Starch Press, Inc. 978-1-59327-281-4 .
- Маккарти, Джон (1960). «Рекурсивные функции символьных выражений и их машинное вычисление, Часть I». (PDF) . Коммуникации АКМ . 3 (4). ACM Нью-Йорк, Нью-Йорк, США: 184–195. дои : 10.1145/367177.367199 . S2CID 1489409 .