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

#2

2009.11.07 02:14 : Computer Science/Web Tech

DB 기본적인 쿼리문을 복습하려다가....그 이전에 먼저 jsp를 개발할 수 있는 환경을 먼저 구축하는게 급선무이므로..

환경설정부터 해보자.

우선 jsp개발 환경 구축을 위해 필요한 프로그램들이 있다.

가장먼저 JDK를 설치하자..버젼은 1.6으로 하자. 최신버전.. 그다음
DB는 뭐...MySQL로 해도 되고.... 그냥 오라클로 하도록 하자.
10g Express Edition을 깔자..(클라이언트 수, 클러스터링 등의 제한이 있지만, 개인적인 용도는 적합하다.)

기본적으로 오라클은 1521포트를 사용한다. 알아두자.

깔고난뒤 도스 cmd창에서 sqlplus를 쳐보면 잘 설치 되었는지 안되었는지 확인할 수 있다..흠흠

그담, 이클립스도 깔고, (갈릴레오판으로 설치하자) 또 SQLGate 도 설치하자.....마지막으로 아파취톰캣도 설치한다.

다 설치 한후, 오라클은 기본적으로 8080 포트를 사용하기 때문에...톰캣의 포트를 변경해준다. (톰캣도 8080을 기본으로 사용한다). 그러나 이클립스로 개발할 것이기 때문에, 실제 톰캣의 포트를 변경할 필요 없이, 이클립스 내부의 톰캣포트를 변경 하면된다. (이클립스는 별도의 톰캣 환경 설정을 가지고 있다.  -> 이크립스는 별로의 파일로 관리한다.)

전체적으로 jsp를 개발하기 위한 환경 세팅은 다 되었다.

자 이제 본론으로 들어가자.

JSP 정말 간단하다. 대부분의 프로젝트는 DB와 연동되기 때문에 DB와 연결되는 클래스를 먼저 만들어 보자. 이 클래스를 나중에 JSP 페이지로 바꾸는것은 거의 복사 붙여넣기 수준에 지나지 않는다.

우선 디비 아이디와 패스워드를 web01로 통일하자.

import java.sql.Connection;
import java.sql.DriverManager;

public class ConnectionTest {

 public static void main(String[] args) {
  
  String url = "jdbc:oracle:thin:@127.0.0.1:1521:xe";
  String userName = "web01";
  String userPw = "web01";
  
  Connection con = null;
  
  try{
   Class.forName("oracle.jdbc.OracleDriver");
   
   con = DriverManager.getConnection(url,userName,userPw);
   
   System.out.println(con.getClass().getName());
   
   con.close();
   con = null;
   
  }catch(Exception e){
   e.printStackTrace();
  }finally{
   if(con != null){
    try {con.close();}catch(Exception e){}
   }
  }
 }
}

이 코드가 거의 베이직 형태이다.  이것으로 디비와 연결이 되는지 확인 할수있다.
위에 코드중, Class.forName("oracle.jdbc.OracleDriver"); 이 부분은 눈여겨 볼만한다. 자바 리플렉션 기능으로 스트링을 인자로 받아서 매칭되는 객체를 생성해 준다. 저렇게 하는 이유는 나중에 오라클 DB를 연동할지, SQLDB를 연동할지 모르기 때문에, 좀더 유연성 있는 코드를 마들어 내기위해, 스트링으로 나중에 전달받아, DB에 상관없이 코드를 사용할 수 있게 하기위해서다. 저 부분대신, import ~~오라클관련,,하고 new oracle~~~ 이런식으로 한다면 DB가 바뀔때마다 일일이 수정해야 하는 번거로움이 생긴다..

또 close() 의 부분을 눈여겨 보아야 하는데 코드를 잘 눈여겨보면, 어떤경우에라도 close()가 실행되도록 해놓았다.

