Mercurial > hg > Papers > 2012 > aplas
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 + +