changeset 13:22dbcdbcae5f

add CbC.mm
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Thu, 14 Jun 2012 21:11:54 +0900
parents bf3c780d3039
children bbbda7a58067
files paper/CbC.mm paper/rectype.ind
diffstat 2 files changed, 118 insertions(+), 127 deletions(-) [+]
line wrap: on
line diff
--- /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 @@
+<map version="0.9.0">
+<!-- To view this file, download free mind mapping software FreeMind from http://freemind.sourceforge.net -->
+<node CREATED="1339674276399" ID="ID_1771190398" MODIFIED="1339674292425" TEXT="CbC">
+<node CREATED="1339674420261" ID="ID_107339161" MODIFIED="1339674428266" POSITION="right" TEXT="motivation">
+<node CREATED="1339674428267" ID="ID_573530181" MODIFIED="1339674437662" TEXT="usage of low level language as C">
+<node CREATED="1339674437662" ID="ID_1306127670" MODIFIED="1339674447124" TEXT="Vitural machine"/>
+<node CREATED="1339674447799" ID="ID_244895865" MODIFIED="1339674457008" TEXT="Layered library"/>
+<node CREATED="1339674458442" ID="ID_179494298" MODIFIED="1339674464995" TEXT="Operating system kernel"/>
+<node CREATED="1339674467749" ID="ID_1991471781" MODIFIED="1339674472871" TEXT="Compiler target">
+<node CREATED="1339674608519" ID="ID_1117288574" MODIFIED="1339674611789" TEXT="state machine"/>
+</node>
+<node CREATED="1339674514325" ID="ID_1023186088" MODIFIED="1339674535784" TEXT="Task description"/>
+</node>
+<node CREATED="1339675325886" ID="ID_656084329" MODIFIED="1339675332216" TEXT="refactoring">
+<node CREATED="1339675343357" ID="ID_1844179957" MODIFIED="1339675358874" TEXT="preserved low level description"/>
+<node CREATED="1339675360812" ID="ID_808475116" MODIFIED="1339675362801" TEXT="trait"/>
+</node>
+<node CREATED="1339674697738" ID="ID_844764484" MODIFIED="1339674701926" TEXT="Reflection">
+<node CREATED="1339675372854" ID="ID_1958389663" MODIFIED="1339675380640" TEXT="meta comutation"/>
+</node>
+<node CREATED="1339674703735" ID="ID_596175816" MODIFIED="1339674707219" TEXT="Parallel task">
+<node CREATED="1339675382696" ID="ID_1537207595" MODIFIED="1339675397863" TEXT="as a kernel of GPU"/>
+</node>
+<node CREATED="1339674477704" ID="ID_1425065491" MODIFIED="1339674495161" TEXT="byte code approach">
+<node CREATED="1339674495164" ID="ID_199764866" MODIFIED="1339674501033" TEXT="unreadable"/>
+<node CREATED="1339674505650" ID="ID_270152448" MODIFIED="1339674510956" TEXT="need upper language"/>
+<node CREATED="1339674546222" ID="ID_1849371936" MODIFIED="1339674549025" TEXT="LLVM"/>
+</node>
+</node>
+<node CREATED="1339674573480" ID="ID_790532910" MODIFIED="1339674581414" POSITION="right" TEXT="CbC language">
+<node CREATED="1339674581415" ID="ID_1398832409" MODIFIED="1339674585815" TEXT="extra syntax"/>
+<node CREATED="1339674586282" ID="ID_1200529793" MODIFIED="1339674591876" TEXT="C compatibility"/>
+</node>
+<node CREATED="1339674292433" ID="ID_536949880" MODIFIED="1339674299670" POSITION="right" TEXT="recursive type syntax">
+<node CREATED="1339674336447" ID="ID_523262861" MODIFIED="1339674346397" TEXT="conventional method">
+<node CREATED="1339674346397" ID="ID_1538826997" MODIFIED="1339674351891" TEXT="struct"/>
+</node>
+<node CREATED="1339674300417" ID="ID_1442947843" MODIFIED="1339674305836" TEXT="syntax detail">
+<node CREATED="1339674377946" ID="ID_1244889275" MODIFIED="1339674384739" TEXT="in function argument"/>
+<node CREATED="1339674385486" ID="ID_94963766" MODIFIED="1339674396901" TEXT="in function body"/>
+<node CREATED="1339674397752" ID="ID_1697939673" MODIFIED="1339674401818" TEXT="in struct"/>
+</node>
+<node CREATED="1339674370822" ID="ID_1966776846" MODIFIED="1339674374400" TEXT="implementation"/>
+</node>
+<node CREATED="1339674763353" ID="ID_982083961" MODIFIED="1339675541367" POSITION="right" TEXT="gcc implementation">
+<node CREATED="1339675521699" ID="ID_438723312" MODIFIED="1339675527223" TEXT="new syntax"/>
+<node CREATED="1339675581478" ID="ID_1706619970" MODIFIED="1339675591877" TEXT="forcing tail call elimination"/>
+<node CREATED="1339675598174" ID="ID_1600927412" MODIFIED="1339675631107" TEXT="return continuation">
+<node CREATED="1339675639689" ID="ID_244694915" MODIFIED="1339675644069" TEXT="thread safe?"/>
+</node>
+<node CREATED="1339675697444" ID="ID_714357535" MODIFIED="1339675703735" TEXT="detail in arXive"/>
+</node>
+<node CREATED="1339675242647" ID="ID_661452631" MODIFIED="1339675245804" POSITION="right" TEXT="data segment">
+<node CREATED="1339675279692" ID="ID_1962538789" MODIFIED="1339675283768" TEXT="input and output"/>
+<node CREATED="1339675287968" ID="ID_1707346128" MODIFIED="1339675298314" TEXT="standard interface"/>
+<node CREATED="1339675298667" ID="ID_959391025" MODIFIED="1339675300800" TEXT="reflection"/>
+<node CREATED="1339675302449" ID="ID_951821309" MODIFIED="1339675306477" TEXT="task description">
+<node CREATED="1339675308862" ID="ID_1984685631" MODIFIED="1339675313138" TEXT="Open CL kernel"/>
+</node>
+</node>
+<node CREATED="1339675408900" ID="ID_78169122" MODIFIED="1339675560710" POSITION="right" TEXT="data segment or recursive type">
+<node CREATED="1339675416313" ID="ID_1337112110" MODIFIED="1339675441962" TEXT="code generation"/>
+<node CREATED="1339675442739" ID="ID_1343153078" MODIFIED="1339675454197" TEXT="run time reconnection of code segment"/>
+</node>
+<node CREATED="1339674554434" ID="ID_628815031" MODIFIED="1339674561121" POSITION="right" TEXT="experience in CbC">
+<node CREATED="1339674601714" ID="ID_388042614" MODIFIED="1339674629913" TEXT="target language for grep"/>
+<node CREATED="1339674633194" ID="ID_972921969" MODIFIED="1339674653285" TEXT="describing TV game"/>
+<node CREATED="1339674677556" ID="ID_970913756" MODIFIED="1339674686429" TEXT="Hardware simulation"/>
+<node CREATED="1339674731002" ID="ID_419758306" MODIFIED="1339674740154" TEXT="debugging difficulty"/>
+<node CREATED="1339674688415" ID="ID_210543554" MODIFIED="1339674692850" TEXT="Model checking"/>
+</node>
+<node CREATED="1339674772437" ID="ID_275141784" MODIFIED="1339674781279" POSITION="right" TEXT="future direction">
+<node CREATED="1339674781600" ID="ID_409591563" MODIFIED="1339674794783" TEXT="data segment"/>
+<node CREATED="1339674796064" ID="ID_1955281999" MODIFIED="1339674808552" TEXT="parallel task manager"/>
+<node CREATED="1339674810226" ID="ID_1065365117" MODIFIED="1339674815309" TEXT="Operation System"/>
+<node CREATED="1339674817702" ID="ID_279688933" MODIFIED="1339674823713" TEXT="LLVM implementation"/>
+<node CREATED="1339674824347" ID="ID_896534752" MODIFIED="1339674839473" TEXT="Editable code"/>
+</node>
+</node>
+</map>
--- 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
+
+