1

Bab 5

Spesifikasi Pengaturcaraan Fungsian

2

Spesifikasi Pengaturcaraan Fungsian Pengaturcaraan fungsian popular dalam implementasi

kecerdasan buatan, pembuktian matematik, logik dan aplikasi pemperosesan selari

Kelebihan pengaturcaraan fungsian berbanding pengaturcaraan imperatif: Penggunaan konsep fungsi untuk menggambarkan aturcara dan data

Kesan sampingan (sede effects) yang terhad

Pengurusan dan penggunaan ingatan secara automatik

Kelemahan utama pengaturcaran fungsian; perlaksanaannya yang tidak efisen kerana ia direkabentuk untuk diterjemah, dan bukan dikompil

3

Spesifikasi Pengaturcaraan Fungsian Pengaturcaraan fungsian mempunyai sifat-sifat berikut:

Lazy function evaluation – mekanisma yang mengurangkan proses penilaian fungsi yang tidak penting. Ini dilakukan menggunakan strategi berikut:

Menangguhkan penilaian suatu fungsi sehingga diperlukan

Mengurangkan penilaian semula fungsi yang sama lebih dari sekali

First-class objects – fungsi-fungsi dianggap sama seperti objek-objek lain suatu fungsi boleh menjadi argumen kepada suatu fungsi lain atau sebagai nilai bagi suatu pembolehubah

Kesemua aturcara dan prosedur adalah fungsi

Kurang penggunaan gelung dan iteratif -gelung diganti dengan panggilan rekursif

4

Spesifikasi Pengaturcaraan Fungsian Kurang penggunaan pembolehubah dan umpukan – pembolehubah

hanya digunakan sebagai nama bagi suatu nilai, dan umpukan sebagai operasi dalam pengaturcaraan fungsian yang tulin, tiada pemolehubah, hanya pemalar, parameter, dan nilai

Referencial transparency – nilai suatu fungsi haya bergantug kepada nilai parameter, bukan pengiraan sebelumnya, jujukan langkah penilaian, atau langkah perlaksanaan yang membawa keapda panggilan fungsi

Persekitaran ingatan dinamik – allocation dan deallocation ingatan berlaku semasa perlaksanaan aturcara pengurursan ingatan secara automatik yang boleh dikelaskan kepada dua kategori:

Maintaining free space

Reclaimation of storage

5

Spesifikasi Pengaturcaraan Fungsian Garbage collection – juga dipanggil ‘reclaimation of storage’

suatu proses yng menjejak storan yang tidak dapat dicapai dan membenarkannya untuk di’allocate’ semula. Garbage collector dipanggil secara automatik apabila tiada lagi ruang kosong dalam storan

Bebas dari kesan sampingan – keupayaan untuk memanggil fungsi tanpa menghasilkan ‘kesan sampingan’, iaitu tanpa menukar keadaan dalaman suatu pengiraan. Ini adalaha kerana pengiraan dilakukan dengan proses penilaian ungkapan, bukan dengan pengumpukan nilai kepada suatu pembolehubah

6

Spesifikasi Pengaturcaraan Fungsian Kebanyakan bahasa pengaturcaraan fungsian masih menggunakan

pembolehubah dan proses umpukan menjadikan bahasa tersebut

bukan bahasa fungsian yang tulin

Secara amnya, kesemua bahasa pengaturcaraan boleh dianggap sebagai

variasi sintaks kalkulus lambda

Operasi utama dalam bahasa fungsian adalah penciptaan fungsi – yang

sebenarnya adalah pengabstarakan lambda dan aplikasi dua operasi

asas kalkulus lambda

Matlamat utama suatu ungkapan lambda dimanipulasi adalah untuk

menukarkannya ke dalam bentuk yang lebih mudah (reduction)

bentuk ini dianggap sebagai nilai suatu ungkapan

7

5.1. Kalkulus Lambda Suatu kaedah matematik untuk mengungkapkan pengiraan

menggunakan fungsi konsep asas dalam pengaturcaraan fungsian

Lambda adalah mirip kepada ungkapan universal yang bermaksud

‘untuk semua’

Bentuk umum ungkapan lambda, yang dikenali sebagai fungsi lambda

ialah:

id1, id2, . . . , idn . ungkapan

Contohnya:

x . x * x

Ungkapan lambda ini boleh diaplikasi seperti berikut:

{x. x * x } (2)

yang mana hasil ungkapan ini boleh diperolehi dengan menggantikan

parameter dengan nilai 2 , maka nilai adalah 4

8

5.1. Kalkulus Lambda Secara umum, ungkapan lambda boleh wujud dalam

bentuk berikut: Suatu pencam atau atom, yang mana atom mewakili

pemalar atau fungsi Suatu peniskalaan (abstraction), yang mewakili suatu

fungsi dengan argumen tunggal seperti x. ungkapan yang mana x adalah pencam dan ungkapan adalah ungkapan

