KANSU PROGRAMMING JISSEN NYUMON by Noriyuki Ookawa Copyright 2014 Noriyuki Ookawa All rights reserved. Original Japanese edition published by Gijyutsu

Transcription

1

2 KANSU PROGRAMMING JISSEN NYUMON by Noriyuki Ookawa Copyright 2014 Noriyuki Ookawa All rights reserved. Original Japanese edition published by Gijyutsu-Hyoron Co., Ltd., Tokyo. This Korean language edition published by arrangement with Gijyutsu-Hyoron Co., Ltd., Tokyo in care of Tuttle-Mori Agency, Inc., Tokyo through Danny Hong Agency, Seoul. Korean translation copyright 2015 by J-PUB. 이 책의 한국어판 저작권은 대니홍 에이전시를 통한 저작권사와의 독점 계약으로 제이펍에 있습니다. 저작권법에 의하여 한국 내에서 보호를 받는 저작물이므로 무단전재와 무단복제를 금합니다. 초판 1쇄 발행 2015년 8월 21일 지은이 오카와 노리유키 옮긴이 정인식 펴낸이 장성두 펴낸곳 제이펍 출판신고 2009년 11월 10일 제 호 주소 경기도 파주시 문발로 141 뮤즈빌딩 403호 전화 / 팩스 홈페이지 / 이메일 jeipub@gmail.com 편집부 이민숙, 이 슬, 이주원 / 소통 기획팀 민지환, 현지환 표지디자인 미디어픽스 / 본문디자인 북아이 용지 에스에이치페이퍼 / 인쇄 해외정판사 / 제본 광우제책사 ISBN (93000) 값 30,000원 이 책은 저작권법에 따라 보호를 받는 저작물이므로 무단 전재와 무단 복제를 금지하며, 이 책 내용의 전부 또는 일부를 이용하려면 반드시 저작권자와 제이펍의 서면동의를 받아야 합니다. 잘못된 책은 구입하신 서점에서 바꾸어 드립니다. 제이펍은 독자 여러분의 책에 관한 아이디어와 원고 투고를 기다리고 있습니다. 책으로 펴내고자 하는 아이디어나 원고가 있으신 분께서는 책에 대한 간단한 개요와 차례, 구성과 저(역)자 약력 등을 메일로 보내주세요. jeipub@gmail.com

3

4 드리는 말씀 이 책에 기재된 내용을 기반으로 한 운용 결과에 대해 저자, 역자, 소프트웨어 개발자 및 제공자, 제이펍 출판사는 일체의 책임을 지지 않으므로 양해 바랍니다. 이 책에 등장하는 각 회사명, 제품명은 일반적으로 각 회사의 등록 상표 또는 상표입니다. 본문 중에는 TM, C, R 마크 등이 표시되어 있지 않습니다. 이 책에서 사용하고 있는 제품 버전은 독자의 학습 시점이나 환경에 따라 책의 내용과 다를 수 있 습니다. 본문 중 일본 내의 실정에만 국한되어 있는 내용이나 그림은 일부를 삭제하거나 국내 실정에 맞도 록 변경하였으니 참고 바랍니다. 책 내용과 관련된 문의사항은 옮긴이나 출판사로 연락해 주시기 바랍니다. 옮긴이: insik8463@gmail.com 출판사: jeipub@gmail.com

5 차 례 옮긴이 머리말... ⅹⅵ 머리말... ⅹⅶ 이 책의 구성... ⅹⅹⅰ 이 책에 필요한 사전 지식... ⅹⅹⅱ 베타리더 후기... ⅹⅹⅳ Chapter 0 [입문] 함수형 프로그래밍 함수 의 세계 _ 함수형 프로그래밍, 그 전에 실용 프로그램에서 활용하는 강점 알기 4 함수형 프로그래밍을 통해 얻을 수 있는 개선 함수란 무엇인가? 명령형 언어의 함수와 무엇이 다른가? 5 함수형 프로그래밍에서 함수 6 부작용 함수형 프로그래밍이란 무엇인가? 프로그램이란 함수다 라는 관점 9 프로그래밍의 패러다임 9 함수가 갖는 모듈화 프로그램을 구성하는 부품 의 독립성 함수형 언어란? 함수가 1급(first class) 대상이다? 대입이 없다? 12 함수형 언어이기 위한 조건 12 차 례 v

6 함수형 언어와 명령형 언어 14 Column 다양한 함수형 언어 함수형 언어의 특징적인 기능 타입의 유무, 정적/동적, 강약 20 typed와 untyped 20 정적 타입과 동적 타입 21 순수 22 타입 검사 23 강한 타입과 약한 타입 24 타입의 추론 24 Column 약한 타입은 무엇을 위한 것인가? 25 의존 타입 25 평가 전략 25 주요 함수형 언어와 명령형 언어의 기능 리스트 왜 지금 함수형 언어인가? 추상화, 최적화, 병행/병렬화 28 함수형 언어의 추상화 수학적인 추상화란? 28 함수형 언어의 최적화 29 함수형 언어와 병행/병렬 프로그래밍 34 Column 함수형 언어와 정리 증명 함수형 언어와 함수형 프로그래밍의 관계 강력한 성과를 끌어내기 위해서는 어떻게 하면 좋은가? 41 함수형 프로그래밍의 도입 명령형이라도 활용할 수 있는 기법 41 함수형 언어에 의한 함수형 프로그래밍의 도입 함수형 언어의 역사 과거를 알고 미래 탐구하기 43 함수형 언어의 발자취 - 지금까지 43 함수형 언어의 발자취 - 앞으로 함수형 언어를 채용하는 장점 선언적일 것, 제약의 충족 체크, 타입과 타입 검사, 타입 추론 49 선언적인 것의 장점 49 제약의 충족 여부를 체크해 주는 장점 50 타입과 타입 검사가 있는 경우의 장점 51 vi 하스켈로 배우는 함수형 프로그래밍

7 타입 추론의 장점 이 책에서 다루는 함수형 언어 Haskell의 특징, 구현, 환경 구축 54 Haskell이 갖는 특징적인 기능 54 Haskell의 구현 55 Haskell 환경의 구축 정리 60 Column 현재 함수형 언어가 채택되어 있는 분야/제품 60 Chapter 1 [비교를 통해 발견하기] 함수형 프로그래밍 C/C++, JavaScript, Ruby 그리고 Haskell _ 좌표 변환 부품 조합하기 66 동일한 것에서 동일한 것으로의 변환 조합하기 66 2차원의 좌표 변환 66 C언어의 경우 맞지 않는 부품 68 JavaScript의 경우 맞을지 안 맞을지도 모르는 부품을 만들거나 맞추는 능력 71 Haskell의 경우 알맞는 부분을 만들거나 알맞는 부품만 맞추는 능력 NULL considered harmful 10억 달러 단위의 실수 79 NULL이 나타내는 것 80 NULL의 위험성 80 값이 없는 것을 취급하는 방법 소수를 세기 올바른 병렬화와 그 사양 변경 대응 90 C(OpenMP)의 경우 어노테이션에 의한 병렬화 91 Haskell의 경우 위험한 병렬화를 배제 96 Column 그래도 병렬화는 어렵다 99 차 례 vii

8 1.4 구조화 데이터의 취급 Visitor 패턴 100 Java(Visitor 패턴)의 경우 비대화와 교환의 유연성 100 Haskell의 경우 타입의 정의/사용의 용이성 문자열의 이스케이프 타입에 성질 갖게 하기 108 HTML의 문자열 이스케이프 108 Ruby의 경우 성질의 수정은 이용자의 권리 110 Haskell의 경우 성질의 보증은 제공자의 의무 정리 118 Chapter 2 타입과 값 타입 은 기본 중의 기본 _ Prelude 기본 모듈 122 기본의 Prelude 모듈 값 조작의 대상 123 값의 기본 123 리터럴 값의 표현 및 그에 대한 방법 124 값 생성자 Haskell의 부울 값 True/False는 값 생성자 변수 값의 추상화 129 변수 129 상수 130 속박 타입 값의 성질 132 타입의 기본 132 타입의 확인과 타입 어노테이션 133 함수의 타입 135 viii 하스켈로 배우는 함수형 프로그래밍

9 의도적으로 피한 타입의 확인 139 타입 검사 139 다형성과 타입 변환 141 타입 추론 타입 정의하기 취급하는 성질의 결정 151 기존의 타입에 별명을 붙인다 type 선언 151 기존의 타입을 기반으로 새로운 타입 만들기 newtype 선언 152 완전히 새로운 타입 만들기 대수 데이터 타입 154 대수 데이터 타입과 프로덕트 타입/섬 타입 타입 클래스 타입에 공통된 성질 165 타입 클래스란 무엇인가? 165 타입 클래스 확인하기 167 다양한 타입 클래스 정리 178 Column 생성자명에 망설이지 않고 데이터의 구조 파악하기 179 Chapter 3 함수 함수 적용, 함수 합성, 함수 정의, 재귀 함수, 고차 함수 _ 함수 만들기 기존의 함수로부터 만들기, 직접 새로운 함수 정의하기 182 함수를 만드는 방법 함수 적용 기존 함수의 인수에 값 부여하기 182 함수 적용의 스페이스(공백) 183 함수 적용의 결합 우선도 183 (함수의 결과로서의) 함수에 함수 적용 184 함수의 2항 연산자화 185 2항 연산자의 함수화 186 차 례 ix

10 부분 적용 함수 합성 기존의 함수 연결하기 188 함수 합성과 합성 함수 Haskell의 소스 파일 소스 파일에 함수를 정의하여 GHCi에서 읽어 보기 191 샘플 파일의 준비와 GHCi로의 로딩 191 소스 파일에서의 추가/편집, 리로딩 함수 정의 패턴 매치와 가드 194 일반적인 함수의 정의 194 패턴 매치 데이터의 구조 보기 194 가드 데이터의 성질을 보기 202 패턴 매치와 가드를 조합하기 204 case와 if 205 Column 문장 과 식 과 그 판별 207 where와 let 209 Column 경우 분류 의 문법상의 편의 알고 보면 전부 case 재귀 함수 반복적인 행동을 정의하는 함수 213 세 개의 제어 구조와 재귀 함수의 자리 매김 연결, 분기, 반복 213 재귀적 정의 214 함수의 재귀적 정의 215 다양한 재귀 함수 216 재귀적인 사고의 요령 219 재귀의 위험성과 그 대처 221 Column 그렇게 많이 재귀를 해도 괜찮을까(?!) 고차 함수 결과가 함수가 되는 함수, 인수로서 함수를 요구하는 함수 222 고차 함수란? 222 결과가 함수가 되는 함수 223 인수로서 함수를 요구하는 함수 223 고차 함수 정의하기 224 다양한 고차 함수 225 x 하스켈로 배우는 함수형 프로그래밍

11 3.8 정리 234 Column 세계에서 가장 아름답다? 퀵 정렬? 235 Chapter 4 평가 전략 지연 평가와 적극 평가 _ 지연 평가를 살펴보자 유효하게 이용할 수 있는 예로부터 확실히 배우기 238 다라이 함수(다케우치 함수) 238 무한의 데이터 244 생략에 의한 오류 내성 249 평균값 평가 전략 지연 평가와 적극 평가의 구조, 장점 및 단점 256 평가 전략과 지연 평가 256 축약 257 적극 평가 260 지연 평가 261 적극 평가와 지연 평가의 이점과 결점 평가 제어하기 성능 튜닝을 위해서 269 성크 없애기 269 Haskell 버전 다라이 함수를 느리게 하기 271 C++ 버전 다라이 함수를 빠르게 하기 정리 275 차 례 xi

12 Chapter 5 모나드 문맥을 지닌 계산을 다루기 위한 장치 _ 타입 클래스를 다시 한 번 살펴보기 직접 만든다는 관점으로 280 타입 클래스 정의하기 280 타입 클래스의 인스턴스 만들기 281 타입 클래스 인터페이스의 디폴트 구현 283 [비교] 다른 언어의 비슷한 기능 과 타입 클래스 모나드의 사용법 문맥을 잘 취급하기 위한 타입 클래스 인터페이스 288 문맥을 갖는 계산 모나드를 사용하는 동기 288 타입 클래스로서의 모나드 액션, return(주의!), bind 연산자 297 모나드 법칙 인스턴스가 만족해야 할 세 가지 성질 298 do 표기법 여러 가지 모나드 Identity, Maybe, 리스트, Reader, Writer, State, IO 304 Identity 문맥을 갖지 않는다 304 Maybe 실패의 가능성을 갖고 있다 305 리스트 복수의 가능성을 갖고 있다 309 Reader 참조할 수 있는 환경을 공유한다 314 Writer 주요 계산의 옆에서, 별개의 값도 일직선으로 합성한다 318 State 상태의 인계 324 IO 부작용 동반하기 다른 언어에 있어서의 모나드 모나드나 이와 유사한 기능의 서포트 상황 332 다른 함수형 언어와 모나드 332 명령형 언어와 모나드 Java 모나드와의 비교 Haskell 프로그램의 컴파일 컴파일해서 Hello, World! 337 일반적 인 실행 방법에 대해 컴파일하여 실행하기 정리 338 Column 함수형 언어로 밥먹고 살기 339 xii 하스켈로 배우는 함수형 프로그래밍

13 Chapter 6 추천하는 개발/설계 테크닉 함수형/Haskell식 의 프로그램 설계/구현, 사고 _ 동작 결정하기 테스트를 작성하자 344 테스트, 그 전에 344 테스트를 위한 라이브러리 345 doctest/quickcheck에 의한 테스트 하향식으로 생각하기 문제를 큰 틀에서 파악하고 작은 문제로 분할해 나가기 349 런 렝스 압축(RLE) 350 숫자넣기(스도쿠) 제약 설계하기 타입에 제약 갖게 하기 384 제약을 어떻게 표현할까? 384 2의 거듭제곱을 요구하는 인터페이스 385 2의 거듭제곱이라는 제약을 갖는 수의 타입 386 가시성을 제어하여 성질 보호하기 적절한 처리를 선택하게 하기 타입과 타입 클래스를 적절하게 이용하여 타입에 제약 기억시키기 394 복수의 이스케이프 보다 복잡한 제어 부여하기 매우 강력한 로직 퍼즐의 예 404 논리 퍼즐 3인의 점심 정리 415 차 례 xiii

