Cloudflare Workersで、自分のはてブをBlueskyに流す

bsky.app

そういえば、古き良き時代は自分のブックマークは自動でTwitterに投稿されていたのだった。 今はBlueskyがメインになっているので、同じ仕組みが欲しい、と思った。ので、作った。

github.com

要件

自分のブックマークはRSSで取得できる。定期的にチェックして新しいのがあれば、といったロジックで検出できる。 なので、基本的にはプログラムを定期実行できる場所があればGitHub Actionsとかでも良い。 ただ、対象のブクマ内容をpostする前に、それを既にpostしているか否かを知る必要がある。

専用のbotアカウントとかであれば、そのアカウントのpost feedを取得して最近のものをチェックすれば確認可能だが、自分のアカウントに流す場合はその方法だと手動で大量にpostしたりしているタイミングだと埋もれてしまう。 よって、何らかの方法でpost済みのものを保持しておく必要がある。

先行事例

で、良いなと思ったのがこれ。

github.com

Cloudflare Workersでも Cron Triggers で定期実行できて、また Workers KV のようなものでデータを保存しておくことができる。 上述要件を満たすプラットフォームとしてはちょうど良さそう。

Rust版

前述のをそのまま使わせていただいても良かったのだけど、折角 ATProtocolのRustライブラリを作っている のだし、Rustで同じような機能のものを作ってみることにした。

WASM対応

まず拙作 ATrium を使ってみようとしたところ、早速ビルドに失敗した。 あまり考えていなかったが、 wasm32-unknown-unknown のtargetでビルドしようとすると失敗する箇所が多々あった。

ので、まずはそこから。

github.com

主に問題は async-trait を使っているところで、これが Send を要求するため wasm32 targetの場合に問題になるようだった。 これは (?Send) を追加することで回避できるとのこと。 wasm32 targetのときだけこれを追加する形に変更した。他のtargetの場合は何も影響を受けない。

#[cfg_attr(target_arch = "wasm32", async_trait(?Send))]
#[cfg_attr(not(target_arch = "wasm32"), async_trait)]

あとは atrium-xrpc-client という専用の非同期HTTP Clientを幾つか提供していたが、それらは reqwest backendのもの以外はすべてwasm32には対応していなかったので、諸々変更して wasm32 の場合は reqwest のClientだけが利用可能になるようにした。

Cloudflare Workersでの実装

以前の記事 でも書いた通り、Cloudflare WorkersはRust環境でも作成することができる。今回のものもJavaScript/TypeScriptを1行も書かずに作成できた。

Cron Triggers用に #[event(scheduled)] をつけた関数を実装するだけ。

1MB制限との戦い

うっかり色んなライブラリを依存に入れていると、ビルド後のサイズが無料枠上限の1MBを超えてしまう。

RSSの解析に最初は feed-rs を使っていたが、ちょっと大きいようだったのでもっとシンプルにRSS 1.0のものだけ扱える rss に変更したりした。

Fetch API

ローカル実行する時の感覚で reqwest を、コンテンツ取得や atrium-xrpc-client のバックエンドとして使っていたが、実は必要なかった… worker-rs には worker::Fetch があり、これを使うことでHTTPリクエストを処理できる。

ATriumでは、非同期HTTP Clientとしてはどんなものを使っても良いようにTraitだけ用意して開発者が自由にClientを実装・選択できるように設計していた。 ので、今回は worker::Fetch を使うように少し繋ぐ部分を書くだけでXRPC Clientとして問題なく利用できるようになった。

github.com

ただ、本来このFetch APIを使って Transform images もできるはずなのだが、どうもRust版はまだ対応できていないっぽい。

Add support for the `cf.image` field in `fetch()` properties by jakubadamw · Pull Request #351 · cloudflare/workers-rs · GitHub

無理矢理やればできるのかな… とはいえOGPの画像はわりと変換かけずにそのまま uploadBlob しても失敗することは少なそう?なのでしばらく様子見でいいかな。

KVでのSessionStore?

ちなみに atrium-api ではセッション情報を管理する AtpAgent というのも用意していて、ここでは SessionStore も自分で実装することで認証情報を保持しておくことができるように設計していた。 通常は memoryに保持するだけの MemorySessionStore を利用するが、今回のようなケースで KV を使ってそこに保持しておくことができないか? と試みたが、やはり Send trait要求の壁があり上手くいかなかった… これはちょっと対応するのも難しいかなぁ。

そもそも今回のように難しい並列処理とか無いような場合はわざわざsession保持しておかなくても都度ログイン(createSession)する、で問題なさそうではある。

Rustで将棋の局面画像生成、そしてCDN Edgeで動的生成

背景

先行・類似事例

その他、自分でも過去にGoで作成したものがあったが、もう今はメンテしていなくて動かない。画像素材を公開してくださっていたサイトも消滅してしまっている。

自作のメリット

  • 自分好みの画像を生成できる
    • 形式もまずはPNGで、SVGも後で追加するなど可能かも
  • Rustのプログラムから使えるライブラリとして存在していると嬉しい
    • WASM化してWebアプリ化もしやすいかもしれない

Rustで局面画像生成

基本的には、透過PNGの素材を組み合わせて盤上に駒を配置するだけ。

あとは持ち駒の表現が様々な表示方法があるが、歩は最大18枚なので重ねて並べるのは微妙で、素直に個数を数字としてレンダリングした方が分かりやすいと思う。

盤・駒画像の素材

最近では Electron将棋 のKubo, Ryosukeさんが使いやすい形で素材画像を公開してくださっている。

sunfish-shogi.github.io

ので、これを使わせていただくことにした。 二文字駒もあると嬉しかったが、一時期追加されていたものの諸事情で削除されてしまったようだ。 今後 誰かがオリジナルで作成してここに追加してくれたりするようになるといいな…。

画像処理

image というライブラリが画像処理によく使われているようだ。 PNG以外にも様々な画像形式に対応していて、拡大縮小や重ね合わせなどの基本的な処理も簡単にできる。

作成時にはPNG画像を合成する操作だけなので、もっと軽いライブラリで同様のものが実現できるならそちらの方が良いかもしれない。とりあえずはimageで実装してみた。

入出力

入力は局面の情報を持つものとして shogi_corePartialPosition を使うことにした。出力はimageRgbaImage

ライブラリ使用者は必要に応じて例えば shogi_usi_parse を使ってSFEN文字列からPartialPositionを作り、それを元に生成した結果のRgbaImageを加工したり好きな形式でファイルに書き出したりすれば良い、という想定。

pub fn pos2img(position: &shogi_core::PartialPosition) -> image::RgbaImage {
    Generator::default().generate(position)
}

Generatorと下準備

局面画像を作成する際の計算負荷が減るよう、Geenratorという構造体を用意した。 スタイルを指定してnewした時点で必要な駒などの素材データを読み込んでおき、generateを呼ばれた際にはそれらを貼り合わせるだけ、にする。 これによって、同じスタイルで複数の局面を生成する場合には、素材の読み込みが一度で済んで高速に生成できるようになる、はず。

盤と駒の画像は事前にサイズを決めておき、それぞれ切り出した上で最適化したPNGファイルとして置いておく。ファイル読み込みはせず、include_bytes!でメモリ上から読み込んで使う。

Publish

というわけで出来上がったので crates.io に公開した。 ご自由にお使いください。

Web Appで使う

せっかくライブラリとして作ったので、ちょっと加工してWeb Appとしても使えると嬉しいかもしれない、と思って作ってみることにした。

局面を表現するSFEN文字列は lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1 のように表現される。これをURLのPathとして受け取って、対応する局面画像を返すようなものを考えた。

例:

https://example.com/3sks3/9/4S4/9/1+B7/9/9/9/9%20b%20S2rb4g4n4l18p%201

スペースは %20エンコードする必要があるのでちょっとカッコ悪いが…。

CDN Edgeで動かす

最近よく聞くようになったEdge Computingをまだ試したことがなかったので、この機会に色々触ってみることにした。

wasm-packでWebAssembly作成

まずは簡単なインタフェースを決めて、WebAssemblyで使えるようにパッケージを用意した。 簡単に扱えるように、入力はSFEN文字列としshogi_usi_parseでそれをparseし局面情報を取得、出力は生成した画像のPNG形式バイナリデータとした。

use shogi_img::{image, pos2img, shogi_core};
use shogi_usi_parser::FromUsi;
use std::io::Cursor;
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub fn sfen2png(sfen: &str) -> Vec<u8> {
    let pos = shogi_core::PartialPosition::from_usi(sfen).unwrap_or_default();
    let mut cursor = Cursor::new(Vec::new());
    pos2img(&pos)
        .write_to(&mut cursor, image::ImageFormat::Png)
        .ok();
    cursor.into_inner()
}

あとは wasm-pack でビルドすればいい感じにwasmファイルが生成される。

Deno Deploy

上記のwasmを使って最も簡単に実現できたのが、Deno Deploy だった。 wasm-pack build --target deno するとDeno用のwasmファイルが生成され、あとはそれを読み込んで使うだけ。

import { sfen2png } from "./pkg/sfen2png.js";

Deno.serve((req: Request) => {
  const sfen = `sfen ${decodeURI(new URL(req.url).pathname).slice(1)}`;
  return new Response(sfen2png(sfen), {
    headers: {
      "content-type": "image/png",
    },
  });
});

これだけのコードを書いて、あとはdeployすれば動く。簡単すぎてすごい。

$ curl -I https://sfen2img.deno.dev/
HTTP/2 200
content-type: image/png
vary: Accept-Encoding
date: Wed, 24 Jan 2024 14:39:32 GMT
content-length: 447458
via: http/2 edgeproxy-h
server: deno/gcp-asia-northeast1

Vercel Edge Functions

同様にwasmを読み込んで使えるものとして、Vercel Edge Functions を試してみた。

ドキュメントには wasm-pack を使った例が無いようで、他の人が作っているexample repositoryなどを参考にしてどうにか。 wasm-pack build --target web で生成し、Next.jsで/src/app/[[...slug]]/route.ts で使う。

// @ts-ignore
import wasm from "@/pkg/sfen2png_bg.wasm?module";
import init, { sfen2png } from "@/pkg/sfen2png.js";

export const runtime = "edge";
export const dynamic = "force-dynamic";

export async function GET(request: Request) {
  await init(wasm);
  const sfen = `sfen ${decodeURI(new URL(request.url).pathname).slice(1)}`;
  return new Response(sfen2png(sfen), {
    headers: {
      "content-type": "image/png",
    },
  });
}

とりあえずこれでローカルでは動いた。deployしてみようとしたが

