컴퓨터컴퓨터
컴퓨터/
프로그래밍 언어프로그래밍 언어
프로그래밍 언어/
HaskellHaskell
Haskell/진보하는 함수형 언어, Haskell (김재우)/
2. 아름다운 언어 Haskell 프로그래밍 (1)

2. 아름다운 언어 Haskell 프로그래밍 (1)

김재우∙서영민∙하용길 kizoo@bluette.com
김재우 씨는 블루엣 인터내셔널의 기술 이사로 재직중이며 개발 환경과 온라인 교육 시스템을 결합 한 소프트웨어를 설계하고 있다. 소프트웨어 공학 기술이나 관련 이론을 실천하도록 만드는 것이 개발자로서의 목표. 현재 동명정보기술원과 함께 분야별 표준 교육 과정, 전문 개발자 양성 및 인증 을 위한 교육 시스템‘Theory Into Practice’를 설계하고 있으며, 인도 Vinayaka 대학 IT Parks 소프 트웨어 개발팀과 함께 기업형 솔루션 교육과정 및 소프트웨어 개발 기술을 연구하고 있다. 서영 민∙하용길 씨는 동명 정보대학교 정보기술원 교육 시스템 연구원으로 있다.
 
Haskell은 탄탄한 수학 이론을 바탕으로 함수를 기본 표현 수단으로 하며, 함수의 합성을 통해 문제를 풀어 나간다. 이번 호에서는 함수를 자유롭게 사용하기 위한 Haskell의 기본 지식과 이를 통해 멋지게 문제를 푸는 방법을 배워보자.
차례
 
프로그래밍이란 문제를 풀어 답을 도출하는 작업이다. 그리고 프로그래밍 언어는 문제 푸는 방법을 표현하는 도구다. 문제의 성격이 A식이면 A식에 맞도록 표현하고, B식이면 B식에 맞도록 표현한다. 모든 문제를 한 가지 방식으로 풀어내려고 고집하는 것은 현명하지 않다. 다시 말해서, 한 프로그래밍 언어의 주된 표현기법만으로 문제를 풀어 내는 것 보다 문제에 맞게 여러 가지 표현 기법을 섞어 프로그래밍하는 것이 유리하다. 이런 방식을 패러다임 섞어쓰기(Multiparadigm Programming)라고 한다. Haskell과 같은 프로그래밍 언어를 배워야 하는 이유가 바로 여기에 있다.
Haskell에서 C언어 흉내를 내는 것보다 C에서 Haskell식으로 프로그램하는 것이 훨씬 어렵다. 그 이유는 언어마다 표현력의 차이가 크기 때문이다. Haskell이 C ∙ C# ∙ C++ 등과 비교할 수 없을 정도로 풍부한 표현력을 갖고 있다는 것은 말할 필요조차 없다. 하지만 그저 수단을 제공한다고 해서 모두 좋은 언어는 아니다. 예를 들어 C++가 그렇다. 언뜻 보면 C++가 Haskell 수준의 다양한 표현력을 갖고 있는 것처럼 보인다. 하지만 사실은 여러 가지 복잡한 언어 기능을 서로 다른 바탕에서 한 곳에 몰아 넣은 것뿐이다. 이와 달리, Haskell은 튼튼한 수학 이론을 바탕으로 함수를 기본 표현 수단으로 사용한다. 함수를 바탕으로 하는 프로그래밍 언어(Functional language)에서는 함수 의 성질이 수학의 그것에 가깝고, 함수 그 자체가 정수나 소수와 같은 보통 데이터일 뿐이다.

함수형 언어의 특성

함수로 프로그래밍하는 언어는 다음과 같은 세 가지 기본 특성을 갖고 있다.
첫째 다른 언어에서 볼 수 있는 변수와 같은 기능을 좋아하지 않는다. 보통 변수란 배정문으로 시간에 따라 내용물을 갈아치울 수 있는 메모리 상자와 같다. 그러나 Haskell과 같은 언어는 한번 정해진 값을 아예 바꿀 수 없도록 하는것이 기본 정책이다. 즉, 모든 표현은 바뀔 수 없는 값을 나타낸다. 이런 특성이 이상하게 보일 지 모르지만 원리를 따져보면 그렇지 않은 쪽이 오히려 잘못된 것이다. 본래 모든 식은 항상 같은 값을 나타내야 정상이고, 함수란 식에 이름을 붙인 것이므로 인자의 값이 동일하면 어떤 환경에서도 같은 값을 나타내야 한다. 이런 원칙을 따르면 우리가 쓴 코드가 기대와 다르게 동작할 가능성은 없다. 이와 같은 특성을 참조 투명성(referential transparency)이라 한다.
 
notion imagenotion image
 
둘째, 모든 식은 함수의 합성으로 표현된다. 두 함수를 하나의 함수로 붙여 더 복잡한 함수를 만들어 내는데, 이런저런 군더더기를 제외하면 이것이 함수형 언어의 유일한 기법이다. 믿기 힘들겠지만 우리가 어린 시절 배웠던 이런 단순한 기법(함수 합성, composition)이 Haskell과 같이 풍부한 표현력을 가진 언어의 기본이 된다. 이렇듯 세상의 모든 복잡한 기능은 아주 단순한 기능과 원리로 체계 있게 결합되어 만들어지는 것이다.
 
notion imagenotion image
 