14 Chapter 7 Haskell에 의한 제품 개발의 길 패키지와의 교제 _ 패키지의 이용 패키지 시스템 Cabal 420 Haskell의 패키지 시스템 420 공개되어 있는 패키지 이용하기 cabal편 422 공개되어 있는 패키지 이용하기 Cabal sandbox편 패키지의 작성 우선은 패키징해 두자 425 cabalize 패키징 작업 425 FizzBuzz 라이브러리 426 Column Hackage에 공개하자 조직 내 개발 패키지의 취급 이런저런 궁리 436 Cabal을 통한 이용 가장 단순한 방법 436 Cabal sandbox를 통한 이용 패키지 데이터베이스를 공유하지 않는 방법 438 조직 내 Hackage 서버의 이용 439 패키지를 나누지 않는다 이용할 패키지의 선정 의존 관계 지옥, 선정의 지침 440 의존 관계 지옥 441 Haskell 관련 패키지 선정 시 고려해야 할 성질 443 Column 버전 상한 을 설정하는 이점 445 Column Cabal sandbox의 명암 - 패키지 레벨에서의 쉬운 조합 의존 패키지의 버전 컨트롤 패키지별로 어떤 버전을 선택할 것인가? 448 버전의 선정 및 고정에 대해서 448 각 OS의 패키지 시스템에 준비되어 있는 것 사용하기 448 Cabal로 롤링 업데이트 정책을 정하여 즉시 업데이트해 나가기 450 xiv 하스켈로 배우는 함수형 프로그래밍

15 7.6 버전 간의 차이 흡수 버전 간 변경점을 검출하는 것부터 453 복수 개발 환경의 공존 453 인터페이스가 안정되지 않은 패키지의 취급법 정리 459 APPENDIX 부록 _ 461 A.1 함수형 언어를 사용하는 프로그래밍 콘테스트 사이트 게임 감각으로 도전 462 [입문] 프로그래밍 콘테스트 462 Anarchy Golf 464 AtCoder 465 CodeChef 466 Codeforces 467 SPOJ 468 A.2 읽어 둘 만한 참고문헌 더 깊은 세계로 469 함수형 프로그래밍에 대해서 469 Haskell에 대해서 471 타입 시스템에 대해서 473 찾아보기 차 례 xv

16 옮긴이 머리말 새로운 프로그래밍 언어를 배운다는 것은 저자의 표현처럼 새로운 도구를 자신의 도구함에 넣는 것처럼 무언가를 새로 얻은 뿌듯함을 느끼게 한다. 하지만 이 책은 다 른 프로그래밍 언어와는 달리 묘한 매력(?)이 있다. 대부분의 프로그래밍 언어 학습서들은 해당 언어의 역사와 Hello World 라는 문 장을 출력하는 기본적인 프로그램 소스로 책을 시작한다. 역자 또한 이 책을 접할 때 그럴 것이라 예상하였다. 하지만 저자도 머리말에서 언급하고 있듯이, 이 책은 처음 부터 다소 난도가 높은 언어 구조와 다른 명령형 언어와의 비교로 시작하고 있다. 앞 부분이 프로그래밍 언어의 이론적인 부분에 치중하고 있어서 일일이 이해하고 나가 는 데 다소 시간이 걸릴지는 모르겠다. 하지만 여러분이 이를 이해한다면 오히려 함 수형 언어의 장단점을 명확히 알 수 있게 될 것이다. 이 책은 특히 수학적인 개념의 함수를 다른 프로그래밍 언어와는 다르게 절차적인 부분과 나누어 명확히 구분하고 있다. 이러한 점은 더 안전한 부품화와 디버깅 작업의 최소화를 극대화한다는 점에 서 매력적이다. 이 책은 객체지향 프로그래밍이나 구조적 프로그래밍을 이미 기본적으로 이해하고 있는 프로그래머들이 함수형 프로그래밍을 제대로 이해할 수 있도록 기존 프로그래 밍 방법론과 비교 분석하여 함수형 프로그래밍 사고방식을 지니게 해 준다. 따라서 이 책은 초급 프로그래머보다는 다른 언어를 이미 꽤 다뤄 본 경력 있는 프로그래머 와 함수형 언어를 공부하려는 학생들에게 체계적인 이론과 실제 도입을 위한 응용력 을 기를 수 있도록 도움을 줄 것이다. 부디 이 책으로 많은 분이 함수형 프로그래밍에 대해 깊이 있고 폭넓은 이해를 얻 기 바란다. xvi 하스켈로 배우는 함수형 프로그래밍

17 감사의 글 또 한 권의 책을 번역하게 해 주신 하나님께 감사드린다. 그리고 책의 출간에 관여하신 모든 분께 감사의 마음을 전한다. 특히, 이 책의 교 정과 편집, 여러 지원을 아낌없이 해 주신 장성두 실장님과 배규호 님의 수고에 감사 의 말씀을 드린다. 끝으로, 사랑하는 나의 아내와 하은, 시온에게도 이 책의 출간에 앞서 기쁨을 함께 나누고 싶다. 이제 여름 휴가철이다! 시원한 해변이나 계곡으로 힐링을 위한 여행을 떠나고 싶다! 일본 동경에서 역자 정인식 옮긴이 머리말 xvii

18 머리말 함수형 프로그래밍 은 함수형 언어 프로그래머뿐만 아니라 대부분의 프로그래머 도 많이 사용한다. 주요 명령형 언어의 최신 버전에서도 함수형 프로그래밍의 에센스를 도입한 기능 들이 존재한다. 즉, 함수형 언어를 사용하지 않는 사람이라 할지라도 사용하는 언어 의 새로운 기능을 잘 도입해서 개발을 계속하려면 함수형 프로그래밍을 배울 필요가 있다. 함수형 프로그래밍은 그 이름대로 함수 를 기본 단위로 구성한 함수의 조합으로 프로그램을 구성한다. 함수형 프로그래밍이라는 스타일 자체는 아마도 실용적인 언 어라면 어떤 언어로도 구현 가능할 것이다. 하지만 아무래도 함수형 프로그래밍을 위해 만들어진 함수형 언어가 함수형 프로그래밍에 제격일 것이다. 주변에서 들어본 적이 있을지도 모르겠지만, 함수형 프로그래밍에는 다양한 소문 이 존재한다. 간결한 코드로 작성할 수 있다 버그가 발생하기 어려워서 안전하다 병렬화하기 쉽다 아니 땐 굴뚝에 연기가 날 리 없겠지만, 이러한 소문들이 생겨나는 데에는 그 나름 의 이유가 존재한다. 특히, 이 책이 집필된 2014년에는 널리 사용되는 오픈 소스 소프트웨어의 심각한 취약점이 연달아 발견되었다. 혹시 여러분 중에도 이에 대응하느라 분주했던 경험이 있을지도 모르겠다. xviii 하스켈로 배우는 함수형 프로그래밍

19 물론, if 문으로도 전혀 할 수 없는 것은 아니지만, 복잡한 사양(specification)임에 도 코드를 간결하게 유지하기 쉬운 언어, 아니면 프로그래머의 사소한 실수도 민감 하게 잘 감지해 내는 안전한 언어가 사용되었다면, 아마 몇 개의 취약점은 막아 낼 수 있었을지 모른다. 만약 위와 같은 특성의 소문이 진실이라면, 함수형 프로그래밍 은 전 세계 사람들이 취약점에 대응하느라 낭비한 시간을 절약할 수 있었을 것이다. 이 책은 함수형 프로그래밍과 함수형 언어란 도대체 어떤 것인지를 명확하게 알려 준다. 그리고 이 책 속에서는 앞에서 언급한 바와 같은 소문이 생기게 된 이유를 설 명한다. 최종적으로, 여러분의 도구함 속에 함수형 프로그래밍의 기초라는 도구를 하나 더 추가해 준다. 이 도구는 실제로 함수형 언어를 사용하는 경우뿐만 아니라, 여러분이 일반적으로 사용하는 언어에 이르기까지 다양하게 활용 가능한 도구가 될 것임이 틀림없다. 함수형 프로그래밍이나 함수형 언어에 관한 서적은 이미 서점에 몇 권 나와 있다. 이 책에서는 함수형 언어의 설명에 Haskell(하스켈)을 사용한다. 그리고 함수형 프로 그래밍의 기초 외에도 다음의 두 가지에 주력해서 설명한다. 함수형 언어에서의 설계 방법/사고 방법 다른 언어와 함수형 언어의 비교 대조 이 책의 대상 독자는 지금까지 다른 언어를 나름대로 사용해 보았으며 앞으로 함 수형 프로그래밍/함수형 언어에도 흥미가 있는 프로그래머와 학생들이다. 이 책에서는 잘 알려진 언어와 비교하여 함수형 언어가 갖는 장단점이 명확히 드 러나도록 하였다. 단순한 비교만이 아니라 함수형 언어의 특정한 유효 기능을 별개 의 주요 언어에 도입하려고 했을 때 어떻게 하면 좋은지도 설명한다. 참고로, 함수형 프로그래밍에서의 사고 방법 은 잘 알려진 구조적 프로그래밍이나 객체지향 프로그래밍의 사고 방법과는 꽤 다르다. 다른 함수형 프로그래밍 관련 서적의 경우, 어떻게 생각해서 작성하면 좋은가 에 대한 설계나 사고 방법의 설명이 머릿속에 확 와 닿지 않았을지도 모르겠다. 작성 방 법을 이해했어도 생각이 뒤따르지 않으면 프로그램을 작성하기 어렵다. 따라서 이 책에서는 함수형 언어를 가지고 함수형 프로그래밍을 할 때 어떤 식으로 생각을 진 머리말 xix

20 행해 나가야 함수형 언어 본연의 간결한 코드가 되는지를 설명한다. 부디 독자 여러분이 이 책을 통해 안전한 프로그램을 만드는 지식을 손에 넣어 함 수형 언어를 가지고, 또는 여러분이 사용할 언어에 이 책의 지식을 도입함으로써 더 나은 미래를 구축하는 데 보탬이 되었으면 한다. 감사의 글 이 책을 집필하는 데 특히 히비노 케이 님과 후지무라 다이스케 님에게 유익한 조 언을 받았다. 마음속 깊이 감사드린다. 또한, Haskell을 이용한 기술 도입, 관련 연구회 개최, 이 책의 집필 등에 대해 너 그럽게 이해해 준 나의 직장 아사히 넷과 그곳의 동료 여러분, 그리고 스킬 향상에 도움되는 연구회를 개최하여 적극적으로 함수형 프로그래밍을 학습하고 있는 프로그 래밍 연구회 회원들, 특히 Haskell과 관련된 많은 분들에게 진심으로 감사의 말씀을 전하고 싶다. 오카와 노리유키 xx 하스켈로 배우는 함수형 프로그래밍

21 이 책의 구성 이 책의 각 장은 다음과 같이 구성되었다. 0장 [입문] 함수형 프로그래밍 함수 의 세계 제0장은 도입부다. 함수형 프로그래밍과 그 실현을 위한 함수형 언어는 도대체 어 떠한 것인지를 설명한다. 이와 더불어 함수형 프로그래밍 분야의 사람들과 대화가 가능한 정도의 기본적인 개념과 특징, 용어, 역사 등을 소개한다. 다양한 함수형 언 어와 해당 언어로 작성된 제품 소개 등도 덧붙인다. 1장 [비교를 통해 발견하기] 함수형 프로그래밍 C/C++, JavaScript, Ruby 그리고 Haskell 1장에서는 동일한 문제 설정하기에서 주요 언어 몇 가지와 Haskell을 비교함으 로써 Haskell(또는 동등한 함수형 언어의 기능)의 기능이 프로그래밍에 미치는 효과를 파악한다. 아직 이 시점에서는 Haskell의 문법을 설명하지 않으나, 비교와 대조로 Haskell 코드를 설명한다. 처음으로 Haskell를 접하는 사람은 일단 1장을 건너뛰고 다음 장인 2장부터 5장까지를 읽은 다음에 되돌아오는 것도 좋다. 2장 타입과 값 타입 은 기본 중의 기본 3장 함수 함수 적용, 함수 합성, 함수 정의, 재귀 함수, 고차 함수 이 책의 구성 xxi

22 4장 평가 전략 지연 평가와 적극 평가 5장 모나드 문맥을 지닌 계산을 다루기 위한 장치 2장에서 5장까지는 Haskell을 비롯한 많은 함수형 언어의 안전성에 크게 공헌한 타입, Haskell 코드를 읽고 쓰기 위한 기본 문법과 Haskell과 다른 언어에서 실제 로 계산이 진행되는 구조적 차이점, 다른 명령형 언어에서 도입되기 시작한 모나드 라는 특징적 기능에 대해 상세히 설명한다. 6장 추천하는 개발/설계 테크닉 함수형/Haskell식 의 프로그램 설계/구현, 사고 6장에서는 Haskell의 추천 설계법에 대해 그 사고 과정을 알 수 있도록 단계별로 설명한다. 무엇이 Haskell식의 코드이며, 어떻게 생각하면 그러한 코드가 작성 가능 한지를 파악할 수 있을 것이다. 이 책을 읽는 독자가 함수형 언어에 대한 경험이 있 다면 5장까지를 건너뛰고 바로 6장부터 읽기 시작하는 것도 좋다. 7장 Haskell에 의한 제품 개발의 길 패키지와의 교제 7장에서는 실제로 Haskell을 사용하여 제품을 만들 때 어떤 코드 베이스나 라이 브러리를 관리해 나가면 좋은지에 대해 다루고 있다. 여러분의 프로그램을 오픈 소 스로 공개하거나 업무에서 Haskell을 사용하거나 할 경우에 도움이 될 것이다. 부록 함수형 언어를 사용할 수 있는 프로그래밍 콘테스트 사이트와 실력 향상을 위해 읽어 두어야 할 참고문헌을 소개한다. xxii 하스켈로 배우는 함수형 프로그래밍

23 이 책에 필요한 사전 지식 이 책에서는 다음과 관련된 사전 지식이 필요하다. 주요 명령형 언어에 대한 경험과 지식 Java, C언어, C++, Ruby, Python, JavaScript 등 Java 8, C++ 11까지 접해 봤다면 더 좋음 구조화 프로그래밍이나 객체지향 프로그래밍의 기본 사항 GoF(Gang of Four)의 디자인 패턴 등 유닉스 계열의 OS나 윈도우즈의 기본 조작 명령 프롬프트에서의 조작 각 언어의 개발, 실행 환경 위의 첫 번째, 두 번째는 비교 및 개념의 대비를 위해 필요하다. 세 번째는 Haskell이나 다른 언어의 샘플 코드를 실제로 테스트해 보기 위해서 필요하다. 이 책에 필요한 사전 지식 xxiii

