この記事は琉大情報工学科（知能情報コース) Advent Calendar 2018 の16日目の記事です．
どうせなのでCasl2のエミュレーターでも書くかという気になりましたが，今日はドラゴンボールを見てしまったのでエミュレーターは途中までとなりました．ご了承下さい．
さて今日は一部界隈でまことしやかに盛り上がっている謎の言語CbCことContinuation Based Cについての話です．
ただしCbCは沼なので間違えている可能性があります．サイレント修正される可能性がありますがご了承下さい．
Continuation Based Cとは
Continuation Based C(以下CbC)とは継続を基本としたC言語の下位言語です．
C言語での関数呼び出しやfor文などのループ文をコードから消滅させ, 状態遷移単位でコードを書くことが出来る言語です．
応用例としては世界最速のgrepやGearsOS, Perl6処理系のCbCMoarVMなどが存在します．
現在はgcc及びllvm/clang上に実装した2種類が存在します．
C言語を使ってプログラミングをする場合，メモリのアロケートやエラーハンドリングなどを記述していく必要があります．
しかしこの処理は複雑かつエラーを発生させやすい為，通常の処理と分離して記述することが望ましいとされます．
これらの処理をMetaComputationと呼びます．
しかしC言語を使ったプログラミングである程度規模が大きいものを行おうとすると，これらの処理と通常の計算処理を分離して記述することは非常に難しいとされます．
CbCでは,関数の代わりにCodeSegmentとDataSegmentを基本単位として導入する事で，これらをやりやすくします．
CodeSegment
CbCでは関数の代わりにCodeSegmentを利用します．
CodeSegmentは関数よりも小さく，ステートメントよりも大きい単位となっています．
CodeSegmentを利用したCbCではループ文を持ちません．
これはCodeSegmentがコンパイラにおける基本ブロックと呼ばれる単位に該当する為です．
CodeSegmentはCの関数の代わりに __code と書くことで宣言出来ます．
これは __code という型が有るわけではなく, CbCプログラマからはCodeSegmentである事を示す指示子の様な役割を果たします．
__code 自体はCbCコンパイラではvoid型として扱います．
CodeSegmentからCodeSegmentへはCのgoto文を利用して遷移します．
この遷移はCの関数呼び出しとは異なり，callなどの命令を利用せずjmpを利用した軽量継続で行います．
実際にコード例を見てみましょう．
extern int printf(const char*,...);
int main (){
int data = 0;
goto cg1(&data);
}
__code cg1(int *datap){
(*datap)++;
goto cg2(datap);
}
__code cg2(int *datap){
(*datap)++;
printf("%d\n",*datap);
}
このコードはmain関数で設定した data = 0 をcg1と言うCodeSegmentに入力として渡します．
この時点ではCの世界からCbCの世界に突入する段階ですので, cg1自体はcallで呼び出されます．
cg1では受け取ったdataのアドレスからdataをインクリメントし data = 1 にします．
インクリメントの後 cg2 に軽量継続します．
cg2では同様にdataをインクリメントし, printするという流れです．
#include <stdio.h>
__code fact(int n, int result,__code (*print)()) {
if (n > 0) {
result *= n;
n--;
goto fact(n,result,print);
} else {
goto (*print)(result);
}
}
__code print_result(int result){
printf("result is %d\n",result);
}
int main(int argc, char** argv){
goto fact(20,0,print_result);
}
他には上記のような階上を求めるコードも書くことが可能です．
fact(int n, int result,__code (*print)()) の引数として __code のCodeSegment自体を渡しています．
この様にCodeSegmentの引数にはCodeSegment自体もいれることが可能です．
この引数の事をDataSegmentもしくはInterfaceと呼びます．
なぜ引数ではなくDataSegmentと呼称するかについては後述します．
軽量継続とは
先程から何回か出ている軽量継続とは何でしょうか．
軽量継続ではなく，継続とはSchemaなどの処理系には実装されています．
Wikipediaによると
継続は、前の状態を引き継ぐこと。持続、保持。 計算機科学における継続（けいぞく、continuation）とは、プログラムの実行においてある時点において評価されていない残りのプログラム（the rest of the program）を意味するものであり、手続き（procedure）として表現される
https://ja.wikipedia.org/wiki/%E7%B6%99%E7%B6%9A
詳しくは http://practical-scheme.net/docs/cont-j.html
つまり，CbCではCレベルで次の処理の命令をよりSchemaなどの関数型言語のように記述することが出来るインターフェイスを提供します．
この際にSchemaなどでは，現在の位置などを環境として保存する必要がありますが, CbCの場合そのあたりを保存しない為軽量な継続，つまり軽量継続と読んでいます．
うれしいところ
Cで軽量継続を使えると何が嬉しいのでしょうか．
それはCの関数呼び出しがコストがかかる事がまず挙げられます．
Cの関数呼び出しでは, 呼び出し側は引数を積み上げ，戻り番地のセーブを行い，
呼び出される方は局所変数を保存したり，スタックやフレームポインタを押し上げるなどの処理が必要となります．
これらを一切行わず，プログラムカウンタを変更するのみのjmp命令にCbCのgotoを利用したCodeSegmentは変換する事が可能です．
その為CodeSegmentを直接指定してgotoするなどの処理が書けるようになり，煩わしいfor文やcase-switch文をなくすことが可能です
Cでも末尾再帰と呼ばれる方法を利用すればこの方法が可能であり，実際CbCは内部的に末尾再帰のアルゴリズムを用いて最適化しています．
その為, CodeSegmentのDataSegment部分を同じにする事で，全ての命令がjmp命令にコンパイルされます．
jmp命令になるということは，CodeSegment間の引き渡しで引数がレジスタに乗ったまま移動されるということです．最高ですね．
つまりCodeSegmentの引数は入力のみではなく入出力としての意味を持つ為，引数ではなくData SegmentやInterfaceという呼び方をしています．
試しにFizzBuzzを書いてみます
#define __environment _CbC_environment
#define __return _CbC_return
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
__code fizzbuzz(int,int,char*,__code(),void*);
__code say2(int,int,char*,__code(),void*);
__code fizz(int,int,char*,__code(),void*);
__code buzz(int,int,char*,__code(),void*);
int main(void){
int n = 100;
fizzbuzz(1,n,"",__return,__environment);
return 0;
}
__code fizzbuzz(int i,int n,char* ret_result,__code(*return1)(),void *return1env) {
if ( i <= n ) {
goto fizz(i,n,ret_result,return1,return1env);
} else {
goto return1(0,return1env);
}
}
__code fizz(int i,int n,char* ret_result,__code(*return1)(),void *return1env) {
if (i % 3 == 0){
ret_result = "fizz";
} else {
ret_result = "";
}
goto buzz(i,n,ret_result,return1,return1env);
}
__code buzz(int i,int n,char* ret_result,__code(*result1)(),void *return1env) {
char *result;
result = (char *)malloc(15);
if (i % 5 == 0){
snprintf(result,9,"%s%s",ret_result,"buzz");
} else {
snprintf(result,8,"%s",ret_result);
}
goto say2(i,n,result,result1,return1env);
}
__code say2(int i,int n,char* ret_result,__code(*return1)(),void *return1env) {
if ( ret_result[0] == '\0'){
printf("%i : %i\n" ,i,i);
} else {
printf("%i:%s\n",i,ret_result);
}
goto fizzbuzz(i+1,n,"",return1,return1env);
}
CbCっぽく書くコツはDataSegmentをそろえる事です．
これを-Sをつけてアセンブラを見てみましょう．
cbclang -S fizzbuzz.cbc
.section __TEXT,__text,regular,pure_instructions
.macosx_version_min 10, 14
.globl _main..ret0
.p2align 4, 0x90
_main..ret0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq (%rsi), %rax
movl %edi, (%rax)
movq 8(%rsi), %rax
movq (%rax), %rbp
movq 8(%rax), %rsi
movq 16(%rax), %rsp
jmpq *%rsi
.cfi_endproc
.globl _main
.p2align 4, 0x90
_main:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rbx
subq $264, %rsp
.cfi_offset %rbx, -56
.cfi_offset %r12, -48
.cfi_offset %r13, -40
.cfi_offset %r14, -32
.cfi_offset %r15, -24
leaq -208(%rbp), %rax
leaq -252(%rbp), %rcx
leaq _main..ret0(%rip), %rdx
movq ___stack_chk_guard@GOTPCREL(%rip), %rsi
movq (%rsi), %rsi
movq %rsi, -48(%rbp)
movl $0, -212(%rbp)
movl $100, -216(%rbp)
movl -216(%rbp), %esi
movq %rdx, -224(%rbp)
movq -224(%rbp), %rdx
movq %rdx, -232(%rbp)
movq -232(%rbp), %rdx
movq %rcx, -248(%rbp)
movq %rax, -240(%rbp)
movq -240(%rbp), %rax
movq %rax, %rcx
movq %rbp, %rdi
movq %rdi, (%rax)
movq %rsp, %rdi
movq %rdi, 16(%rax)
leaq LBB1_8(%rip), %rax
movq %rax, 8(%rcx)
movl %esi, -268(%rbp)
movq %rdx, -280(%rbp)
xorl %eax, %eax
movl %eax, -284(%rbp)
LBB1_7:
movl -284(%rbp), %eax
movq -240(%rbp), %rcx
movq %rcx, %rdx
movq %rbp, %rsi
movq %rsi, (%rcx)
movq %rsp, %rsi
movq %rsi, 16(%rcx)
leaq LBB1_11(%rip), %rcx
movq %rcx, 8(%rdx)
movl %eax, -288(%rbp)
xorl %eax, %eax
movl %eax, -292(%rbp)
LBB1_10:
movl -292(%rbp), %eax
cmpl $0, %eax
je LBB1_2
movl -252(%rbp), %eax
movl %eax, -212(%rbp)
jmp LBB1_3
LBB1_2:
leaq -248(%rbp), %rax
movq %rax, -264(%rbp)
movq -264(%rbp), %rax
leaq L_.str(%rip), %rdx
movl $1, %edi
movl -268(%rbp), %esi
movq -280(%rbp), %rcx
movq %rax, %r8
callq _fizzbuzz
subq $8, %rsp
movl $0, -212(%rbp)
LBB1_3:
movl -212(%rbp), %eax
movq ___stack_chk_guard@GOTPCREL(%rip), %rcx
movq (%rcx), %rcx
movq -48(%rbp), %rdx
cmpq %rdx, %rcx
movl %eax, -296(%rbp)
jne LBB1_5
movl -296(%rbp), %eax
addq $264, %rsp
popq %rbx
popq %r12
popq %r13
popq %r14
popq %r15
popq %rbp
retq
LBB1_5:
callq ___stack_chk_fail
LBB1_8:
movl $1, %eax
movl %eax, -284(%rbp)
jmp LBB1_7
LBB1_11:
movl $1, %eax
movl %eax, -292(%rbp)
jmp LBB1_10
.cfi_endproc
.globl _fizzbuzz
.p2align 4, 0x90
_fizzbuzz:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
subq $48, %rsp
cmpl %esi, %edi
movl %esi, -4(%rbp)
movq %r8, -16(%rbp)
movq %rcx, -24(%rbp)
movq %rdx, -32(%rbp)
movl %edi, -36(%rbp)
jg LBB2_2
movl -36(%rbp), %edi
movl -4(%rbp), %esi
movq -32(%rbp), %rdx
movq -24(%rbp), %rcx
movq -16(%rbp), %r8
addq $48, %rsp
popq %rbp
jmp _fizz
LBB2_2:
xorl %eax, %eax
movb %al, %cl
movl %eax, %edi
movq -16(%rbp), %rsi
movb %cl, %al
movq -24(%rbp), %rdx
callq *%rdx
addq $48, %rsp
popq %rbp
retq $8
.cfi_endproc
.globl _fizz
.p2align 4, 0x90
_fizz:
.cfi_startproc
subq $56, %rsp
.cfi_def_cfa_offset 64
leaq L_.str.1(%rip), %rax
movl $3, %edx
movq %rax, 48(%rsp)
movl %edi, %eax
movl %edx, 44(%rsp)
cltd
movl 44(%rsp), %r9d
idivl %r9d
cmpl $0, %edx
movq 48(%rsp), %r10
movl %esi, 40(%rsp)
movq %r8, 32(%rsp)
movq %rcx, 24(%rsp)
movl %edi, 20(%rsp)
movq %r10, 8(%rsp)
je LBB3_2
leaq L_.str(%rip), %rax
movq %rax, 8(%rsp)
jmp LBB3_2
LBB3_2:
movq 8(%rsp), %rax
movl 20(%rsp), %edi
movl 40(%rsp), %esi
movq %rax, %rdx
movq 24(%rsp), %rcx
movq 32(%rsp), %r8
addq $56, %rsp
jmp _buzz
.cfi_endproc
.globl _buzz
.p2align 4, 0x90
_buzz:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
subq $64, %rsp
movl $15, %eax
movl %eax, %r9d
movl %edi, -4(%rbp)
movq %r9, %rdi
movl %esi, -8(%rbp)
movq %r8, -16(%rbp)
movq %rcx, -24(%rbp)
movq %rdx, -32(%rbp)
callq _malloc
movl $5, %esi
movl -4(%rbp), %r10d
movq %rax, -40(%rbp)
movl %r10d, %eax
cltd
idivl %esi
cmpl $0, %edx
jne LBB4_2
movl $9, %eax
movl %eax, %esi
xorl %edx, %edx
movl $15, %eax
movl %eax, %ecx
leaq L_.str.2(%rip), %r8
leaq L_.str.3(%rip), %rdi
movq -40(%rbp), %r9
movq %rdi, -48(%rbp)
movq %r9, %rdi
movq -32(%rbp), %r9
movq -48(%rbp), %r10
movq %r10, (%rsp)
movb $0, %al
callq ___snprintf_chk
movl %eax, -52(%rbp)
jmp LBB4_3
LBB4_2:
movl $8, %eax
movl %eax, %esi
xorl %edx, %edx
movl $15, %eax
movl %eax, %ecx
leaq L_.str.4(%rip), %r8
movq -40(%rbp), %rdi
movq -32(%rbp), %r9
movb $0, %al
callq ___snprintf_chk
movl %eax, -56(%rbp)
LBB4_3:
movl -4(%rbp), %edi
movl -8(%rbp), %esi
movq -40(%rbp), %rdx
movq -24(%rbp), %rcx
movq -16(%rbp), %r8
addq $64, %rsp
popq %rbp
jmp _say2
.cfi_endproc
.globl _say2
.p2align 4, 0x90
_say2:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
subq $64, %rsp
movsbl (%rdx), %eax
cmpl $0, %eax
movl %esi, -4(%rbp)
movq %r8, -16(%rbp)
movq %rcx, -24(%rbp)
movq %rdx, -32(%rbp)
movl %edi, -36(%rbp)
jne LBB5_2
leaq L_.str.5(%rip), %rdi
movl -36(%rbp), %esi
movl -36(%rbp), %edx
movb $0, %al
callq _printf
movl %eax, -40(%rbp)
jmp LBB5_3
LBB5_2:
leaq L_.str.6(%rip), %rdi
movl -36(%rbp), %esi
movq -32(%rbp), %rdx
movb $0, %al
callq _printf
movl %eax, -44(%rbp)
LBB5_3:
movl -36(%rbp), %eax
incl %eax
leaq L_.str(%rip), %rdx
movl %eax, %edi
movl -4(%rbp), %esi
movq -24(%rbp), %rcx
movq -16(%rbp), %r8
addq $64, %rsp
popq %rbp
jmp _fizzbuzz
.cfi_endproc
.section __TEXT,__cstring,cstring_literals
L_.str:
.space 1
L_.str.1:
.asciz "fizz"
L_.str.2:
.asciz "%s%s"
L_.str.3:
.asciz "buzz"
L_.str.4:
.asciz "%s"
L_.str.5:
.asciz "%i : %i\n"
L_.str.6:
.asciz "%i:%s\n"
.subsections_via_symbols
実際にCodeSegment同士はjmpで，mallocなどの関数呼び出しのみcallになっている事がわかります
~/w/c/S/cbc-sandbox » grep jmp fizzbuzz.s
jmpq *%rsi
jmp LBB1_3
jmp LBB1_7
jmp LBB1_10
jmp _fizz
jmp LBB3_2
jmp _buzz
jmp LBB4_3
jmp _say2
jmp LBB5_3
jmp _fizzbuzz
~/w/c/S/cbc-sandbox » grep call fizzbuzz.s
callq _fizzbuzz
callq ___stack_chk_fail
callq *%rdx
callq _malloc
callq ___snprintf_chk
callq ___snprintf_chk
callq _printf
callq _printf
試すには
試すには gccはこちら
clangはこちらを見ていただくと出来ます．
なおclangが容量をすごく取りますが，現状Mac os Mojaveではclangしかビルド出来ません...助けてくれ...
id:papixさんから, 「本編に出れる」と言われた時は嬉しかったし, Twitterを見た感じ皆さんに楽しんでいただいたようで非常に良かった．
id:cohalzさんとお会い出来たのが良かった．
思えばあの時から, YAPC::Tokyoが前を向かせて貰ったのだと思う．
id:utgwkkさんと初めてリアルで会えたのもいい体験だった．
id:ssabcireくんにTwitterで見ていて影響を受けたとか, 入学式の鹿さんに助けてもらったとか, 
id:kiryuanzuさんにエントリを見たとか言われた．
個人的にはそんなに頑張ってないし, やっているつもりも無かったのだが, そう言っていただけると嬉しかったし, 同時に何か不思議な気持ちになった．
id:mackee_wさんや
id:xtetsujiさんが待っていただいたのが嬉しかった．
id:codehexさんとまたお会い出来たし, 本当に様々な人に支えられているんだなと感じた．
この恩をいつか返せるように, そして新しくPerlやYAPCに出会った方に, 僕がしていただけたことを逆に出来るように, 今後もやっていきたいと思った．
id:anatofuz