-title: Testing and Equivalence using Continuation based C

--abstract:

Continuation based C (CbC) is a language without function call. We have implemented
the language in GCC. This language is suitable for embedded systems or
many core architecture such as Cell, GPGPU or Core i7 architecture. In order
to achieve high performance, special features are necessary like vector processing,
stream arithmetic or Open CL like parallel processing, 
which is usually difficult to use and its correctness is uncertain. 
In CbC, these special features themselves can be expressed. 
We show how to use CbC in Testing and
Equivalence when we use special features.

--Programming Language for Code Generation

Today, quite large size softwares are written and working. 
Many of them are half generated by computer itselves.
For an example, GCC (GNU compiler collection)\cite{gcc} generates many insn-*.c
file from machine description. Another example is Scala\cige{scala}, which
generates Java Byte Code. Ruby on rails generates ruby scripts.

We are developping Continuation based C, here after CbC \cite{cbc}, which is suitable for
state machine description, which is also good for compiler target language.
CbC has two basic elements, code segment and data segment. Code segements are
connected by parameterised goto statements. Data segments are exchanged among code segments. Data segment is designed to fit in various Many Core Architecture such as Cell\cite{cell}.

Generated code is supposed to work efficiently, but it have to running on sepcial
hardware sometimes. Often generated code is modified or is implemeted in a hardware
to achieve high performance. We can use any programming language as a generation
target, but we focus on these points,

    Effective usage of special architecture,
    Representation of behavior,
    Modularity,
    Testability,
    Memory awareness.

In CbC, a large software is divided into units which roughly equal basic block
of compiler. Since CbC has no implicit environment, that is stack, code state
is fully represented in an input interface of the code segment. Of course, 
the input interface may have complex state, for example, simulated stack,
but we can insert test code between two code segments. This is our basic
idea.

In this paper, we describe Continuation based C and its code segment and data
segment system and its implementation on gcc. We will discuss the software
architecture of CbC and Cerium Task Manager for PS3\cite{ps3}, then we
discuss our testing method for CbC.

--Continuation based C

A code segment in CbC is a normal C function actually. It has no return value and
no return statement, if it has it it will be an error. To exit the code segment,
goto statement to other or same code segment is used. Besides return statement,
any C statement can be used, normal C function is allowed also. 

   __code code1(int a, int b) {
	goto code2(a,b);
   }

\verb+__code+ is a type of function. Arguments of code segment arel called input
interface and arguments of goto statement are called output interface. In our
system, input / output interfaces are usually a set of data segments, which we
discuss it later.

It is possible to convert C program into CbC with no funcion calls, using a
kind of CPS transformation \cite{cbc-c} (in Japanese).

A pointer to a code segment is a light weight continuation, since it has no
environment. This is becase code segment has no return. In this way code
segment is different from normal C function.

Unfortunately, ANSI-C has no recursive type, we cannot write exact type
of continuation, but it is not a seriaus problem. It is written like this.
Detailed parameter definitions are ommited.

   __code code1(int a, int b, __code (*cont)(int a, int b, __code (*cont1)()) ) ;
	goto (*cont1)(a,b, cont1);
   }

In many case, many forward reference requires many prototype declaration. In CbC,
these definitions are automatically generated (by scripts).

---Interaction with C function

Since CbC is a C, any C function can be called in a code segment. To enter a
code segment from a C function, a parameterised goto is used, but it has
no return. To return from a code segment, full continuation ( continuation
with full environment) is used. A buitl-in function \verb+__CbC_return+ and
\verb+__CbC_environment+. 

    typedef __code (*return_type)(int, void*);
    __code f(return_type cont,void *env) {
        goto (*cont)(10,env);
    }

    int
    main(int argc, char **argv)
    {
	return_type cont =  _CbC_return;
	void *env = _CbC_environment;
	goto f(cont,env);
    }

In a function \verb+f+, cont contains a code segment to return value
from \verb+main()+. \verb+env+ is a pointr to the environment, that is
a frame pointer or stack pointer.

If you want to return to a middle of a fuction, put a function call.

Of course, in Unix, you can simply \verb+exit()+ from a code segment.
This is much simpler.

--Langugage Implementation

We have to implementation of CbC, one is a hand writtern compiler and
the other one is a patched gcc.

The modification of GCC is not so large. In a \+verb+c-parse.c+ and
\verb+exapnd_call.c+. In a parse, \verb+__code+ type , CbC_return, 
CbC_environment+ is added. CbC_return geneartes a code segment using
a nested function in GCC.

In call.c, a code segment is handle as a forced tail call eliminaton.
In GCC, tail call elimination is easily gave up, which is not allowed
in CbC. So some modification is necessary.

In GCC, CbC code segment has fixed stack frame size. If called
stack frame size is small than caller, no TCE is performed.
Argmeents in goto statement parmeter must not overrapped. 
In order to assure this, we simplly copy argments to newly
created variable at the parse level.

If we use normal C sype ABI (argument passing convention), 
i386 version runs very slow, becase all arguments have to
be in a stack. To avoid this, FASTCAlL option is
forced in all code segments. This is quite good in EMT64 modee
which has more register.

--Data Storage Implemantation

--Software Architecture

--Execution Model

--Testing method 
--Comparison