λ算法

λx(x+1)

(λx(x+1) 2) => 3

‥‥‥うろおぼえだからなんか違う気がする。
- あってたみたい。:)

[[id:696]] 2002-06-24 18:19:14

組み合わせ子

コンビネータ
自由変数 (#5)をもたないλ式のこと？
いろいろな機能をもつ式が知られている。
----
Y Combinator
『ちなみにコンビネータっていうのはプログラム意味論の用語。手続き名も含む「変数」がすべて束縛変数である (引数になっている) λ式のこと。そういうλ式はまわりの環境に依らずに同じ動作ができる……つまり完全に自分自身の意味が固定されている。』‥‥‥だそうです。
----
恒等関数 I Combinator
I = λxx

2変数の関数の引数の順序を変える操作 C Combinator
C = λfλxλy(f(y)x)

2変数の関数に1つの値を二重に与える操作 W Combinator
W = λfλx((fx)x)

定数関数 K Combinator
K = λxλyx

関数合成 B Combinator
B = λfλgλx(f(gx))

以下は調査中*
S = λfλgλx((fx)(gx))
----
# Common Combinators: B, C, W, K, I, S

[[id:697]] 2002-08-26 17:32:44

S Combinator

Re: 組み合わせ子 (#2)
2ch Haskellスレより発見しました。以下引用。
----
>>69
> あとSの意味が判らない。どう使うんだろう？
> S = \ x y z -> x z ( y z )

Distributor.

Combinator式は、グラフとして素直に表すことができるから、
部分グラフは、元のプログラムを分割したものと考えられる。
部分プログラムxと部分プログラムyの両方に引数zを渡し適用するのが役割。

x側では引数zは必要なければ、

(K x' z) (y z)

てな感じになる。(x ≡ K x')
(x z)を(y z)に適用するのは、部分プログラム同士を結合する方法が、
「適用」以外にはないから。Combinator logicやlambda calculusでは。

RAM(Random Access Machine)ではメモリ参照で、データを扱うわけだけど、
Combinator logicやlambda calculusでは、どんどん受け渡していくことになる。
# lambda calculusのβ簡約をメモリ参照で直感的に理解している人も多いと思うが。

[[id:1220]] 2002-09-18 13:54:19

Y Combinator

Schemeで書くと6行。
(define Y
(lambda (X)
((lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg))))
(lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg)))))))

なのに、Haskell で書くと、
y f = f (y f)

なんと1行で済んでしまうらしい。Lazyなせい？
----
λ算法では、Yは不動点演算子と呼ばれるそうだ。以下は岩波講座情報科学 12 「算法表現論」木村泉、米澤明憲著 (本棚) の要約。

基本は、自分自身を適用する関数
λx(xx)

これを更に自分自身に適用すると
(λx(xx)λx(xx))
何回簡約しても同じ式になる式ができる。

ちょっと変形して
(λx(F(xx))λx(F(xx)))
をZとすると、
Z => (FZ) => (F(FZ)) => (F(F(FZ)))
と無限にFを作用し続ける式。

ここで関数F(自由変数)をλ抽象して
Y ≡ λf(λx(f(xx))λx(f(xx)))

ためしにこれをある関数Fに適用すると
(YF) ≡ (F(YF))

をを、Haskell の定義と同じ形が！

[[id:937]] 2002-08-10 01:52:43

自由変数

λx(x+y)
というλ式において、yは自由変数である。これをラムダ抽象した
λyλx(x+y)
という式では自由変数は存在しない。（←間違いでした）
-「自由変数は存在しない」式をclosure(閉方関数)っていう？
- それは組み合わせ子 (#2)。closureが閉じ込めているのは、自由変数です。自由変数というのは関数の外側で定義されている（であろう）変数のことです。関数から見ると、自由変数は任意の定数とみなされます。
ラムダ算法において変数は自由変数と束縛変数に分けられる。一般のプログラミング言語におけるローカル変数、関数の内側で定義され、内側でしか参照されない変数は、束縛変数とみなされます。(letはlambdaで置き換え可能なため)

[[id:698]] 2002-08-07 12:35:40

コンビネータの意味がやっとわかったので補足します

Re: 自由変数 (#5)
λxλy(x + y)
ではコンビネータ―になっていない。なぜなら関数を表す名前 "+" の意味が外から与えられているため。
（⇒ "+" が自由変数となっている）
この + をλ抽象して、λ(+)λx λy (x + y) するとコンビネータになる。
中置演算子"+"だと分かりにくいので普通の関数fに置き換えると
λfλxλy(f x y)

"mod" が整数の剰余を取る中置演算子であるとき、
λ(+)λxλy(x + y) というλ式(コンビネータ)を mod, 8, 3 という値に適用すると、

(λ(+)λxλy(x + y) mod 8 3)
==> (8 mod 3)
==> 2

となる。

LISPで書くと
((lambda (f x y) (funcall f x y)) #'mod 8 3)
==> 2

[[id:936]] 2002-08-07 22:23:26

クロージャ

岩波コンピュータサイエンス「Common Lisp 入門」より引用

クロージャ(closure) という言葉は、closeから連想されるように、本来「閉鎖」を意味する。

(funcall '(lambda (x) (* x y)) 3)

における変数のyはこのラムダ式の外部に対して「開いている」と見なす。
Common Lisp以外の大多数のLisp(*1) ではfuncallがいつ呼び出されたかによってこのyの指す変数が異なる。yの意味がオープンなのである。
その開いたものを「閉じる」、つまりyが定まったものを指すようにするのが本来の役割だったのである。(*2)
Common Lispの場合は、このyは必ず大域変数を指すのでyが開いている感じがあまりしない。
したがってクロージャは閉じるものという本来の意味も薄れているが、Lispの慣習にしたがってCommon Lispでもこの言葉が使われている。

--
*1 純LispやMacLisp、EmacsLispなどのダイナミックスコープなLispのことを指す。Common Lisp、Schemeはレキシカルスコープ。
*2 Common Lispの場合、'function が引数に関数名またはラムダ式を取り、クロージャを返す関数。

(lambda (x) (+ x 1))
=> undefined function 'lambda

((lambda (x) (+ x 1)) 5)
=> 6

(function
(lambda (x) (+ x 1)))
=> #<lexical-closure: (lambda (x) (+ x 1))>

[[id:732]] 2002-06-18 09:24:32

関数適用

式のなかで変数と思われていたものをある値に固定すること、すなわち変数に値を代入することを関数のある値への作用、あるいは適用と呼ぶ。
関数 λx(x^2+x)^2 の、値 2 への適用は、
(λx(x^2+x)^2 2)
と書きあらわされ、結果として 36 が得られる。

また関数 λxλy(y+x) を、値 1 に適用すると、
(λxλy(y+x) 1) --> λy(y+1)
と、引数に１を加える関数 λy(y+1) が得られる。
- このへんがcurryingとか関数の部分適用とかいうところにつながるわけですね。

[[id:822]] 2002-06-30 23:32:24

参考リンク

ラムダ計算ＡＢＣ
型なしλ計算について

[[id:938]] 2002-08-07 12:55:37

top recent

HashedWiki version 3 beta
SHIMADA Keiki

λ算法

目次