PL(프로그래밍 언어)계에서 함수형 프로그래밍 언어는
자동차 엔진으로 치면 로터리 엔진, 발전소 업계로 치면 핵융합 발전 같은 뭔가 이상은 높지만 현실은 아직 좀 시궁창인 그런 떡밥스러운 영역으로 간주되는 것 같다.

전산학을 전공해서 PL 수업을 들은 분이라면 이미 잘 아시겠지만, 프로그래밍 언어란 크게 절차형과 선언형으로 나눌 수 있다.
절차형은 튜링 기계라는 컴퓨터의 특성을 그대로 반영하여 메모리로부터 값을 읽은 뒤 연산을 수행해서 값을 변경하고, 메모리 위치도 바꾸는 절차를 순차적으로 일일이.. 즉 HOW 위주로 기술하는 언어이다. 정보 올림피아드 경시부가 다루는 것은 응당 절차형 프로그래밍 언어를 활용하여 프로그램을 작성해서 문제를 해결하는 능력이다.

(덧붙이자면 튜링 기계에다가 데이터뿐만 아니라 코드, 즉 상태 변환 로직까지 동일한 메모리에다 올려서 해석하는 계산 모델이 바로 오늘날 컴퓨터의 근간이 된 프로그램 내장형, 즉 폰 노이만 모델이다. 자동차 엔진로 치면 정말 외연 기관에서 흡입-압축-폭발-배기 4행정 내연 기관으로 변모한 수준의 발전이 아닌가 싶다.)

한편, 선언형은 우리가 원하는 솔루션의 정의 내지 조건이 이러하다.. 라고만 써 주는 형태의 WHAT 지향형 언어이다. 그러면 컴퓨터가 알아서 문제를 풀어 낸다.
따지고 보면 데이터베이스 질의어인 SQL은 DLL, EXE 같은 실행 파일을 만드는 용도의 언어가 아닐 뿐이지 아주 대표적인 선언형 언어이다. 복잡한 DB에서는 질의어를 만드는 것도 굉장히 복잡한 일이 되며, 두 DB간의 JOIN은 어떻게 시키고 어느 구문부터 풀이해서 최적의 성능으로 질의를 수행할지 결정하는 것도 아주 어려운 축에 든다. 이런 거 성능 소요 시간을 몇 % 단축시키는 알고리즘을 개발해 내면, DB를 연구하는 전산학과 대학원 연구실에서는 그게 곧바로 논문감이 된다.

흔히 인공지능 문제 풀이형 언어로 알려져 있는 프롤로그도 선언형 언어이다. 이건 진짜 여러 변수들을 선언한 뒤 변수들간의 인과관계를 쭈욱 나열해 주면 이를 바탕으로 언어 런타임이 문제의 답을 찾아 낸다.

까놓고 말해 절차형 프로그래밍 언어로 "아인슈타인의 퍼즐" 같은 걸 풀려면, 프로그래머가 재귀호출에 각종 백트래킹 알고리즘을 직접 구사해야 하니 앞에서 말했던 정보 올림피아드 경시부 급의 기술이 필요하다. 그러나 프롤로그에서는 "영국인.집 = 빨강, 스웨덴.애완동물 = 개" 이런 식으로 단서만 주어진 규칙대로 쓴 뒤 쿼리를 날리면 금붕어를 기르는 사람의 국적을 구할 수 있다.

아마 네모네모 로직이나 스도쿠 같은 것도 해답이 갖춰야 할 조건을 명시하는 것만으로 바로 풀 수 있지 싶다. 단서들을 바탕으로 뺑뺑이를 돌리는 추론 과정은 언어 런타임 내지 엔진이 해 준다.
대학 학부 시절, OR개론 수업 때 잠시 접했던 선형계획법 문제 풀이 프로그램인 k-opt도 역시 지정된 문법에 따라 변수와 부등식들을 써 놓고 최소화/최대화 조건을 명시하면 프로그램이 해를 찾아 주니.. 일종의 선언형 프로그래밍 언어 런타임에 속한다고 할 수 있겠다.