24 베타리더 후기 김용균(이상한모임) 함수형 프로그래밍의 전반적인 배경과 더불어 Haskell의 문법과 실제 적용까지 짚 어 주는 책입니다. 같은 코드를 명령형 프로그래밍 언어로도 구현/비교하고 있어서 특히 명령형 프로그래밍에 익숙한 사람이 함수형 프로그래밍을 이해하는 데 도움이 될 것 같습니다. 또한, 그 비교를 통해 함수형 프로그래밍이 지닌 장점을 확연하게 파악할 수 있어 좋았습니다. 김종욱(한국기술교육대학교) 이 책에는 함수형 프로그래밍이 무엇인지, 그리고 이를 통해 독자가 얻을 수 있는 것 이 무엇인지가 잘 요약되어 있습니다. 함수형 언어인 Haskell을 이용하여 다양한 예 제를 구현한 것은 이 책만이 가지는 독특한 묘미이며, 또한 예제를 독자 스스로 구현 하며 익히게 하는 방식 역시 함수형 프로그래밍을 처음 접하는 독자에게 큰 도움이 될 것이라 생각됩니다. 김지헌(이노트리) 이 책은 조금 어려웠습니다. 책이 어렵다기보다는 함수형 프로그래밍 이 어렵다는 느낌적(?) 느낌을 받았습니다. 그래도 인내력을 발휘하며 한 장 한 장 읽다가 재귀 함수, 지연 평가, 무한의 데이터 에 들어서면서 나도 몰래 와우! 를 외쳤습니다. 함 수형 프로그래밍에 살짝 맛을 봤으니 천천히 함수형 프로그래밍을 음미하면서 내 것 으로 만들어 갈까 합니다. 처음은 어렵지만 꾸준히 하다 보면 분명 내 것이 될 거라 믿기에. xxiv 하스켈로 배우는 함수형 프로그래밍

25 송영준(줌인터넷) 함수형 패러다임은 프로그래밍 세계에 영향을 끼치고 있습니다. Java와 C++에서 도 그 대세에 따라서 Lambda 표기법을 지원한 지 몇 년이 지났습니다. 과거 스몰토 크가 많은 언어의 객체지향 설계에 영향을 준 것처럼 Haskell도 많은 언어의 함수형 설계에 영향을 줄 것입니다. 이 책에서는 가장 순수한 함수형 언어 중 하나로 평가받 는 Haskell로 여러분을 함수형 프로그래밍의 세계로 인도할 것입니다. 비록 내용은 좀 어렵지만요. :) 장효진(다음카카오) 함수형 프로그래밍이 주목받는 이유에 관한 최신 이야기를 들을 수 있어서 좋았습니 다. 기존의 명령식 프로그래밍에 익숙하지만 본인이 작성하는 프로그램에서 무결함 을 달성하는 데 다소 버거움을 느끼는 독자라면, 저자가 소개하는 세련된 프레임이 신선한 자극이 될 것이라 생각합니다. 차성호 이 책을 읽기 전에 함수형 책을 몇 권 봤습니다만, 대부분 다른 패러다임의 개발자들 위주로 설명되어 있어서 친절하지만 사고방식을 바꾸기가 쉽지는 않았습니다. 이 책 은 명령식 프로그래밍에 익숙한 개발자들이 이해하기 쉽도록 비교를 위한 예제 코드 를 보여 주고, 함수형 프로그래밍을 개념부터 시작해서 수학적 정의를 하듯이 설명 하고 있습니다. 그래서 다른 함수형 언어를 대충은 알고 있지만 익숙하지 않은 저 같 은 사람들이 (그래도 쉽지는 않겠지만) 사고방식을 전환하는 데 도움이 될 것입니다. Beta Readers... 제이펍은 책에 대한 애정과 기술에 대한 열정이 뜨거운 베타리더들로 하여금 출간되는 모든 서적에 사전 검증을 시행하고 있습니다. 베타리더 후기 xxv

26 0Chapter [입문] 함수형 프로그래밍 함수 의 세계

27 함수 의 세계 0.1 함수형 프로그래밍, 그 전에 실용 프로그램에서 활용하는 강점 알기 0.2 함수란 무엇인가? 명령형 언어의 함수와 무엇이 다른가? 0.3 함수형 프로그래밍이란 무엇인가? 프로그램이란 함수다 라는 관점 0.4 함수형 언어란? 함수가 1급(first class) 대상이다? 대입이 없다? 0.5 함수형 언어의 특징적인 기능 타입의 유무, 정적/동적, 강약 0.6 왜 지금 함수형 언어인가? 추상화, 최적화, 병행/병렬화 0.7 함수형 언어와 함수형 프로그래밍의 관계 강력한 성과를 끌어내기 위해서는 어떻게 하면 좋은가? 0.8 함수형 언어의 역사 과거를 알고 미래 탐구하기 0.9 함수형 언어를 채용하는 장점 선언적일 것, 제약의 충족 체크, 타입과 타입 검사, 타입 추론 0.10 이 책에서 다루는 함수형 언어 Haskell의 특징, 구현, 환경 구축 0.11 정리 최근 들어 함수형 프로그래밍 및 함수형 언어 라는 단어가 자주 언급되고 있다. 개발 효율이 좋고 버그가 적다 라는 캐치프레이즈와 함께 함수형 프로그래밍에 관한 기사도 눈에 띄게 많아 졌는가 하면 이미 함수형 언어에 의해 만들어진 제품도 출시되고 있다(자세한 내용은 나중에 설명). 본래 전산학에서 연구 대상이었던 함수형 프로그래밍은 더 이상 일부 연구자들만의 전유물이 아니다. 함수형 언어는 제품 개발을 위해 충분히 실용적인 선택 요소 중 하나가 되었고, 이제는 잘 알려진 명령형 언어들과 함께 어깨를 나란히 하여 우리 앞에 존재한다. 그렇다면 함수형 프로그래밍 이란 실제로 무엇일까? 그리고 함수형 언어 의 함수 란 무엇일 까? 이것은 명령형 언어에서 말하는 함수와 같은 것일까? 이와 다른 어떤 차이가 있을까? 정말 로 개발 효율이 좋아지거나 버그가 적어질 수 있다면, 그 근거는 도대체 어디에 있는 것일까? 이 장에서는 함수형 프로그래밍의 세계를 조망해 보기 위해, 우선 함수형 프로그래밍 및 함수형 언어의 특징을 명확히 하고자 한다.

28 0.1 함수형 프로그래밍, 그 전에 실용 프로그램에서 활용하는 강점 알기 함수형 프로그래밍이나 함수형 언어를 배우는 데 있어서 우선 동기를 명확히 하 자. 실리를 이길 수 있는 명분이란 좀처럼 없을 테니 말이다. 함수형 프로그래밍을 통해 얻을 수 있는 개선 먼저 함수형 프로그래밍과 함수형 언어를 배워 사용하면 어떤 일이 가능할까? 그 개요를 알아보도록 하자. 코드양이 적어진다 어느 정도의 기능을 갖춘 프로그램을 일반적인 수준으로 작성해 보면, 훨씬 적은 코 드양으로 끝마칠 수 있다는 점에 놀라게 될 것이다. 이것은 함수형 프로그래밍의 경 우, 고도로 유용한 추상화 능력을 가진 것으로 알려진 수학 이라는 분야의 개념을 그대로 프로그래밍에 적용할 수 있기 때문이다. 코드양이 적다는 것은 무엇보다 높 은 유지 보수성에 직접적인 영향을 미친다. 최적화하기 쉽다 최적화는 이미 많은 프로그래머들의 노력을 통해 얻어지는 일이 아니라 컴파일러 (compiler)가 자동으로 해 주는 일이다. 따라서 처리계가 최적화를 위해 사용할 수 있 는 유용한 특징을 많이 갖추고 있을수록 프로그램에서 효율을 신경 쓰지 않아도 고 효율의 프로그램이 자동으로 생성될 수 있다. 여기에서도 함수형 프로그래밍의 고급 추상화 능력이 도움이 된다. 병행/병렬화하기 쉽다 CPU의 진화의 경우, 과거에는 단순히 동작 주파수가 빨라지는 식이었지만, 현재는 코어가 늘어나는 방향으로 가고 있다. 즉 어떤 프로그램이라도 CPU가 새롭게 바뀌 면 왠지 모르게 빠르게 처리되던 과거와는 달리, 병행/병렬화된 프로그램이 아니라 면 CPU를 새롭게 바꾸어도 빨라지지 않는다. 제대로 병행/병렬화된 프로그램이라면 (향후 언급) 프로그램의 변경 없이 코어를 충분히 다 사용하게 될 것이다. 4 Chapter 0 [입문] 함수형 프로그래밍

29 버그가 발생하기 어렵다 일부 함수형 언어에서는 꽤 고도의 제약 조건을 타입(type) 으로 표현하여 그 제약 조건이 지켜지고 있는지를 컴파일 시에 체크할 수 있도록 하였다. 자신이 작성한 라 이브러리를 다른 사람이 사용할 경우, 또는 몇 년 전 자신이 작성한 프로그램을 유지 보수할 경우 등에 잘못된 사용법이 발생하지 않도록 미연에 방지할 수 있다. 문서가 적어진다 고도의 제약 조건이 지켜지는지 컴파일 시에 검사할 수 있다는 것은 그 제약 조건 에 대해 문서화가 필요 없다는 의미를 내포한다. 지켜야 할 제약 조건을 일부러 문 서에 설명할 정도라면 그 시간에 제약 조건을 표현하기 위한 프로그래밍을 하는 편이 더 좋다. 문서로 다시 사용자에게 타입 정보를 알려 주는 것보다 검사를 통해 금지시키는 것이 좋기 때문이다. 일단 실용 프로그램에 종사하는 사람 중에서 위와 같은 항목에 흥미 없는 사람은 없을 것이다. 이후에서는 함수형 프로그래밍과 함수형 언어를 시작하면서 위와 같은 항목에 대해서 적절히 다루어 보겠다. 0.2 함수란 무엇인가? 명령형 언어의 함수와 무엇이 다른가? 함수형 프로그래밍이나 함수형 언어에서 가장 특징적인 것은 함수(function) 다. 우선은 이것들이 취급하는 함수란 도대체 어떠한 것인지에 대해서 살펴보도록 하자. 0.2 함수란 무엇인가? 5

30 함수형 프로그래밍에서 함수 함수형 프로그래밍에서 함수 란 무엇일까? 명령형 언어 주1 에서 함수는 특정 명령/ 절차의 나열에 붙은 라벨 주2 에 지나지 않는다. 이에 반해 함수형 프로그래밍에서 함 수는 주어진 입력 값만으로 단지 하나의 출력되는 값을 결정하는 규칙 이라는 수학 적 의미의 함수다. 주3 예를 들어, 다음의 say.cpp의 say는 함수형 프로그래밍의 함수가 아니다. // C++ // say.cpp // 문자열을 표준 출력으로 표시한다 void say(const std::string& something) { std::cout << something << std::endl; // 외부로 입출력을 실시한다 } 위의 코드에서 say는 외부(표준입출력)로 문자 출력을 한다. 외부로의 입출력은 당 연히 외부의 상황에 의존하므로 항상 같은 결과가 나온다고 단정할 수 없다. 또 하나의 예를 보자. # Ruby # current.rb # 현재 시각을 취득한다 def current Time.now # 주어진 입력값 이외에서 출력이 결정되고 있다 end 주1 컴퓨터가 실행해야 할 명령문의 나열에 의한 프로그램을 기술하는 언어다. 절차형 언어라고도 부른 다. C언어나 Java, Perl이나 Ruby, Python 등 현재 주류인 언어는 거의 명령형 언어다. 주2 덧붙이자면, 여기서의 라벨이란 어셈블러에서 이야기하는 라벨 을 뜻한다. 즉, 여기서는 단순히 명령열 의 선두, 또는 명령열의 블록을 식별하기 위한 이름 이라고 생각해도 좋다. 주3 함수형 프로그래밍 및 함수형 언어와 수학과의 관계는 나중에 다시 이야기하겠다(0.6절의 함수형 언어의 추상화 ). 6 Chapter 0 [입문] 함수형 프로그래밍

31 위의 소스에서 current는 외부에서 현재 시각을 가져온다. current에는 아무것도 인수를 부여하지 않으므로, 주어진 입력값만으로 단 하나의 출력값이 결정되는 수학 적 의미의 함수라면 항상 같은 값이 되어야만 한다. 하지만 실제로 current는 때에 따라 결과가 매번 다르다. 다음의 show.cpp의 show는 함수형 프로그래밍의 함수라고 말해도 상관없을 것이다. // C++ // show.cpp // 정수 값 n을 문자열로 변환한다 // show(1234) => 1234 std::string show(const int n) { std::ostringstream oss; oss << n; return oss.str(); } 위의 코드에 있어서 show는 주어진 숫자에 대해서만 그 값의 문자열 표현을 얻는 다. show는 동일 숫자를 부여하면 언제 어디서나 동일한 문자열 표현을 얻을 수 있 다. show는 수학적인 의미에서 함수다. # Ruby total.rb # numbers 내부 값을 전부 더한다 # total([1,2,3]) => 6 def total(numbers) numbers.inject(:+) end 위의 코드에서 total은 주어진 숫자의 열만을 통해 그 합계를 얻는다. total은 언제 어디서 사용해도 동일 숫자의 열을 부여하면 동일한 합계를 얻을 수 있다. total은 수 학적인 의미에서 함수다. 이후 이 책에서는 단순히 함수 라고만 적혀 있을 경우, 수학적인 의미에서 함수를 0.2 함수란 무엇인가? 7

32 의미하는 것으로 간주하겠다. 이에 반해 함수가 아닌 것, 예를 들어 명령형 언어에서 의 (이른바)함수 는 이 책의 경우, 절차 라고 부르겠다. 부작용 프로그래밍에서 상태 를 참조하거나 상태 에 변화를 줌으로써 다음 번 이후의 결 과에까지 영향을 미치는 효과를 부작용(side effect)이라고 한다. 예를 들어, 대입은 부작용이다. 주4 변화하는 변수의 내용의 경우, 그 시점에서 어떠 한 값을 갖고 있느냐는 하나의 상태 로 표현될 수 있다. 그리고 이것은 다음 참조 시 에 이전과 다른 상태 의 결과를 얻을 수 있을지도 모른다. 예를 들어, 입출력은 언어의 외부 세계 주5 의 상태 에 간섭하므로 부작용이 된다. 파일 쓰기 처리는 물론이며, 파일의 내용을 읽어 오는 처리라고 할지라도 물리 디스 크로부터 읽기 처리를 하는 물리적인 동작 주6 을 발생시킬 수 있다. 그리고 그 동작에 의해 물리 디스크 자신이 파손될지도 모른다. 그렇게 되면, 그 후 동일한 읽기 처리 를 한다 해도 동일한 결과를 얻지 못한다. 주7 부작용을 지닌 절차는 앞서 언급한 함수 가 아니다. 함수형 프로그래밍에 대해 배 운 이상, 프로그래밍이 대상으로 하는 처리 내용에 대해 그림 0.1과 같은 부작용을 구별하여 생각하는 것이 중요하다. 주4 특히, 전역 변수의 참조/변경은 가장 성가신 부작용이다. 주5 즉, 처리의 세계가 아닌 우리가 사는 현실 세계. 주6 자기 헤드 구동이나 플래터(platter)의 회전. 주7 그전에 I/O 오류가 발생할 것이다. 8 Chapter 0 [입문] 함수형 프로그래밍

