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

;;;;;;;;;;;;;;;;;;;;Sudoku Solver;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;Abstract definition of basic functions;;;;;;;;;;;;

(define solutionnum 0)

(define getSolution
  (lambda (arrayList)
    (begin
      ; currentboardSolution.clear();
      (let ((solutionnum 0))
            (if (!checkValidity)
                (void)
                (tryRow arrayList 0))))))

(define tryRow
  (lambda (arrayList row)
    (if (< row BOARD_SIZE)
        (tryCell arrayList row 0)
        (begin
          (let* ((solutionnum (+ solutionnum 1)))
            ;; printBoard;;;;
            ;; currentBoardSolution.add(tem);;
            )))))

(define tryCell
  (lambda (arrayList row col)
    (if (< col BOARD_SIZE)
       (if (isEmpty arrayList row col)
           (tryWithValue arrayList row col 1)
           (tryCell arrayList row (+ col 1)))
        (tryRow arrayList (+ 1 row)))))

(define tryWithValue
  (lambda (arrayList row col n)
    (if (> n BOARD_SIZE)
        (void)
        (if (and (isEmpty arrayList row col) (noConflict arrayList n row col))
            (begin
              (setBoard arrayList row col n)
              (tryCell arrayList row (+ col 1))
              ;;arrayList[row][col] = 0;;
              (tryWithValue arrayList row col (+ n 1))
              )
            (tryWithValue arrayList row col (+ n 1))))))

;;;;;;;;;;;;;;;;;;;;;;;;CPSing;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define getSolution-top
  (lambda (arrayList)
    (getSolution-cps arrayList (lambda () (void)))))

(define getSolution-cps
  (lambda (arrayList k)
    (begin
      ;; currentboardSolution.clear();
      (let ((solutionnum 0))
        (if (!checkValidity)
            (k)
            (tryRow-cps arrayList 0 k))))))

(define tryRow-cps
  (lambda (arrayList row k)
    (if (< row BOARD_SIZE)
        (tryCell-cps arrayList row 0 k)
        (begin
          (let (solutionnum (+ solutionnum 1))
            ;; printBoard;;;
            ;; currentBoardSolution.add(tem);;
            )))))

(define tryCell-cps
  (lambda (arrayList row col k)
    (if (< col BOARD_SIZE
         (if (isEmpty arrayList row col)
             (tryWithValue-cps arrayList row col 1 k)
             (tryCell-cps arrayList row (+ col 1) k))
         (tryRow-cps arrayList (+ 1 row) k)))))

(define tryWithValue-cps
  (lambda (arrayList row col n k)
    (if (> n BOARD_SIZE)
        (k)
        (if (and (isEmpty arrayList row col) (noConflict arrayList n row col))
            (begin
              (setBoard arrayList row col n)
              (tryCell-cps arrayList row  (+ col 1) (lambda ()
                                                  ;; arrayList[row][col] = 0;
                                                  (tryWithValue-cps arrayList row col (+ n 1) k))))
            (tryWithValue-cps arrayList row col (+ n 1) k)))))

;;;;;;;;;;;;;;;;;;;;;;;;Representation independent;;;;;;;;;;;;;;;;;;;;;;;

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

(define getSolution-top-ri
  (lambda (arrayList)
    (getSolution-cps-ri arrayList (make-init-k))))

(define getSolution-cps-ri
  (lambda (arrayList k)
    (begin
      ;; currentboardSolution.clear();
      (let ((solutionnum 0))
        (if (!checkValidity)
            (apply-k k)
            (tryRow-cps-ri arrayList 0 k))))))

(define tryRow-cps-ri
  (lambda (arrayList row k)
    (if (< row BOARD_SIZE)
        (tryCell-cps-ri arrayList row 0 k)
        (begin
          (let (solutionnum (+ solutionnum 1))
            ;; printBoard;;;
            ;; currentBoardSolution.add(tem);;
            )))))

(define tryCell-cps-ri
  (lambda (arrayList row col k)
    (if (< col BOARD_SIZE
         (if (isEmpty arrayList row col)
             (tryWithValue-cps-ri arrayList row col 1 k)
             (tryCell-cps-ri arrayList row (+ col 1) k))
         (tryRow-cps-ri arrayList (+ 1 row) k)))))