일단 이코드의 전체적인 트라이캐치문 형태를 눈익혀 두고, 다음번에는 디비 테이블을 하나 만들어보자.






신고
Posted by 정해권 Trackback 0 Comment 0

웹개발 Review #1

2009.11.04 00:53 : 분류없음

우선 요즘 시대의 웹 플랫폼 위에서의 어플리케이션 개발이란 무엇인가? 라는 것을 생각해 볼 필요가 있다. 웹 초창기만 하더라도 웹기반의 개발을 중요치 않게 생각해 왔다. 그러나 현재 모바일 기기의 보편화, 성능 향상등 많은 부분에 있어 웹 플랫폼과의 연동이 빈번해 지는 추세 이므로, 웹 개발을 예전의 홈페이지 제작으로 그치는 수준이 아니라 다른 각도에서 바라보아야 한다. 지금껏 그래왔듯이, 향 후 웹 시장이 어떻게 변화될지 예측하는것은 매우 어렵다. 다만, 현재 시점에서 무엇이 가장 많이 쓰여지고, 과걱에서 어떻게 흘러왔는가를 알아보는것 만으로 의미가 있는 일이라 생각한다.

긴 설명 필요없이 간단히 말하면,
HTML 만으로 구성된 페이지가 CGI 를 통해 클라이언트와 서버사이의 의사소통 통로가 생기기 시작했다. 서버에서 별도의 프로세스를 가동시켜 클라이언트들의 요구를 수행하도록 설계된 모델이다. 이 후 좀더 좋은 퍼포먼스를 내기위한 통합된 언어의 필요성이 대두되었는데, php, asp, jsp 등 요즘 흔히 널리 쓰이는 것들이다. Ruby on rails 라던가 꽤 나온지 얼마 안된 언어들이 물론 있지만, 다 같은 컨셉이다. 언어 하나를 선택하여 개발해야 하는데, 현재 가장 널리 퍼져있는 언어가 자바 이기 때문에 jsp를 선택하도록 하겠다. asp는 이미 .net의 부진때문에 이미 많이 기울었다고 생각한다. 물론 나의 생각이다. php도 뭐 앞으로 그닥 선전하기는 힘들것 같다.

웹 영역에서도 새로운 기술들이 쏟아져 나오고 있는데, 요즘 스타일은 Web 2.0 , RIA 이다. 뭐 Flex, 실버라이트, JavaFX등 새로운 스타일의 기술들이 이미 퍼져가고 있는 시점이다.  이러한 기술들을 나중에라도 터득하기 위해서 우선 기본적인 웹 개발에 대해 알아보자.

jsp란 일단 쉽게 말해 html코드 + 자바 코드 이다.

언어 상관없이 웹 스크립트의 형태는 대부분

<
    DB연결 부분

    입력값 추출

    Query

    루프  ))-> 출력부분
 
    DB연결 해제
>
저런 구조이다.

일단 머리속으로 기억하고 있으면 코드 이해하기 쉬울것이다.
먼저 개발 환경을 구축하기 위해 DB를 설치 해야 하는데 오라클 Express Edition버젼을 깔아서 실습하는것이 편리하겠다. (클라이언트 수, 클러스터링 기능등 제한이 있지만 실습하는용으로 적합)

오라클을 설치하면 기본적으로 포트 1521번을 사용하게 된다.
디비를 설치한 후, 제대로 설치되었는지 확인하려면, 실행창에 cmd 입력한 후, sqlplus를 쳐보자. 거기에 사용자 Id/password를 입력해서 접속이 되면 잘 설치 된것이다.

웹개발을 하려면 일단 기본적인 DB는 다룰 줄 알아야 한다.
다음에는 기본적인 쿼리문등 공부를 해보도록 하자.

신고
Posted by 정해권 Trackback 0 Comment 0

