M E T A – S Y N T H E S E

Synthese von Programmen, die Programme generieren

Christoph Kreitz

Fachgebiet Intellektik, Fachbereich Informatik, TH Darmstadt

Alexanderstraße 10, 6100 Darmstadt

ÜBERSICHT

1. Rechnergestützte Software-Entwicklung

(a) Ziele und Realität

(b) Wozu Meta-Synthese?

2. Formalisierung von Software-Entwicklung

(a) Objektwissen

(b) Grundbegriffe der Programmierung

(c) Syntheseparadigmen

(d) Synthesestrategien

3. Ausblick

(a) Verwendbarkeit von Formalisierung

(b) Zukünftige Forschungsrichtungen

SOFTWARE-KRISE

Kommerzielle Software wird “von Hand” und direkt

in einer gegebenen Programmiersprache entwickelt.

• Schnelle Produktion von Software

• Hohe Kosten für Erstellung und Wartung

• Modifikationen und Erweiterungen schwierig– keine Dokumentation des Programmierprozesses

• Mangelnde Zuverlässigkeit mit fatalen Folgen– Tests sind nicht aussagekräftig

– Korrektheitsbeweise undurchführbar

SYSTEMATISCHESOFTWARE-ENTWICKLUNG

• Programmierung ist logisches Schließen

• Programmierung verarbeitet Wissenüber Programme, Anwendungsbereiche, Programmiermethoden

• Menschen machen Fehler im Detail

• Formalisierung und Automatisierung nötig

• CASE-tools sind nicht genug

Softwareproduktion braucht

Wissensbasiertes Software-Engineering

PROGRAMMSYNTHESE

Automatisierte Entwicklung validierter Software

• Algorithmen-Synthese aus formalen Spezifikationen

• Hilfe beim Entwurf formaler Spezifikationen

• Hilfsmittel zur– algorithmischen Optimierung,

– Implementierung abstrakter Datentypen

– sprachabhängigen Compilierung / Optimierung...

• Dokumentation getroffener Entscheidungen

• Verfahren zum Erwerb von Synthesewissen

PROGRAMMSYNTHESE –KALKÜLE

• Regeln für syntaktische Manipulation von Formelnersetzen semantisch-logisches Schließen

• Absolut formal, wohlbekannte Eigenschaften

• Ausdruckstark genug zur Formalisierungder gesamten Mathematik und Programmierung

• Abstraktionsniveau gering: Einzelschritte zu atomar

• Wenige praktische Ergebnisse

• Forschung richtet sich auf theoretische Eigenschaften

PROGRAMMSYNTHESE –SYSTEME

• “Halb-formale” Beschreibung auf dem Papier

• Implementierung erfolgreich an Beispielen getestet

• Bald verwendbar für Routineprogrammierung ?

• Einsatz in der Lehre möglich ?

• Implementierung “ad hoc”

• Gleiche Probleme wie konventionelle Software:– tatsächliches Verhalten unklar

– Wartung und Modifikation schwierig

– Korrektheit nicht gesichert

META-SYNTHESE – ZIELE

Systeme für rechnergestützte Software-Entwicklung

müssen systematisch entwickelt werden.

• Formalisiere die Objekt- und Meta-Theorieder Programmierung in einheitlichem Rahmen.

• Durch Abstraktion schließe Lücke zwischen formalen Kalkülenund semi-formalen Syntheseverfahren.

• Beweise Eigenschaften von deduktiven Methodenund erzeugten Programmen als formale Theoreme.

• Realisiere Formalisierung mit einem Beweiseditorfür den zugrundeliegenden logischen Kalkül.

• Leite Implementierungen deduktiver Methoden ab ausTheoremen über Erfüllbarkeit von Spezifikationen.

VERWANDTE GEBIETE

• Formale Kalküle und ihre ImplementierungIntuitionistische Typentheorie (Martin-Löf),

Kalkül der Konstruktionen (Huet/Coquand),

System F, Fω, Lineare Logik (Girard), . . .

• Strategien für automatische ProgrammsyntheseKIDS (Kestrel Institute), PRECOMAS (Franova),