Error: The Edge Function "[[...slug]]" size is 1.62 MB and your plan size limit is 1 MB.

となってしまった。wasmだけで1.3MBくらいあり、Hobbyプランでは1MBまで という制限を超えてしまうようだ。 Pro以上のプランにするか、もっと軽いバイナリになるように工夫が必要になる…。

Cloudflare Workers

よく名前を聞くので是非試してみたかった、Cloudflare Workers

wrangler でプロジェクトを作成する際に worker-rust のテンプレートを使うと、Rustで worker を使うRustプロジェクトが生成される。

wrangler generate [name] https://github.com/cloudflare/workers-sdk/templates/experimental/worker-rust

そして lib.rs を以下のように編集するだけ。

use sfen2png_wasm::sfen2png;
use urlencoding::decode;
use worker::*;

#[event(fetch)]
async fn main(req: Request, _env: Env, _ctx: Context) -> Result<Response> {
    let decoded = decode(&req.path())
        .map(String::from)
        .expect("decode failed");
    let sfen = format!("sfen {}", decoded.strip_prefix('/').expect("invalid path"));
    Ok(Response::from_bytes(sfen2png(&sfen))?
        .with_headers(Headers::from_iter([("content-type", "image/png")])))
}

JavaScriptdecodeURI同等のものは標準には無いようなので urlencoding ライブラリを使っている。

あとは wrangler deploy するだけ。その中で worker-build によってCloudflare Workers用に諸々ビルドされるようで、worker-buildが内部でwasm-packを実行したりしているようだ。 Rustだけで完結し、JS/TSのコードを書く必要がない。wranglerのためにnpmを使うくらい。

Cloudflare WorkersもVercel Edge Functionsと同様に Free planでは 1 MB まで という制限があるが、こちらは size after compression ということで事前にgzip圧縮して送信してくれるおかげで660KB程度になり、制限に引っかかることなくdeploy成功する。

Total Upload: 1414.62 KiB / gzip: 659.91 KiB
$ curl -I https://sfen2img.sugyan.workers.dev/
HTTP/2 200
date: Thu, 25 Jan 2024 06:16:53 GMT
content-type: image/png
content-length: 447458
report-to: {"endpoints":[{"url":"https:\/\/a.nel.cloudflare.com\/report\/v3?s=cT5XwLyJxYgiWXTJ85RHOGIRSxlpJSnl%2F6iPDoQW097set8BelY7M%2Fc6mRULGktwSqBU2Jlv6UoJ3w6eYFDM4bBjNHmZPGvfrnipB8u4Fxmkc3T%2BjFVUyF80dEFkxsn5X1Lp9OzTRhytCWAf%2BLA%3D"}],"group":"cf-nel","max_age":604800}
nel: {"success_fraction":0,"report_to":"cf-nel","max_age":604800}
server: cloudflare
cf-ray: 84ae63d57d908370-KIX
alt-svc: h3=":443"; ma=86400

Fastly Compute@Edge

最後に Cloudflare Workersと並んでよく名前を聞く、Fastly Compute@Edge

こちらは fastly というCLIツールを使う。

$ fastly compute init

...

Language:
(Find out more about language support at https://developer.fastly.com/learning/compute)
[1] Rust
[2] JavaScript
[3] Go
[4] Other ('bring your own' Wasm binary)

このあたりから選べそう。今回はRustで。Cloudflare Workersと同様にRustプロジェクトが生成されるので、同じようにmain.rsを編集していく。

use fastly::http::header;
use fastly::{Error, Request, Response};
use sfen2png_wasm::sfen2png;
use urlencoding::decode;

#[fastly::main]
fn main(req: Request) -> Result<Response, Error> {
    let decoded = decode(req.get_path())?;
    let sfen = format!("sfen {}", decoded.strip_prefix('/').expect("invalid path"));
    Ok(Response::from_body(sfen2png(&sfen)).with_header(header::CONTENT_TYPE, "image/png"))
}

Request/Responseなどのインタフェースは worker とは多少異なるが、おおまかには同じなのでこれくらいの内容であればほぼ同じような感覚で書ける。

あとは fastly compute publish するだけ。こちらは wasm-pack なども使わない。

$ curl -I https://sfen2img.edgecompute.app/
HTTP/2 200
content-type: image/png
x-served-by: cache-nrt-rjtf7700062-NRT
date: Thu, 25 Jan 2024 07:26:11 GMT

その他

Edge Computing系のサービスは他にも多くあるようだが、今回はこれくらいで。 大抵はJSからwasmを呼び出す形でVercel Edge Functionsと同様に動かせる、と予想している。

サイズ制限は厳しい場合が多いので、.wasmが1MBを切る程度には軽量できた方が望ましそうではある…。

まとめ

局面画像生成ライブラリを作ったおかげで、詰将棋画像を投稿するBluesky BotをRustだけで作ることができた。

bsky.app

スクレイピングして得たkifファイルをparseして局面情報を取得する部分も 自作ライブラリ を使っているので、

  • kifから PartialPosition への変換
  • PartialPosition から画像生成
  • 生成画像を含むPostをBlueskyに投稿

の3つを自作のライブラリを使って実現していることになる。

副産物として、Edgeで動的生成するWeb Appが複数できた。 無料枠でそのまま置いておくので、使える限りはご自由にお使いください。

Repository

Advent of Code 2023 を完走した

毎年12月に開催されている Advent of Code に、2019年から参加している。

過去記事:

2023年のAdvent of Codeにも挑戦していて、年が明けてしまったが先日ようやく25日すべての問題に解答して 50 個のスターを集めることができた。

bsky.app

2023年は例年と比較しても難易度が高いものが多かったように思う(英語のストーリーを読解しきれない、のは毎年のことだが)。 いちおう「他の人の解答を見たりせずにまずは自力で回答する」という目標は達成してとりあえずの自力完答はできたが、正直どうするのが正しかったのか分からん…というものも多かった。

github.com

これから Reddit での議論を見たり他の言語でも解いてみたりして、もうちょっと勉強しておこうと思っているところ。

問題の概要と解いた感想

ネタバレしない程度に。

day01

行の文字列の中から数値(数値)を見つける。

1日目の小手調べにしてはpart2がちょっと面倒だった

day02

3色の石の数を推測するゲーム。

正しく入力をparseして処理できれば特に問題ない

day03

2次元の図ではあるが横に並ぶ数字は数値として見る必要がある、というもの。

数値と記号の位置関係をうまく判定できれば、という感じ

day04

クラッチカードの得点計算。

part2はAoCらしいメタな感じでちょっと頭を使う面白い問題

day05

数値の範囲から別の範囲へのマッピング、を繰り返す。

急に難易度が上がって大変だった…!

day06

チャージ時間を調整してボートが進める距離を予測する。

入力のフォーマットが不自然だったのは意味があったか…

day07

トランプのポーカーの役の強さでソートする。

またしてもpart2の展開を予測できなかった

day08

2分岐の迷路を指定された方向に無限に進み続ける。

part2がやはり少し難しく。入力が上手く作られていることに救われている感じ

day09

数列から差分を使って次の値を予測する。

スッと解けると気持ち良い

day10

2次元grid内でループする経路を検出。

part2はだいぶ苦労した… 理論を知っていればもっと簡単だったのだろうか

day11

膨張し続ける宇宙空間で銀河間の距離を求める。

これはpart2はこうなるだろうな、というのが予想できた

day12

イラストロジック的なもの。

そろそろ探索の実装も一筋縄ではいかなくなってくる

day13

2次元grid上で鏡写しになっている境界を見つける。

簡単な方法を自力では思いつけなくて悔しい

day14

2次元grid上で丸い石を一方向に動かして詰めていく。

今年は2次元gridモノが多いな…。

day15

HashとHashMapの独自実装。

工夫のしどころが見つからなかった…

day16

光の反射と分裂シミュレーション。

また2次元grid… しかしこういうのはvisualizationが面白そう

day17

動き方に制約のある最短経路探索。

制約ひとつで色んな考え方が生まれて面白いなぁ

day18

命令の通りに線を引いて囲んだ面積を求める、というもの。

AoCではよく出てくるタイプのもの、かな? すごい苦労したが…

day19

4つの値に対して分岐していくworkflowに流し込んで結果を得る。

どんどん実装が大変になってきた…!

day20

状態を保持する回路を使い、通るpulseのシミュレーション

しばらく悩んで色々ためして一応どうにか解を出せたが… という感じ

day21

2次元grid迷路内で、偶数歩で辿り着き得る範囲は。

これはめっちゃ難しくて悩みまくった… 何度も試行錯誤して解は出せたが

day22

3次元空間でジェンガを積んでいく。ブロックを取り除くとどうなる?

かなり考え込んでようやくどうにか解けた、、という感じ

day23

2次元gridでの一筆書き(同じ点を二度と通らない)最長経路。

計算は大変だったけどどうにか

day24

3次元空間内で移動する座標たち…!

おそらく2023で一番の難問だったと思う、しかし解けるとスッキリする。。

day25

グラフを3辺切断して2つのグループに分ける。

最小カット問題、というのか?アルゴリズム知らなくてちょっと泥臭いやり方で解いた

自動でtokenをrefreshして再送するRustの非同期HTTP Client

半年ほど前から、BlueskyのAT ProtocolのRust版ライブラリを作っている。 memo.sugyan.com

github.com

その中で最近実装した機能の話。

API Agent

本家の atproto (TypeScript実装)に AtpAgent というものがある。

この AtpAgent は、(Blueskyだけに限らない) AT Protocol のための汎用的なエージェントとして提供されている。その機能の一つとしてtokenの管理機能がある。

AT Protocolの認証

少なくとも 2023/11 時点では HTTP Bearer auth でJWTを送信することで認証を行う方式となっている。

com.atproto.server.createSession でログイン成功すると accessJwtrefreshJwt などが含まれる認証情報が返ってくるので、その accessJwt をBearer tokenに使って各エンポイントにアクセスする。

また、 com.atproto.server.refreshSession というエンドポイントがあり、ここを refreshJwt をtokenに使って叩くことでtokenを更新することができる。

tokenの管理と自動更新機構

で、 @atproto/api で提供されている AtpAgent はそれらのtokenの管理を自動で行う機能を持っている。

export class AtpAgent {
  ...
  session?: AtpSessionData

  /**
   * Internal fetch handler which adds access-token management
   */
  private async _fetch(...): Promise<AtpAgentFetchHandlerResponse> {
    ...
    // wait for any active session-refreshes to finish
    await this._refreshSessionPromise
    // send the request
    let res = await AtpAgent.fetch(...)
    // handle session-refreshes as needed
    if (isErrorResponse(res, ['ExpiredToken']) && this.session?.refreshJwt) {
      // attempt refresh
      await this._refreshSession()
      // resend the request with the new access token
      res = await AtpAgent.fetch(...)
    }
    return res
  }
}

まず現時点でもっているsession情報を元にリクエスト処理を試み、そのレスポンスが expired のエラーだったときのみそれを検出してtokenをrefreshして同じ内容のリクエストを再送する。最初のリクエストが成功していた場合はそのままそのレスポンスを返す。 という動き。

ATriumでの実装

で、これと同様の仕組みを持つ AtpAgent をATriumでも実装しようと考えた。

XrpcClient trait

ATriumでは、AT ProtocolのXRPCリクエストを送るための XrpcClient というtraitを定義している。

#[async_trait]
pub trait HttpClient {
    async fn send_http(
        &self,
        request: Request<Vec<u8>>,
    ) -> Result<Response<Vec<u8>>, Box<dyn std::error::Error + Send + Sync + 'static>>;
}

pub type XrpcResult<O, E> = Result<OutputDataOrBytes<O>, self::Error<E>>;

#[async_trait]
pub trait XrpcClient: HttpClient {
    fn base_uri(&self) -> String;
    #[allow(unused_variables)]
    async fn auth(&self, is_refresh: bool) -> Option<String> {
        None
    }
    async fn send_xrpc<P, I, O, E>(&self, request: &XrpcRequest<P, I>) -> XrpcResult<O, E>
    where
        P: Serialize + Send + Sync,
        I: Serialize + Send + Sync,
        O: DeserializeOwned + Send + Sync,
        E: DeserializeOwned + Send + Sync,
    {
        ...
    }
}

XRPC は規約に沿ったHTTPリクエスト/レスポンスでしかないので、内部としてはHTTPの処理をすることになる。 が、RustではHTTPリクエスト/レスポンスを処理するための標準ライブラリのようなものはなく、特に非同期の場合は reqwestIsahcSurf のような3rd partyのライブラリが多く使われている、と思う。

ATriumではこれらのライブラリをバックエンドとして開発者が選択できるよう、HTTP部分を抽象化する HttpClient というtraitを定義し、それを継承した XrpcClient を実装したインスタンスを内部に持つ AtpServiceClient が各XRPCを処理する形にしている。

XrpcClient::send_xrpc() はデフォルト実装を持っており、HttpClient::send_http() さえ実装されていれば、あとはそれを使ってリクエストに使う入力のserializeや返ってきたレスポンスJSONのdeserializeなどの処理を行うようになっている。

session管理するwrapper

認証については XrpcClient のメソッドとして async fn auth(&self, is_refresh: bool) -> Option<String> を定義しているだけなので、ここでどのようなtokenを返すかはtrait実装者に任される。

インメモリで管理する場合、内部で Arc<RwLock<Option<Session>>> のように持っておいて管理することで、マルチスレッドで共有されていても安全に扱えるようになる。

(参考: https://github.com/usagi/rust-memory-container-cs)

なので、内部で XrpcClient を実装したものを持つWrapperを作り、主な処理はそれに移譲して auth() だけを実装することで、保持しているsession情報からtokenを返す XrpcClient 実装を作ることができる。

use std::sync::Arc;
use tokio::sync::RwLock;

struct Wrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    inner: T,
    session: Arc<RwLock<Option<Session>>>,
}

#[async_trait]
impl<T> HttpClient for Wrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    async fn send_http(
        &self,
        request: Request<Vec<u8>>,
    ) -> Result<Response<Vec<u8>>, Box<dyn std::error::Error + Send + Sync + 'static>> {
        self.inner.send_http(request).await
    }
}

