Pemrograman Fungsional

Sebuah program fungsional terdiri dari E ekspresi (mewakili kedua algoritma dan masukan). Ini E ekspresi tunduk pada beberapa aturan menulis ulang. Pengurangan terdiri dari mengganti beberapa bagian dari E P oleh satu lagi P ungkapan 'menurut aturan menulis ulang diberikan. ... Proses pengurangan akan diulangi sampai ekspresi yang dihasilkan memiliki bagian lagi yang bisa ditulis ulang. Ekspresi E * yang diperoleh disebut bentuk normal E dan merupakan output dari program fungsional H. P. Barendregt

Pemrograman fungsional ditandai oleh pemrograman dengan nilai-nilai, fungsi dan bentuk fungsional.

Kata kunci dan frase: kalkulus Lambda, variabel bebas dan terikat, ruang lingkup, lingkungan, pemrograman fungsional, logika kombinatorial, fungsi rekursif, fungsional, kari fungsi.

Bahasa pemrograman fungsional adalah hasil dari kedua abstrak dan generalisasi tipe data peta. Ingat, m pemetaan dari setiap x elemen dari S (disebut domain) ke elemen yang sesuai
m (x) dari T (disebut kisaran) ditulis sebagai:

m: S -> T

Sebagai contoh, fungsi mengkuadratkan adalah fungsi dari jenis:

sqr: Bil -> Bil

dan dapat didefinisikan sebagai:

sqr mana x | -> x * x

Sebuah fungsi f linier dari jenis

f: Bil -> Bil


dapat didefinisikan sebagai:

f mana x | -> 3 * x + 4

Fungsi:

g mana x | -> 3 * x2 + 4
dapat ditulis sebagai komposisi fungsi f dan sqr sebagai:

f \ CIRC sqr

mana

f \ CIRC sqr (x) = f (sqr (x)) = f (x * x) = 3 * x2 + 4

Operator komposisi adalah contoh dari bentuk fungsional. Pemrograman fungsional didasarkan pada
konsep matematika fungsi dan bahasa pemrograman fungsional adalah sebagai berikut:

- Satu set dari fungsi primitif.
Satu set bentuk fungsional.
Operasi aplikasi.
Satu set objek data dan fungsi terkait.
Sebuah mekanisme untuk mengikat nama ke fungsi.

LISP, FP, Skema, ML, Miranda dan Haskell hanya beberapa bahasa untuk melaksanakan hal ini elegan
paradigma komputasi.

Konsep dasar pemrograman fungsional LISP berasal. Pemrograman fungsional
bahasa penting untuk alasan-alasan berikut.

• membagi-bagikan pemrograman fungsional dengan perintah tugas membebaskan programmer dari modus kaku berurutan pemikiran yang diperlukan dengan perintah penugasan.
• pemrograman fungsional mendorong pemikiran pada tingkat abstraksi yang lebih tinggi dengan menyediakan fungsi higherorder - fungsi yang memodifikasi dan menggabungkan program yang ada.
• pemrograman fungsional memiliki implementasi alami dalam pemrograman konkuren.
Pemrograman fungsional memiliki area aplikasi penting. Pemrograman kecerdasan buatan dilakukan dalam bahasa pemrograman fungsional dan teknik-teknik AI bermigrasi ke aplikasi dunia nyata.
• pemrograman fungsional berguna untuk mengembangkan spesifikasi eksekusi dan implementasi prototipe.
• pemrograman fungsional memiliki hubungan dekat dengan teori ilmu komputer. Pemrograman fungsional didasarkan pada kalkulus lambda-yang pada gilirannya menyediakan kerangka kerja untuk mempelajari pertanyaan decidability pemrograman. Inti dari semantik denotational adalah terjemahan dari program konvensional ke dalam program fungsional setara.

Terminologi. Bahasa pemrograman fungsional disebut aplikatif karena
fungsi yang diterapkan pada argumen mereka, deklaratif dan non-prosedural sejak
definisi menentukan apa dan tidak dihitung bagaimana dihitung.

Kalkulus Lambda

Bahasa pemrograman fungsional didasarkan pada kalkulus lambda. kalkulus lambda ditemukan oleh Alonzo Church dan Stephen Kleene pada awal tahun 1930an untuk meresmikan gagasan komputabilitas (dikenal juga sebagai Constructibility dan Calculability Effective).

Itu adalah formalisasi gagasan fungsi sebagai aturan (sebagai lawan fungsi sebagai tupel). Seperti ekspresi matematika, hal itu ditandai dengan prinsip bahwa nilai dari sebuah ekspresi hanya bergantung pada nilai-nilai mengelompokkan sub ekspresi nya.Kalkulus lambda adalah bahasa sederhana dengan beberapa konstruksi dan semantik sederhana.

