리스프 리스트 데이터 타입 Common Lisp: LIST - the most versatile data type (1)

Common Lisp: LIST - the most versatile data type (1)

Designed by Freepik

Lisp’라는 언어의 이름이 List Processor 에서 온 것처럼 리스트는 중심적인 데이터 타입으로, 다용도의 데이터 타입이다. 앞으로 몇 차례에 걸쳐 리스프의 리스트 데이터 타입에 대해 알아본다. 

1. 리스트의 표현방식

---

리스트는 출력형과 내부형 2가지 형태로 표현될 수 있다. 출력형에서 리스트는 괄호 안에 포함된 아이템의 묶음을 의미한다. 그리고 그 아이템은 리스트의 원소라고 부른다. 몇 가지 예를 살펴보면 다음과 같다. 

(RED GREEN BLUE)

(AARDVARK)

(2 3 5 7 11 13 17)

(3 FRENCH HENS 2 TURTLE DOVES 1 PARTRIDGE 1 PEAR TREE)

이에 반해 내부형에는 괄호가 포함되어 있지는 않다. 컴퓨터의 메모리 안에서 리스트는 cons cells (아래 이미지 박스)의 연결로 이루어진다. cons cells은 포인터(아래 화살표)에 의해 연결이 된다. 

각각의 cons cell은 2개의 포인터를 갖는다. 그 중 하나는 리스트의 원소를 가리키고, 다른 하나는 체인에 있는 그 다음 cons cell 을 가리킨다. 아래의 두 문장은 같은 의미이다. 

‘‘lists may include symbols or numbers as elements,’’ 

〓

"cons cells may contain pointers to symbols or numbers, as well as pointers to other cons cells."

(RED GREEN BLUE) 리스트의 경우를 살펴보면 다음과 같다.

●	●	→	●	●	→	●	●	→	NIL
↓			↓			↓
RED			GREEN			BLUE

가장 오른쪽 셀을 보면, cons cell 체인이 NIL 로 끝나는 것을 알 수 있다. 이것은 리스프의 관행이다. 물론 괄호를 이용해 표현하는 경우 체인의 끝에 위치한 NIL 은 생략된다. 

2. 심볼과 하나의 원소로 이루어진 리스트는 같은 것이 아니다. 

---

다음과 같은 리스트를 고려해보자. cons cell 의 하나의 포인터는 AARDVARK 라는 심볼을 가리키고 있고, 다른 하나는 NIL 을 가리키고 있다. 그러므로 (AARDVARK) 라는 리스트와 AARDVARK 라는 심볼은 서로 다른 것임을 알 수 있다. (AARDVARK) 는 AARDVARK 를 가리키는 cons cell 이다. 

(AARDVARK) 

●	●	→	NIL
↓
AARDVARK

3. 리스트는 다른 리스트를 원소로 가질 수 있다. 다음의 3개의 리스트를 살펴보자. 

---

(BLUE SKY)

(GREEN GRASS)

(BROWN EARTH)

위의 3개의 리스트들 전체를 또 다른 괄호로 묶어 하나의 리스트로 만들 수 있다. 결과는 다음과 같다. 괄호가 2단계로 되어 있음을 알 수 있다. 6개의 심볼로 이루어진 리스트가 아니라, 3개의 리스트로 이루어진 하나의 리스트인 것이다. 이를 중첩 리스트 nested list 라고 부른다.

((BLUE SKY) (GREEN GRASS) (BROWN EARTH))

위의 3개의 리스트를 수평으로, 또는 수직으로 나열해도 아무런 문제가 없다. 띄워쓰기와 들여쓰기는 문제가 되지 않는다. 다음과 같이 작성해도 무방한 것이다. 

((BLUE SKY)

 (GREEN GRASS)

 (BROWN EARTH))

해당 리스트의 첫 번째 요소는 여전히 (BLUE SKY) 이다. cons cell 표기법에 따르면, 위의 리스트는 다음과 같이 표현될 수 있다. 

최상단에는 3개의 원소를 가짐으로 3개의 cons cells 이 위치한다. 그리고 각각의 원소는 2개의 심볼을 가진 리스트이므로, 각각의 최상단 셀은 2개의 cons cells 로 구성된 하위 체인을 가리키게 된다. 

