2013/09/05

不動点コンビネータの作り方(λ抽象)

「λ抽象」とわざわざ付けたのは、SKIコンビネータとかでも不動点コンビネータは作れるよなあ、などとしょうがないことを考えただけであって、 λ抽象の方がだいぶ簡単に作れるとはいえどちらも本質的には同じものであるから、とりあえず簡単な方だけ紹介しようという目論見である。
SKIコンビネータで作りたいなら自動生成するなりプロの技で作るなりすればいいと思う。

基本方針

不動点コンビネータとは、
Fg -> g(Fg) となるようなλ抽象Fのことである。
後述するが、これによってλ計算で再帰を記述できるようになる。
(ちなみに、コンビネータとは自由変数を含まないλ抽象のこと……だと思う)

さて、簡約後の式にF自体が含まれているということは、Fは何か断片から全体を再生できる構造になっている必要がある。
より正確には、「コピーや再生、適用を担当する式」と「適用される側の式」の2段構えになっていて、かつ前者と後者はどちらか一方から再現できるのが良い。
まあ最初に思いつくのは前者と後者が全く同じ場合だし、他にクールな方法も思いつかないので、ここではその戦略でいく。
以下では、その断片をfとし、fを代入される予定の束縛変数をcとしよう。

Fg -> ffg

「繰り返し」の最も単純なパターン。まあ発想の単純さと完成したコンビネータの単純さに相関があるかは知らないが。

Fg -> ffg -> g(Fg) -> g(ffg) fab -> b(aab) より f = (λa.(λb.b(aab))) よって F = (λc.cc)(λa.(λb.b(aab)))

Fg -> fgf

これはちょっとひねくれている。とはいえ、することは上と同じだ。

Fg -> fgf -> g(Fg) -> g(fgf) fab -> a(bab) より f = (λa.(λb.a(bab))) よって F = (λc.(λg.cgc))(λa.(λb.a(bab)))

Fg -> fg(fg)

実はこれがなかなか良い。

Fg -> fg(fg) -> g(Fg) -> g(fg(fg)) fab -> a(bb) より f = (λa.(λb.a(bb))) このとき fg -> (λb.g(bb)) より F = (λg.fg(fg)) = (λg.(λb.g(bb))(λb.g(bb)))

これは特に「Yコンビネータ」と呼ばれる。
(普通は (λf.(λx.f(xx))(λx.f(xx))) と書かれる。)

不動点コンビネータの使い方(再帰)

面倒なので再帰としての簡単な使い方だけ書く。
まあこの記事を読みたいような人なら言うまでもないだろうけど。

function f(x) { if(p(x)) { A(x); } else { f(B(x)); } } という処理は、 Yfx -> f(Yf)x より、 f = (λn.(λx.px(Ax)(n(Bx)))) と表現できる。 (ただし、pxは真偽値を返し、true = (λxy.x)、false = (λxy.y) とする)

2013/09/04

「checking version... configure: error: not suitable, we need >= 1.0.6」の解決

詳細はここ。
[Libreoffice-bugs] [Bug 45652] New: error in autogen.sh. Incorrect detection mysqlcppconn (MySQL c++ connector)
ログは略。

$ emerge --version Portage 2.2.1 (default/linux/amd64/13.0/desktop, gcc-4.8.0, glibc-2.17, 3.10.7-gentoo x86_64) $ sudo emerge -u libreoffice (略) checking version... configure: error: not suitable, we need >= 1.0.6 (後略)

問題が起きるlibreofficeのバージョンは4.0.4.2以降。 確認した限りでは4.1.1.2でもこの問題が起きた。
このメッセージの意味するところは「dev-db/mysql-connector-c++ のバージョンが古い」ということなのだが、実際の問題点は「mysqlのshared libraryがロードされていない」ことである。

簡単に説明すると、例えばlibreoffice-4.1.1.2のconfigure.acにおいては以下のような記述がある。
なお、先頭の数字は行番号。

libreoffice-4.1.1.2/configure.ac
7671 AC_MSG_CHECKING([MySQL Connector/C++]) 7672 if test "$with_system_mysql_cppconn" = "yes"; then 7673 AC_MSG_RESULT([external]) 7674 SYSTEM_MYSQL_CPPCONN=YES 7675 AC_LANG_PUSH([C++]) 7676 AC_CHECK_HEADER(mysql_driver.h, [], 7677 [AC_MSG_ERROR(mysql_driver.h not found. install MySQL C++ Connectivity)], []) 7678 AC_CHECK_LIB([mysqlcppconn], [main], [:], 7679 [AC_MSG_ERROR(MySQL C++ Connectivity lib not found or functional)], []) 7680 save_LIBS=$LIBS 7681 LIBS="$LIBS -lmysqlcppconn" 7682 AC_MSG_CHECKING([version]) 7683 AC_RUN_IFELSE([AC_LANG_SOURCE([[ 7684 #include 7685 7686 int main(int argc, char **argv) { 7687 sql::Driver *driver; 7688 driver = get_driver_instance(); 7689 if (driver->getMajorVersion() > 1 || \ 7690 (driver->getMajorVersion() == 1 && driver->getMinorVersion() > 0) || \ 7691 (driver->getMajorVersion() == 1 && driver->getMinorVersion() == 0 && driver->getPatchVersion() >= 6)) 7692 return 0; 7693 else 7694 return 1; 7695 } 7696 ]])],[AC_MSG_RESULT(OK)],[AC_MSG_ERROR([not suitable, we need >= 1.0.6])],[]) 7697 7698 AC_LANG_POP([C++]) 7699 LIBS=$save_LIBS 7700 else

ここで7684行から7695行までのコードがコンパイル・実行され、それが0を返した場合はバージョンが要求される条件を満たすと判断するようだ。
しかし、(少なくとも俺の)gentooでは、/usr/lib/mysql/にパスが通っていないため、コンパイルは通るもののlibmysqlclient.so.18がロードされず、その結果上記プログラムは実行時エラーを返す。無論、戻り値は0ではない。
んで、その結果バージョンが古すぎると判定されるという仕組みだ。
解決策として、mysqlのライブラリがロードされるようにパスを通せば良い。
幸運にも、gentooはld.so.confを編集したりせずともグローバルの環境変数を弄れる仕組みがあるので、それを利用する。

/etc/env.d/99local (追記、無ければ新規作成)
# for mysql LDPATH="/usr/lib/mysql:/usr/lib64/mysql"

シェルのPATH環境変数を弄ったことのある人には違和感があるかもしれないが、ここで記されているように、LDPATHは自動で連結される仕組みになっているので、

LDPATH="foo:bar:$LDPATH"
のように最後にLDPATH自体を繋げる必要は無いらしい。

さて、上記ファイルを作成したら最後に変更を反映させよう。

# env-update && source /etc/profile

have a good gentoo!