Induktive Algorithmen in OOP-Sprachen (C++, Java, ...)

[ComFreek]

Angespornt durch die lange und informative Unterhaltung neben an (Sichtbarkeit Klassenvariablen) poste ich hier mal eine Frage, die ich schon länger hatte

Angenommen ich möchte Abstract Syntax Trees (ASTs) in meinem Programm verwalten. Genauer gesagt ASTs von mathematischen Ausdrücken/Termen im Lambdakalkül, aber das ist nicht wirklich relevant für die Frage, erreicht aber, dass das Problem im trivialen Fall sich nicht in Luft auflöst. Dazu habe ich folgende Klassen in Scala:

// Example: λx. x + x
// Would be represented as: Binding(Context with 'x', Application(Identifier('+', List(Variable('x'), Variable('x')))))

abstract case class Term

// Example: λx. x + x
// Definition of Context irrelevant
case class Binding(context: Context, body: Term) extends Term

// Example: x + x (application of identifier + to arguments x and x)
case class Application(function: Term, arguments: List[Term]) extends Term

// Example: x
case class Variable(name: String) extends Term

// Example: +
case class Identifier(name: String) extends Term

Übersetzung für Nicht-Scala-Kenner: Case Classen als normale immutable Klassen vorstellen, Parameter in den runden Klammern sind nur Syntactic Sugar für Konstruktoten mit eben jenen Konstruktorargumenten.

Induktiver Algorithmus: Jetzt möchte ich z. B. alle Identifiers eines Terms sammeln. Das geht ganz einfach wie folgt in Scala:

def collectIdentifiers(term: Term): List[String] = term match {
  case Binding(_, body) => collectIdentifiers(body)
  case Application(fun, args) => (fun :: args).flatMap(collectIdentifiers)  // prepend fun to arg list and then flatMap!
  case Variable(_) => Nil
  case Identifier(name) => List(name)
}

Wie würde das in anderen (nicht-funktionalen) OOP-Sprachen aussehen?

Ich habe gerade nur zwei Optionen im Kopf:

1. Der Term-Klasse eine abstrakte Methode collectIdentifiers spendieren und diese in allen Kindklassen überladen.
2. Analog zur Scala-Lösung, aber mit sehr unschönem instanceof-Checking.

An Option (1) stört mich, dass ich also alle Klassen mit meinem Algorithmus "zumülle". Ich habe also keine saubere Trennung von Repräsentation des ASTs und Verarbeitung.
Insbesondere gibt es ja unzählige Algorithmen, die man auf ASTs ausführen möchte! Mitunter auch konkurrierende, sodass man auch auf Namensgebung Acht geben müsste.

Fällt einem von euch eine dritte bessere Möglichkeit ein?

Ich habe in letzter Zeit viel mit Scala gearbeitet und mich sehr mit funktionalen Sprachen i. Allg. angefreundet Wobei ich 'purity' zwar theoretisch interessant finde, aber für großere Projekte wohl eine 'impure' Sprache wie Scala auch ihre Vorzüge hat.

 

[melmager]

ich sehe auch nur Lösung 1 :-(
Und ja OOP will keine Trennung zwischen Verarbeitung und Daten
Aber mal ein ganz andre Version:
ReactiveX
Sprich ein ganz andrer Programmieransatz - alles ist ein Ereignis das gefiltert und verteilt und verarbeitet wird ...
nicht funktional nicht OOP sondern den dritten Weg Reactive

 

[cwriter]

Beim Stichwort "AST" fällt mir schlicht das Visitor-Pattern ein. Die Variablen können dann in eine Liste/Array geladen werden, die by reference übergeben wird. Das ist recht unschön, aber funktioniert relativ gut, wenn man den Boilerplate-Code durch hat - ist halt keine 10-Zeilen-Lösung, dafür wiederverwendbar.

Analog zur Scala-Lösung, aber mit sehr unschönem instanceof-Checking.

Scheint mir nicht allzu schlimm? Ist ja eigentlich dasselbe wie die case-Statements im Funktionalen Code.


Gruss
cwriter

 

[ComFreek]

Danke für Eure Antworten!

Scheint mir nicht allzu schlimm? Ist ja eigentlich dasselbe wie die case-Statements im Funktionalen Code.

Tatsache. Wenn man die Kindklassen von Term jeweils als 'final' markiert, hat man schon die Hälfte der Probleme entsorgt, die instanceof bringt. Es bleibt nur noch, dass es immer noch möglich ist, eine neue Kindklasse von Term zu erstellen, die dann nicht behandelt wird. Dieses Problem wird erst zur Laufzeit festgestellt, wohingegen man in Scala das zur Compilezeit überprüfen lassen kann ("exhaustiveness of pattern matching").

Beim Stichwort "AST" fällt mir schlicht das Visitor-Pattern ein.

Danke für den Pointer. Ich habe mich gerade mal etwas ins Visitor-Pattern eingelesen. Das scheint ein wenig wie Pattern Matching für arme Sprachen zu sein

ReactiveX
Sprich ein ganz andrer Programmieransatz - alles ist ein Ereignis das gefiltert und verteilt und verarbeitet wird ...
nicht funktional nicht OOP sondern den dritten Weg Reactive

Ich habe mich mit React noch gar nicht beschäftigt, aber immer mal wieder als der neue Hype in der JS-Welt gehört
Ereignisse klingen aber so, dass ich die Struktur des Termes verliere. Entweder sende ich den ganzen Term als Stück oder seine (feingranularen) Bestandteile. Im ersten Fall habe ich nichts erreicht, im zweiten weiß ich nicht mehr, wie ich die Ergebnisse zusammensetzen soll. (Gut, in meinem Beispiel mache ich immer Listenkonkatenation, da ist die Reihenfolge auch egal, also fällt der letzte Punkt weg.)