#[async_trait]
impl<T> XrpcClient for Wrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    fn base_uri(&self) -> String {
        self.inner.base_uri()
    }
    async fn auth(&self, is_refresh: bool) -> Option<String> {
        self.session.read().unwrap().as_ref().map(|session| {
            if is_refresh {
                session.refresh_jwt.clone()
            } else {
                session.access_jwt.clone()
            }
        })
    }
}

ここでは非同期の RwLock として tokio::sync を使っている。

これで、AtpAgent も同じsessionを共有し、例えばログイン成功時に取得したsession情報を書き込む、といったことをすれば、その後のリクエストでその値が使われるようになる。

struct AtpAgent<T>
where
    T: XrpcClient + Send + Sync,
{
    api: Service<Wrapper<T>>,
    session: Arc<RwLock<Option<Session>>>,
}

impl<T> AtpAgent<T>
where
    T: XrpcClient + Send + Sync,
{
    fn new(xrpc: T) -> Self {
        let session = Arc::new(RwLock::new(None));
        let api = Service::new(Wrapper {
            inner: xrpc,
            session: Arc::clone(&session)
        });
        Self { api, session }
    }
    async fn login(&self, ...) {
        // login process
        let session: Session = ...;
        self.session.write().await.replace(session);
    }
}

tokenの自動更新 (失敗例)

で、これを使ってtokenの自動更新を行うためには、XrpcClient::send_xrpc() をオーバーライドする形で実装すれば良さそう。

impl Wrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    async fn refresh_session() {
        // refresh process
        let session: Session = ...;
        self.session.write().await.replace(session);
    }
    fn is_expired<O, E>(result: &XrpcResult<O, E>) -> bool
    where
        O: DeserializeOwned + Send + Sync,
        E: DeserializeOwned + Send + Sync,
    {
        if let Err(Error::XrpcResponse(response)) = &result {
            if let Some(XrpcErrorKind::Undefined(body)) = &response.error {
                if let Some("ExpiredToken") = &body.error.as_deref() {
                    return true;
                }
            }
        }
        false
    }
}

impl<T> XrpcClient for Wrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    fn base_uri(&self) -> String {
        ...
    }
    async fn auth(&self, is_refresh: bool) -> Option<String> {
        ...
    }
    async fn send_xrpc<P, I, O, E>(&self, request: &XrpcRequest<P, I>) -> XrpcResult<O, E>
    where
        P: Serialize + Send + Sync,
        I: Serialize + Send + Sync,
        O: DeserializeOwned + Send + Sync,
        E: DeserializeOwned + Send + Sync,
    {
        let result = self.inner.send_xrpc(request).await;
        // handle session-refreshes as needed
        if Self::is_expired(&result) {
            self.refresh_session().await;
            self.inner.send_xrpc(request).await
        } else {
            result
        }
    }
}

self.innersend_xrpc() を移譲し、その結果を判定して Expired のエラーであった場合のみ self.refresh_session() を呼び出してtokenを更新し、再度同じ send_xrpc() を呼び出す、という形。

self.refresh_session() が成功して内部のsessionが書き変わっていれば、再度同じリクエストを送ったときにはtokenが更新されているので成功する。

…と思ったが、実際にはこれは思った通りには動かない。 Rustのtrait実装はインスタンスのメソッドをオーバーライドしているわけではなく、あくまでtraitのメソッドを実装しているだけなので、 self.inner に移譲したメソッドは self とは別のインスタンスとして扱われる。

つまり self.inner.send_xrpc() のデフォルト実装中で呼ばれる self.auth() はあくまで self.inner に実装されている auth() であり、Wrapper に実装されている auth() は呼ばれない。なので、いくら Wrapper の内部でsessionを更新しても self.inner には関係がない、ということになる。

2重のwrapperで解決

これをどうやって解決するかしばらく悩んだが、結局wrapperをもう一つ作って2重にsessionを共有することで想定した動きをするようになった。

主な処理を移譲された inner が同じsession情報を持って使ってくれていれば問題ないので、元のwrapperを RefreshWrapper として、同じように XrpcClient を実装する SessionWrapper を作り、 auth()self.session を参照する機能だけをそちらに持たせるようにする。

struct RefreshWrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    inner: T,
    session: Arc<RwLock<Option<Session>>>,
}

#[async_trait]
impl<T> HttpClient for RefreshWrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    ... // (use inner)
}

#[async_trait]
impl<T> XrpcClient for RefreshWrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    async fn send_xrpc<P, I, O, E>(&self, request: &XrpcRequest<P, I>) -> XrpcResult<O, E>
    where
        P: Serialize + Send + Sync,
        I: Serialize + Send + Sync,
        O: DeserializeOwned + Send + Sync,
        E: DeserializeOwned + Send + Sync,
    {
        let result = self.inner.send_xrpc(request).await;
        // handle session-refreshes as needed
        if Self::is_expired(&result) {
            self.refresh_session().await;
            self.inner.send_xrpc(request).await
        } else {
            result
        }
    }
}

struct SessionWrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    inner: T,
    session: Arc<RwLock<Option<Session>>>,
}

#[async_trait]
impl<T> HttpClient for SessionWrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    ... // (use inner)
}

#[async_trait]
impl<T> XrpcClient for SessionWrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    ...

    async fn auth(&self, is_refresh: bool) -> Option<String> {
        self.session.read().await.as_ref().map(|session| {
            if is_refresh {
                session.refresh_jwt.clone()
            } else {
                session.access_jwt.clone()
            }
        })
    }
}

そして、 AtpAgent では XrpcClient を実装したものとして RefreshWrapper<SessionWrapper<T>> を使うようにする。両者間で session を共有するために Arc<RwLock<Option<Session>>> を渡している。

struct AtpAgent<T>
where
    T: XrpcClient + Send + Sync,
{
    api: Service<RefreshWrapper<SessionWrapper<T>>>,
    session: Arc<RwLock<Option<Session>>>,
}

impl<T> AtpAgent<T>
where
    T: XrpcClient + Send + Sync,
{
    fn new(xrpc: T) -> Self {
        let session = Arc::new(RwLock::new(None));
        let api = Service::new(Arc::new(RefreshWrapper {
            inner: SessionWrapper {
                inner: xrpc,
                session: Arc::clone(&session),
            },
            session: Arc::clone(&session),
        }));
        Self { api, session }
    }
}

send_xrpc() 内でのexpire検出と更新・再送の処理は RefreshWrapper で行われるが、実際の送信は内部の SessionWrapper に移譲されることになる。 SessionWrapper では共有されている self.sessionauth() 内で参照する動作をするので、 RefreshWrapper (や、それを使う AtpAgent 本体) で更新されたsession情報がそのまま使われることになる。

これでtokenの自動更新が実現された。

並行処理での同時更新の問題

