최고 엔지니어의 꿈을 향해서

import java.util.Stack;

public class Fibonacci {
  
private int nr;
  
private Stack<Frame> kr;
   private int vr;
   public Fibonacci(int nr, Stack<Frame> kr) {
      this.nr = nr;
      this.kr = kr;
}

public static void main(String[] args) {
   Fibonacci fib =
new Fibonacci(20,new Stack<Frame>());
   System.
out.println("Result = " + fib.run(true));
}

public int run(boolean loop1) {
while(true) {
   if(loop1) {
      
if(nr <= 1) {
         
vr = nr;loop1 = false;
         
continue;
       }
else {
         
kr.push(new Frame"K1",nr));
         
nr--;
         
continue;
        }
       }
else {
         
if (kr.empty()) {
           
return vr;
          }
else {
              Frame fr =
kr.pop();
           
if (fr.first.equals("K1")) {
              
nr = fr.second - 2;
              
kr.push(new Frame("K2", vr));
               loop1 =
true;
              
continue;
              }else
{
                 
vr = fr.second + vr;
                 
continue;
              }
           }
       }
   }
  }
}

public
class Frame {
    String first
;
   
int second;
  Frame(String first,
int second) {
   
this.first = first;
   
this.second = second;}
}

----------------------------------------------------------------------------------
Java로 구현한 피보나치 수열 함수 이다.
Continluation Passing Style (CPS) 을 이용하여 구현했다.
코드에는 CPS에 관련된 extra argument가 없지만 (일반적으로 K) 사실은
CPS를 이용하여 구현한 후에 Registerizing을 하여, 파라메터를 넘기는 대신,
멤버변수 3개를 선언한 후 처리하였다.

저런 코드를 탄생(?) 시키기 위해서는, 먼저 Scheme 같은 언어로 내가 구현하고자 하는
문제를 해결한 후, 그 코드를 CPS화 작업한다. CPS'ed 된 코드를 Registerizing혹은 trampolining같은 작업을 한후(필요에 따라), 그 코드를 자바나 씨나, 씨#이나 등등, 원하는 imperative language로 손쉽게 바꿀 수 있다.
저 작업을 하는 근본적인 이유는, 물론 다양하지만,
프로그래밍의 세계에서 어떤 문제를 해결하기 위해 종종 recursion을 사용하곤 한다.
recursion이 때로는 코드가 심플하고 구현하기가 쉬운 장점을 가지고 있는 반면,
함수호출시 스택문제와 시스템 스택을 사용하기 때문에, 프로그래머 입장에서 그 스택을 가지고 마음대로 지지고 볶고 하는 작업을 하기에는 무리가 따른다.
더군다나, 저 위의 피보나치 함수를 보면, 그 이외에도 단점이 있는데,
int fibonacci(int n) {
    if (n <= 1)
       return n;
    else return fibonacci(n - 1) + fibonacci(n -2);
}
이게 전형적인 피보나치 recursion version이다.
코드는 심플하지만, 양쪽 함수 호출에서 computation 중복이 여러번 일어난다.
함수 스택과 상관없이, computation중복은 성능면에서 저하를 가져온다.
그리하여, 피보나치 함수 의 경우에는, recursion을 사용하여 문제를 해결하는 것보다, for나 while을 이용한 iteration이 적합하다.
프로그래밍을 공부한 사람이라면, 손쉽게 iteration version을 만들수 있을것이다.
단순히 변수 3개정도 선언하여, for문을 돌면서, 각각 변수의 상태를 변화 시키는것이다.
참고로 이러한 방법은 dynamic programming이라 한다.
피보나치의 경우 iteration version을 만드는것이 어렵지 않다. 이유는, 함수 자체가 간단하기 때문이다. 그러나 어떠한 경우는, iteration version을 만드는경우가 매우 힘들고 어렵다.
간단히 말해서 Recursion -> iteration version을 만드는 것인데,
n-queens문제를 예를들면, 솔루션을 얻기위해 backtracking방법을 사용한다.
흔히 볼수 있는 n-queens코드는 recursion인데, iteration으로 바꾸려면, 머리좀 싸매야 한다.(쉽지는 않다).. 참고로 iteration version의 매우 옵티마이즈 된 코드는 제프소머즈가 작성한 것이 있는데, 관심있는 사람은 인터넷에서 검색해 보기 바란다.ㅋ

결국 recursion을 iteration으로 바꿀 수 있는 일반적인 방법이 없을까?
바로 앞에서 설명했듯이,
CPS스타일로 코드를 바꾼후에 작업하면, 한결 수월해 진다.