그러니, 절차형 언어의 컴파일러는 최적화를 하는 게 기계어 코드 생성이나 멀티코어 병렬화 같은 아주 미시적인 것과 관계가 있는 반면, 선언형 언어의 수행 방식을 최적화하는 것은.. 거시적인 알고리즘 전략까지 결정해야 하니 더욱 까다로울 것이다. 미시적인 건 해당 언어 엔진이 아주 정교하게 구현되어 있지 않은 이상 신경 쓰기 힘들다.

앞서 언급한 SQL이나 프롤로그는 선언형 프로그래밍 언어 중에서 일종의 '논리 지향'인 물건들이다. 그런데 선언형의 하위 범주로는 '함수 지향', 함수형 프로그래밍 언어라는 게 있다. 이게 절차형보다는 좀 더 수학자스러운 형태로 컴퓨터를 부려먹는 방법을 기술하는 방법론이라고 한다. (함수형이 여느 절차형 프로그래밍과 계산 능력이 동등하다는 것은 튜링 기계와 람다 대수가 동치라는 것이 증명됨으로써 알려져 있다.)

순수한 함수형 프로그래밍 언어에서는 지저분한 대입 연산이 없고 한번 생성된 값은 변경 없이 계속 그 값으로 남아 있다. 새로운 값이 계속 생성될 뿐이다. 사실 문자열을 이런 사고방식으로 처리하는 라이브러리나 언어, 프레임워크에서는 이미 있는 문자열을 변경하는 게 굉장히 어렵기도 하다. Windows RT의 String 클래스도 그랬던 걸로 기억..

함수형 언어에서는 대입이 없으니 응당 뺑뺑이 loop도 있을 수 없다. loop을 대신하는 것은 재귀호출이다! loop조차도 기존 값을 계속 바꾸는 게 아니라 새로운 값을 자꾸 만들어 내는 방식으로 구현된다는 뜻이다.
처음에 해답의 범위가 0부터 100 사이에 있었다면 그 다음 턴에는 0부터 50 (log n 시간 복잡도), 혹은 0부터 99로 자가호출이 이뤄지고, 이것이 문제가 완전히 해결될 때까지 반복된다. 왜냐하면 이 문제의 솔루션이 바로 그런 형태로 귀납적으로 정의돼 있기 때문이다. 팩토리얼이든, 두 수의 최대공약수이든, 정렬이든 다른 무엇이든.

이 패러다임에서는 함수가 다른 여느 데이터와 완전히 동일한 수준으로 다른 함수의 인자가 될 수 있고, 특히 이름 없이 함수의 몸체만을 여느 값처럼 달랑 전해 줄 수 있고, 다른 함수로부터 합성되고 유도된 새로운 함수가 함수의 리턴값이 될 수 있다. 새로운 함수가 동작하는 데 필요한 주변 문맥은 클로저라는 물건이 알아서 다 처리해 준다.
C/C++의 함수 포인터에 머리가 굳은 프로그래머라면 calling convension은 무엇인지, this 포인터가 포함된 멤버 함수인지, pointer-to-member라면 다중 상속으로 인한 부가 오버헤드는 없는지 같은 디테일 때문에 머리가 복잡해질 것이다.

함수형 언어에서 if문은 응당 자기 자신도 조건이 만족하는 쪽의 값을 되돌리는 함수 형태이다.
그러나 if는 조건이 만족하는 쪽만 '계산'이 행해질 터이니 if(a) b; else c; 를 나타내는 if(a, b, c)는 통상적인 함수 호출 func(a, b, c)와 의미상으로 완전히 동일할 수는 없다. 예약어로 따로 해석되고 취급을 받아야 할 듯하다.