33 프로그래밍이 대상으로 하는 처리 내용 부작용이 없는 것 부작용이 있는 것 (수학적인 의미에서의 함수) 입출력 상태 조작 (대입 등) 그림 0.1 프로그래밍이 대상으로 하는 처리 0.3 함수형 프로그래밍이란 무엇인가? 프로그램이란 함수다 라는 관점 함수형 프로그래밍(functional programming)이란, 값을 가지고 앞 절에서 설명한 함수를 적용해 계산을 진행하는 프로그래밍 스타일이다. 프로그래밍의 패러다임 프로그래밍에서 프로그래밍 패러다임(programming paradiam)이란, 프로그램이 나 그것에 대상이 되는 문제 자체를 어떤 식으로 볼 것인가 라는 것이다. 주8 대개 한 개의 언어는 한 개의 패러다임을 갖는다. 주9 프로그래밍에 국한하지 않고 사물을 다른 관점에서 파악한다는 것은 어려운 일이 주8 망치를 갖고 있는 사람에게 모든 것은 못으로 보인다 라는 의미에 가깝다. 주9 복수의 패러다임으로 프로그래밍할 수 있는 언어를 멀티 패러다임이라고 부른다. 0.3 함수형 프로그래밍이란 무엇인가? 9

34 다. 함수형 프로그래밍이 어렵다는 인상을 주는 이유는 많은 프로그래머가 초창기에 배운 언어의 프로그래밍 패러다임과 함수형 프로그래밍 패러다임이 다르기 때문이 다. 주10 그럼 명령형 및 객체지향의 패러다임을 확인한 후에 함수형 프로그래밍의 패러다 임이란 어떠한 것인지 살펴보자. 명령형 프로그래밍의 패러다임 명령형 프로그래밍의 경우 프로그램은 컴퓨터가 수행해야 할 명령의 나열 이다. 프로그래밍은 명령을 적절한 순서로 나열하는 것으로서 나열한 명령을 순서대로 실 행함에 따라 문제를 해결하는 기능을 실현한다. 객체지향 프로그래밍의 패러다임 객체지향 프로그래밍의 경우 프로그램은 객체와 그것들과의 메시징 이다. 프로그 래밍은 문제에 어떤 객체가 있는지를 찾아내고 정의하는 것이며, 객체를 생성/관리 하여 객체끼리 메시지를 교환함으로써 문제를 해결하는 기능을 실현한다. 함수형 프로그래밍의 패러다임 프로그램은 함수 다 한편, 함수형 프로그래밍에서는 프로그램은 함수 다 라고 생각한다. 그리고 커다 란 프로그램은 작은 프로그램의 조합으로 구성된다. 큰 프로그램은 큰 함수, 작은 프 로그램은 작은 함수라고 했을 때, 프로그램의 조합은 함수 합성(function compostion) 이 된다. 여기서 말하는 함수 합성도 수학에서의 함수 합성과 동일한 것으로, 어떤 함수 f와 함수 g가 있을 때 h(x)=f(g(x))라는 결과를 산출해 내는 새로운 함수 h를 만드는 것을 말한다. 함수 h가 함수 f와 함수 g를 합성한 것일 때, h를 f g라고 쓰고, (f g)(x)=f(g(x)) 로 표현할 수 있다. 이렇게 조립된 함수를 적용함으로써 문제를 해결하는 기능을 실 주10 바꿔 말하면, 그 정도의 이유밖에 없다고 할 수 있다. 10 Chapter 0 [입문] 함수형 프로그래밍

35 현한다. 프로그램이 작은 부품의 조합으로 구성된다 라는 것은 특정 언어를 사용하고 있 는 프로그래머일지라도 동일하게 인식할 것이다. 이때, 조합의 용이성/부품으로서의 독립성을 모듈화(modularity)라고 부른다. 함수형 프로그래밍은 함수와 함수 합성이 가지는 특성에 따라 모듈화의 성능 향상을 보장한다. 함수가 갖는 모듈화 프로그램을 구성하는 부품 의 독립성 함수형 프로그래밍에서 함수는 앞에서 언급한 바와 같이 입력만으로 출력이 결정 되어 그 외의 요인에 의존하지 않는, 즉 부작용이 없으므로 프로그램을 구성하는 부 품 으로서 독립성이 양호하다. 함수에 입력 가능한 값 전체로 이루어진 집합을 정의역(domain), 출력 가능한 값 전 체로 이루어진 집합을 치역(codomain)이라고 한다. 예를 들어, 문자열의 길이를 구하 는 함수라면 정의역은 문자열 전체, 치역은 자연수 주11 전체다. x값이 함수 f의 정의역에 포함되어 있으면 x에 f를 적용할 수 있으며, 함수 f의 치 역이 함수 g의 정의역에 들어가 있으면 함수 f와 g는 문제없이 합성할 수 있다. 함수형 프로그래밍에서 함수에 해당하지 않는 것은 일반적으로 모듈화에 좋지 않 다. 예를 들어, 치역과 정의역이 일치하는 함수 f와 g가 있다고 하자. 즉, f(g(x))이든 g(f(x))이든 호출 자체에는 문제가 없다. 단, f는 내부에서 특정 리소스의 초기화를 실 시하며 g는 내부에서 f와 같은 리소스를 초기화된 것으로 가정하여 이용하려고 한다. 즉, 함수인 것처럼 f와 g를 사용하지만, 이것들이 실은 절차였다는 사실이다. 이 때, f를 적용한 후 g를 적용하는 조합이 가능하지만, g를 적용한 후 f를 적용하는 식 의 조합은 할 수 없다. 따라서 치역과 정의역으로만 함수를 부품으로 결합할 수 없기 주11 0을 포함한다. 0.3 함수형 프로그래밍이란 무엇인가? 11

36 에 f와 g 사이에는 문맥 주12 이 존재한다. 이번 절의 서두에서 언급한 바와 같이 함수형 프로그래밍에서는 절차가 아닌 함수 를 처리한다. 따라서 수학적인 의미에서 함수만 사용하기=절차를 취급하지 않기 라 는 제약이 있게 된다. 0.4 함수형 언어란? 함수가 1급(first class) 대상이다? 대입이 없다? 계속해서 함수형 프로그래밍을 실현하는 함수형 언어(functional language)란 어 떠한 것인가에 대해 살펴보도록 하자. 함수형 언어이기 위한 조건 일반적으로 함수형 언어란 함수가 1급(first class) 대상인 언어를 말한다. 1급 대상이 다 라는 것은 해당 언어에서 단순한 값, 즉 아래와 같은 특징이 있다는 것이다. 리터럴(literal)이 있다. 실행시간에 생성할 수 있다. 변수에 넣어서 취급할 수 있다. 절차나 함수에 인수로서 제공할 수 있다. 절차나 함수의 결과로서 반환할 수 있다. 함수가 1급의 대상이라는 의미는 별다른 것 주13 을 하는 것이 아니라 함수를 값과 주12 여기에서는 정의역과 치역만이 아닌 배후에 숨겨진 무언가를 문맥 이라고 부른다. 함수형 언어에는 문 맥을 프로그래밍할 수 있는 것도 있는데, 예를 들어 F#의 경우, 컴퓨테이션식(compuation expression), Haskell이라면 모나드(monad) 로 취급한다. 모나드는 제5장에서 다루겠다. 주13 함수 포인터를 취급하거나 함수 객체를 만들거나 하는 것. 12 Chapter 0 [입문] 함수형 프로그래밍

37 동일하게 취급하는 기능을 갖는 것 을 말한다. 즉, 함수와 값에 구분이 거의 없다. 함수가 1급 대상이라는 것이 어떤 것인지 앞 절의 항목에 대해 각각 설명하겠다. 함수 리터럴이 있다 문자열이나 값에 리터럴이 있듯이 함수형 언어에서는 함수에도 리터럴이 주어진 다. 자주 나타나는 것이 람다식(λ식, 나중에 설명)에 의한 것이다. 언어에 따라 람다식 의 기법은 다르므로 여기서는 이해를 위해 조금 설명하겠다. 예를 들어, 인수에 1을 더하는 함수는 람다식 (λ x. x + 1)으로 나타내는 식이다. 2를 이 함수에 적용하면 (λ x. x + 1)(2)로 2+1이 된다. 함수를 실행시간에 생성할 수 있다 함수형 언어에서는 함수를 실행시간에 생성할 수 있는데 그 방법이 다양하다. 함 수 합성에 의해 만들어질 수도 있고, 부분 적용(뒤에 설명)이나 고차 함수(뒤에 설명)에 의해 만들어질 수도 있다. 람다식에 의해서도 만들어질 수 있다. 함수를 절차나 함수에 인수로서 제공할 수 있다 정의역이 특정 함수의 집합이 되는 함수를 만들 수 있다. 예를 들면, 함수를 인수 로 취하고 그 함수에 1을 적용한 결과가 되는 함수를 만들 수 있다. (λ f. f(1))와 같 은 식으로 할 수 있다. 함수를 절차나 함수의 결과로서 반환할 수 있다 치역이 특정 함수의 집합이 되는 함수를 만들 수 있다. 예를 들어, 값을 하나 가져 다가 그 값을 더하는 함수가 되도록 함수를 만들 수 있다. 람다식으로 표현하면 (λ a. (λ b. a + b))와 같은 식이다. 실제로, 1에 이 함수를 적용하면 (λ a. (λ b. b + a))(1) 이 (λ b. b + 1)이라는 결과가 된다. 즉, 1을 더하는 함수다. 하지만 최근에는 기존의 명령형 언어에서도 함수형 언어의 특징을 도입하려는 언 어도 존재하므로 이 요구 사항만을 가지고서 함수형 언어의 특징이라고 하는 것은 0.4 함수형 언어란? 13

38 어렵다. 예를 들어, JavaScript 등은 이전부터 함수가 1급의 대상으로 되어 있으며, Java 나 C++도 각각 Java8과 C++11에서 람다식을 도입하는 등 점차 함수형 언어의 기 능을 도입하려는 부분이 있는 것 같다. 물론 함수형 언어의 특징을 가져온 언어로도 함수형 프로그래밍을 할 수 있다. 그 러나 이는 활용하기 쉬운 것 그리고 유용한 것과는 별개의 문제 주14 라고 생각한다. 함수형 언어와 명령형 언어 프로그래밍에 있어서 처음부터 함수형 언어를 시작한 사람은 비율상 그리 많지 않 을 것이다. 많은 사람들이 명령형 언어를 먼저 접할 것이라고 생각하는데, 함수형 언 어와 명령형 언어 사이에는 큰 차이가 있다. 명령형 언어에서는 결과를 달성하기 위해 CPU 또는 처리계의 저수준의 동작을 주 된 부분으로 작성할 필요가 있다. 구체적으로 말하자면 다음과 같다. 값을 어디에 보관할 것인가(대입). 어디로부터 값을 가져올 것인가(참조). 다음에 어떤 절차로 진행할 것인가(절차의 호출). 함수형 언어에서는 특정 결과를 달성하기 위해 그 결과의 성질만을 선언한다. 그 리고 그 성질의 충족 자체는 처리계 주15 에 달려 있다. 선언적이다 라는 것은 출력의 성질이 어떤 것인가에 주목하고 그것만을 기술하는 것이다. 예를 들어, 정렬을 처리함에 있어서 배열의 첫 번째 요소와 그 다음 요소를 비교하여 다음의 요소가 작으면 교체, 그러고 나서 그 후의 처리(이하 생략) 와 같은 식으로 작성된다면 선언적이지 않다고 말할 수 있다. 만일 배열의 특정 위치의 요소 는 그 이후의 요소보다도 작아야 한다 라고만 기술한다면 이는 선언적이 된다. 예를 들어, 많은 명령형 언어에서는 메모리 모델을 직접적으로 취급한다. 그 대표 주14 C언어로도 객체지향 프로그래밍을 할 수 있다는 점과 동일하다고 말해도 과언이 아닐 것이다. 주15 컴파일러, 인터프리터(interpreter), 런타임(runtime) 등. 14 Chapter 0 [입문] 함수형 프로그래밍

39 적인 동작의 하나로서 변수에 값 대입 이 있다. 이것은 그림 0.2와 같이 저장 매체를 다루는 언어가 충분히 추상화해 주지 않아서 메모리에 대한 매우 저수준의 조작이 대입이라는 언어의 기본 조작으로 프로그래머에게 보이는 것이다. 처리 절차를 기술 한다는 이유로 값을(메모리 또는 레지스터 등의) 어디에 둘 것인지를 강하게 의식시키 거나 또는 그것을 서술하도록 요구하는 것이다. 명령형 언어를 배울 때는 변수를 값을 집어넣는 상자 의 개념으로 배우는 경우가 많을 것이다. 이 상자에는 값을 넣는 횟수에 특별한 제한이 있는 것은 아니기에 한 번 값을 대입한 변수에 다른 값을 대입하는 파괴적인 대입 조작 이 가능하다. 주16 변 수에 들어 있는 값을 고쳐 쓸 수 있다는 것은 변수에 어떠한 값이 들어 있는지, 또는 집어넣을 것인지 라는 상태를 취급하는 것이다. 즉, 부작용 항목에서도 설명했듯이 대입은 부작용이라고 생각할 수 있다. 이에 반해 함수형 언어에는 변수로의 대입이 없거나 혹은 매우 한정되어 있어 기 본적으로 한번 변수의 값을 정하면 바꿀 수 없는 속박(binding) 밖에 없다. 대입 기 능을 갖고 있는 함수형 언어에서도 대입과 속박은 명확하게 구별하여 처리된다. 변 수에 들어 있는 값은 그 변수가 사용되는 범위에서는 변화하지 않는다. 즉, 대입과 같이 상태를 취급할 필요가 없다. 함수형 언어에 익숙하지 않은 명령형 언어 프로그래머들에게 대입이 없다는 것은 사용하기 어려운 제약처럼 보일 수 있다. 왜냐하면 대입을 한 번밖에 할 수 없다는 것은 모든 변수에 C언어로 말하는 const 등의 상수화를 거쳐 프로그램을 작성하라 는 것과 같은 것이기 때문이다. 주17 주16 변수에 값을 넣는 조작이 대입이라고 할 때, 이때까지 들어 있던 값을 엎어쓰는 것은 적극적 대입 또는 재대입이라고 부르기도 한다. 하지만, 본질적으로 역할이 다르지는 않기에 특별히 구별하지 않는 경우 도 있다. 주17 그러한 프로그래머야말로 함수형 언어에 익숙해진 후에 명령형 언어로 되돌아와 보기를 바란다. 모든 변수에 대해 const 등의 상수화 키워드를 붙이지 않으면 못 배길 것이다. 0.4 함수형 언어란? 15

