-title: Recursive type syntax in Continuation based C

\newcommand{\rectype}{{\tt \_\_rectype}}

--author: Nobuyasu Oshiro, Shinji KONO

--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 \rectype{} keyword for recursive type, and it is implemented in GCC-4.6.0.
We will compare the conventional methods, \rectype{} keyword and a method using C structure.
Also we show usage of CbC and it's benchmark.

--Motivation

The C programming language is used in many practical programs, operating system  
kernels, byte code machines, network servers or embedded systems. Low level feature
of C is useful, but sometimes it requires programming hacks. For example, in case of
byte code machine often entire program is a huge switch statement which has many
labels which correspond the byte codes. Operating system or network server has
many layers such as system call dispatch, transport or presentation layer. It 
requires deep call levels,  2 or 3 for each layer, resulting 10-30 call levels.

Continuation based C (CbC) provides a structured way to represent these situations. It
is a small medication of C. It consists of a syntax to force tail-call-elimination
and parameterized goto statement. 

Continuation has long history. Usually it means full copy of computational environment as in Scheme\cite{r4rs}. Our continuation is a simple C function without environment because we have no stack in CbC.
Using explicit stack, we can convert normal C program into CbC using CPS transformation\cite{CompilingWithContinuation}, 
but we commit it's detail here.

C has capable of recursive functions, but we find it's type system is not enough
to represent CbC programming. In this paper, we introduce \rectype{}
keyword as a recursive type. To handle recursive type, conventionally tagged struct 
is used. It is also fit for CbC program.

We will describe the CbC and \rectype{} implementation of CbC on GCC 4.6.0.

--Continuation based C

We call CbC's basic programming unit 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. 

   struct interface1  { int i; };
   struct interface2  { int o; };

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

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 may 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}).

<center><img src="figure/code.pdf" alt="code"></center>


\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.

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.

   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");
   }

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.



--Recursive type syntax

A continuation is a pointer to a Code Segment to be executed after.
For example, it is passed as follows;

   __code csA( __code (*p)() ) {
       goto p(csB);
   }

where {\tt p} is the continuation and {\tt csB} is a Code Segment which
has the same type of {\tt csA}.  This declaration is not enough because
it lacks the type of the argument. If add the type declaration, we
get following program;

    __code csA( __code (*p)( __code (*)( __code (*)( __code (*)())))) {
       goto p(csB);
    }

or 
    __code csA( __code (*p)( __code(*)())) {
       goto p(csB);
    }

It is enough to type {\verb+csB+}, but of course it is not completely will typed.
Omitting types of the arguments of a function is allowed, but it requires
complex declaration and it is incomplete.

We introduce \rectype{} syntax for this situation. In an argument deflation,
\rectype{} represents it's function type. Using \rectype{}, previous example can
be written like this;

    __code csA( __rectype *p) {
       goto p(csB);
    }

{\tt *p} has a type of {\tt csA} itself.

The same situation is happen in conventional C, since Code Segment is a
mere C function with tail-call-elimination. \rectype{} provides exact and
concise way to describe recursive type. If we have extra arguments,

    __code csBs(int a,  __rectype *p) ;

    __code csAs(int a,  __rectype *p) {
       goto p(a, csBs);
    }

In this case, we have two \rectype{} keywords. It may points the same type or
different types. There is no ambiguity here, because it point the exact
position. If it points the same position in the same type declaration,
it is the same type.


--Recursive type syntax in a function body

\rectype{} can be appeared in a function arguments, a function body or struct definition as a
pointer type, otherwise it errors.

In a function body, it has a type of the function itself.

    __code csAs(int a,  __rectype *p) {
       __rectype *p1 = p;
       goto p1(a, csBs);
    }

It is possible to write the following way; 

    __code csAs(int a,  __rectype *p) {
       __code (*p)(int, __retype *);
       p1 = p;
       goto p1(a, csBs);
    }

but previous one is shorter.

We cannot allow non pointer type \rectype{}, because it generates infinite size of object.

In case of struct, 

     struct {
         int a;
         __rectype *next;
     }

is the same of this;

     struct b {
         int a;
         struct b *next;
     }

