View
106
Download
1
Category
Preview:
Citation preview
Regelbasierte Programmierung mit XL
Winfried Kurth
Reinhard Hemmerling
BTU Cottbus, Lehrstuhl Grafische Systeme
1. PARADIGMEN DER PROGRAMMIERUNG
Paradigma:
grundlegendes Prinzip, beispielorientierte Vorstellung, zwischen "Modell" und "Analogie" angesiedelt, teilweise exakt, mathematisch unterstützbar, anschaulich, auf virtuellem Niveau.
Paradigmen der Programmierung (nach Floyd 1979):
imperatives Paradigma
objektorientiertes Paradigma
funktionales Paradigma
Fallregel-Paradigma
1. Imperatives Paradigma(John von Neumann)
liegt der klassischen imperativen Programmierung (Befehls-Programmierung) zugrunde.
Auch: "prozedurales Paradigma", "Kontrollfluss-Paradigma".
Computer = Maschine zur Veränderung von Variablen-werten.
Programm = Plan für den Berechnungsprozess mit Angabe der Befehle und des Kontrollflusses (z.B. Schleifen).
Programmfindung: Elementare Einzelschritte finden und in flexible Reihenfolge bringen.
Programmiersprachen: Fortran, Basic, Pascal, C, Teile von Java.
Beispiel:
x = 0;
while (x < 100)
x = x + 1;
Inhalt der Variable x wird verändert
Schleife legt Kontrollfluss fest
Beachte: "=" steht hier nicht für math. Gleichheit, sondern für Zuweisung (prozesshaft)!
2. Objektorientiertes Paradigma
Computer = Umgebung für virtuelle Objekte
Programm = Auflistung von (Objekt-) Klassen, d.h. allgemeiner Spezifikationen von Objekten, die zur Laufzeit des Programms (ggf. mehrfach) erschaffen und wieder vernichtet werden können und miteinander kommunizieren.
Programmfindung: Spezifikation der Klassen (Daten und Methoden), die Objektstruktur und -verhalten festlegen.
Programmiersprachen: Smalltalk, Simula, C++, Delphi, Java(in den letzten 4 mit imperativen Konstrukten vermischt)
Beispiel (in Java):
public class Auto extends Fahrzeug
{
public String marke;public int plaetze;
public void anzeigen(){System.out.println("Das Auto ist ein " + marke);System.out.println("Es hat " + plaetze + "Sitze.");}
}
typisch:
Klassen (class) mit Daten (marke, plaetze) und Methoden (anzeigen)
3. Funktionales Paradigma(applikative Programmierung, McCarthy-Paradigma)
Programmiersprachen: Lisp, Haskell, Lambda-Kalkül, APL
Computer = Maschine, die Verallgemeinerungen von Operationen bilden, d.h. Funktionale definieren kann (vergleichbar der Bildung neuer Begriffe in der Mathematik)
Programm = verschachtelter Ausdruck funktionaler Anwendungen
Programmfindung: Spezifikation von Funktionen, die das Problem lösen
Beispiel (FP-System nach Backus):
def Skalarprod = (/+) ° (a*) ° trans
definiert das Skalarprodukt zweier Vektoren beliebiger Dimension.
Beachte: Keine Sequentialisierung, keine Variablendeklarationen, sehr kompakte Programme möglich.
4. Fallregel-Paradigma(van Wijngaarden, Lindenmayer)
Computer = Transformationsmaschine für Strukturen oder für Zustände.
Es gibt eine aktuelle Struktur, die solange transformiert wird, wie dies möglich ist.
Arbeitsprozess: Such- und Anwendungsprozess.matching: Suchen einer passenden Regel,rewriting: Anwendung der Regel, um die Struktur umzuschreiben.
Programm = Menge von Transformationsregeln.
Programmfindung: Spezifikation der Regeln.
Programmiersprachen: L-Systeme, XL, PROLOG, Intran, KI-Sprachen.
2. L-SYSTEME (Lindenmayer-Systeme)
analog zu Chomsky-Grammatiken, aber:
in jedem Ableitungsschritt parallele Ersetzung aller Zeichen, auf die eine Regel anwendbar ist
von A. Lindenmayer (Botaniker) 1968 zur Modellierung des Wachstums von fadenförmigen Algen eingeführt
Chomsky-Grammatik für natürliche Sprache:
Satz S P O
S Max
S Tina
P lernt
O Englisch
O Französisch
mögliche Ableitungen:
Satz Satz
S P O S P O
Max lernt Französisch Tina lernt Englisch
einfaches L-System:
mathematisch:
Ein L-System ist ein Tripel (, , R); darin ist:
eine Menge von Zeichen, das Alphabet,
eine Zeichenkette mit Zeichen aus , das Startwort (auch "Axiom"),
R eine Menge von Regeln der Form
Zeichen Zeichenkette;
darin sind das Zeichen auf der linken Regelseite und die Zeichenkette aus entnommen.
Ein Ableitungsschritt (rewriting) einer Zeichenkette besteht aus der Ersetzung aller Zeichen in , die in linken Regelseiten von R vorkommen, durch die entsprechenden rechten Regelseiten.
Man vereinbart: Zeichen, auf die keine Regeln anwenbar sind, werden unverändert übernommen.
Ergebnis zunächst nur:
Ableitungskette von Wörtern, die sich durch wiederholte Anwendung des rewriting-Vorgangs aus dem Startwort ergeben.
1 2 3 ....
Beispiel:
Alphabet {A, B}, Startwort A
Regelmenge R:
A B
B AB
Ableitungskette:
A B AB BAB ABBAB BABABBAB
ABBABBABABBAB BABABBABABBABBABABBAB
...
wie lang ist die n-te Zeichenkette in dieser Ableitung?
was für die Modellierung von räumlichen Strukturen noch fehlt:
eine geometrische Interpretation
Füge also zur Def. eines L-Systems hinzu:
eine Abbildung, die jeder Zeichenkette mit Zeichen aus eine Teilmenge des 3-dimensionalen Raumes zuordnet
dann: "interpretierte" L-System-Abarbeitung
1 2 3 ....
S1 S2 S3 ....
S1, S2, S3, ... können als Entwicklungsstufen eines Objekts,
einer Szene oder einer Konfiguration interpretiert werden.
Als Interpretationsabbildung wird meistens gewählt:
Turtle geometry ("Schildkrötengeometrie")
befehlsgesteuertes, lokales Navigieren im 2D- oder 3D-Raum (Abelson & diSessa 1982; vgl. Programmier-sprache "LOGO")
"Turtle": Zeichen- oder Konstruktionsgerät (virtuell)
- speichert (grafische und nicht-grafische) Informationen
- mit einem Zustandsspeicher assoziiert (wichtig für Verzweigungen)
- aktueller Zustand der Turtle enthält z.B. Information über aktuelle Liniendicke, Schrittweite, Farbe, weitere Eigenschaften des als nächstes zu konstruierenden Objekts
Der Turtle-Befehlsvorrat wird zu einer Untermenge der Zeichenmenge des L-Systems. Symbole, die nicht Turtle-Befehle sind, werden von der Turtle ignoriert.
Befehle (Auswahl):
F0 "Forward", mit Konstruktion eines Elements (Linienstück, Segment, Gebäudetrakt...), benutzt wird die aktuelle Schrittweite für die Länge
(die Null steht für "keine explizite Längenfestlegung")
M0 forward ohne Konstruktion (Move-Befehl)
L(x) ändere die aktuelle Schrittweite (Länge) zu x
LAdd(x) inkrementiere die aktuelle Schrittweite um x
LMul(x) multipliziere die aktuelle Schrittweite mit x
D(x), DAdd(x), DMul(x) analog für die aktuelle Dicke
RU(45) Drehung der turtle um die "up"-Achse um 45°
RL(...), RH(...) analog um "left" und "head"-Achse
up-, left- und head-Achse bilden ein rechtwinkliges, räumliches Koordinatensystem, das von der turtle mitgeführt wird
RV(x) Rotation "nach unten" mit durch x vorgegebener Stärke
Beispiel:
L(100) D(3) RU(-90) F(50) RU(90) M0 RU(90) D(10) F0 F0
D(3) RU(90) F0 F0 RU(90) F(150) RU(90) F(140) RU(90)
M(30) F(30) M(30) F(30) RU(120) M0 Sphere(15) erzeugt
was ist das Ergebnis der Interpretation der Zeichenkette
L(10) F0 RU(45) F0 RU(45) LMul(0.5) F0 M0 F0 ?
Wiederholung von Abschnitten der Zeichenkette möglich mit dem Schlüsselwort "for"
z.B. for ((1:3)) ( A B C )
liefert A B C A B C A B C
was ist das Ergebnis der Interpretation von
L(10) for ((1:6)) ( F0 RU(90) LMul(0.8) ) ?
Verzweigungen: Realisierung mit Speicher-Befehlen
[ lege aktuellen Zustand auf Speicher ("Ablage")
] nimm obersten Zustand von der Ablage und mache diesen zum aktuellen Zustand (damit: Ende der Verzweigung)
Beispiel:
Regeln
A F0 [ RU(45) B ] A ;
B F0 B ;
Startwort L(10) A
(A und B werden normalerweise nicht geometrisch interpretiert.)
was für eine Struktur liefert das L-System
A [ LMul(0.25) RU(-45) F0 ] F0 B;
B [ LMul(0.25) RU(45) F0 ] F0 A;
mit Startwort L(10) A ?
was für eine Struktur liefert das L-System
A [ LMul(0.25) RU(-45) F0 ] F0 B;
B [ LMul(0.25) RU(45) F0 ] F0 A;
mit Startwort L(10) A ?
äquivalente Regel:
A [ LMul(0.25) RU(-45) F0 ] F0 RH(180) A;
Weitere Beispiele:
Koch'sche Kurve:
L(50) RU(90) A F0;
A A LMul(0.3333); /* Skalierung */
F0 F0 RU(-60) F0 RU(120) F0 RU(-60) F0;
jedes Linienstück wird durch 4 neue Linienstücke ersetzt (3. Regel); Skalierung durch Hilfssymbol A, welches sich in jedem Schritt reproduziert und dabei jeweils einen zusätzlichen Faktor 1/3 erzeugt (2. Regel).
Das Startwort ist hier " ".
Ausgabe nach 6 Schritten:
Flächenfüllende Kurve:
module R extends RU(-45); /* Vererbungsmechanismus */
module A extends F(10);
Axiom ==> L(100) R X R A R X;
X ==> X F0 X R A R X F0 X;
Sierpinski-Dreieck (Realisierung als geschlossene Kurve, Verwendung von Hilfssymbol X für Insertion des inneren Dreiecks):
L(50) RU(90) B F0 X F0 RU(-120) F0 F0 RU(-120) F0 F0;
F0 F0 F0;
X RU(-120) F0 X F0 RU(120) F0 X F0 RU(120) F0 X F0 RU(-120);
B B LMul(0.5);
Verzweigungsbeispiel:
F0 F0 [ RU(25.7) F0 ] F0 [ RU(-25.7) F0 ] F0 ;
Ergebnis nach 7 Schritten:
(Startwort L(10) F0)
Verzweigung, alternierende Zweigstellung und Verkürzung:
L(10) F0 A ;
A LMul(0.5) [ RU(90) F0 ] F0 RH(180) A ;
welche Struktur liefert
F(10) A ;
A [ RU(-60) F(6) RH(180) A Sphere(3) ] [ RU(40) F(10) RH(180) A Sphere(3) ];
Sphere Z; ?
(F(n) liefert Linie der vorgegebenen Länge n,Sphere(n) eine Kugel mit Radius n)
Stochastische L-SystemeVerwendung von Pseudozufallszahlen
Beispiel:
deterministisch stochastischfloat c = 0.7;
Axiom ==> L(100) D(5) A;
A ==> F0 LMul(c) DMul(c) [ RU(50) A ] [ RU(-10) A ];
float c = 0.7;
Axiom ==> L(100) D(5) A;
A ==> F0 LMul(c) DMul(c) if (probabiliy(0.5)) ( [ RU(50) A ] [ RU(-10) A ] ) else ( [ RU(-50) A ] [ RU(10) A ] );
Erzeugung einer Zufallsverteilung in der Ebene:
Axiom ==> D(0.5) for ((1:300))
( [ Translate(random(0, 100), random(0, 100), 0)
F(random(5, 30)) ] );
Ansicht von oben schräg von der Seite
Erweiterung des Symbol-Konzepts:
Lasse reellwertige Parameter nicht nur bei Turtle-Kommandos wie "RU(45)" und "F(3)" zu, sondern bei allen Zeichen
parametrische L-Systeme
beliebig lange, endliche ParameterlistenParameter werden bei Regel-Matching mit Werten belegt
Beispiel:
Regel A(x, y) F(7*x+10) B(y/2)
vorliegendes Zeichen z.B.: A(2, 6)nach der Regelanwendung: F(24) B(3)
Parameter können in Bedingungen abgeprüft werden(logische Bedingungen mit Java-Syntax):
A(x, y) (x >= 17 && y != 0) ....
Welche Struktur wird von folgendem L-System erzeugt?
[ RU(90) M(1) RU(90) A(1) ] A(1);
A(n) F(n) RU(90) A(n+1);
Welche Struktur wird von folgendem L-System erzeugt?
[ RU(90) M(1) RU(90) A(1) ] A(1);
A(n) F(n) RU(90) A(n+1);
Variante:
in der zweiten Regel "RU(90)" etwa durch "RU(92)" ersetzen.
Interpretationsregeln
Einbau einer weiteren Regelanwendung unmittelbar vor der grafischen Interpretation (ohne Wirkung auf die nächste Generation)
Interpretationsregel-Anwendung
Turtle-Interpretation
public void run(){ [ Axiom ==> A; A ==> Scale(0.3333) for (i:(-1:1)) for (j:(-1:1)) if ((i+1)*(j+1) != 1) ( [ Translate(i, j, 0) A ] ); ] applyInterpretation();}
public void interpret() [ A ==> Box; ]
Beispiel:
public void run(){ [ Axiom ==> A; A ==> Scale(0.3333) for (i:(-1:1)) for (j:(-1:1)) if ((i+1)*(j+1) != 1) ( [ Translate(i, j, 0) A ] ); ] applyInterpretation();}
public void interpret() [ A ==> Box; ]
(a)
(b) (c)A ==> Sphere(0.5); A ==> Box(0.1, 0.5, 0.1) Translate(0.1, 0.25, 0) Sphere(0.2);
was wird durch dieses Beispiel erzeugt?
public void run(){ [ Axiom ==> [ A(0, 0.5) D(0.7) F(60) ] A(0, 6) F(100); A(t, speed) ==> A(t+1, speed); ] applyInterpretation();}public void interpret() [ A(t, speed) ==> RU(speed*t); ]
Kontextsensitivität
Abfrage eines Kontexts, der vorhanden sein muss, damit eine Regel anwendbar ist
Angabe des Kontexts in (* .... *)
Beispiel:
module A(int age);module B(super.length, super.color) extends F(length, 3, color);Axiom ==> A(0);A(t), (t < 5) ==> B(10, 2) A(t+1);A(t), (t == 5) ==> B(10, 4);B(s, 2) (* B(r, 4) *) ==> B(s, 4);B(s, 4) ==> B(s, 3) [ RH(random(0, 360)) RU(30) F(30, 1, 14) ];
Der Schritt zu relationalen Wachstumsgrammatiken
Nachteil von L-Systemen:• in L-Systemen mit Verzweigungen (über Turtle-Kommandos) nur 2 mögliche Relationen zwischen Objekten: "direkter Nachfolger" und "Verzweigung"
Erweiterungen:
• Zulassen weiterer Relationstypen (beliebig wählbar)• Zulassen von Zyklen ( Graph-Grammatik)
• Grammatik modifiziert dann direkt den Graphen, Umweg über String-Codierung entfällt (bzw. wird nur noch für Regel-Input gebraucht)
"relationale Wachstumsgrammatik"
außerdem Nachteil der Turtle-Interpretation von L-Systemen: Segmente sind nur Zylinder, keine Objekte im Sinne der OOP
Erweiterungen:
• Knoten des Graphen können beliebige Objekte sein (auch Grafikobjekte)
• Einbettung von Code einer höheren, imperativen oder objektorientierten Programmiersprache in die Regeln (für uns: Java)
3. RELATIONALE WACHSTUMSGRAMMATIKEN (RGG: Relational Growth Grammars)
allgemeiner Aufbau einer Regel einer RGG:
eine RGG-Regel und ihre Anwendung in grafischer Form:
Regel:
Anwendung:
Kanten-Markierungen repräsentieren verschiedene Artenvon Relationen:
• ist Nachbar von
• enthält
• trägt
• codiert (genetisch)
• ist gepaart mit
• (...)
auch möglich: Darstellung von multiskalierten Strukturen
RGG als Verallgemeinerungen von L-Systemen:
Zeichenketten entsprechen speziellen Graphen
In Textform schreiben wir allgemeine Kanten als -kantensorte->
Kanten des speziellen Typs "Nachfolger" werden als Leerzeichen geschrieben (statt -successor->)
Sonderformen von RGG-Regeln:
Aktualisierungsregeln (Regelpfeil ::> ): es werden nur Parameter verändert
Instanzierungsregeln: einzelne Zeichen werden in Substrukturen aufgelöst, ohne Einfluss auf den nächsten Entwicklungsschritt
Realisierung in einer Programmiersprache:
Sprache XL (eXtended L-system language)
• RGG-Regeln in Blöcken organisiert Kontrolle der Reihenfolge der Regelanwendungen
• Turtle-Kommandos als Knoten erlaubt
• Knoten sind Java-Objekte
• Sprache Java als Rahmen für die gesamte RGG Benutzer kann Konstanten, Variablen, Klassen... definieren
• globale Sensitivität, graph queries
Beispiel: Wachstum nur, wenn genügender Abstand zu anderen F-Objekten
module A(int s);Axiom ==> F(100) [ RU(-30) A(70) ] RU(30) A(100);a:A(s) ==> if ( forall(distance(a, (* F *)) > 60) ) ( RH(180) F(s) [ RU(-30) A(70) ] RU(30) A(100) )
ohne die Bedingung mit der Bedingung
XL wird "verstanden" von der interaktiven 3D-Plattform GroIMP (Growth-grammar related Interactive Modelling Platform)
• GroIMP stellt Objekte für die 3D-Visualisierung bereit. Diese können in XL verwendet werden.
• GroIMP ist ein open source-Projekt; siehe
http://www.grogra.de.
Beispiel eines mit GroIMP realisierten Pflanzenmodells (Gerste):
Recommended