얼마 전, Daum 기술시험을 보게되었는데, 섹션1, 2 로 구성되어 있었다. 1은 간단한 단답형, 리팩토링, 코드 결과값, SQL쿼리문 작성, Unix명령어 조합 등이였다. 섹션 2는 비중이 더 컸는데, 알고리즘 3문제 였다.
첫번째 알고리즘 문제는
정수값을 받으면 역순으로 리턴하는 함수 코드를 작성하는 것이였다. 배열, 메모리같은 것은 쓰지말라는 조건이 있었다.

ex) 입력 12345  출력 54321
     입력 2340    출력 432
     입력 541     출력 145

recursion으로 해결하려 했으나, 그냥 iteration으로 짜보았다. 먼저 정수형의 자릿수를 /10 연산으로 구한뒤 그 자릿수만큼 %10 으로 뒷자리를떼넨후 그 결과값에 10000,1000, 100, 10 등을 곱한후 총 결과를 더하면 역순이 나온다. 시험장에서 생각한거기 때문에 좋은알고리즘인지는 잘 모르겠다. ;;

문제 2번은 스트링 패턴 관련 문제가 나왔다
가령 abcdabc는 abc가 겹치므로 문자열 길이 3을 리턴
       abcdefef 는 ef가 있으므로 2리턴
       aaaaaa 는 aaa가 있으므로 3을 리턴

;;
관련 알고리즘을 모르면, 그냥  a부터 일일이 검사하고 b하고 ab하고 ㅋㅋ ;;;;;

세번째 문제는 선분에 점들이 있을때 가장 가까운 거리를 구하는 것인데 분할정복을 이용하여 해결하라는것이다.
이것은 데이타를 일단 반으로 확 쪼갠후에 ...검사를 한다. 점이 두개인지..두개면 뒤에서 앞에를 빼서 값을 저장한다.
아니면 개속 반토막 낸다. 주의할 점은 반토막 낼때..그 반토막 낼때의 경계값을 나중에 다시 한번 검사해줘야 한다는 것이다.

--3--56---10--

이렇게 점 4개가 있다면 답은 6-5 = 1 이 답인데..
두동강이 낼때 (3, 5)  (6, 10) 이렇게 내서 각각 빼면 2, 4 인데 여기서 min(2, 4) 하면 2가 나온다.
저기 최소값을 경계값 (5, 6)하고 비교를 한번 더 해주는것으로 알고리즘을 생각해 보았다.

Divide and Conquer의 주의점은, 데이타의 싸이즈만 줄이는 것인지, 싸이즈를 줄이면서 문제도 계속 해결해 나가는지, 싸이즈를 줄여나갈때 누수점은 없는지..등을 체크해 보아야 한다.


신고
Posted by 정해권 Trackback 0 Comment 0
알고리즘은 워낙 방대한 분야라서, 시간이 날때마다 조금씩 글을 올리도록 하겠다. 기본적으로 알고있어야 할 소팅, 서치 알고리즘부터 응용 알고리즘까지..다양하게 다뤄보도록 하겠다.

무엇보다 내가 생각하기엔, 테크닉적인 방법의 기억도 중요하지만, 기본이 되는 원리 이해부터 하는것이 중요하다고 생각한다.

알고리즘 영역에서 빠질 수 없는 기본적 컨셉들이 있는데 우선 Recursion에 대해 완벽히 이해 해야 할것이며, 그 다음으로 Divide and conquer, 깊이우선 탐색(DFS), Back tracking, Dynamic programming 등의 굵직한 개념 이해가 필요할 것이다. 이런 원리를 이해 한 후 텍스트 관련 알고리즘, 그래프 알고리즘, 프랙탈, 기하 관련 등등의 분야를 다루어 보면서 기본 알고리즘이 어떻게 응용되고 코딩되는지 하나하나 체득해 가는것이 중요하다.