Tapi, ini ekspresif, cukup kuat untuk mengekspresikan semua fungsi yang dapat dihitung.

Sebagai contoh informal lambda-kalkulus, mempertimbangkan fungsi yang didefinisikan oleh ekspresi polinomial

x2 + 3x – 5.

Variabel x adalah parameter. Dalam kalkulus lambda, notasi \ x.M digunakan untuk menunjukkan suatu fungsi dengan parameter x dan tubuh M. Artinya, x dipetakan kepada M. Kami menulis ulang fungsi kita dalam format ini.

\x.(x2+ 3x – 5)

dan baca itu sebagai “fungsi dari x yang nilainya didefinisikan oleh x2 + 3x - 5 \ '\'. Kalkulus Lambda menggunakan awalan bentuk dan jadi kami menulis ulang tubuh dalam bentuk awalan,

\x. (- (+ (× x x) (× 3 x)) 5).

Kalkulus Lambda membawa lebih dari satu fungsi dari variabel (+ xy) ditulis sebagai ((+ x) y), fungsi (+ x) adalah fungsi yang menambahkan sesuatu untuk x. Menulis ulang contoh dalam bentuk yang kita dapatkan:

\x.((- ((+ ((× x) x)) ((× 3) x))) 5)

Untuk menunjukkan penerapan fungsi f untuk argumen a yang kita tulis

f a

untuk menerapkan contoh kita dengan nilai 1 kita tulis

\x.((- ((+ ((× x) x)) ((× 3) x))) 5) 1.

Untuk mengevaluasi fungsi aplikasi, kita hapus \ \ x. dan mengganti setiap kejadian yang tersisa dari x dengan 1 untuk mendapatkan:

((- ((+ ((× 1) 1)) ((× 3) 1))) 5)

kemudian mengevaluasi dua ekspresi perkalian

((- ((+ 1) 3)) 5)

kemudian penambahannya

((- 4) 5)

dan akhirnya pengurangan

-1.

Kita katakan bahwa variabel x terikat dalam ekspresi lambda-\ \ x.B. variabel tersebut terjadi dalam ekspresi lambda yang tidak terikat dikatakan bebas. Variabel x bebas dalam ekspresi lambda-\ \ y. ((+ X) y). Ruang lingkup variabel diperkenalkan atau terikat oleh lambda adalah himpunan abstraksi lambda . notasi-lambda meluas dengan mudah ke fungsi beberapa argumen. Fungsi lebih dari satu argumen dapat kari untuk menghasilkan fungsi argumen tunggal. Sebagai contoh, ekspresi polinomial xy dapat ditulis sebagai

\x. \y. xy

Ketika abstraksi lambda \ x. \ Y. xy diterapkan pada argumen tunggal seperti dalam (\ x. \ y. xy 5) hasilnya adalah \ y.5y, sebuah fungsi yang mengalikan argumen dengan 5. Sebuah fungsi dari lebih dari satu argumen dianggap sebagai fungsional dari satu variabel yang nilainya merupakan fungsi dari variabel yang tersisa, dalam hal ini, “kalikan dengan fungsi konstan”.Karakter khusus dari kalkulus lambda diilustrasikan ketika diakui bahwa fungsi tersebut dapat diterapkan ke fungsi lain dan bahkan memungkinkan aplikasi itu sendiri.

Sebagai contoh biarkan C = \f.\x . (f(fx))

Kalkulus lambda murni tidak memiliki fungsi built-in atau konstanta. Oleh karena itu, tepat untuk berbicara tentang kalkulus lambda sebagai keluarga bahasa fungsi komputasi. Bahasa yang berbeda diperoleh dari pilihan yang berbeda fungsi dan konstanta.

Kita akan memperpanjang kalkulus lambda dengan operasi matematika umum dan konstanta dimana \x.((+3) x) mendefinisikan sebuah fungsi yang memetakan x ke x + 3. Kita akan menghilangkan sebagian dari tanda kurung untuk mempermudah pembacaan ekspresi lambda.

Sebuah ekspresi lambda dieksekusi dengan mengevaluasinya. Evaluasi dihasilkan dengan berulang kali memilih ekspresi yang dapat dikurangi (atau redex) dan menguranginya. Sebagai contoh, ekspresi (+ (* 5 6) (* 8 3)) tereduksi menjadi 54 dalam pengurangan urutan sebagai berikut.

(+ (* 5 6) (* 8 3)) --> (+ 30 (* 8 3))

--> (+ 30 24)

--> 54

Ketika ekspresi adalah aplikasi dari sebuah abstraksi lambda memiliki batas, batas ini menggantikan variabel dependen. Substitusi ini disebut \reduksi beta. Di urutan pengurangan berikut, contoh-contoh langkah pertama \reduksi beta. Langkah kedua adalah pengurangan yang diperlukan oleh operator penambahan.

(\x.((+ 3) x)) 4