40 언어 내 LOAD나 STORE 등 변수 대입/참조 값 기록 매체 메모리나 레지스터 언어의 외부 사정이 충분히 은폐되어 있지 않다 그림 0.2 메모리 모델과 대입 대입이 없기에 얻을 수 있는 것 대입이 없기에 속박밖에 없다는 말은 다음과 같을 것이다. 값이 들어 있지 않은 경우 주18 가 없다(=값이 항상 들어 있다). 값이 변해 버리는 일이 없다(=값이 변하지 않는다). 값이 들어 있으므로 NULL 체크와 같은 본질에서 벗어난 처리를 작성할 필요가 없으며, 값이 변하지 않으니까 정말로 주목하고 싶은 처리 전후에서 무엇을 해도 신 경 쓸 필요가 적게 된다. 주19 속박이라는 제약상, 값이 들어 있는 것과 변하지 않는 것은 거의 같은 것이다. 만약 어떤 시점에서 변수가 들어 있지 않은 에 상당하는 특정 상태였다면 그 상태가 변하지 않기 때문에 마지막까지 그 변수에 값이 들어가지 않게 된다. 즉, 그 변수는 처음부터 끝까지 그 범위 내에서 쓸모가 없다. 위에서 언급한 포인트에서 들어가 있 다 와 변하지 않는다 를 나누어 예를 든 것은, 대입과 미초기화가 있는 언어에서 이 주18 Ruby의 nil, Java의 null, 또는 디폴트 값이 없는 미초기화의 변수 값 주19 변수명이 shadowing[보다 좁은 스코프(scope)를 갖는 동일 변수가 있는 것]되어 있지는 않은지 주의할 필요 가 있지만, 대개는 처리계가 경고를 해 준다. 16 Chapter 0 [입문] 함수형 프로그래밍

41 두 가지 성질에는 명확한 차이가 있기 때문에 그것들의 속박만을 개별적으로 비교하 기 위해서다. 특히 대형 프로그램을 여러 사람이 개발할 경우 자신의 코드를 작성하는 것보다 다른 사람의 코드를 읽을 기회가 더 많아진다. 사람의 주의력은 관심 있는 것 외에는 쉽게 놓칠 수 있으므로 언어의 기능으로서 제약을 보장한다는 점은 코드를 리딩하는 단계를 매우 편리하게 한다. 또한 처리계에 있어서도 속박한 변수의 값이 변하지 않는 성질은 매우 유용하며 대입을 허용한 경우보다도 고도의 최적화를 기대할 수 있다. 아주 간단한 예이지만, 대입이 있는 언어에서 아래와 같이 코드에서는 기술되어 있어도 중간에 생략된 부분 의 코드에 따라 x와 y는 동일하지 않을 수도 있다. x = a + b; <중간 생략> y = a + b; 즉, 실제로 생략된 부분에서 a나 b에 파괴적인 대입을 하지 않은 채 프로그래머가 x와 y가 같다는 것을 알고 있다 해도, x와 y가 동일한 것을 이용한 최적화가 필요한 경우에 처리계에서는 중간에 생략된 부분의 분석을 해야 한다. 하지만 속박밖에 없 는 언어라면 a도 b도 한번 속박되면 변하지 않는 것이므로, 프로그래머나 처리계에 있어서 x와 y가 동일하다는 것은 쉽게 알 수 있다. 그림 0.3은 파괴적인 대입의 유무가 코드 리딩(code reading) 시의 시선 이동에 미 치는 차이를 간단한 예제로 표현하고 있다. a == b의 a값을 쫓아가 봤을 때, 파괴적 인 대입이 있는 경우, a값이 최종적으로 어떻게 되었는지를 끝까지 쫓아가 봐야만 알 수 있다. a 값이 먼저 대입되고 나서 a == b에서 실제로 사용할 때까지 몇 번이나 그 내용이 변경되었는지 모른다. 그에 반해 파괴적인 대입이 없는 경우는 a가 먼저 속 박된 위치를 찾아보면 그것이 그대로 a의 정의이며, 이후에는 변하지 않는 것이 보 증된다. 0.4 함수형 언어란? 17

42 a = b = a b if (a == b) 파괴적 대입이 있는 경우 a = b = a b if (a == b) 파괴적 대입이 없는 경우 그림 0.3 코드 리딩 시의 시선 이동 Column 다양한 함수형 언어 다양한 함수형 언어를 소개하면 다음과 같다(알파벳순). Agda URL 스웨덴의 찰머스공과대학(Chalmers University of Technology)에서 개발된 함수형 언어. 타 입 중에서도 강력한 의존 타입이라는 구조를 갖고 있어 수학적 정리 및 증명을 할 수 있다. 뒤에서 설명하는 Haskell과 유사한 문법을 가지고 있다. Clean URL 네이메헌 라드바우드 대학(Radboud Universty Nijmegen)에서 개발된 순수 함수형 언어. Miranda라는 함수형 언어를 바탕으로 한 문법을 가지고 있다. 고유형이라는 기능을 통 해 부작용을 취급한다. 개발 환경에는 상용 버전 및 비( 非 )상용 버전이 있다. Clojure URL 리치 히키(Rich Hickey)에 의해 만들어진 JVM(Java VM)에서 작동하는 함수형 언어. LISP 계열 중 하나다. LISP 자체 함수형 언어로 분류되는 경우가 있지만, 최근에는 함수형 언어 를 분류하는 기준의 제약이 다소 느슨해졌다. 이에 대해 Clojure는 보다 더 함수형 언어의 방향으로 기능이 개선되고 있다. Coq URL 프랑스 국립 정보학 자동 제어 연구소(INRIA, Instiut National de Recherche en Infromatique Enautomatique)가 개발한 정리 증명 지원계의 순수 함수형 언어. OCaml의 영향을 받아, OCaml로 구현되어 있다. Agda와 같은 의존 타입의 구조를 갖고 있어, 함수를 작성하고 함 수가 만족해야 할 성질을 기술한 후 그 성질에 대해 정리 증명을 할 수 있다. tactic이라는 증명을 위한 강력한 기능을 제공하고 있어, tactic 명령을 나열하여 증명을 진행할 수 있다. 또한 입증된 함수를 다른 언어로 출력할 수도 있다. 18 Chapter 0 [입문] 함수형 프로그래밍

43 Erlang URL 에릭손(Ericsson)사가 만든 함수형 언어. 병행/분산 처리를 강하게 의식한 언어로 설계되 어 있으며, 경량 프로세스라고도 불리는 자체 스레드 간의 메시징 주a 에 의해 주로 처리한 다. 경량 프로세스 자체는 동일하게 위치된 노드와 원격 노드를 의식하지 않고 투명 주b 하게 처리할 수 있다. 핫 스와프(hot swap), 주c 내장애성 주d 등에도 배려가 잘 되어 있다. F# URL 마이크로소프트(Microsoft)가 OCaml을 바탕으로 개발하고 있는.NET Framework에서의 함수형 언어. Visual Studio 2010부터 추가되어 있다. 컴퓨테이션식(compuation expression) 이라는 것으로 부작용을 제어할 수 있다. Haskell URL 함수형 언어의 개방형 표준으로 만들어진 순수 함수형 언어. Clean처럼 Miranda를 바탕 으로 한 문법을 가지고 있다. 모나드(뒤에 설명)라는 구조를 가지고 부작용을 취급한다. Idris URL 세인트앤드루스 대학(University of St. Andrews)의 에드윈 브래디(Edwin Brady)에 의해 개발 된 의존 타입을 지닌 함수형 언어. Haskell과 비슷한 문법과 언어 기능과 Coq가 갖고 있는 tactic을 가지고 있다. OCaml URL INRIA가 개발한 ML 계열의 언어. C언어로 작성한 경우와 손색이 없는 정도의 동작 속도 를 기대할 수 있다. camlp4라는 전처리 프로세서도 강력하여 구문 확장이 가능하다. 주e OCaml은 원래 Caml이라는 ML의 방언에 대해 객체지향적인 기능을 도입한 것이다. 그 러나 신뢰성을 중시하는 OCaml 프로그래머일수록 그에 상응하는 이유가 없는 한 객체지 향적인 부분은 사용하지 않는 것 같다. 객체지향 패러다임을 안전하게 취급하는 것은 본질 적으로 어렵다. 즉, 버그 없이 처리한다는 것은 사람들에게 매우 어려운 일이다. Scala URL 마틴 오더스키(Martin Odersky)에 의해 개발된 JVM에서 동작하는 함수형 언어. 함수형과 객체지향의 통합을 목적 중 하나로 내걸고 있다. Java의 라이브러리를 사용할 수도 있으므 주a 임의의 값을 메시지로 하여 별도의 경량 프로세스 간의 송수신을 할 수 있다. 주b 여기에서는 경량 프로세스가 동작하고 있는 노드가 차이가 있든 없든 간에 동일하게 처리한다는 의미다. 주c 가동 중의 모듈을 정지하지 않고 바꿀 수 있다 주d 오류에 따라 프로그램 전체의 동작이 정지하지 않도록 할 수 있고, 오류 발생 시의 로깅(logging) 이나 프로세스의 재기동을 하기 쉽다는 점을 의미한다. 주e 여기까지 된다면 너무나 강력하다는 견해가 있다. 0.4 함수형 언어란? 19

44 로 Java 프로그램과 연계시키기 쉬워 기존의 Java 프로그램을 부분적으로 Scala로 치환해 나간다는 소리를 듣고 있다. 다른 함수형 언어의 초보자를 위한 스터디 그룹 주f 에 나가 본 결과, Haskell은 처음이지 만 Scala를 사용한 적이 있다 라는 사람들이 꽤 있었다. Standard ML(SML) Standard ML(SML) 주g 은 나름대로 표준화한 ML. SML 계열의 언어로서는 너무 많은 처 리계 구현이 존재하고 있어 각각에 SML의 사양과 호환성을 유지하면서 확장을 실시하고 있다. 주f 고독의 Haskell 이라는 스터디 그룹이 있다. 주g The Definition of Standard ML (Robin Milner/Robert Harper/David Mac Queen/Mads Tofte, MIT Press, 1997) 0.5 함수형 언어의 특징적인 기능 타입의 유무, 정적/동적, 강약 18페이지의 칼럼에서는 다양한 함수형 언어를 소개하였다. 여기에서는 함수형 언 어의 특징적인 기능 이라는 제목으로 typed(타입이 있는)와 untyped(타입이 없는), 정적 타입과 동적 타입, 순수, 타입 검사, 강한 타입과 약한 타입, 타입 추 론, 의존 타입 그리고 평가 전략 을 다루겠다. typed와 untyped 함수형 언어를 분류하는데 타입에 관한 기능이 차지하는 비중은 매우 크다. 먼저 typed(타입이 있는)와 untyped(타입이 없는)로 크게 나눌 수 있다. typed는 기존의 명령형 언어에서도 자주 봐 왔던 것이다. 타입이 맞지 않는다는 20 Chapter 0 [입문] 함수형 프로그래밍

45 것을 특정 타이밍에 감지하고 이에 대해 무언가 오류를 표시한다. 또한, typed는 정적 타입과 동적 타입으로 나뉘는데 이것들에 대해서는 다음 항에 서 설명하겠다. 반대로 untyped는 도대체 무슨 뜻인지 좀처럼 감이 오지 않을 것이다. untyped는 모든 값에 대해 전혀 타입을 구별하지 않음에도 계산이 가능하다는 것 이다. 예를 들어, 덧셈과 덧셈을 덧셈하는 등 그다지 의미를 알 수 없는 계산을 생각해 보자. typed는 일반적으로 숫자와 계산은 구분되어 있기 때문에 오류가 발생한다. untyped는 수와 계산의 구분도 없기 때문에 계산 결과가 만들어진다. 단, 그 결과 로 완성된 것이 도대체 무엇인지에 대해서는 특별히 신경쓰지 않는다. 이것을 잘 이 해할 수 있도록 하는 것은 우리 인간의 일이다. 현재 실용적 단계에 있는 언어는 typed 방식이 거의 대부분이다. typed라는 것은 어떠한 타입 시스템(type system)이 존재하고 있다는 것이다. 타입 시스템은 프로그램 에 타입을 부여함으로써 그 행동을 보장하기 위한 프레임워크(framework)이다. 앞 으로 타입에 관해서 무언가 언급되는 경우, 그것이 타입 시스템의 프레임워크의 일 부라고 이해해서 읽어 주길 바란다. 정적 타입과 동적 타입 typed의 함수형 언어는 크게 정적 타입 언어와 동적 타입 언어가 있다. 타입 검사 를 컴파일 시에 하는 것이 정적 타입(static typing)이고, 정적 타입을 갖는 것이 정적 타 입 언어(statically typed language)다. 그리고 타입 검사를 실행시간에 실시하는 것 이 동적 타입(dynamic typing)으로, 동적 타입을 갖는 언어를 동적 타입 언어(dynamically typed language)라 한다. 주20 주20 명령형 언어에서도 정적 타입 언어와 동적 타입 언어의 구별은 있다. C언어나 Java 등의 경우가 정적 타입 언어이고, Perl이나 Python 등은 동적 타입 언어다. 0.5 함수형 언어의 특징적인 기능 21

46 순수 순수(pure)란, 동일한 식은 언제 평가해도 같은 결과가 되는 참조 투명성(referential transparency)이라는 성질을 갖고 있다는 것이다. 순수하다면 어떤 변수를 참조했을 때의 결과가 항상 동일하다. 또 순수하다면 함 수를 값에 적용했을 때의 결과가 항상 동일하다. 순수한 함수형 언어는 특별히 순수 함수형 언어(purely functional language)라고 한다. 부작용이 없다면 참조 투명성이 된다. 부작용이 있는 식을 작성할 수 있는 언어는 순수하지 않다. 주21 참조 투명성을 지키지 않는 함수로서 다음과 같은 C언어의 함수 foo를 생각해 보자. int foo() { static int n = 0; return ++n; } foo()라는 식은 foo 자체가 호출된 수를 반환한다. 당연히 매번 결과가 다르다. n 이 상태이며 그것의 참조와 값의 변환이 있을 수 있다. 즉, 이것은 부작용이 있다. 참조 투명성을 지키지 않는 변수를 생각해 보자. 생각해 보자고 말은 했지만, C언 어의 변수 값은 대입으로 쉽게 다시 엎어 써 버리므로 변수 단위로 보면 대체로 참조 투명성이 없다. 그러므로 여기에서는 대입을 하지 않고도 값이 바뀌어 버리는 식을 생성하도록 극단적인 상황도 제공해 보았다. 다음과 같은 C언어의 변수 foo를 생각 해 보자. volatile int *foo = 0xDEADBEEF; 주21 즉, 거의 모든 언어는 순수하지 않다. 22 Chapter 0 [입문] 함수형 프로그래밍