물론 분야에 맞는 최적화된 알고리즘들은 대부분 인터넷에서 쉽게 찾아 활용할 수 있을것이다. 그러나 알고리즘을 직접 구현해 보고 연구해보면 기본적인 문제 해결력이 배양된다. 다양한 알고리즘을 구현해보다보면, (세일즈맨 문제, 가방채우기, nqueen문제 등등) 프로그래밍 실력도 향상될 뿐만 아니라, 새로운 문제에 직면했을때에도, 자세히 들여다보면, 기존 이미 알려진 문제와 흡사하다는 것을 깨닫고, 기존 학습한 방법으로 코딩을 할 수 있게 된다.

알고리즘을 너무 지루하게 생각하지 말고, 퍼즐 문제 푸는 것처럼 생각하면, 재미있어 진다. 알고리즘에 재미를 붙이기 위해 먼저 읽어 봐야 할 책들이 있다.

임백준 님이 지으신 씨리즈 모조리 다 읽어보면 좋다. 책이 너무 소설처럼 쓰여있어서, 정말 재밌다. 누워서 읽는 알고리즘부터 시작해서 요즘에 출간한 책들도 있을텐데 이름은 기억이 안난다.  책에서 다루어 지는 주제들이, 딱딱하지 않고 매우 이해하기 쉽고 재미있게 풀어 쓰셨다. 알고보니 인디애나 선배님 이셨다. 역시 ㅋㅋ

두번째는 생각하는 프로그래밍이다. 원제목은 Programming Pearls 2nd Edition 이고 존 벤틀리 형님께서 지으셨다. 실용적이면서 알아두면 좋을 만한 알고리즘을 다양한 분야에 걸쳐 소개 하고있다. 연습문제들도 있는데 다 풀수 있다면 진정한 geek으로 갈 수 있다. 공간과 속도의 반비례 관계를 잘 풀어서 설명하였다.

세번째는 한국에서 컴퓨터 공부하는 사람이라면 누구나 읽어본 C로 배우는 알고리즘 이재규 형님이 지으신 책이다. 자료구조 뿐만아니라 알고리즘에 대해 설명히 상당히 깔끔하고 잘 되어있다. 나도 지금까지 가장 많이 읽어본 책중에 하나인데, 공부 하면 할수록 이책 정말 잘 만들어 진 책같다.

네번째는 ACM 대비용으로 만들어진 Programming Challengers 라는 책이다. 문제 주고 코딩하라는 식으로 되어 있으며 해설지도 포함되어 있다. 이 문제를 하나하나 풀어보면, 정말 많은 도움이 되고 프로그래밍 신의 영역에 도달할 수 있다. 또한 카테고리별로 분류가 되어있어 나중에 쉽게 참조할 수도 있다.

이런책 외에도 다양한 명서들이 있지만 위에 책들은 부담없이 볼 수 있는 책들이라 소개하였다.

앞으로 하나하나 올려보도록 하겠다.


신고
Posted by 정해권 Trackback 0 Comment 0

웹에 많은 관심을 가지고 있었지만, 지금까지 웹 프로그래밍을 perl, jsp, php등으로 깔짝 대는 수준에 지나지 않았다. 지금부터 웹 언어중에 jsp를 깊숙히 학습해 보도록 하겠다.

신고
Posted by 정해권 Trackback 0 Comment 0


;;;;;;;;;;;;;;;;;;;;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))])))


신고
Posted by 정해권 Trackback 0 Comment 0

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;
    }
}

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


 
 
 

신고
Posted by 정해권 Trackback 0 Comment 0

피보나치, 하노이에 이어서...
간단한 덧셈, 곱셉, 누승을 구하는 함수 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

Hanoi Tower Problem

2008.11.15 19:04 : 분류없음

///////////////////////////////////////////////////////////////////////
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(....))으로 시작했기 때문에, 결과값을 자료구조에 저장안하고, 걍 중간 중간 출력하는것을 볼수 있다...

신고
Posted by 정해권 Trackback 0 Comment 0

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


티스토리 툴바