2009.02.06 22:54

lisp에관한 생각들 -다섯번째

해커 문화의 뿌리를 찾아서 Part 5: Fixed Point 계산과 고차 함수



안윤호안윤호 mindengine@freechal.com

필자는 아마추어 리눅스 커널 해커였으며 최근에 팹(Fab)이라는 책을 번역 출간했다. 컴퓨터의 여러 분야에 관심이 많고 컴퓨터와 문화의 인터페이스에도 관심이 많다.


2007년 8월 7일


연재순서
1회(2007년 4월): 리스프가 탄생하기까지
2회(2007년 5월): 원시 리스프의 재구성
3회(2007년 6월): 해커리즘의 문화
4회(2007년 7월): 액터와 람다
5회(2007년 8월): Fixed Point 계산과 고차 함수



Fixed Point 계산

함수를 반복적으로 적용하는 경우에 대해 생각해 보자. 함수를 여러 차례 적용하는 방식에는 반복(iteration)과 재귀(recursion)가 있다(재귀를 순환이라고 부르는 사람도 있다. 번역하는 사람들마다 다른 용어를 사용하는데 재귀와 반복을 되풀이와 되돌이로 표현하는 용례도 있다).

SICP의 시작부에는 제곱근의 해를 구하는 예제가 나온다. 제곱근을 구할 때 뉴튼 계산법(Newton's Method)을 사용하는 것으로 방정식의 해를 구하는 방법이다. 방정식은 뻔하다. 초기값 x로부터 시작하여 방정식의 해를 근사법으로 추론하는 방법이다. 해는 x의 값과 추론한 근사값의 중간에 있다고 가정하자. 만약 해를 구하는 함수가 있다고 하면 이 함수를 여러 번 적용하면 해를 구할 수 있을지 모른다. 문제는 이 예제가 어렵다는 것이 아니라 책의 초반부에 나온다는 점이다.

우선 SICP 책에서 루트를 구하는 간단한 코드를 보자. 이 코드는 근사치를 구하여 이 근사치의 제곱이 원하는 해에 근접하는지를 조사하는 것이다. 핵심적인 코드는 근사치 guess가 원하는 값에 충분히 가까우면 guess를 리턴하고, 아닌 경우 improve로 guess 값을 계산하여 다시 자기 자신을 호출하는 5줄짜리 sqrt-iter 함수다. improve는 x와 guess로 새로운 guess 값을 만든다.

  
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
(sqrt-iter 1.0 x))


