新春最適化⼿法解説:
Tail Modulo Cons
@第五回関数型プログラミング（仮）の会
びしょ〜じょIAM…
こんにちは､びしょ〜じょです🏢株式会社カンム
Golangerしてます🪁すきなもの代数的効果､継続､処理系

👤Nymphium
Nymphium突然ですが

突然ですが関数型プログラミングといえば…?

突然ですが関数型プログラミングといえば…?

再帰でしょ本⽇の内容本⽇の内容OCaml(≧ 4.14)で

本⽇の内容OCaml(≧ 4.14)で再帰関数に

本⽇の内容OCaml(≧ 4.14)で再帰関数に[@tail_mod_cons]と書くと

本⽇の内容OCaml(≧ 4.14)で再帰関数に[@tail_mod_cons]と書くと速くなる

場合がある本⽇の内容OCaml(≧ 4.14)で再帰関数に[@tail_mod_cons]と書くと速くなる

場合がある再帰最も基本的な構造
let rec map f = function| [] -> []| x :: xs -> f x :: map f xs

再帰
最も基本的な構造
let rec map f = function| [] -> []| x :: xs -> f x :: map f xs
型､関数…

定義に⾃⾝を参照

末尾再帰
関数の末尾位置で⾃⾝を再帰呼び出し
let rec fold_left f x = function| [] -> x| x' :: xs' -> fold_left f (f x x') xs'

末尾再帰
関数の末尾位置で⾃⾝を再帰呼び出し
let rec fold_left f x = function 末尾位置
| [] -> x| x' :: xs' -> fold_left f (f x x') xs'

末尾再帰
関数の末尾位置で⾃⾝を再帰呼び出し
let rec fold_left f x = function 末尾位置
| [] -> x| x' :: xs' -> fold_left f (f x x') xs'
末尾位置+再帰で再帰呼び出し

末尾再帰

末尾呼び出し最適化
末尾再帰にすると末尾呼び出し最適化ができる● 再帰呼び出し(call)をjumpに置き換えられ● コールスタックの操作が不要になりperformant● そしてスタックオーバーフローもしない!

末尾呼び出し最適化
末尾再帰にすると末尾呼び出し最適化ができる● 再帰呼び出し(call)をjumpに置き換えられ● コールスタックの操作が不要になりperformant● そしてスタックオーバーフローもしない!

ところでmapって…末尾再帰じゃない
let rec map f = function| [] -> []| x :: xs -> f x :: map f xs

mapって…末尾再帰じゃない
let rec map f = function| [] -> []| x :: xs -> f x :: map f xs
A正規化すると…
let x' = f x inlet xs'' = map f xs' inx' :: xs''

後続処理
あっ が
無理 てや…

mapを救いたい
どうする…?

mapを救いたい
どうする…?
● map_revしてrev○ performantでないケース● 継続渡し⽅式(CPS)○ ⼿で書くのですか…?

mapを救いたい
どうする…?
● map_revしてrev○ performantでないケース● 継続渡し⽅式(CPS)○ ⼿で書くのですか…?

● Tail-Recursion
Modulo Cons

Tail-Recursion Modulo Cons
Tail-Recursion Modulo Cons とは…

Tail-Recursion Modulo Cons
Tail-Recursion Modulo Cons とは…

末尾再帰

Tail-Recursion Modulo Cons
Tail-Recursion Modulo Cons とは…

末尾再帰+Destination Passing Style(DPS)Tail-Recursion Modulo Conslet rec map f = function| [] -> []| x :: xs -> f x :: map f xs

Tail-Recursion Modulo Cons?!

let rec map f = function| [] -> []| x :: xs -> f x :: map f xs

let rec map f = function and map_dps d f = function| [] -> []| [] -> set_field d 1 []| x :: xs ->| x :: xs ->let y = f x inlet y = f x inlet d = y :: Hole in
let d' = y :: Hole in
map_dps d f xs;
set_field d 1 d';dmap_dps d' fTail-Recursion Modulo Conslet rec map f = function and map_dps d f = function| [] -> []| [] -> set_field d 1 []| x :: xs ->| x :: xs ->let y = f x inlet y = f x inlet d = y :: Hole in
let d' = y :: Hole in
map_dps d f xs;
set_field d 1 d';dmap_dps d' fTail-Recursion Modulo Conslet rec map f = function and map_dps d f = function| [] -> []| [] -> set_field d 1 []| x :: xs -> プレースホルダー| x :: xs ->let y = f x inlet y = f x inlet d = y :: Hole in
let d' = y :: Hole in
map_dps d f xs;
set_field d 1 d';d
map_dps d' fTail-Recursion Modulo Conslet rec map f = function and map_dps d f = function| [] -> []| [] -> set_field d 1 []| x :: xs -> プレースホルダー| x :: xs ->let y = f x inlet y = f x inlet d = y :: Hole in
let d' = y :: Hole in
map_dps d f xs;
set_field d 1 d';dmap_dps d' f

データの宛先を渡す(destination passing)Tail-Recursion Modulo Conslet rec map f = function and map_dps d f = function| [] -> []| [] -> set_field d 1 []| x :: xs -> プレースホルダー| x :: xs ->let y = f x inlet y = f x inlet d = y :: Hole in
let d' = y :: Hole in
map_dps d f xs;
set_field d 1 d';dmap_dps d' f

データの宛先を渡す(destination passing)

値を挿⼊
値を挿入

Tail-Recursion Modulo Cons⾃⾝は再帰してない
let rec map f = function and map_dps d f = function| [] -> []| [] -> set_field d 1 []| x :: xs -> プレースホルダー| x :: xs ->let y = f x inlet y = f x inlet d = y :: Hole in
let d' = y :: Hole in
map_dps d f xs;
set_field d 1 d';dmap_dps d' f

データの宛先を渡す(destination passing)

値を挿⼊
値を挿入

Tail-Recursion Modulo Cons⾃⾝は再帰してない

末尾再帰してる!!

let rec map f = function and map_dps d f = function| [] -> []| [] -> set_field d 1 []| x :: xs -> プレースホルダー| x :: xs ->let y = f x inlet y = f x inlet d = y :: Hole in
let d' = y :: Hole in
map_dps d f xs;
set_field d 1 d';d
map_dps d' f

データの宛先を渡す(destination passing)

値を挿⼊
値を挿入

[@tail_mod_cons]
Tail recursion modulo consは古典的な⼿法

[@tail_mod_cons]
Tail recursion modulo consは古典的な⼿法● Lisp(1970〜)､Prolog､etc.
● しかし⼿書き… 破壊的代⼊危ない ☠

[@tail_mod_cons]
Tail recursion modulo consは古典的な⼿法● Lisp(1970〜)､Prolog､etc.
● しかし⼿書き… 破壊的代⼊危ない ☠
↓定式化することでプログラム変換としてコンパイラに導⼊😁

以降､式はこの論文より引用

[@tail_mod_cons]
let rec map f = function| [] -> []| x :: xs -> f x :: map f xs

[@tail_mod_cons]let[@tail_mod_cons]
let rec map f = function
rec| []map→ f[]= function アノテーション
|| []
-> xs
[] → f x :: mapつけるだけでx ::f
xs| x :: xs -> f x :: map f xs

[@tail_mod_cons]let[@tail_mod_cons]
let rec map f = function
rec| []map→ f[]= function アノテーション
|| []
-> xs
[] → f x :: mapつけるだけでx ::f
xs| x :: xs -> f x :: map f xs

プログラム変換!!
(コンパイラの中間⾔語)
let rec map f = function| [] -> []| x :: xs ->let y = f x inlet d = y :: Hole in
map_dps d f xs;
dand map_dps d f = function| [] -> set_field d 1 []| x :: xs ->let y = f x inlet d' = y :: Hole in
set_field d 1 d';
map_dps d' fTail Modulo Cons Context
⼩さな対象⾔語��Tail Modulo Cons Context

��

⼩さな対象⾔語

関数定義はトップレベルのみ● let式● 関数適⽤● 代数的データ型● パターンマッチング● 代⼊Tail Modulo Cons Context

Tail Modulo Cons Context

コンストラクタに潜っていく("modulo")Tail Modulo Cons Context

コンストラクタに潜っていく("modulo")

例:f x :: map f xs
● U = f x :: ▢● ▢ = map f xs

TMC変換TMC変換え〜､つまり?
どういうことですか?
3⾏で頼む

TMC変換TMC変換1. 対象の関数からDPS versionの関数を作る
map f xs

map_dps d idx f xs

ここで､
set_field d idx (map f xs) = map_dps d idx f xs

TMC変換1. 対象の関数からDPS versionの関数を作る
map f xs

map_dps d idx f xs

ここで､
set_field d idx (map f xs) = map_dps d idx f xs

2. 2つの変換●●

でmapの再帰をmap_dpsの呼び出しにでmapに基づいたmap_dpsの⽣成

TMC変換let rec map f = function| [] -> []| x :: xs ->f x :: map f xs

TMC変換dps版を作成
bodyをコピー
let rec map f = function| [] -> []| x :: xs ->f x :: map f xs

and map_dps d i f = function| [] -> []| x :: xs ->f x :: map f xs

TMC変換dps版を作成
bodyをコピー
let rec map f = function
and map_dps d i f = function| [] -> []| [] -> []| x :: xs ->| x :: xs ->fx ::xs Hole inf x :: map f xs
letd =map
f xf ::
map_dps d 1 f;d

コンストラクタに潜る
f x :: map f xs
dps版を呼ぶTMC変換
変換の終端
フィールドにセットdps版を作成
bodyをコピー

let rec map f = function
and map_dps d i f = function-> []set_field d i []| [] -> []| [] →| x :: xs ->| x :: xs ->fx ::xs Hole inf x :: map f xs
let
d =mapf xf ::
map_dps d 1 f;d

コンストラクタに潜る
f x :: map f xs
dps版を呼ぶTMC変換
変換の終端
フィールドにセット

dps版を作成
bodyをコピー

let rec map f = function
and map_dps d i f = function-> []set_field d i []| [] -> []| [] →| x :: xs ->| x :: xs ->→d'map= ffxxs:: Hole infx ::xs Hole in
flet
x ::
letd =map
f xf ::
set_field d i d';
map_dps d 1 f;d
map_dps d' 1 f

コンストラクタに潜る
f x :: map f xs
dps版を呼ぶ

コンストラクタに潜る
1つ前のフィールドにセット
末尾再帰

misc
● OCamlの標準ライブラリでも利⽤が進んでいる○ containers､baseなどでも普及● 最近の関連研究オモロイ(紹介論⽂は2021)○ Tail Recursion Modulo Context■ consの⼀般化､諸問題にtackle○ Destination-passing style programming: a Haskell
implementation■ DPS+線形型､結局⼿で書きたいパターンも安全に

まとめ● Tail recursion modulo consという技法○ ⾮末尾再帰→末尾再帰○ ⼿で書くと⾯倒だし破壊的代⼊がある● OCamlなら[@tail_mod_cons]でOK!
● つまりOCamlを書こう!!!!!!
○ 公式も読むと良いですよ■ https://v2.ocaml.org/manual/tail_mod_cons.html

Reference● 📝Bour, Frédéric, Basile Clément, and Gabriel
Scherer. "Tail modulo cons." arXiv preprint
arXiv:2102.09823 (2021).
● 📝Bagrel, Thomas. "Destination-passing styleprogramming: a Haskell implementation." arXiv
preprint arXiv:2312.11257 (2023).
● 📝Leijen, Daan, and Anton Lorenzen. "TailRecursion Modulo Context: An EquationalApproach." Proceedings of the ACM on
Programming Languages 7, no. POPL (2023):
1152-1181.

TMC変換equationでdpsの呼び出しに変換

equationで再帰呼び出しに変換末尾呼び出し最適化
Q. なぜ末尾再帰はperformantなんですか?
A. 末尾呼び出し最適化ができるからQ. 末尾呼び出し最適化とはなんですか?
A. 再帰呼び出し(call)をjumpにする(続)末尾呼び出し最適化
再帰呼び出し(call)をjumpにする
fold_left:

fold_left:......

......

call fold_left
後続の処理がない!

jmp fold_left

エントリの先頭までjmpすればよくないですか?