Mercurial > hg > Papers > 2012 > aplas
annotate paper/rectype.ind @ 51:bdbfe2a272ff
fix
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 16 Jun 2012 05:05:25 +0900 |
| parents | 1c9d41bb0c19 |
| children | 0cd49f4081e0 |
| rev | line source |
|---|---|
| 11 | 1 -title: Recursive type syntax in Continuation based C |
| 2 | |
| 32 | 3 \newcommand{\rectype}{{\tt \_\_rectype}} |
| 11 | 4 |
| 32 | 5 --author: Nobuyasu Oshiro, Shinji KONO |
| 11 | 6 |
| 7 --abstract: | |
| 32 | 8 |
| 11 | 9 We have implemented Continuation based C (CbC). |
| 10 CbC is an extension of C, which has parameterized goto statement. | |
| 11 It is useful for finite state automaton or many core tasks. | |
| 12 Goto statement is a way to force tail call elimination. | |
| 13 The destination of goto statement is called Code Segment, which is actually a normal function of C. | |
| 14 To represent recursive function call, the type system of C is not enough, because | |
| 15 it has no recursive types. | |
| 44 | 16 We introduce \rectype{} keyword for recursive type, and it is implemented in GCC-4.6.0. |
| 17 We will compare the conventional methods, \rectype{} keyword and a method using C structure. | |
| 11 | 18 Also we show usage of CbC and it's benchmark. |
| 19 | |
| 32 | 20 --Motivation |
| 21 | |
| 37 | 22 The C programming language is used in many practical programs, operating system |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
23 kernels, byte code machines, network servers or embedded systems. Low level feature |
|
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
24 of C is useful, but sometimes it requires programming hacks. For example, in case of |
| 37 | 25 byte code machine often entire program is a huge switch statement which has many |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
26 labels which correspond the byte codes. Operating system or network server has |
| 37 | 27 many layers such as system call dispatch, transport or presentation layer. It |
| 28 requires deep call levels, 2 or 3 for each layer, resulting 10-30 call levels. | |
| 32 | 29 |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
30 Continuation based C (CbC) provides a structured way to represent these situations. It |
|
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
31 is a small medication of C. It consists of a syntax to force tail-call-elimination |
|
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
32 and parameterized goto statement. |
| 37 | 33 |
| 45 | 34 Continuation has long history. Usually it means full copy of compuational evironment as in Scheme\cite{scheme}. Our continuation is a simple C function without environment because we have no stack in CbC. |
| 35 Using explicit stack, we can convert normal C program into CbC using CPS transformation\cite{cps}, | |
| 36 but we commit it's detail here. | |
| 37 | |
| 37 | 38 C has capable of recursive functions, but we find it's type system is not enough |
| 44 | 39 to represent CbC programming. In this paper, we introduce \rectype{} |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
40 keyword as a recursive type. To handle recursive type, conventionally tagged struct |
| 37 | 41 is used. It is also fit for CbC program. |
| 42 | |
| 44 | 43 We will describe the CbC and \rectype{} implementation of CbC on GCC 4.6.0. |
| 11 | 44 |
| 45 --Continuation based C | |
| 46 | |
| 28 | 47 CbC's basic programming unit is a Code Segment. It is not a subroutine, but it |
| 11 | 48 looks like a function, because it has input and output. We can use C struct |
| 49 as input and output interfaces. | |
| 50 | |
| 51 struct interface1 { int i; }; | |
| 52 struct interface2 { int o; }; | |
| 53 | |
| 54 __code f(struct interface1 a) { | |
| 55 struct interface2 b; b.o=a.i; | |
| 56 goto g(b); | |
| 57 } | |
| 58 | |
| 28 | 59 In this example, a Code Segment |
| 60 \verb+f+ has \verb+input a+ and sends \verb+output b+ to a Code Segment \verb+g+. | |
| 61 There is no return from Code Segment \verb+b+, \verb+b+ should call another | |
| 11 | 62 continuation using \verb+goto+. Any control structure in C is allowed in CwC |
| 63 language, but in case of CbC, we restrict ourselves to use \verb+if+ statement | |
| 64 only, because it is sufficient to implement C to CbC translation. In this case, | |
| 28 | 65 Code Segment has one input interface and several output interfaces (fig.\ref{code}). |
| 11 | 66 |
| 30 | 67 <center><img src="figure/code.pdf" alt="code"></center> |
| 11 | 68 |
| 69 | |
| 70 \verb+__code+ and parameterized global goto statement is an extension of | |
| 71 Continuation based C. Unlike \verb+C--+ \cite{cminusminus}'s parameterized goto, | |
| 72 we cannot goto into normal C function. | |
| 73 | |
| 28 | 74 In CwC, we can go to a Code Segment from a C function and we can call C functions |
| 75 in a Code Segment. So we don't have to shift completely from C to CbC. The later | |
| 11 | 76 one is straight forward, but the former one needs further extensions. |
| 77 | |
| 78 void *env; | |
| 79 __code (*exit)(int); | |
| 80 | |
| 81 __code h(char *s) { | |
| 82 printf(s); | |
| 83 goto (*exit)(0),env; | |
| 84 } | |
| 85 | |
| 86 int main() { | |
| 87 env = __environment; | |
| 88 exit = __return; | |
| 89 goto h("hello World\n"); | |
| 90 } | |
| 91 | |
| 92 In this hello world example, the environment of \verb+main()+ | |
| 93 and its continuation is kept in global variables. The environment | |
| 94 and the continuation can be get using \verb+__environment+, | |
| 28 | 95 and \verb+__return+. Arbitrary mixture of Code Segments and functions |
| 11 | 96 are allowed (in CwC). The continuation of \verb+goto+ statement |
| 97 never returns to original function, but it goes to caller of original | |
| 98 function. In this case, it returns result 0 to the operating system. | |
| 99 | |
| 100 | |
| 101 | |
| 14 | 102 --Recursive type syntax |
| 103 | |
| 37 | 104 A continuation is a pointer to a Code Segment to be executed after. |
| 105 For example, it is passed as follows; | |
| 14 | 106 |
| 107 __code csA( __code (*p)() ) { | |
| 108 goto p(csB); | |
| 109 } | |
| 110 | |
| 37 | 111 where {\tt p} is the continuation and {\tt csB} is a Code Segment which |
| 112 has the same type of {\tt csA}. This declaration is not enough because | |
| 113 it lacks the type of the argument. If add the type declaration, we | |
| 114 get following program; | |
| 14 | 115 |
| 37 | 116 __code csA( __code (*p)( __code (*)( __code (*)( __code (*)())))) { |
| 14 | 117 goto p(csB); |
| 118 } | |
| 119 | |
| 37 | 120 or |
|
26
680becde8c9f
modify coparison
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
25
diff
changeset
|
121 __code csA( __code (*p)( __code(*)())) { |
|
15
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
122 goto p(csB); |
|
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
123 } |
|
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
124 |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
125 It is enough to type {\verb+csB+}, but of course it is not completely will typed. |
| 37 | 126 Omitting types of the arguments of a function is allowed, but it requires |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
127 complex declaration and it is incomplete. |
|
15
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
128 |
| 44 | 129 We introduce \rectype{} syntax for this situation. In an argument deflation, |
| 130 \rectype{} represents it's function type. Using \rectype{}, previous example can | |
| 37 | 131 be written like this; |
| 11 | 132 |
| 133 __code csA( __rectype *p) { | |
| 134 goto p(csB); | |
| 135 } | |
| 136 | |
| 37 | 137 {\tt *p} has a type of {\tt csA} itself. |
| 138 | |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
139 The same situation is happen in conventional C, since Code Segment is a |
| 44 | 140 mere C function with tail-call-elimination. \rectype{} provides exact and |
| 37 | 141 concise way to describe recursive type. If we have extra arguments, |
| 142 | |
| 143 __code csBs(int a, __rectype *p) ; | |
| 144 | |
| 145 __code csAs(int a, __rectype *p) { | |
| 146 goto p(a, csBs); | |
| 147 } | |
| 148 | |
| 44 | 149 In this case, we have two \rectype{} keywords. It may points the same type or |
| 37 | 150 different types. There is no ambiguity here, because it point the exact |
| 151 position. If it points the same position in the same type declaration, | |
| 152 it is the same type. | |
| 153 | |
| 11 | 154 |
| 38 | 155 --Recursive type syntax in a function body |
| 11 | 156 |
| 44 | 157 \rectype{} can be appeared in a function arguments, a function body or struct definition as a |
| 38 | 158 pointer type, otherwise it errors. |
| 159 | |
| 160 In a function body, it has a type of the function itself. | |
| 161 | |
| 162 __code csAs(int a, __rectype *p) { | |
| 163 __rectype *p1 = p; | |
| 164 goto p1(a, csBs); | |
| 165 } | |
| 166 | |
| 167 It is possible to write the following way; | |
| 168 | |
| 169 __code csAs(int a, __rectype *p) { | |
| 170 __code (*p)(int, __retype *); | |
| 171 p1 = p; | |
| 172 goto p1(a, csBs); | |
| 173 } | |
| 11 | 174 |
| 38 | 175 but previous one is shorter. |
| 11 | 176 |
| 44 | 177 We cannot allow non pointer type \rectype{}, because it generates infinite size of object. |
| 38 | 178 |
| 179 In case of struct, | |
| 180 | |
| 181 struct { | |
| 182 int a; | |
| 183 __rectype *next; | |
| 184 } | |
| 185 | |
| 186 is the same of this; | |
| 187 | |
| 188 struct b { | |
| 189 int a; | |
| 190 struct b *next; | |
| 191 } | |
| 192 | |
| 193 this is a conventional way to represent recursive type in C. Using this technique we | |
| 194 can write a continuation like this; | |
| 13 | 195 |
| 196 struct interface { | |
| 197 __code (*next)(struct interface); | |
| 198 }; | |
| 199 | |
| 200 __code csA(struct interface p) { | |
| 201 struct interface ds = { csB }; | |
| 38 | 202 goto p.next(ds); } |
| 13 | 203 |
| 204 int main() { | |
| 205 struct interface ds = { print }; | |
| 206 goto csA(ds); | |
| 38 | 207 /* NOTREACHED*/ |
| 13 | 208 return 0; |
| 209 } | |
| 210 | |
| 44 | 211 \rectype{} is clearer but struct technique provides abstract representation. It requires |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
212 extra struct declaration, but it give us the same assembler output. |
| 13 | 213 |
| 214 __code fibonacci(__rectype *p, int num, int count, int result, int prev) | |
| 215 | |
| 216 | |
| 44 | 217 --How to implement \rectype{} |
| 11 | 218 |
| 45 | 219 \rectype{} syntax is implemented as a GCC's AST (Abstract Syntax Tree). |
| 220 A function type has tree lists of its argments and its return type. | |
| 221 In \verb+__code+ case, return type is void. | |
| 222 When we find \rectype{}, which is as pointer to the function, a pointer type node | |
| 223 is created (Fig.\ref{fig:tree1}). | |
| 224 Normaly the type node has a pointer to function type, but | |
| 225 we put a pointer to the parent function itself (Fig.\ref{fig:tree2}). | |
| 226 | |
| 227 It looks like a normal function type and works fine except type comparison, which | |
| 228 falls into an infinite loop. In order to stop type loop, we introduce \rectype{} flag | |
| 229 in the type node. A type comparison was simply stopped when it met \rectype{} flag. | |
| 24 | 230 |
| 231 \begin{figure}[htpb] | |
| 30 | 232 \begin{minipage}{0.5\hsize} |
| 233 \begin{center} | |
| 24 | 234 \scalebox{0.35}{\includegraphics{figure/tree1.pdf}} |
| 30 | 235 \end{center} |
| 236 \caption{AST of function pointer} | |
| 237 \label{fig:tree1} | |
| 238 \end{minipage} | |
| 239 \begin{minipage}{0.2\hsize} | |
| 240 \begin{center} | |
| 24 | 241 \scalebox{0.35}{\includegraphics{figure/tree2.pdf}} |
| 30 | 242 \end{center} |
| 243 \caption{AST of \rectype} | |
| 244 \label{fig:tree2} | |
| 24 | 245 \end{minipage} |
| 246 \end{figure} | |
| 247 | |
| 45 | 248 A type check is taken in the parametarized goto statement or function call. |
| 21 | 249 |
| 250 __code csA(__rectype *p) { | |
| 251 goto p(3); | |
| 252 } | |
| 253 | |
| 45 | 254 In this case, {\tt 3} is not a type of \verb+__code csA(__rectype *P)+ and the compiler complains. |
| 255 But the code below does not check its argument. | |
| 22 | 256 |
| 45 | 257 __code csA(__code (*p)()) { |
| 258 goto p(3); | |
| 259 } | |
| 260 | |
| 261 The \rectype{} flag is implemented in following program in | |
| 262 gcc/c-family/c-pretty-print.c. | |
| 23 | 263 |
| 264 static void | |
| 265 pp_c_abstract_declarator (c_pretty_printer *pp, tree t) | |
| 266 { | |
| 267 if (TREE_CODE (t) == POINTER_TYPE) | |
| 268 { | |
| 269 if (TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE | |
| 270 || TREE_CODE (TREE_TYPE (t)) == FUNCTION_TYPE) | |
| 271 pp_c_right_paren (pp); | |
| 272 #ifndef noCbC | |
| 273 if (IS_RECTYPE(t)) return; | |
| 274 #endif | |
| 275 t = TREE_TYPE (t); | |
| 276 } | |
| 277 pp_direct_abstract_declarator (pp, t); | |
| 278 } | |
| 279 | |
| 45 | 280 \verb+if (IS_RECTYPE(t)) return;+ prevents infinite type check. |
| 23 | 281 |
|
26
680becde8c9f
modify coparison
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
25
diff
changeset
|
282 --Comparison |
| 11 | 283 |
|
26
680becde8c9f
modify coparison
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
25
diff
changeset
|
284 |
|
19
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
285 |
| 46 | 286 |
| 51 | 287 Here is the result in IA32 and x64 architecture (Table\ref{tab:compare}). |
| 288 GCC-4.2.3 is IA32 architecture. | |
| 289 GCC-4.6.0 is x64 architecture. | |
| 290 | |
| 47 | 291 conv1 1 is function call. conv1 2, conv1 3 is optimized CPS transformed source. |
| 46 | 292 |
| 293 \begin{table}[htpb] | |
| 294 \centering | |
| 295 \small | |
| 296 \begin{tabular}{|l|r|r|r|} \hline | |
| 297 & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline | |
| 48 | 298 GCC-4.2.3(+omit)IA32 & 4.20 & 2.25 & 2.76 \\ \hline |
| 50 | 299 GCC-4.6.0(+O2)x64 & 1.65 & 1.10 & 1.08 \\ \hline |
| 46 | 300 \end{tabular} |
| 47 | 301 \caption{GCC bench mark(in sec)} |
| 302 \label{tab:compare} | |
| 46 | 303 \end{table} |
| 304 | |
| 305 | |
|
19
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
306 --Conclusion |
|
39
09cd9c5c7c40
modify conclution
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
307 |
|
09cd9c5c7c40
modify conclution
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
308 |
|
09cd9c5c7c40
modify conclution
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
309 We have designed and implemented Continuation based language for practical use. |
| 44 | 310 We have implemented \rectype{} syntax in GCC for CbC. |
|
40
4b828672f6b9
modify rectype.ind
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
39
diff
changeset
|
311 Thereby Easyly be able to write CbC program than previous. |
|
39
09cd9c5c7c40
modify conclution
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
312 |
| 44 | 313 This \rectype{} implementation may be other problems. |
|
39
09cd9c5c7c40
modify conclution
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
314 If so, it is necessary to find and fix them on future. |
|
09cd9c5c7c40
modify conclution
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
315 |
|
09cd9c5c7c40
modify conclution
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
316 |