CAR 및 CDR

CAR and CDR
기타 용도는 CAR(동음이의), CDR(동음이의) 및 CADR(동음이의)을 참조하십시오.

컴퓨터 프로그래밍에서 CAR (car) /kɑːr/ (듣기) 및 CDR (cdr) (/ˈkʌdər/ (듣기) 또는 /ˈkʊdər/ (듣기)는 리스프 프로그래밍 언어에 도입된 cons cell(또는 "비원자 S-expression")에 대한 원시 연산이다.conds cell은 두 개의 포인터로 구성되어 있다; 자동차 운행은 첫 번째 포인터를, cdr 운전은 두 번째 포인터를 추출한다.

그래서, 그 표현은(car (cons x y))로 평가하다.x그리고(cdr (cons x y))로 평가하다.y.

cdr이 (나무나 다른 더 복잡한 구조물보다) 단독 연계 리스트를 구현하기 위해 cons cell을 사용할 때, 자동차 운행은 목록의 첫 번째 요소를 반환하고, cdr은 나머지 목록을 반환한다.이 때문에 작전명칭이 먼저 주어지고 휴식이나 머리와 꼬리가 잡히기도 한다.

어원

Lisp는 원래 IBM 704 컴퓨터에서 1950년대 후반에 구현되었다.

CAR과 CDR이 "주소 레지스터의 콘텐트"와 "노후 레지스터의 콘텐트"[1]를 의미한다는 일반적인 설명은 IBM 704 아키텍처와 상당히 일치하지 않는다. IBM 704는 프로그래머 액세스 가능한 주소 레지스터가 없고 세 개의 주소 수정 레지스터를 IBM에 의해 "인덱스 레지스터"라고 불린다.

704와 그 후계자들은 36비트 단어 길이와 15비트 주소 공간을 가지고 있다.이들 컴퓨터에는 두 가지 명령 형식이 있었는데, 그 중 하나는 타입 A로 짧은 3비트 운영 코드 접두사였고, 두 개의 15비트 필드는 3비트 태그로 구분되어 있었다.첫 번째 15비트 필드는 피연산자 주소였고 두 번째 필드는 감소 또는 카운트를 유지했다.태그는 세 개의 인덱스 레지스터 중 하나를 지정했다.인덱싱은 704년도의 감산 프로세스였기 때문에 인덱스 레지스터에 로드되는 값을 "감소"라고 불렀다.[2]: p. 8 704 하드웨어에는 한 마디로 주소와 노쇠 필드에 접근하기 위한 특별한 지침이 적혀 있었다.[2]: p. 26 결과적으로 이 두 개의 필드를 사용하여 목록에 필요한 두 개의 포인터를 한 단어 안에 저장하는 것이 효율적이었다.[3]: Intro.

따라서 "CAR"은 "등록부의 주소 부분의 내용"이다.이 맥락에서 "등록"이라는 용어는 "기억 위치"[4][5]를 가리킨다.

Lisp에 대한 프리커서[6][7](precursors) 포함 기능:

  • 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 ( AC ) # AC 레지스터는 목록의 시작 주소를 수신한다. 팍스 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 ( AC ) # AC 레지스터는 목록의 시작 주소를 수신한다. PDX 0,4     # C(AC의 감소) → C(C) # AC의 감소를 색인 레지스터 C에 적재 PXD 0,4     # C( C ) → C(AC의 감소) # AC를 지우고 인덱스 레지스터 C를 AC의 감소에 로드

기계어는 네 가지 주장(a,d,p,t)을 필요로 하는 cons에 의해 다시 조합될 수 있었다.

접두사와 태그 부품은 리스프 디자인의 초기 단계에서 떨어졌고, CAR, CDR, 2개의 주장 ConES를 남겼다.[3]

구성

의 구성car그리고cdr동일한 형식의 짧고 거의 발음 가능한 이름을 부여할 수 있다.Lisp에서는(cadr '(1 2 3))와 같다(car (cdr '(1 2 3))); 그 가치는2비슷하게.(caar '((1 2) (3 4)))(pronounced /ˈkeɪɑːr/)와 같다.(car (car '((1 2) (3 4)))); 그 가치는1대부분의 Lisps는 예를 들어 Common Lisp과 Scheme과 같은 2-4개의 구성의 모든 변형을 체계적으로 정의한다.car그리고cdr.

기타 컴퓨터 언어

많은 언어(특히 기능적 언어와 기능적 패러다임의 영향을 받는 언어)는 기본 데이터 구조로 단독 링크된 목록을 사용하며, 다음과 유사한 원시 요소나 함수를 제공한다.car그리고cdr이것들의 이름은 다양하다.first그리고rest,head그리고tail, 등. 그러나 Lisp에서 cons cell은 링크된 리스트를 만드는 데만 사용되는 것이 아니라 쌍과 내포된 쌍 구조를 만드는 데에도 사용된다.cdr죄수들의 세포가 리스트가 될 필요는 없다.이 경우, 대부분의 다른 언어들은 전형적으로 또는 의미적으로 쌍 구조와 목록 구조를 구별하기 때문에 서로 다른 원시적 요소를 제공한다.특히 타이핑된 언어의 경우, 목록, 쌍 및 트리는 모두 다른 타입 시그니처를 가진 서로 다른 접근자 함수를 가질 것이다: 예를 들어, Haskell에서는,car그리고cdr되다fst그리고snd페어 타입을 다룰 때의 정확한 유사점car그리고cdr그래서 다른 언어에서는 드물다.Clojure는 자동차 대신 먼저 사용하고, cdr 대신 다음 또는 휴식을 사용한다.

참조

  1. ^ 예를 들어,Mitchell, John C. (2003), Concepts in Programming Languages, Cambridge University Press, pp. 28–29, ISBN 9781139433488, 섹션 3.4, Lisp 설계의 혁신.이 참고문헌은 IBM 704를 식별하고 동의 셀의 주소와 감소 부분을 올바르게 설명하지만, 매카시의 설명에서 "부분"은 생략한다.
  2. ^ a b 704 - 전자 데이터 처리기 http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf
  3. ^ a b McCarthy, John (1979-02-12). "History of Lisp".
  4. ^ McCarthy(1960, 페이지 26–27) 은 무료 목록과 가비지 수집에서 등록부를 논의한다.
  5. ^ McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985), LISP 1.5 Programmer's Manual (second ed.), Cambridge, Massachusetts: MIT Press, ISBN 978-0-262-13011-0, 36페이지에서는 cons cell을 15비트 "주소" 및 "주소" 필드가 있는 단어로 설명한다.
  6. ^ Fortran-Compiled 목록 처리 언어
  7. ^ Fortran-Compiled List-Processing Language, HTML 필사
  8. ^ a b NILS LISP Pages에서 일부 제공- http://t3x.dyndns.org/LISP/QA/carcdr.html
  9. ^ a b MIT AI 연구소 메모 6 https://web.archive.org/web/20170706114352/ftp:///publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf
  10. ^ a b MIT-IBM 704 COMPUTER http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf
메모들