((+ 3) 4)

7

Kalkulus lambda murni hanya memiliki tiga konstruksi: simbol primitif, aplikasi fungsi dan penciptaan fungsi. Gambar N.1 memberikan sintaks kalkulus lambda

Gambar 1. KALKULUS LAMBDA

Sintaks

L DALAM ekspresi lambda

x DALAM Simbol

L ::= x | (L L) | (lx.L)

(L L) adalah fuNGSI apLIKaSI, DAN (lx.L) ADALAH ABSTRAKSI LAMBDA YANG  MENdefinIsIKAN FUNGSI DENGAN ARGUMEN x DAN TUBUH L.

Kita katakan bahwa variabel x terikat dalam ekspresi lambda \x.B. Sebuah variabel yang terjadi dalam tetapi tidak terikat pada ekspresi lambda dikatakan bebas. Ruang lingkup \ x. adalah B. Dalam ekspresi lambda \y.x+y, x adalah bebas dan y adalah terikat.

kita mengadopsi konvensi penulisan sebagai berikut:

Kita memperluas kalkulus lambda dengan fungsi biasa dan konstanta sehingga kita memberikan

(\x.((+ x) 3)) untuk mewakili fungsi x + 3

Kita biasanya menurunkan tanda kurung terluar sehingga kita dapat menulis

\x.((+ x) 3) daripada (\x.((+ x) 3)) dan

\x.((+ x) 3) 4 daripada (\x.((+ x) 3) 4)

Fungsi Aplikasi berasosiasi  ke kiri sehingga kita dapat menulis

(+ x 3) daripada ((+ x) 3) dengan kata lain, kita dapat menulis

\x.+ x 3 daripada \x.((+ x) 3)

Tubuh abstraksi lambda meluas sejauh mungkin sehingga kita harus menulis

(\x.+ x 3) 4 daripada \x.+ x 3 4

Ganti tubuh abstraksi lambda dengan notasi infiks konvensional, sehingga kita dapat menulis

(\x.x + 3) 4 daripada (\x.+ x 3) 4

Beberapa parameter ditulis bersama-sama sehingga kita dapat menulis

\xy.x + y daripada \x.\y.x + y

OPERASIONAL DALAM  SIMANTIK

Perhitungan Lambda-Kalkulus IS semantik dengan menulis ulang (mengurangi) ekspresi lambda dari jenis ke normal. Lambda-kalkulus untuk murni, ekspresi lambda dikurangi dengan substitusi. Bahwa, dalam hal dari parameter yang diganti dengan tubuh (copy of) argument yang lambda-kalkulus kami extende aturan berlaku juga untuk pengurangan biasa.

 contohnya,

1. \x.(x2 - 5) 3 f(3) dimana f(x) = x2 - 5

2. 32 - 5 dari pengurangan

3. 9 - 5 daya

4. 4 subtitusi

Bentuk normal secara formal didefinisikan dalam definisi berikut. Definisi: Sebuah ekspresi lambda-dikatakan dalam bentuk normal jika tidak ada beta-redex, sebuah subexpression dari bentuk (\ \ xP T), yang terjadi di dalamnya. Non-terminating perhitungan adalah contoh dari ekspresi yang tidak memiliki bentuk normal. Lambda-ekspresi

(\x.x x) (\x.x x)

tidak memiliki bentuk normal sebagaimana akan kita lihat. Kita mendefinisikan substitusi, B [x: M], untuk menjadi pengganti bebas dari semua kejadian x di B dengan M. Gambar N.2 berisi definisi formal substitusi. Gambar N.2: Substitusi

            s[x:M] = if (s=x) then M else s

            (A B)[x:M] = (A[x:M] B[x:M])

            (x.B)[x:M] = (x.B)

            (y.B)[x:M] = if (z adalah symbol yang tidak bebas antara B / M) kemudian

z.(B[y:z][x:M])

Dimana symbol , M, A dan B ekspresi lambda.

Ekspresi lambda disederhanakan menggunakan beta-reduksi. Beta-reduksi menerapkan abstraksi lambda untuk argumen menghasilkan sebuah instance dari tubuh abstraksi lambda-di mana kejadian (gratis) dari parameter formal dalam tubuh diganti (salinan) argumen. Dengan definisi substitusi pada Gambar N.2 dan definisi formal dari Fugure pengurangan beta N.3, kita memiliki alat yang diperlukan untuk mengurangi ekspresi lambda bentuk normal.

Gambar N.3: Beta-reduksi

(x.B) e ==> B[x:e]

mudah untuk melihat bahwa ekspresi lambda

(\x.x x) (\x.x x)

tidak memiliki bentuk normal karena ketika ekspresi kedua adalah disubstitusikan ke dalam pertama, ekspresi yang dihasilkan identik dengan ekspresi lambda diberikan.

