この記事は琉大情報工学科（知能情報コース) 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
試しに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 ## -- Begin function main..ret0 .p2align 4, 0x90 _main..ret0: ## @main..ret0 .cfi_startproc ## %bb.0: ## %entry 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 ## -- End function .globl _main ## -- Begin function main .p2align 4, 0x90 _main: ## @main .cfi_startproc ## %bb.0: ## %entry 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 ## imm = 0x108 .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) ## 4-byte Spill movq %rdx, -280(%rbp) ## 8-byte Spill #EH_SjLj_Setup LBB1_8 ## %bb.6: ## %entry xorl %eax, %eax movl %eax, -284(%rbp) ## 4-byte Spill LBB1_7: ## %entry movl -284(%rbp), %eax ## 4-byte Reload 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) ## 4-byte Spill #EH_SjLj_Setup LBB1_11 ## %bb.9: ## %entry xorl %eax, %eax movl %eax, -292(%rbp) ## 4-byte Spill LBB1_10: ## %entry movl -292(%rbp), %eax ## 4-byte Reload cmpl $0, %eax je LBB1_2 ## %bb.1: ## %if.then movl -252(%rbp), %eax movl %eax, -212(%rbp) jmp LBB1_3 LBB1_2: ## %if.end leaq -248(%rbp), %rax movq %rax, -264(%rbp) movq -264(%rbp), %rax leaq L_.str(%rip), %rdx movl $1, %edi movl -268(%rbp), %esi ## 4-byte Reload movq -280(%rbp), %rcx ## 8-byte Reload movq %rax, %r8 callq _fizzbuzz subq $8, %rsp movl $0, -212(%rbp) LBB1_3: ## %return 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) ## 4-byte Spill jne LBB1_5 ## %bb.4: ## %SP_return movl -296(%rbp), %eax ## 4-byte Reload addq $264, %rsp ## imm = 0x108 popq %rbx popq %r12 popq %r13 popq %r14 popq %r15 popq %rbp retq LBB1_5: ## %CallStackCheckFailBlk callq ___stack_chk_fail LBB1_8: ## Block address taken ## %entry movl $1, %eax movl %eax, -284(%rbp) ## 4-byte Spill jmp LBB1_7 LBB1_11: ## Block address taken ## %entry movl $1, %eax movl %eax, -292(%rbp) ## 4-byte Spill jmp LBB1_10 .cfi_endproc ## -- End function .globl _fizzbuzz ## -- Begin function fizzbuzz .p2align 4, 0x90 _fizzbuzz: ## @fizzbuzz .cfi_startproc ## %bb.0: ## %entry 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) ## 4-byte Spill movq %r8, -16(%rbp) ## 8-byte Spill movq %rcx, -24(%rbp) ## 8-byte Spill movq %rdx, -32(%rbp) ## 8-byte Spill movl %edi, -36(%rbp) ## 4-byte Spill jg LBB2_2 ## %bb.1: ## %if.then movl -36(%rbp), %edi ## 4-byte Reload movl -4(%rbp), %esi ## 4-byte Reload movq -32(%rbp), %rdx ## 8-byte Reload movq -24(%rbp), %rcx ## 8-byte Reload movq -16(%rbp), %r8 ## 8-byte Reload addq $48, %rsp popq %rbp jmp _fizz ## TAILCALL LBB2_2: ## %if.else xorl %eax, %eax movb %al, %cl movl %eax, %edi movq -16(%rbp), %rsi ## 8-byte Reload movb %cl, %al movq -24(%rbp), %rdx ## 8-byte Reload callq *%rdx addq $48, %rsp popq %rbp retq $8 .cfi_endproc ## -- End function .globl _fizz ## -- Begin function fizz .p2align 4, 0x90 _fizz: ## @fizz .cfi_startproc ## %bb.0: ## %entry subq $56, %rsp .cfi_def_cfa_offset 64 leaq L_.str.1(%rip), %rax movl $3, %edx movq %rax, 48(%rsp) ## 8-byte Spill movl %edi, %eax movl %edx, 44(%rsp) ## 4-byte Spill cltd movl 44(%rsp), %r9d ## 4-byte Reload idivl %r9d cmpl $0, %edx movq 48(%rsp), %r10 ## 8-byte Reload movl %esi, 40(%rsp) ## 4-byte Spill movq %r8, 32(%rsp) ## 8-byte Spill movq %rcx, 24(%rsp) ## 8-byte Spill movl %edi, 20(%rsp) ## 4-byte Spill movq %r10, 8(%rsp) ## 8-byte Spill je LBB3_2 ## %bb.1: ## %if.else leaq L_.str(%rip), %rax movq %rax, 8(%rsp) ## 8-byte Spill jmp LBB3_2 LBB3_2: ## %if.end movq 8(%rsp), %rax ## 8-byte Reload movl 20(%rsp), %edi ## 4-byte Reload movl 40(%rsp), %esi ## 4-byte Reload movq %rax, %rdx movq 24(%rsp), %rcx ## 8-byte Reload movq 32(%rsp), %r8 ## 8-byte Reload addq $56, %rsp jmp _buzz ## TAILCALL .cfi_endproc ## -- End function .globl _buzz ## -- Begin function buzz .p2align 4, 0x90 _buzz: ## @buzz .cfi_startproc ## %bb.0: ## %entry 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) ## 4-byte Spill movq %r9, %rdi movl %esi, -8(%rbp) ## 4-byte Spill movq %r8, -16(%rbp) ## 8-byte Spill movq %rcx, -24(%rbp) ## 8-byte Spill movq %rdx, -32(%rbp) ## 8-byte Spill callq _malloc movl $5, %esi movl -4(%rbp), %r10d ## 4-byte Reload movq %rax, -40(%rbp) ## 8-byte Spill movl %r10d, %eax cltd idivl %esi cmpl $0, %edx jne LBB4_2 ## %bb.1: ## %if.then 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 ## 8-byte Reload movq %rdi, -48(%rbp) ## 8-byte Spill movq %r9, %rdi movq -32(%rbp), %r9 ## 8-byte Reload movq -48(%rbp), %r10 ## 8-byte Reload movq %r10, (%rsp) movb $0, %al callq ___snprintf_chk movl %eax, -52(%rbp) ## 4-byte Spill jmp LBB4_3 LBB4_2: ## %if.else 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 ## 8-byte Reload movq -32(%rbp), %r9 ## 8-byte Reload movb $0, %al callq ___snprintf_chk movl %eax, -56(%rbp) ## 4-byte Spill LBB4_3: ## %if.end movl -4(%rbp), %edi ## 4-byte Reload movl -8(%rbp), %esi ## 4-byte Reload movq -40(%rbp), %rdx ## 8-byte Reload movq -24(%rbp), %rcx ## 8-byte Reload movq -16(%rbp), %r8 ## 8-byte Reload addq $64, %rsp popq %rbp jmp _say2 ## TAILCALL .cfi_endproc ## -- End function .globl _say2 ## -- Begin function say2 .p2align 4, 0x90 _say2: ## @say2 .cfi_startproc ## %bb.0: ## %entry 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) ## 4-byte Spill movq %r8, -16(%rbp) ## 8-byte Spill movq %rcx, -24(%rbp) ## 8-byte Spill movq %rdx, -32(%rbp) ## 8-byte Spill movl %edi, -36(%rbp) ## 4-byte Spill jne LBB5_2 ## %bb.1: ## %if.then leaq L_.str.5(%rip), %rdi movl -36(%rbp), %esi ## 4-byte Reload movl -36(%rbp), %edx ## 4-byte Reload movb $0, %al callq _printf movl %eax, -40(%rbp) ## 4-byte Spill jmp LBB5_3 LBB5_2: ## %if.else leaq L_.str.6(%rip), %rdi movl -36(%rbp), %esi ## 4-byte Reload movq -32(%rbp), %rdx ## 8-byte Reload movb $0, %al callq _printf movl %eax, -44(%rbp) ## 4-byte Spill LBB5_3: ## %if.end movl -36(%rbp), %eax ## 4-byte Reload incl %eax leaq L_.str(%rip), %rdx movl %eax, %edi movl -4(%rbp), %esi ## 4-byte Reload movq -24(%rbp), %rcx ## 8-byte Reload movq -16(%rbp), %r8 ## 8-byte Reload addq $64, %rsp popq %rbp jmp _fizzbuzz ## TAILCALL .cfi_endproc ## -- End function .section __TEXT,__cstring,cstring_literals L_.str: ## @.str .space 1 L_.str.1: ## @.str.1 .asciz "fizz" L_.str.2: ## @.str.2 .asciz "%s%s" L_.str.3: ## @.str.3 .asciz "buzz" L_.str.4: ## @.str.4 .asciz "%s" L_.str.5: ## @.str.5 .asciz "%i : %i\n" L_.str.6: ## @.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 ## TAILCALL jmp LBB3_2 jmp _buzz ## TAILCALL jmp LBB4_3 jmp _say2 ## TAILCALL jmp LBB5_3 jmp _fizzbuzz ## TAILCALL
~/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しかビルド出来ません...助けてくれ...
