ミツイの発表資料まとめ

これまでにカンファレンスなどで発表した資料をここにまとめます。 随時更新です。

最終更新: 2024-02-28

↓↓↓ 発表日降順で並んでいます

wasm-bindgen で「この型が欲しいときはこう書く」集

この記事は Rust Advent Calendar 2024 の 8日目の記事です。

wasm-bindgen で wasm に型を付ける

Rust は wasm にコンパイルできるよう意図された言語でもあります。Rust コードを wasm にコンパイルしてしまえば、ブラウザをはじめとした wasm ランタイムで実行できてとても便利です。

wasm-bindgen を使うと JavaScript から呼び出しやすいインターフェースを自動で生成できます。さらに TypeScript の型定義ファイル (.d.ts ファイル) も生成されます。
しかし引数や返り値に JsValue を使ってしまうと .d.ts 側では any 型になってしまいます。これではせっかくの型定義が台無しです。
この記事では .d.ts 側で上手く型付けされる Rust コードを書くことを目標とします。「.d.ts 側でこの型が欲しいなら Rust コードではこう書く」というプラクティスをひたすら列挙していきます。

ここで紹介している例は下記のリポジトリにまとめています。
コンパイルした wasm を TypeScript から呼び出すテストコードもあるので挙動の理解に役立つはずです。

github.com

事前準備

下記のクレートを使用します。

• wasm-bindgen
• tsify-next
• serde

事前に Cargo.toml に書き加えておきましょう。

[dependencies]
wasm-bindgen = "0.2.84"
tsify-next = "0.5.4"
serde = "1.0.215"

まとめ

※ ↵ は改行を表す

	TypeScript の型	Rust でこう書く	備考
◾️	number	u8, u16, u32, i8, i16, i32	string から暗黙に型変換される
◾️	number	f32, f64	string から暗黙に型変換される
◾️	bigint	u64, u128, i64, i128	string から暗黙に型変換される
◾️	string	String, &str
◾️	boolean	bool	number から暗黙に型変換される
◾️	Symbol	-	無し
◾️	null	#[derive(Tsify)]↵ struct Null;
◾️	undefined	-	無し
◾️	T[]	Vec<T>	T は具体型でなければいけない
◾️	Uint8Array	Vec<u8>
◾️	Int8Array	Vec<i8>
◾️	Uint16Array	Vec<u16>
◾️	Int16Array	Vec<i16>
◾️	Uint32Array	Vec<u32>
◾️	Int32Array	Vec<i32>
◾️	BigUint64Array	Vec<u64>, Vec<u128>
◾️	BigInt64Array	Vec<i64>, Vec<i128>
◾️	Float32Array	Vec<f32>
◾️	Float64Array	Vec<f64>
◾️	Function	js_sys::Function	引数や返り値の型を明示できない
◾️	[T1, T2, T3]	#[derive(Tsify)]↵ struct MyTuple(T1, T2, T3);	T1 などは具体型でなければいけない
◾️	"Foo" | "Bar" | "Baz"	#[derive(Tsify)]↵ enum MyUnion { Foo, Bar, Baz }
◾️	T1 | T2 | ...	#[derive(Tsify)]↵ enum MyUnion { T1, T2, ... }	T1 などは具体型でなければいけない
◾️	interface { ... }	#[derive(Tsify)]↵ struct MyInterface { ... }
◾️	{ prop?: T; }	#[derive(Tsify)]↵ struct MyInterface { #[tsify(optional)] prop: Option<T> }	T は具体型でなければいけない
◾️	{ prop: T | null; }	#[derive(Tsify)]↵ struct MyInterface { prop: Option<T> }	T は具体型でなければいけない
◾️	Record<K, T>	#[derive(Tsify)]↵ struct MyRecord(HashMap<K, T>);	K, T は具体型でなければいけない
◾️	Map<K, T>	#[derive(Tsify)]↵ struct MyMap(HashMap<K, T>);	features = ["js"] が必要 K, T は具体型でなければいけない Record<K, T> から暗黙に型変換される
◾️	function f(x?: T)	fn f(x: Option<T>) { ... }	T は具体型でなければいけない
◾️	namespace { ... }	#[derive(Tsify)]↵ #[tsify(namespace)]↵ enum MyNamespace { ... }

これ以降、具体的に解説していきます。

プリミティブ型

JavaScript には7種類のプリミティブ型があります。
数値 number, é•·æ•´æ•° bigint, 文字列 string, 論理値 boolean, シンボル Symbol, null, undefined です。

数値 number

number が欲しいときには Rust の u8, u16, u32, i8, i16, i32, f32, f64 を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_number_into_rust_u32(n: u32) -> u32 {
    console::log_1(&format!("value: {:?}", n).into());
    return n;
}

// .d.ts

export function from_ts_number_into_rust_u32(n: number): number;

• 挙動確認のためのテストコード

.d.ts ではどれも number 型になってしまいますが、もちろん Rust に受け渡したときに保持できる値の範囲が変わってきます。
例えば i8 で型付けすると保持できるのは -128 ~ 127 です。

では i8 の最小値・最大値を超える値を JavaScript から渡すとどうなるでしょうか。
なんと「オーバーフロー・アンダーフローして範囲内に収める」という挙動になります。

// JavaScript

from_ts_number_into_rust_i8(128); // i8 の最大値 127 を超えている！
// => log: "value: -128"