물론 이런 함수형 프로그래밍 언어가 구현되기 위해서는 현실에서 컴파일러가 최적화해 줘야 하는 것, 그리고 언어 런타임이 해 줘야 하는 오버헤드가 적지 않다. 끝없이 새로운 값을 생성해 내더라도 이제 참조가 끝나서 더 쓰이지 않는 값은 GC가 알아서 제거해 줘야 하고, 재귀호출, 특히 tail recursion 정도는 알아서 메모리 복잡도를 O(n) 급으로 늘리지 않는 일반적인 loop처럼 돌아가게 컴파일러나 런타임이 최적화를 해 줘야 한다. 함수를 값처럼 부드럽게 다루는 것도 기술적으로는 단순 함수 포인터 이상의 추상화 계층이 필요하며, 말처럼 쉬운 일이 아니다.

예를 들어.. X라는 함수가 있는데.. 얘는 a라는 인자를 받고는,
b라는 인자를 받아서 a에다가 b를 더한 값을 되돌리는 Y라는 함수를 되돌린다고 치자.
결국 Y는 X라는 함수가 호출될 때 전달되었던 매개변수 내지 그때 생성된 X 내부의 지역 변수에 의존하여 동작하는데..
나중에 Y가 단독으로 호출될 때는 X라는 함수는 실행이 끝나고 그 문맥이 존재하지 않는다. 이를 어찌하리?
이런 딜레마를 피하기 위해 C/C++ 언어는 애초에 함수 안에 함수를 만드는 걸 지원하지 않는 쪽으로 설계되었으며, C++의 functor 같은 것도 전부 자기가 자체적으로 데이터 멤버를 갖고 있는 객체 형태로 만들어지게 된 것이다.

또한, 아무리 대입이 사이드 이펙트가 남는 지저분하고 기피되어야 하는 연산이고.. 다른 모든 연산을 loop 대신 재귀호출로 때운다 해도.. 당장 외부 파일/키보드로부터의 input은.. 대입 연산 없이는 감당이 도저히 불가능하다. 그리고
return t1.len() > t2.len() ? t1: t2
처럼 그 재귀호출의 결과값을 취사 선택하는 간단한 판단을 위해서라도 임시 변수에 대입하는 것 정도는 근본적으로 전혀 없을 수가 없다.
어디 그 뿐이랴. 대용량의 단일 데이터를 대상으로 여러 함수들이 포인터만 주고받으며 동작하다 보면, 한 함수가 자기 argument 안에 입출력 대상인 모든 데이터를 집어넣는 것은 무리가 있다.

허나 함수형 프로그래밍이 성능면에서 불리한 요소만 있는 건 아니다. 대입으로 인한 side effect 같은 게 없으니 소스 코드의 정적 분석은 더 용이할 것이고 병렬화 등 입맛에 맞는 최적화에도 더 유리할 것이다. 애초에 선언형 프로그래밍 언어는 구체적인 실행 방식은 그런 똑똑한 컴파일러나 언어 엔진에게 맡기고 있으니까.
이러니 PL 분야를 연구하는 전산학자나 수학 덕후들이 함수형 프로그래밍 언어에 더욱 열광하는 듯하다. 저런 패러다임이 응집도· 결합도 같은 소프트웨어 공학적인 측면에서 더 깔끔한 코드를 만드는 데 도움이 되는 것은 덤이다.

대학교 전산학과에서는 함수형 프로그래밍 언어로 보통 Scheme을 실습하는 편이다. 본인도 먼 옛날 학부 시절에 '프로그래밍의 이해(PP)'라는 과목을 통해 그 물건을 접했으며, 그걸로 무슨 다항식의 곱셈을 하는 프로그램도 숙제로 만들고 여러 덕질을 했었다. 함수형 언어의 진짜 본좌라고 일컬어지는 Haskell 같은 건 난 모름.;;

여담이지만 지금 생각해 보니, 온갖 복잡한 괄호가 배배 꼬여 있는 Scheme 코드는.. 언어학에서 문장 구문 분석을 괄호로 표현해 놓은 것과 사뭇 닮았다는 생각이 들었다. (S (NP .. ) (VP ...)) 이러는 식.
Schme에서는 S 대신에 define, lambda, if 따위가 있을 것이다.