lambda Suatu aplikasi, yang mewakili lebih dari satu ungkapan,

seperti x. ungkapan1 ungkapan2,

yang mana x adalah pencam, dan ungkapan1 dan ungkapan2 adalah ungkapan lambda

9

5.1. Kalkulus Lambda

Contoh fungsi lambda: {n. m. n2 + m} (3,4) = {m. 32 + m}(4) = 32 + 4 = 13 {m. n. n2 + m} (3,4) = {n. n2 + 3}(4) = 42 + 3 = 19 {{{a, b. a + b}3}4} = {b. 3 + b} 4 = 3 + 4 = 7 {x. y. yx}(a, b) = {y. ya}(b) = ba

10

5.2. Pembentukan ungkapan lambda yang lebih mudah (Reduction)

Terdapat 4 petua untuk manipulasi nilai, pembolehubah, dan fungsi dalam ungkapan lambda Alpha-conversion – merujuk kepada penukaran nama

dalam ungkapan lambda :

x. ungkapan y. ungkapan[x y]

yang mana y tidak wujud pada asalnya dalam ungkapan tersebut.

Contoh:

{w. (y. yx) w} x. (y. yz) x

11

5.2. Pembentukan ungkapan lambda yang lebih mudah (Reduction)

Beta-conversion – merujuk kepada penukaran dan peniskalan beta

x. ungkapan1 ungkapan2 b ungkapan1[x ungkapan2]

Contoh:

{x. x + 1} 5 (5 + 1) = 6

Eta-conversion – merujuk kepada penghapusan peniskalaan lambda yang redundan

{x. ungkapan} x ungkapan

Contoh:

{x. (sqr 5)} (x) (sqr 5) = 25

12

5.2. Pembentukan ungkapan lambda yang lebih mudah (Reduction)

Gamma-conversion – dikaitkan dengan nilai dan fungsi yang telah ditakrifkan sebelumnya

{function x y} function(x, y)

Contoh;

(add 5 3) add(5, 3) = 8

13

5.3. Program-forming Operations

Terdapat beberapa operasi pembentukan-aturcara yang menjadi asas operasi dalam pengaturcaraan fungsian Gabungan (composition) Pembinaan (construction) Selit (selit) Apply to all Condition

14

5.3.1. Gabunagn

Gabungan, yang menggunakan simbol o mempunyai sintaks seperti berikut:

(f o g) : X = f : (g : X)

Contoh:f(x) = x + 5 dan g(x) = x + 4

Maka satu bentuk fungsi komposisi f dan g boleh diperolehi:h(x) = f(g(x)) atau

h(x) = (x + 4) + 5 = x + 9

15

5.3.2. Pembinaan

Pembinaan, yang menggunakan simbol [ ] mempunyai sintaks seperti berikut:

[ f1, f2, . . . , fn] : X = < f1:X, f2:X, . . . , fn:X >

Contoh:[Maximum, Minimum, Average] : <1, 2, 3, 4, 5>

Hasilnya adalah:<5, 1, 3>

16

5.3.3. Penyelitan

Penyelitan, yang menggunakan simbol / mempunyai sintaks seperti berikut:

/ f: <X1, X2, . . . , Xn> = f : < X1, / f :< X2, . . . , fn:X >>

/f : dihuraikan kepada:Jika x adalah X1, maka X1Jika tidak, jika x adalah jujukan <X1, X2, . . . , Xn> dan n >= 2

maka f : < X1, / f :< X2, . . . , fn:X >>

Contoh:/+:< 1, 2, 3, 4, 5 >= +:<1, +:<2, +:<3, +:<4, +:<5>>>>>

Hasilnya adalah:15

17

5.3.4. Aplikasi kepada Semua

Aplikasi_kepada_semua, yang menggunakan simbol mempunyai sintaks seperti berikut:

f: < X1, X2, . . . , Xn = < f:X1, f:X2, . . . , f:Xn>

Huraiannya: f: = jika x adalah nil, maka nilJika tidak, jika x adalah jujukan <X1, X2, . . . , Xn>

Maka <f:X1, f:X2, . . . , f:Xn>

Contoh :+:< <2, 3>,<4, 5>,<6, 2> >

Hasilnya adalah:<+:<2, 3>, +:<4, 5>, +:<6, 2>> = <5, 9, 8>

18

5.3.5. Keadaan Bersyarat Keadaan bersyarat, yang menggunakan IF yang menggunakan

3 argumen, mengembalikan argumen yang kedua sekiranya argumen pertama BENAR, dan mengembalikan argumen ketiga sekiranya argumen pertama PALSU

Sintaks:(IF fungsi1 fungsi2 fungsi3) : x =If fungsi1:x = T (benar)

maka fungsi2:xjika tidak fungsi3:x

Contoh:(IF FIRST:<2,3,5> TAIL:<2,3,5> LAST:<2,3,5>):2

Hasilnya adalah:<3,5>