もう一つ、TypeScript実装の AtpAgent が持っている機能として、複数の refreshSession() が同時に来ても1回しか実行されないように制御する、というものがある。

  /**
   * Internal helper to refresh sessions
   * - Wraps the actual implementation in a promise-guard to ensure only
   *   one refresh is attempted at a time.
   */
  private async _refreshSession() {
    if (this._refreshSessionPromise) {
      return this._refreshSessionPromise
    }
    this._refreshSessionPromise = this._refreshSessionInner()
    try {
      await this._refreshSessionPromise
    } finally {
      this._refreshSessionPromise = undefined
    }
  }

内部状態として Promise<void> | undefined を持っており、 _refreshSession() が呼ばれた時点でそれが undefined であれば Promise<void> をセットした上で実際にその処理を await し、既に Promise<void> がセットされている場合はそれを返す、という動き。

もしAgentが並行して複数のAPIをほぼ同時に叩いたときに、tokenがexpiredだった場合はその結果がほぼ同時に返ってくることになる。その時点ではtokenがrefreshされていないので、それぞれがほぼ同時に自動refresh処理を行うことになるが、実際には1回だけrefreshされていれば良いので、そのように制御するための仕組み、と考えられる。

そもそも同じrefresh tokenを使って複数回refreshのリクエストすると、既に使用されたrefresh tokenが無効になり2回目以降のrefreshはエラーになる可能性もあり(ここはサーバ実装次第と思われる、現時点でのblueskyでは特に何も起こらず新しいtokenが発行されるだけ、のようだ)、非同期で並行処理され得る環境ではこういった制御は必要になる。

…しかしRustでは同じように実装しようとしても上手くいかなかった。 async なinnerを呼んだ返り値を保持するとなると Pin<Box<impl Future<Output = Result<...>> + 'static>> のような形になり、しかしこれを Mutex とかで保持しようとしてもこれは Send ではないので Mutex に入れられない、など… 何度もコンパイルエラーに悩まされて挫折した。 Rustの非同期に詳しい人なら上手く実装できるんだろうか…

Notify による制御実装

ChatGPTと長々と議論し、結局 tokio::sync にある MutexNotify を使うことで同様の動作を実現させた。

use tokio::sync::{Mutex, Notify};

struct RefreshWrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    inner: T,
    session: Arc<RwLock<Option<Session>>>,
    is_refreshing: Mutex<bool>,
    notify: Notify,
}

impl<T> RefreshWrapper<T>
where
    T: XrpcClient + Send + Sync,
{
    ...

    async fn refresh_session(&self) {
        {
            let mut is_refreshing = self.is_refreshing.lock().await;
            if *is_refreshing {
                drop(is_refreshing);
                return self.notify.notified().await;
            }
            *is_refreshing = true;
        }
        self.refresh_session_inner().await;
        *self.is_refreshing.lock().await = false;
        self.notify.notify_waiters();
    }
}

まず self.is_refreshing で、refresh実行中のものがあるか否かを保持する。これは Mutex で管理されるので、 最初にロックを取得して true に変更したものが完了してまた false に戻すまでは他の処理からの読み取り結果は必ず true になる。 そして、その true に変更できたものだけが、後続の実際の更新処理である self.refresh_session_inner() を実行する。

self.is_refreshingtrue になっている間は、 self.refresh_session_inner() が終わったあとに呼ばれる self.notify.notify_waiters() によって完了を知らされるまで待機するだけ、という形になる。 こういった他のスレッドからの通知を待つための仕組みとして tokio::sync::Notify があるようだ。この場合は完了したことを知りたいだけなので Notify だが、処理結果も知りたい場合は oneshot などを使うと良いのかもしれない。

ライブラリとしては特定の非同期ランタイムに依存するようにはしたくないので tokio などを使うのは避けたかったが、標準ライブラリや futures などには同様の仕組みがないようだったので仕方なく tokio を使うことにした。実際のところ sync featureで使うこれらのものは特にランタイム依存は無いようで、 async-std など別の非同期ランタイムで実行しても問題なく動作するようではあった。

まとめ

ライブラリの依存は増えてしまったが、どうにか AtpAgent として実装したい機能は実現できた。Rustむずかしい…。

他にもっと良い方法をご存知の方がいればpull-requestなどいただけると嬉しいです。

PentominoをBitboardを使って解く

子どもが百均で買ってきたパズルをやってみたら、全然うまく出来なくて悔しかったのでプログラムで解を探すことにした。

Pentominoとは

調べるまで知らなかったが、このような 5つの正方形を繋げて作られる12種類のピースを使って敷き詰める、というパズルを Pentomino(ペントミノ) というらしい。

en.wikipedia.org

最も一般的なものはこれらを1種類ずつ使って長方形に敷き詰めるもので、5マス x 12種類なので面積60のものが考えられる。回転や反転によって重複するものを同一視すると、それらの解の数は以下の通り、とのこと。

  • 6x10 には 2,339通り
  • 5x12 には 1,010通り
  • 4x15 には 368通り
  • 3x20 には 2通り

そして冒頭の写真のものは2x2の正方形ピースが使われていて、合計面積64なので 8x8 の正方形が作れる。一般的にはこの2x2の正方形は中央に固定され、周囲のドーナツ状の部分に12種類を敷き詰める問題、となる。このときの解は 65 通りになる、とのこと。

探索アルゴリズムと実装

ということで、この問題を解くプログラムをRustで書いてみた。

計算量概算

まず、どれくらいの計算量がかかるのかを概算してみる。

ピースは12種類だが、反転と 90°, 180°, 270°の回転を考えると、それぞれに対し8通りの置き方がある。

12種類のピースの中から未使用のものを順番に選び
  選んだものに対して8通りの反転/回転のどれかを選び
    可能であれば(既に置かれている他のピースとぶつからなければ)置く

12種類の選ぶ順番だけで  12! (= 479,001,600) 通りあり、置き方を考慮するとその8倍、そして置ける場所を探すのにも計算が必要で愚直にやると盤面の全探索になったりして、とにかくかなりの時間がかかる、というのは容易に想像できる。

効率的な探索の方針

無駄な計算を省くために、まずは「端っこから順番に埋めていく」という方針を考える。 例えば最上段の左端から右端へ、次はその下の段の左端から右端へ、と。次に埋めるべきマスが決まっているので、現在選択しているピースではどうやってもそのマスを埋めることができない、となればその先の探索は必要なくなり枝刈りされる。

backtracking

こういう探索でよく使われるのがおそらくbacktrackingだろう。ざっくり以下のような感じ。

fn backtrack(board: &mut <盤面の状態>) {
    if すべてのマスが埋まっている(すなわち12種類のピースをすべて使いきっている) {
        答えを出力
        return;
    }
    for ピース in12種類のピース.filter(|ピース| 未使用) {
        for 反転/回転 in8通り {
            if 現在の盤面で最も上段・左端の空きマスを埋めるように置ける {
                boardに選択したピースを置いた状態にする
                backtrack(board);
                boardを1つ前の状態に戻す
            }
        }
    }
}

可能なものを順番に置いていき、置けなくなったら戻って次のものを置いていく、という処理を、盤面の状態を更新/復元しながら再帰的に探索していく。

あとはこれをどのようなデータ構造で実現するか、というところ。 長方形の盤面なので Vec<Vec<Option<u8>>> のように2次元配列で表していっても良いが、埋めるべき左上の空きマスを探すときや ピースを置けるか否かの判定などに毎回多くのループ処理が必要になってしまう。

Bitboardによる検索と判定

ここで登場するのがBitboard。 将棋ライブラリを自作 したときに学んだものが役に立つ。

u64 を使って64マスの盤面を表現する。0が空きマス、1が置けないマス、を表す。 8x8の中央に2x2の正方形が固定されていると考えると、初期盤面は以下のようになる。

00000000
00000000
00000000
00011000
00011000
00000000
00000000
00000000

この盤面のそれぞれのマスがu64の何bit目に対応するか、を割り当てていく。上段の左端から順に割り振っていくと、以下のようなレイアウトになる。

00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

なので前述の初期盤面は 103_481_868_288 (0x0000_0018_1800_0000) という値で表現される。

こうして表される盤面Bitboardに対し、例えばT型のピースを一番左上に置くとき、

11100000
01000000
01000000
00000000

...

のようなBitboardを作る。盤面とピースのそれぞれのBitboardとして表現されるu64同士をAND演算(&)すると、重なっている部分が1になるので、(board & piece) == 0 で盤面とピースが重なるマスが無いかどうか(すなわち空きマスだけにピースを置くことができるか否か)、を判定できる。 また、その後に board | piece とOR演算(|)を適用することで、盤面にピースを置いた状態を得ることができる。

また、盤面の左上から順番に埋めていくという方針を考えると、前述のレイアウトにしておくことで、 「最も上段・左端の空きマス」の位置を u64::trailing_ones() を使って一発で取得できる。 これは x86_64ならbsf命令、aarch64ならclz命令を使って計算されるので非常に高速に動作する。

あとはすべてのピース、その反転/回転、それらを盤面内の可能な範囲で移動したものをすべてBitboardで表現できれば、探索が進められそうだ。

候補の事前計算

まずピースについて、もう少し深く考えてみる。 前述したように12種類のピースにそれぞれ反転と4種類の回転があるので、全部で 12 * 2 * 4 = 96 通りありそうだが、実際には線対称・点対称な形もあるのでそこまで多くはならない。例えばT型のピースは線対称な図形なので反転を考慮する必要がなく4通りだけ。I型の細長いピースは縦か横の2通りだけだし、X型のピースにいたっては回転しても同じ形になるので1通りしかない。これらを考慮すると、実際には合計で63種類の形しか存在しないことが分かる。

で、これらをそれぞれ各方向に移動したものを考えていくが、この移動によって配置可能な位置の数はピースの横幅・縦幅に依存する。 ちなみに前述のレイアウトにしておくことで、最も左上に配置したときのBitboardを基準として、1つ右に移動したものは piece << 1 で、1つ下に移動したものは piece << 8 で表現できる。 ただしこれは8x8の左上から並べるレイアウトのときに限る話であり、例えば6x10の横長盤面で同様に左上から並べるレイアウトでは、1つ下に移動する操作は piece << 10 になる。

全63種類の形を盤面上の全位置に置く、のを列挙するのは大変ではあるが、探索時にはこれらを毎回すべて確認する必要はない。

上述の探索方針で次に置けるピースを探すとき、埋めるべきマスの位置は分かっていて、盤面でそのマスよりも左上(下位ビット)のものは既にすべて埋まっている、という前提になっている。 ということは、次に置く試行をすべきピースは必ず「埋めるべきマスを含む」ことが分かっているし、さらに「そのマスより下位のビットを含まない」、つまりそのピースを表すBitboardでの最下位ビットが埋めるべきマスに一致する配置のものしか有り得ない、ということになる。