47 이 코드는 임베디드 프로그래밍에서 0xDEADBEEF번지에 매핑되어 있는 하드웨 어 신호를 읽어들이기 위한 부분이다. *foo라는 식으로 그 시점에서의 신호 상태를 취득할 수 있는데, 당연히 *foo라는 식은 사용될 때마다 결과가 다를 수 있다. 이는 값을 참조할 때마다 외부와의 입출력을 발생시키기 주22 때문이다. 참조 투명성을 갖는 변수는 간단하다. 다음과 같은 C언어의 변수는 참조 투명성을 갖는다. const int foo = 0; 이 변수 foo를 참조하는 foo라는 식 주23 이 언제나 0이다. 참조 투명성을 갖는 함수는, 즉 수학적인 의미의 함수다. 다음과 같은 C언어의 함 수 foo는 참조 투명성이 있다. int foo() { return 1; } 이 함수 foo를 호출하는 foo()라는 식은 언제나 1이 된다. 타입 검사 타입 검사(type checking)는 프로그램(함수)으로서 타입 주24 에 일관성이 있는지를 컴 파일 시에 검사해 주는 기능이다. 검사에 실패하는 식이 있는 경우 일반적으로 컴파 일 오류로 처리된다. 주22 그리고 그렇게 되는 것에 의미가 있다. 주23 C언어의 경우, 꽤나 지저분(dirty)한 짓을 하지 않는 한 변경은 없다. 주24 타입에 대해서는 뒷장에서 자세히 설명한다. 0.5 함수형 언어의 특징적인 기능 23

48 강한 타입과 약한 타입 언어 사양(language specification)에서 정의되지 않은 동작을 발생시키지 않는 것 을 안전성(safety)이라고 한다. 여기서 말하는 언어 사양에서 정의되지 않은 동작 의 예를 들면, C언어 등에서 전혀 관계없는 메모리 영역에서 잘못된 데이터를 읽어 버 리는 경우 를 말할 수 있다. 해당 프로그램은 분명 바람직하지 않은 상태로 돌입하게 될 것이다. 이 안전성에 대해 타입 검사를 성공했다면 안전성이 보장되는 타입을 강한 타입 (strong typing), 반대로 타입 검사에 성공하더라도 안전성이 보장되지 않는 타입을 약 한 타입(weak typing)이라고 한다. 정적 타입의 명령형 언어는 약한 타입인 경우가 많 다. 주25 타입 언어라면 강한 타입 쪽이 타입 의 고마움을 느낄 수 있을 것이다. 타입의 추론 타입 추론(type inference)은 명시적으로 부여되는 주26 타입의 정보로부터 암시적인 주27 부분의 타입을 추론해 주는 기능이다. 예를 들어, 어떤 비교 가능한 타입의 값의 열을 가지고 그 열에 있는 값 중에서 최 댓값을 반환하는 함수 maximum과 정수 값을 가지고 문자열 표현(문자열)을 반환 하는 함수 show가 있다고 하자. 함수 maximum이 취하는 것은 비교만 된다면 무 슨 열이라도 상관없지만, 함수를 합성하여 maximum show를 취하면 maximum 은 show의 결과인 문자의 열을 취하므로 함수 maximum show는 정수 값을 가 진 문자를 반환하는 함수가 된다. 어떤 비교 가능한 타입 이 문자 로 타입 추론되 었기 때문이다. 주25 동적 타입 언어에서 타입이 맞지 않은 경우, 강한 타입은 타입 오류를 발생시키지만, 약한 타입은 타입 의 변환을 시도하여 어떻게든 동작하려고 한다. 주26 프로그래머가 부여했다는 의미. 주27 프로그래머가 타입의 기술을 생략했다는 의미. 24 Chapter 0 [입문] 함수형 프로그래밍

49 Column 약한 타입은 무엇을 위한 것인가? 이것에 관해서는 필자도 명확한 이유를 파악한 것은 아니어서 확신은 없지만, 약한 정적 타입의 경우, 있다 보다는 아직 남아 있다 라고 생각한다. 예를 들어, 당초의 C언어에서는 타입이 어셈블러 레벨로 변화될 때나 메모리에 값을 저장할 때에 어떤 명령을 지정하는 것이 적절한지, 얼마나 많은 공간을 점유하는 값인지 를 나타내기 위한 주석 정도의 의미밖에 갖질 않았다. 타입에 관한 이론이 발전해 감에 따라 타입의 역할이 다시 검토되고, 기왕 타입을 붙이는 경우라면 강한 타입이 나오게 된 것이다. 컴파일 시에 체크하지 않는 동적 타이핑의 경우, 비록 의도하지 않은 행동을 하고 있다 고 해도 가능한 한 오류로 멈추지 않고 동작하기 위해서 라는 목적으로(일단, 그 좋고 나쁨 은 제외하자) 약한 타입을 필요로 하게 되었다. 단, 일반적으로 컴파일을 통과해야 하는 정적 타입의 경우, 뭔가 강한 의도가 있어 약한 타입 이 존재하는 것은 아니라고 생각한다. 의존 타입 의존 타입(dependent type)은 다른 타입에 의존한 타입이나 값에 의존한 타입을 만 들 수 있는 기능이다. 예를 들어, 타입A와 타입B가 동일할 때에만 그 타입에 값이 존재하는 타입이나, 길이를 타입 수준에서 갖는 리스트 타입과 같은 보다 강한 제약 을 갖는 타입을 만들 수 있다. 평가 전략 평가 전략이란, 프로그래밍 언어에서 어떠한 순서로 식을 평가할까? 라는 규칙을 말한다. 적극 평가(eager evaluation) 또는 지연 평가(lazy evaluation) 등이 있다. 적극 평 가에서는 인수가 전달되기 전에 평가된다. 지연 평가에서는 필요할 때까지 평가하지 않는다. 함수형 언어에 한정되지 않고 현재 대부분의 언어는 적극 평가를 사용한다. 일부 순수 함수형 언어가 지연 평가를 사용하고 있을 뿐이다. 다음의 함수 tarai는 재귀적으로 호출되는 다라이 함수(다케우치 함수) 라고 불리 는 함수다. 0.5 함수형 언어의 특징적인 기능 25

50 int tarai(int x, int y, int z) { return (x <= y)? y : tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)); } 이 함수에서는 x가 y보다 작으면 z값은 볼 필요도 없이 결과가 결정난다. 따라서 적극 평가의 언어로 순수히 구현하면 z의 계산 때문에 느려지고, 지연 평가의 언어로 구현하면 z의 계산이 필요 없다고 판단해 생략되므로 빨라진다는 특징적인 함수로 되어 있다. 물론 어떠한 경우에도 지연 평가가 더 빨라진다는 것은 아니다. 평가 대기의 상태 주28 를 대량으로 생산할 수 있으므로 적극 평가가 빠른 경우가 압도적으로 많을 것이 다. 그럼에도 지연 평가가 존재하는 이유는 지연 평가의 경우가 언어로서는 수학적 으로 자연스럽게 기술하기 쉬운 편이고, 실제로 끝까지 평가해 보면 오류가 되지만, 생략되는 경우라면 오류에 관계없이 계산이 진행된다는 점 등의 유리한 점도 있기 때문이다. 주요 함수형 언어와 명령형 언어의 기능 리스트. 주요 함수형 언어와 명령형 언어에 대해 구비된 기능을 표 0.1에 정리하여 두었 다. 주29 주28 최종적으로 평가되지 않는다고 해도. 주29 표 안에 가 많다고 해서 좋다든가 추천한다는 뜻이 아니다. 툴은 적재적소에 사용되어야 한다. 26 Chapter 0 [입문] 함수형 프로그래밍

51 표 0.1 주요 함수형 언어와 명령형 언어의 기능 언어 type 순수 타입 추론 의존 타입 Agda 강함, 정적 Clean 강함, 정적 X Coq 강함, 정적 F# 강함, 정적 X X Haskell 강함, 정적 Idris 강함, 정적 OCaml 강함, 정적 X Scala 강함, 정적 X X SML 강함, 정적 X X Clojure 강함, 동적 X - - Erlang 강함, 동적 X - - C 약함, 정적 - X - C++(C++11) 약함, 정적 - - Java 강함, 정적 - - JavaScript 약함, 동적 Perl 약함, 동적 Python 강함, 동적 Ruby 강함, 동적 X: 지원 안 함, O: 지원, 세모: 부분 지원 0.5 함수형 언어의 특징적인 기능 27

52 0.6 왜 지금 함수형 언어인가? 추상화, 최적화, 병행/병렬화 지금 함수형 언어를 채용하는 이유에는 여러 가지가 있다. 여기서는 추상화, 최 적화, 병행/병렬화 등 현대적인 프로그래밍에 있어서 개발 효율과 실행 효율에 영 향을 주는 중요한 관점에서 함수형 언어를 사용하는 이유를 살펴보자. 함수형 언어의 추상화 수학적인 추상화란? 프로그래밍에서 추상화(abstraction)는 중요한 기술이다. 모듈의 재사용성을 강화하 고, 구현과 인터페이스를 분리해 두는 적절한 추상화에 의해 프로그램은 유연하게 유지된다. 프로그래머가 갖고 있는 추상화 능력에서 차지하는 비율도 크지만, 언어 기능에 의해 가능한 추상화 또한 무시하지 못하는 것도 사실이다. 함수형 언어에서 추상화할 때 함수형 프로그래머 모두가 명확하게 좋다고 말하는 방향성이 있다. 그것은 그룹 이론과 범주론 주30 이라는 수학적 방향으로의 추상화다. 여기서 좋은 추상화는 무엇인지에 대해 생각해 보자. 필자가 생각하는 추상화의 장점에 대한 평가 기준은 다음과 같다. 많은 문제에 대해 범용적으로 적용할 수 있다. 추상화 후의 세계에서 실시할 수 있는 조작이 풍부하다. 범용적으로 적용할 수 없는 것은 원래부터 추상화한다고 말할 수 없다. 따라서 전 자에 대해서는 당연한 기준일 것이다. 후자에 대해서는 어떨까? 추상화한 후 누군가 위에서 많은 강력한 조작을 할 수 있는가 하는 점은 의외로 고려되지 않았을 것이라 생각한다. 주30 그룹 이론과 범주론은 수학적인 구조를 다루기 위한 분야다. 함수형 언어에서는 수학적인 의미에서 함 수를 취급하므로 수학적인 구조를 취급하는 방법이 그대로 적용되기 쉬운 경향이 있다. 28 Chapter 0 [입문] 함수형 프로그래밍

53 수학은 실로 많은 문제를 처리할 수 있으며 문제를 한번 수학의 세계로 추상화할 수 있다면 컴퓨터의 역사보다 긴 세월에 걸쳐 축적된 풍부하고 강력한 수학의 세계 의 성과를 모두 그대로 적용할 수 있는 상태가 된다. 이것은 앞서 언급한 좋은 추상 화의 평가 기준 두 가지를 충분히 충족하고 있다. 혹시, 수학 실력 때문에 걱정인가? 수학 실력이 별로 좋지 않은 사람이라도 너무 걱정할 필요 없다. 모든 함수형 프로그래머가 수학적인 지식이 없으면 함수형 언어 를 사용할 수 없다는 뜻이 아니다. 주31 수학적으로 명료한 추상화된 프로그램을 작성하고 싶거나 라이브러리를 제공하려 는 경우를 제외하고는 선배들이 준비한 명확히 추상화된 라이브러리를 사용할 수 있 다. 또한 자신이 수학적 의미를 잘 몰라도 특정 인터페이스와 타입의 제약에 따라 작 성하는 것만으로도 마음대로 수학적으로 명료한 추상화를 할 수 있는 경우도 있다. 함수형 언어의 최적화 프로그래밍 언어 및 프로그래머에게 있어서 최적화(optimization) 또한 매우 중요한 요소다. 최적화가 강력할수록 프로그래머는 효율을 신경 쓰지 않고 간결성에만 유의 해서 의미 있는 코드를 작성하면 된다. 최적화가 강력할수록 코드의 표현 이상으로 충분히 효율 좋은 동작을 해 줄 것이기 때문이다. 주32 특히 예전처럼 컴퓨터의 성능이 낮은 시대와는 달리 컴퓨터의 성능이 크게 향상된 요즈음에서는 컴파일러 등의 처리계에 최적화를 맡기는 것이 좋을 만큼, 프로그래머 가 편해질 수 있는 가능성이 높아졌다. 앞서 언급한 바와 같이 함수형 언어에서는 수학적 추상화를 한다. 수학적으로 명 확한 세상을 경유함으로써 최적화도 수학의 성과를 이용하는 것이 가능하다. 주31 필자의 경우도 그다지 수학적 지식이 많지 않다. 주32 예를 들어, 사람의 힘에 의한 최적화의 경우, 캐시에 올라갈 수 있는 데이터 양을 생각한 후에 그 단위 로 데이터를 구분하여 처리하도록 코드를 작성해야 하지만, 그것은 캐시 크기가 바뀌면 함께 변경해야 한다. 이것은 실제 대상으로 하고 있는 문제에 대한 알고리즘의 본질과는 또 다른 이야기다. 사람의 힘 으로 무리하게 최적화함으로써 대상의 문제를 해결하는 것 과 처리를 빨리하는 것 의 두 가지 과제를 동시에 해결하려는 코드를 기술하는 것이므로 전체적으로 이해하기 어려워 유지 보수 또한 어렵다. 0.6 왜 지금 함수형 언어인가? 29

54 그럼, 1에서 n까지의 자연수를 모두 더하는 함수 totalfrom1to를 생각해 보자. 예를 들어, C언어에서는 다음과 같이 될 것이다. // C(C99) int totalfrom1to(int n) { int result = 0; for (int i = 1; i <= n; result += i++); return result; } result에 더해지는 수 i를 1부터 증가시키면서 더해 나가, i가 n이 될 때까지 반복 시키면 된다. 이에 반해 Haskell로 다음과 같이 작성했다고 치자. -- Haskell totalfrom1to = sum. enumfromto 1 이 코드에서는 두 개의 함수, 리스트의 모든 내용을 더하여 전체 합의 값으로 하는 함수 sum과 1부터 n까지의 리스트를 만드는 함수 enumfromto 1을 함수 합성하 고 있다. Haskell 코드의 예와 같이, 일단 중간 리스트를 만들고 나서 생성한 리스트 를 하나 하나 읽어서 처리하는 부분을 작성하면 리스트를 만드는 만큼의 처리가 아 까운 것은 아닌지? 라고 생각할지도 모르겠다. 하지만 이러한 처리는 최적화를 통해, C언어의 코드와 동일하게 중간 리스트를 만들지 않는 처리로 하는 것이 가능하다. 이것은 일종의 구조(이번 예에서는 리스트)를 만드는 함수와 특정 구조(이번 예에서는 리 스트)를 넣어서 처리하는 함수가 합성할 때 중간 구조를 만들지 않는 함수로 변환 가 능하다는 수학의 세계의 성과가 반영되어 있기 때문이다. 만약 이러한 최적화가 없는 경우, C언어의 코드와 같은 처리를 기대한다면 다음과 같이 기술하게 될 것이다. -- Haskell totalfrom1to = auxtotalfrom1to 0 where 30 Chapter 0 [입문] 함수형 프로그래밍

