Pengertian Lambda kalkulus
Lambda kalkulus ( juga ditulis sebagai λ - kalkulus
atau disebut " kalkulus lambda " ) adalah sistem formal dalam
matematika logika dan ilmu komputer untuk mengekspresikan perhitungan dengan
cara variabel mengikat dan substitusi . Pertama dirumuskan oleh Gereja Alonzo ,
lambda kalkulus menemukan keberhasilan awal dalam bidang teori komputabilitas ,
seperti jawaban negatif ke Hilbert Entscheidungsproblem .
Karena pentingnya gagasan substitusi mengikat dan variabel , tidak ada satu sistem lambda kalkulus , dan khususnya ada yang diketik dan varian untyped . Secara historis , sistem yang paling penting adalah kalkulus lambda untyped , di mana fungsi aplikasi tidak memiliki batasan ( sehingga gagasan dari domain fungsi tidak dibangun ke dalam sistem ) . Dalam Tesis Church - Turing , lambda kalkulus untyped diklaim mampu menghitung semua fungsi efektif dihitung . The lambda kalkulus diketik adalah berbagai yang membatasi fungsi aplikasi , sehingga fungsi hanya dapat diterapkan jika mereka mampu menerima masukan yang diberikan itu "tipe " dari data.
Hari ini , kalkulus lambda memiliki aplikasi di berbagai bidang dalam matematika , filsafat , linguistik , dan ilmu komputer . Hal ini masih digunakan di bidang teori komputabilitas , meskipun mesin Turing juga merupakan model penting untuk perhitungan . Lambda kalkulus telah memainkan peran penting dalam pengembangan teori bahasa pemrograman . Rekan-rekan untuk lambda kalkulus dalam ilmu komputer adalah bahasa pemrograman fungsional , yang pada dasarnya menerapkan kalkulus ( ditambah dengan beberapa konstanta dan tipe data ) . Selain bahasa pemrograman , kalkulus lambda juga memiliki banyak aplikasi dalam teori bukti. Sebuah contoh utama dari hal ini adalah Curry - Howard korespondensi , yang memberikan korespondensi antara sistem yang berbeda dari diketik lambda kalkulus dan sistem logika formal .
1 Lambda kalkulus dalam sejarah matematika
The lambda kalkulus diperkenalkan oleh matematikawan Alonzo Church pada 1930-an sebagai bagian dari penyelidikan atas dasar matematika . [ 1 ] [ 2 ] Sistem asli terbukti secara logis tidak konsisten pada tahun 1935 ketika Stephen Kleene dan JB Rosser mengembangkan Kleene - Rosser paradoks .
Selanjutnya , pada tahun 1936 Gereja terisolasi dan diterbitkan hanya bagian yang relevan dengan perhitungan , apa yang sekarang disebut lambda kalkulus untyped [ 3 ] Pada tahun 1940 , ia juga memperkenalkan . Sebuah komputasi lemah , tetapi sistem logis konsisten , yang dikenal sebagai lambda kalkulus hanya diketik . [ 4 ]
Karena pentingnya gagasan substitusi mengikat dan variabel , tidak ada satu sistem lambda kalkulus , dan khususnya ada yang diketik dan varian untyped . Secara historis , sistem yang paling penting adalah kalkulus lambda untyped , di mana fungsi aplikasi tidak memiliki batasan ( sehingga gagasan dari domain fungsi tidak dibangun ke dalam sistem ) . Dalam Tesis Church - Turing , lambda kalkulus untyped diklaim mampu menghitung semua fungsi efektif dihitung . The lambda kalkulus diketik adalah berbagai yang membatasi fungsi aplikasi , sehingga fungsi hanya dapat diterapkan jika mereka mampu menerima masukan yang diberikan itu "tipe " dari data.
Hari ini , kalkulus lambda memiliki aplikasi di berbagai bidang dalam matematika , filsafat , linguistik , dan ilmu komputer . Hal ini masih digunakan di bidang teori komputabilitas , meskipun mesin Turing juga merupakan model penting untuk perhitungan . Lambda kalkulus telah memainkan peran penting dalam pengembangan teori bahasa pemrograman . Rekan-rekan untuk lambda kalkulus dalam ilmu komputer adalah bahasa pemrograman fungsional , yang pada dasarnya menerapkan kalkulus ( ditambah dengan beberapa konstanta dan tipe data ) . Selain bahasa pemrograman , kalkulus lambda juga memiliki banyak aplikasi dalam teori bukti. Sebuah contoh utama dari hal ini adalah Curry - Howard korespondensi , yang memberikan korespondensi antara sistem yang berbeda dari diketik lambda kalkulus dan sistem logika formal .
1 Lambda kalkulus dalam sejarah matematika
The lambda kalkulus diperkenalkan oleh matematikawan Alonzo Church pada 1930-an sebagai bagian dari penyelidikan atas dasar matematika . [ 1 ] [ 2 ] Sistem asli terbukti secara logis tidak konsisten pada tahun 1935 ketika Stephen Kleene dan JB Rosser mengembangkan Kleene - Rosser paradoks .
Selanjutnya , pada tahun 1936 Gereja terisolasi dan diterbitkan hanya bagian yang relevan dengan perhitungan , apa yang sekarang disebut lambda kalkulus untyped [ 3 ] Pada tahun 1940 , ia juga memperkenalkan . Sebuah komputasi lemah , tetapi sistem logis konsisten , yang dikenal sebagai lambda kalkulus hanya diketik . [ 4 ]
2 Deskripsi
Informal
a. motivasi
Fungsi Computable adalah konsep fundamental dalam ilmu komputer dan matematika . The λ - kalkulus menyediakan semantik sederhana untuk perhitungan , memungkinkan sifat komputasi untuk dipelajari secara formal . The λ - kalkulus menggabungkan dua penyederhanaan semantik yang membuat ini sederhana.
Salah satu penyederhanaan pertama adalah bahwa λ - kalkulus memperlakukan fungsi " anonim " , tanpa memberi mereka nama eksplisit . Sebagai contoh, fungsi
\ operatorname { } sqsum ( x , y ) = x \ kali x + y \ kali y
dapat ditulis dalam bentuk anonim sebagai
( x , y ) \ Maps untuk x \ kali x + y \ kali y
( dibaca sebagai " pasangan x dan y dipetakan ke x \ kali x + y \ kali y " ) . Demikian pula ,
\ operatorname { id } ( x ) = x
dapat ditulis dalam bentuk anonim sebagai x \ Maps untuk x , dimana input hanya dipetakan ke dirinya sendiri .
Penyederhanaan kedua adalah bahwa λ - kalkulus hanya memperlakukan fungsi input tunggal . Fungsi biasa yang membutuhkan dua input , misalnya \ operatorname { } sqsum fungsi , dapat dikerjakan ulang menjadi fungsi yang setara yang menerima input tunggal , dan sebagai output mengembalikan fungsi lain , yang pada gilirannya menerima input tunggal . Sebagai contoh,
( x , y ) \ Maps untuk x \ kali x + y \ kali y
dapat dikerjakan ulang ke
x \ Maps untuk ( y \ Maps untuk x \ kali x + y \ kali y )
Metode ini , yang dikenal sebagai currying , mengubah fungsi yang mengambil beberapa argumen ke dalam rantai fungsi masing-masing dengan argumen tunggal .
Menerapkan \ operatorname { } sqsum fungsi argumen ( 5 , 2 ) , hasil :
( ( x , y ) \ Maps untuk x \ kali x + y \ kali y ) ( 5 , 2 )
= 5 \ 5 kali + 2 \ kali 2 = 29
Namun, kari hasil versi :
( ( x \ Maps untuk ( y \ Maps untuk x \ kali x + y \ kali y ) ) ( 5 ) ) ( 2 )
= ( Y \ Maps untuk 5 \ 5 kali + y \ kali y ) ( 2 )
= 5 \ 5 kali + 2 \ kali 2 = 29
dan dengan demikian menghitung hasil yang sama .
b. lambda kalkulusa. motivasi
Fungsi Computable adalah konsep fundamental dalam ilmu komputer dan matematika . The λ - kalkulus menyediakan semantik sederhana untuk perhitungan , memungkinkan sifat komputasi untuk dipelajari secara formal . The λ - kalkulus menggabungkan dua penyederhanaan semantik yang membuat ini sederhana.
Salah satu penyederhanaan pertama adalah bahwa λ - kalkulus memperlakukan fungsi " anonim " , tanpa memberi mereka nama eksplisit . Sebagai contoh, fungsi
\ operatorname { } sqsum ( x , y ) = x \ kali x + y \ kali y
dapat ditulis dalam bentuk anonim sebagai
( x , y ) \ Maps untuk x \ kali x + y \ kali y
( dibaca sebagai " pasangan x dan y dipetakan ke x \ kali x + y \ kali y " ) . Demikian pula ,
\ operatorname { id } ( x ) = x
dapat ditulis dalam bentuk anonim sebagai x \ Maps untuk x , dimana input hanya dipetakan ke dirinya sendiri .
Penyederhanaan kedua adalah bahwa λ - kalkulus hanya memperlakukan fungsi input tunggal . Fungsi biasa yang membutuhkan dua input , misalnya \ operatorname { } sqsum fungsi , dapat dikerjakan ulang menjadi fungsi yang setara yang menerima input tunggal , dan sebagai output mengembalikan fungsi lain , yang pada gilirannya menerima input tunggal . Sebagai contoh,
( x , y ) \ Maps untuk x \ kali x + y \ kali y
dapat dikerjakan ulang ke
x \ Maps untuk ( y \ Maps untuk x \ kali x + y \ kali y )
Metode ini , yang dikenal sebagai currying , mengubah fungsi yang mengambil beberapa argumen ke dalam rantai fungsi masing-masing dengan argumen tunggal .
Menerapkan \ operatorname { } sqsum fungsi argumen ( 5 , 2 ) , hasil :
( ( x , y ) \ Maps untuk x \ kali x + y \ kali y ) ( 5 , 2 )
= 5 \ 5 kali + 2 \ kali 2 = 29
Namun, kari hasil versi :
( ( x \ Maps untuk ( y \ Maps untuk x \ kali x + y \ kali y ) ) ( 5 ) ) ( 2 )
= ( Y \ Maps untuk 5 \ 5 kali + y \ kali y ) ( 2 )
= 5 \ 5 kali + 2 \ kali 2 = 29
dan dengan demikian menghitung hasil yang sama .
lambda kalkulus terdiri dari bahasa istilah lambda , yang didefinisikan oleh sintaks formal yang tertentu , dan satu set aturan transformasi , yang memungkinkan manipulasi istilah lambda . Aturan transformasi ini dapat dilihat sebagai teori equational atau sebagai definisi operasional .
Seperti dijelaskan di atas , semua fungsi dalam kalkulus lambda adalah fungsi anonim , tidak memiliki nama . Mereka hanya menerima satu variabel input, dengan currying digunakan untuk mengimplementasikan fungsi dengan beberapa variabel .
istilah lambda
Sintaks dari kalkulus lambda mendefinisikan beberapa ekspresi sebagai pernyataan lambda kalkulus valid dan beberapa sebagai tidak sah , sama seperti beberapa string karakter adalah program C yang valid dan ada juga yang tidak . Sebuah ekspresi lambda kalkulus valid disebut " lambda istilah" .
Tiga aturan berikut memberikan definisi induktif yang dapat diterapkan untuk membangun semua persyaratan lambda sintaksis valid :
variabel , x , itu sendiri merupakan istilah lambda valid
jika t adalah istilah lambda , dan x adalah variabel , maka ( \ lambda xt ) adalah istilah lambda ( disebut abstraksi lambda ) ;
jika t dan s adalah istilah lambda , maka ( ts ) adalah istilah lambda ( disebut aplikasi ) .
Tidak ada lagi adalah istilah lambda . Jadi istilah lambda berlaku jika dan hanya jika dapat diperoleh dengan aplikasi berulang dari ketiga aturan . Namun, beberapa tanda kurung dapat dihilangkan sesuai dengan aturan-aturan tertentu . Misalnya, tanda kurung terluar biasanya tidak ditulis .
Sebuah abstraksi lambda \ lambda xt adalah definisi dari fungsi anonim yang mampu mengambil input tunggal x dan menggantikannya ke dalam ekspresi t . Dengan demikian mendefinisikan fungsi anonim yang mengambil x dan mengembalikan t . Misalnya \ lambda xx ^ 2 +2 adalah abstraksi lambda untuk fungsi f ( x ) = x ^ 2 + 2 menggunakan istilah x ^ 2 +2 untuk t . Definisi fungsi dengan abstraksi lambda hanya " set up " fungsi tetapi tidak meminta itu. Abstraksi mengikat x variabel dalam jangka t .
Sebuah ts aplikasi merupakan aplikasi dari fungsi t ke input s , yaitu , itu merupakan tindakan memanggil fungsi t input untuk memproduksi t ( s ) .
Tidak ada konsep dalam kalkulus lambda deklarasi variabel . Dalam definisi seperti \ lambda x.x + y ( yaitu f ( x ) = x + y ) , memperlakukan lambda kalkulus y sebagai variabel yang belum didefinisikan . The lambda abstraksi \ lambda x.x + y adalah sintaksis yang valid , dan merupakan fungsi yang menambahkan masukan terhadap y yang belum diketahui .
Bracketing dapat digunakan dan mungkin diperlukan untuk disambiguate istilah. Sebagai contoh, \ lambda x . ( ( \ Lambda xx ) x ) dan ( \ lambda x . ( \ Lambda xx ) ) x menunjukkan istilah yang berbeda .
Fungsi yang beroperasi pada fungsi
Dalam kalkulus lambda , fungsi diambil untuk menjadi ' nilai-nilai kelas' , sehingga fungsi dapat digunakan sebagai input kembali sebagai output dari fungsi lain .
Sebagai contoh, \ lambda xx merupakan fungsi identitas , x \ Rightarrow x , dan ( \ lambda xx ) y merupakan fungsi identitas diterapkan untuk y . Selanjutnya , ( \ lambda xy ) merupakan konstanta fungsi x \ Rightarrow y , fungsi yang selalu mengembalikan y , tidak peduli input . Dalam kalkulus lambda , fungsi aplikasi dianggap sebagai kiri - asosiatif , sehingga stx berarti ( st ) x .
Ada beberapa pengertian tentang " kesetaraan " dan " pengurangan " yang memungkinkan istilah lambda untuk "mengurangi " untuk " setara " istilah lambda .
Alpha kesetaraan
Bentuk dasar kesetaraan , didefinisikan pada istilah lambda , adalah alpha kesetaraan . Ia menangkap intuisi bahwa pilihan tertentu dari variabel terikat , dalam abstraksi lambda , tidak (biasanya ) materi. Misalnya , \ lambda xx dan \ lambda yy adalah alpha -setara istilah lambda , dan mereka berdua merupakan fungsi yang sama ( fungsi identitas ) . Istilah x dan y tidak alpha -setara , karena mereka tidak terikat dalam abstraksi lambda . Dalam banyak presentasi , biasanya untuk mengidentifikasi alpha -setara istilah lambda .
Definisi berikut diperlukan agar dapat menentukan pengurangan beta .
variabel bebas
Variabel bebas dari istilah adalah variabel-variabel tidak terikat oleh abstraksi lambda . Himpunan variabel bebas ekspresi didefinisikan secara induktif :
Variabel bebas x hanya x
Himpunan variabel bebas \ lambda xt adalah himpunan variabel bebas t , tetapi dengan x dihapus
Himpunan variabel bebas ts adalah persatuan dari himpunan variabel bebas t dan set variabel bebas s .
Misalnya, istilah lambda mewakili identitas \ lambda xx tidak memiliki variabel bebas , tetapi fungsi \ lambda x.x + y memiliki satu variabel bebas , y .
Menangkap - menghindari substitusi
Misalkan t , s dan r adalah istilah lambda dan x dan y adalah variabel . Notasi t [ x : = r ] menunjukkan substitusi r untuk x di t dengan cara capture - menghindari . Ini didefinisikan sehingga :
x [ x : = r ] = r ;
y [x : = r ] = y jika x \ neq y ;
( ts ) [x : = r ] = ( t [ x : = r ] ) ( s [ x : = r ] ) ;
( \ lambda x.t ) [x : = r ] = \ lambda x.t ;
( \ lambda yt ) [x : = r ] = \ lambda y . ( t [ x : = r ] ) jika x \ neq y dan y tidak dalam variabel bebas r . Variabel y dikatakan " fresh " untuk r .
Sebagai contoh, ( \ lambda xx ) [ y : = y ] = \ lambda x . ( X [ y : = y ] ) = \ lambda xx , dan ( ( \ lambda xy ) x ) [x : = y ] = ( ( \ lambda xy ) [x : = y ] ) ( x [ x : = y ] ) = ( \ lambda xy ) y .
Kondisi kesegaran ( mengharuskan y tidak dalam variabel bebas r ) sangat penting untuk memastikan substitusi yang tidak mengubah arti dari fungsi . Misalnya, substitusi dibuat yang mengabaikan kondisi kesegaran : ( \ lambda xy ) [ y : = x ] = \ lambda x ( y [ y : = x ] ) . = \ Lambda xx Substitusi ini ternyata konstan fungsi \ lambda xy ke dalam identitas \ lambda xx dengan substitusi .
Secara umum, kegagalan untuk memenuhi kondisi kesegaran dapat diatasi dengan alpha - mengganti nama dengan variabel segar cocok . Misalnya, beralih kembali ke gagasan yang benar kita substitusi , di ( \ lambda yx ) [x : = y ] abstraksi lambda dapat diganti dengan variabel z segar, untuk mendapatkan ( \ lambda zx ) [x : = y ] = \ lambda z . ( x [ x : = y ] ) = \ lambda zy , dan makna dari fungsi tersebut diawetkan dengan substitusi .
pengurangan Beta
Penurunan beta aturan menyatakan bahwa sebuah aplikasi dari bentuk ( λx.t ) s mengurangi ke t istilah [ x : = s ] . Notasi ( λx.t ) s → t [x : = s ] digunakan untuk menunjukkan bahwa ( λx.t ) s beta mengurangi t [x : = s ] . Sebagai contoh, untuk setiap s , ( λx.x ) s → x [x : = s ] = s . Hal ini menunjukkan bahwa λx.x benar-benar adalah identitas . Demikian pula , ( λx.y ) s → y [ x : = s ] = y , yang menunjukkan bahwa λx.y adalah fungsi konstan.
The lambda kalkulus dapat dilihat sebagai sebuah bahasa pemrograman fungsional ideal , seperti Haskell atau Standard ML . Dalam pandangan ini , pengurangan beta sesuai dengan langkah komputasi . Langkah ini dapat diulang oleh konversi beta tambahan sampai tidak ada lagi aplikasi yang tersisa untuk mengurangi . Dalam kalkulus lambda untyped , seperti yang disajikan di sini , proses reduksi ini tidak perlu mengakhiri. Sebagai contoh, mempertimbangkan istilah ( λx.xx ) ( λx.xx ) . Di sini ( λx.xx ) ( λx.xx ) → ( xx ) [x : = λx.xx ] = ( x [ x : = λx.xx ] ) ( x [ x : = λx.xx ] ) = ( λx. xx ) ( λx.xx ) . Artinya, istilah tereduksi menjadi dirinya sendiri dalam pengurangan beta tunggal , dan oleh karena itu proses reduksi tidak akan pernah berakhir .
Aspek lain dari kalkulus lambda untyped adalah bahwa hal itu tidak membedakan antara berbagai jenis data. Misalnya, mungkin diinginkan untuk menulis fungsi yang hanya beroperasi pada angka. Namun, dalam kalkulus lambda untyped , tidak ada cara untuk mencegah fungsi dari yang diterapkan pada nilai-nilai kebenaran , string , atau benda non - nomor lain .
definisi formal
definisi
Ekspresi Lambda terdiri dari
variabel v1 , v2 , ... , vn , ...
abstraksi simbol λ dan .
kurung ( )
Himpunan ekspresi lambda , Λ , dapat didefinisikan secara induktif :
Jika x adalah variabel , maka x ∈ Λ
Jika x adalah variabel dan M ∈ Λ , kemudian ( λx.M ) ∈ Λ
Jika M , N ∈ Λ , kemudian ( M N ) ∈ Λ
Contoh aturan 2 dikenal sebagai abstraksi dan contoh aturan 3 dikenal sebagai aplikasi . [ 5 ]
catatan
Untuk menjaga notasi ekspresi lambda rapi , konvensi berikut ini biasanya diterapkan .
Kurung terluar dijatuhkan : MN bukan ( MN )
Aplikasi diasumsikan kiri asosiatif : MNP dapat ditulis bukan ( ( MN ) P ) [ 6 ]
Tubuh abstraksi meluas sejauh tepat mungkin : λx.MN berarti λx ( MN ) dan tidak ( λx.M ) N .
Urutan abstraksi dikontrak : λx.λy.λz.N disingkat sebagai λxyz.N [ 7 ] [ 8 ]
Variabel bebas dan terikat
Operator abstraksi , λ , dikatakan untuk mengikat variabel mana pun itu terjadi dalam tubuh abstraksi . Variabel yang termasuk dalam ruang lingkup dari abstraksi dikatakan terikat . Semua variabel lain disebut bebas . Sebagai contoh, dalam hal berikut ekspresi y adalah variabel terikat dan bebas x : λy.xx y . Perlu diketahui juga bahwa variabel terikat oleh " terdekat " abstraksi . Pada contoh berikut terjadinya tunggal x dalam ekspresi terikat oleh lambda kedua : λx.y ( λx.zx )
Himpunan variabel bebas dari ekspresi lambda , M , dilambangkan sebagai FV ( M ) dan didefinisikan dengan rekursi pada struktur istilah , sebagai berikut :
FV ( x ) = { x } , di mana x adalah variabel
FV ( λx.M ) = FV ( M ) \ { x }
FV ( M N ) = FV ( M ) ∪ FV ( N ) [ 9 ]
Sebuah ekspresi yang tidak mengandung variabel bebas dikatakan ditutup . Ekspresi lambda tertutup juga dikenal sebagai combinators dan setara dengan istilah dalam logika combinatory .
