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

피보나치, 하노이에 이어서...
간단한 덧셈, 곱셉, 누승을 구하는 함수 3개를 구현해보자..

일단.. 세개의 함수에 대해 각각 recursion버젼으로 정의 해 보았다.


public class Operation_recursion {
 
 public static void main(String[] args) {
  System.out.println("Result = " + multiply(6,5));
  System.out.println("Result = " + pow(2,5));
 }
 
 public static int add(int n, int m) {
  if(n == 0)
   return m;
  else
   return add(n-1, m+1);
 }
 
 public static int multiply(int n, int m) {
  if(n == 0)
   return 0;
  if(n == 1)
   return m;
  else
   return add(m, multiply(n-1, m));
 
 }
 
 public static int pow(int n, int m) {
  if(m == 0) return 1;
  if(m == 1) return n;
  return multiply(n, pow(n, m-1));
 }
}

결과값
Result = 30
Result = 32

----------------------------------------------------------------------------------------
코드를 보면 각각 함수가 재귀로 구현되어 있으며, 재귀함수 인자안에 또다른 재귀 함수를 호출하고 있다.
물론 실제 프로그램을 작성할때 저렇게 정의 하지는 않겠지만, 복잡한 recursion이 있다고 간주하기 위하여 작성하였다.
그럼 저런 복잡한 재귀를...필요에 의해 iteration버젼으로 바꾸어야 한다고 해보자.
(성능상의 이유, 프로그래머가 각각의 computation step을 컨트롤해야 할 필요가 있을때..등등등)

그럼 일단 저 위에 3개의 함수를 Scheme Code로 바꾸어 보고,
이전에 했던 CPS작업과 Registerizing작업을 해 보겠다.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;Basic definition of operation functions;;;;;;;;;;;;;;;;;;;;;;;;;

(define add
  (lambda (n m)
    (if (= n 0)
        m
        (add (- n 1) (+ m 1)))))

(define mul
  (lambda (n m)
    (cond
      [(= n 0) 0]
      [(= n 1) m]
      [else (add m (mul (- n 1) m))])))

(define pow
  (lambda (n m)
    (cond
      [(= m 0) 1]
      [(= m 1) n]
      [else (mul n (pow n (- m 1)))])))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;CPS'ed Version of operation functions;;;;;;;;;;;;;;;;;;;;;;;;

(define add-top
  (lambda (n m)
    (add-cps n m (lambda (v) v))))

(define add-cps
  (lambda (n m k)
    (if (= n 0)
        (k m)
        (add-cps (- n 1) (+ m 1) k))))

(define mul-top
  (lambda (n m)
    (mul-cps n m (lambda (v) v))))

(define mul-cps
  (lambda (n m k)
    (cond
      [(= n 0) (k 0)]
      [(= n 1) (k m)]
      [else (mul-cps (- n 1) m (lambda (v) (add-cps m v k)))])))

(define pow-top
  (lambda (n m)
    (pow-cps n m (lambda (v) v))))

(define pow-cps
  (lambda (n m k)
    (cond
      [(= m 0) (k 1)]
      [(= m 1) (k n)]
      [else (pow-cps n (- m 1) (lambda (v) (mul-cps n v k)))])))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Representation independent;;;;;;;;;;;;;;;;;;;

(define make-init-k
  (lambda ()
    (lambda (v) v)))

(define add-cps-ri
  (lambda (n m k)
    (if (= n 0)
        (apply-k k m)
        (add-cps-ri (- n 1) (+ m 1) k))))

(define mul-cps-ri
  (lambda (n m k)
    (cond
      [(= n 0) (apply-k k 0)]
      [(= n 1) (apply-k k m)]
      [else (mul-cps-ri (- n 1) m (make-mul-k1 m k))])))

(define make-mul-k1
  (lambda (m k)
    (lambda (v) (add-cps-ri m v k))))

(define pow-cps-ri
  (lambda (n m k)
    (cond
      [(= m 0) (apply-k k 1)]
      [(= m 1) (apply-k k n)]
      [else (pow-cps-ri n (- m 1) (make-pow-k1 n k))])))