this is a conventional way to represent recursive type in C. Using this technique we
can write a continuation like this;

    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);
        /* NOTREACHED*/ 
        return 0;
    }

\rectype{} is clearer but struct technique provides abstract representation. It requires
extra struct declaration, but it give us the same assembler output.


--How to implement \rectype{}

\rectype{} syntax is implemented as a GCC's AST (Abstract Syntax Tree).
A function type has tree lists of its arguments and its return type. 
In \verb+__code+ case, return type is void.
When we find \rectype{}, which is as pointer to the function, a pointer type node
is created (Fig.\ref{fig:tree1}).
Normally the type node has a pointer to function type, but
we put a pointer to the parent function itself (Fig.\ref{fig:tree2}).

It looks like a normal function type and works fine except type comparison, which
falls into an infinite loop. In order to stop type loop, we introduce \rectype{} flag
in the type node.  A type comparison was simply stopped when it met \rectype{} flag.

\begin{figure}[htpb]
\begin{minipage}{0.5\hsize}
\begin{center}
\scalebox{0.35}{\includegraphics{figure/tree1.pdf}}
\end{center}
\caption{AST of function pointer}
\label{fig:tree1}
\end{minipage}
\begin{minipage}{0.2\hsize}
\begin{center}
\scalebox{0.35}{\includegraphics{figure/tree2.pdf}}
\end{center}
\caption{AST of \rectype}
\label{fig:tree2}
\end{minipage}
\end{figure}

A type check is taken in the parameterized goto statement or function call. 

    __code csA(__rectype *p) {
       goto p(3);
    }

In this case, {\tt 3} is not a type of \verb+__code csA(__rectype *P)+ and the compiler complains.
But the code below does not check its argument.

    __code csA(__code (*p)()) {
       goto p(3);
    }

The \rectype{} flag is implemented in  following program in
gcc/c-family/c-pretty-print.c.

    static void
    pp_c_abstract_declarator (c_pretty_printer *pp, tree t)
    {
      if (TREE_CODE (t) == POINTER_TYPE)
        {
          if (TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE
          || TREE_CODE (TREE_TYPE (t)) == FUNCTION_TYPE)
        pp_c_right_paren (pp);
    #ifndef noCbC
          if (IS_RECTYPE(t)) return;
    #endif
          t = TREE_TYPE (t);
        }
      pp_direct_abstract_declarator (pp, t);
    }

\verb+if (IS_RECTYPE(t)) return;+ prevents infinite type check.
 
--CbC on GCC

Our CbC implementation on GCC is working on AST level and
RTL generation level. This means there no architecture dependency, so we
expect it is working on any architecture, but some of architecture restrict
tail call elimination itself such as old PPC architecture.

We devised small test programs. {\tt conv1 1} is a normal function call. 
{\tt conv1 2} and {\tt conv1 3} are CbC program which are  optimized CPS transformed version.

Here is the result in IA32 and x64 architecture (Table\ref{tab:compare}).
GCC-4.2.3 is IA32 architecture.
GCC-4.6.0 is x64 architecture. We use {\tt -fno-inline} to prevent call expansion in {\tt conv1 1}.

In case of GCC 4.2, CbC version run faster than normal function, because of register usage. But
in case of GCC 4.6, the difference becomes small because x64 has 16 registers.

\begin{table}[htpb]
\centering
\small
\begin{tabular}{|l|r|r|r|} \hline
& ./conv1 1 & ./conv1 2 &  ./conv1 3 \\ \hline
GCC-4.2.3(+omit)IA32   & 4.20 & 2.25 & 2.76 \\ \hline
GCC-4.6.0(+O2)x64     & 1.65 & 1.10 & 1.08 \\ \hline
\end{tabular}
\caption{GCC bench mark(in sec)}
\label{tab:compare}
\end{table}

We use CbC for PS2 based TV game, Simple protocol simulation and Model checking.

--Conclusion

We have designed and implemented Continuation based language for practical use.
We have introduced \rectype{} syntax, which provides strict type of Code Segment and
short representation.

We are currently investing to use CbC as an Operating System kernel description or Embedded Systems.