型検査でもエラーにならず実行時の例外にもならないので、この挙動には驚くかも知れません。

また .d.ts で number で型付けされるものの、「数値として解釈可能な文字列」を渡すことが可能です。
内部で数値としてパースされます。

// JavaScript

from_ts_number_into_rust_i8("42"); // 文字列を渡す
// => log: "value: 42"

é•·æ•´æ•° bigint

number が欲しいときには Rust の u64, u128, i64, i128 を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_bigint_into_rust_u64(n: u64) -> u64 {
    console::log_1(&format!("value: {:?}", n).into());
    return n;
}

// .d.ts

export function from_ts_bigint_into_rust_u64(n: bigint): bigint;

• 挙動確認のためのテストコード

もちろん bigint を渡すことが可能です。例えば 9_007_199_254_740_991n など。
一方で number を渡そうとすると例外が投げられます。

// JavaScript

from_ts_bigint_into_rust_u64(9_007_199_254_740_991n);
// => log: "value: 9007199254740991"

from_ts_bigint_into_rust_u64(42); // number は渡せない
// => 例外が投げられる

数値に解釈可能な文字列を渡せる仕様も健在です。

// JavaScript

from_ts_bigint_into_rust_u64("9007199254740991");
// => log: "value: 9007199254740991"

文字列 string

string が欲しいときには Rust の String または &str を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_string_into_rust_string(s: String) -> String  {
    console::log_1(&format!("value: {:?}", s).into());
    return s;
}

// .d.ts

export function from_ts_string_into_rust_string(s: string): string;

• 挙動確認のためのテストコード

string 以外の値を渡すと例外が投げられます。暗黙に数値が文字列化されるような挙動はありません。

// JavaScript

from_ts_string_into_rust_string(42);
// => 例外が投げられる

論理値 boolean

boolean が欲しいときには Rust の bool を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_boolean_into_rust_bool(b: bool) -> bool {
    console::log_1(&format!("value: {:?}", b).into());
    return b;
}

// .d.ts

export function from_ts_boolean_into_rust_bool(b: boolean): boolean;

• 挙動確認のためのテストコード

JavaScript から呼び出すときには boolean の他に number も受け入れてくれるようです。
0 を渡せば Rust 側で false と解釈されます。0 以外の値は true と解釈されます。

// JavaScript

from_ts_boolean_into_rust_bool(true);
// => log: "value: true"

from_ts_boolean_into_rust_bool(false);
// => log: "value: false"

from_ts_boolean_into_rust_bool(1);
// => log: "value: true"

from_ts_boolean_into_rust_bool(0);
// => log: "value: false"

シンボル Symbol

Symbol を受け渡しする方法はありません。

null

関数の引数を null で型付けしたい場面は無い気がしますが、そのように書く方法はあります。
Rust のユニット構造体 (unit struct) から型を生成すると null になります。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
pub struct Null;

#[wasm_bindgen]
pub fn from_ts_null_into_rust_unit_struct(_null: Null) -> Null {
    console::log_1(&format!("value: {:?}", _null).into());
    return _null;
}

// .d.ts

export type Null = null;

export function from_ts_null_into_rust_unit_struct(_null: Null): Null;

• 挙動確認のためのテストコード

null のエイリアスとして Null が定義されました。
Null を引数や返り値に使うことで null で型付けできます。

null が登場するもっと実用的な例は string | null などの Nullable な型でしょう。それについてはこの記事の後の方で解説します。

undefined

引数や返り値を undefined で型付けする方法はありません。

実用的な例として省略可能な引数を表現するときに undefined が登場します。それについてはこの記事の後の方で解説します。

配列型・TypedArray

引数や返り値に配列型を指定することで複数の値をまとめて受け取ったり返したりできます。

T[]

T[] が欲しいときには Rust の Vec<T> を使います。
ただし T は具体型でないとダメで、型パラメーターを使って fn f<T>(x: Vec<T>) { ... } のようには書けません。

// Rust

#[wasm_bindgen]
pub fn from_ts_array_into_rust_vec(strings: Vec<String>) -> Vec<String> {
    console::log_1(&format!("value: {:?}", strings).into());
    return strings;
}

// .d.ts

export function from_ts_array_into_rust_vec(strings: (string)[]): (string)[];

Uint8Array

Uint8Array が欲しいときには Rust の Vec<u8> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_uint8array_into_rust_vec(numbers: Vec<u8>) -> Vec<u8> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_uint8array_into_rust_vec(numbers: Uint8Array): Uint8Array;

Int8Array

Int8Array が欲しいときには Rust の Vec<i8> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_int8array_into_rust_vec(numbers: Vec<i8>) -> Vec<i8> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_int8array_into_rust_vec(numbers: Int8Array): Int8Array;

Uint16Array

Uint16Array が欲しいときには Rust の Vec<u16> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_uint16array_into_rust_vec(numbers: Vec<u16>) -> Vec<u16> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_uint16array_into_rust_vec(numbers: Uint16Array): Uint16Array;

Int16Array

Int16Array が欲しいときには Rust の Vec<i16> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_int16array_into_rust_vec(numbers: Vec<i16>) -> Vec<i16> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_int16array_into_rust_vec(numbers: Int16Array): Int16Array;

Uint32Array

Uint32Array が欲しいときには Rust の Vec<u32> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_uint32array_into_rust_vec(numbers: Vec<u32>) -> Vec<u32> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_uint32array_into_rust_vec(numbers: Uint32Array): Uint32Array;

