LISP

LISP

Bahasa pemrograman LISP adalah bahasa pemrograman yang mengikuti kaidah pada Algoritma Euclidean. Bahasa pemrograman ini menggunakan struktur data sederhana yang disebut sebagai list, bersama dengan operator-operator sederhana dan notasi fungsi. Dengan adanya struktur list tersebut, struktur algoritma dalam bahasa pemrograman LISP dapat direpresentasikan dalambentuk pohon (tree).

Struktur Data dalam Pemrograman LISP

Struktur pemrograman LISP terdiri kode-kode dan data yang membentuk suatu ekspresi. Ekspresi ini dapat berupa sebuah atom, yaitu deretan satu atau beberapa karakter, atau sebuah list yang terdiri dari beberapa ekspresi dan boleh kosong. Di bawah ini beberapa contoh ekspresi dalam LISP :

aaa

()

(aaa)

(abc def)

(a b (c) d)

LISP bekerja dengan menempatkan sebuah ekspresi sebagai operator di awal fungsi, dan diikuti oleh argumen-argumen atau operand-operand di belakangnya. Secara umum direpresentasikan sebagai berikut :

(operator operand1 operand2 operand3 ...)

Operand yang dioperasikan dapat berupa sebuah list yang di dalamnya terdapat sebuah fungsi lain. Apabila kita wakilkan operator dengan X dan operand dengan bilangan bulat maka bentuk diatas dapat menjadi sebagai berikut :

(X 1 2 3 ...)

Dimana 1 mengandung (X 4 5 6 ...) dan memberikan bentuk keseluruhan (X (X 4 5 6 ...) 2 3 ...). Ini merupakan konsep yang sama dengan operasi dalam Algoritma Euclidean, sederhana tapi sangat efisien untuk digunakan.

Algoritma Euclidean dalam LISP

Berikut ini adalah realisasi Algoritma Euclidean

dalam notasi pseudo-code [1]:

procedure Euclidean (input m, n : integer, output PBB

: integer)

{

Mencari PBB (m, n) dengan syarat m dan n bilangan

tak negatif dan m ≥ n

Masukan : m dan n, m ≥ n, dan m, n ≥ 0

}

Deklarasi

r : integer

Algoritma

while n ≠ 0 do

r ← m mod n

m ← n

n ← r

endwhile

{

n = 0, maka PBB (m, n) = m

}

PBB ← m

Untuk lebih jelasnya, berikut ini adalah contoh aplikasi algoritma tersebut. Kita berikan masukan untuk algoritma tersebut bilangan integer 50 dan 7.

Maka hasilnya adalah sebagai berikut :

m ← 50

n ← 7

n ≠ 0

r ← 50 mod 7 = 1

m ← 7

n ← 1

n ≠ 0

r ← 7 mod 1 = 0

m ← 1

n ← 0

n = 0

stop

PBB = m

Aplikasi dari Algoritma Euclidean ini dapat kita lihat ketika kita memroses sebuah fungsi dalam LISP dimana operand yang ada mengandung fungsi lain yang harus dioperasikan terlebih dahulu. Kita akan melihat contoh kasusnya pada operasi aritmatika

dengan input berikut :

(+ (- 9 7) (* 1 8))

Struktur Data Tree dalam LISP

Secara umum, bentuk sebuah fungsi dalam LISP adalah sebuah list berisi operand-operand berupa ekspresi, dan kesemua operand tersebut berpusat pada operator yang diletakkan di awal list tersebut. Karena semua operand dioperasikan bergantung pada operator yang ada, maka kita dapat mengandaikan sebuah hubungan subordinasi antara operator dan operand dalam suatu fungsi, dimana operator akan menempati posisi yang lebih tinggi (menjadi “parent”), sedangkan operand menempati posisi yang lebih rendah (menjadi “children”).

LISP menyimpan bentuk data berupa list sebagai bagian dari sebuah pohon dalam komputer dengan setiap elemennya berisi sebuah address dan decrement. Sebuah elemen dalam list dapat kita representasikan sebagai kotak yang mengandung dua elemen tersebut.

