title: CbC 言語による OS 記述 
author: Mitsuki Miyagi
profile:
lang: Japanese
code-engine: coderay

# メタ計算の重要性
- プログラムを記述する際、ノーマルな処理の他に、メモリ管理やスレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。これらの計算をメタ計算と呼ぶ。
- メタ計算はノーマルな計算から切り離して記述したい。
- そのためには処理を細かく分割する必要があるが、関数やクラスなどの単位は容易に分割できない。
- そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。

# Code Gear と Data Gear
- Code Gear とはプログラムの処理の単位である。
- Code Gear は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
- Data Gear はデータの単位であり、Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。

# Continuation based C (CbC)
- Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。
- CbC では Code Gear は \_\_code という型を持つ関数の構文で定義される。
- Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
- goto の後に Code Gear 名と引数を並べて、次の Code Gear の遷移を記述する。
- この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。
```Code_Gear
__code cs0(int a, int b){
  goto cs1(a+b);
}

__code cs1(int c){
  goto cs2(c);
}
```

# Gears OS
- Gears OS は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。
- 並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
- またGears OS ではメタ計算を Meta Code Gear、Meta Data Gear で表現する。
- Meta Code Gear はノーマルの Code Gear の直後に遷移され、メタ計算を実行する。
- Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。

# CbC による Gears OS 記述の問題点
- Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
- 本研究ではこれらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
- そのためのプロトタイプとして perl スクリプトを作成した。

# Context
- Gears OS には Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
- Gears OSは必要なCode/DataGearに参照したい場合、このContext を通す必要がある。

<img src="./fig/context.svg" alt="message" width="800" >

# Gearef、GearImpl
- Context には Allocation で生成した Data Gear へのポインタが格納されている。
- Code Gear が Context にアクセスする際、ポインタを使用してデータを取り出すためコードが煩雑になってしまう。

```
__code clearSingleLinkedStack_stub(struct Context* context) {
        SingleLinkedStack* stack = (SingleLinkedStack*)context->data[D_Stack]->Stack.stack->Stack.stack;
        enum Code next = context->data[D_Stack]->Stack.next;
        goto clearSingleLinkedStack(context, stack, next);
}
```

- そこで Code Gear がデータを参照するための Gearef と GearImpl というマクロを定義した。

```
__code clearSingleLinkedStack_stub(struct Context* context) {
        SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack);
        enum Code next = Gearef(context, Stack)->next;
        goto clearSingleLinkedStack(context, stack, next);
}
```

# stub Code Gear
- Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。
- しかし、メタであるContext をノーマルレベルの Code Gear から直接アクセスするのはよろしくない。
- そこで Context から必要なデータを取り出して Code Gear に接続する、メタレベルの stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。 

```stub
__code clearSingleLinkedStack(struct Context *context,struct SingleLinkedStack* stack,enum Code next) {
    stack->top = NULL;
    goto meta(context, next);
}

__code clearSingleLinkedStack_stub(struct Context* context) {
        SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack);
        enum Code next = Gearef(context, Stack)->next;
        goto clearSingleLinkedStack(context, stack, next);
}
```

# interface の記述
- interface を記述することで Context を通して Code Gear が参照できるようになった。
- create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。
- return で interface を返し、その先で inter face の持つ Code Gear へと継続できるようになる。
```impl
Stack* createSingleLinkedStack(struct Context* context) {
    struct Stack* stack = new Stack();
    struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
    stack->stack = (union Data*)singleLinkedStack;
    singleLinkedStack->top = NULL;
    stack->push = C_pushSingleLinkedStack;
    stack->pop  = C_popSingleLinkedStack;
    stack->pop2  = C_pop2SingleLinkedStack;
    stack->get  = C_getSingleLinkedStack;
    stack->get2  = C_get2SingleLinkedStack;
    stack->isEmpty = C_isEmptySingleLinkedStack;
    stack->clear = C_clearSingleLinkedStack;
    return stack;
}
```

# Context、stub Code Gear の自動生成
- Gears OS ではノーマルレベルの計算の他に Context や stub などのメタ計算を記述する必要がある。
- 現在の CbC で Gears OS を記述すると、このメタ計算の記述も行わなくてはならず、これには多くの労力を要する。
- この記述を助けるために Context を生成する generate_context と stub Code Gear を生成する generate_stub を perl スクリプトで作成した。

# stub Code Gear の生成
- stub Code Gear は Code Gear 間の継続に挟まれ、Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
- stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
- generate_stub は指定された cbc ファイルの __code型である Code Gear を取得。
- 引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
- cbc ファイルのから、生成した stub Code Gear を加えて、c ファイルを生成する。

# Context の生成
- Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。 
- generate_context は context.h から Data Gear、c ファイルから Code Gear を取得。
- 取得した Code/Data Gear の enum の定義は enumCode.h、enumData.h に生成される。
- generate_context は取得した Code/Data Gear から Context の生成を行うコードを生成する。
- これらを自動生成することで Gears OS の記述量を約半分にすることができます。
<img src="./fig/generate_context.svg" alt="message" width="800" >

# 今後の課題
- 本研究では interface の記述、CbC ファイルから Gears OS の記述に必要な Context と stub の生成を行う perl スクリプトの生成を行なった。
- これにより Gears OS のコードの煩雑さは改善され、ユーザーは Context への接続を意識する必要がなくなった。
- 今後の課題は Code Gear からメタ計算を行う meta Code Gear を生成できるようにし、ユーザーがメタレベルの処理を意識せずにコードを記述できるようにする。
- また、今回 perl スクリプトによって Context や stub の生成を行なったが、LLVM/clang 上で実装しコンパイラで直接 CbC を実行できるようにすることを目的とする。