Gambar 2 mendefinisikan semantik operasional kalkulus lambda-dalam hal pengurangan dalam versi beta.

 Gambar N.4: semantik Operasional kalkulus lambda-penerjemah

 ekspresi E mengurangi ke bentuk normal.                                 

Pengurangan dalam  L --> L

pengurangan[s] = s

pengurangan [x.B M] = pengurangan [ B[x:M] ]

pengurangan [L1 L2] = (pengurangan [ L1 ] pengurangan [ L2 ])

dimana

 s adalah simbol dan B, L1, L2, dan M adalah ekspresi lambda

Gambar N.4-operasional semantik menggambarkan transformasi sintaks lambda-ekspresi

Mengingat pengurangan

Orde ekspresi lambda, substitusi dan beta-aturan pengurangan menyediakan peralatan yang diperlukan untuk mengurangi ekspresi lambda untuk bentuk normal tetapi tidak memberi tahu kami apa untuk menerapkan pengurangan ketika lebih dari satu redex tersedia. Teorema berikut ini, karena Curry, menyatakan bahwa jika ekspresi memiliki bentuk normal, maka bentuk normal yang dapat ditemukan dengan pengurangan paling kiri.

Teorema: Jika E memiliki bentuk normal N maka ada pengurangan di sebelah kiri dari E ke N.

Penurunan paling kiri terluar (pengurangan urutan normal) strategi ini disebut pengurangan malas karena tidak pertama mengevaluasi argumen argumen tetapi pengganti langsung ke ekspresi. Pengurangan bersemangat adalah ketika argumen berkurang sebelum substitusi.

 Fungsi ini tegas jika itu akan membutuhkan argumen. Jika suatu fungsi adalah non-ketat, kita mengatakan bahwa itu adalah malas.

parameter passing: dengan nilai, dengan nama, dan evaluasi malas

struktur data terbatas

panggilan oleh kebutuhan

mengalir dan prosesnya terus-menerus