Int32Array

Int32Array が欲しいときには Rust の Vec<i32> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_int32array_into_rust_vec(numbers: Vec<i32>) -> Vec<i32> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_int32array_into_rust_vec(numbers: Int32Array): Int32Array;

BigUint64Array

BigUint64Array が欲しいときには Rust の Vec<u64> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_biguint64array_into_rust_vec(numbers: Vec<u64>) -> Vec<u64> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_biguint64array_into_rust_vec(numbers: BigUint64Array): BigUint64Array;

BigInt64Array

BigInt64Array が欲しいときには Rust の Vec<i64> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_bigint64array_into_rust_vec(numbers: Vec<i64>) -> Vec<i64> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_bigint64array_into_rust_vec(numbers: BigInt64Array): BigInt64Array;

Float32Array

Float32Array が欲しいときには Rust の Vec<f32> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_float32array_into_rust_vec(numbers: Vec<f32>) -> Vec<f32> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_float32array_into_rust_vec(numbers: Float32Array): Float32Array;

Float64Array

Float64Array が欲しいときには Rust の Vec<f64> を使います。

// Rust

#[wasm_bindgen]
pub fn from_ts_float64array_into_rust_vec(numbers: Vec<f64>) -> Vec<f64> {
    console::log_1(&format!("value: {:?}", numbers).into());
    return numbers;
}

// .d.ts

export function from_ts_float64array_into_rust_vec(numbers: Float64Array): Float64Array;

クロージャー

関数・クロージャーで型付けする上手い方法は無いようです。
限定的ではありますが Rust の js_sys::Function で型付けすると .d.ts で Function 型が生成されます。

// Rust

#[wasm_bindgen]
pub fn from_ts_closure_into_js_sys_function(f: js_sys::Function) -> js_sys::Function {
    console::log_1(&format!("value: {:?}", f).into());
    return f;
}

// .d.ts

export function from_ts_closure_into_js_sys_function(f: Function): Function;

• 挙動確認のためのテストコード

とはいえ引数や返り値の型を明示できないのでいまひとつですね。

タプル

タプルが欲しいときには Rust のタプル構造体 (tuple struct) を使います。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
pub struct MyTuple(u8, String, bool);

#[wasm_bindgen]
pub fn from_ts_tuple_into_rust_struct(tuple: MyTuple) -> MyTuple {
    console::log_1(&format!("value: {:?}", tuple).into());
    return tuple;
}

// .d.ts

export type MyTuple = [number, string, boolean];

export function from_ts_tuple_into_rust_struct(tuple: MyTuple): MyTuple;

ユニオン型

ユニオン型が欲しいときには Rust の Enum を使います。

文字列リテラル型のユニオン

特によく使う文字列リテラル型のユニオンを見てみましょう。
"Foo" | "Bar" | "Baz" のような型が欲しいときにはこのようにします。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
pub enum StringLiteralTypeUnion {
    Foo,
    Bar,
    Baz,
}

// .d.ts

export type StringLiteralTypeUnion = "Foo" | "Bar" | "Baz";

• 挙動確認のためのテストコード

小文字はじまりで "foo" | "bar" | "baz" のような型が欲しいときには、#[serde(rename_all = "camelCase")] 属性を付けましょう。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
#[serde(rename_all = "camelCase")]
pub enum StringLiteralTypeUnion {
    Foo,
    Bar,
    Baz,
}

// .d.ts

export type StringLiteralTypeUnion = "foo" | "bar" | "baz";

その他のユニオン

Rust の値付き列挙子は .d.ts では object のユニオンとして表現されます。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
pub enum ObjectUnion {
    N(u32),
    S(String),
    B(bool),
    Tuple(u32, String, bool),
    Named { n: u32, s: String, b: bool },
}

// .d.ts

type ObjectUnion =
    | { N: number }
    | { S: string }
    | { B: boolean }
    | { Tuple: [number, string, boolean] }
    | { Named: { n: number; s: string; b: boolean } };

• 挙動確認のためのテストコード

interface

素朴に interface が欲しいときには Rust の構造体 (named struct) を使います。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
pub struct MyInterface {
    n: u8,
    s: String,
    b: bool,
}

// .d.ts

export interface MyInterface {
    n: number;
    s: string;
    b: boolean;
}

省略可能プロパティ・Nullable プロパティ

interface の中で省略可能プロパティ・Nullable プロパティを表現するには Rust の Option<T> を使います。
Option<T> は T | null に解釈されます。さらに #[tsify(optional)] 属性を付けると T | null | undefined に解釈され、省略可能になります。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
pub struct ObjectHasOptionalProperty {
    pub nullable_property: Option<String>,

    #[tsify(optional)]
    pub optional_property: Option<String>,
}

// .d.ts

export interface ObjectHasOptionalProperty {
    nullable_property: string | null;
    optional_property?: string;
}

Record<K, T> åž‹

interface ではあらかじめ決められたキーしか指定できません。任意のキーをもつ object を扱いたい場合には Record<K, T> 型が欲しくなります。
Rust の HashMap<K, T> を使います。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
pub struct MyRecord(HashMap<String, u32>);

// .d.ts

export type MyRecord = Record<string, number>;

• 挙動確認のためのテストコード

Map<K, T> åž‹

