# HG changeset patch # User Shinji KONO # Date 1339792351 -32400 # Node ID 0cd49f4081e02d921d604de75c9f21ed575da29c # Parent bdbfe2a272ffd83240cca593d19e652f2ea5b7c4 final fix diff -r bdbfe2a272ff -r 0cd49f4081e0 paper/rectype.ind --- a/paper/rectype.ind Sat Jun 16 05:05:25 2012 +0900 +++ b/paper/rectype.ind Sat Jun 16 05:32:31 2012 +0900 @@ -31,8 +31,8 @@ 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 compuational evironment as in Scheme\cite{scheme}. 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{cps}, +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 @@ -44,9 +44,9 @@ --Continuation based C -CbC's basic programming unit is a Code Segment. It is not a subroutine, but it +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. +as input and output interfaces. struct interface1 { int i; }; struct interface2 { int o; }; @@ -60,7 +60,7 @@ \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 +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}). @@ -211,17 +211,15 @@ \rectype{} is clearer but struct technique provides abstract representation. It requires extra struct declaration, but it give us the same assembler output. - __code fibonacci(__rectype *p, int num, int count, int result, int prev) - --How to implement \rectype{} \rectype{} syntax is implemented as a GCC's AST (Abstract Syntax Tree). -A function type has tree lists of its argments and its return type. +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}). -Normaly the type node has a pointer to function type, but +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 @@ -245,7 +243,7 @@ \end{minipage} \end{figure} -A type check is taken in the parametarized goto statement or function call. +A type check is taken in the parameterized goto statement or function call. __code csA(__rectype *p) { goto p(3); @@ -279,16 +277,22 @@ \verb+if (IS_RECTYPE(t)) return;+ prevents infinite type check. ---Comparison +--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. +GCC-4.6.0 is x64 architecture. We use {\tt -fno-inline} to prevent call expansion in {\tt conv1 1}. -conv1 1 is function call. conv1 2, conv1 3 is optimized CPS transformed source. +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 @@ -302,15 +306,12 @@ \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 implemented \rectype{} syntax in GCC for CbC. -Thereby Easyly be able to write CbC program than previous. +We have introduced \rectype{} syntax, which provides strict type of Code Segment and +short representation. -This \rectype{} implementation may be other problems. -If so, it is necessary to find and fix them on future. - - +We are currently investing to use CbC as an Operating System kernel description or Embedded Systems.