Membangun kombinator lain dari kombinator S dan K (Bagian 1)

Kombinator S dan K dalam CL (combinatory logic) didefinisikan dengan

SXYZ \equiv XZ(YZ)

dan

KXY \equiv X

untuk sembarang CL-term X,Y,Z.

Secara makna, kombinator K dapat dipandang sebagai fungsi yang menerima dua masukan X dan Y, kemudian memberikan keluaran berupa parameter pertama X. Kombinator S sendiri dapat dipandang sebagai fungsi komposisi (saya baru paham cara menggunakannya setelah membaca buku Lambda Calculus and Combinators – an Introduction oleh J. Roger Hindley dan Jonathan P. Seldin). Fungsi komposisinya kurang lebih begini secara simbol:

(S(f,g))x = f(x,g(x)).

Jika Anda mempelajari logika melalui jalur lain, pasti cukup familiar dengan fungsi f(x,g(x)) ini. Dapat dilihat bahwa makna S yang berbentuk SXYZ \equiv XZ(YZ) ini sesuai dengan makna fungsi rekursif ini.

Sekarang, fungsi-fungsi kombinator lain dapat dibangun hanya menggunakan kombinator S dan K ini. Berikut adalah contoh dan cara mencari bentuk ekivalennya.

Contoh 1. Kombinator identitas

Kombinator I identitas memenuhi sifat IX \equiv X. Kombinator I ini dapat ditulis sebagai SKK. Mudah diverifikasi bahwa SKKX \rhd_w KX(KX) \rhd_w X. Namun, bagaimana cara mendapatkan bentuk SKK ini?

Contoh 2. Kombinator komposisi

Kombinator komposisi B berfungsi sebagai berikut:

(B(f,g))x \equiv f(g(x))

atau dalam bahasa CL, ditulis BXYZ = X(YZ). Mudah diverifikasi bahwa B \equiv S(KS)K:

S(KS)KXYZ \rhd_w (KSX)(KX)YZ \rhd_w S(KX)YZ \rhd_w (KXY)(YZ) \rhd_w X(YZ).

Nah, bagaimana pula mendapatkan bentuk S(KS)K ini?

Contoh 3. Fungsi suka-suka seperti [x,y,z].y(xz) atau [x,y].xyy

Kita juga bisa mencari bentuk CL-term dalam S dan K untuk fungsi di atas, misalnya

[x,y,z].y(xz) \equiv S(S(KS)(K(S(KS)K)))K

[x,y].xyy \equiv S(S(KS)(S(S(KS)K)(K(SKK))))(K(SKK)).

Sepertinya ribet sekali, ya? Padahal setelah paham cara menggunakan kombinator S ini sama sekali tidak susah ternyata. Kalau mau coba-coba latihan, coba kerjakan ini dulu:

Latihan 1. [x].xx

Latihan 2. [x,y,z].xzy

Pada bagian selanjutnya, saya akan mencoba menjelaskan cara mendapatkan kombinator ekivalen dalam S dan K saja.

(bersambung…)

 

 

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s