Map<K, T> が欲しいときには Rust の HashMap<K, T> を使います。
ただし tsify-next に対して features = ["js"] を有効にしてコンパイルする必要があります。そのため Map<K, T> と Record<K, T> を共存させることはできません。

# Cargo.toml

[dependencies.tsify-next]
version = "0.5.4"
features = ["js"]

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(into_wasm_abi, from_wasm_abi)]
pub struct MyMap(HashMap<String, u32>);

// .d.ts

export type MyMap = Map<string, number>;

• 挙動確認のためのテストコード

省略可能引数

関数の引数に Option<T> を使うと T | undefined に解釈されます。

// Rust

#[wasm_bindgen]
pub fn from_ts_nullable_string_into_rust_option_string(x: Option<String>, y: String) -> String {
    console::log_1(&format!("value: {:?}", x).into());
    console::log_1(&format!("value: {:?}", y).into());
    x.unwrap_or(y)
}

// .d.ts

export function from_ts_nullable_string_into_rust_option_string(x: string | undefined, y: string): string;

さらにその引数が末尾引数であれば省略可能引数になります。

// Rust

#[wasm_bindgen]
pub fn from_ts_optional_parameter_into_rust_option_string(x: Option<String>) -> Option<String> {
    console::log_1(&format!("value: {:?}", x).into());
    return x;
}

// .d.ts

export function from_ts_optional_parameter_into_rust_option_string(x?: string): string | undefined;

namespace

Rust の Enum から TypeScript の namespace を生成できます。

// Rust

#[derive(Tsify, Serialize, Deserialize, Debug)]
#[tsify(namespace, into_wasm_abi, from_wasm_abi)]
pub enum Color {
    Red,
    Blue,
    Green,
    Rgb(u8, u8, u8),
    Hsv {
        hue: f64,
        saturation: f64,
        value: f64,
    },
}

// .d.ts

declare namespace Color {
    export type Red = "Red";
    export type Blue = "Blue";
    export type Green = "Green";
    export type Rgb = { Rgb: [number, number, number] };
    export type Hsv = { Hsv: { hue: number; saturation: number; value: number } };
}

おわりに

いかがでしょうか。Rust の型と .d.ts を丁寧に対応づけることで Rust と JavaScript の両方から「同じ型」を参照するという体験が得られます。
wasm-bindgen も tsify-next もまだまだ発展途中です。今後いま以上に型の表現力が得られることを期待したいですね。

私からは以上です。

不動点コンビネータで無名再帰を作る流れをおさらい with JavaScript

この記事は はてなエンジニア Advent Calendar 2024 の 2 日目の記事です。
昨日は id:hogashi さんの「querySelectorAllの結果をmapしたいときはArray.fromすると良い」でした。

どうも、趣味で関数型言語をやっている者です。
長らく関数型言語をやってなかったら無名再帰を忘れかけていたので、おさらいがてら不動点コンビネータで無名再帰を作る流れを書き下します。

以下、JavaScript の文法で書かれたコードをもとに説明していきます。

目次

無名再帰とは

まずはモチベーションの確認から。
通常、再帰関数は、

function sum(nums) {
  if (nums.length === 0) {
    return 0;
  } else {
    const num = nums.pop();
    return num + sum(nums);
  }
}

といったように、関数定義の中で自分自身を呼ぶことで再帰処理を記述できます。
この例では、 return num + sum(nums); の部分で自分自身を呼んでいますね。

では、以下のような制約をイメージしてみてください。

• 関数に名前を付けることができない
• 関数定義の中で自分自身を呼ぶことができない

このような制限の中で再帰を書きたくなったらどうすればいいでしょうか？
そんな要望に応えるために人類は 無名再帰 という方法を編み出しました。その名の通り、関数名に依らない再帰処理の方法です。

今回は無名再帰の具体的な作り方を見ていきます。

不動点コンビネータ (Z コンビネータ)

いきなりですが 不動点コンビネータ というやつがあります。
関数を変換する関数 (高階関数) の形をしています。定義はこうです。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));

なんだこれはって感じですね。落ち着いて fix(f) がどのように展開されるか見てみましょう。

fix(f)
→ (f => (g => g(g))(h => f(y => h(h)(y))))(f)
→ (g => g(g))(h => f(y => h(h)(y)))
→ (h => f(y => h(h)(y)))(h => f(y => h(h)(y)))
→ f(y => (h => f(y => h(h)(y)))(h => f(y => h(h)(y)))(y))
    = f(y => fix(f)(y))

fix(f) = f(y => fix(f)(y)) という関係が見えました。とはいえ、まだちょっと何がしたいのか分からない感じの関数ですね。

こんどはもっと具体的に f に特定の関数を代入してみましょう。

f = next => x => next(x) の場合

f = next => x => next(x) のときの fix(f)(0) を考えます。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const f = next => x => next(x);

fix(f)(0)

// fix(f) の定義を展開
→ f(y => fix(f)(y))(0)

// f の定義を展開
→ (next => x => next(x))(y => fix(f)(y))(0)

// 無名関数を評価する
→ (x => (y => fix(f)(y))(x))(0)
→ (y => fix(f)(y))(0)

→ fix(f)(0)

なんと fix(f)(0) を評価すると再び fix(f)(0) が現れました。
関数を実行しようとすると同じ関数の実行に行き着くので、このプログラムは延々と同じ関数を呼び出し続けることになります。

