Mercurial > hg > Papers > 2018 > ryokka-thesis
view final_main/chapter2.tex @ 5:eafc166804f3
fix Capter4.2,5,1
author | ryokka |
---|---|
date | Mon, 19 Feb 2018 18:44:59 +0900 |
parents | 12204a2c2eda |
children | 28f900230c26 |
line wrap: on
line source
\chapter{Continuation based C} %% CbCとはなにか?どのようなものか?どのようにしてなりたっているか? % CodeGearが何なのか?とかの話は1章。すでに CodeGearが存在している前提で % 書いてる Continuation based C (以下 CbC )は当研究室で開発しているプログラミング言語である。 CbC では処理を CodeGear 、処理に使うデータを DataGear と呼ばれる単位で記述 しプログラムを構成する。 本章は CbC について説明する。 \section{CodeGear と DataGear} %% どういう概念? どうしてそうするの? どうやってつかうの? 本研究室では検証しやすいプログラムの単位として CodeGear と DataGear という 単位を用いるプログラミングスタイルを提案している。 CodeGear とはプログラムの処理部分である。 DataGear は CodeGear で扱うデータの単位であり、処理に必要なデータが全て入って いる。 CodeGear の入力となる DataGear を Input DataGear と呼び、 出力は Output DataGear と呼ぶ。 CodeGear は他の CodeGear と継続することでプログラムを構成する。 図\ref{fig:csds}のように Input DataGear を受け取り、 CodeGear で Output DataGear に変更を加えることでプログラムを記述していく。 % CS,DSの図 \begin{figure}[htpb] \begin{center} \scalebox{0.55}{\includegraphics{fig/csds.pdf}} \end{center} \caption{CodeGear と DataGear} \label{fig:csds} \end{figure} % \section{環境付き継続} % \label{sec:withEnv} % 環境付き継続の話はいらないよね \section{CbC での CodeGear と DataGear } %% 例題 %% Metaな話は今書いてもどうせ使わないので検証に使える〜くらいで置いておく? %% 部分は生成でき、そこで検証用の動作をする感じでは?hora理論使ったりするといい %% かんじにできるんじゃないかな % 流れ CbCではどうやってCodeGearつかうの?他との違いは?軽量継続って何?ルー % プ処理とかってどうするの? Metaってなに?なるほど?ってかんじ CbC での簡単な記述例をソースコード\ref{code_simple}、流れを図\ref{fig:code_simple}に示 す。CbC では CodeGear を$\_\_$code キーワードを指定する。その際、Input DataGear は関数の引数として定義される。 CodeGear は継続で次の CodeGear に遷移するために関数末尾で goto キーワードの後に CodeGear 名と Input DataGear を指定する必要がある。 ソースコード\ref{code_simple}では cs0、 cs1 が CodeGear で a+b が cs0 の Output DataGear であり、 cs1 の Input DataGear である。 \begin{lstlisting}[frame=lrbt,label=code_simple,caption={\footnotesize CodeGear の継続の例}] __code cs0(int a, int b){ goto cs1(a+b); } __code cs1(int c){ goto cs2(c); } \end{lstlisting} \begin{figure}[htpb] \begin{center} \includegraphics{fig/codesegment.pdf} \end{center} \caption{ソースコード\ref{code_simple}の流れ} \label{fig:code_simple} \end{figure} CbC の継続は、呼び出し元の情報を持たずに処理を続ける。この継続を軽量継続と呼ぶ。 ソースコード\ref{code_simple}は cs0 から cs1 へ継続した後、 cs0 には戻らずに次の継 続に指定された CodeGear へ継続する。 CbC でのループ処理の記述例をソースコード\ref{factorial}、流れを図\ref{fig:factorial}に示 す。 軽量継続では関数呼び出しのスタックは存在しないが、ソースコード\ref{factorial}の ように計算中の値を DataGear で持つことでループ処理を行なうこともできる。 \begin{lstlisting}[frame=lrbt,label=factorial,caption={\footnotesize 階乗を求め る CbC プログラムの例}] __code print_factorial(int prod) { printf("factorial = %d\n",prod); exit(0); } __code factorial0(int prod, int x) { if ( x >= 1) { goto factorial0(prod*x, x-1); }else{ goto print_factorial(prod); } } __code factorial(int x) { goto factorial0(1, x); } int main(int argc, char **argv) { int i; i = atoi(argv[1]); goto factorial(i); } \end{lstlisting} \begin{figure}[htpb] \begin{center} \scalebox{0.8}{\includegraphics{fig/factorial.pdf}} \end{center} \caption{階乗を求める CbC プログラムの流れ} \label{fig:factorial} \end{figure} \section{メタ計算} % メタ計算の論文引用どうするかな… % メタプログラミング~系の本とかもいれていいのかな メタ計算(リフレクション)とは、対象とするレベルとメタなレベルを分離し、対象レベルでの推論や計算に 関するメタな情報をメタレベルで明示的に記述し操作する。 メタ計算(自己反映計算)\cite{weko_5056_1} とはプログラムを記述する際に通常の処理 と分離し、他に記述しなければならない処理である。例えばプログラム実行時のメモリ管 理やスレッド管理、資源管理等の計算がこれに当たる。 % \section{Meta CodeGear とMeta DataGear} % CbC % \section{Interface} % Interface では使用する DataGear とそれに対する処理を行う CodeGear の集合をま % とめて定義する。 % \lstinputlisting[label=src:interface, caption=CbCでのStack-Interfaceの記述] {src/interface.cbc} % DataGear に対して何らかの操作(API)を行う CodeGear とその % CodeGear で使われる DataGear の集合を抽象化した メタレベルの DataGear % として定義される。 % Interface を記述することでデータ構造の api と DataGear の結びつきを高め、呼び出しが容易になる。 \section{Context} CbC で DataGear を扱う際、 Context と呼ばれる接続可能な CodeGear、 DataGear のリ スト、Temporal DataGear のためのメモリ空間等を持っている Meta DataGearである。 CbC で必要な CodeGear 、 DataGear を参照する際は Context を通してアクセスする必 要がある。 \section{stub CodeGear} CodeGear が必要とする DataGear を取り出す際、 Context を通す必要がある。 しかし、 Context を直接扱えるようにするのは信頼性を損なう。そのため CbC では Context を通して必要なデータを取り出して次の Code Gear に接続する stub CodeGear を定義している。CodeGear は stub CodeGear を介してのみ必要な DataGear へアクセス することができる。 stub CodeGear は CodeGear 毎に生成され、次の CodeGear へと接 続される。 stub CodeGear は CodeGear の Meta CodeGear に当たる。 \section{CbCによる Interface の記述と継続} CodeGear は通常の関数と比べ、細かく分割されるためメタ計算をより柔軟に記述でき る。 CodeGear 、 DataGear にはそれぞれメタレベルとして、 Meta CodeGear 、 Meta DataGear が存在する。 CbC で実装していると、stub CodeGear の記述が煩雑になることが分かった。 そのため 既存の実装を モジュールとして扱うため Interface という仕組みを導入した。 DataGear に対して何らかの操作(API)を行う CodeGear とその CodeGear で使われる DataGear の集合を抽象化した メタレベルの DataGear として定義される。 % interface は データ構造に record で interface 名を列挙し、実際の動作をする関数と紐付けている。使用する際は、$ DataName->InterfaceFunk $のように使用する。 例として CbC による Stack Interface のソースコード(\ref{src:interface}, \ref{src:interface-real})がある。Stack への push 操作に注目して見ると 実態は SingleLinkedStack の push であることが\ref{src:interface-real}で分 かる。実際の SingleLinkedStack の push では Stack をユーザーが指定することができ るが、 Interface として実装した Stack では push 先の Stack が stackImpl として扱 われている。この stackImpl は$ Stack->push $で呼ばれた時の Stack と同じであり、 実行時にユーザーが異なる Stack に push することを防ぐことができる。 このように Interface 記述をすることで CbC で通常記述する必要がある一定の部分を省略し呼び出 しが容易になる。 % stack の push は引数を一つ取り、 stack->push のように呼び出すことでその stack 自 % 身に引数を push し stack を更新することで stack に push 操作を行う。 \lstinputlisting[label=src:interface, caption=CbCでのStack-Interfaceの記述] {src/interface.cbc} \lstinputlisting[label=src:interface-real, caption=CbCでのStack-Interfaceの実装] {src/singleLinkedStackInterface.cbc} % そのへんのSourceをたくさんばらまく。 % 書かずにAgda側でそういうのあるんだけど〜ってしてAgda側で実装したよ。って書くの % はあり?あんまり話すことがががが