>>>>> "ES" == Emre Sevinc <[EMAIL PROTECTED]> writes:
>>>>> "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:
ES> "Turing makinasi" denen soyut makinadan bahsettigimizde ve
ES> Turing makinasinin misal elimizdeki bilgisayara denk oldugunu
ES> düsünürsek ve sonlu durum makinasi dedigimiz seyin de aslinda
ES> bir Turing makinasi üzerinde calisan bir sey oldugunu
ES> düsünürsek o zaman Turing makinasi, sonlu durum makinasindan
ES> daha etkindir demek anlamli mi?
Aynen bunu kastediyorum. Turing Makinasi, sonlu durum makinasinin
taniyabilecegi (recognize) ve karar verebilecegi (decide) dillerin
tumunu tanir ve karar verir, ustune ustluk sonlu durum makinasinin
yapamayacagi daha bir cok is yapar. Oyle ki, bir sonlu durum
makinasini, illa oyle olmasi gerekmese de Turing Makinasi uzerinde
simule edebiliriz. Hatta, bir Turing makinasini da bir baska Turing
makinasinda simule edebiliriz.
(Bu arada su anda kullandigimiz bilgisayar modeli Turing makinasina
denk dusuyor. Daha otesi, kullandigimiz programlama dilleri ve
yazgimiz programlar da cogunlukla birer Turing makinasi. "Turing
complete" olmayan dillerden biri SQL. Az bulunur oyle ornek.)
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.
ES> Sonlu durum makinasini, Turing makinasina denk olmayan bir
ES> bilgisayarda islemekten mi bahsediyorsun?
Hayir. Edi Weitz'in cl-ppcre'yi yazarken yaptigi sey, turing-complete
bir dil kullanarak sonlu durum makinasi ureten bir program
yazmak. Yani disaridan oyle gozukuyor. Netice de biz de bu sonlu durum
makinasini yine turing-complete bir dilde yazdigimiz bir programin
icerisinde ve Turing makindasina denk bir bilgisayarda
calistiriyoruz. Soyutlamada bir sorun oldugunu zannetmiyorum ve bu
kadar cok katman yerine daha az katman kullanarak daha hizli bir
sekilde sonuca varabiliriz.
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.
ES> Evet o sekilde islem yapiyor diye biliyorum, daha dogrusu ona
ES> denk gelecek sonlu durum makinasini kuruyor (biri beni
ES> düzeltsin sacmaliyorsam).
Butun dediklerim cercevesinde sacmaladigim noktalarda ben de
duzeltilmek istiyorum :)
VST> Burada dikkati cekmek istedigim olay, kiyaslama olayi.
VST> Sonuc: Girdileri bir patternle kiyaslamak zaten hizli bir
VST> islem degil.
ES> Evet, statik yani sabit karakter dizisi parcasini daha büyük
ES> bir dizi icinde aramaya kiyasla daha yavas.
VST> Regex kutuphanelerinin yazilmasinin sebebi, bu kiyaslamayi
VST> hizli yapmak icin degilmis de hizli kod yazmak icinmis gibime
VST> geliyor. Halbuki basit ama regexe kiyasla uygulamasi daha
VST> uzun algoritmalarla is halletmek cok daha hizli sonuclar
VST> veriyor. Bu genelleme dogru olabilir mi?
ES> Basitlik... Ne kadar basit? Yukarida gercekten basit örnek
ES> verdin, biliyorsun ki cok cok acayip patternler aradigimiz
ES> oluyor duruma göre. O zaman elle yazacagin algoritma optimize
ES> bir regex kütüphanesinin üretecegi sonlu durum makinasina
ES> kiyasla daha mi iyi olacak? Bu bir tartisma konusu.
Bilemiyorum. Hakli olabilirsin. Basitlik regex kullaninca ortaya
cikiyor. Ama regex kullanmak herseyi derli toplu hale getirse de, yan
etki olarak fazladan bir programlama katmani kullanmamiza neden
oluyor.
ES> Öte yandan, DSL yani "domain specific language"in gücü buradan
ES> cikmiyor mu, kendin prosedürel yöntemle imperatif olarak bir
ES> seyler yazdin, sonra o örüntüde (pattern'de) bir degisiklik
ES> yapman gerekti, ne olacak, tekrar git koda müdahale et! Koda
ES> müdahale kötü, veriye müdahale iyi diyorum. Bkz. RDBMS modeli.
ES> Arka planda karmasik kodlar var, kapali kutu. Sen veri ile
ES> ugrasir onu minciklayip durursun. SQL sana bir DSL gibi arayüz
ES> saglar. Hayat sürer gider...
Orasi oyle. Ama spesifik bir soruna genel bir cozum ortaya
koydugumuzda ve bu genel cozum cercevesinde dusunmeye basladikca
gozden kacirdigimiz seyler olabiliyor, bence...
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.
ES> CVS... DARCS... yapsak ortaya bir karisik, sonra Common Lisp
ES> SNA modülünün CVS ya da DARCS modülü islevselligi olsa,
ES> commitleri filan analiz edip SNA yapsa :)
ES> Neyse saka bir yana, hakikaten bir kod deposu mevzusuna girsek
ES> ve o sekilde ortaklasa Lisp kodlasak, Emacs icinden kod
ES> deposuna baglansak, o tadi yakalasak, güzel bir deneyim olmaz
ES> mi diye düsünüyorum ben hala...
Ben hafta ici bakmaya calisacagim. Zor olmasa gerek.
$ apt-cache search darcs
arch2darcs - Convert Arch/tla repositories to Darcs
darcs - an advanced revision control system
darcs-buildpackage - Suite to help with Debian packages in Darcs archives
darcs-load-dirs - Import upstream archives into darcs
darcs-server - the darcs server-side software
load-dirs-common - Common files for tla-load-dirs and darcs-load-dirs
tailor - migrate changesets between version control systems
--vst
_______________________________________________
cs-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
