기사 전체를 통해 기사 원문의 구조, 각주, 코드 예제를 그대로 살리며 함수형 프로그래밍을 왜 배워야 하는지, 나이트 투어 문제를 예로 들어 Haskell와 wholemeal programming, 게으름, 상태 공간, 모듈성, 합성의 관점을 설명합니다.
“함수형 프로그래밍은 대체 왜 배워야 하죠?” — 내가 조교(티에이)로 있던 함수형 프로그래밍 강의에서 한 학생이 진지하게 했던 질문이다.
조금 배경 설명부터 하자. 겁먹은 얼굴의 학생들 앞에 서서 Haskell 기초를 복습하고 있다 보니, 온갖 낯선 개념들을 한꺼번에 쏟아내고 있다는 죄책감이 밀려오기 시작했다.1 재귀, 커링, 함수 합성, 대수적 데이터 타입 등등, 끝이 보이질 않는다. 그러다 보니 학생들에게 일종의 ‘탈출구’를 주는 게 자연스럽게 느껴졌다.
가령, 인생 내내 루프만 써 온 사람에게, 재귀만 가지고 어떻게든 버텨 보라고 하는 게 과연 가능한 일일까? 그래서 새로운 과제 공지를 할 때, 우리는 대략 이런 식의 힌트를 줬다.
먼저 파이썬 느낌의 의사코드로 풀어 보세요. 그리고 루프가 나올 때마다, 다음과 같이 꼬리 재귀 함수로 바꿀 수 있습니다…
그리고는 루프를 꼬리 재귀로 바꾸는 방법을 설명했다.2 그때 몇몇 학생들은 약간 안도한 표정으로 과제를 이어서 했다.
제출이 끝난 뒤 어느 날, 한 학생이 수업 후에 나에게 질문을 하러 왔다. 지금까지는 Haskell 쇼크 상태라 그런지 수업 밖에서 본 적이 거의 없는 학생이라 놀랐다. 학생이 이렇게 말했다. “우리가 한 게 그냥 파이썬 코드를 Haskell 문법으로 옮겨 쓴 거라면, 함수형 프로그래밍을 배우는 의미가 뭐예요?”
곰곰이 생각해 보니, 학생 말이 맞았다. 우리가 탈출구로 제시한 방식대로라면, 학생들은 과제를 문자 그대로 파이썬 코드를 Haskell로 기계 번역해서 풀 수 있었다. 새로운 문법 몇 개 빼면, 사실상 새로 배우는 건 거의 없었던 셈이다. 그건 아쉬운 일이다. Haskell과 함수형 프로그래밍으로부터 배울 수 있는 건 너무나 많고, 이런 기회를 날려 버리면 정말 손해니까.
더 잘할 수 있을까?
과제는 나이트 투어(knight's tour) 문제를 푸는 것이었다. 즉, 임의 크기의 체스판과 시작 위치가 주어졌을 때, 나이트가 체스판의 모든 칸을 정확히 한 번씩만 방문하도록 이동하는 경로를 찾는 문제다.
효율성이 이 연습의 목적은 아니었기 때문에, 학생들은 백트래킹을 이용해 정답 경로를 브루트 포스로 찾아도 괜찮았다. 당신이 학생이고 파이썬이 주력 언어라고 해 보자. 이 문제를 어떻게 풀겠는가?
아주 단순한 브루트 포스 시도의 핵심 함수는 대충 다음과 같을 수 있다.3
python# 1 def tour(n, visited, moves, pos): if len(visited) == n * n: # 2 return moves for knight_move in all_moves: # 3 (row, col) = pos (dx, dy) = knight_move.value # 4 next_row = row + dx next_col = col + dy next_pos = (next_row, next_col) # 5 if is_valid(n, visited, next_row, next_col): new_visited = visited + [next_pos] # 6 new_moves = moves + [knight_move] # 7 result = tour(n, new_visited, new_moves, next_pos) # 8 if result is not None: return result # 9 return None
여러 가지 이유로 그다지 좋은 코드는 아니다. 하지만 지금 중요한 포인트는 아니다. 어쨌든 (아주 느리게라도) 문제의 요구사항을 만족시키는 해를 구하고, 예시로 쓰기에는 충분하다. 이 코드가 하는 일을 정리해 보자.
tour는 재귀 함수(1)이며, 현재 상태를 인자로 받는다.
nvisitedmovespos종료 조건(2)이 있다. 지금까지 방문한 경로가 체스판 전체를 덮었다면, 경로 구성이 끝난 것이므로 지금까지 만든 moves를 반환한다.
그렇지 않다면, 모든 가능한 나이트 이동을 순회한다(3). 이 이동들은 별도의 enum으로 정의되어 있다.
각 이동에 대해, 다음에 방문할 칸을 계산한다(4).
새로운 칸이 유효하다면(5) — 즉, 체스판 범위 안에 있고 아직 방문하지 않은 칸이라면
새로운 위치를 방문한 칸 리스트에 추가하고(6), 해당 나이트 이동을 moves에 추가한다.4
그런 다음 업데이트된 상태로 tour를 재귀 호출한다(7).
재귀 호출이 성공적인 결과를 반환하면, 그 결과를 그대로 반환한다(8).
그렇지 않으면 이 시도는 백트래킹하고 다음 나이트 이동을 시도한다.
가능한 나이트 이동을 전부 시도했는데도 실패하면, 포기하고 None을 반환한다(9).
이 정도면 괜찮지만, 실제 과제는 Haskell로 풀어야 한다. 그렇다면 이 파이썬 해법이 무슨 소용일까?
물론, 구체적이고 올바른 해를 코드로 적어 보는 건 문제를 이해하는 데 큰 도움이 된다. 거기에, 루프를 재귀로 바꾸라는 힌트까지 줬기 때문에, 파이썬 코드를 Haskell로 옮기는 일은 상당히 기계적인 수준이 된다. 예를 들어 보자.5
haskelltour n visited moves row col = if length visited == n * n then Just moves -- 1 else go allMoves -- 2 where -- 3 go [] = Nothing go (knightMove : rest) = let (dx, dy) = moveValue knightMove nextRow = row + dx nextCol = col + dy nextPos = (nextRow, nextCol) in if isValid n visited nextRow nextCol then let newVisited = visited ++ [nextPos] newMoves = moves ++ [knightMove] result = tour n newVisited newMoves nextRow nextCol -- 4 in case result of Just solution -> Just solution Nothing -> go rest -- 5 else go rest -- 6
Haskell 문법에 익숙하다면, 이 코드는 원래 파이썬 코드와 거의 똑같이 보일 것이다. 몇 가지 차이점이 있지만, 대부분은 문법적인 것뿐이다.
None (혹은 일반적인 null)이 없기 때문에, Maybe로 감싸야 한다(1). 파이썬에 비해 문법이 조금 길어지긴 하지만 그 정도다.else (2)가 필요하고, 여기서 다음 단계의 로직을 호출한다.go라는 꼬리 재귀 함수(3)로 대체됐다. 바로 우리가 준 “루프를 재귀로 바꾸라”는 팁이다.Maybe를 다루려면 좀 더 많은 의식(boilerplate)이 필요하므로, 패턴 매칭(4)을 사용한다.go를 명시적으로 호출해야 한다(5, 6).이제, 파이썬 스케치를 기반으로 이런 Haskell 해법을 만들어 낸 학생의 입장이 되어 보자. 여기서 새로 배운 건 무엇인가?
널을 쓰지 않고도 코드를 짤 수 있다는 사실 정도는 배웠을지 모른다. 하지만 이 코드는 작기 때문에, 널이 없다는 사실의 영향이 크게 드러나지 않고, 문법적인 잡음이 조금 늘어난 것에 가까워 보인다.6 게다가 널이 없는 건 함수형만의 특권도 아니다. 예컨대 Rust도 널을 쓰지 않는다.
표현식 중심이라는 점이 슬쩍 보이기도 한다. 이건 굉장히 깊고 영향력 큰 원칙이다. 하지만 여기서는 파이썬에서 기계적으로 옮겨 왔기 때문에, 그 의미를 놓치기 쉽다. 특히 이런 “작은” 코드 조각에서는 표현식 중심이 어떤 결과를 가져오는지 체감하기가 어렵다.
마지막으로, 반복을 단순 재귀로 바꿀 수 있다는 걸 배웠다. 멋지긴 한데, 그게 무슨 소용인가? for 루프도 잘만 돌아가는데, 굳이 재귀를 쓰는 건 이미 잘 알고 있는 걸 더 번거로운 (그리고 과하게 일반적인) 문법으로 표현하는 느낌일 수도 있다.
이 해법을 제출하고 나면, “그래서 이게 무슨 의미가 있지?”라는 생각이 드는 것도 무리는 아니다.
화면을 보고 “아니야, 함수형 프로그래밍은 배울 가치가 있어, 그냥 문법만 다른 파이썬이 아니야”라고 말하고 있을지도 모른다. 맞다. 지금 다루고 있는 이런 단순한 과제만 가지고도, 배울 수 있는 건 무척 많다.
하지만 이런 이점을 얻으려면, 우리가 익숙한 “주류” 프로그래밍 사고에서 벗어나려고 노력해야 한다. 기존 방식을 새 문법으로 번역하는 데서 멈추면 안 된다. 문제와 해법을 바라보는 방식 자체를 바꿔야 한다.
이런 나이트 투어 같은 문제에서는, 이른바 “wholemeal programming”이라 불리는 접근이 좋은 선택 중 하나다.
함수형 언어는 wholemeal programming에 탁월하다. 이 용어는 Geraint Jones가 만들었다. Wholemeal programming은 크게 생각하는 것을 의미한다. 요소 하나하나의 시퀀스 대신 리스트 전체로 작업하기; 개별 해답 대신 해답 공간 전체를 구성하기; 단일 경로가 아니라 그래프 전체를 상상하기. 이러한 wholemeal 접근은 종종 새로운 통찰을 주거나 문제에 대한 새로운 관점을 제공한다. 이는 projective programming이라 불리는 아이디어와도 잘 어울린다. 먼저 더 일반적인 문제를 풀고, 그 후 그 일반 프로그램을 보다 특수한 형태로 변형하면서 흥미로운 부분들을 뽑아내면 된다.
그러니 해 공간을 한 단계씩 탐색하는 대신, 전체 해답 공간의 리스트를 한 번에 만들어 보고, 그 리스트를 이용해 우리가 관심 있는 문제를 풀어 보자. 그러면 분명 프로그래밍과 문제 해결에 대해 새로운 걸 배울 기회가 생길 것이다.
제일 먼저 부딪히는 문제는 이것이다. 전체 해답 공간을 어떻게 표현할까? 엄청나게 클 수도 있는데? 운 좋게도 Haskell은 기본이 게으른 평가(lazy evaluation)라, 마치 전체 리스트를 전부 갖고 있는 것처럼 생각해도, 실제로는 필요할 때만 계산된다.
다음으로, 이제 상태 공간(state space)을 다루기로 했으니, 실제로 다루게 될 상태가 무엇인지 정해야 한다.
투어 중인 단일 상태를 다음 레코드로 표현할 수 있다.7
haskelldata TourState = TourState { board :: Board , visited :: [KnightPos] , moves :: [KnightMove] , current :: KnightPos }
이는 기본적으로, 원래 tour 함수의 인자들을 하나의 레코드로 묶어 둔 것과 같다(좀 더 깔끔한 래퍼 타입들을 사용하긴 했다).8
상태 공간을 탐색하려면, 상태들 사이를 옮겨 다닐 방법이 필요하다. 이를 위해 다음과 같이 정의할 수 있다.
haskellmoveState :: TourState -> KnightMove -> Maybe TourState
하나의 상태와 하나의 이동을 받아, 새로운 위치를 계산하고 이동 리스트를 갱신함으로써 다음 상태를 계산한다. 어떤 상태에서는 모든 이동이 합법적인 것은 아니므로, 실패 가능성을 Maybe로 표현한다. 다음 상태로 이동할 수 없다면 결과는 Nothing이다.
구현은 레포에서 볼 수 있지만, 기본 논리는 앞에서 봤던 것과 같고, 단지 TourState를 사용하도록 바꾸었을 뿐이다.
moveState가 있으면 한 이동을 한 상태에 적용할 수 있다. 다음으로, 한 상태에서 가능한 모든 나이트 이동을 시도해 보고 싶다. 그 시그니처는 다음과 같다.
haskellnextStates :: TourState -> [TourState]
주어진 TourState에서, 한 번의 이동으로 도달할 수 있는 모든 (합법적인) 상태들을 생성한다. 구현은 다음과 같다.
haskellnextStates state = mapMaybe (moveState state) allKnightMoves
가능한 모든 나이트 이동 리스트에 대해, 현재 상태에서 moveState를 적용하고, 그 결과들 중 Nothing인 항목은 mapMaybe가 제거해 준다. 그래서 최종적으로 도달 가능한 유효 상태들만 담긴 평평한(flat) 리스트를 얻는다.
이게 바로 wholemeal programming을 적용한 첫 예다. 한 단계씩 이동을 시뮬레이션하지 않았다. 개별 나이트 이동들을 순차적으로 따라가는 대신, 이동 리스트 전체에 mapMaybe를 적용해 이동 로직을 일괄적으로 적용했다.
이제 이 도우미 함수들을 가지고, 초기 상태에서 투어를 찾는 동안 우리가 거칠 수 있는 모든 상태들의 (잠재적으로) 무한한 리스트를 만들 준비가 되었다. 구체적으로는 다음 시그니처를 구현해야 한다.
haskellallStatesFrom :: TourState -> [TourState]
단일 상태가 주어지면, 그 상태에서 도달 가능한 모든 상태들의 리스트를 만든다.
무한한 단계 리스트를 만든다는 건 다소 위압적으로 들릴 수 있지만, 그냥 해 보자.
haskellallStatesFrom state = -- 1 let next = nextStates state -- 2 allTheRest = concatMap allStatesFrom next -- 3 in state : allTheRest -- 4
먼저 초기 state로부터 시작한다(1). 그리고 nextStates로 모든 합법적인 다음 상태들 next를 계산한다(2). 이것이 한 단계 앞까지의 탐색이다. 그다음에는 이 새 상태들 각각에서 다시 다음 단계를 밟고 싶다. 이를 위해 next의 각 원소에 대해 allStatesFrom을 재귀적으로 호출한다(3).9 concatMap은 이렇게 얻은 여러 리스트를 하나의 큰 리스트로 평탄화한다. 마지막으로, 초기 state를 더 깊은 단계들을 담은 allTheRest 앞에 붙여 전체 상태 리스트를 구성한다(4).
이렇게 해서, 우리가 풀고 있는 문제에서 발생 가능한 모든 상태를 표현하는 리스트를 하나 손에 넣었다. 약간 머리가 꼬일 수 있으니, 이 재귀가 어떻게 돌아가는지 잠시 곱씹어 보는 것도 좋다.
이 코드가 얼마나 “wholemeal”한지 눈여겨보자. 경계 조건이나 종료 조건을 직접 다루지 않는다. 그냥 전체를 한 번에 만들어 낸다. 또한 무한히 계속 나아가는 것 같아 보여도, Haskell의 게으름 덕분에 이 리스트는 필요해지기 전까지 실제로 계산되지 않기 때문에, “무한”해도 문제되지 않는다.10
이 리스트까지 만들어 놓으면, 나이트 투어 문제를 푸는 일은 거의 사소해진다. 리스트에서 체스판 전체를 덮는 첫 번째 상태만 찾으면 된다.
종료 조건은 다음과 같이 정의할 수 있다.
haskellisComplete TourState{board, visited} = boardSize board == length visited
이 함수는 방문한 위치 리스트의 길이를 확인해, 주어진 상태가 해답인지 판정한다(원래 파이썬 해법에서의 종료 조건과 동일하다).
이제 상태 리스트와 종료 조건이라는 두 개의 빌딩 블록을 갖고 있으니, 이들을 합성해서 단일 해법으로 만들 수 있다.
haskelltour :: Board -> KnightPos -> Maybe [KnightMove] tour board pos = -- 1 let -- 2 init = initState board pos -- 3 finalState = find isComplete (allStatesFrom init) in fmap getMoves finalState -- 4
단계별로 보면:
tour 함수는 체스판과 시작 위치를 인자로 받는다(1).TourState를 초기화하는 일이다.find를 사용해(3), 초기 상태에서 생성한 전체 상태 리스트 allStatesFrom init 안에서 isComplete를 만족하는 첫 번째 TourState를 찾는다.Maybe다)에서 이동 리스트만 추출한다(fmap getMoves).나는 이 접근이 숨 막힐 정도로 우아하다고 느낀다. 영감을 준 고전 논문인 “Why Functional Programming Matters”논문 덕분이기도 하다. 이 방식은 실제로 작동할 뿐 아니라, 완전히 새로운 것을 배울 기회를 우리에게 제공해 준다.
이렇게 이전 해법과 전혀 다른 접근을 택하면, 새로 배울 수밖에 없다. 여기에서 얻을 수 있는 교훈 몇 가지를 정리해 보자.
상태 리스트를 생성할 때 우리는 게으름을 본질적이고도 비인위적인(non-contrived) 방식으로 사용했다. 게으름이 없다면, 이 리스트는 메모리를 초과하거나, 미리 계산하는 데 너무 많은 시간이 걸려 “전체 상태 공간”을 실제로 만드는 것이 실용적이지 않을 수 있다.
Haskell의 내장 게으름 덕분에 이 모든 것이 (좋든 나쁘든) 눈에 띄지 않게 자연스럽게 일어난다. 하지만 여기서 얻는 교훈은 거의 어디서든 적용 가능하다. 게으름의 필요성을 인식하기만 하면, 현대 언어라면 거의 무엇이든 적절한 기법을 사용해 같은 효과를 얻을 수 있다. 파이썬에서는 제너레이터, 자바에서는 스트림/이터레이터, 기타 언어에서는 각종 스트리밍 라이브러리가 그 예다.
개념적 의미의 게으름은 어디서든 활용 가능한 강력한 도구다. Haskell의 게으른 리스트로부터 이런 감각을 길러 두면, 다른 환경에서 게으름을 도입하는 일이 훨씬 수월해진다.
상태 공간을 탐색하는 방식을 택하면서, 우리는 그 상태 공간 자체에 대해 곰곰이 생각할 수밖에 없었다. 가능한 상태들이 무엇인가? 상태들 사이를 어떻게 옮겨 다니는가?
이는 TourState 타입과 moveState 함수에 명시적으로 구체화(reify)되었다.
상태 공간은 우리가 의식하든 말든 항상 존재한다. 하지만 절차적인 사고로 코드를 생각할 때는 “나무만 보고 숲을 못 보는” 것이 훨씬 쉽다고 느껴진다. 반복 루프 안에서 각 단계에만 집중하면, 전체 상태 공간의 의미를 놓치기 쉽다.
함수형을 쓰든 말든, 상태 공간을 염두에 두는 건 무조건 유익하다. 대표적으로 “불법 상태를 표현 불가능하게 만들기” 같은 것만 생각해 봐도 그렇다.
상태 공간 탐색과 종료 조건을 분리함으로써, 우리는 코드를 이전보다 훨씬 더 모듈화할 수 있었다. 예전에는 종료 조건을 반복 로직 속에 직접 엮어 넣어야 했지만, 이제는 그럴 필요가 없다.
이런 종류의 모듈성 덕분에, 코드의 한 부분을 수정해도 다른 부분을 건드리지 않고도 되는 경우가 많아진다.
몇 가지 예를 들어 보자.
여기서 중요한 점은, 이런 변경들을 그 기능을 담당하는 코드 부분만 수정해도 가능하다는 것이다. 주변 코드에는 손댈 필요가 없다. 또한 각 부분을 서로 독립적으로 테스트할 수 있다.
반면 처음 파이썬/단순 Haskell 해법에서는, 뭔가를 고치거나 테스트하려면 전체 코드를 건드릴 수밖에 없었다. 종료 조건이 반복 로직 한가운데에 박혀 있었기 때문이다.
이 정도 수준의 모듈성을 절차적 코드에서 구현하려면 꽤 많은 노력이 들지만, wholemeal 접근 방식에서는 상당 부분 자연스럽게 흘러나온다.
모듈성과 짝을 이루는 개념이 바로 합성이다.11
코드를 여러 모듈로 나누는 것과, 그 모듈들을 다시 합쳐 실제 문제를 해결하는 단일 코드 조각으로 만드는 것이 얼마나 쉬운가는 완전히 별개의 문제다.
우리 예제에서는 이 과정이 매우 쉬웠다. 상태 공간 리스트와 종료 조건을 find 호출로 한데 묶기만 하면 됐다. 앞에서 언급한 여러 변형들에도 똑같이 적용된다. 서로 다른 구현들을 손쉽게 섞고 조합해, 새로운 동작을 하는 프로그램을 빠르게 만들어 낼 수 있다.
find 같은 고계 함수(higher-order function)를, 단순하고 순수한(혹은 부수효과 없는) 컴포넌트들을 이어 붙이는 접착제로 사용하는 건, 좋은 합성 특성을 가진 코드를 얻는 데 훌륭한 레시피다.
Tony Morris의 말을 인용해 보자.
가령 어떤 함수가 있다고 하자. 이 함수는 A, B, C, D라는 부분들로 이뤄져 있다고 가정하겠다. 이를 A ∘ B ∘ C ∘ D라고 적어 보자. 이제 A, B, C, E로 이뤄진 함수를 만들고 싶다고 하자. 그렇다면 새 함수에 드는 노력은 오직 E를 만드는 데 드는 노력에만 비례해야 한다.
어떤 함수에 대해서든, 이 목표에 얼마나 가까운지를 기준으로, 당신이 (순수) 함수형 프로그래밍의 본질에 얼마나 가까이 와 있는지 판단할 수 있다. 이 본질은 프로그래밍 언어와는 무관하게 존재하지만, 언어마다 이 목표를 얼마나 잘 뒷받침하는지는 크게 다를 수 있다.
명령형 프로그래밍 — 특히 파괴적 갱신(destructive update)의 스코프 — 은 이 목표의 정반대 지점에 있다.
이 모든 개념을 하나로 묶는 것이 바로 wholemeal programming이다. 문제를 완전히 다른 사고방식으로 다루는 법을 보여 준다.
이 접근은 단지 문제 해결 방식을 바꾸게 할 뿐 아니라, 우리가 만들어 내는 코드에 구체적이고 실용적인 이점을 가져다준다.
물론 이런 각각의 이점들은 다른 패러다임에서도 어느 정도 발견할 수 있다. 하지만 함수형 프로그래밍은 이런 이점들이 훨씬 더 분명하게 드러나게 만들어 준다. 한 번 이 개념들을 제대로 배우고 나면, 사실상 어디서든 활용할 수 있다. 다만, 기존 지식을 기계적으로 번역하는 습관을 멈추고, 지금까지 알고 있던 모든 것에서 한 발짝 떨어져 나올 필요가 있다.
그러면, 함수형 프로그래밍을 배우는 이유는 무엇일까? 이제는, 당신이 답해 볼 차례다…