>>>>> "VST" == Vehbi Sinan Tunalioglu <[EMAIL PROTECTED]> writes:
>>>>> "BM" == Bulent Murtezaoglu <[EMAIL PROTECTED]> writes:
>>>>> "VST" == Vehbi Sinan Tunalioglu <[EMAIL PROTECTED]> writes:
VST> Ote yandan bunlar bana Regular Expression ve Turing Machine
VST> arasindaki kullanim farkini merak ettirdi. Computational
VST> complexity acisindan degil tabii ki... Ama az once gordugumuz
VST> gibi, regex yerine, bu tarz bir kod kullaninca (Turing
VST> Machine equivalent sanirim) daha az CPU cycle ve CONS ile
VST> isimizi halledebiliyoruz. Ne dersiniz?
BM> Hmm. Yok. Bunu belki biraz farkli ifade etmek lazim
BM> manasinin acik olmasi icin. Ben anlamadim bu paragrafi
BM> mesela.
VST> Evet, pek acik degil. Hatta biraz da hatali belirtmisim.
VST> Aciklayayim: Regular Expressionlar, Turing Machine'den cok
VST> daha kisitli dillerdir. Bu haliyle "finite state automata"
VST> ile islenebilirler. Yani cok daha az maliyetli ve performansi
VST> yuksek cihazlar ile... Ancak, diyorum ki, Turing Machine
VST> diyerek betimleyebilecegimiz programlarla, herhangi bir regex
VST> `pattern'ini bir `finite state automata'dan daha verimli bir
VST> sekilde test edebilir miyiz? Bizim buradaki ornegimizi ele
VST> alacak olursak, bildigim kadariyla, regex girdinin tamamini
VST> okumadan karar vermiyor. Ornek:
"Turing makinasi" denen soyut makinadan bahsettigimizde ve Turing
makinasinin misal elimizdeki bilgisayara denk oldugunu düsünürsek
ve sonlu durum makinasi dedigimiz seyin de aslinda bir Turing
makinasi üzerinde calisan bir sey oldugunu düsünürsek o zaman
Turing makinasi, sonlu durum makinasindan daha etkindir demek
anlamli mi?
VST> Regex: ab.*
VST> Bu ornekte "abfoobarfoobarfoobar" girdisinin tamami okunmadan
VST> karar verilmiyor (mu acaba?). Burada dikkate deger nokta,
VST> regex makineleri (finite state automatonlarin) bilgisayar
VST> ortaminda aslinda Turing Machine ile (yani bir bilgisayar
VST> programlama dilinde yazilmis programlarla) simule edildikleri
VST> icin `finite state automaton'un basitliginden ve dolayisi ile
VST> hizindan mahrum kalmamiz.
Sonlu durum makinasini, Turing makinasina denk olmayan bir
bilgisayarda islemekten mi bahsediyorsun?
VST> Ayni `pattern' icin bir Turing Machine (kisacasi bir
VST> algoritma) ile sunu da diyebilirdik:
VST> TM: ilk iki harf sirasiyla a ve b'ye esitse KABUL, yoksa RED.
VST> Burada anlatmaya ve anlamaya calistigim seyi bircok sekilde
VST> ifade etmem mumkun. Bir kez de su sekilde bir soru kuruyorum:
VST> Herhangi bir regex kutuphanesi de, kendi kendimize
VST> uyguladigimiz bir algoritma da su islemi yapmiyor mu:
VST> 0. girdi bittiyse kabul et, aksi takdirde, 1. girdinin
VST> siradaki harfini register-1'e al, 2. kiyaslayacagin
VST> `pattern'deki siradaki harfi register-2'ye al, 3. iki
VST> registeri kiyasla, ayniysa bir sonraki harfe gec ve bu
VST> proseduru uygulamaya devam et, degilse REDDET.
Evet o sekilde islem yapiyor diye biliyorum, daha dogrusu ona
denk gelecek sonlu durum makinasini kuruyor (biri beni
düzeltsin sacmaliyorsam).
VST> Burada dikkati cekmek istedigim olay, kiyaslama olayi.
VST> Sonuc: Girdileri bir patternle kiyaslamak zaten hizli bir
VST> islem degil.
Evet, statik yani sabit karakter dizisi parcasini daha
büyük bir dizi icinde aramaya kiyasla daha yavas.
VST>Regex kutuphanelerinin yazilmasinin sebebi, bu
VST> kiyaslamayi hizli yapmak icin degilmis de hizli kod yazmak
VST> icinmis gibime geliyor. Halbuki basit ama regexe kiyasla
VST> uygulamasi daha uzun algoritmalarla is halletmek cok daha
VST> hizli sonuclar veriyor. Bu genelleme dogru olabilir mi?
Basitlik... Ne kadar basit? Yukarida gercekten basit örnek verdin,
biliyorsun ki cok cok acayip patternler aradigimiz oluyor duruma
göre. O zaman elle yazacagin algoritma optimize bir regex kütüphanesinin
üretecegi sonlu durum makinasina kiyasla daha mi iyi olacak?
Bu bir tartisma konusu.
Öte yandan, DSL yani "domain specific language"in gücü buradan
cikmiyor mu, kendin prosedürel yöntemle imperatif olarak
bir seyler yazdin, sonra o örüntüde (pattern'de) bir degisiklik
yapman gerekti, ne olacak, tekrar git koda müdahale et! Koda
müdahale kötü, veriye müdahale iyi diyorum. Bkz. RDBMS modeli.
Arka planda karmasik kodlar var, kapali kutu. Sen veri ile
ugrasir onu minciklayip durursun. SQL sana bir DSL gibi
arayüz saglar. Hayat sürer gider...
BM> Kod aciksa gecin buraya bence, topluca elleyelim bakalim ne
BM> hale gelecek. Iyi bir egzersiz olur.
VST> Agabey, izin ver, kodun oldugu dosyayi temizleyeyip,
VST> aciklamalariyla beraber bahsettigim fonksiyonlari
VST> gondereyim. Zira, gereksiz ve konumuzla ilgisiz bir cok
VST> fonksiyon ile kafanizi sisirmek istemem.
CVS... DARCS... yapsak ortaya bir karisik, sonra Common Lisp
SNA modülünün CVS ya da DARCS modülü islevselligi olsa, commitleri
filan analiz edip SNA yapsa :)
Neyse saka bir yana, hakikaten bir kod deposu mevzusuna girsek
ve o sekilde ortaklasa Lisp kodlasak, Emacs icinden kod deposuna
baglansak, o tadi yakalasak, güzel bir deneyim olmaz mi
diye düsünüyorum ben hala...
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
_______________________________________________
cs-lisp mailing list
cs-lisp@cs.bilgi.edu.tr
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
