|
11
|
1 -title: Recursive type syntax in Continuation based C
|
|
|
2
|
|
|
3 \newcommand{\rectype}{{\tt \_\_rectype}}
|
|
|
4
|
|
13
|
5 --author: Nobuyasu Oshiro, Shinji KONO
|
|
11
|
6
|
|
|
7 --abstract:
|
|
13
|
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.
|
|
|
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.
|
|
|
18 Also we show usage of CbC and it's benchmark.
|
|
|
19
|
|
13
|
20 --Motivation
|
|
|
21
|
|
|
22
|
|
11
|
23
|
|
|
24 --Continuation based C
|
|
|
25
|
|
|
26 CbC's basic programming unit is a code segment. It is not a subroutine, but it
|
|
|
27 looks like a function, because it has input and output. We can use C struct
|
|
|
28 as input and output interfaces.
|
|
|
29
|
|
|
30 struct interface1 { int i; };
|
|
|
31 struct interface2 { int o; };
|
|
|
32
|
|
|
33 __code f(struct interface1 a) {
|
|
|
34 struct interface2 b; b.o=a.i;
|
|
|
35 goto g(b);
|
|
|
36 }
|
|
|
37
|
|
|
38 In this example, a code segment
|
|
|
39 \verb+f+ has \verb+input a+ and sends \verb+output b+ to a code segment \verb+g+.
|
|
|
40 There is no return from code segment \verb+b+, \verb+b+ should call another
|
|
|
41 continuation using \verb+goto+. Any control structure in C is allowed in CwC
|
|
|
42 language, but in case of CbC, we restrict ourselves to use \verb+if+ statement
|
|
|
43 only, because it is sufficient to implement C to CbC translation. In this case,
|
|
|
44 code segment has one input interface and several output interfaces (fig.\ref{code}).
|
|
|
45
|
|
|
46 \includegraphics[width=6cm]{
|
|
|
47 \begin{figure}[htb]
|
|
|
48 \begin{center}
|
|
|
49 \includegraphics[width=6cm]{figure/code.pdf}
|
|
|
50 \caption{code}
|
|
|
51 \end{center}
|
|
|
52 \label{code}
|
|
|
53 \end{figure}
|
|
|
54
|
|
|
55
|
|
|
56
|
|
|
57 \verb+__code+ and parameterized global goto statement is an extension of
|
|
|
58 Continuation based C. Unlike \verb+C--+ \cite{cminusminus}'s parameterized goto,
|
|
|
59 we cannot goto into normal C function.
|
|
|
60
|
|
|
61 In CwC, we can go to a code segment from a C function and we can call C functions
|
|
|
62 in a code segment. So we don't have to shift completely from C to CbC. The later
|
|
|
63 one is straight forward, but the former one needs further extensions.
|
|
|
64
|
|
|
65 void *env;
|
|
|
66 __code (*exit)(int);
|
|
|
67
|
|
|
68 __code h(char *s) {
|
|
|
69 printf(s);
|
|
|
70 goto (*exit)(0),env;
|
|
|
71 }
|
|
|
72
|
|
|
73 int main() {
|
|
|
74 env = __environment;
|
|
|
75 exit = __return;
|
|
|
76 goto h("hello World\n");
|
|
|
77 }
|
|
|
78
|
|
|
79 In this hello world example, the environment of \verb+main()+
|
|
|
80 and its continuation is kept in global variables. The environment
|
|
|
81 and the continuation can be get using \verb+__environment+,
|
|
|
82 and \verb+__return+. Arbitrary mixture of code segments and functions
|
|
|
83 are allowed (in CwC). The continuation of \verb+goto+ statement
|
|
|
84 never returns to original function, but it goes to caller of original
|
|
|
85 function. In this case, it returns result 0 to the operating system.
|
|
|
86
|
|
|
87
|
|
|
88
|
|
|
89 --recursive type syntax
|
|
|
90
|
|
|
91 We implemented \rectype syntax in CbC on GCC.
|
|
|
92 \rectype syntax is declare a recursive type.
|
|
|
93 This example is using \rectype in CbC.
|
|
|
94
|
|
|
95 __code csA( __rectype *p) {
|
|
|
96 goto p(csB);
|
|
|
97 }
|
|
|
98
|
|
|
99 *p represent pointer of csA at \ref{code:rectype} .
|
|
|
100 p's argument type is same csA that function pointer.
|
|
|
101
|
|
|
102 Recursive type Can not declarated in C.
|
|
|
103 Because
|
|
|
104
|
|
|
105
|
|
|
106
|
|
|
107 It is the same as the following.
|
|
|
108
|
|
|
109 void csA( void (*p)(void*)) {
|
|
|
110 p(csB);
|
|
|
111 }
|
|
|
112
|
|
|
113
|
|
|
114
|
|
|
115 __code csA( __code (*p)( __code (*)( __code (*)( __code )))) {
|
|
|
116 goto p(csB);
|
|
|
117 }
|
|
|
118
|
|
|
119
|
|
13
|
120 --Recursive type syntax
|
|
|
121
|
|
|
122 struct interface {
|
|
|
123 __code (*next)(struct interface);
|
|
|
124 };
|
|
|
125
|
|
|
126 __code csA(struct interface p) {
|
|
|
127 struct interface ds = { csB };
|
|
|
128 goto p.next(ds);
|
|
|
129 }
|
|
|
130
|
|
|
131 int main() {
|
|
|
132 struct interface ds = { print };
|
|
|
133 goto csA(ds);
|
|
|
134 return 0;
|
|
|
135 }
|
|
|
136
|
|
|
137
|
|
|
138
|
|
|
139 __code fibonacci(__rectype *p, int num, int count, int result, int prev)
|
|
|
140
|
|
|
141
|
|
|
142 --GCC implementation
|
|
11
|
143
|
|
|
144
|
|
|
145 \begin{figure}[htpb]
|
|
|
146 \begin{minipage}{0.5\hsize}
|
|
|
147 \begin{center}
|
|
|
148 \scalebox{0.35}{\includegraphics{figure/tree1.pdf}}
|
|
|
149 \end{center}
|
|
|
150 \caption{}
|
|
|
151 \label{fig:tree1}
|
|
|
152 \end{minipage}
|
|
|
153 \begin{minipage}{0.2\hsize}
|
|
|
154 \begin{center}
|
|
|
155 \scalebox{0.35}{\includegraphics{figure/tree2.pdf}}
|
|
|
156 \end{center}
|
|
|
157 \caption{\rectype}
|
|
|
158 \label{fig:tree2}
|
|
|
159 \end{minipage}
|
|
|
160 \end{figure}
|
|
|
161
|
|
|
162
|
|
|
163
|
|
|
164 \begin{table}[htpb]
|
|
|
165 \centering
|
|
|
166 \small
|
|
|
167 \begin{tabular}{|l|r|r|r|} \hline
|
|
|
168 (unit: s) & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
|
|
|
169 Micro-C(32bit) & 9.93 & 6.31 & 7.18 \\ \hline
|
|
|
170 Micro-C(64bit) & 5.03 & 5.12 & 5.00 \\ \hline \hline
|
|
|
171 GCC -O3(32bit) & 2.52 & 2.34 & 1.53 \\ \hline
|
|
|
172 GCC -O3(64bit) & 1.80 & 1.20 & 1.44 \\ \hline
|
|
|
173 \end{tabular}
|
|
|
174 \caption{Micro-C, GCC bench mark (in sec)}
|
|
|
175 \label{tab:mc,gcc,compare}
|
|
|
176 \end{table}
|
|
|
177
|
|
|
178
|
|
|
179
|
|
13
|
180 --Data Segment
|
|
|
181
|
|
|
182 --Data Segment vs recursive type
|
|
|
183
|
|
|
184
|
|
|
185 --Experience in CbC
|
|
|
186
|
|
|
187 --Future direction
|
|
|
188
|
|
|
189
|
