CPS変換
先週（2023/12)の #定期ミートアップ で聞いたんだけど、PenはCPS変換してTokioのスケジューラに載せてるらしい Shiikaで同じことができないか
code:a.mmd
sequenceDiagram
participant T as Tokio Scheduler
participant S as Shiika
participant R as Rust
participant TT as Tokio library
T->>S: start
Note over S: I/O operation
S->>R: File＃read
R->>TT: tokio::fs
TT->>R: core::task::Poll
R->>S:
S->>T: (continuation)
デメリットはなんだろう。RustからShiikaメソッドを呼ぶときにCPS形式で書かないといけないこと？
code:a.sk
def foo(x: Int)
bar(x) + baz(x)
end
↓
# 中間表現（イメージ）
def foo(x: Int, c: Cont)
bar(x){|bar_result|
baz(x){|baz_result|
c(bar_result + baz_result)
}
}
end
↓
# LLVM IR (久しぶりなのでうろ覚え）
@foo(ptr %self, ptr %x, ptr %c) void {
%c2 = ...(@foo_1を呼ぶ、という情報)
call @bar(ptr %x, ptr %c2)
}
@foo_1(ptr %bar_result, ptr %x, ptr %c) void {
%c2 = ...(@foo_2を呼ぶ、という情報)
call @baz(ptr %x, ptr %c2)
}
@foo_2(ptr %baz_result, ptr %x, ptr %orig_c, ptr %c) void {
call %c
}
とりあえず小さいもので試さないとなあということでリポジトリを作った
とりあえずtokioを入れるとこまでできた
code:rust
pub extern "C" fn sleep(n: i64) -> i64 {
let future = sleep_(n);
match future.poll(ctx) {
Poll::Ready(value) => {
chiika側に戻る
}
Poll::Pending => {
まだ待つ
}
}
}
async fn sleep_(n: i64) -> i64 {
tokio::time::sleep(Duration::from_secs(n)).await;
}
これsleepがC関数をとるようにできないのかな
再帰でループを書いたときにスタックが伸び続ける問題がある？とかって見たような
まあ継続を何らかの形で渡さないといけないのは確か
かつ
chiikaの関数を呼び出す毎に「スタック」にpushする
Penの実装見てからずっと気になってるんだけど伝統的なCPSってスタック使わなくない？
chiikaをスタック使わないCPS に変換できるか
code:chiika
func foo(x) {
baz(bar(x))
}
↓
func foo(x, cont) {
bar(x, fn(bar_result){
baz(bar_result, fn(baz_result){
cont(baz_result)
}
}
}
code:chiika
func foo(x) {
let a = 1;
baz(a + bar(x))
}
func foo(x, cont) {
let a = 1;
bar(x, fn(env2, bar_result){
baz(env20 + bar_result, fn(env3, baz_result){ }
}
}
code:chiika
func foo(env, cont, x) {
let a = 1;
env.push(a)
env.push(cont)
bar(env, foo_1, x) //calls foo_1(env, bar_result)
}
func foo_1(env, bar_result){
baz(env, foo_2, env-2 + bar_result) //calls foo_2(env, baz_result) }
func foo_2(env, baz_result){
let cont = env.pop
let a = env.pop
cont(env, baz_result)
}
ABIとしては、「env, cont, ...argsをとり、処理が終わったらcont(env, 結果)をよぶ」となる
chiika関数は関数呼び出しを境としていくつかに分割される
envには境をまたいで保持すべきものが随時pushされる
分割した最後の関数でpopする
性能のことを考えると、asyncでない関数の呼び出しは境とする必要がない
asyncかどうかは別途リストを作って管理する(Rustで実装されたものだけでよい。それがあればchiika側は自動解析できるため)
上記でbarが同期関数だとする
この場合ABIは単にbar(x) -> valueとなる
code:chiika
func foo(env, cont, x) {
let a = 1;
env.push(cont)
baz(env, foo_1, a + bar(x)) //calls foo_1(env, baz_result)
}
func foo_1(env, baz_result){
let cont = env.pop
cont(env, baz_result)
}
こうかな。境が一つ減った