LOPS (Bibel), OYSTER-CLAM (Bundy), . . .

+ Formale Methoden des Software-Engineering (VDM)

• Meta-programmierung (“taktisches Beweisen”)LCF (Edinburgh / Cambridge), NuPRL (Cornell),

KIV (Heisel/Reif/Stephan), DEVA (GMD Karlsruhe)

OYSTER-CLAM, . . .

• Meta-Reasoning und Logical FrameworksIsabelle (Paulson, Cambridge), λ-Prolog (Felty/Miller)

LF (Edinburgh), Elf (Pfenning), FOL (Weyrauch)

INTUITIONISTISCHETYPEN-THEORIE

Basiskalkül für Logik, Datentypen und Berechnung

• Sortierte Logik höherer Stufe• Gleichheitsbegriff abhängig vom Datentyp• Funktionale Programmiersprache• Viele Datentyp-Konstrukte vordefiniert:

– Zahlen, Strings, Funktionenräume, Produkträume,

– disjunkte Vereinigung, Listen, Sub-Typen, Faktorisierung,

– Rekursive Datentypen, Partiell-rekursive Funktionen.

• Top-Down Sequenzenkalkül (ca. 150 Regeln)• NuPRL: Interaktives Theorie-Entwicklungs-System

– Beweiseditor

– Programmextraktion aus Beweisen

– Definitionsmechanismus (Textmacros mit Parametern)

– Meta-level Programmierung von Beweisstrategien

– Bibliothek

DARSTELLUNG VONOBJEKTWISSEN

Begriffe prägen – Eigenschaften als Lemmata beweisen

• Explizit definierte Operationen und Konzepte– Implementiert durch direkte Definition

– Zugriff durch Instantiierung der Definition

• Formal verifizierte Lemmata(elementare Eigenschaften der Kombination von Operationen)

• Definition abstrakter Datentypen(endliche Sequenzen, Mengen, Abbildungen, Arrays, . . . )

– Definition von Signaturen und Axiomen

– Implementiert durch Theorem über Erfüllbarkeit

– Zugriff nur auf Axiome

Zur Zeit ca. 150 Definitionen, 650 Lemmata

ABSTRAKTER DATENTYP: Menge

Abstrakte Definition:

FINITE SETS(α)

≡TYPES Set(α)

OPERATIONS ∅: Set(α)+: Set(α)××α → Set(α)∈: α××Set(α) → Bool

AXIOMS ∀S:Set(α).∀x,a:α.a 6∈∅

∧ x ∈(S+a) ⇔ (x=a ∨ x ∈S)∧ (S+a)+x = (S+x)+a

∧ (S+a)+a = S+a

∧ ∀P:PROP(Set(α)).P(∅) ∧ ∀S:Set(α).∀a:α. P(S) ⇒ P(S+a)⇒ ∀S:Set(α).P(S)

Implementierungstheorem:

∀α:TYPES. FINITE SETS(α) has a model

PROGRAMMIERUNG: Grundbegriffe

Eine Spezifikation besteht aus Ein- und Ausgabetypen DD und RR, einer

Eingabebedingung I und einer Ausgabebedingung O.

Ein Programm besteht aus einer Spezifikation (DD,RR,I,O) und einer

(berechenbaren, partiellen) Funktion body:DD 6→RR.Formale Definitionen:

SPECIFICATIONS ≡ DD:TYPES×× RR:TYPES×× PROP(DD)×× PROP(DD××RR)DOM(spec) ≡ let spec=(DD,RR,I,O) in {x:DD | I(x)}PROGRAMS ≡ spec:SPECIFICATIONS ×× DOM(spec)→RR(spec)consistent(p)≡ let p=( (DD,RR,I,O), body) in

∀x:DD. I(x) ⇒ O(x,body(x))spec is satisfiable ≡ ∃body:DOM(spec)→RR(spec).

consistent(spec,body)

Programmsynthese = Beweis von spec is satisfiable

Notation mit Schlüsselwörtern:

