Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
Для использования в других целях, см CAR (значения) , CDR (значения) и CADR (значения) .

В компьютерном программировании , CAR ( car) / к ɑːr / ( слушать )Об этом звуке и CDR ( cdr) ( / к ʌ д ər / ( слушать )Об этом звуке или / к ʊ д ər / ( слушать )Об этом звуке ) примитивные операции на минусы клеток (или " неатомарные S-выражения "), представленные в языке программирования Lisp . Консольная ячейка состоит из двух указателей; автомобиля операция извлекает первый указатель, и корд операция извлекает второй.

Таким образом, выражение вычисляется и вычисляется как .(car (cons x y))x(cdr (cons x y))y

Когда cons-ячейки используются для реализации односвязных списков (а не деревьев и других более сложных структур ), операция car возвращает первый элемент списка, а cdr возвращает остальную часть списка. По этой причине операциям иногда дают имена сначала и rest или head и tail .

Этимология [ править ]

Изначально Лисп был реализован на компьютере IBM 704 в конце 1950-х годов.

Популярное объяснение, что CAR и CDR обозначают «содержимое регистра адреса» и «содержимое регистра декремента» [1] , не совсем соответствует архитектуре IBM 704; IBM 704 не имеет доступного программисту адресного регистра, а три регистра изменения адреса называются IBM "индексными регистрами".

704 и его последователи имеют длину слова 36 бит и адресное пространство 15 бит . У этих компьютеров было два формата инструкций , один из которых, Тип A, имел короткий 3-битный префикс кода операции и два 15-битных поля, разделенных 3-битным тегом. Первое 15-битовое поле было адресом операнда, а второе содержало декремент или счетчик. Тег определяет один из трех индексных регистров . Индексирование на 704 было вычитающим процессом, поэтому значение, загружаемое в индексный регистр, называлось «декрементом». [2] : с. 8 Аппаратное обеспечение 704 имело специальные инструкции для доступа к полям адреса и декремента одним словом. [2]: p. 26 В результате было эффективно использовать эти два поля для хранения в одном слове двух указателей, необходимых для списка. [3] : Введение.

Таким образом, «CAR» - это «Содержание адресной части реестра». Термин «регистр» в этом контексте относится к «ячейке памяти». [4] [5]

Предшественники [6] [7] Lisp включали функции:

  • car («содержимое адресной части номера регистра»),
  • cdr ("содержимое декрементной части номера регистра"),
  • cpr («содержимое префиксной части номера регистра»), и
  • ctr ("содержимое теговой части номера регистра"),

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

704 макроса [ править ]

Макрос ассемблера 704 для car: [8] [9] [10]

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могут быть даны короткие и более или менее произносимые названия одного и того же вида. В Лиспе (cadr '(1 2 3))это эквивалент (car (cdr '(1 2 3))); его ценность 2. Точно так (caar '((1 2) (3 4)))же, как (car (car '((1 2) (3 4)))); его ценность 1. Большинство Лиспов, например Common Lisp и Scheme , систематически определяют все вариации от двух до четырех композиций carи cdr.

Другие компьютерные языки [ править ]

Многие языки (особенно функциональные языки и языки, на которые влияет функциональная парадигма ) используют односвязный список в качестве базовой структуры данных и предоставляют примитивы или функции, подобные carи cdr. Они называются по-разному, firstи rest, headи tailт.д. В Лиспе, однако, cons-ячейка используется не только для построения связанных списков, но также для построения парных и вложенных парных структур, т.е.cdrcons-ячейки не обязательно должен быть списком. В этом случае большинство других языков предоставляют различные примитивы, поскольку они обычно различают парные структуры от структур списков либо типично, либо семантически. В частности, в типизированных языках списки, пары и деревья будут иметь разные функции доступа с разными сигнатурами типов: в Haskell , например, carи cdrстановиться fstи sndпри работе с парным типом. Точные аналоги carи cdrпоэтому редко встречаются в других языках.

Ссылки [ править ]

  1. ^ См., Например, Mitchell, John C. (2003), Concepts in Programming Languages , Cambridge University Press, стр. 28–29, ISBN. 9781139433488, Раздел 3.4, Нововведения в дизайне Lisp . Ссылка идентифицирует IBM 704 и правильно объясняет адрес и декремент части cons-ячейки, но затем опускает «часть» в объяснении Маккарти.
  2. ^ a b 704 - электронная машина обработки данных http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf
  3. ^ a b Маккарти, Джон (1979-02-12). «История Лиспа» .
  4. ^ Маккарти (1960 , стр. 26–27)обсуждает регистры в списке свободных номеров и в сборке мусора.
  5. ^ Маккарти, Джон; Abrahams, Paul W .; Эдвардс, Дэниел Дж .; Харт, Тимоти П .; Левин, Майкл И. (1985), Руководство программиста LISP 1.5 (второе издание), Кембридж, Массачусетс: MIT Press, ISBN 978-0-262-13011-0, стр. 36, cons-ячейки описаны как слова с 15-битными полями «адрес» и «декремент».
  6. ^ Язык обработки списков, скомпилированный на Фортране
  7. ^ Язык обработки списков, скомпилированный на Фортране; Транскрипция HTML
  8. ^ a b Отрывки из LISP PAGES NILS - http://t3x.dyndns.org/LISP/QA/carcdr.html
  9. ^ a b MIT AI Lab Memo 6 ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf
  10. ^ a b КОДИРОВКА для КОМПЬЮТЕРА MIT-IBM 704 ftp://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf
Ноты
  • Рассел, Стив . «Написание и отладка программ» (PDF) . Вычислительный центр RLE и MIT. Публикации и цифровой архив CSAIL (Memo). AI Memo , нет. 6. Кембридж , Массачусетс: Лаборатория искусственного интеллекта Массачусетского технологического института . OCLC  35415961 . Проверено 20 июля 2017 года .
  • Фазе, Франс (10 января 2006 г.). «Происхождение CAR и CDR в LISP» .
  • Грэм, Пол (1996). ANSI Common Lisp . Прентис Холл. ISBN 978-0-13-370875-2.
  • Барски, Конрад (2010). Land of Lisp: учитесь программировать на Лиспе, по одной игре за раз! . Сан-Франциско, Калифорния: ISBN No Starch Press, Inc. 978-1-59327-281-4.