.O##.   ..O#.   ..O..
..#..   .##..   .###.
..#..   ..#..   ..#..

例えば上図のように.以外で表現される形のピースの場合、Oの位置が埋めるべきマスになっている必要があり、そうでないとピース内の他の箇所が既に埋まっているはずの盤面にぶつかってしまう。

この条件を考慮して「埋めるべきマスの位置」(00-63)のそれぞれに対して「そのマスを埋めることができるピースの候補」を引けるようにしておく。対象1箇所あたり高々63種類で、すべて事前に計算しておくことができる。

実装と実行結果

というわけで、ここまでを踏まえて以下のような実装。

use std::array;

const NUM_PIECES: usize = 12;

pub type Bitboard = u64;

pub struct SimpleSolver {
    table: [[Vec<Bitboard>; NUM_PIECES]; 64],
}

impl SimpleSolver {
    pub fn new(rows: usize, cols: usize) -> Self {
        assert!(rows * cols <= 64);
        let shapes = calculate_shapes();
        let mut table = array::from_fn(|_| array::from_fn(|_| Vec::new()));
        for (n, shape) in shapes.iter().enumerate() {
            for s in shape {
                if s.iter().any(|&(x, y)| x >= cols || y >= rows) {
                    continue;
                }
                let v = s.iter().map(|p| (1 << (p.0 + p.1 * cols))).sum::<u64>();
                let (w, h) = s
                    .iter()
                    .fold((0, 0), |(xmax, ymax), &(x, y)| (xmax.max(x), ymax.max(y)));
                for y in 0..rows - h {
                    for x in 0..cols - w {
                        let offset = x + y * cols;
                        table[s[0].0 + offset][n].push((v << offset).into());
                    }
                }
            }
        }
        Self { table }
    }
    fn backtrack(
        &self,
        current: Bitboard,
        solutions: &mut Vec<[Bitboard; NUM_PIECES]>,
        s: &mut [Bitboard; NUM_PIECES],
    ) {
        if !s.iter().any(|u| *u == 0) {
            return solutions.push(*s);
        }
        let target = current.trailing_ones() as usize;
        for i in 0..NUM_PIECES {
            if s[i] == 0 {
                for &b in self.table[target][i].iter() {
                    if (current & b).is_empty() {
                        s[i] = b;
                        self.backtrack(current | b, solutions, s);
                        s[i] = Bitboard::default();
                    }
                }
            }
        }
    }
    pub fn solve(&self, initial: Bitboard) -> Vec<[Bitboard; NUM_PIECES]> {
        let mut solutions = Vec::new();
        self.backtrack(
            initial,
            &mut solutions,
            &mut [Bitboard::default(); NUM_PIECES],
        );
        solutions
    }
}

通常backtrackingというとVecをstackとして使ってpush()pop()による更新/復元を使って探索していくことが多いと思うが、この問題の場合は必ず全部使い切るまで探索を続けるものなので固定長の配列を使っている。

手元の環境(MacBook Pro 14-inch, 2021 Apple M1 Pro 32 GB)でrelease buildを使うことで以下のような結果を得た。

  • 8x8-2x2: Found 520 solutions in 325.862ms
  • 6x10: Found 9356 solutions in 11.493s
  • 5x12: Found 4040 solutions in 24.804s
  • 4x15: Found 1472 solutions in 50.362s
  • 3x20: Found 8 solutions in 37.092s

解の数は、反転や回転による同一視をしていないので長方形では4倍、正方形では8倍の値になっている。 それぞれ割れば前述した通りの数になる。

Bitboardによる判定と候補の事前計算によってある程度は効率的に探索ができているはずで、8x8-2x2の盤面なら1秒以内に全解答を列挙できているが、他の長方形はかなりの時間がかかっている…

反転・回転での重複の除外

全解答を探索することはできたが、反転や回転で同一になる解を除外することはできていない。 これらを除外するためには、探索できた解とそれを反転・回転してできるものをすべてチェックし、既に発見済みの解と同一かどうかを判定する必要がある。

そのためには盤面に合わせてBitboardの反転・回転を実装する必要があるが、一旦これは後回しにして、とりあえず盤面のグリッド表現を愚直に作ってしまうことにする。

#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, FromPrimitive)]
pub enum Piece {
    O = 0,
    P,
    Q,
    R,
    S,
    T,
    U,
    V,
    W,
    X,
    Y,
    Z,
}

impl Solver {
    ...

    fn represent_solution(&self, solution: &[Bitboard; NUM_PIECES]) -> Vec<Vec<Option<Piece>>> {
        let mut ret = vec![vec![None; self.cols]; self.rows];
        for (i, b) in solution.iter().enumerate() {
            let p = Piece::from_usize(i);
            for (y, row) in ret.iter_mut().enumerate() {
                for (x, col) in row.iter_mut().enumerate() {
                    if b & (1 << (x + y * self.cols)) != 0 {
                        *col = p;
                    }
                }
            }
        }
        ret
    }
}

これによって2次元配列として表現される盤面を得られるので、単純に反転・回転を実装することができる。 8x8-2x2の場合はXY軸を反転させたものも考慮する必要があるので、それも用意しておく。

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Board(Vec<Vec<Option<Piece>>>);

impl Board {
    fn is_square(&self) -> bool {
        let (rows, cols) = (self.0.len(), self.0[0].len());
        rows == cols
    }
    fn flip_x(&self) -> Self {
        let mut ret = self.clone();
        for row in ret.0.iter_mut() {
            row.reverse();
        }
        ret
    }
    fn flip_y(&self) -> Self {
        let mut ret = self.clone();
        ret.0.reverse();
        ret
    }
    fn flip_xy(&self) -> Self {
        let mut ret = self.clone();
        for row in ret.0.iter_mut() {
            row.reverse();
        }
        ret.0.reverse();
        ret
    }
    fn transpose(&self) -> Self {
        let mut ret = self.clone();
        for (y, row) in ret.0.iter_mut().enumerate() {
            for (x, col) in row.iter_mut().enumerate() {
                *col = self.0[x][y];
            }
        }
        ret
    }
}

あとはこれを使ってHashSetなどに同一解を登録しておき、本当に未発見の解だけを記録するようにすれば良い。

use std::collections::HashSet;

struct UniqueSolutionStore {
    solutions: Vec<[Bitboard; NUM_PIECES]>,
    set: HashSet<Board>,
}

impl UniqueSolutionStore {
    fn add_solution(&mut self, board: Board) {
        if !self.set.contains(&board) {
            self.solutions.push(*pieces);
        }
        self.set.insert(board.flip_x());
        self.set.insert(board.flip_y());
        self.set.insert(board.flip_xy());
        if board.is_square() {
            self.set.insert(board.transpose());
        }
    }
}

impl Solver {
    fn backtrack<S: SolutionStore>(
        &self,
        current: Bitboard,
        pieces: &mut [Bitboard; NUM_PIECES],
        store: &mut S,
    ) {
        if !pieces.iter().any(|u| *u == 0) {
            return store.add_solution(pieces);
        }
        ...
    }
    pub fn solve(&self, initial: Bitboard) -> Vec<[Bitboard; NUM_PIECES]> {
        let store = UniqueSolutionStore::new(...);
        self.backtrack(
            initial,
            (1 << NUM_PIECES) - 1,
            &mut [Bitboard::default(); NUM_PIECES],
            &mut store,
        );
        store.get_solutions()
    }
}

これによって、

  • 8x8-2x2: Found 65 solutions in 362.164ms
  • 6x10: Found 2339 solutions in 11.707s
  • 5x12: Found 1010 solutions in 25.003s
  • 4x15: Found 368 solutions in 51.320s
  • 3x20: Found 2 solutions in 39.203s

と、全列挙していたときと探索時間はほぼ変わらず、正しく重複を除外した解を得ることができたようだ。

高速化

さて、とりあえずは正しく解を列挙できるようになったので、次は探索の高速化を考えてみる。 これには様々な手法やテクニックが古くから研究されていたようだ。

短辺から埋める

まず重要なのが、「最上段から順番に左端から右端へと埋めていく」と考えたときに、盤面が長方形の場合は横長の盤面より縦長の盤面の方が探索が早く終わる、ということ。

これは例えばU型のピースを最初に変な向きで置いてしまったときのことを考えると分かりやすい。

##.............
.#.............
##.............
...............

4x15の盤面で左上から埋めていくと、最上段の残りの13マスをまず埋める探索を繰り返していくが、頑張って埋めたとしても埋める対象が2段目に来た時点で左端の1マスの空間はどうしても埋められないことが分かりそこで探索が止まる。

これが15x4の縦長盤面だと

##..
.#..
##..
....

...

となり、もっと早く2段目の不可能なマスに到達できるので、そこまでの無駄な探索が少なくなる。

なので、この探索方針の場合は横幅は短ければ短いほど効率が良くなる、ということになる。 ので、6x10(6行10列)の横長盤面の場合は10x6(10行6列)の縦長盤面として、5x1212x5に、と縦と横を入れ替えて探索することで効率が良くなる。 解の表示が横長の方が良かったら表示時にだけまた入れ替えて戻してやれば良い。

当然8x8-2x2の正方形の盤面に対しては効果が無いが、それ以外の長方形たちは

  • 6x10: 約12s → 約1.02s
  • 5x12: 約25s → 約344ms
  • 4x15: 約51s → 約82ms
  • 3x20: 約39s → 約3.7ms

と何百倍、何千倍も高速化される。ものすごい効果だ。

X を最初に配置する

次に大きな効果を得られるのが、X型のピースを最初に配置して探索範囲を絞る、というもの。

4. Xピースによる解の重複排除 の記事が詳しいが、X型のピースは反転しても回転しても同じ形になるので、盤面左上の1/4の領域にだけ最初に配置することで探索範囲を絞ることができる。それ以外の領域にX型ピースを置くことで得られる解は必ずその左上領域に置いて得られた解を反転/回転することで得られるものになるからだ。

さらにX型ピースは最も左上に配置すると左上隅に隙間ができてしまうので有り得ない、ということも分かるので、実際に初期配置として有り得る箇所は  \lfloor\frac{(W-1)}{2}\rfloor\times\lfloor\frac{(H-1)}{2}\rfloor-1 通りになる。最も多くても5x12のときの 9通り程度だ。それらを配置した状態を初期状態として、X型以外の11種類のピースで今まで同様のbacktrackingで探索していけば良い。