FUNCTION f(x:DD):RR WHERE I(x)

RETURNS y SUCH THAT O(x,y)

= body(x)

METHODEN als METATHEOREME

“Erzeuge korrektes Programm für Spezifikation spec

durch den Nachweis bestimmter Bedingungen”

• Formalisierung: Formulierung eines Metatheorems‘‘spec is satisfiable ⇐ Bedingungen’’

• Validierung: Beweis des Metatheorems

• Implementierung des Ableitungsschrittes:Anwendung des computerisierten Metatheorems

• Implementierung der Algorithmenkonstruktion:Enthalten im computerisierten konstruktiven Beweis

SYNTHESEPARADIGMEN

• Beweise als Programme– Extraktion aus konstruktivem Beweis eines Theorems

• Synthese durch Transformationen– Äquivalenzumformung in ausführbare Form

• Algorithmenschemata– Wissensbasierte Verfeinerung von Standardlösungen

für algorithmische Grundstrukturen

Unterscheiden sich durch

– Interne Aufgabenstellung (Darstellung des Problems)

– Interne Lösungsmethode (Art der Inferenz)

– Konstruktion des Algorithmus aus interner Lösung

Individuelle Notationen und Heuristiken variieren stark.

ÄQUIVALENZ DER PARADIGMEN

Formales Meta-Theorem:

∀spec=(DD,RR,I,O):SPECIFICATIONS.spec is satisfiable

⇔ ∀x:DD. ∃y:RR. I(x) ⇒ O(x,y) is provable⇔ ∃OD:PROP(DD××Seq(DD)). ∃OC:PROP(DD××Seq(DD)××Seq(RR)××RR).∀x,y. O(x,y) ⇔ ∃x̄,ȳ. OD(x,x̄) ∧ O∗(x̄,ȳ) ∧ OC(x,x̄,ȳ,y)∧ OD is a well-founded relation

∧ ( DD, Seq(DD), I, OD ) is satisfiable

∧ ( DD××DD××RR, RR, I, OC ) is satisfiable⇔ ∃A:THEORIES.∃A:Models(A).

A is an algorithm theory ∧ A extends spec

Macht individuelle Ansätze zur Programmsynthese

originalgetreu darstellbar, korrekt implementierbar,

vergleichbar und integrierbar

SYNTHESE-STRATEGIEN

Formalisierung repräsentiert, verfeinert, verbessert und

implementiert Beschreibungen existierender Strategien.

LOPS (Bibel, 1980 . . . )

• Ausformulierung der verbalen Beschreibung• Verifikation von Teilstrategien• Grundlage für Neuimplementierung

KIDS (Kestrel Institute, 1985 . . . )

• Verfeinerung einer Formalisierung• Aufdeckung kleiner Fehler• Schließen von Lücken durch neue Konzepte

Implementierung einer Strategie wird identisch

mit ihrer textueller Beschreibung

SYNTHESE von GS-ALGORITHMEN

Berechnung aller Lösungen eines Problems

GLOBALSUCHE:

– Manipulation von Mengen von Lösungskandidaten

– Verallgemeinerung von Binärsuche, Backtracking, etc.

– Vollständig

Synthese durch Analyse der Struktur

• Darstellung durch “space descriptors” s ∈SJ(x,s): s ist ein sinnvoller Deskriptor für x

sat(z,s): z ist in der durch s beschriebenen Menge

• Initialdeskriptor s0(x) ∈S umfaßt alle Lösungen• Direkte Extraktion ext(s) ∈Set(RR) von Kandidaten• Aufspaltung von Deskriptoren split(x,s) ∈Set(S)• Elimination von Deskriptoren durch Filter Φ(x,s)• Rekursion bis kein Splitting mehr möglich ist

FORMALE GS-SCHEMATA

G is a GS-theory

≡ let G=((DD,RR,I,O), S, J, s0, sat, split, ext) in

consistent((DD,RR,S,J), s0)

∧ ∀x:DD.I(x) ⇒ ∀s:S. J(x,s) ⇒ ∀t ∈split(x,s).J(x,t)∧ ∀x:DD.I(x) ⇒ ∀z:R. O(x,z) ⇒ sat(z,s

0(x))

