SAMOCHÓD i CDR

W programowaniu komputerowym CAR ( samochód ) / k ɑːr / ( słuchaj ) i CDR ( cdr / k ʊ d ər ) / ( słuchaj ) ) to prymitywne ( / operacje k ʌ d ər / ( słuchaj ) lub na komórkach cons ( lub „nieatomowe wyrażenia S ”) wprowadzone w języku programowania Lisp . Komórka cons składa się z dwóch wskaźników ; operacja car wyodrębnia pierwszy wskaźnik, a operacja cdr wyodrębnia drugi.

Zatem wyrażenie (car (cons x y )) daje x , a (cdr (cons x y )) daje y .

Gdy komórki cons są używane do implementacji list pojedynczo połączonych (zamiast drzew i innych bardziej skomplikowanych struktur ), operacja car zwraca pierwszy element listy, podczas gdy cdr zwraca resztę listy . Z tego powodu operacjom czasami nadawane są nazwy najpierw i reszta lub głowa i ogon .

Etymologia

Lisp został pierwotnie zaimplementowany na komputerze IBM 704 pod koniec lat pięćdziesiątych.

Popularne wyjaśnienie, że CAR i CDR oznaczają „Zawartość rejestru adresowego” i „Zawartość rejestru dekrementacyjnego”, nie do końca pasuje do architektury IBM 704; IBM 704 nie ma rejestru adresowego dostępnego dla programisty, a trzy rejestry modyfikacji adresu są nazywane przez IBM „rejestrami indeksowymi”.

704 i jego następcy mają 36-bitową długość słowa i 15-bitową przestrzeń adresową . Komputery te miały dwa instrukcji , z których jeden, Typ A, miał krótki, 3-bitowy prefiks kodu operacji i dwa 15-bitowe pola oddzielone 3-bitowym znacznikiem. Pierwsze 15-bitowe pole było adresem operandu, a drugie zawierało ubytek lub liczbę. Znacznik określał jeden z trzech rejestrów indeksowych . Indeksowanie było procesem subtraktywnym w 704, stąd wartość do załadowania do rejestru indeksowego była nazywana „zmniejszeniem”. Sprzęt 704 miał specjalne instrukcje dostępu do pól adresu i dekrementacji jednym słowem. W rezultacie efektywne było użycie tych dwóch pól do przechowywania w jednym słowie dwóch wskaźników potrzebnych do utworzenia listy.

części adresowej rejestru”. Termin „rejestr” w tym kontekście odnosi się do „lokalizacji pamięci”.

Prekursory Lispa obejmowały funkcje:

samochód („zawartość części adresowej numeru rejestracyjnego”),
cdr („zawartość części dekrementacyjnej numeru rejestru”),
cpr („zawartość części przedrostkowej numeru rejestru”), oraz
ctr („zawartość części znacznika numeru rejestru”),

z których każdy przyjmował jako argument adres maszyny, ładował odpowiednie słowo z pamięci i wyodrębniał odpowiednie bity.

704 makr

Makro asemblera 704 dla samochodu to:

    
 0     
 0     
 0      LXD  JLOC  4  # C( Zmniejszenie JLOC ) → C( C ) # Ładuje Zmniejszenie położenia JLOC do rejestru indeksu C  CLA  ,  4  # C( 0 - C ( C ) ) → C ( AC ) # Rejestr AC otrzymuje adres początkowy listy  PAX  ,  4  # C( Adres AC ) → C( C ) # Ładuje adres AC do rejestru indeksowego C  PXD  ,  4  # C( C ) → C ( Dekrementacja AC ) # Czyści AC i ładuje Indeks Zarejestruj C do dekrementacji AC

Makro asemblera 704 dla cdr brzmiało:

    
 0     
 0     
 0      LXD  JLOC  4  # C( Zmniejszenie JLOC ) → C( C ) # Ładuje Zmniejszenie położenia JLOC do rejestru indeksu C  CLA  ,  4  # C( 0 - C ( C ) ) → C ( AC ) # Rejestr AC otrzymuje adres początkowy listy  PDX  ,  4  # C( Zmniejszenie AC ) → C ( C ) # Ładuje Zmniejszenie AC do Rejestru Indeksowego C  PXD  ,  4  # C( C ) → C ( Zmniejszenie AC ) # Czyści AC i ładuje Indeks Zarejestruj C do dekrementacji AC

Słowo maszynowe można było ponownie złożyć za pomocą cons , co wymagało czterech argumentów ( a , d , p , t ).

Części prefiksu i znacznika zostały usunięte na wczesnych etapach projektowania Lispa, pozostawiając CAR, CDR i dwuargumentowy CONS.

Kompozycje

Kompozycjom car i cdr można nadać krótkie i mniej lub bardziej wymawialne nazwy tej samej formy. W Lispie (cadr '(1 2 3)) jest odpowiednikiem (car (cdr '(1 2 3))) ; jego wartość wynosi 2 . Podobnie, (caar '((1 2) (3 4))) (wymawiane / ˈ k eɪ ɑːr / ) jest takie samo jak (samochód (samochód '((1 2) (3 4)))) ; jego wartość wynosi 1 . Większość Lispów, na przykład Common Lisp i Scheme , systematycznie definiuje wszystkie warianty dwóch do czterech kompozycji car i cdr .

Inne języki komputerowe

Wiele języków (zwłaszcza języki funkcjonalne i języki, na które ma wpływ paradygmat funkcjonalny ) używa pojedynczo połączonej listy jako podstawowej struktury danych i zapewnia prymitywy lub funkcje podobne do car i cdr . Są one nazywane różnie first i rest , head and tail , itp. Jednak w Lispie komórka cons jest używana nie tylko do budowania połączonych list, ale także do budowania par i zagnieżdżonych struktur par, tj. cdr komórki cons nie musi być lista. W tym przypadku większość innych języków zapewnia różne prymitywy, ponieważ zazwyczaj odróżniają one struktury par od struktur list albo typowo, albo semantycznie. Szczególnie w językach typowanych listy, pary i drzewa będą miały różne funkcje akcesorów z różnymi sygnaturami typów: na przykład w Haskell car i cdr stają się fst i snd , gdy mamy do czynienia z typem pary. Dokładne odpowiedniki car i cdr są zatem rzadkie w innych językach. Clojure używa first zamiast car i next or rest zamiast cdr.

Notatki

Russel, Steve . „Pisanie i debugowanie programów” (PDF) . Centrum obliczeniowe RLE i MIT. Publikacje CSAIL i archiwum cyfrowe (notatka). Notatka AI , nie. 6. Cambridge , Massachusetts: Laboratorium Sztucznej Inteligencji MIT . OCLC 35415961 . Zarchiwizowane od oryginału (PDF) w dniu 06.07.2017 . Źródło 20 lipca 2017 r .
Faase, Frans (2006-01-10). „Pochodzenie CAR i CDR w LISP” .
Graham, Paweł (1996). ANSI Common Lisp . Sala Prentice'a. ISBN 978-0-13-370875-2 .
Barski, Konrad (2010). Land of Lisp: naucz się programować w LISP, jedna gra na raz! . San Francisco, Kalifornia: No Starch Press, Inc. ISBN 978-1-59327-281-4 .
McCarthy, John (1960). „Rekurencyjne funkcje wyrażeń symbolicznych i ich obliczanie przez maszynę, część I”. (PDF) . Komunikaty ACM . ACM Nowy Jork, NY, USA. 3 (4): 184–195. doi : 10.1145/367177.367199 . S2CID 1489409 .