Continuation based Cを試す

Continuation based Cとは

以下、長いので略称のCbCと書きます。

状態遷移記述に向いたプログラミング言語 CbC の開発
C 言語における関数呼び出しやfor 文・while 文を排除し，状態遷移単位(code) での処理を記述できる言語の開発をしてます．
https://ie.u-ryukyu.ac.jp/%E5%AD%A6%E7%A7%91%E7%B4%B9%E4%BB%8B/%E7%A0%94%E7%A9%B6%E5%AE%A4%E7%B4%B9%E4%BB%8B/%E4%B8%A6%E5%88%97%E7%A0%94%E7%A9%B6%E5%AE%A4%EF%BC%88%E6%B2%B3%E9%87%8E%E7%A0%94%EF%BC%89/

詳しくはこの辺の論文を読むとよさそう
http://www.ie.u-ryukyu.ac.jp/~kono/papers.html

CbCで拡張されてる言語機能

__code型として通常の関数のような形で処理の単位を宣言できる。
goto文が拡張されていて__code型の処理を呼び出せる。
gotoで__codeを呼び出す際に通常の関数のように引数を渡せる。

嬉しみ(だと理解している部分)

• gotoと違い明示的に引数が渡せる
• __code型にしかgotoできない(無闇矢鱈にジャンプ出来ない)
• 普通の関数呼び出しに近くて読みやすい、書きやすい
• 末尾再帰最適化しなくてもjmpになる
• jmpになるので効率的
  • call/retがない
  • __codeを呼び出すと戻ることはないためその__code内で使った局所変数が必要なくなる
  • __codeを呼び出した場所に戻ることはないため戻り先のアドレスを覚えておく必要もない
  • __codeに渡された引数も取っておく必要がない
• 引数のインターフェイスが合っていればほとんどの引数をレジスタの上に乗せたまま次の__codeを呼び出せるため効率的
• setjmp/longjmpのように元に戻るための色々を行わないため軽量? (setjmp/longjmpで実装してるコンパイラもある?(このへんよくわかってない))¹

CbC向けの変更が入ったGCCをビルドする

Wikiを参考にする
http://www.cr.ie.u-ryukyu.ac.jp/~game/pukiwiki/index.php?GCC

今回は~/local以下にインストールする

% mkdir -p ~/local
% ghq get http://firefly.cr.ie.u-ryukyu.ac.jp/hg/CbC/CbC_gcc/
% cd ~/src/firefly.cr.ie.u-ryukyu.ac.jp/hg/CbC/CbC_gcc
% ./configure CFLAGS="-O0 -g3" --prefix ~/local --disable-bootstrap --disable-nls --enable-languages=c --enable-checking

FizzBuzz書いてみた

はい

fizzbuzz.cbc

#define __environment _CbC_environment
#define __return _CbC_return

#include <stdio.h>

typedef __code(*main_ret_code_t)(int, void *env);

__code fizzbuzz(int n, int max, main_ret_code_t ret, void *env);
__code fizz(int n, int max, main_ret_code_t ret, void *env);
__code buzz(int n, int max, const char *fizz, main_ret_code_t ret, void *env);
__code print_fizzbuzz(int n, int max, const char *fizz, const char *buzz, main_ret_code_t ret, void *env);

int main(void){
  goto fizzbuzz(1, 100, __return, __environment);
}

__code fizzbuzz(int n, int max, main_ret_code_t ret, void *env) {
  if (n > max) goto ret(0, env);

  goto fizz(n, max, ret, env);
}

__code fizz(int n, int max, main_ret_code_t ret, void *env) {
  if (n % 3 == 0) {
    goto buzz(n, max, "Fizz", ret, env);
  } else {
    goto buzz(n, max, "", ret, env);
  }
}

__code buzz(int n, int max, const char *fizz, main_ret_code_t ret, void *env) {
  if (n % 5 == 0) {
    goto print_fizzbuzz(n, max, fizz, "Buzz", ret, env);
  } else {
    goto print_fizzbuzz(n, max, fizz, "", ret, env);
  }
}

