Systematische Fehlersuche in deklarativen Programmen

• Antragsteller: Professor Dr. Michael Hanus
• Fachliche Zuordnung: Softwaretechnik und Programmiersprachen
• Förderung: Förderung von 2004 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5427727

• Erstellungsjahr: 2010

Zusammenfassung der Projektergebnisse

In diesem Bericht sind die Arbeiten und Ergebnisse der zweiten Förderphase des Forschungsvorhabens dokumentiert. Die Schwerpunkte in dem Berichtszeitraum lagen in den Bereichen • Skalierung der erstellten Software um deren praktische Einsetzbarkeit zu ermöglichen • Entwurf eines flexiblen Rahmens zur Programmierung von Werkzeugen zur Fehlersuche • Erstellung verschiedener Werkzeuge zur Fehlersuche • Erweiterung der formalen Grundlagen • Erschließung weiterer Themengebiete der deklarativen Fehlersuche, wie (a) dynamische Überprüfung spezifizierter Eigenschaften (Zusicherungen) (b) automatische Testfallgenerierung und (c) anwendungsspezifische Programmanalysen. In Bezug auf die Skalierung des in der ersten Phase des Projektes erarbeiteten Ansatzes ist in der zweiten Projektphase ein wesentlicher Durchbruch gelungen. Wie berichtet, sah der erste Ansatz eine umfassende Aufzeichnung des operationalen Geschehens bei der Ausführung eines deklarativen Programms vor. In der zweiten Phase des Projektes stellte sich dann heraus, dass dieser Ansatz sowohl in Bezug auf die Effizienz der Aufzeichnung als auch im Aufwand der späteren Verarbeitung der gesammelten Daten nicht auf reale Anwendungen skalierbar sein würde. In der Folge haben wir einen rundum verbesserten Ansatz entwickeln können, der 1.) um Größenordnungen weniger Daten aufzeichnet und 2.) eine effiziente Bearbeitung der erhobenen Daten ermöglicht. Durch Ausnutzung einiger fortgeschrittener Techniken der deklarativen, in diesem Fall der funktionalen, Programmierung ist es gelungen, einen besonders ?exiblen Rahmen zu erstellen, in dem sich Werkzeuge zur Fehlersuche zum Teil mit wenigen Zeilen Programmcode erstellen lassen. Der Programmierer eines Werkzeugs ist dabei vollständig von der Aufgabe entlastet, die aufgezeichneten Daten der Programmausführung zu interpretieren. Seine Aufgabe ist damit auf die Erstellung der Funktionalität des eigentlichen Werkzeugs beschränkt. Mit Hilfe des flexiblen Rahmens konnten dann auch eine Reihe von Werkzeugen im Lauf der zweiten Projektphase umgesetzt werden. Diese Werkzeuge umfassen (a) die Übertragung bekannter Techniken der Fehlersuche aus Teilbereichen der deklarativen Programmierung auf den allgemeinen Sprachumfang der logisch-funktionalen Programmiersprachen, (b) Übertragung bekannter Techniken aus dem Bereich der imperativen Programmiersprachen, wobei erstmals auch ein simulierender Ansatz zur Fehlersuche in Programmen mit I/O-Operationen entwickelt wurde und (c) die Entwicklung neuer Techniken zum Beispiel für die Analyse von Programmen mit Endlosschleifen und der Geometrie von Suchräumen. Einige der entwickelten Werkzeuge sind dabei, entsprechend der Gutachterempfehlungen, auch graphisch umgesetzt worden. Zur Erweiterung der formalen Grundlage für die traceorientierte Fehlersuche war in der zweiten Projektphase zunächst die Korrektheit des neuen Ansatzes zu beweisen. Nichtsdestotrotz ist es gelungen, die formale Grundlage näher an die wirklich ablaufende Aufzeichnung zu bringen, was eines der Ziele der zweiten Phase war. Zudem konnte auch die geplante Erweiterung der allgemeinen Grundlagen zur logisch-funktionalen Programmierung auf das Phänomen des Sharings von deterministischen Berechnungen über verschiedene Bereiche des Suchraums hinweg durchgeführt werden. Ein wesentlicher Punkt des Antrages konnte nicht umgesetzt werden: die geplante Evaluation der entwickelten Werkzeuge zur Fehlersuche. Durch die Entwicklung des neuen Ansatzes musste der Zeitplan so überarbeitet werden, dass dieses Teilprojekt leider fallen gelassen werden musste.

Projektbezogene Publikationen (Auswahl)

• A pattern logic for prompt lazy assertions in haskell. In Zoltán Horváth, Viktória Zsók, and Andrew Butterfield, editors, IFL, volume 4449 of Lecture Notes in Computer Science, pages 126–144. Springer, 2006
  Olaf Chitil and Frank Huch
  
• CurryBrowser: A generic analysis environment for Curry programs. In Proc. of the 16th Workshop on Logic-based Methods in Programming Environments (WLPE’06), pages 61–74, 2006
  M. Hanus
  
• Type-oriented construction of web user interfaces. In Proceedings of the 8th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP’06), pages 27–38. ACM Press, 2006
  M. Hanus
  
• A framework for interpreting traces of functional logic computations. Electronic Notes in Theoretical Computer Science, 177:91–106, 2007
  B. Braßel
  