셋째, 함수는 기본 데이터다. 즉, 객체지향에서 객체가 특별한 데이터가 아니듯 함수를 쓰는 언어에서는 함수가 그와 같은 역할을 한다. 수학의 이치로 따지면 자연스럽고 당연한 얘기다. 당연히 함수는 함수의 인자가 될 수 있고, 더하거나 뺄 수 있는 값이며,식을 계산한 결과도 함수일 수 있다. 보통 이런 특징을 고차 함수(Higher-order Functions)라고 부르는데, 이 용어 때문에 이 기능이 특수하고 이질적인 표현 수단으로 오해받는 경우가 많다. 다시 말하지만 함수는 값이다. 우리가 쉽게 접할 수 있는 다른 많은 언어들이 오히려 잘못된 것이다.
 
딱딱하고 뜬구름 잡는 얘기는 이쯤에서 접고, 실제 프로그래밍을 하면서 차근차근 알아보자. 지난 호의 내용이 낯설고 어렵다는 반응이 와 이번에는 조금 반복되는 내용을 더해서라도 쉽게 쓰려고 노력했다. 우리에게 널리 알려지지는 않았지만, 함수를 써서 문제를 푸는 기법에 익숙하지 않은 프로그래머에게 Haskell과 같은 좋은 언어를 소개하는데 목적을 두었다.
 

Hugs98과 vim을 이용한 환경 설정

지난 호에서 이미 다룬 내용이지만 이번에는 쉽게 쓸 수 있는 GUI판을 예로 들어 설명한다. WinHugs라 불리는 이 판은 더 이상 지원되지 않으므로 실제로 연습할 때는 콘솔 버전을 쓰는 것이 좋을 것이다. 여기서는 단지 설명의 편의를 위해 잠시 이 버전을 사용하기로 한다.
Hugs는 http://cvs.haskell.org/Hugs/pages/downloading.htm에서 Hugs98-Dec2001.msi 파일을 받아 설치한다. 편집기로는 노트패드를 사용해도 되지만 지난 호에서 설명한 vim을 사용하기로 하자. vim을 구해(ftp://ftp.kr.vim.org/pub/vim) 설치한다. 윈도우 환경에서 Hugs와 vim을 연결하려면, Hugs를 실행한 후 메뉴에서 「Interperter|Option|Editor」를 선택한 다음, 아래와 같이 설정한다.
 
Editor : (각자의 vim 실행 파일의 경로) + %d %s 
예) C\vim6.0\vim60\gvim + %d%s
 
이와 같은 모든 기능은 콘솔에서도 환경변수와 Hugs 인터프리터 명령어로 설정할 수 있다. 콘솔 환경 설정에 관련된 사항은 Hugs를 다운받은 사이트에서 설명서를 구할 수 있으므로 참고하기 바란다.
이제 환경 설정이 잘 됐는지 확인하기 위해 Hugs를 실행하자. Haskell 스크립트를 작성하기 위해 연결된 Edit을 실행하려면 다음과 같이 한다.
 
:edit quicksort.hs  -- quicksort.hs 파일을 편집하겠다는 명령
 
 
<화면 1>은 연결된 편집기를 띄운 후, Haskell의 표현 방식으로 quicksort 프로그램을 작성한 것이다. 코드의 세부적인 내용은 차차 알게 되니 지금은 너무 신경쓰지 말자. 우선 ‘:wq’ 명령어로 저장한 다음 인터프리터 환경으로 돌아가자.
방금 작성한 스크립트를 환경에 더하기 위해 load 명령어로 읽어 들이고, 새로 정의한 quicksort 함수를 실행해 보자.
 
notion imagenotion image
 
Prelude>:load Quicksort.hs
Main> qsort [4, 3, 5, 7, 2]
Main>[2,3,4,5,7]
 
이와 같은 결과가 나왔다면, Haskell 프로그램을 위한 Hugs 설정 작업은 끝난 것이다. 앞으로 다룰 내용은 다른 언어와 유사하다. 그러나 문법이나 기본 의미를 되짚어 보기 위해 뻔한 내용이지만 한번 살펴보자.

Haskell의 계산 기능

Haskell과 친해지기 위해 계산 기능을 간단히 살펴보자. 쓰는 방법은 다른 언어와 크게 다르지 않다.
 
3 * (9 + 5)
-> 3 * 14
-> 42

3 * (9 + 5)
4 * (6 + 2)
7 * (8 + 1)
 
연산의 반복된 패턴을 함수로 만들어 보자. 함수를 정의하는 방법은 간단하다. 이와 비슷한 식 이 있으면 반복되는 표현을 찾아내어 다음처럼 함수로 표현할 수 있다.
 
easy x y z = x * (y + z)

Haskell의 타입

이번에는 식(expression), 값(value), 꼴(type)에 대해 알아보자. 쉽게 생각해 식은 값을 표현한다. 보통 값이라 하면 수나 문자열과 같은 상수 값을 뜻하는데 정확하게는 더 이상 줄일 수 없는 식이라고 해야 옳다. 즉 값도 식이다. 이와 달리 계산해야 값을 얻어 낼 수 있는 식이 있다. 이런 식을 redex(reduciable expression)라 하고, 여러 함수를 결합해 어떤 값을 어떻게 만들어 내는지 표현한다. 예를 들어 42는 값이고‘38 + 4’는 redex다.
Haskell의 모든 식은 꼴(타입)을 갖고 있다. 꼴이란 같은 속성을 갖고 있는 원소의 집합을 말한다. 지난 호에 설명한 바와 같이 Hugs에서 어떤 식의 타입을 알아보려면 다음과 같이 알 수 있다.
 
:t 42
🗣
42 :: Num a => a
 