(define make-pow-k1
  (lambda (n k)
    (lambda (v) (mul-cps-ri n v k))))

(define apply-k
  (lambda (k v)
    (k v)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Data structural representation;;;;;;;;;;;;
(define add-top
  (lambda (n m)
    (add-cps-ri n m '())))
 
(define mul-top
  (lambda (n m)
    (mul-cps-ri n m '())))
 
(define pow-top
  (lambda (n m)
    (pow-cps-ri n m '())))

(define add-cps-ri
  (lambda (n m k)
    (if (= n 0)
        (apply-k k m)
        (add-cps-ri (- n 1) (+ m 1) k))))

(define mul-cps-ri
  (lambda (n m k)
    (cond
      [(= n 0) (apply-k k 0)]
      [(= n 1) (apply-k k m)]
      [else (mul-cps-ri (- n 1) m (list 'mul-k1 m k))])))

(define pow-cps-ri
  (lambda (n m k)
    (cond
      [(= m 0) (apply-k k 1)]
      [(= m 1) (apply-k k n)]
      [else (pow-cps-ri n (- m 1) (list 'pow-k1 n k))])))

(define apply-k
  (lambda (k v)
    (cond
      [(null? k) v]
      [(eq? (car k) 'mul-k1)
       (add-cps-ri (cadr k) v (caddr k))]
      [(eq? (car k) 'pow-k1)
       (mul-cps-ri (cadr k) v (caddr k))])))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;Registerizing;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define nr '*)
(define mr '*)
(define kr '*)
(define vr '*)

(define add-top
  (lambda (n m)
    (set! nr n)
    (set! mr m)
    (set! kr '())
    (add-cps-ri)))

(define mul-top
  (lambda (n m)
    (set! nr n)
    (set! mr m)
    (set! kr '())
    (mul-cps-ri)))
 
(define pow-top
  (lambda (n m)
    (set! nr n)
    (set! mr m)
    (set! kr '())
    (pow-cps-ri)))

(define add-cps-ri
  (lambda () ;;nr mr kr
    (if (= nr 0)
        (begin
          (set! vr mr)
          (apply-k))
        (begin
          (set! nr (- nr 1))
          (set! mr (+ mr 1))
          (add-cps-ri)))))

(define mul-cps-ri
  (lambda () ;;nr mr kr
    (cond
      [(= nr 0)
      (set! vr 0)
      (apply-k)]
      [(= nr 1)
      (set! vr mr)
      (apply-k)]
      [else
        (begin
          (set! nr (- nr 1))
          (set! kr (list 'mul-k1 mr kr))
          (mul-cps-ri))])))

(define pow-cps-ri
  (lambda () ;;nr mr kr
    (cond
      [(= mr 0)
      (set! vr 1)
      (apply-k)]
      [(= mr 1)
      (set! vr nr)
       (apply-k)]
      [else
       (begin
        (set! mr (- mr 1))
        (set! kr (list 'pow-k1 nr kr))
        (pow-cps-ri))])))

(define apply-k
  (lambda () ;;kr vr
    (cond
      [(null? kr) vr]
      [(eq? (car kr) 'mul-k1)
       (set! nr (cadr kr))
       (set! mr vr)
       (set! kr (caddr kr))
       (add-cps-ri)]
      [(eq? (car kr) 'pow-k1)
       (set! nr (cadr kr))
       (set! mr vr)
       (set! kr (caddr kr))
       (mul-cps-ri)])))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
자 결국 변환과정을 거쳐서 Registerized된 스킴코드 마지막 부분을 얻게 되었다.
그럼 저 마지막 부분만 가지고 다시 자바 iteration 버젼의 함수로 만들어 보자.

Version 1 코드는 재귀가 남아있으며...사실 tail recursion 이기 때문에...내부적으로는
for 문이나 while문의 iteration과 별반 다를바가 없다.(컴파일러가 옵티마이져까지 해줄것이다, 안해준다고 쳐도..함수 호출 컨텍스트 스위치 비용만 부담되고, 시스템 스택 비용은 없다.)

import java.util.Stack;

public class Operation_iteration {
 private int nr;
 private int mr;
 private Stack<Frame> kr;
 private int vr;
 
 public Operation_iteration(int nr,int mr, Stack<Frame> kr) {
  this.nr = nr;
  this.mr = mr;
  this.kr = kr;
 }
 
 public static void main(String[] args) {
  Operation_iteration addCal = new Operation_iteration(5,5,new Stack<Frame>());
  Operation_iteration mulCal = new Operation_iteration(9,8,new Stack<Frame>());
  Operation_iteration powCal = new Operation_iteration(2,10,new Stack<Frame>());
  System.out.println("Result = " + addCal.add());
  System.out.println("Result = " + mulCal.mul());
  System.out.println("Result = " + powCal.pow());
 }
 
 public int add() {
  if(nr == 0) {
   vr = mr;
   return applyK();
  }
  else {
   nr--;
   mr++;
   return add();
  }
 }
 
 public int mul() {
  if(nr == 0) {
   vr = 0;
   return applyK();
  }
  else if(nr == 1) {
   vr = mr;
   return applyK();
  }
  else {
   nr--;
   kr.push(new Frame("mul-k1", mr));
   return mul();
  }
 }
 
 public int pow() {
  if(mr == 0) {
   vr = 1;
   return applyK();
  }
  else if(mr == 1) {
   vr = nr;
   return applyK();
  }
  else {
   mr--;
   kr.push(new Frame("pow-k1",nr));
   return pow();
  }   
 }
 
 public int applyK() {
  if (kr.empty()) {
   return vr;
  } else {
   Frame fr = kr.pop();
   if (fr.first.equals("mul-k1")) {
    nr = fr.second;
    mr = vr;
    return add();
   } else {
    nr = fr.second;
    mr = vr;
    return mul();
   }
  }
 }
}

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

이 코드를 돌리면 정확한 값이 나온다.
Result = 10
Result = 72
Result = 1024
-------------------------------------------------------------------------------
그럼 저 위의 코드를 완전한 버젼의 iteration 버젼으로 바꾸어 보자..
사실 이부분은 그냥 아무런 개념없이 여러 함수를 하나의 함수로 합치는 작업만 하면 되기 때문에 그렇게 어렵지 않으나...때로는 복잡해질수도 있다...(논리적으로 또 if문 for문을 집어 넣어야 하기 때문에)
이 복잡함을 피하려면 예전에 언급했던 trampolining 작업을 Registerizing하기 전에 해줘야 하는데..이부분은 나중에 설명하겠다.

import java.util.Stack;

public class Operation_iteration2 {
 private int nr;
 private int mr;
 private Stack<Frame> kr;
 private int vr;

 public Operation_iteration2(int nr, int mr, Stack<Frame> kr) {
  this.nr = nr;
  this.mr = mr;
  this.kr = kr;
 }

 public static void main(String[] args) {
  Operation_iteration2 addCal = new Operation_iteration2(8, 5,
    new Stack<Frame>());
  Operation_iteration2 mulCal = new Operation_iteration2(3, 24,
    new Stack<Frame>());
  Operation_iteration2 powCal = new Operation_iteration2(2, 4,
    new Stack<Frame>());
  System.out.println("Result = " + addCal.add(true));
  System.out.println("Result = " + mulCal.mul(true));
  System.out.println("Result = " + powCal.pow(true));
 }

 public int add(boolean loop1) {
  while (true) {
   if (loop1) {
    if (nr == 0) {
     vr = mr;
     loop1 = false;
     continue; // applyK call
    } else {
     nr--;
     mr++;
     continue; // add call
    }
   } else { // applyK definition
    if (kr.empty()) {
     return vr;
    } else {

     // it won't be here //
     /*
      * Frame fr = kr.pop(); if (fr.first.equals("mul-k1")) { nr =
      * fr.second; mr = vr; loop1 = true; continue;
      */
    }
   }
  }
 }

 public int mul(boolean loop1) {
  boolean loop2 = true;
  while (true) {
   if (loop1) {
    if (nr == 0) {
     vr = 0;
     loop1 = false;
     continue; // applyK call
    } else if (nr == 1) {
     vr = mr;
     loop1 = false;
     continue; // applyK call
    } else {
     nr--;
     kr.push(new Frame("mul-k1", mr));
     continue; // mul call
    }
   } else { // applyK definition
    if (kr.empty()) {
     return vr;
    } else {
     Frame fr = kr.pop();
     if (fr.first.equals("mul-k1")) {
      nr = fr.second;
      mr = vr;
      /////return add(true);////////////////////
      while (true) {
       if (loop2) {
        if (nr == 0) {
         vr = mr;
         loop2 = false;
         continue; // applyK call
        } else {
         nr--;
         mr++;
         continue; // add call
        }
       } else { // applyK definition
        if (kr.empty()) {
         return vr;
        } else {
         fr = kr.pop();
         if (fr.first.equals("mul-k1")) {
          nr = fr.second;
          mr = vr;
          loop2 = true;
          continue;
         }
        }
       }
      }
      ////////////////////////////////////////////
     } else {
      /* it won't be here */
     }
    }
   }
  }
 }
 

 public int pow(boolean loop1) {
  boolean loop2 = true;
  boolean loop3 = true;
  boolean loop4 = true;
  while(true) {
   if(loop1) {    // pow
    if(mr == 0) {
     vr = 1;
     loop1 = false;
     continue;
    }
    else if(mr == 1) {
     vr = nr;
     loop1 = false;
     continue;
    }
    else {
     mr--;
     kr.push(new Frame("pow-k1",nr));
     continue;
    }
   }
   else { // applyK
    if (kr.empty()) {
     return vr;
    } else {
     Frame fr = kr.pop();
     if (fr.first.equals("mul-k1")) {
      nr = fr.second;
      mr = vr;
      // return add(true);//
      while (true) {
       if (loop2) {
        if (nr == 0) {
         vr = mr;
         loop2 = false;
         continue; // applyK call
        } else {
         nr--;
         mr++;
         continue; // add call
        }
       } else { // applyK definition
        if (kr.empty()) {
         return vr;
        }
        else {
         loop2 = true; //
        }
       }
      }
     ///////////////////////////////////////////
     
     
     } else { // else if(fr.first.equals("pow-k1"))
      nr = fr.second;
      mr = vr;
      //return mul(true);///////////////
      loop3 = true;
      while (true) {   // mul
       if (loop3) {
        if (nr == 0) {
         vr = 0;
         loop3 = false;
         continue; // applyK call
        } else if (nr == 1) {
         vr = mr;
         loop3 = false;
         continue; // applyK call
        } else {
         nr--;
         kr.push(new Frame("mul-k1", mr));
         loop3 = true; //
         continue; // mul call
        }
       } else { // applyK definition
        if (kr.empty()) {
         return vr;
        } else {
         fr = kr.pop();
         if (fr.first.equals("mul-k1")) {
          nr = fr.second;
          mr = vr;
          /////return add(true);////////////////////
          while (true) {
           if (loop4) {
            if (nr == 0) {
             vr = mr;
             loop4 = false;
             continue; // applyK call
            } else {
             nr--;
             mr++;
             continue; // add call
            }
           } else { // applyK definition
            if (kr.empty()) {
             return vr;
            } else {
             fr = kr.pop();
             if (fr.first.equals("mul-k1")) {
              nr = fr.second;
              mr = vr;
              loop4 = true;
              continue;
             }
            }
           }
          }
          ////////////add////////////////////////////////
         }
        }
       }
      }
         
      ////////mul//////////////////////////
     }
    }
   }
  }
 }
}

class Frame {
 String first;
 int second;

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

///////////////////////////////////////////////////////////////////////
생각보다 복잡한 코드가 나왔다......
아 마지막 pow함수 버그 있는데 못잡겠다......일단 보류.......
사실 이것도 만만치는 않군요........이게 바로 시스템 스택 시뮬레이션 이다..
이거 이런 일련의 과정없이 첨부터 저런코드 만들기는 .....불가능이겠죠..

Posted by 정해권 Trackback 0 Comment 2


티스토리 툴바