__code print_fizzbuzz(int n, int max, const char *fizz, const char *buzz, main_ret_code_t ret, void *env) {
  if (*fizz || *buzz) {
    printf("%s%s\n", fizz, buzz);
  } else {
    printf("%d\n", n);
  }

  goto fizzbuzz(n + 1, max, ret, env);
}

jmpになっているのか確認する

なってるっぽい

% ~/local/bin/gcc -S fizzbuzz.cbc && cat fizzbuzz.s | grep call && cat fizzbuzz.s | grep jmp
	call	fizzbuzz
	call	printf
	call	printf
	jmp	*%rdx
	jmp	.L8
	jmp	.L3
	jmp	*%rax
	jmp	fizz
	jmp	buzz
	jmp	buzz
	jmp	print_fizzbuzz
	jmp	print_fizzbuzz
	jmp	.L21
	jmp	fizzbuzz

同じような感じのFizzBuzzをCで書いた

#include <stdio.h>

void fizzbuzz(int n, int max);
void fizz(int n, int max);
void buzz(int n, int max, const char *fizz_s);
void print_fizzbuzz(int n, int max, const char *fizz_s, const char *buzz_s);

int main(void){
  fizzbuzz(1, 100);
  return 0;
}

void fizzbuzz(int n, int max) {
  if (n > max) {
    return;
  }

  fizz(n, max);
}

void fizz(int n, int max) {
  if (n % 3 == 0) {
    buzz(n, max, "Fizz");
  } else {
    buzz(n, max, "");
  }
}

void buzz(int n, int max, const char *fizz_s) {
  if (n % 5 == 0) {
    print_fizzbuzz(n, max, fizz_s, "Buzz");
  } else {
    print_fizzbuzz(n, max, fizz_s, "");
  }
}

void print_fizzbuzz(int n, int max, const char *fizz_s, const char *buzz_s) {
  if (*fizz_s || *buzz_s) {
    printf("%s%s\n", fizz_s, buzz_s);
  } else {
    printf("%d\n", n);
  }

  fizzbuzz(n + 1, max);
}

こちらも確認してみる

% ~/local/bin/gcc -S fizzbuzz.c && cat fizzbuzz.s | grep call && cat fizzbuzz.s | grep jmp 
	call	fizzbuzz
	call	fizz
	call	buzz
	call	buzz
	call	print_fizzbuzz
	call	print_fizzbuzz
	call	printf
	call	printf
	call	fizzbuzz
	jmp	.L3
	jmp	.L10
	jmp	.L14
	jmp	.L18

callだー

最適化オプション(-O2)渡したとき

末尾再帰最適化が効いてるのかどっちもjmpになった。

速度の評価

できるほどの規模のプログラムを書いてない／(^o^)＼

使いどころ

状態遷移の各状態を__codeとして表現できる。
__code間の移動は効率的に行われる。
そのため、状態遷移が多く行われるようなプログラムを機械的に生成するのに適しているっぽい。
http://sinya8282.sakura.ne.jp/etc/xhago/

余談: LLVM版

Wikiを参考にビルドしたけどビルド時間がかなりかかるのとディスク容量が尽きて断念、以下メモ書き

% ghq get http://firefly.cr.ie.u-ryukyu.ac.jp/hg/CbC/CbC_llvm/
% mkdir -p ~/local/cbc_llvm
% cd ~/local/cbc_llvm
% cmake -DLLVM_TARGETS_TO_BUILD="X86" ~/src/firefly.cr.ie.u-ryukyu.ac.jp/hg/CbC/CbC_llvm
% cmake --build .

1. でもsetjmp/longjmp使った実装するといろんなコンパイラ上で実装できて便利みたいなの書いてた気がする、このへんはコンパイラの実装ちゃんと追えていない... ↩