# HG changeset patch # User Shinji KONO # Date 1339675914 -32400 # Node ID 22dbcdbcae5f3956496d823f723dafdeebc386c3 # Parent bf3c780d3039b0fff87c0064d327e8cd860b0679 add CbC.mm diff -r bf3c780d3039 -r 22dbcdbcae5f paper/CbC.mm --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/CbC.mm Thu Jun 14 21:11:54 2012 +0900 @@ -0,0 +1,80 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r bf3c780d3039 -r 22dbcdbcae5f paper/rectype.ind --- a/paper/rectype.ind Thu Jun 14 20:06:04 2012 +0900 +++ b/paper/rectype.ind Thu Jun 14 21:11:54 2012 +0900 @@ -2,9 +2,10 @@ \newcommand{\rectype}{{\tt \_\_rectype}} ---author: Shinji Kono, Nobuyasu Oshiro +--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. @@ -16,6 +17,9 @@ 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 + + --Continuation based C @@ -54,8 +58,6 @@ Continuation based C. Unlike \verb+C--+ \cite{cminusminus}'s parameterized goto, we cannot goto into normal C function. ---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. @@ -83,101 +85,6 @@ function. In this case, it returns result 0 to the operating system. ---What's good? - -CbC is a kind of high level assembler language. It can do several -original C language cannot do. For examples, - -{\small -\begin{verbatim} - Thread Scheduler - Context Switch - Synchronization Primitives - I/O wait semantics - -\end{verbatim} -} - -are impossible to write in C. Usually it requires some help of -assembler language such as \verb+__asm+ statement extension which is -of course not portable. - ---Scheduler example - -We can easily write these things in CbC, because -CbC has no hidden information behind the stack frame of C. -A thread simply go to the scheduler, - - goto scheduler(self, task_list); - - -and the scheduler simply pass the control to the next -thread in the task queue. - - code scheduler(Thread self,TaskPtr list) - { - TaskPtr t = list; - TaskPtr e; - list = list->next; - goto list->thread->next(list->thread,list); - } - -Of course it is a simulator, but it is an implementation -also. If we have a CPU resource API, we can write real multi -CPU scheduler in CbC. - -This is impossible in C, because we cannot access the hidden -stack which is necessary to switch in the scheduler. In CbC, -everything is visible, so we can switch threads very easily. - -This means we can use CbC as an executable specification -language of OS API. - ---Self Verification - -Since we can write a scheduler in CbC, we can also enumerate -all possible interleaving of a concurrent program. We have -implement a model checker in CwC. CbC can be a self verifiable -language\cite{kono08a}. - -SPIN\cite{holzmann97model} is a very reliable model checker, but it have to -use special specification language PROMELA. We cannot directly -use PROMELA as an implementation language, and it is slightly -difficult to study its concurrent execution semantics including -communication ports. - -There are another kind of model checker for real programming -language, such as Java PathFinder\cite{havelund98model}. Java PathFinder use -Java Virtual Machine (JVM) for state space enumeration which -is very expensive some time. - -In CbC, state enumerator itself is written in CbC, and its concurrency -semantics is written in CbC itself. Besides it is very close -to the implementation. Actually we can use CbC as an implementation -language. Since enumerator is written in the application itself, we -can perform abstraction or approximation in the application specific -way, which is a little difficult in Java PathFinder. It is possible -to handle JVM API for the purpose, although. - -We can use CPS transformed CbC source code for verification, but -we don't have to transform all of the source code, because CwC -supports all C constructs. (But not in C++... Theoretically it is -possible with using cfront converter, it should be difficult). - - ---As a target language - -Now we have GCC implementation of CbC, it runs very fast. Many -popular languages are implemented on top of C. Some of them -uses very large switch statement for the byte code interpreter. -We don't have to use these hacks, when we use CbC as an implementation -language. - -CbC is naturally similar to the state charts. It means it is very -close to UML diagrams. Although CbC does not have Object Oriented -feature such as message passing nor inheritance, which is not -crucial in UML. - --recursive type syntax @@ -210,7 +117,29 @@ } ---Implementation of \rectype in CbC on GCC +--Recursive type syntax + + 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; + } + + + + __code fibonacci(__rectype *p, int num, int count, int result, int prev) + + +--GCC implementation \begin{figure}[htpb] @@ -232,34 +161,6 @@ ---Method other than \rectype - - 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; - } - - - - - - __code fibonacci(__rectype *p, int num, int count, int result, int prev) { - - - -\section{Comparision} - - \begin{table}[htpb] \centering \small @@ -276,3 +177,13 @@ +--Data Segment + +--Data Segment vs recursive type + + +--Experience in CbC + +--Future direction + +