\documentclass[envcountsame]{llncs}
\usepackage[dvipdfmx]{graphicx}
\usepackage{llncsdoc}
\usepackage{url}
\usepackage{listings}


%\title{The implementation of recursive type syntax on GCC-4.6 for CbC}
\title{Recursive type syntax in Continuation based C}
\titlerunning{title running}
\toctitle{toc title}
%\subtitle{sub title}
\author{Shinji Kono\inst{1} Nobuyasu Oshiro\inst{2}}
\authorrunning{authorrunning}
\institute{University of the Ryukyus}
\email{}

\begin{document}
\maketitle

\begin{abstract}
We have implemented Continuation based C (CbC).
CbC is an extension of C, which has parameterized goto statement.
It is useful for finite state automaton or many core tasks. 
Goto statement is a way to force tail call elimination.
The destination of goto statement is called Code Segment, which is actually a normal function of C.
To represent recursive function call, the type system of C is not enough, because
it has no recursive types.
We introduce \verb+__rectype+ keyword for recursive type, and it is implemented in GCC-4.6.0.
We will compare the conventional methods, \verb+__rectype+ keyword and a method using C structure.
Also we show usage of CbC and it's benchmark.

\end{abstract}


\section{Introduce}


\paragraph{paragraph}


\section{Continuation based C}
CbC's basic programming unit is a code segment. It is not a subroutine, but it
looks like a function, because it has input and output. We can use C struct
as input and output interfaces.

{\small
\begin{verbatim}
   struct interface1  { int i; };
   struct interface2  { int o; };

   __code f(struct interface1 a) { 
       struct interface2 b; b.o=a.i;  
       goto g(b); 
   }

\end{verbatim}
}


In this example, a code segment
\verb+f+ has \verb+input a+ and sends \verb+output b+ to a code segment \verb+g+.
There is no return from code segment \verb+b+, \verb+b+ should call another
continuation using \verb+goto+. Any control structure in C is allowed in CwC
language, but in case of CbC, we restrict ourselves to use \verb+if+ statement
only, because it is sufficient to implement C to CbC translation. In this case,
code segment has one input interface and several output interfaces (fig.\ref{code}).

\begin{figure}[htb]
\begin{center}
\includegraphics[width=6cm]{figure/code.pdf}
\caption{code}
\end{center}
\label{code}
\end{figure}



\verb+__code+ and parameterized global goto statement is an extension of
Continuation based C. Unlike \verb+C--+ \cite{cminusminus}'s parameterized goto,
we cannot goto into normal C function.

\subsection{ Intermix with C}

In CwC, we can go to a code segment from a C function and we can call C functions
in a code segment. So we don't have to shift completely from C to CbC. The later
one is straight forward, but the former one needs further extensions.

{\small
\begin{verbatim}
   void *env;
   __code (*exit)(int);

   __code h(char *s) { 
        printf(s);
        goto (*exit)(0),env;
   }

   int main() {
        env  = __environment;
        exit = __return;
        goto h("hello World\n");
   }

\end{verbatim}
}

In this hello world example, the environment of \verb+main()+
and its continuation is kept in global variables. The environment
and the continuation can be get using \verb+__environment+,
and \verb+__return+. Arbitrary mixture of code segments and functions
are allowed (in CwC). The continuation of \verb+goto+ statement 
never returns to original function, but it goes to caller of original
function. In this case, it returns result 0 to the operating system.






%\begin{figure}[htpb]
%  \begin{center}
%\scalebox{0.35}{\includegraphics{figure/codesegment.pdf}}
%  \end{center}
%  \caption{}
%  \label{fig:codesegment}
%\end{figure}

\newpage

\section{recursive type syntax}
We implemented \verb+__rectype+ syntax in GCC.
\verb+__rectype+ syntax is declare a recursive type.
This example is using \verb+__rectype+ in CbC.

\begin{figure}[htpb]
\begin{verbatim}
__code csA( __rectype *p) {
    goto p(csB);
}
\end{verbatim}
\caption{example using \_\_rectype}
\label{code:rectype}
\end{figure}

*p represent pointer of csA at \ref{code:rectype} .
p's argument type is same csA that function pointer.

Recursive type Can not declarated in C.
Because 



It is the same as the following.

\begin{verbatim}
void csA( void (*p)(void*)) {
    p(csB);
}
\end{verbatim}



\begin{verbatim}
__code csA( __code (*p)( __code (*)( __code (*)( __code )))) {
    goto p(csB);
}
\end{verbatim}


\subsection{Implementation of \_\_rectype in GCC}


\begin{figure}[htpb]
  \begin{minipage}{0.5\hsize}
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/tree1.pdf}}
  \end{center}
  \caption{}
  \label{fig:tree1}
  \end{minipage}
  \begin{minipage}{0.2\hsize}
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/tree2.pdf}}
  \end{center}
  \caption{\_\_rectype}
  \label{fig:tree2}
\end{minipage}
\end{figure}



\subsection{Method other than \_\_rectype}

\begin{verbatim}
struct interface {
     __code (*next)(struct interface);
};

__code csA(struct interface p) {
     struct interface ds = { csB };
     goto p.next(ds);
}

int main() {
     struct interface ds = { print };
     goto csA(ds);
     return 0;
}
\end{verbatim}





\begin{verbatim}
__code fibonacci(__rectype *p, int num,  int count, int result, int prev) {
\end{verbatim}



\section{conclusion}


\begin{table}[htpb]
\centering
\small
\begin{tabular}{|l|r|r|r|} \hline
(unit: s) & ./conv1 1 & ./conv1 2 &  ./conv1 3 \\ \hline
Micro-C(32bit)         & 9.93 & 6.31 & 7.18 \\ \hline 
Micro-C(64bit)         & 5.03 & 5.12 & 5.00 \\ \hline \hline
GCC -O3(32bit)         & 2.52 & 2.34 & 1.53 \\ \hline
GCC -O3(64bit)         & 1.80 & 1.20 & 1.44 \\ \hline
\end{tabular}
\caption{Micro-C, GCC bench mark (in sec)}
\label{tab:mc,gcc,compare}
\end{table}







\bibliographystyle{junsrt}
\bibliography{cbc}
\nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals}



\end{document}