A prettier printer
필립 와들러 Philip Wadler
조이스 킬머(Joyce Kilmer)뿐만 아니라 대부분의 컴퓨터 쟁이들은 "트리만큼 사랑스러운 시는 없다"는 데 동의할 것이다. 트리를 어찌나 사랑하는지 그것을 파싱하고 패턴매칭하고 가지치기하고... 그리고 출력하는데 사용한다. 프리티프린터(pretty printer)는 트리를 텍스트로 바꾸는 걸 도와주는 도구이자 라이브러리이다. 텍스트는 본래의 트리 구조를 반영하는 들여쓰기(indentation)를 유지하면서도 최소한의 길이로 표현된다. 좋은 프리티프린터는 사용상의 편의성과 출력 형식의 유연성을 취하면서도 최적의 형태로 출력할 수 있는 균형을 갖춰야 한다.
오랜 시간에 걸쳐 리차드 버드(Richard Bird) 등은 프로그래밍의 "대수(algebra)"를 정교한 예술 수준으로 발전시켰다. 존 휴즈(John Hughes)는 프리티프린터 라이브러리가 만들어지는 과정을 기술하면서 대수를 효과적으로 적용함으로써 설계와 구현이 더 견고해질 수 있었다고 설명했다.(1995) 이 라이브러리는 표준 패키지가 되었고 이 분야에서 널리 쓰이게 되었다. 사이먼 페이튼 존스(Simon Peyton Jones)가 GHC에 사용한 것도 이 라이브러리를 변형한 것이었다.(1997)
이 장에서는 새로운 프리티프린터 라이브러리를 보여줄 것이다. 휴즈가 설계한 라이브러리보다 더 향상되었다고 믿는다. 새 라이브러리는 문서(document)를 이어붙이는 방법이 하나뿐이다.(여기에는 왼쪽 항등원과 오른쪽 항등원이 있다.) 너무 당연게 보일 수도 있지만 다시 돌아보았을 때에만 분명하게 보일 수도 있다. 휴즈의 라이브러리는 문서를 이어붙이는 방법이 두 가지다. 수평 연결과 수직 연결. 수평 연결은 오른쪽 항등원이 있지만 왼쪽 항등원은 없으며, 수직 연결은 항등원이 없다. 여기서 제시하는 새 라이브러리는 휴즈의 것보다 30% 더 짧고 30% 더 빠르다.
명령형 스타일의 프리티프린터 중에는 데렉 오펜(Derek Oppen)의 것이 널리 쓰인다.(1980) 오펜의 것은 Caml의 프리티프린트 기술에 근간을 둔 것으로 보인다. 이 장에서 제시하는 프리티프린터는 오펜의 것과 동등한 알고리즘을 사용한다. 대신 명령형 스타일이 아니라 함수형 스타일로 보여줄 것이다. 휴즈와 오펜의 것과 더 자세히 비교한 내용은 결론에서 다룬다.
프리티프린터 라이브러리의 전체 코드는 이 장 끝에 있다.
1 단순한 프리티프린터
단순한 경우부터 시작해보자. 문서의 레이아웃이 단 한 가지만 가능한 경우를 단순한 문서라고 보자. 단순한 문서는 더 압축하여 한 줄로 줄일 필요가 없다. 이를 위해서는 다음 여섯 개의 연산자가 필요하다.
(<>) :: Doc -> Doc -> Doc
nil :: Doc
text :: String -> Doc
line :: Doc
nest :: Int -> Doc -> Doc
layout :: Doc -> String
<> 결합 연산자는 두 개의 문서를 이어붙인다. nil은 빈 문서를 의미하며 결합 연산자의 좌우 항등원이다. text 함수는 문자열을 해당 문서로 변환한다. line은 줄바꿈을 나타내는 문서이다. 대신 text 함수에 전달하는 문자열에는 줄바꿈 문자가 없다는 규칙을 따른다. 줄바꿈을 추가하려면 항상 line을 사용해야 한다. nest 함수는 문서에 들여쓰기를 추가한다. 마지막 layout 함수는 문서를 문자열로 변환한다. (실제로는 line처럼 동작하게 만들기 위해 줄바꿈 문자 하나로만 이뤄진 문자열을 이용하여 (text "\n")를 사용할 수도 있을 것이다.)
단순한 문서들을 나타내는 방법 중 하나는 문자열을 그대로 사용하는 것이다. <>는 문자열 연결(혹은 이어붙이기), nil은 빈 문자열, text는 항등함수, line은 줄바꿈 문자 하나로 된 문자열, nest i는 모든 줄바꿈 문자 뒤에 i 개의 공백문자(space)를 추가하는 함수, layout은 항등함수로 구현할 수 있다. 이 단순한 구현이 딱히 효율적이지는 않다. nest 함수의 경우 들여쓰기할 문서의 모든 문자들을 살펴봐야 하며 쉽게 일반화할 수도 없다. 좀더 대수적인(algebraic) 구현은 곧 살펴볼 것이다.
들여쓰기의 경우 오직 줄바꿈 문자가 있을 때만 발생한다는 점에 유의하자. 문자열의 앞부분을 들여쓰기 하지는 않는다. 휴즈의 프리티프린터를 잘 알고 있는 독자라면 이러한 결정이 다소 특이하다 생각할 것이다. 하지만 바로 이 결정 덕분에 이어붙이기 연산을 두 개가 아닌 하나로 처리할 수 있게 된다.
첫 번째 예로서 단순한 트리 자료 구조와 이 트리를 문서(document)로 변환하는 함수를 살펴보자.
data Tree = Node String [Tree]
showTree (Node s ts) = text s <> nest (length s) (showBracket ts)
showBracket [] = nil
showBracket ts = text "[" <> nest 1 (showTrees ts) <> text "]"
showTrees [t] = showTree t
showTrees (t:ts) = showTree t <> text "," <> line <> showTrees ts
이제 트리는 다음과 같은 형식으로 출력된다.
aaa[bbbbb[ccc,
dd],
eee,
ffff[gg,
hhh,
ii]]
또는 위 함수를 약간 변형하여 다음처럼 할 수도 있을 것이다.
showTree' (Node s ts) = text s <> showBracket' ts
showBracket' [] = nil
showBracket' ts = text "[" <>
nest 2 (line <> showTrees' ts) <>
line <> text "]")
showTrees' [t] = showTree' t
showTrees' (t:ts) = showTree' t <> text "," <> line <> showTrees' ts
이 함수를 이용하면 트리가 다음의 형식으로 출력된다.
aaa[
bbbbb[
ccc,
dd
],
eee,
ffff[
gg,
hhh,
ii
]
]
다른 형식으로 출력하도록 변형하는 것도 어렵지 않다.
모든 문서는 줄바꿈과 들여쓰기를 반복하는 다음의 형태로 정규화할 수 있다.
text s0 <> nest i1 line <> text s1 <> ... <> nest ik line <> text sk
s0, s1, ... 는 문자열이고 i1, i2, ... 는 0 또는 자연수다. 예를 들어 다음 문서는...
text "bbbbb" <> text "[" <>
nest 2 (
line <> text "ccc" <> text "," <>
line <> text "dd"
) <>
line <> text "]"
다음과 같이 정규화된 형태로 나타낼 수 있다.
text "bbbbb[" <>
nest 2 line <> text "ccc," <>
nest 2 line <> text "dd" <>
nest 0 line <> text "]"
그러면 문서는 다음처럼 출력된다.
bbbbb[
ccc,
dd
]
<> 연산자가 nil 항등원을 가진다는 사실에 더해서 다음 규칙(law)들 정도면 임의의 문서를 정규화할 수 있다.
text (s ++ t) = text s <> text t
text "" = nil
nest (i+j) x = nest i (nest j x)
nest 0 x = x
nest i (x <> y) = nest i x <> nest i y
nest i nil = nil
nest i (text s) = text s
마지막 규칙을 빼면 모두 쌍을 이룬다. 이항 연산자를 포함하는 규칙은 항등원을 다루는 것을 동반한다. 첫 번째 규칙 쌍은 text 함수가 문자열 연결을 문서 연결로 이어주는 준동형(homomorphism)임을 의미한다. 두 번째 규칙 쌍은 nest 함수가 더하기를 합성으로 이어주는 준동형임을 말한다. 그 다음 규칙 쌍은 nest 함수가 이어붙임 연산에 대해 분배 법칙이 성립함을 말한다. 마지막 규칙은 nest 들여쓰기가 text 함수에 의해 무효화되는 것을 보여준다. 문서를 정규화할 때 앞의 네 규칙은 왼쪽에서 오른쪽으로 적용되고 나머지 세 규칙은 오른쪽에서 왼쪽으로 적용된다.
문서의 레이아웃과 관련된 규칙도 정리할 수 있다.
layout (x <> y) = layout x ++ layout y
layout nil = ""
layout (text s) = s
layout (nest i line) = '\n' : copy i ' '
첫 두 개의 규칙은 layout 함수가 문서 연결을 문자열 연결로 이어주는 준동형임을 의미한다. 이렇게 보면 layout은 text의 역함수다. 이 사실은 그 다음 규칙이 설명한다. 마지막 규칙은 줄바꿈을 들여쓰기하는 것이 그 줄바꿈 뒤에 들여쓰기한 만큼의 공백 문자가 이어지는 것을 보여준다.
단순하면서도 부족함이 없는 구현을 문서 대수(algebra)로부터 직접적으로 유도할 수 있다. 문서 타입을 텍스트 혹은 들여쓰기를 포함한 줄바꿈 항목들의 연결로 표현할 수 있다.
data Doc = Nil
| String `Text` Doc
| Int `Line` Doc
생성자들은 다음처럼 문서 연산자들과 연관된다.
Nil = nil
s `Text` x = text s <> x
i `Line` x = nest i line <> x
앞서 정규화의 예로 들었던 문서는 다음처럼 표현할 수 있다.
"bbbbb[" `Text` (
2 `Line` ("ccc," `Text` (
2 `Line` ("dd" `Text` (
0 `Line` ("]" `Text` Nil)))))
문서가 항상 정규화 형식을 갖출 필요는 없다. 텍스트와 줄바꿈이 꼭 교차해서 나타나지 않아도 되기 때문이다.
위의 등식들을 이용하면 각 함수들의 구현을 쉽게 유도할 수 있다.
nil = Nil
text s = s `Text` Nil
line = 0 `Line` Nil
(s `Text` x) <> y = s `Text` (x <> y)
(i `Line` x) <> y = i `Line` (x <> y)
Nil <> y = y
nest i (s `Text` x) = s `Text` nest i x
nest i (j `Line` x) = (i+j) `Line` nest i x
nest i Nil = Nil
layout (s `Text` x) = s ++ layout x
layout (i `Line` x) = '\n' : copy i ' ' ++ layout x
layout Nil = ""
예를 들어 <> 연산자 첫 번째 정의의 유도 과정은 다음과 같다.
(s `Text` x) <> y
= { Text 정의 }
(text s <> x) <> y
= { <> 결합 법칙 }
text s <> (x <> y)
= { Text 정의 }
s `Text` (x <> y)
나머지 정의들도 이와 마찬가지로 간단히 유도할 수 있다.
2 여러가지 레이아웃을 지원하는 프리티프린터
이제 여러가지 레이아웃이 가능한 문서를 고려해보자. 앞에서는 문서를 문자열과 동등하게 봤지만 이제는 문자열의 집합 정도로 볼 것이다. 같은 문서가 여러 형태의 레이아웃으로 나타날 수 있고 각각이 집합의 요소에 해당한다.
아래 함수 하나를 추가하여 개념을 확장할 수 있다.
group :: Doc -> Doc
group은 문서를 입력으로 받고 가능한 레이아웃을 한 가지 추가한 문서를 반환한다. 새로 추가되는 레이아웃은 문서의 모든 요소들을 한 줄로 표시하는 것이다. 한 줄로 표시하기 위해 모든 줄바꿈과 이어지는 들여쓰기를 공백 문자 하나로 바꿀 수 있다. (또다른 방법도 가능하다. 줄바꿈마다 바꾸기를 위한 텍스트를 연관짓는 것이다. 어떤 줄바꿈은 빈 문자열, 어떤 줄바꿈은 공백 하나로 바꿔치기 할 수 있다.)
이제 layout 함수는 가능한 레이아웃들 중에서 가장 예쁜 모양을 선택하는 것으로 바뀌게 된다. 레이아웃을 선택하려면 원하는 최대 줄 길이를 의미하는 인자를 추가로 받아야 한다.
pretty :: Int -> Doc -> String
(추가 인자를 다른 의미로 정의할 수도 있다. 예를 들어 "리본 길이"라고 하여, 들여쓰기 공백을 제외한 최대 줄 길이를 인자로 받는 변형도 가능하다.)
group을 사용하는 예를 살펴보자. 트리를 문서로 출력하는 함수를 조금 변형한 것이다. 마지막에 group을 추가로 호출한다.
showTree (Node s ts) = group (text s <> nest (length s) (showBracket ts))
이렇게 만들어진 예제 문서를 pretty 30으로 프린트하면 아래와 같은 출력을 얻게 된다.
aaa[bbbbb[ccc, dd],
eee,
ffff[gg, hhh, ii]]
한 줄로 표시할 수 있는 트리는 한 줄로 표시하지만 그렇지 않은 경우에는 줄바꿈을 추가하여 전체 줄 길이가 30 글자를 넘지 않도록 한다.
새로운 동작의 의미를 명확히 정의하기 위해 아래의 두 연산자를 추가한다.
(<|>) :: Doc -> Doc -> Doc
flatten :: Doc -> Doc
<|> 연산자는 두 레이아웃 집합을 하나로 합쳐 준다. flatten 연산자는 모든 줄바꿈(과 이어진 들여쓰기 공백)을 공백 하나로 바꿔준다. 문서는 가능한 레이아웃들의 집합을 의미하고 모든 레이아웃 대안들은 flatten을 적용했을 때 같은 모양이 된다. (x <|> y)가 정의되려면 x와 y의 모든 레이아웃이 하나의 형태로 플랫하게 만들어질 수 있어야 한다. <|>나 flatten 연산자는 사용자에게 직접 노출되지 않는다. 대신 group이나 4절에서 정의할 fillwords, fill 같은 함수들을 통해서 간접적으로 노출된다. 이 함수들은 <|>가 필요로 하는 성질을 만족시킨다.
새로 추가된 연산들을 고려하여 대수 규칙들을 확장하자.
(x <|> y) <> z = (x <> z) <|> (y <> z)
x <> (y <|> z) = (x <> y) <|> (x <> z)
nest i (x <|> y) = nest i x <|> nest i y
집합의 각 요소들은 한 줄로 표현했을 때 같은 모양이 되므로 flatten 함수를 합집합에 적용하는 것은 아주 간단하다.
flatten (x <|> y) = flatten x
아래의 추가 규칙들은 flatten이 문서 생성자들에 어떤 영향을 주고 받는지를 설명한다. line의 경우가 매우 흥미롭다.
flatten (x <> y) = flatten x
flatten nil = nil
flatten (text s) = text s
flatten line = text " "
flatten (nest i x) = flatten x
이제 group을 flatten과 <|>로 정의할 수 있다.
group x = flatten x <|> x
지금까지의 규칙들을 기반으로 모든 문서들이 아래의 정규화된 형식으로 환원시킬 수 있다.
x1 <|> ... <|> xn
여기서 x1, x2, ... 는 단순한 문서에서의 정규화된 형식이다.
이제 문서에서 표현할 수 있는 다양한 레이아웃들 중에서 최선을 선택하는 방법을 정의해야 한다. 휴즈를 따르자면 먼저 줄 간의 순서를 정의하고 이를 확장하여 문서 간의 순서를 매길 수 있다.
상대적 순서를 매기려면 허용 가능한 문서 폭, 그러니까 줄 길이가 무엇인지 알아야 한다. 두 줄이 모두 허용 폭보다 짧으면 더 긴 줄이 더 낫다고 정의한다. 한 줄은 허용 폭에 들어맞는데 다른 줄은 넘는다면 폭에 맞는 줄이 더 낫다. 두 줄이 모두 허용 폭보다 길다면 짧은 줄이 더 낫다. 이렇게 순서를 정의한다는 것은 주어진 문서 폭보다 긴 줄이 출력 결과에 포함될 수도 있다는 얘기다. 하지만 피할 수 없는 경우에 한해서만 그러하다. (이 점이 휴즈와 결정적으로 다른 점이다. 여기에 대한 논의는 뒤에서 이어진다.)
문서가 레이아웃 집합이라고 봤을 때 이를 구현하는 한 가지 방법은 집합을 리스트로 표현하고 레이아웃을 문자열로 표현하거나 혹은 앞 절의 대수적 표현 그대로 나타내는 것이다. 이런 구현 방법은 어처구니 없을 정도로 비효율적이다. 100 가지 선택지가 주어진다면 2100가지 레이아웃이 가능하기 때문이다.
다행이도 앞서 정의한 대수적 명세 덕분에 좀더 그럴듯하게 구현할 수도 있다. 새로운 구현은 기존 구현과 비슷하지만 두 문서의 합집합을 생성자로 추가하였다.
data Doc = Nil
| String `Text` Doc
| Int `Line` Doc
| Doc `Union` Doc
이 생성자들은 다음처럼 연산자들과 연관지을 수 있다.
Nil = nil
s `Text` x = test s <> x
i `Line` x = nest i line <> x
x `Union` y = x <|> y
이제 (x `Union` y)에 대해 두 가지 불변 특성을 생각할 수 있다. 이전과 마찬가지로 x와 y는 모두 같은 레이아웃으로 플랫화되어야 한다. 여기에 더해 x의 레이아웃 중 어떤 것도 첫 줄이 y의 첫 줄들 보다 짧을 수 없다는 특성이다. Union을 만드는 경우에는 이 두 성질을 꼭 만족시켜야 한다.
받아들일 수 있을 정도의 성능을 내기 위해 우리는 분배 법칙을 이용할 것이다. ((s `Text` x) `Union` (s `Text` y)) 대신 동등한 (s `Text` (x `Union` y))을 사용한다. 예를 들어 다음의 문서를 보자.
group (
group (
group (text "hello" <> line <> text "a")
<> line <> text "b")
<> line <> text "c")
이 문서는 다음과 같은 레이아웃이 가능하다.
hello a b c hello a b hello a hello
c b a
c b
c
이 문서를 최대 허용 폭 5 기준으로 출력하려면 가능한 레이아웃 중에서 마지막 모양을 선택해야 한다. 다른 가능성들을 한 번에 모두 배제시킬 수 있다면 좋을 것이다. 그러자면 앞 부분에 공통되는 문자열을 모두 모을 수 있는 방식이 필요하다. 만약 아래처럼 표현할 수만 있다면 x나 y가 어떤 모양이든 상관없을 것이다.
"hello" `Text` ((" " `Text` x) `Union` (0 `Line` y))
"hello"가 공통 부분으로 빠져있다. x에서도 " "가 공통 부분으로 빠져있다. "hello" 뒤에 " "를 연결하는 것만으로 이미 6 글자가 되고 줄 길이는 5로 제한되었으므로 x는 더 살펴볼 필요없이 곧바로 Union의 오른쪽 항을 선택할 수 있다.
nil, text, <>, nest 함수들의 정의는 이미 정의한 것에서 바뀌지 않고, <>와 nest만 Union을 처리하는 절을 추가하면 된다.
(x `Union` y) <> z = (x <> z) `Union` (y <> z)
nest k (x `Union` y) = nest k x `Union` nest k y
추가한 두 정의는 분배 법칙을 따르고 있다. 첫 번째 정의에서 Union이 만족해야 하는 특성이 지켜지는지 살펴보자. x의 가능한 모든 첫 줄이 y의 어떤 첫 줄보다도 짧지 않다면 x <> z의 모든 첫 줄이 y <> z의 어떤 첫 줄보다도 짧지 않으므로 약속한 성질을 만족한다.
group과 flatten의 정의는 쉽게 유도할 수 있다.
group Nil = Nil
group (i `Line` x) = (" " `Text` flatten x) `Union` (i `Line` x)
group (s `Text` x) = s `Text` group x
group (x `Union` y) = group x `Union` y
flatten Nil = Nil
flatten (i `Line` x) = " " `Text` flatten x
flatten (s `Text` x) = s `Text` flatten x
flatten (x `Union` y) = flatten x
group 정의에서 두 번째 절의 유도 과정을 살펴보자.
group (i `Line` x)
= { Line 정의 }
group (nest i line <> x)
= { group 정의 }
flatten (nest i line <> x) <|> (nest i line <> x)
= { flatten 정의 }
(text " " <> flatten x) <|> (nest i line <> x)
= { Text, Union, Line 정의 }
(" " `Text` flatten x) `Union` (i `Line` x)
마지막 줄을 보면, Union 왼쪽의 모든 문서는 공백 문자로 시작하고 오른쪽의 모든 문서는 줄바꿈으로 시작한다. 따라서 Union이 갖춰야 할 조건을 만족하다.
group의 세 번째 줄을 유도하는 과정이 매우 중요하다.
group (s `Text` x)
= { Text 정의 }
group (text s <> x)
= { group 정의 }
flatten (text s <> x) <|> (text s <> x)
= { flatten 정의 }
(text s <> flatten x) <|> (text s <> x)
= { <>는 <|>에 대해 분배 법칙을 만족하므로 }
text s <> (flatten x <|> x)
= { group 정의 }
text s <> group x
= { Text 정의 }
s `Text` group x
group 정의에서 비롯된 두 개의 text를 다시 하나로 합치는데 분배 법칙이 적용되었다. 여기서 보듯이 공통 요소를 추출하는 것이 효율적인 표현 방법을 결정하는데 매우 중요하다.
group과 flatten 정의의 다른 절들도 쉽게 유도할 수 있다. 두 함수의 마지막 절들은 Union으로 합쳐지는 두 문서가 모두 같은 형태로 플랫화 된다는 특성이 적용되었다.
이제 가능한 문서 레이아웃 중에서 최선을 선택해야 한다. best라는 함수가 그 역할을 한다고 하자. 이 함수는 여러 가능성을 가진(즉 Union을 가진) 문서를 입력으로 받아서 Union이 없는 문서를 반환한다. 이 함수가 인자를 두 개 더 필요로 한다는 것을 금방 알 수 있다. 하나는 문서 폭을 한정하는 w이고 다른 하나는 공백을 포함하여 현재 줄에 출력하기로 결정된 글자 수를 의미하는 k이다. 코드는 별로 어렵지 않다.
best w k Nil = Nil
best w k (i `Line` x) = i `Line` best w i x
best w k (s `Text` x) = s `Text` best w (k + length s) x
best w k (x `Union` y) = better w k (best w k x) (best w k y)
better w k x y = if fits (w-k) x then x else y
두 번째와 세 번째 경우는 현재 위치를 조정할 뿐이다. 줄바꿈이 있는 경우 들여쓰기 값으로 재지정하고, 텍스트가 있는 경우 그 길이만큼 위치를 증가시킨다. Union의 경우에는 두 문서의 최선을 먼저 구하고, 그 중에서 더 나은 것을 선택하면 된다. 내부 문서들에 대해 best를 계산하는 부분이 지연 연산되도록 하는 것이 성능을 확보하는데 핵심이다. Union의 불변 성질에 따라 왼쪽 문서의 모든 첫 줄이 오른쪽 문서의 첫 줄들보다 짧지 않으므로, 문서 폭에 들어맞는지에 대한 검사는 왼쪽 문서에 대해 먼저 살펴본다.
문서의 첫 줄이 w 폭에 들어맞는지 확인하는 것만 남았다. 이 함수도 간단하다.
fits w x | w < 0 = False
fits w Nil = True
fits w (s `Text` x) = fits (w - length s) x
fits w (i `Line` x) = True
만약 남은 공간 w가 0보다 작다면 문서를 폭에 맞출 수 없다. 남은 공간이 있는 경우에, 빈 문서이거나 줄바꿈으로 시작하는 문서라면 첫 줄이 들어맞았다는 얘기다. 텍스트로 시작하는 문서는 남은 공간을 문자열 길이만큼 줄인 뒤 나머지 문서가 들어맞는지 확인한다. 텍스트 길이가 음수가 될 수 있는 경우라면 남은 공간이 음수인 경우도 처리해야 할 것이다. Union의 경우를 처리할 필요는 없다. 이 함수는 문서에서 최선이라고 선택한 결과에만 적용되기 때문이다.
드디어 문서에 출력하기 위한 최선의 레이아웃을 선택하고 문자열로 변환할 수 있게 되었다.
pretty w x = layout (best w 0 x)
layout 함수는 처음 정의한 것에서 바뀌지 않았다.
3 성능 향상
앞에서 구현한 것의 성능은 어느 정도 참을만한 정도다. 하지만 더 빠르게 만들 수 있다. 문서를 프리티프린트하는 것은 문서의 길이 s에 대해 O(s)의 성능을 낼 수 있어야 하지 않을까. (문서의 길이는 문서를 구성하는 <>, nil, text, nest, group 연산의 갯수와 text로 포함된 모든 문자열의 길이를 말한다.) 그리고 공간 복잡도 측면에서도 O(w max d)이어야 하지 않을까. (w는 문서의 폭, d는 nest나 group의 중첩된 깊이를 의미한다.)
앞의 프로그램에는 효율성을 떨어뜨리는 두 가지 원인이 있다. 하나는 문서의 연결이 왼쪽으로 겹겹이 쌓인다는 점이다.
(...(text s0 <> text s1) <> ...) <> text sn
모든 문자열의 길이가 1이라고 가정했을 때, 위와 같이 만들어진 문서를 처리하려면 O(n2)의 시간이 걸린다. O(n)이 아니다. 두 번째 원인은 첫 번째와는 별개로 문서를 nest로 중첩할 때 내부 문서들의 들여쓰기를 누적 증가시켜야 하는 문제이다.
nest i0 (text s0 <> nest i1 (text s1 <> ... <> nest in (text sn)...))
이번에도 모든 문자열의 길이가 1이라고 가정했을 때, 마찬가지로 O(n)이 아니라 O(n2)의 시간이 걸린다.
첫 번째 문제를 해결하는 방법 중 하나는 문서 연결 혹은 결합을 나타내는 명시적인 생성자를 추가하고 연산자들을 수정하여 연결된 문서의 목록을 처리할 수 있게 만드는 것이다. 두 번째 문제를 해결하는 방법은 nest를 위한 생성자를 추가하여 들여쓰기가 중첩될 때 현재 위치에서의 들여쓰기 수준을 계산하여 유지하게 만드는 것이다. 이 두 가지 개선 방법을 적용하면 모든 연산자들을 확장하여 들여쓰기 수준과 문서의 쌍을 리스트 형태로서 처리할 수 있게 해야 한다.
이러한 개선을 위해 문서를 나타내는 새로운 표현이 필요하다. 문서를 만드는 모든 연산자와 일대일 대응하는 생성자를 만든다. 앞의 구현과 차별화하기 위해 모든 이름을 대문자로 나타냈다.
data DOC = NIL
| DOC :<> DOC
| NEST Int DOC
| TEXT String
| LINE
| DOC :<|> DOC
이제 각 연산자들은 생성자를 호출할 뿐이다.
nil = NIL
x <> y = x :<> y
nest i x = NEST i x
text s = TEXT s
line = LINE
여전히 (x :<|> y)를 위해서 x와 y의 모든 레이아웃들이 같은 형태로 플랫화되어야 하고, x의 모든 첫 줄들이 y의 첫 줄들보다 짧으면 안된다.
group과 flatten 함수를 구현하는 것은 간단하다. 이미 살펴봤던 등식을 그대로 따르기만 하면 된다.
group x = flatten x :<|> x
flatten NIL = NIL
flatten (x :<> y) = flatten x :<> flatten y
flatten (NEST i x) = flatten x
flatten (TEXT s) = TEXT s
flatten LINE = TEXT " "
flatten (x :<|> y) = flatten x
표시(representation) 함수는 들여쓰기/문서 쌍의 리스트를 대응하는 문서로 변환한다.
rep z = fold (<>) nil [ nest i x | (i,x) <- z ]
최상의 레이아웃을 찾는 것은 들여쓰기/문서 쌍의 리스트를 처리하는 것으로 일반화된다. 일반화된 함수는 이미 정의했던 연산과 표시 함수로 정의된다.
be w k z = best w k (rep z) ...가설
사실은 기존의 best 정의를 가져와서 구현할 수 있다.
best w k x = be w k [(0,x)]
be w k [] = Nil
be w k ((i,NIL):z) = be w k z
be w k ((i,x :<> y):z) = be w k ((i,x):(i,y):z)
be w k ((i,NEST j x):z) = be w k ((i+j,x):z)
be w k ((i,TEXT s):z) = s `Text` be w (k + length s) z
be w k ((i,LINE):z) = i `Line` be w i z
be w k ((i,x :<|> y):z) = better w k (be w k ((i,x):z))
(be w k ((i,y):z))
첫 줄의 유도 과정을 보자.
best w k x
= { nest 0은 변화 없음 }
best w k (nest 0 x)
= { <> nil은 변화 없음 }
best w k (nest 0 x <> nil)
= { rep 정의와 가설에 따라 }
be w k [(0,x)]
:<>의 경우를 보자.
be w k ((i,x :<> y):z)
= { 가설, rep 정의, :<> 정의 }
best w k (nest i (x <> y) <> rep z)
= { nest는 <>에 분배 가능 }
best w k ((nest i x <> nest i y) <> rep z)
= { <> 결합 법칙 }
best w k (rest i x <> (nest i y <> rep z))
= { rep 정의, 가설 }
be w k ((i,x):(i,y):z)
NEST의 경우를 보자.
be w k ((i,NEST j x):z)
= { 가설, rep 정의, NEST 정의 }
best w k (nest i (nest j x) <> rep z)
= { nest는 들여쓰기 덧셈과 합성에 대해 준동형 }
best w k (nest (i+j) x <> rep z)
= { rep 정의, 가설 }
be w k ((i+j,x):z)
TEXT의 경우를 보자.
be w k ((i,TEXT s):z)
= { 가설, rep 정의, TEXT 정의 }
best w k (nest i (text s) <> rep z)
= { text는 nest를 무효화 }
best w k (text s <> rep z)
= { best 정의 }
s `Text` best w (k + length s) (rep z)
= { 가설 }
s `Text` be w (k + length s) z
다른 경우들도 비슷하다.
best 함수의 인자는 새로 정의한 DOC를 사용하고 결과는 기존의 Doc를 사용한다. 따라서 pretty 함수는 여전히 다음처럼 정의할 수 있다.
pretty w x = layout (best w 0 x)
layout, better, fits 세 함수는 바뀌지 않는다. 전체 코드는 7절에 확인할 수 있다.
4 예제
몇 가지 편의 함수들을 정의하였다.
x <+> y = x <> text " " <> y
x </> y = x <> line <> y
folddoc f [] = nil
folddoc f [x] = x
folddoc f (x:xs) = f x (folddoc f xs)
spread = folddoc (<+>)
stack = folddoc (</>)
독자 입맛에 따라 다른 편의 함수들을 정의할 수 있다.
레이아웃을 하다보면 괄호를 열면서 조금 들여쓰기를 한 뒤 마지막으로 괄호를 닫는 경우가 자주 있다.
bracket l x r = group (text l <>
nest 2 (line <> x) <>
line <> text r)
아래는 트리 출력 함수에 적용하여 더 간단해진 모습이다.
showBracket' ts = bracket "[" (showTrees' ts) "]"
bracket을 사용하는 다른 예는 뒤에 또 나온다.
fillwords 함수는 문자열을 입력으로 받아서 각 줄을 가능한 많은 단어들로 채운 문서를 반환한다. 이 함수는 하스켈 표준 라이브러리의 words 함수를 이용하여 문자열을 공백으로 구분하여 단어 리스트로 만든다.
x <+/> y = x <> (text " " :<|> line) <> y
fillwords = folddoc (<+/>) . map text . words
:<|>를 사용자에게 노출시키지 않기로 했었다. 하지만 x <+/> y는 안심하고 노출할 수 있다. 이 함수는 여전히 :<|>가 요구하는 조건을 만족하고 있기 때문이다. text " "와 line은 모두 같은 레이아웃으로 플랫화된다. 그리고 첫 번째 인자의 첫 줄이 두 번째 인자보다 더 길다. 다른 방법으로는 (text " " :<|> line) 대신 이와 동등한 (group line)으로 바꿔도 된다.
fillwords를 변형한 fill 함수는 문서 리스트를 문서 하나로 합친다. 두 문서를 가능하면 공백으로 연결하고 그렇지 않으면 줄바꿈으로 연결한다. (이 함수는 페이튼 존스와 휴즈의 프리티프린트 라이브러리에서 가져왔다.)
fill [] = nil
fill [x] = x
fill (x:y:zs) = (flatten x <+> fill (flatten y : zs))
:<|>
(x </> fill (y : zs))
flatten을 사용하여 두 문서가 한 줄에 표시될 때에는 공백만 나타나도록 하였다. :<|>가 갖춰야 하는 조건은 충족되었다. fill의 쓰임새를 보여주는 다음 예에서 flatten의 역할도 확인할 수 있다.
다음 사례는 엘리먼트, 애트리뷰트, 텍스트로만 구성된 약식 XML을 프리티프린트하는 함수이다.
data XML = Elt String [Att] [XML]
| Txt String
data Att = Att String String
showXML x = folddoc (<>) (showXMLs x)
showXMLs (Elt n a []) = [text "<" <> showTag n a <> text "/>"]
showXMLs (Elt n a c) = [text "<" <> showTag n a <> text ">" <>
showFill showXMLs c <>
text "</" <> text n <> text ">"]
showXMLs (Txt s) = map text (words s)
showAtts (Att n v) = [text n <> text "=" <> text (quoted v)]
quoted s = "\"" ++ s ++ "\""
showTag n a = text n <> showFill showAtts a
showFill f [] = nil
showFill f xs = bracket "" (fill (concat (map f xs))) ""
아래는 페이지 폭 30에 맞춰 출력한 XML 문서이다.
<p
color="red" font="Times"
size="10"
>
Here is some
<em> emphasized </em> text.
Here is a
<a
href="http://www.eg.com/"
> link </a>
elsewhere.
</p>
아래는 같은 XML 문서를 페이지 폭 60 기준으로 출력한 것이다.
<p color="red" font="Times" size="10" >
Here is some <em> emphasized </em> text. Here is a
<a href="http://www.eg.com/" > link </a> elsewhere.
</p>
내부 마크업이 어떤 식으로 플랫화되어 한 줄로 표시되는지 살펴보라. 만약 fill 함수의 정의에서 두 번째 flatten이 없었다면 아래와 같은 결과를 얻었을 것이다.
<p color="red" font="Times" size="10" >
Here is some <em>
emphasized
</em> text. Here is a <a
href="http://www.eg.com/"
> link </a> elsewhere.
</p>
이 결과는 별로 예쁘지 않다. em 엘리먼트와 a 엘리먼트의 시작/끝 태그가 같은 줄 혹은 같은 칼럼에 나란히 나타나지 않고 다른 텍스트와 섞여있기 때문이다.
5 관련 작업 및 결론
대수 휴즈는 전혀 다른 결합 연산자를 두 개 사용했다. 수평 결합 연산자(똑같이 <>로 표현)는 복잡하다. 두 번째 인자의 첫 줄에 적용된 모든 들여쓰기를 무시하고, 그 다음 줄부터는 첫 번째 인자의 마지막 줄에 있는 텍스트만큼 들여쓰기되어야만 한다. 수직 결합 연산자($$로 표현)는 간단하다. 항상 줄바꿈으로 문서들을 연결한다. 더 자세한 내용은 휴즈의 글을 참고하라.(1995)
휴즈의 연산자들은 둘 다 결합 법칙을 따른다. 하지만 두 가지 가능한 경우 중에서 한 경우만 허용한다. 아래의 두 가지 경우 중에서 첫 번째 등식은 만족하지만 두 번째 등식은 허용하지 않는다.
x $$ (y <> z) = (x $$ y) <> z
x <> (y $$ z) = (x <> y) $$ z
수평 연결은 왼쪽 항등원이 있지만 두 번째 인자의 들여쓰기를 무시하기 때문에 근본적으로 오른쪽 항등원이 있을 수 없다. 수직 연결의 경우에는 항상 줄바꿈을 추가하기 때문에 어느 쪽에 대해서도 항등원이 없다.
여기서는 결합 연산자를 하나만 사용하고 있으며 왼쪽/오른쪽 모두 항등원이 있다. 수직 결합 연산자를 비슷하게 정의할 수 있다.
x </> y = x <> line <> y
</>가 결합 법칙을 따른다. 그리고 </>가 항등원을 가지지는 않지만 <>와 </>는 서로 어느 방향으로든 결합할 수 있다.
표현력 휴즈는 sep 연산자를 정의하였다. 이 연산자는 문서 리스트를 입력으로 받아서 전체를 공백으로 연결하여 한 줄로 표시할 수 있으면 그렇게 하고 아닌 경우에는 수직으로 연결한다. 여기서는 group 연산자가 있어서 한 줄로 표시할 수 있는 경우에는 한 줄로 표시하게 하였다.
몇 가지 차이점은 있지만 두 라이브러리는 여러가지 대표적인 레이아웃 규칙을 거의 비슷하게 표시할 수 있다. 어떤 경우에는 휴즈의 방식이 더 편리하기도 하고, 여기서 제시한 방식이 더 편리하기도 하다.
하지만 휴즈의 방식으로만 표현할 수 있는 레이아웃도 있다. 그러한 레이아웃이 실제로도 쓰임새가 있는지는 확실하지 않지만 휴즈의 라이브러리가 아래와 같은 어려움을 드러낸다는 점은 분명하다.
최적성 가능한 한 지정 폭을 넘지 않도록 줄바꿈을 추가하는 알고리즘을 최적(optimal)이라고 보자. 그리고 줄바꿈을 추가할지 여부를 최대 w(지정 폭)개의 글자만큼 들여다보고 결정할 수 있다면 유한(bounded)하다고 보자. 휴즈는 자신의 라이브러리를 이용할 때 최적이면서 유한한 알고리즘은 없다는 점을 명시했다. 반면 내가 제시하는 알고리즘은 두 속성을 모두 보여준다.
유도 과정 휴즈의 라이브러리와 여기서 제시한 라이브러리는 효율적 구현을 유도하는 과정에서 대수를 사용했다.
휴즈의 유도 과정은 여기서 보여준 것보다 더 복잡하다. 휴즈의 라이브러리에서는 문서 수준에서 한 줄 표현을 따로 제공하지 않으며 오직 sep을 적용하는 문서 리스트의 모든 문서들이 한 줄 표현이 가능한 경우에만 그 결과 역시 한 줄 표현이 가능하다. 휴즈의 경우 flatten 비슷한 함수가 있다면 빈 집합을 결과로 내 놓을 수도 있고 이런 빈 집합은 유도 과정에서 따로 처리해야 하므로 복잡해진다. 여기서는 모든 문서가 하나 이상의 레이아웃을 포함하는 집합으로 보고 있다. 휴즈이 경우 수평 결합으로 생겨나는 들여쓰기가 종료되면서 음수의 들여쓰기를 처리하고 있지만 여기서는 모든 들여쓰기가 0 이상이다.
오펜(Oppen)은 여기서 설명하는 프리티프린터와 비슷한 것을 보여줬다.(1990) 여기서와 마찬가지로 최적이고 유한한 알고리즘이다. 가능한 한 지정 폭을 넘지 않도록 줄바꿈을 추가하고, 지정 폭만큼만 살펴보면 줄바꿈 여부를 결정할 수 있다. 오펜의 알고리즘은 버퍼를 사용하며 구현하기 까다로울 수 있다. 내가 처음 컴비네이터들을 구현할 때 시도한 것도 오펜과 비슷한 방법으로 버퍼를 이용하는 것이었지만 꽤 복잡했다. 이 문서에 제시한 방법은 두 번째 시도의 결과로서, 휴즈에게서 영감을 얻은 대수를 사용하고 훨씬 더 단순하다.
(치틸(Chitil)은 오펜의 알고리즘대로 구현한 것을 발표했는데, 순수 함수형 스타일로 정확히 구현하기가 얼마나 까다로운지 보여주는 것이 목적이었다.(2001))
버드(Bird)의 영향 리차드 버드는 대수적 설계라는 새로운 장을 열었다. 존 휴즈의 프리티 프린터는 대수적 접근의 대표적 사례가 되었다. 모방은 최고의 오마쥬이다. 여기서 나는 최대한 휴즈와 버드의 방식을 따르고자 노력했다.
경의를 표하기 위한 나의 노력에 있어서 들여쓰기를 처리하는 부분에 특별한 신경을 썼다. 휴즈는 들여쓰기를 처리하면서 명령형 스타일을 선택했다. 그러다보니 들여쓰기를 되돌리는 음수 들여쓰기를 도입하는 기발함을 보여줬다. 여기서는 버드의 대수적 접근을 철저히 따르면서도 같은 결과를 얻을 수 있었다. 들여쓰기(nest) 연산이 이어붙이기 연산에 분배 가능하다는 사실 덕분이었다. 이렇게 말해도 좋을 것이다. "더 예쁜 프리티프린터는 버드의 네스트(Bird's nest)에서 부화했다"
6 감사
코멘트를 해 준 분들께 감사드린다. Richard Bird, Koen Classen, John Hughes, Sam Kamin, Daniel J. P. Leijen, Jeffrey Lewis, Chris Okasaki, Simon Peyton Jones, Andreas Rossberg.
7 코드
-- The pretty printer
infixr 5 :<|>
infixr 6 :<>
infixr 6 <>
data DOC = NIL
| DOC :<> DOC
| NEST Int DOC
| TEXT String
| LINE
| DOC :<|> DOC
data Doc = Nil
| String `Text` Doc
| Int `Line` Doc
nil = NIL
x <> y = x :<> y
nest i x = NEST i x
text s = TEXT s
line = LINE
group x = flatten x :<|> x
flatten NIL = NIL
flatten (x :<> y) = flatten x :<> flatten y
flatten (NEST i x) = NEST i (flatten x)
flatten (TEXT s) = TEXT s
flatten LINE = TEXT " "
flatten (x :<|> y) = flatten x
layout Nil = ""
layout (s `Text` x) = s ++ layout x
layout (i `Line` x) = '\n' : copy i ' ' ++ layout x
copy i x = [ x | _ <- [1..i] ]
best w k x = be w k [(0,x)]
be w k [] = Nil
be w k ((i,NIL):z) = be w k z
be w k ((i,x :<> y):z) = be w k ((i,x):(i,y):z)
be w k ((i,NEST j x):z) = be w k ((i+j,x):z)
be w k ((i,TEXT s):z) = s `Text` be w (k+length s) z
be w k ((i,LINE):z) = i `Line` be w i z
be w k ((i,x :<|> y):z) = better w k (be w k ((i,x):z))
(be w k ((i,y):z))
better w k x y = if fits (w-k) x then x else y
fits w x | w < 0 = False
fits w Nil = True
fits w (s `Text` x) = fits (w - length s) x
fits w (i `Line` x) = True
pretty w x = layout (best w 0 x)
-- Utility functions
x <+> y
x </> y
folddoc f [] = nil
folddoc f [x] = x
folddoc f (x:xs) = f x (folddoc f xs)
spread = folddoc (<+>)
stack = folddoc (</>)
bracket l x r = group (text l <>
nest 2 (line <> x) <>
line <> text r)
x <+/> y = x <> (text " " :<|> line) <> y
fillwords = folddoc (<+/>) . map text . words
fill [] = nil
fill [x] = x
fill (x:y:zs) = (flatten x <+> fill (flatten y : zs))
:<|>
(x </> fill (y : zs))
-- Tree example
data Tree = Node String [Tree]
showTree (Node s ts) = group (text s <> nest (length s) (showBracket ts))
showBracket [] = nil
showBracket ts = text "[" <> nest 1 (showTrees ts) <> text "]"
showTrees [t] = showTree t
showTrees (t:ts) = showTree t <> text "," <> line <> showTrees ts
showTree' (Node s ts) = text s <> showBracket' ts
showBracket' [] = nil
showBracket' ts = bracket "[" (showTrees' ts) "]"
showTrees' [t] = showTree' t
showTrees' (t:ts) = showTree' t <> text "," <> line <> showTrees' ts
tree = Node "aaa" [
Node "bbbbb" [
Node "ccc" [],
Node "dd" []
],
Node "eee" [],
Node "ffff" [
Node "gg" [],
Node "hhh" [],
Node "ii" []
]
]
testtree w = putStr (pretty w (showTree tree))
testtree' w = putStr (pretty w (showTree' tree))
-- XML example
data XML = Elt String [Att] [XML]
| Txt String
data Att = Att String String
showXML x = folddoc (<>) (showXMLs x)
showXMLs (Elt n a []) = [text "<" <> showTag n a <> text "/>"]
showXMLs (Elt n a c) = [text "<" <> showTag n a <> text ">" <>
showFill showXMLs c <>
text "</" <> text n <> text ">"]
showXMLs (Txt s) = map text (words s)
showAtts (Att n v) = [text n <> text "=" <> text (quoted v)]
quoted s = "\"" ++ s ++ "\""
showTag n a = text n <> showFill showAtts a
showFill f [] = nil
showFill f xs = bracket "" (fill (concat (map f xs))) ""
xml = Elt "p" [
Att "color" "red",
Att "font" "Times",
Att "size" "10"
] [
Txt "Here is some",
Elt "em" [] [
Txt "emphasized"
],
Txt "text.",
Txt "Here is a",
Elt "a" [
Att "href" "http://www.eg.com/" ] [
Txt "link"
],
Txt "elsewhere."
]
testXML w = putStr (pretty w (showXML xml))
참고
- [Chitil 2001] Olaf Chitil. Pretty Printing with Lazy Dequeues. ACM SIGPLAN Haskell Workshop, Firenze, Italy, 2 September 2001, Universiteit Utrecht UU-CS-2001-23, p. 183-201.
- [Hughes 1995] John Hughes. The design of a pretty-printer library. In J. Jeuring and E. Meijer, editors, Advanced Functional Programming, Springer Verlag LNCS 925, 1995
- [Oppen 1980] Derek Oppen. Pretty-printing. ACM Transactions on Programming Languages and Systems, 2(4): 1980.
- [Peyton Jones 1987] Simon Peyton Jones. Haskell pretty-printer library, 1997. Available from http://www.haskell.org/libraries/#prettyprinting.