継続を基本とするC言語CbCのご紹介

この記事は琉大情報工学科(知能情報コース) 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しかビルド出来ません...助けてくれ...