Haskell에서 기본으로 제공하는 자료구조인 tuple과 list의 꼴은 다음과 같이 재미있게 표현된다.
 
[1,2,3] :: [Integer] -- Integer형 List
(‘b’,4) :: (Char,Integer) -- Char형과 Interger형이 쌍을 이루는 tuple
 
이번에는 함수의 타입을 알아보자. 앞에서 정의한 easy의 타입을 알아보면 다음과 같다.
 
easy :: Integer -> Integer -> Integer -> Integer
 
이 표현은 easy 함수가 정수 세 개를 차례대로 받아 정수형 값을 돌려주는 함수 값을 나타낸 것이다. Haskell에서 이와 같은 방식으로 식의 꼴을 표현하는 것을 type expression이라 한다. 쉬운 내용이지만 이런 표기방법에 익숙하지 않은 사람을 위해 우리가 잘 알고 있는 수학 함수의 개념과 간단히 비교해보자. 수학의 함수 정의와 같이 Haskell의 함수도 두 타입 간의 대응 관계를 표현한다. 그러므로 type expression의 문법은 다음과 같다
 
함수이름 :: 인자타입 -> 결과타입
그리고 다음과 같은 문법으로 정의한다.
 
함수이름 인자 = 정의
 
예를 들어, 어떤 수를 받아 그 수를 제곱하는 square의 완전한 정의는 다음과 같다.
 
square :: Integer -> Integer
square x = x * x
 
notion imagenotion image

Haskell의 제어 표현

지난 호에서도 언급했다시피 Haskell에서의 모든 제어식 표현은 필수 불가결한 특수 기능이 아니라 편리한 표현 수단으로 제공하는 기능이다. 다시 말해 제어를 목적으로 자주 쓰는 함수 값을 편리하고 읽기 쉽게 쓸 수 있도록 문법을더한 것일 뿐이다. Haskell에서는 ‘if A then B else C , |(Guard)’형태로 조건식을 표현한다. 예를 들면 다음과 같다.
 
add :: Integer -> Integer
add n = if n > 0 then n + add (n-1) else 0
 
조건이 여러 개일 경우에는 if then else의 중첩으로 가능하지만, 간단히 Guard expression(|)을 사용하면 깔끔하다. 뒤에 나오는 피보나치 수열을 구하는 함수(fibo)에서 사용 예를 볼 수 있다.
 

리스트

ML이나 Scheme, 파이썬 같은 언어를 써본 경험이 있다면 리스트를 사용하는 것에 익숙할 것이다. 리스트는 같은 꼴의 원소를 묶어서 처리할 때 매우 편리한 자료구조이며, C와 같은 언어에서 기본으로 제공하는 배열과 같은 역할을 한다. 그러나 리스트는 원소를 빼고, 붙이기가 쉬운 구조를 갖고 있으므로 배열을 쓸 때보다 프로그래밍하기가 매우 편리하다. 전에 이런 기능을 써본 적이 없더라도 Haskell의 리스트를 쓰는 방법이 직관적이므로 여기서는 간단한 기본 연산만 소개하고 넘어가기로 한다. 먼저 리스트를 다음과 같이 만들 수 있다.
 
[] -- 빈 리스트
[1] -- 원소 하나의 리스트
[1,3,2] -- 원소가 세 개인 리스트, 각 원소는 콤마로 구분
 
이외에 list comprehension이라 부르는 아주 아름다운 문법이 있다. 그 표현이 수학에서 집합을 표현할 때 쓰는 조건제시법과 크게 다를 바 없고, 앞으로 나오는 프로그래밍 예제에서 이 문법을 자주 보게 될 것이다.
<표1> Haskell에서 자주 사용하는 리스트 연산자
연산자
설명
!!
리스트에서 !! 다음의 인덱스에 해당하는 원소를 나타낸다. 예) [1,2,3,4,5] !! 3 → 4
++
리스트를 결합하는 연산자다. 예) [1,2] ++ [3,4,5] → [1,2,3,4,5]
:
원소를 엮어 리스트를 만드는데 오른쪽에서부터 결합한다. 예) 1 : 3 : 5 : [] → 1 : (3 : (5 : []))) → [1,3,5]
..
리스트는 순서대로 열거할 때 사용한다. 예) [1..10] → [1,2,3,4,5,6,7,8,9,10] 예) 처음 두 원소의 차가 다음 요소를 결정하는 경우 [1,3..8] → [1,3,5,7] — (3-1)

식을 줄이는 방법

지난 호에서 Haskell이 갖는 표현력은, 미뤄뒀다가 계산하는 기법(lazy evaluation, 옮긴이 주: 이를 '느긋한 평가'라 부르기도 한다. 반면 earnly evaluation은 '깐깐한 평가'라고도 한다.)에 바탕을 두고 있다고 설명했다. 이번에는 계산하는 기법의 종류와 동작 방식을 좀 더 자세히 알아보자. 계산 방법의 차이를 알면 왜 미뤄뒀다가 계산하는 기법이 더 풍부한 표현력을 제공하는지 알게 될 것이다.
식(expression)을 계산하는 방법에는 보통 두 가지가 있다. 안에서부터 밖으로 줄여가며 계산하는 방법(innermost)과 밖에서 안으로 줄여가며 계산하는 방법(outermost)이 있는데, 간단한 예제로 두 방법의 차이를 살펴보자. 다음의 코드는 수를 제곱하는 함수(square)와 이 함수를 사용해 더 복잡한 함수를 정의했을 때를 예로 든 것이다.
 
square x = x * x
square_sum x y = square x + square y
 
