>>>>> "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 cs-lisp@cs.bilgi.edu.tr http://church.cs.bilgi.edu.tr/lcg http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp