Generic Pointers란 무엇인가?

* 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다.

우리는 이전에 stack을 만들었는데 element type을 바꾸려면 우리는 매번 기존 stack을 copy해서 새로 만들어야 한다. 

이건 상당히 힘들고 귀찮은 일이다!

 

stack은 일반적으로 generic data structures라고 할 수 있다. 

- element type과 상관없이 항상 같은 방식으로 operate하며 element를 변경하지 않는다.

 

만약 stack을 generic library로 나타낼 수 있다면 다양한 element type에 따라 매번

stack을 새로 만들지 않아도 된다. 

-generic library : 어떤 type의 element에도 사용될 수 있는 single stack implementation

 

Attempt 1) generic type elem을 사용하여 client가 client interface에서 elem을 직접 define하도록 한다.

=>typedef _____ elem

장점: 어떠한 종류의 stack이라도 하나의 library로 관리 가능하다.

단점: 1. client application이 client definition file(typedef ___ elem이 들어가는 곳) 과 그 외 두가지로 나뉘어져야 한다. 

이걸 실제로 compile하게 될 경우 unnatural compilation pattern을 일으킨다. 

2. client application에서는 최대 1가지 타입의 stack만 가질 수 있게 된다. 

-같은 application에서 동시에 string stack과 int stack을 가질 수는 없다(elem type이 한번만 define되기 때문에)

 

이 단점을 해결할 수 있는 것이 c1이다. 

C1의 generic pointer에 대해 살펴보자. 

 

 

<void*>

C1에서 우리는 새로운 pointer type인 void*를 볼 수 있다. 

어떠한 pointer도 cast를 통해서 void* type으로 변환 시킬 수 있다. 

int* p = alloc(int);
*p = 7;
q = (void*)p; #q는 void* type이지만 p와 같은 주소를 공유한다.

# 다시 원래 type으로 
int* r = (int*)q; # r은 int*이지만 q와 같은 주소를 공유한다.

Casting을 통해서 우리는 specific pointer(ex-int*)를 generic pointer(void*)인것처럼 할 수 있다.

int* p;
p = alloc(int);
q = (void*)p; # void* casting을 통해 generic하게 만들었다. 
r = (int*)q; # int* casting을 통해 specific

void* pointer에서 가능한것과 불가능한것은 무엇일까?

Allowed	Not allowed
원래 type으로 다시 cast하기 ex) int*p = alloc(int);       void* q1 = (void*) p;       int* r = (int*) q1;	Dereference ex) void x = *q1; - void 자체가 "type"이 아니기에 dereference할 수가 없다.
비교하기 ex) void* q2 = (void*) alloc(int);       if (q1==q2) println("same");	allocate ex) void* q4 =  alloc(void); - 역시 void가 type이 아니기 때문이다.
다른 void* 변수에 assign하기 ex) void*q3 = q1;	원래 type이 아닌 다른 type으로 다시 cast하기 ex) println((string*)q1);

void*가 어떤 type으로든 cast가능 하다면 원래 type이 아닌 다른 type으로 다시 cast하는 것은 왜 안될까?

int main(){
   int* n = alloc(int);
   *n = 42;
   void* q = (void*) n;
   string*s = (string*) q;
   print(*s);
   return 0;
}

위 코드에서 볼 수 있듯이 s를 dereference하면 우리는 42(int)를 가지게 되지만 print에서는 string을 원한다.

-> safety violation

 

이때 발생하는 에러는 "untagging pointer failed"이다.

-void*는 꼬리표처럼 그 변수의 원래 type을 tag형태로 가지고 있다. 따라서 C1은 다시 원래 type으로 cast하기 전까지

tag가 맞는지 확인한다. 

 

\hastag

-annotation-only함수인 \hastag(tp, ptr)로 우리는 해당 generic pointer ptr이 tp타입을 가지는지 확인할 수 있다.

int main(){
   void* q;
   
   int* n = alloc(int);
   *n = 42;
   
   string* s = alloc(string);
   *s = "hello";
   
   q = (void*)n;
   //@assert \hastag(int*, q); #checks that q has tag int*
   printint(*(int*)q);
   
   q = (void*)s;
   //@assert \hastag(string*, q);
   //@assert !\hastag(int*, q);
   print(*(string*)q);
   
   return 0;
 }

\hastag는 void*에서 원래 type으로 cast back하기 전에 사용해야 한다.

 

NULL

NULL은 void*를 포함해서 모든 종류의 pointer이다.

-우리는 NULL을 자유롭게 casting할 수 있다.

int*p = NULL;
void*q = (void*)p;
string*r = (string*)q; #q가 NULL이면 어떤 type으로든 cast가능

-void* 타입의 NULL 변수는 모든 tag를 가지고 있다.

void*v = NULL;
//@assert \hastag(int*, v);
//@assert \hastag(string*, v);

//@assert \hastag(void*, v); # compilation error

casting하는 것이 unsafe할 수 있기 때문에 우리는 contract을 통해 safety를 확인해주어야 한다.

1) specific -> generic일 경우

- x가 이전에 tp*로 지정되어 있었을 경우 (void*)x 

-> //@ensures \hastag(tp*, \result);

 

2) generic->specific일 경우

-q가 (void*)인 (tp*)q

-> //@requires \hastag(tp*, q);

 

Generic Stacks

앞에서 보았던 generic stack구현 attempt 1에서 소개되었던 client interface에 void*를 elem타입으로 지정해보자

typedef void* elem;

장점: stack을 바꿀 필요가 없다.

단점: void*가 pointer여서 stack element도 pointer로 바꿔줘야 한다. 

 

int* stack을 generic하게 바꾼다고 생각해보자.

1) pushing할때 void*로 cast한다.

2) pop할때 다시 int*로 cast한다.

int main(){
   stack_t l = stack_new();
   
   int* x = alloc(int);
   *x = 42;
   void* p = (void*)x;
   push(l,p);
   
   int* y = alloc(int);
   *y = 15122;
   push(l, (void*)y);
   
   int*z = (int*)pop(l);
   printint(*z);
   
   printint(*(int*)pop(l));
   
   return 0;
}

두가지 다른 타입의 elem을 가진 stacks을 한 application에서 사용하기

int main(){
   stack_t l = stack_new();
   
   int* x = alloc(int);
   *x = 42;
   void* p = (void*)x;
   push(l,p);
   
   int*y = alloc(int);
   *y = 15122;
   push(l, (void*)y);
   
   int z = *(int*)pop(l);
   printint(z);
   printint(*(int*)pop(l));
   
   stack_t S = stack_new();
   
   string* s1 = stack_new();
   string* s1 = alloc(string);
   *s1 = "hello";
   push(S,(void*)s1);
   
   string*s = alloc(string);
   *s = "world";
   push(S,(void*)s);
   
   string w = *(string*)pop(S);
   println(w);
   println(*(string*)(pop(S)));
   
   return 0;
}