안에서부터 밖으로 줄여가는 방법을 쓰면 다음과 같이 계산한다.
 
square_sum (3 + 4) 5
→ square_sum 7  5     ( +의 정의에 따라 3 + 4 → 7 )  -- [1]
→ square 7 + square 5 ( square_sum의 정의에 따라 )   -- [2]
→ 7*7 + square 5      ( square의 정의에 따라 )
→ 49 + 5*5            ( *의 정의에 따라 )
→ 49 + 25             ( +의 정의에 따라 )
→ 74
 
두 단계를 거쳐 값이 나왔다. 앞에서 값과 식의 정의에 대해 얘기한 것과 같이 74라는 것은 더 이상 줄일 수 없는 식을 의미한다. 반대로 식을 밖에서부터 안으로 줄여가는 방법으로 계산하면 다음과 같이 전개된다.
 
square_sum (3 + 4) 5
→ square (3+4) + square 5    ( square의 정의에 따라 ) -- [3]
→ (3+4) * (3+4) + square 5   ( square의 정의에 따라 )
→ (3+4) * (3+4) + 5*5        ( square의 정의에 따라 )
→ 7 * (3+4) + 5*5            ( +의 정의에 따라 )      -- [4]
→ 7 * 7 + 5*5                ( +의 정의에 따라 )
→ 49 + 5*5                   ( *의 정의에 따라 )
→ 49 + 25                    ( *의 정의에 따라 )
→ 74                         ( +의 정의에 따라 )
 
이번에는 모두 8단계를 거쳐 값이 나왔다. 이 두 방법의 차이점을 하나하나 따라가 보면 계산 방법을 쉽게 알 수 있지만, 답부터 말하자면, 첫 번째 방법에서는 함수의 인자에 redex가 있으면 이를 먼저 계산하고, 인자 중에 redex가 없을 때, 그 값을 함수에 적용하는 방법이다. 즉, [1]에서 redex (3+4)가 7로 되고, [2]에서 함수를 계산하기 시작한다. 두 번째 방법은 식을 최대한 펼칠 수 있을 만큼 펼친 다음, 더 이상 펼칠 식이 없는 경우에 계산을 시작하는 방법이다. [3]에서처럼 (3+4)를 계산하지 않고 식 자체를 square_sum의 인수로 넘긴 후, 더 이상 식을 펼칠 수 없는 [4]에서 식을 줄여가기 시작한다. 이러한 특징 때문에, 첫 번째 방식을 AOR(applicative-order reduction)이라 하고, 두 번째 방식을 NOR(normal-order reduction)이라 한다. 두 방식의 차이를 좀 더 정확히 이해할 수 있도록 한가지 예를 더 살펴보자.
 
left x y = x
 
함수 left는 x, y 중에서 항상 x를 반환한다. AOR과 NOR 각각의 방법으로 식이 줄어가는 과정을 비교하기 위해 redex , left(square 4) (sqare 2)를 줄여 보자. 우선 AOR 방식을 적용해보면 다음과 같이 식이 전개된다.
 
left [square 4) (square 2)
→ left (4*4) (square 2)      ( square의 정의에 따라 )
→ left 16 (square 2)         ( *의 정의에 따라 )
→ left 16 (2*2)              ( square의 정의에 따라 )
→ left 16 4                  ( *의 정의에 따라 )
→ 16                         ( left의 정의에 따라 )
 
이와 달리, NOR을 쓰면 다음과 같다.
 
