Warum abstrakte Datentypen? (Q797272)

Die klassischen Hilfsmittel zum rekursiven Aufbau von Datenstrukturen - Tupelbildung und Variantenbildung - sind unzureichend, wenn nicht zusätzlich Kongruenzrelationen eingeführt werden. Dies führt auf natürliche Weise zu abstrakten, algebraischen Datentypen, deren Modelle ja gerade gewissen Kongruenzrelationen über beliebigen Termbildungssystemen gehorchen. Es kann nicht-isomorphe Modelle geben, die man durch verschiedene Homomorphismen über der Term-Algebra erhält (''Rechenstrukturen''); dies hat den Vorteil, mehr Entwurfs- Freiheit zu lassen. Die Konstruktion von Modellen wird für einige exemplarische Fälle diskutiert. Es wird gezeigt, daß für gewisse abstrakte algebraische Typen durch Tupelbildung und Variantenbildung allein keine Modelle erhältlich sind; die klassische Theorie braucht das zusätzliche Hilfsmittel der ''Zeiger'', um solche ''unendlichen'' Objekte einführen zu können.