((BLUE SKY) (GREEN GRASS) (BROWN EARTH))

●

●

→

●

●

→

●

●

→

NIL

↓

↓

↓

●

●

→

●

●

→

NIL

●

●

→

●

●

→

NIL

●

●

→

●

●

→

NIL

↓

↓

↓

↓

↓

↓

BLUE

SKY

GREEN

GRASS

BROWN

EARTH

4. 중첩리스트 

---

cons cell 표기법에 따르면 nested list는 최상단 체인 아래에 최소한 하나의 cons cell 을 가진다. 중첩되지 않은 리스트는 보통 flat lists 라고 부른다. flat list 는 단 하나의 최상단 레벨의 cons cell 체인을 가진다. 그리고 리스트의 형태가 항상 동일한 것은 아니다. 아래는 리스트, 심볼, 리스트로 구성된 리스트의 예시이다. 

((BRAIN SURGEONS) NEVER (SAY OOPS))

5. 리스트의 길이는 리스트가 가지는 원소의 개수이다. 

---

예를 들어 (HI MOM) 의 경우 리스트의 길이 2이다. 그러면 리스트로 이루어진 리스트의 경우는 어떤한가? 예를 들어, 

(A (B C) D) 리스트의 원소는 A, (B C), 그리고 D 이다. 여기서 심볼 B 와 C 는 그 자체로 원소가 아니라, 원소 (B C)의 구성요소일 뿐이다. 

컴퓨터는 내부적으로 괄호를 쓰지 않는다는 것을 명심해야 한다. 컴퓨터의 관점에서 보자면 리스트 (A (B C) D) 는 3개의 원소를 가진다. 왜냐하면 내부적 표현에는 3개의 최상단 레벨의 cons cells 을 가지기 때문이다. 

6. 리스트의 길이는 포함된 원소의 복잡성 여부와는 무관하다.

---

리스트의 길이는 리스트가 가지는 원소의 복잡성 여부와는 무관하다. 그리고 LENGTH 함수는 기본적으로 리스트의 길이를 계산하는 것으로 심볼이나 숫자가 입력되면 오류를 발생하게 된다. 

7. 비어있는 리스트

---

구성요소가 없는 리스트는 empty list 라고 한다. 하나의 cons cells도 가지지 않는 것이다. 다음과 같이 안이 비어있는 괄호로 표현된다. 

( )

컴퓨터 내부에서는 NIL 이라는 심볼로 표현된다. 심볼 NIL 은 empty list이다. 그렇기 때문에 cons cell 체인의 마지막에 NIL을 사용하는 것이다. NIL 과 empty list 는 동일하므로, ( ) 대신에 NIL 을 사용해도 무방하다. 그러므로 (A NIL B) 는 (A ( ) B) 와 같이 표현할 수 있다. 

empty list 의 길이는 0 이다. 

NIL 이 심볼임에도 LENGTH 함수에서 유효한 입력으로 작용한다. 왜냐하면 NIL 역시 리스트이기 때문이다. NIL 이야말로 유일하게 심볼이면서 리스트인 것이다. 

8. 포인터를 통한 처리

---

리스트나 심볼같은 객체를 함수에 입력할 때, 실제 컴퓨터의 내부에서 처리는 포인터를 통해 이루어진다. 그러므로 실제로 입력되는 것은 객체 그 자체가 아닌 객체에 대한 포인터인 것이다. 마찬가지로 함수에 의해 반환되는 값 역시 포인터다. 

(THE BIG BOPPER) 라는 리스트가 REST 함수에 입력된다고 가정해보자. 실제 REST는 첫번째 cons cell 에 대한 포인터를 받게된다. REST 에 의한 결과값은 두 번째 cons cell -(BIG BOPPER) 리스트의 첫번째이기도 한-에 대한 포인터이다. 그러면 이 포인터는 어디에서 왔는가?

REST가 수행한 것은 첫번째 cons cell의 오른쪽 절반으로부터 포인터를 추출해내고, 그 포인터를 결과값으로 반환한 것이다. 그러므로 REST 실행의 결과는 같은 cons cell 체인의 포인터이다. REST에 의해 (BIG BOPPER) 리스트를 반환할 때 새롭게 생성된 cons cells 은 없다. 포인터를 추출하고 반환했을 뿐이다.