この 関数の呼び出しが延々と繰り返される というやつは、実際にやってみると 処理が無限にループして停止しない という扱いになるでしょう。

ブラウザで fix(f)(0) を実行したときに表示されるエラー

そんな関数が役に立つのか？
大丈夫、もう少し別の例を見ていきましょう。

f = next => x => next(x + 1) の場合

f = next => x => next(x + 1) のときを考えましょう。
さきほどととても似ていますが x + 1 と足し算をしています。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const f = next => x => next(x + 1);

fix(f)(0)
→ f(y => fix(f)(y))(0)
→ (next => x => next(x + 1))(y => fix(f)(y))(0)
→ (x => (y => fix(f)(y))(x + 1))(0)
→ (y => fix(f)(y))(0 + 1)
→ fix(f)(0 + 1)
→ fix(f)(1)

fix(f)(0) が評価されて fix(f)(1) になりました。
再度 fix(f)(1) を評価すると fix(f)(2) になります。さらに繰り返せば fix(f)(3) になります。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const f = next => x => next(x + 1);

fix(f)(0)
→ ...
→ fix(f)(1)
→ ...
→ fix(f)(1 + 1)
→ fix(f)(2)
→ ...
→ fix(f)(2 + 1)
→ fix(f)(3)
→ ...

同じ関数を呼び出し続けているという点では先ほどの同じで。この例でも関数の実行は停止せずにエラーになります。
ただ今度は引数の部分で計算が行われているので、何か 再帰処理されている感じ が持てますね。

f = next => x => x > 1 ? x : next(x + 1) の場合

もう一歩踏み込んで条件分岐を加えてみましょう。
f = next => x => x > 1 ? x : next(x + 1) について考えます。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const f = next => x => x > 1 ? x : next(x + 1);

fix(f)(0)
→ f(y => fix(f)(y))(0)
→ (next => x => x > 1 ? x : next(x + 1))(y => fix(f)(y))(0)
→ (x => x > 1 ? x : (y => fix(f)(y))(x + 1))(0)
→ 0 > 1 ? 0 : (y => fix(f)(y))(0 + 1)
→ (y => fix(f)(y))(0 + 1)
→ fix(f)(0 + 1)
→ fix(f)(1)
→ ...
→ fix(f)(2)
→ ...
→ (x => x > 1 ? x : (y => fix(f)(y))(x + 1))(2)
→ 2 > 1 ? 2 : (y => fix(f)(y))(2 + 1)
→ 2

ついに無限の関数呼び出しを回避できました。
ブラウザで実行してみても同じ結果が得られます。

エラーは無い

f がどんな式だったかもう一度見てみましょう。

const f = next => x => x > 1 ? x : next(x + 1);

種明かしすると next(~) の部分が再帰呼び出しに相当しています。
条件分岐を追加して next(~) ã‚’ 呼び出さない ことで再帰を打ち切ることができるのです。

この挙動を手続的に書いてみるとこんな感じになるはずです。

let x = 0;
while (true) {
  if (x > 2) {
    return x;
  } else {
    x += 1;
  }
}

どうでしょう？条件分岐を組み込んだ式 f を渡すことで 何か実用的な式を組み立てられそうな気がしてきた と思いませんか？

実用的な計算例: 階乗計算

いよいよ不動点コンビネータを使った実用的な例を見ていきましょう。
0以上の自然数 n の階乗 fact(n)を計算してみます。

まず階乗関数 fact を定義するための補助関数 _fact を次のように定義します。

const _fact = next => n => n === 1 ? 1 : n * next(n - 1);

これを fix に与えて展開してみましょう。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const _fact = next => n => n === 1 ? 1 : n * next(n - 1);

fix(_fact)
→ (f(y => fix(f)(y)))(_fact)
→ _fact(y =>  fix(_fact)(y))
→ (next => n => n === 1 ? 1 : n * next(n - 1))(y =>  fix(_fact)(y))
→ n => n === 1 ? 1 : n * (y =>  fix(_fact)(y))(n - 1)

はい！ 三項演算子の else 節に注目してください fix(_fact)(y) という形で再帰的構造が見えていますね。

n にも具体的な値を入れてみましょう。 fix(_fact)(3) を展開します。

fix(_fact)(3)

// fix の定義に従い fix(_fact) を展開
→ _fact(y => fix(_fact)(y))(3)

// _fact の定義に従い式を展開
→ (next => n => n === 1 ? 1 : n * next(n - 1))(y => fix(_fact)(y))(3)
→ (n => n === 1 ? 1 : n * (y => fix(_fact)(y))(n - 1))(3)
→ 3 === 1 ? 1 : 3 * (y => fix(_fact)(y))(3 - 1)

// 三項演算子を評価
→ 3 * (y => fix(_fact)(y))(3 - 1)

// 3 - 1 を評価
→ 3 * (y => fix(_fact)(y))(2)
→ 3 * fix(_fact)(2)

// 以下、繰り返し
→ 3 * _fact(y => fix(_fact)(y))(2)
→ 3 * (next => n => n === 1 ? 1 : n * next(n - 1))(y => fix(_fact)(y))(2)
→ 3 * (n => n === 1 ? 1 : n * (y => fix(_fact)(y))(n - 1))(2)
→ 3 * (2 === 1 ? 1 : 2 * (y => fix(_fact)(y))(2 - 1))
→ 3 * 2 * (y => fix(_fact)(y))(2 - 1)
→ 3 * 2 * (y => fix(_fact)(y))(1)
→ 3 * 2 * fix(_fact)(1)

