CAR и CDR - CAR and CDR

Для использования в других целях, см 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 обозначают «содержимое регистра адреса» и «содержимое регистра декремента», не совсем соответствует архитектуре IBM 704; IBM 704 не имеет доступного программисту адресного регистра, и три регистра изменения адреса называются IBM "индексными регистрами".

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

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

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

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

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

704 макроса

Макрос ассемблера 704 для car: 

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: 

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 ).

Части префикса и тега были отброшены на ранних этапах разработки Lisp, оставив CAR, CDR и CONS с двумя аргументами.

Композиции

Композиции из 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поэтому редко встречаются в других языках. Clojure использует first вместо car и next или rest вместо cdr.

использованная литература

Примечания