Mercurial > hg > Papers > 2018 > nozomi-master

annotate paper/cbc.tex @ 14:6bf2e0196a1e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add goto.cbc and goto.pdf
author atton <atton@cr.ie.u-ryukyu.ac.jp>
date Thu, 19 Jan 2017 11:29:13 +0900
parents 99a9be7e6bc9
children 6dedd4ed6b6d
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
12
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \chapter{Continuation based C}
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 Continuation based C (CbC)は当研究室で開発しているプログラミング言語であり、OSや組み込みソフトウェアの開発を主な対象としている。
13
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
4 CbC は C言語の下位の言語であり、構文はほぼC言語と同じものを持つが、よりアセンブラに近い形でプログラムを記述する。
12
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 CbC は CodeSegment と呼ばれる単位で処理を定義し、それらを組み合わせることにでプログラム全体を構成する。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 データの単位は DataSegment と呼ばれる単位で定義し、それら CodeSegment によって変更していくことでプログラムの実行となる。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 CbC の処理系には llvm/clang による実装\cite{110009766999} と gcc\cite{weko_82695_1}による実装などが存在する。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
13
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
9 % {{{ section: CodeSegment と DataSegment
12
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 \section{CodeSegment と DataSegment}
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 本研究室では検証を行ないやすいプログラムの単位として CodeSegment と DataSegment を用いるプラグラミングスタイルを提案している。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 CodeSegment は処理の単位である。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 入力を受け取り、それに対して処理を行なった後を出力を行なう。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 また、CodeSegment は他の CodeSegment と組み合わせることが可能である。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 あるCodeSegment A を CodeSegment B に接続した場合、 A の出力は B の入力となる。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 % TODO: figure (cs A . cs B)
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 DataSegment は CodeSegment が扱うデータの単位であり、処理に必要なデータが全て入っている。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 CodeSegment の入力となる DataSegment は Input DataSegment と呼ばれ、出力は Output DataSegment と呼ばれる。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 CodeSegment A と CodeSegment B を接続した時、A の Output DataSegment は B の入力 Input DataSegment となる。
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 % TODO: figure (cs A --(ds)--> cs B)
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
13
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
27 % }}}
12
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 \section{Continuation based C における CodeSegment と DataSegment}
14
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
30 最も基本的な CbC のソースコードをリスト\ref{src:goto}に、ソースコードが実行される流れを図\ref{fig:goto}に示す。
13
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
31 Continuation based C における CodeSegment は返り値を持たない関数として表現される。
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
32 CodeSegment を定義するためには、C言語の関数を定義する構文の返り値の型部分に \verb/__code/ キーワードを指定する。
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
33 Input DataSegment は関数の引数として定義される。
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
34 次の CodeSegment へ処理を移す際には \verb/goto/ キーワードの後に CodeSegment 名と Input DataSegment を指定する。
14
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
35 処理の移動を軽量継続と呼び、リスト\ref{src:goto}内の \verb/goto cs1(a+b);/ がこれにあたる。
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
36 この時の \verb/(a+b)/ が次の CodeSegment である cs1 の Input DataSegment となる cs0 の Output DataSegment である。
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
37
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
38 \lstinputlisting[label=src:goto, caption=CodeSegment の軽量継続] {src/goto.cbc}
12
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
14
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
40 \begin{figure}[htbp]
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
41 \begin{center}
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
42 \includegraphics[scale=1.0]{fig/goto.pdf}
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
43 \caption{CodeSegment の軽量継続}
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
44 \label{fig:goto}
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
45 \end{center}
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
46 \end{figure}
13
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
47
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
48 % TODO: scheme ref?
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
49 Scheme などの call/cc といった継続はトップレベルから現在までの位置を環境として保持する。
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
50 通常環境とは関数の呼び出しスタックの状態である。
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
51 CbC の軽量継続は呼び出し元の情報を持たないため、スタックを破棄しながら処理を続けていく。
14
6bf2e0196a1e Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
52 よって、リスト\ref{src:goto} のプログラムでは cs0 から cs1 へと継続した後にcs0 へ戻ることはできない。
13
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
53
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
54 % TODO: factorial
99a9be7e6bc9 Update cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
55
12
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 \section{MetaCodeSegment と MetaDataSegment}
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 \section{GearsOS}
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 \section{メタ計算ライブラリ akasha}
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 \section{akasha を用いた赤黒木の実装の検証}
1c9fc852e4ce Add cbc description
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62