→ 3 * 2 * _fact(y => fix(_fact)(y))(1)
→ 3 * 2 * (next => n => n === 1 ? 1 : n * next(n - 1))(y => fix(_fact)(y))(1)
→ 3 * 2 * (n => n === 1 ? 1 : n * (y => fix(_fact)(y))(n - 1))(1)
→ 3 * 2 * (1 === 1 ? 1 : 1 * (y => fix(_fact)(y))(1 - 1))
→ 3 * 2 * 1

→ 6

ふぅ、お疲れさまでした。fix(_fact)(3) が 3 * 2 * 1 に展開される様子が見えて、まさに階乗計算している感じですね。

さてfix(_fact)(n) で n の階乗が計算できることが分かったので、

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
const _fact = next => n => n === 1 ? 1 : n * next(n - 1);
const fact = fix(_fact);

として階乗関数 fact() を定義することができました。

実際に計算できている様子

 

何が起こっている？

あらためて _fact と fact の定義を見てみましょう。

const _fact = next => n => n === 1 ? 1 : n * next(n - 1);
const fact = fix(_fact);

_fact の定義にも fact の定義にも自分自身を呼び出す記述はありませんから、今回のテーマ通り 自分自身を呼び出すことなく再帰処理を実現できた ということになります。
さらに _fact の定義をよく見ていると仮引数の next をまるで再帰呼び出しのように使っていることが分かります。

形式的な知識としてはこうです。

• fix に関数 g を与えることで関数 f が得られる
• f は通常の1引数関数として振る舞う
• g の第一仮引数 next の呼び出しは、f の再帰呼び出しのように振る舞う

掴めてきましたか？実際に紙に手書きで運算してみるとより理解が深まるかも知れません。

2引数関数への展開

先ほどの例で見た fact() はただ一つの引数 n を取る1引数関数でした。
次に2引数関数を無名再帰で書く例を見てみましょう。

例に取り上げるのは自然数 m, n の最大公約数を求める関数 gcd(m, n) です。 ユークリッドの互除法 を使って計算します。

まずは名前再帰版です。

const gcd = (m, n) => n === 0 ? m : gcd(n, m % n);

gcd(1071, 1029);
// => 21

これを無名再帰で書きたいところですが困ったことがあります。さきほど紹介した不動点コンビネータ fix は1引数関数を作るときにしか使えないのです。

上手く機能していない

問題の解決策を3つ紹介します。

解決策1: 2引数版の不動点コンビネータを使う

const fix2 = f => (g => g(g))(h => f((x, y) => h(h)(x, y)));

この不動点コンビネータ fix2 は先ほどまで見てきた fix の2引数版です。
使い方は fix と変わりません。

const fix2 = f => (g => g(g))(h => f((x, y) => h(h)(x, y)));
const _gcd = next => (m, n) => n === 0 ? m : next(n, m % n);
const gcd = fix2(_gcd);

gcd(1071, 1029);
// => 21

fix2 を使えば正しく機能する

もちろん3引数関数を書きたくなったら3引数版の fix3 が、4引数関数を書きたくなったら4引数版の fix4 が必要になります。少し面倒ですね。

// 3引数版
const fix3 = f => (g => g(g))(h => f((x, y, z) => h(h)(x, y, z)));

// 4引数版
const fix4 = f => (g => g(g))(h => f((x, y, z, w) => h(h)(x, y, z, w)));

解決策2: カリー化🍛する

カリー化 という方法を使うと多引数関数と同等のものを1引数関数だけで書くことが可能になります。
例として Math.pow(x, y) ã‚’1引数関数で表現すると、

const pow = x => y => Math.pow(x, y);

Math.pow(2, 4);
// => 16

pow(2)(4); // 呼び出し方が変わるので注意
// => 16

pow は1引数関数です。
ただし pow(2) の返り値もまた1引数関数になっています。引数を一つずつ渡して 2回呼び出す ことで2引数での呼び出しと同等の結果が得られます。

カリー化してしまえば全ての関数は1引数関数になるので、先ほどの gcd ã‚’1引数版の fix を使って定義できます。

const fix = f => (g => g(g))(h => f(x => h(h)(x)));
const _gcd = next => m => n => n === 0 ? m : next(n)(m % n);
const gcd = fix(_gcd);

gcd(1071)(1029); // カリー化によって呼び出し方が変わるので注意
// => 21

カリー化すれば複数の引数を扱える

解決策3: 1引数関数にタプルを渡すことで対応する

「2引数を受け取る関数」は「2要素のタプルを1つ受け取る関数」と同等です。
JavaScript にはタプルが無いので配列で代用すると。

const pow = ([x, y]) => Math.pow(x, y);

Math.pow(2, 4);
// => 16

pow([2, 4]); // 呼び出し方が変わるので注意
// => 16

Math.pow(x, y) と同等の計算をする1引数関数 pow([x, y]) が定義できました。

1引数版の fix を使って、タプル渡しの gcd 関数を定義してみましょう。

const fix = f => (g => g(g))(h => f(x => h(h)(x)));
const _gcd = next => ([m, n]) => n === 0 ? m : next([n, m % n]);
const gcd = fix(_gcd);

gcd([1071, 1029]); // タプル渡しで呼び出す
// => 21