fungsi yang ketat jika dan hanya jika (f 

Rencana mengevaluasi parameter sebelum lewat (menghilangkan kebutuhan untuk mengubah nama) penelaahan atas efektivitas waktu dan ruang.

DETATIONAL SEMANTIK

 Kami memeriksa semantik semantik operasional kalkulus lambda denotational di bagian sebelumnya. Hal ini disebut operasional karena itu adalah "\ dinamis", dia melihat sebuah fungsi sebagai urutan operasi. Lambda-ekspresi dinilai oleh transformasi sintaksis murni tanpa referensi apa istilah "berarti \".

Tujuan dari semantik denotational bahasa adalah untuk memberikan nilai untuk ekspresi masing-masing dalam bahasa. Kita dapat mengekspresikan semantik dari kalkulus lambda sebagai fungsi matematika, ekspresi nilai-nilai Eval. Sebagai contoh,

Eval[+ 3 4] = 7

mendefinisikan nilai dari ekspresi (+ 3 4) 7. Bahkan sesuatu yang lebih diperlukan, dalam kasus nama variabel dan fungsi, fungsi Eval membutuhkan parameter kedua berisi lingkungan AA yang berisi hubungan antara variabel dan nilai-nilai mereka. Beberapa program yang dilingkarkan di beberapa membatalkan dengan runtime error.  diucapkan  ^Untuk mengelola situasi ini, kami memperkenalkan simbol  "bawah \".

Gambar N.5 memberikan semantik denotational untuk lambda-kalkulus.

Gambar N.5: semantik Denotational untuk lambda-kalkulus

Domain Semantic:

D di s

 Fungsi Semanti c:

 Eval di L ->  D

Persamaan simantik

Eval [ s ] = s

            Eval [ (\x.B M) ] = Eval [ B[x:M] ]

            Eval [ (L1 L2) ] = (Eval [ L1 ] Eval [ L2 ])

            Eval [ E ] = _|_

Gambar N.5 memberikan semantik denotational untuk lambda-kalkulus. Gambar N.5: Denotational sewhere s adalah sebuah simbol, B, L1, L2, dan M adalah sebuah ekspresi, B [x: M] adalah substitusi seperti pada Gambar N.2, E adalah sebuah ekspresi yang tidak memiliki bentuk normal, dan _ | _ diucapkan di bawah ini.

Gambar N.5 semantik denotational menggambarkan pemetaan ekspresi lambda untuk nilai-nilai dalam beberapa kalkulus lambda-semantik domain.

Fungsi Rekursif

Kami memperpanjang sintaks lambda-kalkulus untuk memasukkan ekspresi dinamai sebagai berikut: Ekspresi Lambda

L ::= ...| x : L | …

di mana x adalah nama dari ekspresi lambda

Dengan diperkenalkannya ekspresi bernama yang memiliki potensi definisi rekursif dan sintaks yang memungkinkan kami keluar dalam nama-abstraksi lambda dan kemudian merujuk kepada mereka dalam ekspresi lambda. Perhatikan definisi rekursif berikut fungsi faktorial.

FAC : \n.(if (= n 0) 1 (* n (FAC (- n 1))))

yang dengan sugaring sintaksis

FAC : \n.if (n = 0) then 1 else (n * FAC (n – 1))

Kami memperlakukan panggilan rekursif sebagai variabel bebas dan mengganti definisi sebelumnya dengan berikut ini.

FAC : (\fac.(\n.(if (= n 0) (* n (fac (- n 1))))) FAC)

Let

H : \fac.(\n.(if (= n 0) 1 (* n (fac (- n 1)))))

Perhatikan bahwa H adalah tidak rekursif didefinisikan. Sekarang kita dapat mendefinisikan kembali FAC sebagai

FAC : (H FAC)

Definisi ini seperti persamaan matematika. Dikatakan bahwa ketika fungsi h diterapkan pada FAC, FAC mengatakan hasilnya adalah bahwa FAC adalah titik tetap atau titik H. Secara umum, fungsi dapat memiliki lebih dari satu titik tetap. Dalam hal ini titik tetap adalah fungsi matematika faktorial. Secara umum, 'benar' titik tetap ternyata menjadi titik hanya kurang tetap. Hal ini diinginkan untuk memiliki fungsi yang berlaku untuk abstraksi lambda-titik mengembalikan setidaknya tetap abstraksi. Misalkan ada semacam fungsi y, di mana

FAC : Y H

Y adalah disebut titik tetap combinator. Dengan fungsi dan tidak menggunakan definisi rekursi FAC. Dari, fungsi dua definisi dan memiliki properti yang

Y H = H (Y H)

Sebagai contoh, di sini adalah perhitungan dari FAC 1 menggunakan combiner Y.

FAC 1 = (Y H) 1

                 = H (Y H) 1

            = \fac.(\n.(if (= n 0) 1 (* n (fac (- n 1))))) (Y

H) 1

                 = \n.(if (= n 0) 1 (* n((Y H)(- n 1)))) 1

            = if (= 1 0) 1 (* 1 ((Y H)(-11)))

            = (* 1 ((Y H)(-11)))

             (* 1 ((Y H)0))

            = (* 1 (H (Y H) 0))

            ...

            = (* 1 1)

            = 1

fungsi dapat didefinisikan dalam kalkulus lambda

Y : \h.(\x.(h (x x)) \x.(h (x x)))

Ini sangat menarik karena didefinisikan sebagai abstraksi lambda-tanpa menggunakan rekursi. Untuk menunjukkan bahwa ekspresi lambda untuk menentukan hak combinator Y, ini diterapkan untuk H.

(Y H) = (\h.(\x.(h (x x)) \x.(h (x x))) H)

                 = (\x.(H (x x)) \x.(H (x x)))

            = H ( \x.(H (x x))\x.(H (x x)))

                 = H (Y H)

Blok dengan definisi lokal dapat didefinisikan dalam kalkulus lambda. Kami memperkenalkan dua jenis blok, let dan ekspresi letrec. Definisi diperkenalkan dengan ekspresi iteratif memungkinkan:

let n : E in B is an abbreviation for (\n.B) E

di sini adalah contoh menggunakan let-extention

let x : 3 in (* x x)

Let dapat digunakan dimanapun ekspresi lambda-diperbolehkan. Sebagai contoh,

\y. let x : 3 in (* y x)

Itu sama dengan

\y. (* y 3)

Dengan ekspresi letrec yang didefinisikan dalam istilah ekspresi let dan definisi rekursif combinator diperkenalkan dan sederhana:

letrec n : E in B is an abbreviation for let n : Y (\n.E) in B

Definisi let dan letrec ditunjukkan pada Gambar N.6.

Lexical Scope Rules

let n : E in B = (\n.B) E

letrec n : E in B = let n : Y (\n.E) in B

Terjemahan Semantik dan Kombinator

Aturan pengurangan beta / Beta Reduction sulit untuk diimplementasikan. Karena memerlukan substitusi tekstual  dari argumen setiap kemunculan parameter dan memerlukan tidak ada variabel bebas dalam argumen yang harus menjadi terikat. Hal ini menyebabkan studi tentang cara-cara di mana variabel dihilangkan.

Curry, Feys, dan Craig menentukan jumlah kombinator antara mereka sebagai berikut:

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

  K = \x .\y. x

  I = \x.x

  Y = \f. \x.( f(x x)) \x.(f (x x))

Definisi ini mengarah pada aturan transformasi untuk urutan kombinasi. Pengurangan aturan untuk perhitungan SKI diberikan pada Gambar N.7.

Gambar N.7: Aturan pengurangan untuk kalkulus SKI

S f g x --> f x (g x)

K c x --> c

I x --> x

Y e --> e (Y e)

(A B) --> A B

(A B C) --> A B C

Aturan pengurangan memerlukan pengurangan yang dilakukan dari kiri ke kanan. Jika tidak ada S, K, I, atau pengurangan Y yang berlaku, maka tanda kurung dihapus dan pengurangan dilanjutkan.

Kalkulus SKI adalah komputasi yang lengkap, maka dari itu, tiga operasi tersebut cukup untuk melakukan operasi apapun. Hal ini ditunjukkan oleh aturan-aturan dalam Gambar N.8.

Gambar N.8: Terjemahan Semantik untuk Kalkulus Lambda

    Compile [ s ] --> s

    Compile [ (E1 E2)] --> (Compile [ E1] Compile [ E2 ])

    Compile [ \x.E] --> Abstract [ (x, Compile [ E] ) ]

    Abstract [ (x, s) ] --> if (s=x) then I else (K s)

    Abstract [ (x, (E1 E2))] --> ((S Abstract [ (x, E1)] ) Abstract [ (x, E2) ] )

Dimana S adalah simbol

Yang menerjemahkan ekspresi lambda ke bentuk rumus dalam kalkulus SKI

Setiap bahasa pemrograman fungsional dapat diterapkan oleh sebuah mesin yang mengimplementasikan kombinator SKI, bahasa fungsional dapat diubah menjadi ekspresi lambda dan rumus SKI

Fungsi aplikasi ini relatif sulit pada komputer konvensional. Alasan prinsipnya adalah menjaga kompleksitas struktur data yang mendukung akses ke pengidentifikasi yang terikat. Masalah ini sangat parah ketika fungsi tatanan yang lebih tinggi yang diizinkan. Karena formula tidak mengandung pengidentifikasi kalkulus SKI yang terikat, pengurangan aturan dapat diimplementasikan sebagai manipulasi struktur data sederhana. Selanjutnya, aturan pengurangan dapat diterapkan dalam urutan apapun, atau paralel. Jadi mungkin untuk merancang komputer paralel yang banyak (grafik mesin reduksi) yang menjalankan bahasa-bahasa fungsional dengan efisien.

fungsi rekursif dapat didefinisikan dengan operator Y

1.    Optimasi

Perhatikan bahwa ukuran dari kode SKI tumbuh kuadratik dalam jumlah variabel terikat. Gambar N.9.

                                         B = \ x. (\ Y. (\ Z. ((x y) z)))
          C = \ x. (\ Y (\ z ((x z) y)))

dengan aturan pengurangan yang sesuai.
        
                                         B b c -->(( b) c)
          C b c -->(( c) b)

Setelah ini kita dapat menyederhanakan combinators ekspresi diperoleh dengan menerapkan aturan-aturan dalam Gambar N.9.

Gambar N.9: Optimasi untuk kode SKI

                                         S (K e) (K f) -> K (e f)
          S (K e) Saya -> e
          S (K e) f -> (B e) f
          S e (K f) -> (C e) f

Optimasi harus diterapkan dalam urutan yang diberikan.


Sama seperti bahasa mesin (assembler) dapat digunakan untuk pemrograman, logika kombinatorial dapat digunakan sebagai bahasa pemrograman. FP bahasa pemrograman adalah bahasa pemrograman berbasis pada gagasan logika kombinatorial.
 

2.    Skema

Skema, keturunan LISP, didasarkan pada lambda-kalkulus. Meskipun memiliki fitur penting, dalam bagian ini kita mengabaikan fitur-fitur dan berkonsentrasi pada kalkulus lambda-seperti fitur dari Skema. Skema memiliki dua jenis benda, atom dan daftar. Atom yang diwakili oleh string non-kosong karakter. Sebuah daftar diwakili oleh urutan dari atom atau daftar dipisahkan dengan kosong dan tertutup dalam tanda kurung. Fungsi dalam Skema juga diwakili oleh daftar. Ini memfasilitasi penciptaan fungsi yang menciptakan fungsi lainnya. Suatu fungsi dapat dibuat dengan fungsi lain dan kemudian fungsi diterapkan pada daftar argumen. Ini merupakan fitur penting bahasa untuk aplikasi AI.
 

Sintaksis

Sintaks dari Skema ini mirip dengan kalkulus lambda.

                   Skema Sintaks

                                         E dalam Ekspresi
          A dalam Atom (variabel dan konstanta)
          ...
          E:: = A | (E. ..) | (lambda (A. ..) E) | ...

Ekspresi adalah atom yang variabel atau konstanta, daftar panjang sewenang-wenang (yang juga aplikasi fungsi), lambda-abstraksi dari satu atau lebih parameter, dan lain built-in fungsi.

Skema menyediakan sejumlah fungsi yang dibangun di antaranya adalah +, -, *, /, <, <=, =, >=,>, dan tidak. Skema menyediakan untuk ekspresi kondisional dari bentuk (jika E0 E1 E2) dan (jika E0 E1). Di antara konstanta yang disediakan dalam Skema adalah nomor, # f dan daftar kosong () keduanya dihitung sebagai t palsu, dan # dan setiap hal lain selain # f dan () yang dihitung sebagai benar. nihil juga digunakan untuk mewakili daftar kosong.

Definisi

Skema mengimplementasikan definisi dengan sintaks berikut

E:: = ... | (mendefinisikan saya E) | ...

Daftar dengan nihil, kontra, mobil dan cdr

Daftar adalah struktur data dasar dengan nihil repesenting daftar kosong. Diantara dibangun pada fungsi untuk manipulasi daftar yang disediakan dalam Skema yang kontra untuk melampirkan sebuah elemen ke kepala dari sebuah mobil, untuk mengekstraksi daftar elemen pertama dari daftar, dan CDR yang mengembalikan daftar dikurangi elemen pertama.

Gambar N.10: operasi Stack dalam Skema

(Mendefinisikan empty_stack
(Lambda (tumpukan) (jika (null stack)? \ # T \ # f)))

(Mendefinisikan mendorong
(Lambda (tumpukan elemen) (tumpukan elemen kontra)))

(Mendefinisikan pop
(Lambda (tumpukan elemen) (cdr tumpukan)))

(Mendefinisikan atas
(Lambda (tumpukan) (tumpukan mobil)))


Gambar N.10 berisi contoh writtem tumpukan operasi di Skema. Angka tersebut menggambarkan definisi, ekspresi kondisional, null predikat daftar? untuk menguji apakah daftar kosong, dan manipulasi daftar fungsi kontra, mobil, dan CDR.
 

Definisi Lokal

Skema memberikan definisi lokal dengan sintaks berikut

                   Skema Sintaks

                                          ...
          B di Bindings
          ...
                                          E:: = ... | (biarkan B0 E0) | (biarkan * B1 E1) | (letrec B2 E2) | ...
                                          B:: = ((saya E )...)

Definisi membiarkan dilakukan secara independen satu sama lain (binding agunan), nilai-nilai * izinkan dan binding dihitung secara berurutan dan binding letrec yang berlaku sementara nilai sedang dihitung untuk memungkinkan definisi rekursif saling.

3.     ML

4.     Haskell

Berbeda dengan LISP dan Scheme, Haskell merupakan bahasa fungsional. pemrograman modern

N.11: A Contoh Program dalam Haskell

module AStack( Stack, push, pop, top, size ) where

data Stack a = Empty

                                                                       | MkStack a (Stack a)

push :: a -> Stack a -> Stack a

push x s = MkStack x s

size :: Stack a -> Integer

size s = length (stkToLst s) where

                                                                       stkToLst Empty = []

                                                                       stktoLst (MkStack x s) = x:xs where xs =

stkToLst s

pop :: Stack a -> (a, Stack a)

pop (MkStack x s) = (x, case s of r -> i r where i x = x)

top :: Stack a -> a

top (MkStack x s) = x

module Qs where

qs :: [Int] -> [Int]

qs [] = []

qs (a:as) = qs [x | x <- as, x <=a] ++ [a] ++ qs [x | x <- as, x> a]

module Primes where

primes :: [Int]

primes = map head (iterate sieve [2 ..])

sieve :: [Int] -> [Int]

sieve (p:ps) = [x | x <- ps, (x `mod` p)=0]

module Fact where

fact :: Integer -> Integer

fact 0 = 1

fact (n+1) = (n+1)*fact n -- * "Foo"

fact _ = error "Negative argument to factorial"

module Pascal where

pascal :: [[Int]]

pascal = [1] : [[x+y | (x,y) <- zip ([0]++r) (r++[0])] | r <- pascal]

tab :: Int -> ShowS

tab 0 = \x -> x

tab (n+1) = showChar ' ' . tab n

showRow :: [Int] -> ShowS

showRow [] = showChar '\n'

showRow (n:ns) = shows n . showChar ' ' . showRow ns

showTriangle 1 (t:_) = showRow t

showTriangle (n+1) (t:ts) = tab n . showRow t . showTriangle n ts

module Merge where

merge :: [Int] -> [Int] -> [Int]

merge [] x = x

merge x [] = x

merge l1@(a:b) l2@(c:d) = if a < c then a:(merge b l2)

                                                                       else c:(merge l1 d)

half [] = []

half [x] = [x]

half (x:y:z) = x:r where r = half z

sort [] = []

sort [x] = [x]

sort l = merge (sort odds) (sort evens) where

odds = half

evens = half (tail l)

5.    Perspektif Sejarah dan Bacaan Lebih Lanjut

Pada tahun 1930 Alonzo Church mengembangkan kalkulus lambda sebagai alternatif teori dasar matematika dan set Haskell B. Curry conbinatory logika untuk alasan yang sama. Sementara tujuannya adalah tidak terpenuhi, kalkulus lambda dan combinators menangkap sifat formal yang paling umum dari konsep fungsi matematika.

Kalkulus lambda dan combinatory logika adalah model abstrak dari perhitungan setara dengan mesin Turing, fungsi rekursif dan rantai Markov. Tidak seperti memutar mesin yang berurutan di alam, mempertahankan hadir paralelisme implisit dalam ekspresi matematika

Kalkulus lambda adalah pengaruh langsung pada bahasa pemrograman LISP, panggilan dengan parameter nama melewati mekanisme Algol 60 dan substitusi tekstual dilakukan dengan menghasilkan makro.

eksplisit dan penggunaan sistematis kalkulus lambda dalam ilmu komputer mulai pada tahun 1960 oleh Peter Landin, Christopher Strachy dan lain-lain mulai teori formal semantik bahasa disebut semantik denotational. Dana Scott (1969) menemukan model matematika pertama untuk jenis-kalkulus lambda gratis.

Desain komponen perangkat keras baru muncul untuk mendukung eksekusi langsung dari kalkulus lambda dan combinators yang mendukung eksekusi paralel dari program fungsional, menghilangkan beban (sisi-effictive, sinkronisasi, komunikasi) untuk mengontrol programmer parallel

LISP (list processing) dirancang oleh John McCarthy pada tahun 1958. LISP muncul dari kepentingan dalam perhitungan simbolis. Secara khusus, minat di berbagai bidang seperti mesin teorema membuktikan, kecerdasan pemodelan manusia dan pengolahan bahasa alami. Dalam setiap bidang ini, list processing dipandang sebagai prasyarat. LISP dikembangkan sebagai sistem untuk memproses daftar berdasarkan fungsi rekursif. Sumber daya yang diharapkan, kelas fungsi dan pengumpulan sampah. Semua konsep baru saat ini. LISP sengaja aturan pelingkupan dilaksanakan dinamis, tidak statis. Skema adalah inkarnasi modern LISP. Ini adalah bahasa yang relatif kecil dengan aturan lingkup statis, bukan dinamis. LISP diadopsi sebagai bahasa pilihan untuk aplikasi kecerdasan buatan dan masih banyak digunakan dalam komunitas intelijen aritficial.

Haskell merupakan bahasa modern bernama setelah ahli logika Haskell B. Curry dan dirancang oleh sebuah komite dari 15 anggota. Tujuan desain untuk Haskell mengalami bahasa fungsional yang menggabungkan penelitian ideas''Recent all''good pada bahasa fungsional dan cocok untuk pengajaran, penelitian dan aplikasi. Haskell memiliki instalasi memberatkan yang dibangun ke dalam sistem tipe polimorfis, e / s murni fungsional, matriks, data abstraksi dan menyembunyikan informasi.

Bahasa pemrograman fungsional disajikan dalam urutan mesin pemrograman virtuales.bahasa fungsional dapat mengakibatkan kalkulus lambda, kalkulus lambda dan combinatory logika logika kombinasional dalam kode untuk mesin penurunan grafik. Ini semua mesin virtual.

model dari kalkulus lambda

Sejarah (McCarthy60) untuk diakses pengenalan pemrograman fungsional, lambda-kalkulus, combinators dan pelaksanaan mesin tampilan grafik Revesz (1988). Untuk Backus Turing Award kertas 'dalam pemrograman fungsional melihat \ mengutip {} Backus78. Sebuah referensi lengkap untuk lambda-kalkulus \ mengutip {} Bare84. Untuk semua Anda pernah ingin tahu tentang logika combinatory melihat \ mengutip {CF68, CHS72, HS86}. Untuk pengantar pemrograman fungsional melihat Henderson (1980), BirdWad88, MLennan90. Untuk intoduction untuk LISP melihat \ mengutip {} dan untuk LISP McCarthy65 umum untuk melihat \ mengutip {} Steele84. Untuk pengenalan skema melihat \ mengutip {} AbSus85. Haskell Sehubungan dengan bahasa pemrograman lambda-kalkulus melihat \ mengutip {} Landin66. Untuk implementasi bahasa pemrograman fungsional melihat Henderson (1980) dan Peyton-Jones (1987).

Henderson, Peter (1980) Fungsional Pemrograman: Aplikasi dan Implementasi Prentice-Hall International. Peyton-Jones, Simon L (1987) Implementasi Bahasa Pemrograman Fungsional Prentice-Hall International. Revesz, GE (1988) Lambda-kalkulus, combinators, dan Fungsional Pemrograman Cambridge University Press.

sumber: cai.elearning.gunadarma.ac.id/webbasedmedia