Di Erlang From 99 Lisp Problems terdapat contoh dasar-dasar kode Erlang, namun tidak ada pembahasan bagaimana cara kerja dari kode-kode tersebut. Pada post ini saya akan membahas problem 5 dan 6. Problem 1 sampai dengan 4 bisa dibaca pada tulisan-tulisan sebelumnya termasuk simbol-simbol yang tidak saya bahas di sini (seperti [H|T], [_|T], dsb). Problem-problem yang lain akan saya bahas di lain waktu.
Problem 5.a. Reverse List
rev([]) -> [];
rev([H|T]) -> rev(T)++[H].
Input list adalah [a,b,c,d]. Program dijalankan melalui shell dengan perintah: nama_modul:rev([a,b,c,d]). Kali ini diperkenalkan append operator: ++. Contoh penggabungan 2 list menggunakan ++ adalah [1,2] ++ [3,4] = [1,2,3,4]. Cara kerja program di atas secara berurutan adalah sebagai berikut:
Catatan: Nomor berhuruf ‘a’ menggunakan fungsi rev([]) -> [], sedangkan nomor berhuruf ‘b’ menggunakan fungsi rev([H|T]) -> rev(T)++[H].
1.a. Tidak digunakan karena list tidak kosong.
1.b. rev(a,b,c,d) -> rev(b,c,d) ++ [a]
2.a. Tidak digunakan karena list tidak kosong.
2.b. rev(b,c,d) -> rev(c,d) ++ [b] ++ [a].
3.a. Tidak digunakan karena list tidak kosong.
3.b. rev(c,d) -> rev(d) ++ [c] ++ [b,a].
4.a. Tidak digunakan karena list tidak kosong.
4.b. rev(d) -> rev([]) ++ [d] ++ [c,b,a].
5.a. rev([]) -> [] ++ [d,c,b,a] -> [d,c,b,a].
5.b. Tidak digunakan karena list kosong.
Sisi kanan yang berhuruf tebal dan berwarna maroon adalah hasil sesungguhnya dari sisi kiri, sedangkan sisanya adalah penggabungan dari hasil sebelumnya.
Problem 5.b. Reverse with Tail Rec
Program ini mempunyai hasil yang sama dengan problem 5.a., hanya melalui pendekatan yang berbeda.
revtail(L) -> revt(L,[]).
revt([],L) -> L;
revt([H|T], L) -> revt(T, [H|L]).
revtail(L) akan memanggil fungsi revt(L,[]). Jadi, yang perlu dibahas adalah fungsi revt/2. Input list adalah [a,b,c,d]. Program dijalankan melalui shell dengan perintah: nama_modul:revtail([a,b,c,d]). Cara kerja program di atas secara berurutan adalah sebagai berikut:
Catatan: Nomor berhuruf ‘a’ menggunakan fungsi revt([],L) -> L, sedangkan nomor berhuruf ‘b’ menggunakan fungsi revt([H|T], L) -> revt(T, [H|L]).
1.a. Tidak cocok. revt([],L) minta argumen 1 kosong,
sedangkan argumen 1 dari revt(L,[]) tidak kosong.
1.b. revt([a,b,c,d], []) -> revt([b,c,d], [a]).
2.a. Lihat alasan 1.a.
2.b. revt([b,c,d], [a]) -> revt([c,d], [b,a]).
3.a. Lihat alasan 1.a.
3.b. revt([c,d], [b,a]) -> revt([d], [c,b,a]).
4.a. Lihat alasan 1.a.
4.b. revt([d], [c,b,a]) -> revt([], [d,c,b,a]).
5.a. revt([], [d,c,b,a]) -> [d,c,b,a].
5.b. Tidak cocok.
Problem 6. Is Palindrome
Program ini berfungsi untuk menguji bila sebuah list memiliki urutan yang sama baik dibaca dari depan maupun dari belakang.
ispalin(L) -> L =:= revtail(L).
Kali ini diperkenalkan operator =:= yang berguna untuk menguji keidentikan (test of identical).
Program ini memanggil revtail/1 yang telah saya bahas di problem 5.b. yang berfungsi untuk membalik sebuah list. Program dijalankan melalui shell dengan perintah: nama_modul:ispalin(L). dimana L adalah sebuah list. Cara kerja program di atas secara berurutan adalah sebagai berikut dan kali ini saya menggunakan 2 input sebagai perbandingan.
Input = [a,b,c,d] :
ispalin([a,b,c,d]) -> [a,b,c,d] =:= [d,c,b,a] -> false;
Input = [a,b,b,a] :
ispalin([a,b,b,a]) -> [a,b,b,a] =:= [a,b,b,a] -> true;
Sebagai bonus, mari kita lihat operator-operator dalam Erlang beserta artinya:
Operator: Artinya:
X > Y X lebih besar dari Y.
X < Y X lebih kecil dari Y.
X =< Y X sama dengan atau lebih kecil dari Y.
X >= Y X lebih besar dari atau sama dengan Y.
X == Y X sama dengan Y.
X /= Y X tidak sama dengan Y.
X =:= Y X identik dengan Y.
X =/= Y X tidak identik dengan Y.
Operator =:= mendapat perhatian khusus di sini. Operator =:= mirip dengan == pada bahasa C dan Java, sedangkan programer Delphi akan menggunakan operator =. Erlang memiliki operator ==, tapi hanya digunakan untuk membandingkan antara nilai float dan integer. Bila ada kode Erlang yang menggunakan == maka harus dicurigai dan diperiksa ulang, bisa jadi tidak menghasilkan error selama tidak melibatkan float, tetapi hampir 99% kode Erlang cenderung menggunakan =:=.
Maret 18, 2009 pukul 3:11 pm
Tambahan info Van, walaupun barangkali Ivan juga sudah tahu bahwa untuk reverse, versi 5.b. lebih efisien daripada versi 5.a. Ada dua faktor yang mempengaruhi, yang pertama karena penggunaan operator ++ di versi 5.a, yang kedua karena tail recursion yang dipakai di versi 5.b.
Yang pertama ini kata Joe Armstrong yang bikin bahasa Erlang :
Untuk menambahkan satu persatu elemen, lebih baik pakai seperti yang di 5.b dari [List] -> [H|List] di append satu persatu ke kepala dari list, baru belakangan di reverse kalau perlu. Persisnya inefficient kenapa, mungkin karena operasi ++ ini butuh mengcopy list di kiri dan kanan operator sementara menambahkan di kepala list tidak, kalau secara internal list nya itu sebenarnya diimplementasikan sebagai linked list, operasi menambah kepala list ini jauh lebih efisien.
Versi tail recursion lebih efisien karena setelah sampai ke tail case, sampai ke buntut/step 5.a dari penjelasan Ivan untuk code 5.b,, program Erlang ini tidak perlu melihat ke stack/langkah sebelumya lagi. Kerja program ini sudah selesai, karena hasilnya sudah tersedia ([d,c,b,a])
Sementara untuk versi pertama, yang terjadi sebenarnya adalah :
0 rev(a,b,c,d)
1.a rev(b,c,d) ++ [a]
2.a rev(c,d) ++ [b]
3.a rev(d) ++ [c]
4. [] ++ [d]
3.b [d] ++ [c]
2.b [d,c] ++ [b]
1.b [d,c,b] ++ [a]
0 [d,c,b,a]
Yang dikerjakan oleh compiler selalu lebih dulu ke pemanggilan fungsi rekursif yang berikutnya, Apa yang ada di sebelah kanan ++, di simpan dulu di stack, dan ditambahkan belakangan setelah fungsi rekursif itu ketemu base case/kasus dasar.
Di versi yang bukan tail recursive ini, ada step kembali, mentraverse back ke stack untuk menggabung kerja yang belum selesai, 1.a masih harus mengingat bahwa [a] harus ditambahkan setelah 2.a selesai, 2.a harus menambahkan [b] setelah 3.a selesai dst.
Sementara di tail recursion, begitu sampai langkah terakhir, kita langsung dapat hasilnya, tanpa harus melakukan operasi tambahan.
Coba saja di timing, reverse kedua versi ini, dan dibandingkan lagi dengan list:reverse built in library erlang kalau penasaran
.
Ok, good luck lagi, semoga tetep semangat belajar Erlang, kali-kali saya juga jadi belajar lagi
.
Maret 19, 2009 pukul 11:28 am
@wongiseng:
Blas.. bener-bener gak ngerti kalo cara kerja 5.a. seperti uraian sampean. Ada yang kelewatan kali waktu baca bukunya joe. Aku lagi baca bukunya joe dan masih mondar-mandir di bab 11. Belum sempat nerusin lagi gara-gara kejar setoran.
…Ok, good luck lagi, semoga tetep semangat belajar Erlang, kali-kali saya juga jadi belajar lagi…
Wah, apa benar-benar pernah pake Erlang untuk produksi? Pokoke, kalau sampean mau kasih komen terus aku tambah semangat belajarnya. Ditunggu blog tentang Erlang-nya.
Maret 19, 2009 pukul 3:18 pm
Belum pernah pakai Erlang untuk produksi
Dan latihan 99 soal dari lisp ini sebenarnya baru membantu dasar-dasar Erlang sekuensial, jadi pada dasarnya ini baru belajar pemrograman fungsional. Sementara untuk produksi, masih jauh ceritanya, butuh belajar Erlang untuk concurrent programming, Erlang OTP, etc.
Rasanya saya iseng belajar Erlang dulu gara-gara membuka sourcenya Disco dan pengen mengerti apa yang terjadi disana. Wah kalau blog saya rasanya suka bosan dan tidak konsisten, tapi kalau sekedar mengomentari kerjaan orang masih bisa
. he..he..he..
Lumayan ini kalo bisa berlanjut terus sampai ke pemrograman parallelnya siapa tau bisa jadi buku pengantar Erlang dalam bahasa indonesia, kita lihat saja nanti
.