ECMAScript 2015 の分割代入によってタプル渡しが書きやすくなった

どの方法でも2引数関数の無名再帰に上手く対応できていますね。

型はどうなってる？

ここまで見てきた不動点コンビネータ fix やそれを使って定義した無名再帰関数に適切に型付けできるのか気になりますよね？
なんと TypeScript なら fix に適切に型をつけることが可能です。

このようになります。

function fix<S, T>(f: (_: (_: S) => T) => (_: S) => T) {
  type U = (_: U) => (_: S) => T;
  return (g => g(g))((h: U) => f((y: S) => h(h)(y)));
}

型付きの fix を使って階乗関数 fact を書いた例を TypeScript Playground に用意しました。
_fact に最低限の型注釈をつけるだけで fact = fix(_fact) の型が正しく推論されています。

• TypeScript Playground

正しく fact: (_: number) => number と推論されている

まとめ

不動点コンビネータを使うと決まったパターンで無名再帰が実現できることを見てきました。
また多引数関数に応用することや TypeScript による型付けについても知ることができました。

ここで紹介した不動点コンビネータや無名再帰は計算機科学の始まりの頃から研究されてきたテーマです。コンビネータ理論を確立してくれた先人に感謝します。

私からは以上です。

余談

この記事は下記の記事とほぼ同じ内容を JavaScript で焼き直したものです。
下記の記事ではサンプルコードを Haskell で書いていましたが、「Haskell でサンプルコード書いて誰が読めんねん！」と思ったので JavaScript で書き直しました。

blog.mudatobunka.org

余談2

不動点コンビネータの型付けについては下記の記事を大いに参考にさせていただきました。

qiita.com

Array.prototype.includes と Set.prototype.has の速さ比べ

配列がとある要素を含むかどうか調べるには Array.prototype.includes を使います。

const arr = [1, 2, 4, 8, 16];

arr.includes(4); // => true
arr.includes(7); // => false

ところで、JavaScript には Set というデータ型があり、同じように Set.prototype.has を使って要素を含んでいるか検索できます。

const set = new Set([1, 2, 4, 8, 16]);

set.has(4); // => true
set.has(7); // => false

mdn を見ると要素数が同じなら Array.prototype.includes より Set.prototype.has のほうが速いと 書いてあります 。

has メソッドは、値が Set 内にあるかどうかをチェックします。
これは、以前に Set に追加された要素のほとんどを確認するよりも平均すると高速なアプローチを使用します。
特に、 Array オブジェクトの length が Set オブジェクトの size と等しい場合、平均して Array.prototype.includes メソッドより速くなります。

本当でしょうか？実際にベンチマーク計測してみました。

3行まとめ

• Array.prototype.includes より Set.prototype.has のほうが速い
• ただし Set を初期化するのに時間がかかる
• Array → Set の変換は遅い, Set → Array の変換は速い

Deno.bench で計測してみる

計測には Deno.bench を使います。
まず計測したい処理をコードに起こします。

import { assert } from "jsr:@std/assert";
import { crypto } from "jsr:@std/crypto/crypto";

// 1,000,000 要素の配列を作る
// 要素は何でもいいので uuid を詰めておく
const arr = Array.from({ length: 1_000_000 }, () => crypto.randomUUID());

// 検索対象を用意する
const found = arr[Math.floor(Math.random() * arr.length)]; // これは見つかる
const notfound = crypto.randomUUID(); // これは見つからない

// ここからが計測
Deno.bench({
  name: 'Array.prototype.includes',
  fn() {
    assert(arr.includes(found));
    assert(!arr.includes(notfound));
  },
});

そしてコマンド deno bench example.js でベンチマークを実行します。

$ deno bench example.js 
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/example.js

benchmark                  time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------------------- ----------------------------- --------------------- --------------------------
Array.prototype.includes            3.9 ms         258.6 (  3.7 ms …   4.3 ms)   3.9 ms   4.3 ms   4.3 ms

するとこのように結果が表示されます。

では具体的に比較してみましょう。

Array.prototype.includes vs in 演算子 vs Set.prototype.has

Array.prototype.includes と in 演算子 と Set.prototype.has の実行にかかる時間を比べます。
計測に使ったコードは ここ にあります。
要素数1,000,000件の Array と Object と Set を作って比較しています。

$ deno bench array_vs_object_vs_set.js 
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/array_vs_object_vs_set.js

benchmark                  time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------------------- ----------------------------- --------------------- --------------------------
Array.prototype.includes            3.1 ms         317.5 (  2.9 ms …   3.7 ms)   3.4 ms   3.6 ms   3.7 ms
in operator                        15.9 ns    62,780,000 ( 15.7 ns …  34.0 ns)  15.8 ns  18.5 ns  19.2 ns
Set.prototype.has                  13.1 ns    76,210,000 ( 13.0 ns …  15.8 ns)  13.1 ns  14.1 ns  14.6 ns

単位を揃えてみると、

	time/iter (avg)	iter/s
Array.prototype.includes	3.1 ms	317.5
in operator	0.0000159 ms	62,780,000.0
Set.prototype.has	0.0000131 ms	76,210,000.0

というわけで圧倒的に Set.prototype.has が速いようです。
Object から in 演算子で探すのもかなり速いですね。

Object と Set の初期化を加味した計測

先ほどの計測では Array, Object, Set を作る時間は計測せず、検索にかかる時間のみを対象にしていました。

