리습의 개발 방법을 배우자: 함수와 하위 함수의 개발

상위 함수에서 하위 함수를 구현해 나가는 것을 탑-다운 방식으로 설명하보겠다. 보통 큰 틀을 설계할 때는 탑-다운 방식이 적합하다.

2014/06/20 - [Programming/Functional] - 리습의 개발 방법을 배우자: 대도 웜퍼스 게임의 설계

2014/06/26 - [Programming/Functional] - 리습의 개발 방법을 배우자: 함수의 구현

이 게임의 배경이 되는 도시를 만든다. 주인공이 처음 방문한 도시이기 때문에 매 게임마다 새로운 도시를 만들어야 한다. [규칙 3.2] 새로운 도시를 만드는 것은 새 지도를 만드는 것이고, 지도라 함은 경로의 집합니다.

우리는 경로를 그래프로 표현한다. 경로의 끝이나 교차점을 노드라고 표현한다. 엣지는 경로의 최소 표현 단위로써, 두개의 노드를 가지고 있다. 이는 두 노드가 인접하여 연결되었음을 의미한다.

아래 그림은 노드 X, Y를 가지는 엣지를 그림으로 표현한 것이다.

이 게임에서 엣지의 양쪽 노드는 서로 각각 출발점과 도착점의 역활을 모두 가진다. 즉, 엣지 상에 두 노드는 이쪽에서 저쪽으로 또는 그 반대로도 이동이 가능하다. 이를 유향 그래프와 무향 그래프로 표현하면 다음과 같다.

• 유향 그래프(Directed Graph)로 표현. X에서 Y로 갈 수도 있고, Y에서 X로 갈 수도 있기 때문에, 항상 두개의 엣지가 필요하다.

  '((X Y) (Y X))

• 무향 그래프(Undirected Graph)로 표현. X와 Y를 가지는 하나의 엣지로 표현이 가능하다.

  '((X Y))

책의 저자는 유향 그래프의 표현을 선택했다. 논리의 간결함이 유향 그래프로 표현한 것이 더 낫기 때문이다. 예를 들면, K에서 갈 수 있는 노드를 구할 때 (K, A) (K, F) (K Z), ... 와 같이 맨 앞에 K가 있는지 확인하면 된다. 반면 무향 그래프는 (K, Z) 처럼 앞의 요소 뿐만 아니라 (A K)와 같이 뒤의 요소까지 살펴봐야 한다. 구체적인 구현을 보자면, 어떤 노드와 곧바로 연결된 노드를 구할 때, 유향 그래프는 REMOVE-IF-NOT^[각주:1]과 CAR로 쉽게 해결 할 수 있다. 무향 그래프라면 이보다 복잡하다.

어떤 표현 방식을 선택할지 결정했다. 이제 새로운 지도를 만들어보자. 임의의 경로의 목록을 생성하는 것부터 시작한다.

MAKE-EDGE-LIST

임의의 엣지 목록을 생성한다.[규칙 3.2] 엣지는 두 노드(지점)를 연결한 길을 의미한다.

1. 임의의 노드를 얻는다.
2. 두 쌍을 묶으면 하나의 유향 엣지가 된다. 경로는 양방 통행이 가능함으로 하나의 유향 엣지 (A B)에 대응하는 (B A)도 만든다.
3. 이 과정을 구하고자 하는 경로의 수만큼 반복하여 목록으로 엮는다.

(defparameter *node-num* 30)
(defparameter *edge-num* 45)

(defun random-node ()
  (1+ (random *node-num*)))

(defun edge-pair (a b)
  (unless (eql a b)
    (list (cons a b) (cons b a))))

;; generate random edges
(defun make-edge-list ()
  (apply #'append (loop repeat *edge-num*
                     collect (edge-pair (random-node) (random-node)))))

MAKE-NODE-LIST

전체 노드 목록을 만든다. 노드는 지도상에 존재하는 지점을 의미한다.

(defun make-node-list ()
  (loop for i from 1 to *node-num*
     collect i))

MAKE-EDGE-LIST로 임의로 일부 노드를 연결했기 때문에 모든 노드가 서로 연결되었다고 보장할 수 없다. 즉, 연결되지 않은 노드가 존재할 수 있다. 이는 모든 장소는 이동이 가능해야 한다는 [규칙 3.9]에 저촉된다.

CONNECT-ALL-ISLANDS

섬(islands)이란 개념이 등장한다. 섬은 서로 연결된 노드의 집합니다. 엣지 (A C) (C D) (D H) (B F) (F G)를 예를 들어보자. A에서 출발하여 여러 경로를 지나다보면 D에 다다를 수 있다. 이는, A와 D가 같은 섬에 있다는 것을 의미한다. A에서 갈 수 있는 노드는 D이외에도 C와 H가 있다. A가 속한 섬을 (A C D H)라고 표현할 수 있다. A에서 여러 경로를 충분히 지난다고 하더라도 절대로 G로는 갈 수 없다. 따라서 A와 G는 다른 섬에 있다. G가 속한 섬은 (B F G)이다.

