このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

ブロックラムダ式

抽象的なセッティングで議論していても、最後は結局“具体的な計算”に頼ることはよくあります。具体的な計算には(インフォーマルな)ラムダ式/ラムダ計算が使われることが多いでしょう。具体的な計算をできるだけ楽にするために、ラムダ式の記法を工夫してみます。

内容:

簡単な事例

R2 の標準的ユークリッドノルムを norm と書くことにすると、次のようになります。


norm(x, y) := \sqrt{x^2 + y^2}

二乗する関数を sq 、足し算を sum 、平方根関数を sqrt とすると、norm は次の可換図式で定義されます。

\require{AMScd}%
\newcommand{\R}{ {\bf R} }%
\begin{CD}
\R^2 @>{sq\otimes sq}>> \R^2 \\
@V{norm}VV               @VV{sum}V \\
\R   @<{sqrt}<<         \R
\end{CD}

 {sq\otimes sq} sq\times sq でもいいのですが、数の掛け算との混同を避けて記号'\otimes'を使っています。

  •  (sq\otimes sq)( (x, y) ) = (sq(x), sq(y))

上図の可換性は、次の等式と同じです。

  •  norm = sq\otimes sq \,;\, sum \,;\, sqrt

セミコロンは、関数の図式順結合記号です。

等式の左右をラムダ式で表現しようと思いますが、ラムダ式で使うラムダ変数〈引数変数 | 束縛変数〉を図式に記入しておきます。


\begin{CD}
(x, y)\in \R^2 @>{sq\otimes sq}>> \R^2 \ni (p, q)\\
@V{norm}VV               @VV{sum}V \\
r\in \R   @<{sqrt}<<         \R \ni s
\end{CD}

記号 '\in,\, \ni' は、集合への所属を主張しているというよりは、変数の型宣言です。ペア(長さが2のタプル)を引数に取る関数は、多変数関数ではなくてタプル1変数関数と考えます(「タプル1変数関数と多変数関数」参照)。

可換図式に対応する等式は:


\lambda\, (x, y)\in \R^2.(\,norm( (x, y) ) \,) \\
=\\
\lambda\, (x, y)\in \R^2.(\, (sq\otimes sq)( (x, y)) \,) \,;\, \\
\lambda\, (p, q)\in \R^2.(\, sum( (p, q) ) \,) \,;\, \\
\lambda\, s \in \R.(\, sqrt(s) \,)

簡単なことをわざと複雑に書いている印象があるでしょうが(実際そうです)、事例として使うためにこんなことしてます。この等式の右辺のように、ラムダ式(の関数抽象)で書かれた関数が結合記号で繋がった形が今日の話題です。

一般に、結合記号で繋がれたラムダ式(関数抽象)を簡約化するルールは次のようです; \mathscr{E}, \mathscr{F} がなんらかの式だとして、

\newcommand{\LA}{\big[\!\!\big(\,}\newcommand{\RA}{\,\big)\!\!\big]}%
\lambda\, x\in X.\mathscr{E} \,;\, \lambda\,y\in Y.\mathscr{F} \\
=> \\
\lambda\, x\in X.(\, \mathscr{F}\LA y := \mathscr{E} \RA \,)

ここで、=> は式の変形方向付きのイコール、凹レンズ括弧(\LA \cdots \RA)は、直前の式に対する代入操作を表します。

この一般的なルールに基づいて、ノルムの例を計算してみます。


\lambda\, (x, y)\in \R^2.(\, (sq\otimes sq)( (x, y)) \,) \,;\, \\
\lambda\, (p, q)\in \R^2.(\, sum( (p, q) ) \,) \,;\, \\
\lambda\, s \in \R.(\, sqrt(s) \,) \\
=> \\
\lambda\, (x, y)\in \R^2.(\, (sq\otimes sq)( (x, y)) \,) \,;\, \\
\lambda\, (p, q)\in \R^2.(\, sqrt(s)\LA s := sum( (p, q) ) \RA \,) \\
=> \\
\lambda\, (x, y)\in \R^2.(\, (sqrt(s)\LA s := sum( (p, q) ) \RA )\LA (p, q) := (sq\otimes sq)( (x, y)) \RA \,) \\

式も、その変形の過程も、あまり見やすくないですねぇ。

ブロックラムダ式

関数の結合や代入を簡潔に表すために、ブロックラムダ式を導入します。まず、\lambda\, x\in X.\mathscr{E} を次の形で書くことにします。

%
\newcommand{\LET}{\mbox{let }}%
\newcommand{\IND}{\:\:\:\:}%
\newcommand{\FOR}{\mbox{for }}
\newcommand{\RET}{\mbox{return }}
\newcommand{\DEF}{\mbox{define }}
\newcommand{\IF}{\mbox{if }}
\newcommand{\THEN}{\mbox{ then }}
\newcommand{\ELSE}{\mbox{ else }}
\{ \\
\IND\FOR x\in X\\
\IND\RET \mathscr{E} \\
\}