∧ ∀x:DD.I(x) ⇒ ∀s:S. J(x,s) ⇒ ∀z:R.sat(z,s) ⇔ ∃k:IN.∃t ∈splitk(x,s). z ∈ext(t)

splitk(x,s)

≡ if k=0 then {s} else ⋃{splitk−1(x,t)|t ∈split(x,s)})G is well-founded

≡ let G=((DD,RR,I,O), S, J, s0, sat, split, ext) in

∀x:D.∀s:S. ∃k:IN. splitk(x,s) = ∅G extends spec

≡ let G=((DD,RR,I,O), S, J, s0, sat, split, ext) in

spec = (DD,RR,I,O) in SPECIFICATIONS

GS-STRATEGIE

Eine Spezifikation wird synthetisiert durch Einbettung in

ein wohlfundiertes Globalsuch-Schema. (Smith, 1988)

Implementierungstheorem:

∀spec=(DD,RR,I,O):SPECIFICATIONS.FUNCTION f(x:DD):Set(RR) WHERE I(x)

RETURNS S SUCH THAT S={y:RR|O(x,y)}is satisfiable

⇐ ∃G. G is a GS-theory ∧ G is well-founded∧ G extends spec

Beweis durch explizite Angabe des Lösungsschemas

Sei G=((DD,RR,I,O), S, J, s0, sat, split, ext)

Setze f(x) := Fgs(x,s0(x))

Fgs(x,s) := {z|z ∈ext(s) ∧O(x,z)}∪ ⋃{Faux(x,t)| t ∈split(x,s)}

Verifiziere Schema durch Induktion über die Anzahl

der Schritte bis kein Splitting mehr möglich ist.

GS-STRATEGIE – verfeinert

Synthetisiere durch Spezialisierung eines GS-Schemas und

eines Wohlfundiertheits-Filters aus der Wissensbank.

Implementierungstheorem:

∀spec=(DD,RR,I,O):SPECIFICATIONS.FUNCTION f(x:DD):Set(RR) WHERE I(x)

RETURNS S SUCH THAT S={y:RR|O(x,y)}is satisfiable

⇐ ∃G.∃Φ. G is a GS-theory ∧ Φ is a wf-filter for G∧ G generalizes spec

G generalizes spec

≡ let G=((DD,RR,I,O), S, J, s0, sat, split, ext)

and spec=(DD’,RR,I’,O’) in

∀x:DD. I(x) ⇒ ∃x’:DD’. I’(x’) ∧ ∀z:RR. O(x,z) ⇒ O’(x’,z)Φ is a wf-filter for G

≡ let G=((DD,RR,I,O), S, J, s0, sat, split, ext) in

∀x:DD.∀s:S. I(x) ∧J(x,s)⇒ ∃k:IN. splitΦk(x,s) = ∅splitΦ ≡ λx,s.{t|t ∈split(x,s) ∧Φ(x,t)}

ZUSAMMENFASSUNG

Logisch-formale Theorie der Programmentwicklung

• Einheitliche Behandlung von Objekt- und Metalevel• Hohes Abstraktionsniveau• Erfaßt alle Aspekte der Programmierung• Erweiterbar auf andere Gebiete der Deduktion• Vollständig formal• Ohne Modifikationen implementierbar

Ermöglicht

• Verifizierte Implementierung von Synthesestrategien• Integration verschiedenartiger Strategien• Integration einer Vielfalt von Komponenten

Fundament der Inferenzmaschine innerhalb einer

Umgebung für wissensbasiertes Software-Engineering

FORSCHUNGSRICHTUNGEN

• Interface zwischen Mensch und formaler Theorie

• Entwurf formaler Spezifikationen

• Darstellung von Planungs- und Beweismethoden

• Vergleich und Integration von Designstrategien

• Systematischen Optimierung von Algorithmen

• Datentyp-Verfeinerung

• Automatische Entwicklung von Standardwissen

• Rechnergestützte Synthese von Strategien