CPS의 목적은 다양하지만, 또다른 장점으로는, 사용자 스택을 이용하기 때문에,
Reversible Computing의 한 예인, Undo, Redo를 구현할 경우도 용이하다.
객체지향세계에서 물론 디자인패턴중에 Undo같은 작업을 우아하게 구현할 수 있는 패턴이 있긴있다. 그러나 주의할것은 CPS를 이용하여 구현하는 것은 객체 구조가 아니라 (CPS와 객체지향이랑은 전혀 무관), 함수 인자 하나를 추가하여 (인자는 사용자 스택을 의미) 코드수준으로 처리한다. 씨나 파이쓴이나 등등의 일반적인 절차지향의 언어에서도 구현할 수 있다.

그러면, 저 코드가 어떻게 탄생했는지는 지금부터 알려드리겠다.
(define nr '*)
(define kr '*)
(define vr '*)

(define fib-top-ri
  (lambda (n)
    (set! nr n)
    (set! kr '())
    (fib-cps-ri)))

;;;;;;;;;;;;;;;;;;;;;Data structural representation;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define make-init
  (lambda ()
    '()))

(define fib-cps-ri
  (lambda () ;; nr kr
    (if (<= nr 1)
        (begin
          (set! vr nr)
          (apply-k))
        (begin
          (set! kr (list 'K1 nr kr))
          (set! nr (- nr 1))
          (fib-cps-ri)))))

(define apply-k
  (lambda () ;; kr vr
    (cond
      [(null? kr) vr]
      [(eq? (car kr) 'k1)
       (set! nr (- (cadr kr) 2))
       (set! kr (list 'K2 vr (caddr kr)))
       (fib-cps-ri)]
      [(eq? (car kr) 'K2)
       (set! vr (+ (cadr kr) vr))
       (set! kr (caddr kr))
       (apply-k)])))
이것은 CPS'ed 된 Scheme코드를 Registering한 코드 인데, 저 단계가 마지막 단계에 속한다.
저 코드를 가지고 Java코드로 바꾸었다.

그럼 저 Registerized된 코드가 나오기 위해선 CPS된 코드와 함수의 기본정의, Representation Independent된 코드가 필요하다.

(define fib
  (lambda (n)
    (if (<= n 1)
        n
        (+ (fib (- n 1)) (fib(- n 2))))))   ;;; 피보나치 함수의 기본 정의

(define fib-top
  (lambda (n)
    (fib-cps n (lambda (v) v))))       ;;; CPS 함수 콜을 위한 기본 드라이버

(define fib-cps
  (lambda (n k)
    (if (<= n 1)
        (k n)
        (fib-cps (- n 1) (lambda (v) (fib-cps(- n 2) (lambda (w)
                                                       (k (+ v w)))))))))             ;;; CPS버젼의 피보나치 함수



 ;;; CPS 함수 콜을 위한 기본 드라이버 Representation Independent
(define fib-top-ri
  (lambda (n)
    (fib-cps-ri n (make-init))))
 

;;; CPS버젼의 피보나치 함수 Representation Independent
(define fib-cps-ri
  (lambda (n k)
    (if (<= n 1)
        (apply-k k n)
        (fib-cps-ri (- n 1) (make-rec-k1 n k)))))

;;; Representation Independent
(define make-rec-k1
  (lambda (n k)
    (lambda (v)
      (fib-cps-ri (- n 2) (make-rec-k2 v k)))))

;;; Representation Independent
(define make-rec-k2
  (lambda (v k)
    (lambda (w)
      (apply-k k (+ v w)))))

;;; Representation Independent
(define make-init
  (lambda ()
    (lambda (v) v)))

;;; Representation Independent for apply-k
(define apply-k
  (lambda (k v)
    (k v)))

;;; 위의 Functional representation 한것들을 Data structural representation으로 바꾼다..
(ps: functional language 가 아닌 일반 우리가 흔히 쓰는 랭귀지들은 스택을 List 등등으로 표현하기 때문에)
;;;;;;;;;;;;;;Data structural representation;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define make-init
  (lambda ()
    '()))

(define fib-cps-ri
  (lambda (n k)
    (if (<= n 1)
        (apply-k k n)
        (fib-cps-ri (- n 1) (list 'k1 n k)))))

(define apply-k
  (lambda (k v)
    (cond
      [(null? k) v]
      [(eq? (car k) 'k1)
       (fib-cps-ri (- (cadr k) 2) (list 'k2 v (caddr k)))]
      [(eq? (car k) 'k2)
        (apply-k (caddr k) (+ (cadr k) v))])))

이게 필요한것의 전부이다.
Data structural representation 코드부분을 registerizing한 코드는 맨 위에 적었다.
만약, 로컬 변수를 사용하지 않고, 함수 인자로 넘겨서 처리하고 싶으면, registerizing안해도 된다.

자 이방법을 이용하면, 재귀 버젼의 함수를 비재귀 버젼의 함수로 손쉽게 바꿀 수 있다.

Posted by 정해권 Trackback 0 Comment 0


티스토리 툴바