Common Lisp: LIST - the most versatile data type (2)
1. CAR 과 CDR
cons cell의 두 부분은 모호한 이름을 가지고 있는데, 좌측 절반은 CAR, 그리고 우측 절반은 CDR (‘‘cou-der,’’라고 발음한다) 라고 불린다.
CAR 라는 명칭은 Contents of Address portion of Register를 의미하고, CDR은 Contents of Decrement portion of Register를 의미한다. 이런 용어가 현대 컴퓨터 하드웨어에는 적합하지는 않지만 Common Lisp 에서는 여전히 cons cells 을 언급할 때 CAR와 CDR이라는 축약어를 사용한다. 역사적인 이유도 있지만, 일부는 CADR나 CDDAR 등으로 확장이 용이하다는 측면도 있다.
CAR와 CDR은 셀의 CAR 또는 CDR에 들어있는 포인터를 반환해주는 리스프에 내장된 함수의 이름이기도 하다. (THE BIG BOPPER)라는 리스트를 다시 살펴보면, CAR 에 입력될 때 실제 받는 것은 리스트 그 자체가 아니라 첫 번째 cons cell을 가리키는 포인터이다.
2.
CAR는 실제 cons cell을 가리키는 포인터를 따라서 CAR 부분에 위치한 포인터를 추출해낸다. 따라서 결과값으로 CAR는 THE라는 심볼을 가리키는 포인터를 반환한다.
CDR은 cons cell을 가리키는 포인터를 따라간 뒤, CDR에 해당되는 부분에 위치한 포인터를 추출해 그것이 가리키는 부분을 반환한다. 그러므로 CDR의 결과값은 (BIG BOPPER)라는 리스트를 가리키는 포인터이다.
위의 예에서 보듯이 CAR은 FIRST와 같고, CDR은 REST와 같다. 리스프 프로그래머들은 보통 다음과 같이 표현한다. FIRST는 리스트의 CAR를 반환하고, REST는 CDR을 반환한다고 말이다.
3. 단일 원소 리스트의 CDR
앞서 우리는 (AARDVARK) 라는 리스트가 AARDVARK 라는 심볼과 동일하지 않음을 살펴봤다.
(AARDVARK) 라는 리스트는 다음과 같은 형태이다.
(AARDVARK)
● | ● | → | NIL | ||||||
↓ |
|
| |||||||
AARDVARK |
|
|
길이가 1인 리스트는 하나의 cons cell로 이루어져있다. 즉, 길이가 1인 리스트의 CDR은 길이가 0인 리스트인 NIL과 같다.
((PHONE HOME)) 이라는 리스트는 하나의 원소만 가지고 있다. 리스트의 원소는 최상위 레벨의 cons cells 이 가리키는 아이템을 의미하기 때문에 ((PHONE HOME))의 CAR은 (PHONE HOME)이고 CDR 은 NIL이다.
4. CAR 과 CDR 의 조합
(FEE FIE FOE FUM)의 첫 번째 원소는 FEE 이다.
두 번째 원소는 REST의 FIRST 또는 CDR의 CAR 이다.
(FEE FIE FOE FUM) | → | CDR | → | CAR | → | FIE |
|
| |
(FEE FIE FOE FUM) | → | CADR | → | FIE |
|
| |||
함수 박스를 왼쪽부터 읽으면 ‘CDR’ 그리고 ‘CAR.’로 읽게 된다. 하지만 CAR 함수에 대한 입력은 CDR 함수의 출력이기 때문에 보통 리스트의 'the CAR of the CDR’이라고 부른다. 리스프에서는 CADR 함수를 ‘the CAR of the CDR.’의 축약어로 이해한다. 그리고 CADR 는 ‘kae-der.’라고 발음한다.
(FEE FIE FOE FUM) | → | CDAR | → | error |
|
| |||
CDAR ('coudar’)함수는 리스트의 'the CDR of the CAR'이다. (FEE FIE FOE FUM)의 CAR은 FEE 이다. 이것의 CDR 은 호출하면 에러 메시지가 출력된다.
((FEE FIE) (FOE FUM)) | → | CDAR | → | (FIE) |
|
| |||
CADDR (‘ka-dih-der’) 함수는 리스트의 세번째 원소를 반환한다. 리스트의 'the CAR of the CDR of the CDR'이기 때문이다.
(FEE FIE FOE FUM) | → | CADDR | → | FOE |
|
| |||
CADDR이 어떻게 작동하는지 정확히 이해하기 위해서, A와 D를 오른쪽에서 왼쪽으로 읽어야 한다.
5. 중첩리스트의 CAR 과 CDR
((BLUE CUBE) (RED PYRAMID)) 의 CAR은 (BLUE CUBE) 이다.
BLUE 를 얻기 위해서는 CAR of the CAR, 즉 CAAR (‘ka-ar,’)를 사용하면 된다.
그러면 심볼 CUBE를 얻기 위해서는 어떻게 해야 하는가?
리스트의 CAR 포인터는 (BLUE CUBE)이고, 거기에 CDR 을 적용하면 리스트 (CUBE)를 가리킨다.
거기에 CAR를 적용하면 심볼 CUBE 를 얻게 된다.
따라서 CUBE 는 리스트의 CAR의 CDR의 CAR인 셈이다.
즉, CADAR (‘‘ka-dar’’) 이다.
그러면 심볼 RED는 어떻게 얻을 수 있는가?
RED 는 리스트의 SECOND의 FIRST 이다.
즉, CADR의 CAR이다. CAADR(‘ka-aeder.’)이다.
PYRAMID는 다음과 같이 구한다.
Step | Result |
start | ((BLUE CUBE) (RED PYRAMID)) |
C...DR | ((RED PYRAMID)) |
C..ADR | (RED PYRAMID) |
C.DADR | (PYRAMID) |
CADADR | PYRAMID |
6. NIL의 CAR 과 CDR
NIL의 CAR 과 CDR 은 NIL 로 정의된다. 예를 들어, (DING ALING) 리스트에서 THIRD 는 CADDR 이다.
(DING ALING)의 CDR은 (ALING)이고, (ALING)의 CDR은 NIL이다. 그리고 그것의 CAR는 NIL이다.
CONS 함수는 cons cells 을 생성한다.
2개의 입력을 받아서 하나의 새로운 cons cell에 대한 포인터를 반환한다.
A→ | CONS | →(A B C D) |
|
|
|
|
|
|
|
(B C D)→ |
|
|
|
|
|
|
|
CAR는 첫 번째 입력을 가리키고, CDR은 두 번째 입력을 가리킨다.
CONS 라는 용어는 CONStruct의 줄임말이다. CONS 는 리스트의 앞에 원소를 추가한다. 예를 들어, 리스트 (B C D) 앞에 심볼 A를 추가할 수 있다.
CONS가 어떤 역할을 하는지 제대로 이해하기 위해서는 cons cell 표기법을 알아둘 필요가 있다. CONS는 매우 간단한 함수이다. 모든 CONS 가 하는 것은 새로운 cons cell 을 생성해내는 것 뿐이다. 하지만 CONS에 대한 두 번째 입력이 n 이라는 길이를 가지는 cons cell 체인이라면, 새로운 cell 은 n+1 의 길이를 가지는 cons cell 체인의 헤드를 형성하게 된다. 아래 그림을 참고한다.
그러므로 CONS가 생성해낸 cell에 대한 포인터를 반환한다고 해도, 실제로는 두 번째 입력보다는 하나 더 긴 cons cell 을 반환하는 셈이다.
1) CONS는 새로운 cons cell 을 생성한다.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ● | ● | → | ● | ● | → | ● | ● | → | NIL |
|
|
|
| ↓ |
|
| ↓ |
|
| ↓ |
|
|
|
|
HELLO |
|
| THERE |
|
| MISS |
|
| DOOLITTLE |
|
|
| |
2) CAR 와 CDR 포인터를 채운다.
● | ● |
|
|
|
|
|
|
|
|
|
|
|
|
|
| ↘ |
|
|
|
|
|
|
|
|
|
|
|
↓ |
|
| ● | ● | → | ● | ● | → | ● | ● | → | NIL |
|
|
|
| ↓ |
|
| ↓ |
|
| ↓ |
|
|
|
|
HELLO |
|
| THERE |
|
| MISS |
|
| DOOLITTLE |
|
|
| |
3) CONS의 두 번째 입력보다 길이가 하나 더 긴 cons cell 체인의 head인 새로운 셀에 대한 포인터를 반환한다.
Result of CONS |
|
|
|
|
|
|
|
|
|
|
|
| |
↓ |
|
|
|
|
|
|
|
|
|
|
|
|
|
● | ● | → | ● | ● | → | ● | ● | → | ● | ● | → | NIL |
|
↓ |
|
| ↓ |
|
| ↓ |
|
| ↓ |
|
|
|
|
HELLO |
|
| THERE |
|
| MISS |
|
| DOOLITTLE |
|
|
| |
8. CONS 와 비어있는 리스트
NIL은 비어있는 리스트인 관계로, NIL에 CONS를 적용하면 하나의 원소를 가진 리스트를 얻게 된다.
(FROB)의 CAR는 심볼 FROB이고, (FROB)의 CDR은 NIL이다. 따라서 CONS 는 FROB 와 NIL로부터 (FROB) 라는 리스트를 얻게 되는 것이다. 출력 표기법에 따르면 NIL에 무언가를 콘싱한다는 것은 추가적인 괄호를 치는 것과 똑같다.
9. CONS 를 가지고 아무 것도 없는 상태에서 리스트를 만들 수 있다.
아무 것도 없는 상태에서 (FOO BAR BAZ)라는 리스트를 만들고자 한다면, CONS를 이용하여 원소를 하나씩 추가해나가면 된다. 먼저 비어있는 리스트에 심볼 BAZ 를 넣는다. 그러면 (BAZ) 라는 리스트가 생긴다. 그리고 거기에 BAR 를 추가한다. 마지막으로 FOO를 추가한다.
CONS 와 CAR/CDR 사이에는 흥미로운 대칭 관계가 있다.
x 라는 리스트가 있다고 하고, x의 CAR와 x의 CDR 을 알고 있다고 하면, 그 2가지를 CONS 함으로써 x가 무엇인지를 알아낼 수 있다. 예를 들어, 만약 x의 CAR 가 심볼 A라고 하고, x의 CDR이 (E I O U)라는 리스트라고 하면, x가 (A E I O U) 라는 리스트가 되어야한다는 것을 알 수 있다.
CONS 와 CAR/CDR 사이의 관계는 다음과 같이 표현할 수 있다.
x = CONS of (CAR of x) and (CDR of x)
하지만, 이 관계는 오직 비어있지 않은 리스트에만 적용된다.
x 가 NIL인 경우, x의 CAR와 CDR 역시 NIL이다. CAR와 CDR 부분을 콘싱함으로써 x를 재구축하고자 하면 - 즉, NIL 과 NIL 의 CONS - 비어있는 리스트인 NIL이 아닌 (NIL)이라는 리스트를 얻게 된다.
'프로그래밍 Programming' 카테고리의 다른 글
| 리스프 리스트 데이터 타입 Common Lisp: LIST - the most versatile data type (3) (0) | 2017.04.24 |
|---|---|
| LISP - CAR/CDR Pronunciation Guide (0) | 2017.04.24 |
| 리스프 리스트 데이터 타입 Common Lisp: LIST - the most versatile data type (1) (0) | 2017.04.22 |
| OSError : setuptools pip wheel failed with error code 1 (0) | 2017.04.14 |
| conda vs. pip vs. virtualenv (0) | 2017.04.13 |