물론 그때는 본인은 <날개셋> 한글 입력기 개발에 도움이 안 되는 건 진짜 생까고 무시하던 시절이어서 그 코스의 의미를 제대로 이해를 못 했다. 왜 괜히 계산 과정을 이 따위로 어색하게 표기를 하는지..??
그건 사칙연산 같은 기초적인 연산자조차도 통상적인 표기법이나 우선순위를 깡그리 무시하고 정말로 오로지 함수 위주로.. 프로그래밍이, 아니 계산(computing)이라는 작업 자체를 몽땅 주어진 규칙대로 피연산자들을 처리해서 reduce하는 과정이라고 극도로 추상화한 귀결일 것이다. 일종의 발상의 전환인 것이다. car, cdr 명령이 튜링 기계로 치면 메모리 셀을 이동하고 값을 읽는 동작에 해당할 것이다.

단, Scheme도 마냥 순수 함수형 언어이기만 한 것은 아니다. 필요한 경우 대입 연산이 있을 수 있고 일부 절차형 패러다임 구문을 집어넣을 수도 있다. 마치 C#에서 부분적으로 unsafe, unmanaged 코드를 집어넣듯이 말이다.
그리고 반대로 C++ 역시, 기본적으로 객체지향 패러다임을 주류로 내세운 절차형 언어이지만 최근에는 함수형 프로그래밍 패러다임도 받아들여서 람다 함수를 기존 함수 포인터나 functor의 대용으로 쓸 수 있게 되었듯이.. 요즘 언어들의 대세는 자기 정체성은 유지하면서 다른 패러다임에서도 유용한 건 적극 받아들이는 것인 듯하다.

과연 함수형 프로그래밍 언어가 그저 대학교 과목에서나 잠깐 접하고 마는 떡밥 내지 PL 분야의 연구자들만 쓰는 도구 수준을 넘어.. 현업에서 적극 즐겨 쓰이는 날이 올지 모르겠다. 지금 현업에서 전혀 안 쓰인다는 말은 아니지만 아직까지는 수학 덕후, 컴덕후들의 전유물이라는 인상이 강한 편이니 말이다. 그래도 한 가지 확실한 건, 함수형 프로그래밍 패러다임을 실현해도 될 정도로 요즘 컴터 환경이 좋아지자, 각종 언어들에도 이 패러다임이 적극 많이 도입되고 이게 유행을 타고 있다는 사실이다.

여담으로, 람다 대수를 고안한 앨론조 처치는 family name이 어째 '교회'다..;; 독실한 신자 가문이기라도 했나 싶은 잡생각이 든다.

그리고 궁금한 게 있는데.. 이름 없는 함수에서 재귀호출을 해야 할 때 함수 자기 자신을 가리키는 this, self 같은 키워드는 없는가 싶다.
이 의문은 C++에서 람다 함수가 추가되었을 때부터 여러 프로그래머들에 의해 제기되어 왔다. 하지만 뾰족한 해결책은 없으며, std::function에다가 자신을 저장한 뒤, 그 변수명을 캡처로 도로 넘겨 줘야만 재귀호출이 가능하다. Scheme 역시 일단 def로 자기 이름을 지은 뒤, 그 이름을 호출해 줘야 된다.

재귀호출을 그렇게도 좋아하는 함수형 언어가

[](int x) { return x<=1 ? 1: this_func_itself(x)*(x-1); }

개념적으로 this_func_itself에 해당하는 키워드 같은 건 정말 없는 건지 신기한 노릇이 아닐 수 없다.

Posted by 사무엘

2014/12/28 08:39 2014/12/28 08:39
, , ,
Response
No Trackback , 9 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1044


블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2019/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

Site Stats

Total hits:
1294043
Today:
26
Yesterday:
668