매우 간단하지만 상당한 정밀도까지 해를 구할 수 있다. SICP(http://mitpress.mit.edu/sicp/full-text/book/book.html) 1장에는 코드에 대한 자세한 설명이 나오고 뉴튼 계산법은 미적분학을 배운 사람들에게는 쉬운 문제다. 수치해석까지 공부한 사람들은 훨씬 많은 예들을 알고 있을 것이다.



x=cos(x)의 그림
그림 1. x=cos(x)의 그림

위의 식에서 중요한 것은 적당한 x에 대해 sqrt-iter를 여러 번 적용하면 해가 나온다는 것이다. 이런 예제들 중에 fixed point의 방법론을 적용하는 문제들이 있다. 그것은 f(x) = x를 만족시키는 조건에서 초기값 x0으로 시작한 문제들이 수렴하는 값 x가 있다는 것이다. 그렇다면 반복적으로 함수를 적용할 때 다음은 어떤 값으로 수렴할 것이다.





경우에 따라 f는 아주 여러 번 적용될 수 있고 몇 번만 적용될 수도 있다. 때로는 무한정으로 적용될 수도 있을 것이다.

함수를 여러 번 적용하여 라디안으로 표현한 코사인 함수에서 x=cos(x)를 만족하는 해를 찾는 것을 그림 1에서 보여주고 있다. 해는 중앙의 점으로 수렴한다(수렴은 리아푸노프 안정성이나 위상평면에서 해의 존재 유무나 궤적 문제로 복잡하게 풀어나갈 수도 있다). 어떤 시스템은 일정한 범위에서는 수렴한다는 것이 알려져 있다. 비슷한 예들은 매우 많으며 자연계에서도 관찰된다. 비선형 동력계 또는 카오스 패턴으로 나타난다. 로렌츠 어트랙터나 다른 여러 가지 스트레인지 어트랙터(strange attractor)들이 자연계에 존재한다는 것이 밝혀졌다. 해들은 특정한 값이나 일정한 범위에 있는 수많은 해를 갖는다.

수렴하는 조건이나 식들이 수식만이 아니라 기호나 집합일 수도 있다. 컴퓨터에서는 데이터들을 수렴하는 방법이 있을지도 모른다. 표현 방식은 여러 가지지만 단순한 반복문이나 재귀 코드나 다를 것이 없다. 여러 번 적용하는 것에서 일정한 패턴이 나오는 것을 기대할 수 있다. 만약 f가 수학의 함수가 아니라 리스프의 함수인 경우 재귀 형태나 반복 형태나 형식상의 큰 차이는 없다. 안에서 어떤 방법으로 구현되는지가 중요하다. f를 그냥 람다 함수라고 생각해도 마찬가지다. 또 어떤 함수를 fixed point로 만드는 변환 T를 만들고 새로이 변환된 함수가 수렴하기를 기대해 볼 수도 있다.

어떻게 보면 별다른 내용이 없는 수학 이야기 같지만 생각하기에 따라 생각할 거리를 던진다. 상징적으로 어떤 함수를 재귀적으로(또는 반복적으로) 사용하여 기호를 처리하거나 계산을 하는 것은 수렴 여부에 관계없이 다음과 같은 함수를 적용하는 하나의 패턴으로 생각해 볼 수 있다.





이런 방식으로 표현하면 평상시 사용하는 자바나 C++ 코드와는 다른 모습으로 생각해 볼 수 있다. 반복이나 재귀는 그저 함수를 여러 번 적용하는 것일 수 있다. 실제 코드에서 중간에 있는 f는 실제로 조건에 따라 내부의 함수 g나 h를 부를지도 모르며 리턴되는 값의 형태도 다양하다(fixed point의 성질과 적용에 대해 조금 더 생각해 보고 싶은 독자들은 서스만과 아벨슨의 강의 비디오 7a의 뒷부분을 보면 궁금증이 풀릴 것이다. Y 연산자의 문제나 fixed point가 수렴하는 문제들에 대한 통찰을 제공한다).



위로



리스프 머신의 기본 아이디어

브라이언 하비(Brian Harvey)라는 해커가 있다(http://www.cs.berkeley.edu/~bh/). 1960년대 말 MIT 졸업 후 AI 연구소에서 일한 적이 있다. 현재는 버클리에서 강의를 하고 있다. ‘Simply Scheme’이라는 책의 저자이기도 하다. 버클리 로고(LOGO) 개발자이기 때문에 로고에 관심이 있는 필자는 가끔 하비의 홈페이지를 들여다본다.

이번 글에 하비가 나온 이유는 SICP 강의를 하기 때문이다. 이 강의 동영상은 공개되어 있으며(이 글을 쓰는 현재 http://webcast.berkeley.edu/course_details.php?seriesid=1906978342에서 볼 수 있다) SICP 저자인 서스만과 아벨슨의 강의와는 또 다른 느낌의 강의를 하고 있다. 서스만의 강의보다는 느슨하게 진행되지만 새로운 관점을 보여주고 있다. 하비의 강의를 보고 새로운 시각에서 스킴과 SICP를 바라보는 사람들도 있었다고 한다. 필자도 강의를 보면서 많은 것을 배웠다. 학부 저학년을 대상으로 하는 강의로 가벼운 마음으로 들을 수 있다.

강의 주제 ‘Interpreter’에서는 리스프의 인터프리터에 대해 설명한다. 한마디로 인터프리터는 만능 기계(universal machine)이라는 것이다. 필자의 첫 번째와 두 번째 글이 인터프리터를 만드는 것으로 시작했으므로 독자들은 람다 계산법을 실행하는 특이한 프로그램에 대해 이미 알고 있으며 함수 apply와 eval에 대해서도 이미 알고 있을 것이다.

그림 2에서 (lambda(x)(+ (* 2 x) 3))을 인터프리터가 읽으면서 람다를 수행하는 기계처럼 변하고 7을 받아 결과 값이 나오는 모습을 보여주고 있다. 인터프리터는 주어진 식에 따라 변신을 한다. 식을 읽은 인터프리터는 마치 (2x +3)을 수행하는 기계처럼 변신하는 것이다. ((lambda(x)(+ (* 2 x) 3)) 7)은 17을 리턴한다.



람다식 그림
그림 2. 람다식 그림

그림 2에서 칠판의 오른쪽 그림은 인터프리터 기계에 람다식과 계산할 값을 제공하는 개념을, 왼쪽 그림은 람다식을 읽은 인터프리터가 2x+3을 계산하는 기계로 변한 것을 설명하고 있다.

그림 3은 식 (lambda (x) (+ (* 2 x) 3))을 cons cell 구조로 그려본 것이다. 당연히 식은 리스트 구조이지만 내부적으로는 이런 모습이라는 것을 보여주고 싶었다.



(lambda (x) (+ (* 2 x) 3)) 리스트
그림 3. (lambda (x) (+ (* 2 x) 3)) 리스트

인터프리터 역시 지난번에 보았듯이 조금 커다란 리스트다. 리스트로 만들어진 리스프 인터프리터 기계는 리스트로 만들어진 식을 읽고 결과를 리턴한다. 이 시스템에서 모든 것은 리스트다. 자료구조 역시 간단한 아톰이 아니라면 리스트이며 결과 역시 아톰이 아니라면 리스트다. 변수표도 리스트이며 환경이라고 불리는 변수 값 찾아보기의 프레임들 역시 리스트로 표기한다(최적화를 위해 실제로는 리스트가 아니지만 리스트로 표기한다).

리스트를 읽고 리스트를 만들어내는 프로그램도 리스트이며 이런 일을 모두 주관하는 인터프리터마저 리스트다. 이미 만들어진 리스프의 인터프리터를 이용하여 다른 리스프를 만들어내는 메타서큘러 인터프리터 역시 새로운 리스트를 원래의 인터프리터가 읽고 만들어낸 또 하나의 리스트일 뿐이다. 그런데 그 리스트는 실제로 작업을 한다!

앞의 비유를 들자면 인터프리터 기계에 새로운 인터프리터 코드를 넣었더니 기계가 새로운 기계로 변신한 경우다. 그러니 만능 기계라는 말은 맞다. A4 1장으로 만든 개념적인 인터프리터 안에 내재된 특성치고는 놀라운 것이다. 그리고 람다 계산법의 특성에서 도출되는 결론이지만 코드와 프로그램은 잘 구분되지 않는다(연재 3회의 글 가운데 람다를 소개한 부분을 살펴보라).



위로



고차 함수(Higher Order function)

SICP 책의 앞부분인 1.3에 나오는 글이면서도 상당히 어려운 부분이다. 우선 고차 함수라고 번역할 수 있는 이 함수는 하나 또는 그 이상의 함수를 인수로 취하거나 결과값으로 함수를 내어주어야 한다. 컴퓨터보다는 수학에서 더 적절한 비유를 찾을 수 있다. 미분연산자는 함수를 받아 다른 함수로 내어준다. 함수형 프로그래밍 언어에서 많이 쓰이는 map 함수 역시 고차 함수다. 이를테면 함수 f를 입력으로 받아 개별적인 요소들에 대해 계산한 결과 값을 돌려준다.

독자들도 알다시피 함수형 프로그래밍(functional programming)은 함수의 계산(evaluation)만으로 프로그래밍하며 상태(state)를 갖거나 데이터 값을 변경하지 않는 것이다. 간단히 말하면 함수형 프로그래밍에는 대입 연산이라는 것이 없다. 그러나 명령형 프로그래밍(imperative programming)은 상태 변화에 기반을 둔다. 리스프에는 원래 대입 연산이 없었다. 나중에 대입 연산이 구현되었으나 함수형 언어처럼 사용할 수 있다. 스킴 역시 마찬가지다.

고차 함수를 사용하면 함수 대입이나 변환에서 상당한 유연성을 제공하는 것이 분명하다. 여기에 든 예제들은 주로 수식 위주지만 기호와 리스트, 다른 함수가 제공하는 지연된 답들마저도 고차 함수를 이용하여 표현할 수 있다. 앞서 예를 든 반복문의 적용 패턴도 일종의 고차 함수처럼 바라볼 수 있다.

고차 함수의 정의와 무관하지 않은 몇 가지 패턴이 있다. 우선 프로시저가 다른 프로시저의 인자로 작용하는 경우를 생각할 수 있다. 다음 식은





아래와 같은 모습의 프로시저로 구성할 수 있다(공통된 패턴이 있다는 것은 유용한 추상화가 가능하다는 증거이기도 하다. 일단 양측을 잘 살펴볼 필요가 있다).

  
(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))


위 식에서 term과 next는 함수이면서 실제로 함수의 인자이자 이름처럼 넘겨졌다. C와 같은 언어라면 함수의 포인터를 넘기는 것으로 비슷한 일을 할 수 있지만 제약이 있을 것이다. 리스프 계열 언어에서는 용법의 사소한 차이는 있어도 함수 그 자체가 다른 함수의 인자가 된다. 밑의 식은 1부터 10까지의 정수를 그냥 더하는 것이다. 제곱이나 세제곱 아니면 다른 복잡한 함수도 쉽게 적용할 수 있다. identity 대신 square나 cubic이 붙은 함수를 정의하고 적용하면 되는 것이다. term과 next에 해당하는 함수를 바꾸어주는 것만으로도 많은 일을 할 수 있다.

  
(define (inc n) (+ n 1))
(define (identity x) x)

(define (sum-integers a b)
 (sum identity a inc b))


그러면 (sum-integers 1 10)은 55를 리턴한다.

두 번째는 람다 함수 사용이다. sum을 만드는 프로시저 코드 안에 직접 람다를 사용하여 좀 더 유연하게 프로시저를 만들 수 있다. pi-sum은 a에서 b까지 계산마다 +4씩 증가하고 이 값을 (lambda (x) (/ 1.0 (* x (+ x 2))))에 적용하고 결과를 더해가는 프로시저다.

  
(define (pi-sum a b)
  (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
       a
       (lambda (x) (+ x 4))
       b))


세 번째로는 프로시저를 일종의 메서드처럼 사용하는 방법이다. 프로시저가 다른 프로시저와 복합적인 방법으로 사용되는 것은 물론이고 다른 프로시저를 컨트롤하는 프레임워크가 되는 것이다.

네 번째는 프로시저의 결과 값 자체가 새로운 프로시저가 되는 것이다. 앞서 말한 것처럼 미분연산자를 통과한 함수가 전혀 다른 것이 되는 일 같이 어떤 프로시저는 입력으로 받은 프로시저 자체를 새로운 프로시저로 되돌린다. 지면상 이 방법의 예제를 적는 것은 생략하지만 SICP의 1.3.4에 간단한 예제가 있다. 만능 기계처럼 움직이는 인터프리터 예제도 이 범주에 속한다(사실 1.3을 한 번에 이해할 수 있다면 정말 지나치게 총명한 독자라고 할 수 있다. 이 장에는 보물찾기처럼 많은 것들이 숨어있다).

앞의 예들은 일반적 언어에서는 자주 사용되지 않는다. 강력한 권한 때문에 안전성이나 코드 효율 면에서 복잡한 문제들이 발생할 소지가 있다. 그래서 보통 프로그래밍 언어들은 조작되는 요소들에 제약을 걸고 있다. 가장 적게 제한 받는 요소들을 first-class의 요소들이라고 한다. first-class 요소들의 ‘책임과 권리’는 다음과 같다.

  • 변수를 사용하여 이름을 부여할 수 있고
  • 프로시저의 인자로 넘겨질 수 있으며
  • 프로시저의 결과 값으로 되돌려질 수 있고
  • 자료 구조 내에 포함될 수 있다.

독자들의 머리를 아프게 하기 때문에 좋은 예라고 볼 수는 없지만 SICP 1.3장은 뉴튼 계산법으로 제곱근을 계산하는 방법들을 여러 가지 방법으로 추상화하여 만들어낼 수 있음을 보여준다. 하나의 아이디어를 표현하는 여러 가지 우아한 방법이 있다는 것을 알려준다.

보충에 가까운 내용으로 피터 노빅의 글 ‘A Retrospective on Paradigms of AI Programming’에 있는 ‘PAIP로부터 배운 것들’ 부분에서는 다음과 같은 내용이 일종의 교훈이라고 전한다. 모두 52개나 되지만 지금까지 이야기한 것과 관련이 있는 것은 몇 개 안 된다.

  • 람다 함수를 사용하라(앞서 설명했다).
  • 실행시에 새로운 함수(closure)를 만들어내라(closure는 다음 회에 설명할 강력한 프로그래밍 패러다임이다).
  • 문제 해결에 가장 적절한 표기법을 사용한다.
  • 여러 가지 프로그램에 같은 데이터를 사용한다.
  • 구체적이어야 한다. 추상화를 사용하라. 간단해야 한다. 주어진 도구를 사용하라. 애매해지면 안 된다. 시종일관하라.
  • 매크로를 사용하라(정말 필요한 경우에만).
  • 20개 또는 30개 정도의 중요한 데이터 타입이 있는데 이들에 대해서는 잘 알고 있어야 한다,

위의 내용 중 클로저라는 것은 OOP에 나오는 개체의 인스턴스를 만드는 과정의 리스프 버전과 비슷하나 람다 함수의 특성을 이용한다. 지면상 다음 회에서 설명해야 한다.





   소셜 북마크

   mar.gar.in mar.gar.in
    digg Digg
    del.icio.us del.icio.us
    Slashdot Slashdot


다음 회에는 ‘GÖdel, Escher, Bach’라는 책에 대해 잠시 설명할 것이다. 상당히 어려운 책이지만 많은 컴퓨터 사람들의 영감을 자극했다(퓰리처상도 받았고 이미 고전이다). 책에는 여러 가지 테마가 섞여있지만 필자가 이야기하려는 것은 그 중의 일부만으로 내용 설명이 아니라 영감을 줄지 모르는 몇 가지 화두를 설명하기 위해서다.





그 다음은 해커들의 힘이라는 것이 결국 집단지능이라는 민스키의 이야기를 해야 할 것이다(사실 민스키와 매카시의 AI 연구소에 모여있던 프로그래머들을 해커라고 부르면서 해커리즘이 생겼다). 그리고 민스키를 소개하면서 그의 대표작인 ‘Society of Mind’를 이야기하지 않을 수도 없다. 이 책은 앞서 말한 ‘GÖdel, Escher, Bach’와는 또 완전히 다른 무엇이 들어있다.



신고
Trackback 0 Comment 1


티스토리 툴바