left (squarre 4) (square 2)
→ square 4                    ( left의 정의에 따라 )
→ 4 * 4                       ( square에 따라 (
→ 16                          ( *의 정의에 따라 )
 
 
이전 것과 달리 이 예제를 보면 확연히 나타난다. 값을 구하기 위해 AOR 방식은 5단계가 필요하며, NOR 방식은 3단계가 필요하다. NOR 방식이 더 간단한 이유는 square 2를 아예 계산하지 않기 때문이다. 즉, NOR은 식을 줄여가는 과정에서 필요하지 않은 식이라면 계산하지 않기 때문에 보통 NOR 방식을 쓰면 계산 과정이 짧다. 이런 특징은 계산 과정을 간편하게 할 뿐만 아니라 계산의 의미를 더 충실하게 반영할 수 있다는 장점이 있다. 다시 말해서 AOR 방식을 써서 계산할 수 없는 것도 NOR 방식을 써서 계산할 수 있다. 다음의 예를 보자.
 
newIf True thenExpr elseExpr = thenExpr
newIf False thenExpr elseExpr = elseExpr
 
이 식은 지난호에 예로 들었던 함수다. newIf를 사용해 다음 식을 계산한다고 하자.
 
newIf True 5 (4/0)
 
AOR을 사용할 경우에는 redex (4 / 0)를 먼저 계산하기 때문에 에러가 발생한다. 하지만 NOR 방식에서는 식이 펼쳐지는 과정에서 redex ( 4 / 0 )가 제외되기 때문에 에러 없이 값 5를 얻을 수 있다(물론 Haskell은 NOR 방식을 따르므로 5가 나온다). newIf의 정의에 따르면 조건이 True인 경우 필요없는 redex( 4/ 0 )가 계산 결과에 아무런 영향을 주지 않아야 하기 때문이다. 이처럼 필요없는 식을 계산하지 않기 때문에 표현력이 늘어나는 예를 하나 더 살펴보자(NOR 방식의 장점은 지난 호에서 밝힌 적이 있다. 여기서는 어떻게 그런 현상이 일어나는지 더 꼼꼼하게 살펴보도록 한다).
 
factIf n = newIf (n < 0) ( error“negative integer”) 
    (newIf(n == 0) 1 (n * factIf (n-1)))
 
factIf는 n까지의 팩토리얼을 구하는 함수다. factIf에는 Haskell이 제공하는 제어식 if를 쓰는 대신, 같은 기능의 함수 newIf를 사용했다. factIf 3을 AOR과 NOR을 이용해서 계산하는 과정을 스스로 그려보기 바란다. 먼저 AOR 방식으로 factIf 3을 계산하는 경우 인자가 모두 계산한 후 newIf 전체 식을 계산하기 때 문에 계산을 멈출 수 없다. 달리 말하면 함수 newIf는 계속 펼쳐지기만 할 뿐 값으로 줄어들 기회를 갖지 못하게 된다. 진행 과정을 보자.
 
factIf 3 = newIf ( 3 < 0 ) (error“..”)
( newIf (3==0) 1 (3*factIf( 3- 1)))
= ...

= newIf False ( error“..”) 
   ( newIf False 1 (3 * factIf 2))
   = ..... ( newIf True 1 (1*factIf (-1))) = ..... ( newIf True 1 (1* newIf (-1 < 0)
(error“..“)(newIf (-1==0) 1 ( 0* factIf(-1-1)) = ...
= ..... (newIf False 1 (0* factIf (-2))
 
인자를 계산한 후 함수에 적용하기 때문에 계속 인자의 값을 구하기 위해 무한 반복이 발생하고 결코 값을 가질 수 없다. 다시 말하면, 함수 newIf는 계속 펼쳐지기만 할 뿐 값으로 줄어들 기회는 갖지 못한다는 것이다.
반대로 NOR 방식을 보기로 하자. 식을 풀기 위해 전개되는 과정을 그려보면 다음과 같을 것이다.
 
factIf 3 = newIf (3<0) (error“..“)
(newIf ( 3== 0) 1 (3 * factIf(3-1)))
= newIf False (error“..“)
(newIf (3== 0 ) 1 (3 * factIf (3-1))
� (3<0)이 newIf가 전개되기 전에 먼저 계산이 됐다.
= newIf (3 == 0) 1 (3* factIf(3-1)) � False이기 때문 = newIf False 1 (3 * factIf (3-1))
� (3==0)이 newIf 전개 이전에 먼저 계산
= 3 * factIf (( 3-1)-1) � False이기 때문 = .....
= 3 * (3-1) * ((3-1)-1) * factIf (((3-1)-1)-1)
= 3 * (3-1) * ((3-1)-1) * newIf
((((3-1)-1)-1) <0)(error“..“) (newIf ((((3-1)-1)-1)== 0) 1
(((3-1)-1) * factIf((((3-1)-1)-1)-1))) =3*(3-1)*((3-1)-1)*1 =3*2*((3-1)-1)*1=3*2*(2-1)*1=3*2*1*1 =6*1*1=6*1=6
 
우리가 작성한 newIf가 Haskell에서 기본으로 제공하는 if~then~else와 동일하게 동작해 factIf 3의 식을 6이라는 값으로 바르게 변화시켰다. 이것을 가능하게 한 것은 Haskell이 NOR 전개 방식을 기반으로 하고 있기 때문이다(원래 이 곳에서 패턴매칭(pattern matching)에 관한 이야기를 더 언급해야 하지만 다소 어려운 내용이라 생략하기로 하겠다).
여기서 중요한 사실을 발견할 수 있다. Haskell은 NOR 방식을 바탕으로 하기 때문에 if, while 등과 같은 제어식이 특별한 기능으로 제공되지 않아도 일반 함수와 별다를 바 없이 만들어 쓸 수있다.이 말은 어떤 특수한 기능을 더해도 언어의 기본 의미 구조가 파괴되거나 체계 없이 늘어날 이유가 없다는 것을 뜻한다. 이와 같이 Haskell의 모든 풍부한 표현력은 문법을 확장한 것에 불과하다. 하지만 자바 ∙ C# ∙ C++ 같은 언어에서는 새로운 기능을 추가할 때마다 언어의 의미도 복잡해지고, 그와 함께 언어 자체의 덩치도 감당할 수 없을 만큼 불어난다. 그러므로 비슷한 수준의 표현력을 제공한다고 하더라도 C++는 무겁고 복잡한 언어라는 오명을 씻을 수 없고, Haskell과 같은 언어는 가볍고, 간결한 언어로 남아 있게 되는 것이다.
여러 예를 통해 NOR이 AOR에 비해 많은 장점을 갖고 있고, 유연성이 뛰어나다는 사실을 알았다. 하지만 효율성 면에서 두 방식을 비교해 보면 사뭇 다른 방식이 나올 때가 있다. 인수가 함수 내에서 반복 사용되는 redex라면, AOR은 인수를 함수에 건네줄 때 한번만 계산하면 되지만, NOR은 완전히 펼친 다음 사용하기 때문에 같은 redex가 전체에서 여러번 나타난다. 이런 경우라면, NOR이 AOR에 비해 효율이 훨씬 떨어진다(앞에서 square_sum을 NOR 방식으로 전개했을 때 (3+4)가 두 번 계산되는 것을 확인 할 수 있다). 이렇게 효율의 차가 크기 때문에 NOR 방식을 쓰더라도 이런 문제를 해결하는 기법이 필요하다. NOR 방식으로 식을 전개하는 과정은 나무구조를 사용하지만, 그래프 구조를 사용해 같은 redex를 함께 쓸 수 있다면, 효율이 떨어지는 문제를 잘 해결할 수 있다.
 
notion imagenotion image
 
<그림 3>에서 알 수 있듯이 식의 구조를 그래프 방식으로 전개하면 redex를 반복해서 쓰는 것이 아니라 하나의 redex를 여러 곳에서 함께 사용할 수 있다. 이와 같이 그래프 구조로 만들어진 식을 그래프 리덕션(Graph reduction)이라 하고 식은 다음과 같 이 줄어든다.
 
notion imagenotion image
 
 
그래프 줄이는 방식을 쓰면 AOR과 같은 7단계로 처리되는데, 같은 식을 한번 이상 계산하지 않기 때문에 이런 효과를 얻을 수 있다. 그래프 줄이는 방식은 좋지 않아도 AOR과 처리 효율이 동일하다. 이런 계산 방식을 lazy evaluation이라 부르고, 이와 대조해서 AOR 방식에 바탕을 두는 계산 방식을 eager evaluation이라 부르기도 한다. Haskell은 lazy evaluation을 쓴다.
 

함수로 쓰는 프로그래밍

 
지금까지 함수로 프로그램을 작성하기 위한 배경 지식을 살펴보았다. 이제 Haskell을 사용해 함수로 프로그래밍하는 방법을 배워보자. Haskell의 독특한 기능만을 이용하는 프로그래밍 기법은 다음호로 미루고, 함수를 쓰는 언어라면 모두 사용할 수 있는 기법을 소개하겠다. 우리가 풀어야 할 문제는 다음 두 가지다.
 
문제 1 : 임의로 제공되는 리스트의 원소 중에서 홀수만을 뽑아내고 그 값을 제곱한 결과를 모두 더한 값을 구하라.
문제 2 : 주어진 수까지의 피보나치 수열을 모두 구한 다음, 그 중에서 짝수인 것만의 리스트를 구성하라.
 
지금까지 소개한 표현을 사용해 별다른 생각없이 문제를 푼다면 대부분 답은 다음과 같을 것이다

문제 1에 대한 풀이:

sum_odd_square [] = 0                         -- [1]
sum_odd_square (x:xs)
    | odd x     = x * x + sum_odd_square xs   -- [2]
    | otherwise = sum_odd_square xs           -- [3]
 
 
[1]은 인자로 리스트를 받아 리스트가 비어 있으면 0을 돌려준다. [2]는 인자로 리스트를 받아 리스트의 첫 요소가 홀수이면 x 를 제곱하고 리스트에서 첫 요소를 뺀 나머지 리스트로 재귀 호출한다. [3]은 홀수가 아니면 첫 요소를 무시하고 첫 요소를 제외 한 나머지 리스트로 재귀 호출한다.
 

문제 2에 대한 풀이:

even_fibo' = reverse . even_fibo                -- [1]
    where even_fibo n =                         -- [2]
        if n == 0 then [0]                      -- [3]
        else if even k then k : even_fibo (n-1) -- [4]
        else    even_fibo (n-1)                 -- [5]
        where
            k = fibo n                          -- [6]

-- 피보너치 수열을 구하는 함수
fibo n                                          -- [7]
    | n == 0 = 0
    | n == 1 = 1
    | otherwise = fibo (n-1) + fibo (n-2)
 
 
[1] even_fibo’는 even_fibo와 reverse의 합성 함수로 reverse는 주어진 리스트와 반대 순서로 원소를 열거한 리스트를 만드는 함수이다(reverse . even_fibo는 ( . ) reverse even_fibo와 동일한 표현이다).
[2] even_fibo n은 n까지의 피보나치 수열을 구하여 리스트를 만드는 함수이다. [3] n이 0이면 [0]을 반환한다. [4] k의 결과가 짝수이면 리스트에 추가한다.
[5]∙[3]∙[4]를 제외한 경우는 n을 1 감소시키고 재귀 호출한다.
[6] k는 n에 대한 피보나치 수열을 반환한다.
[7] fibo는 n=0이면 0, 1이면 1, 그 외는 fibo( n - 1)과 fibo( n - 2 )의 합이다(재귀 호출).
두 문제를 Haskell로 표현해 보았다. 하지만 문제를 푸는 방식은 함수를 쓰는 기법답지 않다. 그저 답이 나오도록 문제를 표현했을 뿐이다. 그러므로 Haskell 다운 프로그램은 아니다. 이제부터 좀더 Haskell 답게 함수를 잘 쓰는 프로그램으로 바꿔보자.
우선 첫 번째 문제를 쉽게 이해할 수 있는 작은 단위로 나눠보자. 구분되는 기능에 따라 주어진 문제를 세 개의 작은 문제로 나눌 수 있다. 각각의 나눠진 문제는 기능을 한번에 쉽게 파악할 수 있을 만큼 작고 단순하다. 어려운 문제를 이렇게 나눌 수만 있다면 프로그래밍이 정말 쉽지만 정작 어려운 것은 큰 문제를 이렇게 잘라내는 일이다.
 
  1. 리스트에 있는 원소 중에서 홀수만을 뽑아내라.
  1. 리스트에 있는 모든 원소를 제곱하라.
  1. 리스트 안에 있는 모든 원소를 더하라.
 
각 단계를 다른 문제로 생각하고 차례대로 필요한 기능을 만들자. 1번은 Haskell의 표준 라이브러리인 표준 prelude에서 제공하는 filter와 odd를 사용하면 풀 수 있다. 함수 odd는 홀수면 True, 짝수이면 False 값을 돌려주며, 함수 filter는 리스트(xs)에서 모든 원소(x)를 차례로 검사하고 어떤 조건(p)을 만족하는 원소 ([ x | ... ])만 모은 리스트를 만들어 돌려준다.
 
-- filter의 정의( Prelude.hs)
filter :: (a -> Bool) -> [a] -> [a]
filter p xs =[x | x <- xs, px]
-- 예) 1에서 10까지 리스트에서 홀수 뽑기
filter odd [1..10]
🗣
[1,3,5,7,9]
 
2는 표준 함수 map과 square 함수를 만들면 풀 수 있다. square는 간단하게 수를 제곱하는 함수이다. map은 어떤 리스트(xs)에 함수 f를 적용한 결과를 리스트로 만들어 돌려준다.
[x2,x2,...] → [f x1, fx2, ...]
 
-- map의 정의(Prelude.hs)
map ::(a -> b) -> [a] -> [b]
map f xs = [f x| x <- xs]
-- 예) 1에서 5까지 리스트 원소 제곱하기
map square [1..5]
 
🗣
[1,4,9,16,25]
 
3은 표준함수 foldr과 (+)함수를 사용해서 풀 수 있다. 이 문제를 푸는 데 쓰는 foldr(folding right) 함수는 foldl(folding left)과 함께 Haskell 프로그래밍에서 가장 많이 쓰는 함수 중 하나로, 이번 기회에 어떤 기능인지 확실히 알고 넘어가는 것이 좋다.
foldr함수는 세 개 인자를 받는데, 첫째 인자인 f는 2진 연산이고, 둘째 인자 z는 초기 값이며, 마지막이 f로 묶어버릴 리스트이다. 풀어 설명하면 foldr 함수의 기능은 리스트의 모든 원소와 초기 값을 사용해 함수 f로 묶어버리는 것이다. foldr 함수를 이해하려면 다음 예와 같이 식을 전개해봐야 제대로 이해할 수 있다. 일단 익숙해지면 foldr만큼 재사용성이 뛰어난 함수도 드물다는 걸 자연스럽게 알게 될 것이다.
 
-- foldr의 정의(Prelude.hs)
foldr ::(a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
-- foldr의 예) 리스트 안의 모든 원소를 더하라
foldr (+) 0 [1..3]
--(+)1((+) 2 ((+) 3 0))) → 6

foldr (:)[][1..3]
-- (:) 1 ((:)2((:) 3 [])))-->[1,2,3]
 
[1]에서 [3]까지 풀어놓은 작은 문제들을 붙여 전체 문제를 풀어보면 다음과 같다.
 
sum_of_square xs = foldr (+) 0 (map square (filter odd xs))
옮긴이 주: $를 이용해서 다음과 같이 좀 더 간결하게 만들 수도 있다.
sum_of_square xs = foldr (+) 0 $ map square $ filter odd xs
 
전에 풀었던 방법보다 깔끔하긴 하지만 이렇게 문제 푸는 방식에 익숙하지 않은 사람에게는 여전히 마술과도 같은 표현이다. 그러나 작은 문제가 어떻게 연결됐는지는 <그림 4>를 보면 이해하기 쉽다.
 
notion imagenotion image
 
비슷한 방식으로 두 번째 문제를 풀어보자 먼저 두 번째 문제 도 다음과 같이 작게 나눈다.
 
  1. n까지 리스트를 만들어라.
  1. 리스트에 있는 각 원소에 대한 Fibonacci 수를 구하라.
  1. 리스트에서 짝수 만을 뽑아내라.
 
1번 문제를 풀려면 일정한 범위의 원소를 열거해 리스트로 만드는 기능이 필요하다. Haskell에서는 모든 원소의 순서관계(total order)가 정해진 집합의 원소를 enumFromTo 함수를 사용해 쉽게 리스트로 묶을 수 있다. 예를 들어 3에서 100까지의 원소를 묶으려면 다음과 같이 표현하면 된다.
 
enumFromTo 3 100
 
참고로 앞의 식과 의미가 같은 간편한 표현을 사용하려면, [3..100]과 같이 사용하면 된다. 2번 문제는 표준 함수 map과 Fibonacci 수를 구하는 fibo 함수를 만들어 간단하게 풀 수 있다. map은 첫 번째 문제를 풀면서 설명했고, fibo 함수는 글 앞머리에서 정의한 바 있다.
 
-- 예) 1에서 5까지의 피보나치 수를 구하고 리스트를 만들어라.
map fibo [1..5]
🗣
[1,1,2,3,5]
 
3번 문제는 표준함수 filter와 even을 사용해 풀 수 있다. 이 문제는 첫 번째 문제의 2번과 같은 문제로 odd 대신 even을 썼을 뿐이다.
 
-- 사용 예) 1에서 10까지의 수에서 짝수만을 뽑아내어 리스트를 만들어라.
filter even [1..10]
[2,4,6,8,10]
 
이제 모든 문제를 합쳐서 두 번째 문제를 풀어보자.
 
even_fibs n = (filter even (map fibo [0..n]))
 
notion imagenotion image
 
앞에서와 마찬가지로 프로그램의 구조는 <그림 5>와 같다. 두 번째 문제를 풀기 위해 쓰는 함수는 첫 번째 문제에서 이미 써본 것들이기 때문에 이해하기 어렵지 않다. 전체 문제를 하나의 함수만 사용해서 풀어내면, 문제를 풀기 어렵고 프로그램 코드도 복잡하다. 더 나쁜 것은 두 문제 사이의 공통점을 발견할 수 없다는 점에 있다. 복잡한 문제를 작은 문제로 잘 나누어 풀면 문제를 풀기 쉬울 뿐만 아니라 앞의 예와 같이 공통점을 찾아내기가 쉽다. 같은 문제를 찾아내는 방식으로 프로그램하게 되면 map, filter, foldr과 같이 다시 쓸 가능성이 매우 높은 함수를 얻어낼 수도 있다. 정말로 map, filter, foldr과 같은 함수는 그 쓰임새가 무한하다. 이런 함수를 표현할 수 있는 이유가 함수를 데이터로 쓰기 때문에 가능하다는 것을 알아두자. 보통 map, filter, foldr 같이 함수를 인자로 받거나, 돌려주기도 하는 함수를 고차함수(higher-order function)라고 부르기도 한다. 고차 함수란 말은 함수로 값을 취급하지 않는 즉, 언어에서의 함수와 다르다는 것을 강조하기 위해 나온 용어일 뿐이다. 하지만 그 의도와 달리 자연스럽지 않다는 느낌을 주기 때문에 그 의미가 왜곡되거나 부풀려서 받아들여지기도 한다. 고차함수는 함수 그 자체의 의미에 더욱 가깝고, 자연스러운 표현일 뿐이다.
큰 문제를 작은 문제로 나누어 풀어내는 기법을 앞에서 공부했다. 이 기법의 장점을 더 확실히 느껴보기 위해 몇 가지문제를 더 풀어 보자. 가능하면 스스로 풀어본 다음 이 글에서 제시한 답과 비교해 보기 바란다.
 
문제 3 : n+1번째까지 피보나치 수열을 제곱한 리스트를 만들어 보라.
문제를 둘로 나눈다.
  1. n까지의 피보나치 수열을 구하여 리스트로 만든다
  1. 리스트의 내용을 제곱한다.
두 기능은 앞에서 사용한 함수를 다음과 같이 붙여서 해결할 수 있다.
 
list_square_fib_n n = (map square (map fibo [0..n]))
 
문제 4 : 주어진 리스트 내의 모든 홀수만 골라내어 제곱한 리스트를 만들고, 그 리스트의 모든 원소를 곱한 값을 구하라.
문제를 다음과 같이 작게 나눈다.
  1. 리스트에서 홀수를 골라낸다.
  1. 리스트의 원소를 제곱한다.
  1. 리스트의 원소를 모두 곱한다.
이 문제 역시 앞에 소개한 함수만 사용해도 간단하게 풀어낼 수 있다.
 
product_odd_square xs = foldr (*) 1 (map square (filter odd xs))
 
문제 5 : 어떤 회사의 인사기록 자료가 있을 때, 프로그래머 중 가장 높은 급여액을 찾아내라.
다음과 같이 문제를 잘라낸다.
  1. 인사기록 자료에서 프로그래머의 자료만 뽑아낸다.
  1. 인사기록 자료에서 급여만 뽑아서 리스트로 만든다.
  1. 리스트 중에서 최대 값을 뽑아낸다.
 
세 개의 함수 isProgrammer, salary, max를 만들었다고 가정하고 문제를 풀어보자. 이 때, 각각의 함수의 기능을 살펴보자. isProgrammer는 한 레코드를 살펴보고 그 업무가 프로그래머인지 아닌지 확인하는 함수이며, salary는 한 개의 인사기록 레코드에서 급여만 가져오는 함수다, 그리고 max는 리스트에서 가장 큰 원소를 뽑아내는 함수다.
 
salary_of_highest_programmer records
    = foldr max 0 (map salary (filter isProgrammer records)))
 