では任意の Array が与えられたとき、検索のために Object や Set を初期化するところからやらないといけないようなシチュエーションではどうでしょうか。
そのシチュエーションを想定するなら Object や Set の初期化を計測に含めるべきですね。

その場合のコードが これ です。
実行してみます。

$ deno bench array_vs_object_vs_set_2.js 
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/array_vs_object_vs_set_2.js

benchmark                  time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------------------- ----------------------------- --------------------- --------------------------
Array.prototype.includes            4.0 ms         247.4 (  4.0 ms …   4.2 ms)   4.0 ms   4.2 ms   4.2 ms
in operator                       109.0 ms           9.2 ( 96.1 ms … 153.1 ms) 110.4 ms 153.1 ms 153.1 ms
Set.prototype.has                  84.8 ms          11.8 ( 72.4 ms … 146.7 ms)  76.8 ms 146.7 ms 146.7 ms

はい、初期化の時間を加味すると in 演算子も Set.prototype.has も遅いという結果になりました。

先ほどの結果と合わせてまとめると、

	検索	初期化 + 検索
Array.prototype.includes	3.1 ms	-
in operator	0.0000159 ms	109.0 ms
Set.prototype.has	0.0000131 ms	84.8 ms

このように。

数回だけ検索するだけであれば、Object ã‚„ Set を作らず愚直に Array.prototype.includes を使ったほうがトータルで速くなりそうです。
数十回以上の検索を繰り返すのであれば初期化のコストを払ってでも Object や Set を作ったほうが有利になります。

Object と Set の初期化のコストを測ってみる

せっかくなので Array から Object や Set を作るのにかかる時間を測ってみます。
要素数が10件~1,000,000件の場合で見てみましょう。

計測に使ったコードは これ です。

$ deno bench array_to.js
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/array_to.js

benchmark                             time/iter (avg)        iter/s      (min … max)           p75      p99     p995
------------------------------------- ----------------------------- --------------------- --------------------------
Array -> Set    > length:        10          159.9 ns     6,256,000 (150.3 ns … 195.0 ns) 163.7 ns 190.9 ns 194.4 ns
Array -> Set    > length:       100            2.2 µs       453,800 (  2.1 µs …   3.1 µs)   2.2 µs   3.1 µs   3.1 µs
Array -> Set    > length:     1,000           26.0 µs        38,510 ( 24.5 µs … 160.3 µs)  25.6 µs  33.4 µs  38.0 µs
Array -> Set    > length:    10,000          369.5 µs         2,706 (339.4 µs … 916.9 µs) 363.2 µs 722.2 µs 789.4 µs
Array -> Set    > length:   100,000            3.8 ms         262.1 (  3.6 ms …   4.5 ms)   4.1 ms   4.4 ms   4.5 ms
Array -> Set    > length: 1,000,000           94.0 ms          10.6 ( 78.9 ms … 118.7 ms)  97.2 ms 118.7 ms 118.7 ms
Array -> Object > length:        10          178.1 ns     5,615,000 (163.7 ns … 586.9 ns) 176.4 ns 321.6 ns 341.2 ns
Array -> Object > length:       100            1.9 µs       521,300 (  1.9 µs …   2.1 µs)   1.9 µs   2.1 µs   2.1 µs
Array -> Object > length:     1,000           21.6 µs        46,290 ( 18.4 µs … 150.1 µs)  22.7 µs  30.5 µs  91.3 µs
Array -> Object > length:    10,000          335.2 µs         2,983 (287.7 µs … 976.0 µs) 320.2 µs 730.0 µs 797.1 µs
Array -> Object > length:   100,000            6.4 ms         155.5 (  5.7 ms …   7.3 ms)   6.7 ms   7.3 ms   7.3 ms
Array -> Object > length: 1,000,000          107.9 ms           9.3 ( 96.2 ms … 171.6 ms) 102.2 ms 171.6 ms 171.6 ms

要素数	Array -> Object	Array -> Set
10	0.0001781 ms	0.0001599 ms
100	0.0019 ms	0.0022 ms
1,000	0.0216 ms	0.0260 ms
10,000	0.3352 ms	0.3695 ms
100,000	6.4 ms	3.8 ms
1,000,000	107.9 ms	94.0 ms

Object と Set で大きな差があるわけではなく、要素が増えることによる影響が大きいように見えます。

Object や Set から Array を得るときのコスト

逆に Object や Set を持っている状態から Array がほしいときにはどれくらいのコストがかかるのでしょうか。
要素数1,000,000件の Object と Set に対して、Object.key(obj), Array.from(set.keys()) を比べてみます。

計測に使ったコードは これ です。

$ deno bench array_from.js 
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/array_from.js

benchmark            time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------------- ----------------------------- --------------------- --------------------------
Object.keys                 131.1 ms           7.6 (122.1 ms … 160.5 ms) 135.8 ms 160.5 ms 160.5 ms
Set.prototype.keys            1.5 ms         657.1 (  1.4 ms …   2.2 ms)   1.5 ms   2.1 ms   2.2 ms

要素数	Object -> Array	Set -> Array
1,000,000	131.1 ms	1.5 ms

意外にも Set から Array を作る方が Object から作るのに比べて80倍ほど速いという結果になりました。

まとめ

Set から要素を検索するのは確かに速い、ただし Set を作るのにかなりの時間がかかる。
少し残念な結果でした。

私からは以上です。