Sebuah list dapat diekspresikan dengan menggunakan sebuah pointer yang mengacu pada car (elemen pertama) dari ekspresi list tersebut, dan memberikan pointer yang mengacu pada cdr (elemen sisanya) dari list tersebut. Sebuah list juga dapat mengandung subekspresisubekspresi

yang sama, misalnya ((M .N ) X (M . N).

Dengan hubungan tersebut, sebuah list tidak perlu didefinisikan dua kali. Apabilaterdapat list yang identik dengan list yang telah didefinisikan, maka untuk memanggil list tersebut cukup dengan mengacu kepada pointer tempat list tersebut berada. Sebuah list juga dapat berupa list sirkuler. List seperti ini tidak umum digunakan, tetapi bisa muncul sebagai hasil dari operasi tertentu. Beberapa keuntungan menggunakan struktur data tree seperti ini antara lain :

1. Dengan menggunakan metode susunan tree seperti ini, maka ukuran dan jumlah ekspresi yang akan ditangani oleh program tidak perlu ditentukan dari awal. Struktur data tree ini memungkinkan operasi dengan ekspreseiekspresi yang terus membesar.

2. Register yang sudah selesai digunakan dapat langsung dikosongkan, sehingga dapat menghemat memori yang terpakai saat menjalankan program. Apabila struktur data disimpan secara linier, maka akan sulit untuk ditentukan kapan register yang dipakai di dalam fungsi dapat dikembalikan untuk dipakai dalam proses-proses lain.

3. Sebuah ekspresi yang menjadi subekspresi dari ekspresi lainnya hanya perlu

dialokasikan sekali saja.

Salah satu kekuatan dalam bahasa pemrograman LISP adalah kemampuan untuk menerima definisi fungsi yang menggunakan fungsi dari dirinya sendiri. Fungsi seperti ini disebut fungsi rekursif. Hal seperti ini bisa dilakukan dengan memanggil nama atau label dari fungsi tersebut (apabila telah didefinisikan sebelumnya) di dalam fungsi itu sendiri, atau dengan cara tidak langsung, menggunakan definisi fungsi berantai yang akan berujung pada fungsi-fungsi yang asli. Fungsi ini mengikuti kaidah Algoritma Euclidean dimana fungsi tersebut akan mengulangi dirinya sendiri terhadap hasil operasinya apabila hasil yang diinginkan belum terpenuhi. Penggunaan fungsi rekursif ini sangat efisien, karena kita tidak perlu mendefinisikan fungsi baru untuk menjalankan proses yang sama berulangkali. Dengan demikian proses coding dapat dipercepat dan memori yang diperlukan untuk menyimpan program dapat dihemat.

Salah satu contoh penggunaan fungsi rekursif ada pada fungsi pencarian/search. Berikut ini contoh fungsi search sederhana sebuah atom dalam sebuah list menggunakan fungsi car dan cdr dalam LISP. Fungsi car adalah fungsi yang akan mengembalikan elemen pertama dari suatu list. Elemen pertama tersebut adalah ekspresi yang berupa atom ataupun list. Sedangkan fungsi cdr adalah kebalikan dari fungsi car. Fungsi cdr akan mengembalikan nilai suatu list kecuali elemen pertamanya. Fungsi search dalam notasi pseudo-code adalah sebagai berikut.

function search (input x : list, y : atom output :

boolean)

while search ← false do

car x

if car x = y then

true

{

Mengembalikan nilai true apabila nilai y

yang dicari terdapat dalam car x

}

else

search cdr x

{

Melakukan search terhadap elemen sisanya

apabila y belum didapati

}

Fungsi search di atas akan mencocokkan atom pertama yang ditemukan dalam list yang dioperasikan dengan atom y yang dicari. Apabila atom y tersebut sama dengan elemen pertama dari list, maka fungsi akan mengembalikan nilai true. Sedangkan apabila atom y belum ditemukan, maka fungsi akan mencari di dalam sisa dari list tersebut setelah diambil atom pertamanya pada operasi sebelumnya.