Lecture 8 복잡한 구조 프로그래밍 프로그램 짤 때의 마음가짐 invariant 데이터 구성 list pair value-oriented vs. object-oriented 데이터 구성 만드는 방법 + 사용하는 방법 + 속내용감추기

List ., 1-., 1-2-., 1-2-3-4-., 모든 List 는 . 이거나

typedef struct {int v; c *next;} node; 정수 List를 C로 구현 typedef struct {int v; node *next;} node; typedef node* list; list Null = 0; list link(int x; list l) { node *n; n = (node *)malloc(sizeof(node)); n->v = x; n->next = l; return n; } “리스트는 . 이거나” “있는 리스트에 하나 덧 붙인것” typedef struct {int v; c *next;} node;

List 만들기 link(1,Null); link(1,link(2,Null)); link(1,link(2,link(3,Null)));

List 사용하기 int head(list l) { if (isNull(l)) { printf(“no head of empty list.”); exit(1); } else return l->v; int rest(list l) { printf(“no rest of empty list.”); else return l->next;

List 주무르기 두개의 list를 붙이기 list append(list l1, list l2) { … } list를 뒤집기 list reverse(list l) {…} list의 원소들을 모두 합하기 int sum(list l) {…} list에서 원하는 원소만 가지고 list만들기 list filter(list l) {…}

프로그램 짤 때의 마음가짐 있는 것을 변화시키는 것으로? object-oriented imperative 있는 것은 변하지 않도록? value-oriented applicative

list를 불변하는 값으로 유지하기 list reverse(list l) { if (isNull(l)) {return l;} else if(isNull(rest(l))) {return l;} else { return append(reverse(rest(l)), link(head(l),Null) ); } list를 불변하는 값으로 유지하기

list를 변하는 물건으로 다루기 list reverse(list l) { list ans; if (isNull(l)) {return l;} else if(isNull(rest(l))) {return l;} else { ans = reverse(rest(l)); set_last_next(ans,l); l->next = Null; return ans; } list를 변하는 물건으로 다루기

int sum(list l) { if (isNull(l)) {return 0;} else {return (head(l) + sum(rest(l))); }

list를 불변하는 값으로 유지하기 list filter(list l) { if (isNull(l)) {return l;} else { if (isOk(head(l))) { return link(head(l), filter(rest(l))); } else return filter(rest(l)); } list를 불변하는 값으로 유지하기

list를 변하는 물건으로 다루기 list filter(list l) { if (isNull(l)) {return l;} else if(isOk(head(l))) { l->next = filter(rest(l)); return l; } else return filter(rest(l)); } list를 변하는 물건으로 다루기

Pair Pair = 두 값 혹은 두 물건의 쌍 (1,2), (1,(2,3)), (1,Nil), ((1,2),(1,”a”)), ((1,(Nil,3)),(2, (3,4))), … 임의의 구조를 표현할 수 있슴(!) list: (head, rest) 또는 Null 두갈래list: (r, (left, right)) 임의의갈래list: (r, list)

Pair를 C로 구현 typedef struct{char *fst; char *snd;} pair; pair *cons(char *fst, char* snd) { pair *n = (pair *)malloc(sizeof(pair)); n->fst = fst; n->snd = snd; return n; } char *fst(pair *p) {return p->fst;} char *snd(pair *p) {return p->snd;} char *Nil = 0; 모든것을 표현하는 방법: 포인터!

int *x, *y; pair *p; x = (int*)malloc(sizeof(int)); y = (int*)malloc(sizeof(int)); *x = 1; *y = 2; p = cons(x,y); p = cons(cons(x,y),cons(y,x)); p = cons(x,cons(y,cons(x,Nil))); p = cons(p,cons(p,Nil)); p = cons(link(1,(link(2,Null))),p);

다음의 구조를 만들자 1-2-3-4-. 1-. 1 1 3 2 2 4 3 5 6 6 4 5 1 2 3

pair에 매달리는 데이터의 종류를 구분할 방법이 있어야 typedef struct{char *fst; char *snd;} pair; char *fst(pair *p) {return p->fst;} char *snd(pair *p) {return p->snd;} char *Nil = 0; fst, snd가 Nil인지 아닌지? 방법이 있다 fst, snd가 pair인지 아닌지? 방법이 없다 모든것을 표현하는 방법: 포인터!

pair의 부품들이 어떤 물건인지? 0이 아니므로 pointer구나 4321 Nil이구나 … 이게 pair인지 다른것인지?

해결책: 꼬리표 만드는 모든 값/물건에 꼬리표를 단다 pair에 “pair”라는 꼬리표가 있다

pair의 구성원들이 어떤 물건인지? 4321 4321 … 0이 아니므로 pointer구나 pair Nil이구나 정수 이구나 4321 pair Nil이구나 4321 … int 정수 이구나

데이터의 표현 = 내가 구축하는/계산하는 세계의 설계 데이터의 표현 = 내가 구축하는/계산하는 세계의 설계 pair로 모든 임의의 구조물을 만들 수 있다. 좋아, pair를 가지고 구성할 값/물건들의 종류를 정해보자. 값/물건들의 타입(type)들: 예) Pair, Int, Car, Energy, … 각 타입들을 어떻게 표현할 지 정해보자. 구분을 위해서, 각 타입의 값/물건마다 꼬리표가 있어야 각 타입의 물건/값마다 부품들의 이름은 정해져 있어야 모든 타입의 물건/값마다 꼬리표의 이름은 같아야

내가 만들 세상의 물건/값들을 표현하는 방법을 정하자 내가 만들 세상의 물건/값들을 표현하는 방법을 정하자 typedef enum {Pair, Int, Car, Energy} type; typedef struct {type tag;} obj; tag typedef struct {type tag; obj *fst; obj *snd;} pair; fst snd typedef struct {type tag; int val;} integer; tag val tag typedef struct {type tag;int yr;int cc;int km;} car; yr cc km

꼬리표있는 pair 만들기와 사용하기 pair *make_pair(obj *fst, obj* snd) { pair *n = (pair *)malloc(sizeof(pair)); n->fst = fst; n->snd = snd; n->tag = Pair; return n; } char *fst(pair *p) {return p->fst;} char *snd(pair *p) {return p->snd;} char *Nil = 0;

꼬리표있는 int 만들기와 사용하기 integer *make_int(int z) { integer *n = (integer *)malloc(sizeof(integer)); n->val = z; n->tag = Int; return n; } int int_val(integer *z) {return z->val;}

모든 타입의 값/물건이 뒤섞일 수 있는 프로그램은 no make_pair(make_int(1), make_pair(make_int(2),Nil)); make_pair(make_pair(make_int(1),Nil), make_pair(Nil,make_int(2))); int sum_pair(pair *p) { /* fst(p) = Nil or Int or Pair or Car or … */ /* snd(p) = Nil or Int or Pair or Car or … */ if (fst(p) == Nil && snd(p) == Nil) {…} else if (fst(p) == Nil && snd(p) != Nil) {…} … else if (fst(p)->tag == Int && snd(p)->tag == Int) {…} else if (fst(p)->tag == Pair && snd(p)->tag == Pair) {…} too many cases: 모든 타입의 값/물건이 뒤섞일 수 있는 프로그램은 no 타입별로 계산과 데이터의 세계가 나누어져야 int list, car list, (int+car) list, int tree, (car+animal) list

binary int tree만들기와 사용하기

typedef pair* tree; tree empty_tree = Nil; tree make_leaf(int z) { return make_pair(make_int(z), empty_tree); } tree make_ltree(int z, tree t) { return make_pair(make_int(z), make_pair(t,empty_tree)); tree make_rtree(int z, tree t) { make_pair(empty_tree,t)); tree make_lrtree(int z, tree l, tree r) { return make_pair(make_int(z), make_pair(l,r));

tree root_val (tree t) { return t->fst; } tree left_tree(tree t) { if (t == empty_tree) {abort(“illegal tree.\n”);} else if (t->snd == empty_tree) {return empty_tree;} else {return t->snd->fst;} } tree right_tree(tree t) { else {return t->snd->snd;}

t1 = make_lrtree(5,make_leaf(3),make_leaf(8)); t2 = make_rtree(4, t1); (* * empty_tree: tree * make_ltree: int x tree -> tree * make_rtree: int x tree -> tree * make_lrtree: int x tree x tree -> tree *) tree t1, t2, t3; t1 = make_lrtree(5,make_leaf(3),make_leaf(8)); t2 = make_rtree(4, t1); t3 = make_lrtree(10,t1,t2);

int sum_tree(tree t) { if (t == empty_tree) {return 0;} else {return (root_val(t) + sum_tree(left_tree(t)) + sum_tree(right_tree(t)) ); }