• Computing with subspaces. In Michael Leuschel and Andreas Podelski, editors, Proceedings of the 9th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, pages 121–30. ACM, 2007
  Sergio Antoy and Bernd Braßel
  
• Lazy call-by-value evaluation. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming (ICFP’07), pages 265 – 276, 2007
  B. Braßel, S. Fischer, M. Hanus, F. Huch, and G. Vidal
  
• Monadic, prompt lazy assertions in Haskell. In Proc. APLAS 2007, pages 38–53. Springer LNCS 4807, 2007
  O. Chitil and F. Huch
  
• On a tighter integration of functional and logic programming. In Zhong Shao, editor, APLAS, volume 4807 of Lecture Notes in Computer Science, pages 122–138. Springer, 2007
  Bernd Braßel and Frank Huch
  
• Putting declarative programming into the web: Translating Curry to JavaScript. In Proceedings of the 9th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP’07), pages 155–166. ACM Press, 2007
  M. Hanus
  
• Systematic generation of glass-box test cases for functional logic programs. In Proceedings of the 9th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP’07), pages 75–89. ACM Press, 2007
  S. Fischer and H. Kuchen
  
• The interactive Curry observation debugger iCODE. Electronic Notes in Theoretical Computer Science, 177:107–122, 2007
  P.H. Sadeghi and F. Huch
  
• A Debugger for Functional Logic Languages. In Sebastian Fischer and Michael Hanus, editors, 25. Workshop der GI-Fachgruppe “Programmiersprachen und Rechenkonzepte”, pages 78–92. Christian-Albrechts-University of Kiel, 2008. Technical Report 0811
  Bernd Braßel
  
• A relation algebraic semantics for a lazy functional logic language. In Rudolf Berghammer, Bernhard Möller, and Georg Struth, editors, RelMiCS, volume 4988 of Lecture Notes in Computer Science, pages 37–53. Springer, 2008
  Bernd Braßel and Jan Christiansen
  
• A Technique to build Debugging Tools for Lazy Functional Logic Languages. In Moreno Falschi, editor, Proceedings of the 17th Workshop on Functional and (Constraint) Logic Programming (WFLP 2008), pages 63–76, 2008
  B. Braßel
  
• Call pattern analysis for functional logic programs. In Proceedings of the 10th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP’08), pages 67–78. ACM Press, 2008
  M. Hanus
  
• Data-flow testing of declarative programs. In Proc. of the 13th ACM SIGPLAN International Conference on Functional Programming (ICFP 2008), pages 201–212. ACM Press, 2008
  S. Fischer and H. Kuchen
  
• Debugging Lazy Functional Programs by Asking the Oracle. In Olaf Chitil et al., editor, Proc. Implementation of Functional Languages (IFL 2007), volume 5083 of Lecture Notes in Computer Science, pages 183–200. Springer, 2008
  Bernd Braßel and Holger Siegel
  
• Declarative programming of user interfaces. In Proc. of the 22nd Workshop on (Constraint) Logic Programming (WLP 2008), pages 37–49. Technical Report 2008/08, University Halle-Wittenberg, 2008
  M. Hanus and C. Kluß
  
• Denotation by transformation: Towards obtaining a denotational semantics by transformation to point-free style. In Andy King, editor, Proceedings of the 17th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2007), volume 4915 of LNCS, pages 90–105. Springer, 2008
  Bernd Braßel and Jan Christiansen
  
• EasyCheck - test data for free. In Proc. of the 9th International Symposium on Functional and Logic Programming (FLOPS 2008), pages 322–336. Springer LNCS 4989, 2008
  J. Christiansen and S. Fischer
  
• From Functional Logic Programs to Purely Functional Programs Preserving Laziness. In Proc. 20th Workshop on Implementation and Application of Functional Languages (IFL 2008), pages 214 – 215, 2008
  Bernd Braßel and Sebastian Fischer
  
• High-level database programming in curry. In Paul Hudak and David Scott Warren, editors, Practical Aspects of Declarative Languages, 10th International Symposium, PADL 2008, San Francisco, CA, USA, January 7-8, 2008, volume 4902 of Lecture Notes in Computer Science, pages 316–332. Springer, 2008
  Bernd Braßel, Michael Hanus, and Marion Müller
  
• The Kiel Curry System KiCS. In D. Seipel, M. Hanus, and A. Wolf, editors, Proceedings of the 21st Workshop on (Constraint) Logic Programming, WLP’2007, Lecture Notes in Artificial Intelligence, pages 195–205. Springer, 2008
  Bernd Braßel and Frank Huch
  
• Functional (logic) programs as equations over ordersorted algebras. In Dean Voets, editor, Proceedings of the 19th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2009), 2009
  Bernd Braßel and Rudolf Berghammer
  
• Proposing Order-Sorted Algebra as Foundation for Declarative Programming. In Bernd Braßel and Michael Hanus, editors, 26. Workshop der GI-Fachgruppe “Programmiersprachen und Rechenkonzepte”, pages 114 – 123. Christian-Albrechts-University of Kiel, 2009. Technical Report 0915
  Bernd Braßel
  
• Run-Time Debugging for Functional Logic Languages. PhD thesis, Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Juni 2009
  P.H. Sadeghi