좋은 게 편한 건 아니다

이번호에는 함수를 쓰는 프로그래밍 기법을 소개했다. 이런 기법이 처음이라면 어려운 것은 당연하다. 그러나 쉽다는 것은 익숙함에서 오는 지극히 주관적인 생각이다. 익숙해지면 쉬워진다. 물론 좋다는 것이 편하다는 것을 뜻하지는 않는다. 그러나프로그래밍은 편해야 될 일이 아니라 제대로 해야 될 일이다. 그러므로 프로그래밍의 가치는‘제대로’에 초점을 맞춰야 한다.
최근에 이런 언어를 연구하는 활동이 있어 매우 기쁘다. 제대로 프로그래밍하는 재미를 느끼는 데 이 글이 부족하다면, http://ropas.kaist.ac.kr/~kwang 에서 바라던 바를 찾아낼 수 있을지 모르겠다. 이 웹 페이지에서 ‘지금의 정보기술을 보는 눈높이 I,II’란글을꼭읽어보기바란다.
 

참고문헌

 
  • Herold Abelson, Gerald Jay Sussman with Juile Sussman,“Structure and Interpretation of Computer Programs,” 2nd Ed. MITPress, 1996
  • Richard Bird,“Introduction to Functional Programming using Haskell,”2nd Ed. PrenticeHall, 1998
  • Richard Bird, Philip Wadler,“Introduction To Functional Programming,” PrenticeHall, 1988
  • Anthony J. Field, Peter G.Harrison“ Functional Programming,” Addison Wesley, 1988
  • TimothyBudd,”MultiparadigmProgramminginLeda,”AddisonWesley, 1995
  • Paul Hudak John Peterson,Joseph Fasel,”The Gentle Introduction to Haskell,” http://www.haskell.org/tutorial/,2000
  • Simon Peyton Jones, AboutHaskell,”http://www.haskell.org/aboutHaskell.html, 2001
 
Copyright (c) 2002 김재우. All rights reserved.