こうして得られる解は必ずX型ピースが左上の領域に存在することになり、前述した重複除外の手順と逆に、これらが重複を含まない解となる。そしてそれらを反転/回転したものを含めるようにすることで全探索した場合の解を得ることができるようになる。実際にはX型ピースが奇数マス長の辺の中央にいた場合は反転での重複が有り得るし、8x8-2x2の正方形の場合はXY軸を反転させたものへの重複チェックなどが必要になる。

最初の1ピースの配置箇所候補が1/4になるので、単純に探索規模が約1/4に減ることになる、つまり約4倍の高速化が見込まれる。

結果として

  • 8x8-2x2: 約22ms
  • 6x10: 約103ms
  • 5x12: 約43ms
  • 4x15: 約9ms
  • 3x20: 約380μs

と、実際に約4〜10倍程度の高速化が確認された。

github.com

Bitboardの反転/回転

重複除外などの計算で盤面を反転/回転したものを得る必要があるが、簡単にするためにまずは盤面の2次元配列表現を愚直に作って処理してしまっていた。これを高速化するためにBitboardの反転/回転を実装する。 これによってHashSetなどで重複チェックする際にも、キーとして [Bitboard; NUM_PIECES] がそのまま使用でき、2次元配列を作る必要がなくなる。

とはいえ盤面によってビット表現のレイアウトは違うし、それぞれに対する反転や回転を計算するのは簡単ではない。 勿論64回のループを回して1ビットずつ反転後/回転後のビット位置を計算しながらコピーしていくこともできるが、それでは2次元配列作るのとあまり変わらず、旨味がない。

Delta Swap による手法

参考にしたのは以下の記事。 qiita.com

Delta Swap というXOR演算を利用した数回の操作で、maskで指定した範囲のビットを他の箇所のビットと入れ替えることができる。 これを利用することで、例えば隣り合う列同士、のように複数のビットの交換を同時に行うことができる。次は隣り合う2列同士、その次は隣り合う4列同士、とすれば8列の反転が3回のDelta Swapで実現できる。行・列のそれぞれの長さに対し  O(\ln{n}) 程度で盤面上での反転が機能する。 また、8x8-2x2におけるXY軸の反転も、上述の記事に書かれている通り斜めに並ぶmaskを指定することで同様に3回のDelta Swapで実現できる。

盤面の縦横サイズによってビットのレイアウトが変わるので、必要なmaskの値もシフトすべきdeltaの値も異なるものを用意する必要があるが、盤面が決定した時点で事前に計算できるので、それらをVecで用意しておくことで、実際にはDelta Swapの計算は高速に行うことができる。

Const Genericsなんかを使って盤面サイズごとに定数値を埋め込んでおくともっと効率的かな、とも思ったが、試してみた感じではそれほど差異は無さそうだった。実際にBitboardの反転/回転の計算が必要になるのは解が見つかったときだけなので、探索の計算量と比較すると無視できる程度の差にしかならないのかもしれない。

巨大テーブルによるループ効率化

とにかく探索のループが何度も実行されるので、この処理を高速化することが重要になる。

まず使用済みのピースをBitboard同様にビットで管理する。i番目のピースが使用済みか否かのチェックは used & (1 << i) == 0 で判定でき、探索の終了はこの used で使うビットがすべて1になっているか否かで判定できる。そうするとbacktrackingから戻ってきたときにpieces[i]をわざわざdefault値に戻したりする必要はなくなる。

impl Solver {
    fn backtrack<S: SolutionStore>(
        &self,
        current: Bitboard,
        used: usize,
        pieces: &mut [Bitboard; NUM_PIECES],
        store: &mut S,
    ) {
        if used == (1 << NUM_PIECES) - 1 {
            return store.add_solution(pieces);
        }
        let target = current.trailing_ones() as usize;
        for i in 0..NUM_PIECES {
            if used & (1 << i) == 0 {
                for &b in self.table[target][i].iter() {
                    if (current & b).is_empty() {
                        pieces[i] = b;
                        self.backtrack(current | b, used | (1 << i), pieces, store);
                    }
                }
            }
        }
    }
}

ここまでは特に効率化できていないが、ここでself.tableから候補を探索する処理を考えてみる。

このtableには target(埋めるべきマスの位置)それぞれに対してi番目の種類のピースで配置可能なBitboardのリストが格納されている。ピースがすべて未使用なら12個のVecをすべて調べるし、残り1種類なら1個だけのVecに対して判定をしていくことになる。いずれにしても2重ループでの処理となる。

ただ、table自体は変更されるものではないので実際にtargetusedの値の組み合わせに対して探索されるBitboardのリストは不変だ。 少し富豪的な発想だが「使用済みピースの状態数は高々4096(= 1<<12)程度なのだから、これも事前計算でそれぞれ1つのVecとしてすべて用意してしまえば良いのでは?」と考える。

    let mut table: [[Vec<Bitboard>; NUM_PIECES]; 64] = array::from_fn(|_| array::from_fn(|_| Vec::new()));
    for (i, shape) in shapes.iter().enumerate() {
        ...
        for target in 0..64 {
            let b: Bitboard = ...;
            table[target][i].push(b);
        }
    }

のようにVec<Bitboard>を格納する[64, 12]の2次元配列として準備していたものを、

    let mut table: [Vec<Vec<(usize, Bitboard)>>; 64] = array::from_fn(|_| vec![Vec::new(); 1 << NUM_PIECES]);
    for (i, shape) in shapes.iter().enumerate() {
        ...
        for target in 0..64 {
            let b: Bitboard = ...;
            for j in 0..(1 << NUM_PIECES) {
                if (j & (1 << i)) == 0 {
                    table[target][j].push((i, b));
                }
            }
        }
    }

Vec<(usize, Bitboard)>を格納する[64, 4096]の2次元配列に拡張する。こうすることで、usedに対応する全候補リストを一発で引けるようになる。

    fn backtrack(
        &self,
        current: Bitboard,
        used: usize,
        pieces: &mut [Bitboard; NUM_PIECES],
        store: &mut dyn SolutionStore,
    ) {
        ...
        let target = current.trailing_ones() as usize;
        for &(i, b) in &self.table[target][used] {
            if current & b == 0 {
                ...
            }
        }
    }

結局判定する内容は変わらないが、このようにループ処理を変えるだけでも意外に明確に速度が改善された。

ただし、初期化のコストは大幅に増大する…。tableの準備段階で1<<12回のループを回すことになるし、格納する値も冗長になりメモリ消費量が増える。手元の環境では6x10の盤面に対し巨大テーブルを使うようにすることで探索時間が約70msから約50msへと短縮されたが、そのぶん初期化にかかる時間が約0.1msから約70msへと激増していて、トータルの実行時間でいうとむしろ遅くなっている。このあたりは探索を速くしたいのかトータルでの実行時間を短くしたいのか、によって使い分けることになるだろう。

github.com github.com

もう一方のループ効率化

巨大テーブルを使わないとどうしても速くならないのか、というとそうでもなく、usedの判定をしながらループを回すのも多少は効率化できる。

毎回12回のループを回して使用済みの場合はskip、としていると無駄な計算が多くなる。

    for i in 0..NUM_PIECES {
        if used & (1 << i) != 0 {
            continue;
        }
        ...
    }

ので、ここでもビット演算によって未使用ビットに該当するものだけを列挙するように変更する。

    let mut u = !used & ((1 << NUM_PIECES) - 1);
    while u != 0 {
        let i = u.trailing_zeros() as usize;
        ...
        u &= u - 1;
    }

これも将棋Bitboardで学んだテクニック。u &= u - 1で最下位の1を消していくことができるので、これをすべて0になるまで繰り返すだけ。少数のビットしか未使用のものがない場合に無駄なループ処理を省くことができる。

これによっても速度は改善し、巨大なテーブルを用意しなくても90msかかっていたものが70ms程度になるくらいの効果があった。

孤立点検出による枝刈り

探索処理自体の高速化はこれくらいにして、最後に枝刈りについて考える。

探索途中のある状態において、この先はどう置いても解が得られないと分かっている場合は、その時点で探索を打ち切ることでその先での無駄な探索を省くことができる。この枝刈りをどれだけできるかでも大きな速度の差が出る。前述した縦長と横長の交換も枝刈りを多く発生させるための工夫だ。

まず一番分かりやすいのはU型ピースを壁際に配置するときで、

#.#.
###.
....
....

##..
.#..
##..
....

のように1箇所の穴が壁際に生じてしまう向きで配置すると、その穴のマスはどうやっても埋めることができないのでその先の探索はすべて無駄になる。

同様に四隅に空白ができるような配置も考えられる。左上から埋める限りはその左上に空間はできないように埋めていくが、それ以外の3箇所の角では起こりうる。

########
########

...

###.....
..##....

こうした配置は最初から考慮できるので、候補の事前計算時に除外しておくことはできる。

あとは探索途中の状態における孤立空間を検出して枝刈りできるかどうか。

######
###o..
.#....

...

のように#が埋まっているとき、次に埋めるべきマスがoになるが、ここで次に配置するピースによっては、その右側や左下に空間が生じ得る。

######
####..
.#.##.
....##

######
####..
.#.#..
..###.

のような感じ。少なくとも5の倍数の面積でない空間が生じていると、もうそれらを埋める手段は存在しないので、可能であれば即座に探索を打ち切ってしまいたい。

しかし、こういった空間の検出やその面積の計算まで毎回行うのは探索の高速化には逆に計算負荷が増大して逆効果になったりする。検出のコストと枝刈りの効果のバランスを考える必要がある。

Bitboardを使用して簡単に検出することができるのは、孤立点の空間だ。あるマスが空いていて、その上下左右がすべて壁もしくは他のピースによって埋まっている、という状態。これは

..#..
.###.
..#..

のようなX型のmaskを用意し、そのmaskと現在の盤面BitboardのAND演算の結果が

..#..
.#.#.
..#..

の値になるか否か、という判定で簡単に実現できる。盤面上のマスすべてに対してこのmaskと値を事前に計算しておけば、いつでもこういった「穴」のマスを検出することができる。

とはいえ実際にこのような「穴」が生じ得るのは、targetとなる埋めるべきマスにピースを置いた後の、その周辺だけ。なので毎回の探索ごとに穴の出現を判定するのは最小限にしたい。

targetを埋めるようにピースを置いたときに穴が生じやすいのはtargetのすぐ右隣のマス、もしくはすぐ下の段の左隣のマス、だ。先述の図でいうとoに対してXの位置。この2点だけに絞ってピースを置いた後に穴が生じるかどうかを判定して枝刈りを行うことにした。 本当はtargetの場所によって穴の発生が起こりやすい位置が違うかもしれないので一律に同じ相対位置にしないで調整した方が良いかもしれないが、そこまではやっていない。

