Schema-based logic program transformation
- Global styles
- Apa
- Bibtex
- Chicago Fullnote
- Help
Abstract
ÖZET TASLAĞA DAYALI MANTIK PROGRAMI DÖNÜŞTÜRME Halime Büyükyıldız Bilgisayar ve Enformatik Mühendisliği. Yüksek Lisans Tez Yöneticisi: Yrd. Doç. Pierre Flener Ağustos 1997 Geleneksel programlama metodolojisinde, doğru ve etkili program geliştirme iki aşamaya ayrılır: birinci aşamada, sentez aşaması denir, doğru, fakat yeterince etkili olmayabilen bir program yapılır, ve ikinci aşamada, dönüştürme aşaması denir, yapılan program daha etkili eşdeğer bir programa dönüştürülür. Eğer sentez aşaması belirli bir program ailesinin yapımını özetleyebilen algoritma plan bilgisini içeren program taslağı rehberliğindeyse, dönüştürme aşaması da giren program taslağından çıkan program taslağına tanımlanmış dönüşüm tekniklerini daha etkili eşdeğer bir program elde etmeyi sağlayacak gerekli koşulları tanımlayarak kodlayan dönüşüm taslakları kullanarak yapılabilir. Böl-ve-fethet ve genelleme metodlarını kullanarak sentezlenebilecek program ailelerini temsil eden yedi program taslağı sunuluyor. Sunulan dönüşüm taslakları ya içine birikeç sokmak ve yapısal genellemenin özel bir hali olan Çoğullama genellemesi gibi dönüşüm tekniklerinin otomasyonunu sağlar, ya da fonksiyonel programlamanın temel teoremlerinden birini (fold operatörlerinin ilk ikilik kuralını) mantıksal programlamaya geliştirerek uygular. Sunulan dönüşüm taslaklarını kullanarak program dönüştürebilen prototip bir sistem geliştirilmiştir. Anahtar Sözcükler: mantıksal programlama, program geliştirme, program dönüştürme, program taslağı, dönüşüm taslağı, genelleme, ikilik kuralları. ABSTRACT SCHEMA-BASED LOGIC PROGRAM TRANSFORMATION Halime Büyükyıldız M.S. in Computer Engineering and Information Science Supervisor: Ass't Prof. Pierre Flener August 1997 In traditional programming methodology, developing a correct and efficient program is divided into two phases: in the first phase, called the synthesis phase, a correct, but maybe inefficient program is constructed, and in the sec ond phase, called the transformation phase, the constructed program is trans formed into a more efficient equivalent program. If the synthesis phase is guided by a schema that embodies the algorithm design knowledge abstracting the con struction of a particular family of programs, then the transformation phase can also be done in a schema-guided fashion using transformation schemas, which encode the transformation techniques from input program schemas to output program schemas by defining the conditions that have to be verified to have a more efficient equivalent program. Seven program schemas are proposed, which capture sub-families of divide- and-conquer programs and the programs that are constructed using some gen eralization methods. The proposed transformation schemas either automate transformation strategies, such as accumulator introduction and tupling gen eralization, which is a special case of structural generalization, or simulate and extend a basic theorem in functional programming (the first duality law of the fold operators) for logic programs. A prototype transformation system is presented that can transform programs, using the proposed transformation schemas. Keywords: logic programming, program development, program transforma tion, program schema, transformation schema, generalization, duality laws. iii
Collections