55 auxtotalfrom1to result 0 = result auxtotalfrom1to result n = auxtotalfrom1to (result+n) (n-1) 여기에서는 이 코드에 대한 설명은 하지 않는다. 중요한 것은 이번 예에서 일단 리 스트를 통한 코드의 예가 프로그래머에게 있어 파악하기 좋다는 것이다. 1부터 n 까지의 리스트를 만들고 나서 만든 리스트의 내용을 전부 더한다 라는 코드는, result에 더해지는 수 i를 1부터 증가시키면서 n까지 더하는 코드보다도 부품화되 어 있다. 부품마다 제대로 작동하는지 확인하는 것도 간단할 것이다. 프로그래머에게 있어 파악하기 좋다는 것은 특별히 프로그램을 짧게 작성할 수 있 거나 하는 것이 아니다. 주33 프로그램의 정확성(올바른 결과를 반환하는 것) 이 사람의 눈에도 명확하다는 것을 의미한다. 그러나 명확하게 올바른 코드는 종종 효율 주34 이 좋지 않다. 함수형 언어의 최적화 메커니즘은 언어가 갖는 강한 제약과 수학적 추상 화를 이용하여 올바른 것이 분명하지만, 비효율적인 프로그램으로부터 동일하면서 도 더 효율적인 프로그램으로 변환할 수 있다는 것이다. 그림 0.4는 위의 코드에 대한 최적화가 되지 않은 경우 주35 에 계산해 나가는 과정을 보여 준다. 마찬가지로 그림 0.5는 최적화가 된 경우에 계산해 나가는 과정을 보여 준다. 모두 1부터 5까지의 숫자를 더한 결과를 계산하고 있지만, 최적화가 된 동작에 서는 도중에 리스트를 만드는 작업을 하지 않는 만큼 시간 효율도 공간 효율도 개선 되고 있다. 물론 다른 언어에도 있는 저수준의 최적화 또한 별도로 적용된다. 여기에서 설명 한 최적화는 보다 추상적인 단계에서의 최적화다. 그림 0.6은 언어가 갖는 최적화를 요약하고 있다. 함수형 언어는 추상화의 항목에서도 언급했듯이 수학적 추상화가 좋 다고 판단해서 이용하므로 다른 언어에서도 이루어지는 일반적인 최적화 기법 외에 수학적 추상화를 이용한 최적화 단계를 가질 수 있다. 당연하겠지만, 언어가 갖는 성 주33 그러한 면도 있지만. 주34 시간 효율(실행 속도)이나 공간 효율(메모리 사용량)이 대표적인 효율의 지표다. 주35 즉, 코드에서 이해한 그대로의 동작을 할 것이라고 생각했을 경우. 0.6 왜 지금 함수형 언어인가? 31

56 질이 수학적으로 깨끗할수록 수학적인 최적화를 적용하기 쉽다. 단, 최적화할 수 있는 것이 많다고 해서 반드시 효율이 좋은 것이 생성되는 것은 아니라는 점은 기존의 명령형 언어와 동일하다. 특히 현재의 CPU는 명령형 언어 주36 를 빨리 동작시키는 것에 중점을 두고 있다. 물론 본래 CPU가 있으면 이를 위해 기계어라는 명령형 언어가 존재하고 있으므로 명령형 언어 쪽이 CPU에, 좋게 말하면 좀 더 가까운 위치에, 나쁘게 말하면 추상도 가 낮은 위치에 있으므로 당연하기는 하다. 따라서 단순히 명령형 언어와 비교하면 실행 속도에 있어서 함수형 언어에 불리한 점이 있다는 것 또한 사실이다. 더욱이 최 적화를 포함해도 원하는 성능에 이르지 못했을 경우, 일반적으로 말하는 고급 최적 화 주37 를 걸 정도로 튜닝의 난이도가 올라간다. :는 리스트의 선두에 요소를 붙인다 sum (enumfromto 1 5) => sum (1 : enumfromto 2 5) => sum (1 : 2 : enumfromto 3 5) => sum (1 : 2 : 3 : enemfromto 4 5) => sum (1 : 2 : 3 : 4 : enumfromto 5 5) => sum (1 : 2 : 3 : 4 : 5 : enumfromto 6 5) => sum (1 : 2 : 3 : 4 : 5 : []) => 1 + sum (2 : 3 : 4 : 5 : []) => 1 + (2 + sum (3 : 4 : 5 : [])) => 1 + (2 + (3 + sum (4 : 5 : []))) => 1 + (2 + (3 + (4 + sum (5 : [])))) => 1 + (2 + (3 + (4 + (5 + sum [])))) => 1 + (2 + (3 + (4 + (5 + 0 )))) => 15 리스트를 만들고 있다 []는 공백 리스트 리스트를 없애고 있다 그림 0.4 최적화 없음 주36 꼭 집어 말하자면 C언어. 주37 최적화 메커니즘에 따르지 않고 어찌되었든 간에 사람에게 있어서 분명하지 않은 변환을 시행하는 것들. 32 Chapter 0 [입문] 함수형 프로그래밍

57 리스트를 만들지 않고 sum (enumfromto 1 5) 계산이 진행 가능 => 1 + sum (enumfromto 2 5) => 1 + (2 + sum (enumfromto 3 5)) => 1 + (2 + (3 + sum (enumfromto 4 5))) => 1 + (2 + (3 + (4 + sum (enumfromto 5 5)))) => 1 + (2 + (3 + (4 + (5 + sum(enumfromto 6 5))))) => 1 + (2 + (3 + (4 + (5 + 0)))) => 15 그림 0.5 최적화 있음 함수형 언어 명령형 언어 수학적인 성질을 이용한 최적화 일반적으로 자주 시행되는 최적화 기법 루프, 데이터 플로, SSA 등의 최적화 어셈블러 레벨의 코드 생성 최적화 Static Single Assignment form (정적 단일 대입) 그림 0.6 이용할 수 있는 최적화 메커니즘 그러나 어떤 언어에 있어서도 언어의 수학적 성질이 개선되는 것은 거의 없지만, 다른 한편에서는 연구를 통한 최적화 기법이 진보하고 있다. 다른 언어에서 적용할 수 있는 최적화 기법 주38 이라도 특정 언어에서는 언어 그 자 체의 성질이 그다지 좋지 않아서(순수하지 않은) 적용할 수 없는 최적화 기법이라는 것도 있을 것이다. 추상도가 높고 언어의 성질이 비교적 좋다는 점에서 함수형 언어 는 명령형 언어에 비해 최적화의 성장 가능성이 높다고 말할 수 있다. 주38 예를 들어, 순수한 언어로 참조 투명성을 이용하여 동일한 인수라면 재계산 없이 앞에서 계산한 결과를 부여하거나 하는 최적화. 0.6 왜 지금 함수형 언어인가? 33

58 함수형 언어와 병행/병렬 프로그래밍 여러분이 가지고 있는 CPU는 몇 코어인가? 주39 해마다 CPU의 코어 수는 증가하 고 있으며, HT(Hyper-Threading)를 포함하여 10개 이상의 병렬 처리를 할 수 있는 환경도 이미 상품화되고 있다. 그런데 프로그램 쪽은 어떨까? 대부분의 경우, 동일 프로그램이라고 해도 보다 주파수가 큰 CPU에서 작동시키면 기대되는 처리의 속도 가 빨라질 것이다. 하지만 동일 프로그램이라고 해도 보다 코어가 많은 CPU에서 동 작시키면 그만큼 기대가 될 정도로 속도가 빨라질까? 병행/병렬이라는 개념과 프로그래밍의 어려움 프로그램이 멀티 코어 CPU를 충분히 활용하기 위해서는 적절하게 병행/병렬 프 로그래밍되어 있지 않으면 안 된다. 그러나 병행/병렬 프로그래밍은 일반적으로 쉽 지 않다. 예를 들어, 병렬 실행에 있어서 어떤 특정 처리의 열과 다른 처리의 열이 서 로 어떻게든 잘 혼합하여 실행되었다 하더라도 전체적으로 기대하는 동작으로 나타 나야 하기 때문이다. 서로를 혼합하는 방법의 패턴은 일반적으로 방대하고, 그중 극 소수에서 기대하는 동작을 하지 않는다면 재현성 주40 이 매우 낮은 버그로 다시 표면 화될 수 있다. 일반적으로 그림 0.7과 같이 물리적으로 여러 작업을 동시에 수행할 수 있는 것을 병렬(parallel)이라고 말하고, 그림 0.8과 같이 논리적으로 여러 작업을 동시에 실행할 수 있거나 실행 상태를 여러 개 유지할 수 있는 것을 병행(concurrent)이라고 한다. 병 렬이라면 병행할 수 있다. 예를 들어, 싱글 코어 환경에서 스레드 전환(시분할)으로 여러 작업을 외관상 동시에 수행하는 것처럼 보이는 것은 병행 실행을 말한다. 주39 참고로, 필자의 메인 환경은 6코어(HT/Hyper-Threading으로 12개의 스레드)다(이 책의 원고 집필 시점 2014년 10월). 주40 동일한 조건에서 동일한 것을 한다면 같은 결과를 얻을 수 있는 성질. 34 Chapter 0 [입문] 함수형 프로그래밍

59 코어1 코어2 처리1 처리2 시간 그림 0.7 병렬 코어1 처리1 처리2 시간 스레드의 전환 그림 0.8 병행 목적으로부터 고려하는 병행/병렬 프로그래밍 실제로 대상으로 하는 문제와 그 해결책으로서 프로그래밍에 주목하면, 병행/병렬 프로그래밍이 목적으로 하는 방향성의 차이를 알 수 있다. 병행 프로그래밍을 하는 이유는 여러 태스크를 동시에 수행할 수 있다는 점 때문이다. 이에 반해 병렬 프로그 래밍에서는 명확하게 태스크의 고속화를 목적으로 하고 있다. 병행 프로그래밍에서는 여러 태스크가 같은 모양이어야 한다는 필요와 결과가 결정적 주41 이어야 할 필요가 특 별히 없다. 주목하는 문제에 대해 동시에 실행되면 좋겠다는 조건밖에 없기 때문이다. 예를 들어, 웹 애플리케이션은 병행 프로그래밍되어 있다고 말할 수 있다. 웹 애플 리케이션의 경우, 여러 태스크는 요청에 대한 응답의 생성이며, 요청은 동시에 처리 되지만 응답의 내용은 타이밍에 따라 비결정적 역주 이다. 그림 0.9는 액세스 카운터를 갖는 웹 애플리케이션에 대해 거의 동시에 여러 요청이 발생하는 경우다. 적절히 병 행 프로그래밍되어 있으면 이러한 여러 요청은 병행하게 처리된다. 주41 같은 응답을 얻을 것. 역주 비결정적이란 말은 같은 응답을 얻지 못하는 것을 말한다. 0.6 왜 지금 함수형 언어인가? 35

60 그러나 액세스 카운터 부분은 순서대로 처리될 필요가 있으므로, 실제 어떤 요청 에 대해 먼저 카운트 업을 할지에 따라 각 요청에 대한 응답 내용은 비결정적으로 바 뀐다. 거의 동시 액세스 요청1 요청2 액세스 카운터 응답1 응답2 응답2 응답 결과 결과 그림 0.9 웹 애플리케이션에 의한 요청의 병행 처리 병렬 프로그래밍에서는 원래 (순차로 행해지는) 태스크의 고속화를 목적으로 하므 로 결과가 결정적인 것까지 기대할 경우가 있다. 즉, 싱글 코어에서 실행했을 때와 멀티 코어에서 실행했을 때에 다른 결과가 되기도 하는 것은 실제로 사용하기에는 곤란하다. 예를 들어, 무언가 계산하는 동안에 매우 큰 배열의 내용을 전부 더하는 식의 합계 처리가 있다고 치자. 이 합계 처리를 병렬화하면 그림 0.10과 같이 배열 을 코어 수만큼으로 나누어서 각 코어에서 각각 담당한 만큼을 더한 후에 마지막으 로 각 코어의 결과를 모아서 더하게 된다. 사실은 이 병렬화에서는 덧셈이 결합 법칙 a+(b+c)=(a+b)+c를 만족하지 못하는 값의 배열에 적용한 경우, 결정적이지 않다. IEEE 754 부동 소수점 숫자 등에서는 바로 덧셈이 결합 법칙을 만족하고 있지 않으 므로 분야 주42 에 따라서는 이 병렬 알고리즘에서 문제가 될 수 있다. 주42 작은 오차가 큰 오차를 발생시키고 그것이 치명적인 영향을 끼치는 분야로는 금융이나 항공 우주 과학 분야가 있다. 36 Chapter 0 [입문] 함수형 프로그래밍

61 병행 프로그래밍의 어려움 결합 상태, 데드록 일부 함수형 언어는 경량 스레드와 경량 프로세스라는 매우 낮은 비용의 스레드 메커니즘 주43 과 이를 제어하기 위한 우수한 스레드 컨트롤러와 I/O 매니저를 가지고 있다. 병행 프로그래밍은 일반적으로 멀티 스레드 프로그래밍(multithreaded programming) 에 의해 실현한다. 따라서 병행 프로그래밍의 어려움은 멀티 스레드 프로그래밍의 어려움이다. 멀티 스레드 프로그래밍이 어려워 주로 문제가 되는 경우는 여러 스레드가 동일한 리소스에 거의 동시에 액세스할 때 리소스가 예기치 않은 상태가 되어 버리는 경쟁 상 태(race condition)다. 일반적으로 mutex 잠금 주44 등을 이용하여 리소스에 접근할 때 크리티컬 섹션(critical section: 임계 영역) 내로 국한하는 등 적절하게 경쟁 상태를 일 으키지 않도록 배타적 제어 주45 를 할 필요가 있다. 0,1,2,3,4,5,6,7 분할 0,1, 2,3, 4,5, 6,7 합계 합계 합계 합계 합계 각 부분마다 동시에 계산 28 각 부분의 결과를 합산한다 그림 0.10 병렬 합계 주43 사용자 공간에서 동작하며 문맥(context)이 작아서 스위칭 또한 빠르다는 특징이 있다. 주44 동시에 한 개의 처리밖에 크리티컬 섹션(임계 영역)에 들어가지 못하도록 하기 위한 상호 배타 메커니즘. 잠금(lock)을 취득한 문맥의 처리만이 크리티컬 섹션 내에서 실행할 수 있다. 주45 동시에 이용되는 것을 막기 위한 것. 0.6 왜 지금 함수형 언어인가? 37