(define tryWithValue-cps-ri
  (lambda (arrayList row col n k)
    (if (> n BOARD_SIZE)
        (apply-k k)
        (if (and (isEmpty arrayList row col) (noConflict arrayList n row col))
            (begin
              (setBoard arrayList row col n)
              (tryCell-cps-ri arrayList row  (+ col 1) (make-tryWithvalue-k1 arrayList row col n k)))
            (tryWithValue-cps-ri arrayList row col (+ n 1) k)))))

(define make-tryWithValue-k1
  (lambda (arrayList row col n k)
    (lambda ()
      ;; arrayList[row][col] = 0;
      (tryWithValue-cps-ri arrayList row col (+ n 1) k))))

(define apply-k
  (lambda (k)
    (k)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Change representation;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

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

(define make-tryWithValue-k1
  (lambda (arrayList row col n k)
    ;;  ;; arrayList[row][col] = 0;
    (list 'k1 arrayList row col n k)))

(define apply-k
  (lambda (k)
    (cond
      [(null? k) (void)]
      [(eq? (car k) 'k1)
       (begin
         ;; arrayList[row][col] = 0;
         (tryWithValue-cps-ri (cadr k) (caddr k) (cadddr k) (+ (caddddr k) 1) (cadddddr k)))])))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Registerized code;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define arrayListr '*)
(define kr '*)
(define solutionnumr '*)
(define rowr '*)
(define colr '*)
(define nr '*)

(define getSolution-top-ri
  (lambda (arrayList)
    (set! arrayListr arrayList)
    (set! kr '())
    (getSolution-cps-ri)))

(define getSolution-cps-ri
  (lambda () ;;arrayListr kr
    (begin
      ;; currentboardSolution.clear();
      (let ((solutionnum 0))
        (set! solutionnumr solutionnum)
        (if (!checkValidity)
            (apply-k)
            (set! rowr 0)
            (tryRow-cps-ri))))))

(define tryRow-cps-ri
  (lambda () ;;arrayListr rowr kr
    (if (< rowr BOARD_SIZE)
        (set! colr 0)
        (tryCell-cps-ri)
        (begin
          (set! solutionnumr (+ 1 solutionnumr))
          ;; printBoard;;;
          ;; currentBoardSolution.add(tem);;
          ))))

(define tryCell-cps-ri
  (lambda () ;;arrayListr rowr colr kr
    (if (< colr BOARD_SIZE)
         (if (isEmpty arrayListr rowr colr)
             (begin
               (set! nr 1)
               (tryWithValue-cps-ri)
               )
             (begin
               (set! colr (+ 1 colr))
               (tryCell-cps-ri)
               ))
        (begin
          (set! rowr (+ 1 rowr))
          (tryRow-cps-ri)))))

(define tryWithValue-cps-ri
  (lambda () ;;arrayListr rowr colr nr kr
    (if (> nr BOARD_SIZE)
        (apply-k)
        (if (and (isEmpty arrayListr rowr colr) (noConflict arrayListr nr rowr colr))
            (begin
              (setBoard arrayListr rowr colr nr)
              (set! colr (+ 1 colr))
              (set! kr (list 'k1 arrayList row col n k))
              (tryCell-cps-ri))
            (begin
              (set! nr (+ 1 nr))
              (tryWithValue-cps-ri))))))

(define apply-k
  (lambda () ;;kr
    (cond
      [(null? kr) (kr)]
      [(eq? (car kr) 'k1)
       (begin
         ;; arrayList[row][col] = 0;
         (set! arrayListr (cadr k))
         (set! rowr (caddr k))
         (set! colr (cadddr k))
         (set! nr (+ (caddddr k) 1))
         (set! kr (cadddddr k))
         (tryWithValue-cps-ri))])))

Fractal 알고리즘 중에서 Sierpinski Carpet을 선택해 보았다.

import java.awt.*;
import java.applet.*;
 
public class SierpinskiCarpet_recursion extends Applet {
    private Graphics g=null;
    private int d0=729; // 3^6
 
    public void init() {
        g=getGraphics();
        resize(d0,d0);
    }
 
    public void paint(Graphics g) {
        //  start recursion:
     drawSierpinskiCarpet ( 0, 0, getWidth(), getHeight() );
    }
 
    private void drawSierpinskiCarpet(int xTL, int yTL, int width, int height) {
        if (width>2 && height>2) {
            int w=width/3, h=height/3;
            g.fillRect ( xTL+w, yTL+h, w, h );
            drawSierpinskiCarpet ( xTL+0*w, yTL+0*h, w, h );
            drawSierpinskiCarpet ( xTL+(1/3)*w, yTL+1*h, w, h );
            drawSierpinskiCarpet ( xTL+(2/3)*w, yTL+2*h, w, h );
            drawSierpinskiCarpet ( xTL+1*w, yTL+0*h, w, h );
            drawSierpinskiCarpet ( xTL+(5/3)*w, yTL+2*h, w, h );
            drawSierpinskiCarpet ( xTL+2*w, yTL+0*h, w, h );
            drawSierpinskiCarpet ( xTL+(7/3)*w, yTL+1*h, w, h );
            drawSierpinskiCarpet ( xTL+(8/3)*w, yTL+2*h, w, h );
        }
    }
       
}

///////////////////////////////////////////////////////////////////////////////////
위의 코드는 자바 애플릿 인데, 실제 도형을 그려주는 drawSierpinskiCarpet함수가 핵심이다.
저 루틴을 Iteration버젼으로 바꿔보면 어떻게 될까? 사실 그냥 생각해서 할수 있지만, 계속 해오던대로
절차를 거쳐서 해보왔다.
저 함수를 For문으로 좀더 간략히 표현한다음 CPS를 거치면 훨씬 간단해 지지만, 그냥 있는그대로로
시도해 보았다. 결국 컨티뉴에이션이 많이 발생하기 때문에, 좀 코드가 쓸데없이 길어지는 문제가 있었다.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Original Scheme code;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define drawSierpinskiCarpet
  (lambda (xTL yTL width height)
    (if (or (<= width 2) (<= height 2))
        (void)
        (let* ((w (/ width 3))
               (h (/ height 3)))
          ;g.fillRect ( xTL+w, yTL+h, w, h );
          (drawSierpinskiCarpet xTL yTL w h)
          (drawSierpinskiCarpet (+ (* (/ 1 3) w) xTL) (+ yTL h) w h)   
          (drawSierpinskiCarpet (+ (* (/ 2 3) w) xTL) (+ yTL (* 2 h)) w h)  
          (drawSierpinskiCarpet (+ w xTL) yTL w h)   
          (drawSierpinskiCarpet (+ (* (/ 5 3) w) xTL) (+ yTL (* 2 h)) w h)  
          (drawSierpinskiCarpet (+ (* 2 w) xTL) yTL w h)   
          (drawSierpinskiCarpet (+ (* (/ 7 3) w) xTL) (+ yTL h) w h)   
          (drawSierpinskiCarpet (+ (* (/ 8 3) w) xTL) (+ yTL (* 2 h)) w h)))))
       
       

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;CPSed code;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define drawSier-top
  (lambda (xTL yTL width height)
    (drawSier-cps (xTL yTL width height (lambda () (void))))))

(define drawSier-cps
  (lambda (xTL yTL width height k)
    (if (or (<= width 2) (<= height 2))
        (k)
        (let* ((w (/ width 3))
               (h (/ height 3)))
          ;g.fillRect ( xTL+w, yTL+h, w, h );
          (drawSierpinskiCarpet xTL yTL w h
            (lambda () (drawSierpinskiCarpet (+ (* (/ 1 3) w) xTL) (+ yTL h) w h)
              (lambda () (drawSierpinskiCarpet (+ (* (/ 2 3) w) xTL) (+ yTL (* 2 h)) w h)
                (lambda () (drawSierpinskiCarpet (+ w xTL) yTL w h)
                  (lambda () (drawSierpinskiCarpet (+ (* (/ 5 3) w) xTL) (+ yTL (* 2 h)) w h)
                    (lambda () (drawSierpinskiCarpet (+ (* 2 w) xTL) yTL w h)
                      (lambda () (drawSierpinskiCarpet (+ (* (/ 7 3) w) xTL) (+ yTL h) w h)
                        (lambda () (drawSierpinskiCarpet (+ (* (/ 8 3) w) xTL) (+ yTL (* 2 h)) w h k)))))))))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;represent continuations using abstract datatype;;;;;;;;;;;;;;;;

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

(define apply-k
  (lambda (k)
    (k)))

(define drawSier-top-ri
  (lambda (xTL yTL width height)
    (drawSier-cps-ri (xTL yTL width height (make-init-k)))))

(define drawSier-cps-ri
  (lambda (xTL yTL width height k)
    (if (or (<= width 2) (<= height 2))
        (apply-k k)
        (let* ((w (/ width 3))
               (h (/ height 3)))
          ;g.fillRect ( xTL+w, yTL+h, w, h );;
          (drawSier-cps-ri xTL yTL w h (make-rec-k1 xTL yTL width height w h k))))))

(define make-rec-k1
  (lambda (xTL yTL width height w h k)
    (lambda ()
      (drawSier-cps-ri (+ (* (/ 1 3) w) xTL) (+ yTL h) w h (make-rec-k2 xTL yTL width height w h k)))))

(define make-rec-k2
  (lambda (xTL yTL width height w h k)
    (lambda ()
      (drawSier-cps-ri (+ (* (/ 2 3) w) xTL) (+ yTL (* 2 h)) w h (make-rec-k3 xTL yTL width height w h k)))))

(define make-rec-k3
  (lambda (xTL yTL width height w h k)
    (lambda ()
      (drawSier-cps-ri (+ w xTL) yTL w h (make-rec-k4 xTL yTL width height w h k)))))

(define make-rec-k4
  (lambda (xTL yTL width height w h k)
    (lambda ()
      (drawSier-cps-ri (+ (* (/ 5 3) w) xTL) (+ yTL (* 2 h)) w h (make-rec-k5 xTL yTL width height w h k)))))

(define make-rec-k5
  (lambda (xTL yTL width height w h k)
    (lambda ()
      (drawSier-cps-ri (+ (* 2 w) xTL) yTL w h (make-rec-k6 xTL yTL width height w h k)))))

(define make-rec-k6
  (lambda (xTL yTL width height w h k)
    (lambda ()
      (drawSier-cps-ri (+ (* (/ 7 3) w) xTL) (+ yTL h) w h (make-rec-k7 xTL yTL width height w h k)))))

(define make-rec-k7
  (lambda (xTL yTL width height w h k)
    (lambda ()
      (drawSier-cps-ri (+ (* (/ 8 3) w) xTL) (+ yTL (* 2 h)) w h k))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; change representation;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

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

(define drawSier-top-ri
  (lambda (xTL yTL width height)
    (drawSier-cps-ri (xTL yTL width height (make-init-k)))))

(define drawSier-cps-ri
  (lambda (xTL yTL width height k)
    (if (or (<= width 2) (<= height 2))
        (apply-k k)
        (let* ((w (/ width 3))
               (h (/ height 3)))
          ;g.fillRect ( xTL+w, yTL+h, w, h );;
          (drawSier-cps-ri xTL yTL w h (list 'k1 xTL yTL width height w h k))))))

;w = (cadddddr k)
;xTL = (cadr k)
;yTL = (caddr k)
;h = (caddddddr k)
;k = (cadddddddr k)

(define apply-k
  (lambda (k)
    (cond
      [(null? k) (void)]
      [(eq? (car k) 'k1)
       (drawSier-cps-ri
         (+ (* (/ 1 3) (cadddddr k) (cadr)) (+ (caddr) (caddddddr))
          (cadddddr) (caddddddr) (list 'k2 xTL yTL width height w h k)))]
      [(eq? (car k) 'k2)
       (drawSier-cps-ri
         (+ (* (/ 2 3) (cadddddr k)) (cadr k)) (+ (caddr k) (* 2 (caddddddr k)))
         (cadddddr k) (caddddddr k) (list 'k3 xTL yTL width height w h k))]
      [(eq? (car k) 'k3)
       (drawSier-cps-ri (+ (cadddddr k) (cadr k)) (caddr k)
         (cadddddr k) (caddddddr k) (list 'k4 xTL yTL width height w h k))]
      [(eq? (car k) 'k4)
       (drawSier-cps-ri
         (+ (* (/ 5 3) (cadddddr k)) (cadr k)) (+ (caddr k) (* 2 (caddddddr k)))
         (cadddddr k) (caddddddr k) (list 'k5 xTL yTL width height w h k))]
      [(eq? (car k) 'k5)
       (drawSier-cps-ri (+ (* 2 (cadddddr k)) (cadr k))
         (caddr k) (cadddddr k) (caddddddr k) (list 'k6 xTL yTL width height w h k))]
      [(eq? (car k) 'k6)
       (drawSier-cps-ri (+ (* (/ 7 3) (cadddddr k)) (cadr k)) (+ (caddr k) (caddddddr k))
         (cadddddr k) (caddddddr k) (list 'k7 xTL yTL width height w h k))]
      [(eq? (car k) 'k7)
       (drawSier-cps-ri (+ (* (/ 8 3) (cadddddr k)) (cadr k))
         (+ (caddr k) (* 2 (caddddddr k))) (cadddddr k) (caddddddr k) (cadddddddr k))])))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Registerizing;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define xTLr '*)
(define yTLr '*)
(define widthr '*)
(define heightr '*)
(define kr '*)
(define wr '*)
(define hr '*)

(define drawSier-top-ri
  (lambda (xTL yTL width height)
    (set! xTLr xTL)
    (set! yTLr yTL)
    (set! widthr width)
    (set! heightr height)
    (set! kr '())
    (drawSier-cps-ri)))

(define drawSier-cps-ri
  (lambda () ;; xTLr yTLr widthr heightr kr
    (if (or (<= widthr 2) (<= heightr 2))
        (apply-k)
        (let* ((w (/ widthr 3))
               (h (/ heightr 3)))
          (set! wr w)
          (set! hr h)
          ;g.fillRect ( xTL+w, yTL+h, w, h );; This is referred to as simple
          (drawSier-cps-ri xTLr yTLr wr hr (list 'k1 xTLr yTLr widthr heightr wr hr kr))))))

(define apply-k
  (lambda () ;;kr
    (cond
      [(null? kr) (void)]
      [(eq? (car kr) 'k1)
       (set! xTLr (+ (* (/ 1 3) (cadddddr kr)) (cadr kr)))
       (set! yTLr (+ (caddr kr) (caddddddr kr)))
       (set! widthr (cadddddr kr))
       (set! heightr (caddddddr kr))
       (set! kr (list 'k2 xTLr yTLr widthr heightr wr hr kr))
       (drawSier-cps-ri)]
      [(eq? (car kr) 'k2)
       (set! xTLr (+ (* (/ 2 3) (cadddddr kr)) (cadr kr)))
       (set! yTLr (+ (caddr kr) (* 2 (caddddddr kr))))
       (set! widthr (cadddddr kr))
       (set! heightr (caddddddr kr))
       (set! kr (list 'k3 xTLr yTLr widthr heightr wr hr kr))
       (drawSier-cps-ri)]
      [(eq? (car kr) 'k3)
       (set! xTLr (+ (cadddddr kr) (cadr kr)))
       (set! yTLr (caddr kr))
       (set! widthr (cadddddr kr))
       (set! heightr (caddddddr kr))
       (set! kr (list 'k4 xTLr yTLr widthr heightr wr hr kr))
       (drawSier-cps-ri)]
      [(eq? (car kr) 'k4)
       (set! xTLr (+ (* (/ 5 3) (cadddddr kr)) (cadr kr)))
       (set! yTLr (+ (caddr kr) (* 2 (caddddddr kr))))
       (set! widthr (cadddddr kr))
       (set! heightr (caddddddr kr))
       (set! kr (list 'k5 xTLr yTLr widthr heightr wr hr kr))
       (drawSier-cps-ri)]
      [(eq? (car kr) 'k5)
       (set! xTLr (+ (* 2 (cadddddr kr)) (cadr kr)))
       (set! yTLr (caddr kr))
       (set! widthr (cadddddr kr))
       (set! heightr (caddddddr kr))
       (set! kr (list 'k6 xTLr yTLr widthr heightr wr hr kr))
       (drawSier-cps-ri)]
      [(eq? (car kr) 'k6)
       (set! xTLr (+ (* (/ 7 3) (cadddddr kr)) (cadr kr)))
       (set! yTLr (+ (caddr kr) (caddddddr kr)))
       (set! widthr (cadddddr kr))
       (set! heightr (caddddddr kr))
       (set! kr (list 'k7 xTLr yTLr widthr heightr wr hr kr))
       (drawSier-cps-ri)]
      [(eq? (car kr) 'k7)
       (set! xTLr (+ (* (/ 8 3) (cadddddr kr)) (cadr kr)))
       (set! yTLr (+ (caddr kr) (* 2 (caddddddr kr))))
       (set! widthr (cadddddr kr))
       (set! heightr (caddddddr kr))
       (set! kr (cadddddddr kr))
       (drawSier-cps-ri)])))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
그럼 마지막 registerized 된 코드를 가지고 다시 자바 함수로 변환해 보겠다.

import java.awt.*;
import java.applet.*;
import java.util.Stack;

public class SierpinskiCarpet_iteration extends Applet {
    private Graphics g=null;
    private int d0=729; // 3^6
   
    private int xTLr;
 private int yTLr;
 private int widthr;
 private int heightr;
 private Stack<Frame> kr;
 private int wr;
 private int hr;
   
    public void init() {
        g=getGraphics();
        resize(d0,d0);
       
        ///////initialize
      
        kr = new Stack<Frame>();
               
    }
 
    public void paint(Graphics g) {
        //  start recursion:
        xTLr = 0;
        yTLr = 0;
        widthr = getWidth();
        heightr = getHeight();
       
        drawSierpinskiCarpet ();
    }
 
    private void drawSierpinskiCarpet() {
     if(widthr <=2 || heightr <=2) {
      applyK();
     }
     wr = widthr / 3;
     hr = heightr / 3;
     g.fillRect ( xTLr + wr, yTLr + hr , wr, hr);
     
     widthr = wr;
     heightr = hr;
     kr.push(new Frame("k1", xTLr, yTLr, widthr, heightr, wr, hr));
     drawSierpinskiCarpet();
     
    }
   
    public void applyK() {
     
     if(kr.empty()) return;
     Frame fr = kr.pop();
     if(fr.first.equals("k1")) {
      xTLr = (1 / 3) * fr.sixth + fr.second;
      yTLr = fr.third + fr.seventh;
      widthr = fr.sixth;
      heightr = fr.seventh;
      kr.push(new Frame("k2", xTLr, yTLr, widthr, heightr, wr, hr));
      drawSierpinskiCarpet();
     }
     else if(fr.first.equals("k2")) {
      xTLr = (2 / 3) * fr.sixth + fr.second;
      yTLr = fr.third + (2 * fr.seventh);
      widthr = fr.sixth;
      heightr = fr.seventh;
      kr.push(new Frame("k3", xTLr, yTLr, widthr, heightr, wr, hr));
      drawSierpinskiCarpet();
     }
     else if(fr.first.equals("k3")) {
      xTLr = fr.sixth + fr.second;
      yTLr = fr.third;
      widthr = fr.sixth;
      heightr = fr.seventh;
      kr.push(new Frame("k4", xTLr, yTLr, widthr, heightr, wr, hr));
      drawSierpinskiCarpet();
     
     }
     else if(fr.first.equals("k4")) {
      xTLr = (5 / 3) * fr.sixth + fr.second;
      yTLr = fr.third + (2 * fr.seventh);
      widthr = fr.sixth;
      heightr = fr.seventh;
      kr.push(new Frame("k5", xTLr, yTLr, widthr, heightr, wr, hr));
      drawSierpinskiCarpet();     
     }
     else if(fr.first.equals("k5")) {
      xTLr = (2 * fr.sixth) + fr.second;
      yTLr = fr.third;
      widthr = fr.sixth;
      heightr = fr.seventh;
      kr.push(new Frame("k6", xTLr, yTLr, widthr, heightr, wr, hr));
      drawSierpinskiCarpet();
 
     }
     else if(fr.first.equals("k6")) {
      xTLr = (7 / 3) * fr.sixth + fr.second;
      yTLr = fr.third + fr.seventh;
      widthr = fr.sixth;
      heightr = fr.seventh;
      kr.push(new Frame("k7", xTLr, yTLr, widthr, heightr, wr, hr));
      drawSierpinskiCarpet();
 
     }
     else if(fr.first.equals("k7")) {
      xTLr = (8 / 3) * fr.sixth + fr.second;
      yTLr = fr.third + (2 * fr.seventh);
      widthr = fr.sixth;
      heightr = fr.seventh;
      drawSierpinskiCarpet();
 
     }
    }
}

class Frame {
    String first;
    int second;
    int third;
    int fourth;
    int fifth;
    int sixth;
    int seventh;
   
    Frame (String first, int second, int third, int fourth, int fifth, int sixth, int seventh) {
        this.first = first;
        this.second = second;
        this.third = third;
        this.fourth = fourth;
        this.fifth = fifth;
        this.sixth = sixth;
        this.seventh = seventh;
    }
}

////////////////////////////////////////////////////////////
위에 꺼 버그..아직..고쳐야 하는데 어디선가 실수했나..일단 ..킵디스..

 
 
 

피보나치, 하노이에 이어서...
간단한 덧셈, 곱셉, 누승을 구하는 함수 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함수 버그 있는데 못잡겠다......일단 보류.......
사실 이것도 만만치는 않군요........이게 바로 시스템 스택 시뮬레이션 이다..
이거 이런 일련의 과정없이 첨부터 저런코드 만들기는 .....불가능이겠죠..

///////////////////////////////////////////////////////////////////////
public class Frame {
    private int n;
    private String from, to, spare;

    public Frame (int n, String from, String to, String spare) {
        this.n = n;
        this.from = from;
        this.to = to;
        this.spare = spare;
    }

    public int getN () { return n; }
   
    public String getFrom () { return from; }

    public String getTo () { return to; }

    public String getSpare () { return spare; }
}

///////////////////////////////////////////////////////////////////////
/////////////////////////////Hanoi Version 1///////////////////////////
// 하노이 버젼에서는 레지스터라이징을 사용하지 않았기 때문에, 함수 호출시 스택을 넘겨준다.
// 버젼 1은 여전히 재귀 함수를 쓰고는 있지만, 잘보면 Tail recursion or Tail call이다.
// 이것을 version2에서는 iteration버젼으로 바꾸었다.

import java.util.Stack;

public class Hanoi {

    public static void main (String[] args) {
        move(3,"start","end","spare");
    }

    public static void move (int n, String from, String to, String spare) {
        moveCps(n, from, to, spare, new Stack<Frame>());
    }

    public static void moveCps (int n, String from, String to, String spare, Stack<Frame> k) {
        while (n > 0) {
            Frame f = new Frame(n,from,to,spare);
            n = n-1;
            String temp = to;
            to = spare;
            spare = temp;
            k.push(f);
        }
        applyK(k);
    }

    public static void applyK (Stack<Frame> k) {
        if (k.empty()) return;
       
        Frame f = k.pop();
        System.out.printf("move from %s to %s%n", f.getFrom(), f.getTo());
        moveCps(f.getN()-1, f.getSpare(), f.getTo(), f.getFrom(), k);
    }
   
}
///////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

import java.util.Stack;

public class Hanoi2 {

    public static void main (String[] args) {
        move(4,"start","end","spare");
    }

    public static void move (int n, String from, String to, String spare) {
        moveCps(n, from, to, spare, new Stack<Frame>());
    }

    public static void moveCps (int n, String from, String to, String spare, Stack<Frame> k) {
        while (n > 0 || !k.empty()) {
            if (n > 0) {
                Frame f = new Frame(n,from,to,spare);
                n = n-1;
                String temp = to;
                to = spare;
                spare = temp;
                k.push(f);
            }
            else {
                Frame f = k.pop();
                System.out.printf("move from %s to %s%n", f.getFrom(), f.getTo());
                n = f.getN() - 1;
                from = f.getSpare();
                to = f.getTo();
                spare = f.getFrom();
            }
        }
    }

}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
아시다 시피, 위의 코드는 밑에 글에서 설명한데로 Scheme 코드를 거쳐 CPS한 후에 탄생되었다.
근데 내가 Hanoi scheme코드를 side effect있는 버젼(including printf(....))으로 시작했기 때문에, 결과값을 자료구조에 저장안하고, 걍 중간 중간 출력하는것을 볼수 있다...

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안해도 된다.

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