プログラムコードに近い雰囲気になりました。1行目は、繰り返しのfor文ではないので、区別したいときは所与for文と呼ぶことにします。"for given x" の意味です*1。2行目はreturn文で、常識的に解釈してください*2

for, return 以外に、代入を示すlet文が書けるとします。例えば、前節最後の例だと:


\{ \\
\IND\FOR (x, y)\in \R^2 \\
\IND\LET (p, q) := (sq\otimes sq)( (x, y)) \\
\IND\LET s := sum( (p, q) ) \\
\IND\RET sqrt(s) \\
\}

随分と見やすいでしょう。関数結合の連続、代入の連続が、上から下に向かって読む順次実行の形で表現されます。手続き的な表現ですが、セマンティクスはラムダ計算のセマンティクス(表示的意味論)がそのまま使えます。

この書き方の式をブロックラムダ式〈block lambda {expression | term}〉と呼ぶことにします。ブロックラムダ式の変形(代入操作)は次のように行います。


\{ \\
\IND\FOR (x, y)\in \R^2 \\
\IND\LET (p, q) := (sq\otimes sq)( (x, y)) \\
\IND\LET s := sum( (p, q) ) \\
\IND\RET sqrt(s) \\
\}\\
=>\\
\{ \\
\IND\FOR (x, y)\in \R^2 \\
\IND\LET (p, q) := (sq\otimes sq)( (x, y)) \\
\IND\RET sqrt(sum( (p, q) )) \\
\}\\
=>\\
\{ \\
\IND\FOR (x, y)\in \R^2 \\
\IND\RET sqrt(sum( (sq(x), sq(y)) )) \\
\}\\

変形の過程も見やすいですね。これは、可換図式を、ショートカットをしながら変形していく過程と同じことです。


\begin{CD}
\R^2 @>{sq\otimes sq}>> \R^2\\
@.                      @VV{sum}V \\
\R   @<{sqrt}<<         \R
\end{CD}\\
\:\\
=>\\
\:\\
\begin{CD}
\R^2 @>{sq\otimes sq}>> \R^2 \\
@.               @VV{sqrt\circ sum}V \\
{}      @.         \R
\end{CD}\\
\:\\
=>\\
\:\\
\begin{CD}
\R^2 @>{(sq\otimes sq)\circ sqrt\circ sum}>> \R \\
\end{CD}\\

ブロックラムダ式の動機は、可換図式が指示する計算を、なるべく素直に見やすく写し取ることです。

定義環境の記述

ノルムの例で、sum と sqrt は組み込み関数〈プリミティブ関数〉だとします。しかし、sq はユーザー定義関数だとしましょう。sq の定義がないと未定義エラーになってしまいます。

関数の定義もlet文で次のように書くことができます。


\{\\
\IND \LET sq := \lambda\,x\in \R.x\times x \\
\IND\{ \\
\IND\IND\FOR (x, y)\in \R^2 \\
\IND\IND\LET (p, q) := (sq\otimes sq)( (x, y)) \\
\IND\IND\LET s := sum( (p, q) ) \\
\IND\IND\RET sqrt(s) \\
\IND\}\\
\}

ただし、この書き方だと若干視認性が悪いし、関数定義であることをもっと強調したいので、次のようにします。


\{\\
\IND \DEF \FOR x\in \R \\
\IND\IND sq(x) := x\times x \\
\IND\{ \\
\IND\IND\FOR (x, y)\in \R^2 \\
\IND\IND\LET (p, q) := (sq\otimes sq)( (x, y)) \\
\IND\IND\LET s := sum( (p, q) ) \\
\IND\IND\RET sqrt(s) \\
\IND\}\\
\}

define文はシンタックスシュガーなので、let文による記述を禁止するものではありません(そもそも、letもシンタックスシュガーです)。必要なら、(記述順で)後から代入(むしろ束縛)を指定するwhere文を入れてもいいでしょう。

関数定義は何度も利用されることがあるので、別に書いておくこともできます(できるとします)。複数の関数をまとめて定義しておけば、関数ライブラリとして使えます。


\{\\
\IND \DEF \FOR x\in \R \\
\IND\IND sq(x) := x\times x \\
\IND \DEF \FOR (x, y)\in \R^2\\
\IND\IND sqsum(x, y) := sq(x) + sq(y) \\
\}

おわりに

モナドやベックの分配法則などに関わる法則は、ストリング図等式や可換図式で表現されます。ストリング図ノードや図式矢印が行列計算や積分計算を含む複雑なものになることもあります。それらの関数をテキストに写し取るとき間違いを犯すことはよくあります。

絵図と親和性が高くて視認性が良いテキスト記法を採用すれば、間違いを減らせます。ブロックラムダ記法は、この目的で使えると思います。

*1:キーワードの競合を避けるために、given x∈X とすることも考えられますが、語感としては for が自然な気がします。

*2:僕は、return を明示的に書くのはめんどうで嫌いなんですが、今回は視認性の観点から return を入れておきます。