######
###oX.
.#X...

...
    fn backtrack(
        &self,
        current: Bitboard,
        used: usize,
        pieces: &mut [Bitboard; NUM_PIECES],
        store: &mut dyn SolutionStore,
    ) {
        ...

        let target = current.trailing_ones() as usize;
        for &(i, b) in &self.table[target][used] {
            if current & b == 0 {
                let next = current | b;
                // `target`に対してチェックすべき`holes`は初期化時に計算しておく
                if self.holes[target].iter().any(|&(u, v)| next & u == v) {
                    continue;
                }
                pieces[i] = b;
                self.backtrack(next, used | (1 << i), pieces, store);
            }
        }
    }

最終的にこれらの工夫を施すことで、巨大テーブルを使用し初期化コストを無視することで探索自体は

  • 8x8-2x2: 約22ms → 約9ms
  • 6x10: 約103ms → 約44ms
  • 5x12: 約43ms → 約18ms
  • 4x15: 約9ms → 約3ms
  • 3x20: 約380μs → 約147μs

くらいまで短縮することができた。 6x10ではどうしてもまだ40ms以上かかってしまうが、まぁ10秒以上かかっていた頃からすれば200倍以上は速くなっているし、じゅうぶん速くはなったと思う。

github.com

あとはマルチスレッド化したりすればもっと速くなるのかなぁ…。

その他の実装・手法

ここまでまったく触れなかったが、Pentomino Solverの実装として"Knuth's Algorithm X"というものを使う手法があるらしい。

en.wikipedia.org

Pentominoを含むPolyominoによる敷き詰め問題をExtract cover problemとして考え、その解法としてDancing Linksというデータ構造を利用して効率的に計算していく、というものらしい。 以下の記事が詳しい。

matsu7874.hatenablog.com

実際に試していない(RustでLinked List的なものを扱うのが面倒そう、というのもあり…)が、これを使ってもそこまで劇的に速くなるわけでもないっぽい。 参考記事でも触れているが全パターンの探索には効率的かもしれないが枝刈りのような処理がないはず?なので、今回のようにX型を最初に置いたり孤立点チェックをしたりといった高速化の工夫の方が探索時間の短縮には効果的なように思える。

WebAssembly化してWebAppで使う

RustでSolverを書けたので、WASM化してWebAppから使えるようにしてみた。 最近はViteを使ってReact+TypeScriptの環境をさくっと作れると聞いたので、それで。 探索は100msかからないくらいだしメインスレッドで実行しても良いかな、とも思ったが念のためWebWorkerで実行するようにしている。

sugyan.com

手元の環境ではCLIで実行するときと遜色ないパフォーマンスがブラウザでも実現できているが、どうもスマホ(iPhone SE)で試してみたところ 巨大テーブルを使う方は最初の初期化に10秒以上の時間がかかる。メモリ確保がすごい重いんだろうか… 一度読み込んでしまえばその後はそこそこの速度になるようだけども。ともかくこれだとWebWorker経由じゃないと使いものにならない。

100msかからずに全解答を列挙できるようなブラウザ上で動く実装は他では見かけなかったので現時点では最速のWebAppになっているかもしれない。 もっと速いものを知っている方は教えてください。

参考

とても参考にしたページ。

まとめ

最大限にチューニングするとどこまで速くできるものなのかは気になるところだけど、とりあえず自分が満足できるくらいのパフォーマンスでの探索は実現できた。

AT Protocol(Bluesky)のためのRustライブラリを作った

前記事OCamlやってくぞ、と書いたけど結局Rustです。

Bluesky

Twitter代替の候補として噂される(?)分散型SNS Bluesky。 現状ではまだprivate betaということで招待コードが無いと使えないのだけど、先月運良くコードをいただくことができて使い始めてみている。

一通りのSNS的な動きはしているものの、まだまだ鋭意開発中ということで足りていない機能があったり 日々新機能が追加されたりと目紛しく動いている世界のようだ。

AT Protocolとエコシステムの現状 (〜2023/04)

AT Protocolについてはこちら。

atproto.com

日本語では以下の記事が詳しいでしょう。

ざっくりとした理解では、新しい分散型SNSのために「AT Protocol」が開発されていて、いま使っているBlueskyというSNSもこのAT Protocolに従って実装されているSmall-worldの一つである、という感じなのかな。

「AT Protocol」は様々なテクノロジーの総称という感じで、その中の汎用通信レイヤーとして「XRPC」というものがある。これを使ってサーバーと通信する、ということらしい。 BlueskyはWeb UIも提供されているが、DevToolsを覗いてみる限りでは確かにすべてのデータ取得や更新などこのXPRCのリクエストによって行われているようだ。

GitHubでは以下のリポジトリが公開されている。

主要なプロトコル実装としてTypeScriptで書かれた atproto があり、そのGo版ということで indigobluesky-social organizationによって管理されている。

その他の非公式の言語実装やClient, Applicationなどが以下のrepositoryにまとめられている。

言語としてTypeScriptがメインであり それを使ってすべての現存機能が動かせるので、Webフロントエンドで完結する、ということでWeb Clientが多く作られているようだ。

Rust版の実装

上記で紹介されているライブラリでRustのものは、(2023/04時点で)以下の adenosine のみ。

このrepository ownerはBlueskyの中の人ではあるが、公式としてGitHubのorganizationに入れられはしなかった、ようだ。

Lexiconとコード生成

前述したXRPCによるメッセージングは、すべて Lexicon というスキーマシステムによって型が定義されている。 JSON Schemaのように記述されるJSONによって、すべてのリクエストやレスポンス、その中のデータ型やフィールド名などが定義される。

ので、これがAPI通信の仕様のすべて、ということになる。

前述した atprotoindigoAPIライブラリは、このLexicon schemaを示すJSONファイルからコード生成によって作成されているようだ。

この仕組みで作っていない限り、どうしてもclient libraryは最新のAPIに追従できない、ということになる。AT Protocolはまだまだすごい頻度で変更が加えられていて、lexicon schemaも毎日、とはいかないまでも毎週くらいのペースでは何らかの変更がある。

上述の adenosine は、このコード生成によって作られたものではないため、実際既に最近追加されたAPIは使えないようだった。

その他にも reqwest の blocking client に依存している、とか 結局内部のxprc clientには serde_json::Value を渡していて何でも自由にできてしまう、など 微妙だなと思う点もあったので、自分でまったく別のRustライブラリを作ってみよう、ということになった。

(一応他にもそれっぽいlibraryやrepositoryを検索して先行事例を調査してみたりもしたが、ちゃんとそういったコード生成によって作られているものはなさそうだった。)

自作Rust版実装: ATrium

github.com

AT Protocolのための小さなライブラリが集まり青空を望む中庭、ということでATrium、という名前に。最初は atprs とか雑な名前で書き始めていたけど ChatGPT に「いいかんじのプロジェクト名ないですかね」と相談したところ、ATriumという名前を提案してくれたので採用した。最近 YAPC::Kyoto の会場でも聞いた単語だったし丁度いいな、と。

Lexicon schema

まずは必要になるのはLexicon schemaのJSONを読み込むためのライブラリ。 これ自身のJSON Schemaなどが存在するわけではなく、実際のvalidationは zodを使って書かれている ので、これを必死に翻訳する形で。

このJSON自体もかなり柔軟性があり、色んな入力が有り得るので大変…。いちおう type の tag を使って判別可能なようにはなっているので、それを使って enum に振り分けることでどうにか serde で正しく読み込めるようになった。 Option なfieldが多く、一度 deserialize してから元のJSONに同等に戻せるようにすると記述が大変だったので、serde_withskip_serializing_none を使った。

unionで新しい定義を作られるところが、単純に enum に変換すると一段深くなってしまうしtagがずれても困るし…ということで仕方なくいちいちコピーしてしまっているが、もっといい方法あるだろうか。…macroを使えば良いのか?

コード生成

ともかくLexicon schemaを正しく読み込むことができれば、あとはそこからRustコードに落とし込んでいける。 細かいところはまだ実装できていないが、基本的な object などはだいたい書けている、と思う。

Lexiconではdefsの名前は camelCase だが Rustコードでは 型名は PascalCase で field名やmodule名は snake_case にしたい、などの変換が必要だったので、 heck というライブラリを使用した。

正しくnamespaceをマッピングさせていれば ref はそのまま定義済みの型として参照できるが、 union はまぁ厄介で、それ用の enum を追加で定義して Lexicon解析のとき同様に $type tagで判別して振り分けるようにする必要があった。

とりあえず正しいコードとして生成されているかどうかは cargo build で確認できて 通ればまぁ動くだろう、という判断ができて便利だった。

API設計

型の定義だけならまだラクだが、Lexiconには query もしくは procedure のXRPCリクエストの定義が含まれる。 これは関数の実装を提供することになるが、そのためにはHTTP requestを実行するためのclientが必要になる、がAPIライブラリとしてはそういったものは含めたくない、と考えた。

実はRustでHTTP clientをマトモに使ったことが無かったが、 hyper だったり isahc だったり surf だったり、いろいろあるらしい。ライブラリでClientも含めることになると、どれを使うか判断する(もしくはすべてサポートするなどの)必要がでてきてしまう。

ので、それらは回避して HttpClient というTraitを定義して、それを実装するものを外部から注入する形にした。 各XRPCリクエストは「HttpClient をSupertraitとする、デフォルト実装を持つTrait」となり、外部で実装したClientがそれらの実装を宣言すれば各リクエストが使えるようになる、ということになる。

#[async_trait::async_trait]
pub trait HttpClient {
    async fn send(&self, req: http::Request<Vec<u8>>) -> Result<http::Response<Vec<u8>>, Box<dyn Error>>;
}

最初こういうのもライブラリとして存在しているのでは、と探して http-client というのがあったので使おうとしたが、同梱されている HyperClient を使ってみたら依存のtokioのバージョンが古すぎて動かず、またこのTraitで使われている http-types も良いけど http を使ったほうがより汎用的で良いですよ、とChatGPTが教えてくれたので自前で簡単に定義することにした。

ともかく、この形にすることで、ライブラリのユーザーは一手間はかかるけど自分の好きなHTTP clientを使って各種XRPCリクエストを送ることができるようになっている。はず。

とりあえずこうして作った APIライブラリをまず atrium-api という名前でpublishした。

docs.rs https://crates.io/crates/atrium-api

Lex