62 그러나 기존의 잠금에 의한 리소스 제어는 매우 복잡하고, 병행 프로그래밍의 트러 블의 근원점이 되고 있다. 예를 들어, 다음과 같은 것이 대표적인 트러블일 것이다. 잠금해야 할 리소스인 것을 사양/설계/기존 코드 등으로부터 파악하지 못하고 잠금 해야 하는 것을 잊어버렸다. 잠금한 리소스를 사용한 후, 잠금을 푸는 것을 잊어버렸다. 잠금할 필요가 없거나 아니면 당초 필요가 있었지만 할 필요가 없어진 리소스에 대 해 여전히 잠금을 하고 있어 성능이 올라가지 않는다. 잠금을 취할 범위가 쓸데없이 커서 성능이 올라가지 않는다. 스레드 두 개가 서로 잠금 상태인 리소스를 서로 취하는 바람에 멈춰 버리는 데드록. 그리고 이에 기인하는 대부분의 문제가 재현성이 없는 버그 리포트(bug report)로 올라와 있다. 결과적으로 좀처럼 재현하지 않는 문제를 재현하기 위한 단순한 작업을 오로지 운 에 맡기고 반복하는 데에 프로그래머의 귀중한 시간이 소요된다. 특히 위험한 것은 데드록(deadlock)이다. 데드록은 프로그램이 다음 조건을 만족하 는 것만으로 발생할 수 있다. 잠금해야 할 두 개 이상의 리소스가 있다. 이미 한 개 이상의 리소스를 잠금한 채로, 별도의 리소스의 잠금을 요구하며 기다리 는 일이 있다. 이미 잠금되어 있는 리소스를 다시 취할 수 없다. 리소스의 잠금을 취하는 순서가 정해지지 않았다. 멀티 스레드 프로그래밍에서는 처음 세 가지 조건은 비교적 어쩔 수 없는 일이라 손댈 수 없어, 마지막 조건을 잡기 위해 리소스의 잠금 순서를 정해 둠으로써 대처하 곤 한다. 그러나 이 조치는 분명히 사람의 주의력에 의존한다. 뒤늦게 개발에 뛰어든 프로 그래머에게 프로그램 전체에서 몇 개 있는지도 명확하지 않은 리소스의 잠금에 관한 순서를 코드에서 파악하게 하는 것은 가혹하다고 말할 수 있다. 그렇다고 해서 도큐 먼트로 관리한다면 드물게 우스갯소리 주46 로 나오는 스프레드 시트로 관리되는 변 38 Chapter 0 [입문] 함수형 프로그래밍

63 수 관리 테이블 과 같은 존재가 되어 버리는 것은 아닐까 싶다. 게다가 어떤 리소스 를 잠그고 있는 절차 중에 다른 리소스를 잠글 필요가 있는 절차를 부르려고 한다면, 결과적으로 리소스 두 개의 잠금 순서가 정해진 잠금 순서에 어긋난 경우 이 호출은 하면 안 된다. 호출하려는 절차 중에 있다고 해도 무엇을 어떤 순서로 잠갔는지 모두 쫓아가 검증할 수 없다면, 일반적으로 부담 없이 하는 절차 호출조차 위험한 것이다. 사실상 잠금을 포함한 절차끼리는 결합할 수 없다고 말해도 좋다. 일부 함수형 언어는 STM(Software Transactional Memory)이라는 DB의 트랜잭 션(transaction) 주47 및 그 리트라이(retry) 제어와 비슷한 메커니즘을 갖추고 있어 비 교적 높은 실행 효율로 리소스의 배타적 처리를 쉽게 할 수 있다. 리소스의 배타 처 리 중에는 실시해야 할 처리가 제한되므로 안전하다. 병렬 프로그래밍의 기여 참조 투명성의 보증 함수형 언어는 명령형 언어와의 비교에서도 언급했듯이 파괴적인 대입 조작을 할 수 없거나 매우 제한적인 조건에서만 허용된다. 특히 순수 함수형 언어에서는 함수 가 언제 어떻게 평가해도 같은 결과가 된다. 즉, 그 처리만 병렬화하여도 같은 결과 가 된다는 것을 알고 있다. 중요한 것은 알고 있다 라는 것이다. 예를 들어, 굳이 함수형 언어가 아니라도 참 조 투명성을 만족하는 처리만 있으면 아무런 생각 없이 병렬화하여도 전혀 문제가 없다. 그러나 정말 참조 투명성을 만족하는 처리인지, 그리고 훗날 누군가가 처리에 손을 댔다고 해도 참조 투명성을 계속해서 만족하는지 등, 일일이 프로그래머가 사 람의 주의력의 한계 내에서 보장해야 한다는 사실이다. 크기에 있어 일정 수준의 처리라면 컴파일할 때에 참조 투명성을 만족하는지를 처 리계가 자동으로 판단할 수 있을 것이다. 하지만 대부분의 언어에서는 만족하지 못 하고 있다고 해도 컴파일 오류가 발생하지 않는다. 여기서의 알고 있다 는 처리계 주46 이제는 우스갯소리가 아닐지도 모르겠다. 주47 상태의 무결성을 갖는 목적 등, 여러 처리를 불가분의 관계로 실행하여 그들 모두가 문제없이 실행되었 을 경우에만 반영시키는 처리. 0.6 왜 지금 함수형 언어인가? 39

64 의 기준에 있어서 언어 기능으로서의 판단 이라는 것이다. 담당한 프로그래머가 있으므로 때문에 괜찮다고 말할 수 있을지도 모르겠지만, 프 로그래머 자신이 인간으로서 한계가 있는 기억력으로 언제까지 기억할 것인지, 또 코드에 손을 대는 다른 프로그래머도 마찬가지로 이해하고 있는지는 전혀 보장되지 않는다. 이에 대해 어차피 프로그래머가 언어의 제약을 깨뜨리는 것이 불가능하다 면, 처리계가 처리의 성질을 판단할 수 있어 성질을 만족하지 않을 때에 컴파일 오류 로 처리해 누가 처리에 손을 대도 성질을 보장할 수 있다. 실수 없이 작성할 수 있다면, 그리고 실수 없이 유지 관리해 나갈 수 있다면, 현대 컴퓨터 아키텍처에서는 명령형 언어 쪽이 빠른 경우가 많다. 진정으로 속도가 요구 되는 부분이라면 Fortran 등의 병렬 계산 능력 쪽이 아직 우위성도 있다고 할 수 있 다. 그러나 한번 작성하고 버려도 좋다고 확실히 말할 분야의 프로그램이라면 몰라 도 대부분의 경우, 프로그램은 유지 보수 등의 업데이트를 통해 사용자에게 제공해 야 한다. 사양상에서 올바른 동작을 다시 정하고 현실적인 비용과 시간 내에서, 그리 고 가능하면 프로그래머에게 과도한 부담이 가지 않는 범위 내에서 프로그램에 손을 댈 필요가 있는 것이다. 병렬화 부분이 문제없이 동작하기 위한 성질 주48 로 처리계를 보장할 수 있다는 사실은 분명 프로그래머에게 큰 도움이 될 것이다. Column 함수형 언어와 정리 증명 소프트웨어나 하드웨어의 사양/설계/검증을 수학적인 엄밀함을 갖고서 처리하는 형식 기법이 있다. 정리 증명(theorem proving)은 형식 기법(formal method)의 한 분야로 시스템이 나 프로그램, 한 개의 함수 등 사양대로 동작하는 것을 테스트에 의존하지 않고 통째로 증 명하는 것이다. 테스트에서는 테스트를 통과한 경우만 올바로 동작한다고 생각한다. 결과 적으로 경계값과 같은 코너 케이스(corner case)의 테스트 누락 등이 발생하여 버그로 나 타나면 프로그래머의 시간을 빼앗기게 된다. 이에 반해 사양대로인 것이 증명되면, 어떠한 경우의 입력에 대해서도 올바로 동작하는 것이 보증된다. 함수형 언어는 정리 증명과 궁합이 좋은 것으로 알려져 있다. 18페이지의 칼럼에서 소개 한 Coq와 Agda, Idris 등도 정리 증명을 할 수 있는 함수형 언어다. 주48 예를 들어, 병렬 라이브러리에 대한 이용자가 제공하는 처리가 수학적인 의미의 함수여야만 한다 등 의 성질. 40 Chapter 0 [입문] 함수형 프로그래밍

65 일반적으로 정리 증명이 아직 간단하지는 않다. 함수형 언어에 익숙한 프로그래머라도 정리 증명을 제대로 사용할 수 있는 프로그래머는 아마도 많지 않을 것이다. 그만큼 정리 증명을 하려면 비용이 소요된다. 그러나 세상에는 시스템이 버그를 만들 경우 인명과 관련된 분야가 있다. 예를 들어, 항 공 우주, 의료, 원자력 등이 그러하다. 또한 암호화를 비롯한 보안 분야의 경우, 완벽하다는 것으로 가치가 인정된다. 이러한 분야에서의 형식 기법은 비용에 걸맞은 효과를 발휘할 가 능성이 있다. 그 밖에도 여러 미션 크리티컬(mission critical: 핵심 업무 수행)한 분야에서 정리 증명을 비롯한 형식 기법의 효과는 점차 인정을 받으며 나아가게 될 것이다. 0.7 함수형 언어와 함수형 프로그래밍의 관계 강력한 성과를 끌어내기 위해서는 어떻게 하면 좋은가? 함수형 프로그래밍을 위해서 함수형 언어를 사용하는 편이 좋은 이유가 있다. 여 기에서는 그 이유를 확인한다. 함수형 프로그래밍의 도입 명령형이라도 활용할 수 있는 기법 함수형 프로그래밍은 이를 위한 몇 가지 제한 사항을 지키면 아마도 많은 언어에 서 가능할 것이다. 실제로 함수형 프로그래밍을 배운 후 명령형 언어를 사용하게 되 더라도 그 언어에서 함수형 프로그래밍을 사용해 이득이 될 기회가 있다는 점을 알 게 될 것이다. 다른 언어를 사용하더라도 함수형 프로그래밍에서 얻은 지식을 반영하여 안전한 프로그램을 목표로 하는 것은 가능하다. 주49 함수형 프로그래밍에 대한 제약을 지키 주49 현실 문제, 새롭게 시작하는 프로젝트가 아닌 한, 함수형 언어를 사용하지 않은 업무에 있어서 함수형 언어를 사용하기 시작하는 것은, 기존의 자산이나 속박/교육 비용 등과 비추어 보면 고려해 볼 수 있는 것이다. 0.7 함수형 언어와 함수형 프로그래밍의 관계 41

66 며 가능한 한 대입을 하지 않고, 혹여나 해야 할 경우에도 최소한의 범위에 한해 함 수의 적용을 기반으로 처리를 기술할 수 있도록 하면 되는 것이다. 주50 함수형 언어에 의한 함수형 프로그래밍의 도입 위와 같은 함수형 프로그래밍을 하려면 역시 함수형 언어가 적합하다고 말할 수 있다. 함수형 프로그래밍을 위한 제약을 지키고 규율에 맞는 프로그램을 작성하는 것을 보통은 함수형 언어가 체크해 주기 때문이다. 예를 들어, 입출력을 포함한 처리를 작성해서는 안 된다 라는 제한된 스코프 (scope)를 정의할 수 있으며, 실제로 그 안에서 입출력을 포함한 처리를 작성할 수 없 는 기능이 있다면 이것은 매우 유용한 기능이다. 트랜잭션처럼 롤백(rollback)이 발 생할 수 있는 처리에서는 입출력 처리와 같이 실행하면 되돌릴 수 없는 것은 사용해 서는 안 된다. 그런 부분이 앞서 언급한 제약의 범위로 있으면 안전한 프로그래밍을 할 수 있다. 그러나 이러한 기능이 없는 언어의 경우, 입출력 처리를 포함하지 않는다는 제약 을 프로그래머에게 지키게 하려면 그 취지를 문서나 주석으로 작성하는 것밖에 방법 이 없고, 정말로 입출력이 적혀 있지 않은지 코드를 일일이 살펴보는 것 이외에는 확 인할 수 없는 것이 현실이다. 18페이지의 칼럼에서 소개한 함수형 언어는 함수형 프로그래밍을 간단히 하기 위 해, 그리고 함수형 프로그래밍을 실시한 결과로부터 보다 강력한 성과를 도출하기 위해 기능을 발전시켜 온 언어들이다. 주51 주50 실제, 필자는 명령형 언어를 사용할 경우 이렇게 코딩하는 버릇이 생겼다. 주51 이 점에 대해서는 0.9절 함수형 언어를 채용하는 장점 에서 좀 더 상세하게 다루겠다. 이와 함께 참조 하길 바란다. 42 Chapter 0 [입문] 함수형 프로그래밍

67 0.8 함수형 언어의 역사 과거를 알고 미래 탐구하기 함수형 언어가 걸어온 역사를 살펴봄으로써 향후의 발전 방향을 알아보겠다. 함수형 언어의 발자취 - 지금까지 표 0.2는 함수형 언어의 등장 연표다. 함수형 언어의 배경인 람다 계산(λ계산)은 1930년대에 알론조 처치(Alonzo Church) 에 의하여 고안되었다. 주52 람다 계산은 그 자체가 튜링 완전(turing completeness), 즉 만능 튜링 머신(universal turing machine)과 같은 계산 능력을 가졌다. 더 직관적 으로 말한다면 다른 잘 알려진 언어와 같은 표현 능력이 있다는 것을 나타낸다. 함수형 언어로서 첫 번째 실제적인 구현이라 할 수 있는 LISP 주53 는 1958년에 나타 났다. LISP는 S식 주54 이라는 간단하고 강력한 기법을 도입했다. S식에서는 프로그 램 자체를 데이터로 취급하는 것이 매우 용이하다. 파생 언어인 Scheme과 Common Lisp, Clojure를 포함하여 오늘날에도 열렬한 팬이 있는 언어다. Emacs를 사용하는 사람이라면 Emacs LISP라는 LISP 파생 언어를 사용하고 있을 것이다. 1966년, ISWIM 주55 라는 추상 프로그래밍 언어가 고안되었다. ISWIM은 람다 계산 의 코어를 명령형 언어에서 구문 정의한 것으로 구현조차 주어지지 않았지만, 나중 에 ML, SASL 주56 계열의 함수형 언어 구문에 큰 영향을 주었다. 주52 A. Church A set of postulates for the foundation of logic (Annals of Mathematics, Series 2, 33: , 1932) 주53 J. McCarthy Recursive functions of symbolic expressions and their computation by machine (Communications of the ACM, 3: , 1960) 주54 S식은 심벌 과 S식의 그룹 만으로 이루어진 매우 간단한 식으로 트리 구조의 데이터로서 취급한다. 괄호가 대량으로 나온다. 주55 P.J. Landin The next 700 programming languages (Communications of the ACM, 9(3): , 1966) 주56 Untyped의 순수 함수형 언어다. 0.8 함수형 언어의 역사 43