차례 SNU 4190.210 프로그래밍원리 (Principles of Programming) Part II Prof. Kwangkeun Yi 다음 데이타구현하기 (data implementation) 새로운타입의데이타 / 값구현하기 기억하는가 : 타입들 (types) τ ::= ι primitive type τ τ pair(product) type τ + τ or(sum) type τ τ ftn type, single param τ τ τ ftn type, multi params any type t user-defined type s name τ t user-defined type s name, with param ι ::= int real bool string symbol unit 새로운타입 (t 혹은 τ t) 의데이타구현해야
새로운데이타타입 새로운데이타타입구현하기 기본으로제공되는타입들 int, real, bool, string, symbol, unit 이아닌 소프트웨어마다새로운타입의데이타 / 값이필요 예 ) 짝, 집합, 리스트, 가지, 나무, 숲, 땅, 감정, 관계, 지식, 자동차, 목록표, 하늘, 바람, 원자, 분자, 세포, 뉴런, 책, 색깔, 종이, 건물, 층, 벽, 기둥, 사람, 테란, 젤-나가, 저그, 프로토스, 등등 기억하는가 : 모든프로그래밍언어에는각타입마다그타입의값을만드는식과사용하는식을구성하는방법이제공된다. 구현할새로운타입의데이터 / 값에대해서도 만드는 (introduction, construction) 방법과 사용하는 (elimination, use) 방법을함수로구현해서사용하면된다. 새로운데이타타입구현하기 예 ) 짝 (pair) τ τ 새로운타입을 τ 라고하면 만들기함수들의타입은 τ 사용하기함수들의타입은 τ 사용하기그함수들의구현 : (define pair cons) (define l car) (define r cdr) pair : τ τ τ τ l : τ τ τ r : τ τ τ
예 ) 리스트 (list) τ list 예 ) 두갈래가지구조 (binary tree) τ bintree 사용하기 empty : τ list link : τ τ list τ list leaf : τ τ bintree node-l : τ τ bintree τ bintree node-r : τ τ bintree τ bintree node-lr : τ τ bintree τ bintree τ bintree 그함수들의구현 : (define empty ()) (define is-empty? null?) (define link pair) (define fst l) (define rest r) is-empty? : τ list bool fst : τ list τ rest : τ list τ list 사용하기 node-val : τ bintree τ is-leaf? : τ bintree bool is-ltree? : τ bintree bool is-rtree? : τ bintree bool is-lrtree? : τ bintree bool l-subtree : τ bintree τ bintree r-subtree : τ bintree τ bintree 그함수들의구현 : (define (leaf x) (pair leaf x)) (define (node-l x t) (pair r (pair x t))) (define (node-r x t) (pair l (pair x t)))... 예 ) 두갈래가지구조 (binary tree) τ bintree empty : τ bintree node : τ τ bintree τ bintree τ bintree 사용하기 node-val : τ bintree τ is-empty? : τ bintree bool l-subtree : τ bintree τ bintree r-subtree : τ bintree τ bintree 그함수들의구현 : (define empty empty) (define (node x lt rt) (pair x (pair lt rt))) (define (node-val t)...) (define (is-empty? t)...)... 예 ) 일반가지구조 (tree) τ tree empty : τ tree node : τ (τ tree) list τ tree 사용하기 node-val : τ tree τ is-empty? : τ tree bool num-subtrees : τ tree int nth-subtree : τ tree int τ tree 그함수들의구현 : (define empty empty) (define (node x trees) (pair x trees) (define (node-val t)...) (define (is-empty? t)...) (define (nth-subtree t n)...)
데이타타입구현이슈들 하나의테이타타입에대해서 여러버전가능 : 만들기 / 사용하기함수들의기획 leaf, node-l, node-r, node-lr node-val, is-leaf?, is-rtree?, is-ltree?, is-lrtree? l-subtree, r-subtree 9 8 >= >< >; v.s. >: empty, node node-val, is-empty? l-subtree, r-subtree 여러버전가능 : 만들기 / 사용하기함수들의구현 (define empty A) (define empty ㄱ ) (define node B) (define node ㄴ ) (define node-val C) v.s. (define node-val ㄷ ) (define l-subtree D) (define r-subtree E) (define l-subtree ㄹ ) (define r-subtree ㅁ ) 데이타타입기획과구현원리 새로운데이타타입의구현은만들기 (introduction) 함수와사용하기 (elimination) 함수들을정의하면된다. 이때, 만들기 / 사용하기함수들의기획은드러내고구현은감추어서, 외부에서는기획이드러낸 (interface, 겉 ) 내용만이용해서프로그램을작성하도록한다. 기획을작성하는언어 : 이름, 타입, 하는일}{{}}{{} 프로그래밍언어자연어, 수학 기획 (interface) 과구현 (implementation) 은독립적으로 : 데이터속구현감추기 (data abstraction) 다음 데이타속구현감추기 (data abstraction) 분리 : 외부와데이타구현의속내용 외부에알릴것. 변하지말것. (interface) / 사용하기함수들의기획 : 이름, 타입, 하는일 외부에서는만들기 / 사용하기함수들만이용하기 외부에알리지말것. 변해도될것. (implementation) 만들기 / 사용하기함수들의구현 장점 : 외부는데이터구현과무관 데이타구현변경과외부사용코드변경이독립됨 데이타구현과외부사용프로그래밍동시진행가능
예 ) 짝 τ τ 기획 (interface) pair : τ τ τ τ l : τ τ τ r : τ τ τ 구현은기획에맞기만하면다양하게가능 안 1: cons, car, cdr 안 2: lambda 외부사용 (define (leaf x) (pair leaf x)) (define (node-l x t) (pair r (pair x t))) (define (node-r x t) (pair l (pair x t))) (define (l-subtree t) (if (equal (l t) l) (r (r t)))) (define (r-subtree t) (if (equal (l t) r) (r (r t)))) 예 ) 두갈래가지구조 (tree) τ bintree 기획 (interface) empty : τ bintree node : τ τ bintree τ bintree τ bintree node-val : τ bintree τ is-empty? : τ bintree bool l-subtree : τ bintree τ bintree r-subtree : τ bintree τ bintree 외부사용 (node 10 (node 8 (node 5 empty empty) (node 9 empty empty)) empty) (node 1 empty (node 2 empty (node 3 empty empty))) (define (traverse t) (if (is-empty? t) () (begin (print (node-val t)) (traverse (l-subtree t)) (traverse (r-subtree t))) )) 연습 : 데이터구현하기 + 속구현감추기 다음 대수식 (algebraic expression) 데이터 미분함수 (symbolic differentiation) diff : ae string ae 부분계산함수 (partial evaluation) eval : ae string real ae
여러구현동시지원 : 예 ) 복소수데이타 표면 단계 기획 (interface) 외부사용 make-from-real-imag : real real complex make-from-mag-angle : real real complex is-complex? : bool real : complex real imag : complex real mag : complex real angle : complex real add-complex : complex complex complex mul-complex : complex complex complex 여러구현동시지원 : 예 ) 복소수데이타 한가지방식만구현한경우 (define (make-from-real-imag r i)...) (define (make-from-mag-angle m a)...) (define (is-complex? x)...) (define (real x)...) (define (imag x)...) (define (mag x)...) (define (angle x)...) 여러구현동시지원 : 예 ) 복소수데이타 예 ) 복소수데이타구현 A 두가지방식의구현을같이이용하는경우 rectangular representation 기획 (interface) (define (make-from-real-imag r i)...) (define (make-from-mag-angle m a)...) (define (is-complex? x)...) (define (real x)...) (define (imag x)...) (define (mag x)...) make-from-real-imag-rectangular : real real complex make-from-mag-angle-rectangular : real real complex is-rectangular? : complex bool real-rectangular : complex real imag-rectangular : complex real mag-rectangular : complex real angle-rectangular : complex real (define (angle x)...)
예 ) 복소수데이타구현 B 여러구현방식을지원할때의원리 polar representation 기획 (interface) make-from-real-imag-polar : real real complex make-from-mag-angle-polar : real real complex is-polar? : complex bool real-polar : complex real imag-polar : complex real mag-polar : complex real angle-polar : complex real 데이터속구현감추기 (data abstraction) 원리를유지한다. 즉, 각구현방식마다만들기와사용하기함수를제공한다. 단, 그함수들의이름이다른구현방식과구별되게한다. 그리고, 표면 단계의만들기와사용하기함수들을아랫단계의여러구현방식들을이용해서정의한다. 새로운구현방식도사용하도록확장하려면? 같은원리로 : 새로운구현방식을첨가 / 삭제하기더쉬운방 법? 표면 단계의함수들모두를매번변경해주는번거로움 : (define (real x) (cond ((is-rectangular? x) (real-rectangular x)) ((is-polar? x) (real-polar x)) ((is-xyz? x) (real-xyz x)) (else (error)))) 그리고, 바꿀것은? 표면 단계의만들기와사용하기함수들 : make-from-real-imag,, angle, is-complex? (define (angle x) (cond ((is-rectangular? x) (angle-rectangular x)) ((is-polar? x) (angle-polar x)) ((is-xyz? x) (angle-xyz x)) (else (error)))).
새로운구현방식을첨가 / 삭제하기더쉬운방법? 2차원의함수테이블사용. ( 테이블은변할수있는물건으로 ) 가로 : 함수이름태그 ( real, imag, 등등 ) 다음 세로 : 구현방식태그 ( rectangular, polar, 등등 ) real imag rectangular real-rectangular imag-rectangular polar real-polar imag-polar xyz real-xyz imag-xyz 새로운구현방식? 해당함수들을테이블에등록 표면 의함수들은고정됨 두개의태그 ( 함수이름, 구현방식 ) 로테이블에서 가져온다 (define (real x) ((lookup ftn-tbl real (rep-tag x)) x)) (define (imag x) ((lookup ftn-tbl imag (rep-tag x)) x)). 계층별로속구현감추기원리 여러구현방식을지원할때의원리와같다 : 데이터속구현감추기 (data abstraction) 원리를유지한다. 즉, 각구현방식마다만들기와사용하기함수를제공한다. 단, 그함수들의이름이다른구현방식과구별되게한다. 그리고, 표면 단계의만들기와사용하기함수들을아랫단계의여러구현방식들을이용해서정의한다.