Mercurial > hg > Papers > 2012 > aplas
changeset 35:f9e7052a380e
merge
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 16 Jun 2012 00:18:11 +0900 |
| parents | 7294b17518c6 (diff) be591bf4e2b5 (current diff) |
| children | 2dd2b481b291 |
| files | paper/rectype.ind |
| diffstat | 3 files changed, 113 insertions(+), 78 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/CbC.mm Sat Jun 16 00:18:11 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/o2tex Fri Jun 15 23:02:04 2012 +0900 +++ b/paper/o2tex Sat Jun 16 00:18:11 2012 +0900 @@ -279,7 +279,7 @@ for ($depth = 1; substr($_, $depth, 1) eq '-'; $depth++) { ; } - if ($depth == 3) { + if ($depth == 2) { $file = sprintf('%d', $section) . '.tex'; &Pick('>>', $file) && (print $fh "\\section{", substr($_, $depth, @@ -295,7 +295,7 @@ $section++; # print STDOUT "$section "; } - elsif ($depth == 4) { + elsif ($depth == 3) { $file = sprintf('%d', $section - 1) . '.tex'; &Pick('>>', $file) && (print $fh "\\subsection{", substr($_, $depth, @@ -306,7 +306,7 @@ length($_) - $depth + 1) . '}'); (print $fh "\\end{bwslide}\n\n"); } - elsif ($depth == 5) { + elsif ($depth == 4) { $file = sprintf('%d', $section - 1) . '.tex'; &Pick('>>', $file) && (print $fh "\\subsubsection{", substr($_, $depth, @@ -409,7 +409,7 @@ &Pick('>>', $file) && (print $fh $_); } - if (/\\cite\{/) { $cite = ""; } # } + if (/\\cite\{/) { $cite = ""; } } } @@ -475,7 +475,7 @@ } sub Pick { - local($mode,$name,$pipe) = @_; + my ($mode,$name,$pipe) = @_; $fh = $opened{$name}; if (!$fh) { $fh = $opened{$name} = 'fh_' . ($nextfh++ + 0);
--- a/paper/rectype.ind Fri Jun 15 23:02:04 2012 +0900 +++ b/paper/rectype.ind Sat Jun 16 00:18:11 2012 +0900 @@ -50,8 +50,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. @@ -79,7 +77,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, @@ -125,51 +122,6 @@ 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 @@ -211,7 +163,34 @@ p's argument type is same csA that function pointer. + + +--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) + + + + --How to implement \rectype + \rectype syntax is implemented overriding AST. First, \rectype syntax make Tree same \code(\ref{fig:tree1}). Second, tree was created to be rectype flag. @@ -243,10 +222,10 @@ We have to override it in the pointer of csA. --- --Problems with implementation of \rectype. + Segmentation fault has occurred in the following program on compile. __code csA(__rectype *p) { @@ -376,28 +355,4 @@ Here is the result. -\begin{table}[htpb] -\centering -\small -\begin{tabular}{|l|r|r|r|} \hline - & 10000 \\ \hline -using rectype & 0.7 \\ \hline -not use rectype & 0.7 \\ \hline -\end{tabular} -\caption{bench mark (in sec)} -\label{tab:gcc,compare} -\end{table} - -There was no difference in the results are as we predicted. - - --Conclusion - -We have designed and implemented Continuation based language for practical use. -We have implemented \rectype syntax in GCC for CbC. -Thereby Easily be able to write CbC program than previous. - -This \rectype implementation may be other problems. -If so, it is necessary to find and fix them on future. - -