섬이 2개 이상 존재한다는 것은 모든 장소는 이동가능하다는 규칙에 위배된다.

1. 노드 목록 (A B C D E F G H)와 엣지 목록((A C) (C D) (D H) (B F) (F G))으로
2. 섬 (A C D H) (B F G) (E)을 구하고
3. 이를 연결하여 하나의 섬 (A B C D E F G H) 로 만드는 함수를 만들자.

이 함수의 이름은 CONNECT-ALL-ISLANDS 이다.

(let ((edge-list (connect-all-islands (make-node-list) (make-edge-list))))

이제 본격적으로 CONNECT-ALL-ISLANDS를 구현해보자.

1. 지도의 모든 노드의 목록으로부터 섬을 찾는다.
2. 모든 섬에 다리를 놓는다^[각주:2]. 즉, 두 섬을 서로 연결한다.
3. 새로운 엣지(다리)의 목록을 기존 엣지에 포함한다.

;; find all islands and then connect them
(defun connect-all-islands (nodes edge-list)
  (append (connect-with-bridges (find-islands nodes edge-list)) edge-list))

;; find all islands
(defun find-islands (nodes edge-list)
  nil)

;; join all the islands together
(defun connect-with-bridges (islands)
  nil)

섬을 연결하려면 섬을 찾아야 한다. FIND-ISLANDS

FIND-ISLANDS

모든 섬을 찾는다.

1. 노드의 목록 중에 처음 것을 골른다. 찾는 섬의 첫번째 노드이다.
2. 이 노드와 연결된 모든 노드를 구한다. GET-CONNECTED. 즉, 이 노드가 속한 섬을 얻는다.
3. 노드의 목록에서 이 섬을 제외하면, 지금까지 조사된 섬과 연결되지 않은 노드 목록이 나온다. 이 목록에 위 과정을 반복한다.

;; find all nodes connected to a given node
(defun find-islands (nodes edge-list)
  (let ((islands nil))
    (labels ((find-island (nodes)
               (let* ((connected (get-connected (car nodes) edge-list))
                      (unconnected (set-difference nodes connected)))
                 (push connected islands)
                 (when unconnected
                   (find-island unconnected)))))
      (find-island nodes))
    islands))

(defun get-connected (node edge-list)
  nil)

인자로 주어진 노드가 속한 섬을 구하는 GET-CONNECTED를 구현해보자.

GET-CONNECTED

주어진 노드와 연결된 모든 노드를 구한다.

1. 주어진 노드와 직접적으로 연결된 노드 목록을 구한다. TRAVERSE
   이 노드를 첫번째 요소로 가지는 엣지를 찾는다. 이 엣지의 두번째 요소가 연결된 노드이다.
2. 새롭게 얻은 노드 중에 조사하지 않은-즉, 방문하지 않은 노드- 노드와 연결된 목록을 구한다. (TRAVERSE (CDR EDGE))
3. 연결 노드 중에 새로운 노드가 노드가 없을 때까지, 위 과정을 반복한다.

;; find all the edges in an edge list that start from a given node
(defun get-connected (node edge-list)
  (let ((visited nil))
    (labels ((traverse (node)
               (unless (member node visited)
                 (push node visited)
                 (mapc (lambda (edge)
                         (traverse (cdr edge)))
                       (direct-edges node edge-list)))))
      (traverse node))
    visited))

(defun direct-edges (node edge-list)
  (remove-if-not (lambda (x)
                   (eql (car x) node))
                 edge-list))

마지막으로, 이 섬에 다리는 놓으면 하나의 섬이 된다. CONNECT-WITH-BRIDGES

CONNECT-WITH-BRIDGES

섬을 서로 연결한다.

1. 첫번째 섬의 첫째 노드와 두번째 섬의 첫째 노드를 연결한다.
2. 두번째 섬과 세번째 섬을 서로 연결한다.
3. 나머지 섬에 대해서도 동일하게 처리한다.

(defun connect-with-bridges (islands)
  (when (cdr islands)
    (append (edge-pair (caar islands) (caadr islands))
            (connect-with-bridges (cdr islands)))))

이것으로 모든 노드들이 빠짐없이 서로 연결된 엣지 목록을 생성하는 기능을 구현했다.

1. "아닌 것을 제거한다."는 "맞는 것만 선택한다."의 의미로 치환된다. 그래서 `REMOVE-IF-NOT'을 `SELECT'라고 생각하면 편하다. [본문으로]
2. 예를 들면, 진도는 육지와 연결된 진도대교 때문에 더 이상 섬이 아니고 한반도에 포함되었다. 단지 하나의 다리만 있어도 충분하다. [본문으로]