ちなみに Lexicon schema解析のための型定義だけのもので一つのライブラリとして切り出して作っていて、まだ publishはしていないけどやる予定。 上記の atrium-api の設計が気に入らない、という人はこれを使って自分でコード生成を作って別のAPIライブラリを作ってくれれば良いと思います。

CLI

作成したAPIの動作実験も兼ねて、 mattn/bsky のようなCLIも作ってみている。 これはこれで便利、なのかな? バイナリ配布だけしてみても良いかもしれない。

今後

まだまだ未完成で未実装のところも多いので埋めていく予定。 あとは本家のLexicon更新を検知して自動でコード生成してpushして publishまで…が自動化できても良さそうだけど そこまでは無理か? ちょっと調べてやってみたいところ。

あとは…折角Rustで動かせるようになるならTauriとか使ってGUIアプリまで作れると良いのかな… さすがにそんな余裕は無さそうだけども。

ともかくちゃんと使ってもらえるかもしれない(現時点で22 starsとかだけど)OSSっぽいものを初めて作った気がするので、まずは色々整備していきたいところ。

40歳から始める関数型言語、OCaml

というわけで、今年に入ってからのここ数ヶ月、OCamlを勉強し始めている。

動機

これまで「関数型言語をちゃんと触ったことがない」ということが若干コンプレックスになっていた。40歳になった今、唐突に始めてみる気になったので、やることにした。

Why OCaml

そもそも関数型にどんな言語があるのか、それぞれがどんな特徴であり、どういったところで使われているのか、という情報すらほとんど知らなかったので、「関数型言語やってみたいんですけど、どれがいいんすかね?」と某所で雑に相談したところ、OCamlを挙げてもらったので、素直にそれに従ってみることにした。

そんな適当で良いのか?とも思うけど、とにかくどれであっても触ってみないことには何も分からないし。実際、OCamlを選んで間違いは無かったと今は思う。

学習方法

Real World OCaml

とにかくOCamlの学習にはこれが良いらしい、という話をきいた。

dev.realworldocaml.org

ので、これを最初の数章は頑張って読んでみて、あとは実際にコードを書いてみつつ必要になったら参照して勉強していく、という感じで。 実際とても詳しく丁寧に書かれていて、とても良い本だと思う。

Github Copilot と ChatGPT

これらはもう現代のプログラマにとって欠かせないものになっていると思う。

最近のメジャーな言語と比較してOCamlに関する学習データがどの程度の量と質で、どの程度優れたコード出力能力であるのかは分からないが、少なくとも初心者から始める人間にとっては十分に助けになる。

特にChatGPTは、環境構築からライブラリの使い方などは勿論、「Rustでこう書いてたのはOCamlではどう書くの」とか「こういうのできないの」「こう書いてみたけど他にも書き方あるのかな」みたいな、独り言で呟くようなことでもChatで気軽に書いて質問できて体験が良かった。 めちゃくちゃ親しくて時間を奪うこと気にせずに何でも質問できる友人、が隣に居ればそういう人に頼れるかもしれないが、そういう友達が居ない人間にとってはこうした心理的なハードル低く幾らでも質問できる存在はとても有り難いと思う。

とはいえやはり正確性は保証されなくてChatGPTも平気で実在しないライブラリ関数をでっちあげて使用例を提示してきたりするし、油断せずにちゃんと公式ドキュメントなど探して確認しながら書く必要はある。 このへんは仕方ないと腹を括って、「俺が学習データを提供してやるぜ」くらいの気概でできるだけ良い(と自分が思う)コードを書いてとにかく公開していく。

オンラインジャッジ (競プロ)

簡単なコード片を書いて正しい入出力を得られたか確認できる、また別の人の書いた同じ目的のコードを気軽に参照できる、という点で競技プログラミングの過去問などは良い学習材料になると思う。とりあえず他人と競うことは考えず、オンラインジャッジシステムとして利用させてもらう。

個人的には LeetCode でやりたかったが、LeetCodeにはOCamlの選択肢が無い…。ので、 AtCoder を使うことにした。 AtCoder Problems の「Boot camp for Beginners」 というのがあることを @naoya_ito さんのTweet で知ったので、真似してこれらを解いてみることにした。

とはいえAtCoderOCamlのランタイムや使えるライブラリが少し古くて(2023/04時点)、手元で Core 最新を使って動くコード書けて意気揚々とSubmitしてみたら CE (Compilation Error) 出てガックリすることも。 ここは今後 言語のアップデート で更新されてより使いやすくなることを期待している。

簡単な問題を解くことで基礎的なデータ構造やアルゴリズムの扱いは練習できるが、難易度が上がると当然 数学的な思考力やより高度なアルゴリズムの知識が主眼になってくる。 そこは言語習得とはまた別の話になってくるのでそこまで頑張る必要はない(本当に競プロを頑張るならC++とかRustとか他の言語でやったほうが良いと思う)、ということでほどほどにして止めるつもり。

Advent of Code

より実践的に「プログラミングによる問題解決」をできるようにする練習として、 Advent of Code は非常に良い題材だと思う。 AtCoderのような競技プログラミング的な要素もあるが、それだけではなく

  • 入力データが必ずしも扱いやすいものばかりではない
    • → 様々な形式に対応したparse処理を書く練習になる
  • part1/part2 で同じ入力から異なる解を出す、など出力も様々な型・形式になり得る
    • → interfaceを考える練習になる
  • アルゴリズムだけで解決しないこともある
    • → 力技での膨大な探索や泥臭い実装などが必要になることも

といった点でまた別の実装力を鍛えることができると考えられる。

2022を完走した記事 にも書いたが、2022年の問題は特にバランス良く様々な題材のものがあって言語習得の練習に十分に適している、と感じた。

というわけで、OCamlAdvent of Code 2022 を解くチャレンジをしている。

github.com

まだ18日目までだが、どうにか最後まで頑張りたい…!

その次?

やはり「問題を解く」だけではなく、最終的には「何らかのアプリケーションを自作する」ことができるくらいにはなりたいので、それを考えていく。

自分の場合は「過去に他の言語で作ったことがあるもの」「自分が使いたいもの」を作るのが最もモチベーションが高くなるので、そういうもので考えると、、、今はコンピュータ将棋関連だろうか。 幸い(?) opam を検索してみた限りではビットボード実装や将棋関連のライブラリなどは存在していないようなので、自分で作ってみるのは面白そうだ。関数型言語での将棋プログラムなんて全然需要は無さそうだけどw とりあえずOCamlでの実装がC++やRustと比較してどの程度の速度になるのかは知りたいので perft できるくらいまではやってみたい。

あとは今の流行でいうと Bluesky で使われている AT Protocol の実装をしてみる、とかだろうか。これもわざわざOCamlでやろうとする人はあんまり居なそう…

所感

とりあえず数週間触ってみての感想。

|> は多用することが分かったので自作キーボード(Claw44)のキーマップにマクロとして追加した。

関数型という概念

結局、現状どれくらい理解できているだろうか…。まだまだ理解が浅いとは思う。

基本的に Base ライブラリを使用しているが、 List に対する様々な処理が再帰で表現できるというのを見て驚かされた。というか List というデータ構造がこんなにも使いやすくて色々できるんだなぁ、と少し親しみを持てるようになった。 とりあえず、 List などを使って |> でパイプを繋げてデータを変換していく、という操作は慣れてきた。

最初はどうしても「手続き型の言語だと普通こう書くので、それを関数型で表現すると…」と変換していく感じにはなりがちだったが、だんだん「この関数とこの関数を組み合わせてこういう関数を作って、そしてこの入力にこういう出力を返す関数を作る、」という感じで考えられるようになってきた気がする。

高階関数の部分適用とか使ってみるとめっちゃ便利だな〜と感心したり。

プログラミングHaskell という本を何年か前に買ったものの序盤ですぐに挫折してしまっていたのだけど、OCamlを通じて多少なりとも理解が深まってきたおかげか、今は再チャレンジして楽しく読めている。

OCamlの書き味

思っていた以上にツールチェインなどが整っていて、環境構築からエディタ設定などほとんど問題なくできて良かった。 VSCodeでは OCaml Platform 入れるだけだし、 ocamlformat を使って自動整形もできる。このあたりの「揃っていて欲しい」ものは大抵ちゃんと揃っている。

コンパイラのエラーメッセージは正直あまり親切な感じはなくて、型が合わないのはどこをどうすれば… みたいなのがなかなか詰まりやすかったりした。とはいえ「ちゃんとコンパイルが通ればだいたいちゃんと動く」という感覚がRustに近いものがある、と感じる。

あとは dune がRustでいう cargo と同じような感覚で使えるので、これも便利。

Rust, Python の経験

Rustを書いたことがあると、色んなところで「似ているな」と感じるところがあった。例えば option とかそれに対するパターンマッチとか。 Rustのiteratorをメソッドチェーンで繋いで処理するのと同じような感覚で |> で繋ぐ処理を書けるな、とか。 Rustがまったくの未経験だったらもっとOCamlに戸惑っていたかもしれない。

Pythonはそんなに似てないかな…? Haskellみたいに内包表記があるともっと違う感想になったかな。 ただOCamlの影響で自分が書くPythonコードがちょっと変わってきたような気がする。関数の使い方をより意識するようになったというか、なんというか。上手く言語化できないけど。

関数型言語をやるとプログラミングが上手くなる」という言説を聞いたことがあるが、こういうところで少しは効果がでるのかな…?気のせいかもしれない。

AIとの親和性

ところで Github Copilot にコードの補完をしてもらうときに、関数のシグネチャの情報はわりと重要だと思っていて。 「こういう名前の関数でこの型のこの名前の引数を受け取って、この型の値を返す」という情報が書いてあると当然補完も正確になりやすいだろう、と。

一方でOCaml型推論が強力なので、型はあるもののtype annotationを書く必要が殆どなく、またちょっとした処理は無名関数を書くことが多いし、そうでなくとも let rec loop acc x = ... とか let f x y = ... とか、簡潔な書き方になりがち。 そうすると、補完しようとするAIとしては情報が足りなすぎて難しいよなぁ、ということを思った。

明瞭な関数名や型注釈をいちいち書くのは面倒で人間としては省略できる方が有り難いが、それはそれでAIに助けてもらいながら書く場合には意図や情報を渡せるという点で良いのかもしれない。 今後新しく作られる言語の設計もそういう観点が考慮されるようになってくるんだろうか、とか。

まとめ

コードを書く仕事はAIに奪われていくかもしれないが、プログラミングは楽しいので好きなように書きたいだけ書いたら良い。