Daten, Typen
Die Daten der "Computer"-Welt sind in Klassen eingeteilt, in die sogenannten (Daten-)Typen. So gibt es:
    Ganze Zahlen (integer),
    Buchstaben (character),
    Worte (string),
    Variable (Pointer, Adressen),
    Programme (procedure),   etc.
Wir haben zwei Daten-Konstanten mit dem Namen "#" und "nil", das Datum "nicht belegt" und das Datum "nicht definiert". Diese Daten haben keinen Typ bzw. sie kommen in jedem Typ vor.

Variable
Es gibt bestimmte Daten - wir nennen sie Variablen -, die die Eigenschaft haben, daß ihnen andere Daten zugeordnet sind: sie stehen für andere Daten, sie enthalten andere Daten. Den Inhalt einer Variablen, also das Datum, das diese Variable enthält, wollen wir seinen Wert nennen. Die Variablen nennen wir auch Adressen, beide Begriffe wollen wir gleichwertig nebeneinander gebrauchen. Wir können uns anschaulich darunter Speicherplätze vorstellen, die Daten enthalten können. Jede Adresse hat einen Typ, der sagt, welche Daten diese Adresse enthalten kann. Es gibt Integeradressen, aber auch Integer-Adress-Adressen, die selber als Daten Integer-Adressen enthalten können etc. Zu Anfang eines Programms sind alle Variablen mit dem Wert # belegt (was man auch so deuten kann, daß sie eigentlich nicht belegt sind). Diese Variablen nennen wir auch frei.

Namen, freie Variablen, bereitstellen
Daten können Namen (Deskriptoren) bekommen, mit denen wir diese im Programmtext ansprechen können. Diese Namen sind Zeichen oder endliche Zeichenfolgen. Für die natürlichen Zahlen sind dies die Zeichen 1,2,3,.. bzw. die Zeichenfolgen 11,12,13,14,..etc. Für die Buchstaben haben wir die Zeichen a,b,c,d,.. und für Strings Zeichenfolgen wie 'Hello world'. Das konstante Datum "nicht definiert" hat den Namen "nil".

Auch Adressen können solche Namen bekommen. Dies sind jedoch keine konstanten Namen, die immer diese eine Adresse benennen, sondern sie werden erst  in einem Programmtext gesetzt durch eine Deklaration. Durch  die Deklaration  "var i: integer"  wird eine freie Adresse vom Typ Integer bereitgestellt und mit dem Name i benannt, der jetzt allerdings in diesem Programm unlösbar mit dieser Adresse verbunden ist. Bereitstellen heißt, den Wert der Adresse von # auf nil setzen, d.h. die Adresse wird gleichzeitig initialisiert, mit einem Initialwert belegt. Damit ist sie nicht mehr frei.

Statements
Die einfachsten Statements legen Variable an –stellen Adressen mit Namen bereit –legen Daten in die Adressen und vergleichen Werte von Adressen. val(x) sei der Wert, den die Adresse x zu einer gewissen Zeit beinhaltet. Die Funktion val gibt also die Belegung der Variablen in dem momentanen Zeitpunkt an.

Statements:	Erklärung:	Ergebnis:
var x,y:integer	Zwei freie Adressen  vom Typ "integer" werden bereitgestellt und mit "x" bzw. "y" benannt.	val(x) = val(y) = nil
x := 4	lege in die Adresse (mit Namen) x den Integer 4	val(x) = 4
x := y	lege den Wert von Adresse y in die Adresse x .	val(x) = val(y)
x := x+y	addiere die Werte der Adressen x und y und lege die Summe in Adresse x	val(x) = val(x)+val(y)
if x=4	wenn der Wert von Adresse x der Integer 4 ist	Test: val(x) = 4
if x=y	wenn die Werte der Adressen x und y gleich sind.	Test: val(x) = val(y)

Man beachte dabei, daß das Zeichen :=  nur wenig mit dem Gleichheitszeichen der Mathematik zutun hat. Grundsätzlich gilt:
 

:=	links von := steht immer der Namen einer Adresse, während rechts davon immer ein Datum gemeint ist, das in diese Adresse paßt, also ihren Typ hat.
=	links und rechts von dem Zeichen  =  sind immer Daten  vom selben Typ gemeint.

Datenstrukturen
Man kann mehrere Daten zu einer Datenstruktur zusammenfassen. Eine Datenstruktur besteht aus  einer oder mehreren Datenmengen zusammen mit einer oder mehreren  Operationen, die den Zugriff auf die Daten steuern.

Eine Struktur im Sinne der Mathematik besteht aus einer oder mehreren Mengen (den Trägermengen) und Operationen darauf. Sie bildet die Menge aller Worte über den Symbolen 0 und 1 zusammen mit der Operation Konkatenation (Zusammenkleben) eine Struktur, die wir ({0,1}*, konkat) schreiben können. Die Menge der ganzen Zahlen (Integer) zusammen mit den Operationen + und - bilden eine Struktur ( I,+,-). Ein Vektorraum über einem Skalarkörper ist ein Beispiel für eine Struktur mit mehreren Trägermengen: der Menge der Vektoren und der Menge Skalare.

Eine Datenstruktur ist nun genau solch eine Struktur. Sie besteht aus einer oder mehreren Mengen von Daten und Operationen auf diesen Mengen. Definiert man eine solche Struktur lediglich durch Angabe von Axiomen (oft Gleichungen zwischen verschiedenen Ausdrücken, die man mit diesen Operationen bilden kann), so spricht man auch von einer "abstrakten Datenstruktur". Leider sagt man noch häufiger "abstrakter Datentyp" (ADT) obwohl man natürlich nicht nur die Daten meint, sondern auch die Operationen, also eine Struktur.

Die  Datenstruktur "Array".

Wir fassen n Integer zusammen zu einer Einheit, einem n-Tupel. Ist (n1, .., n99) ein solches 99-Tupel von Integern, so selektiert uns die
Projektionsfunktion pr(10,(n1, .., n99)) = n10 gerade den 10-ten Integer daraus. Wenn wir durch Deklaration eine freie Array-Adresse A bereitstellen, so wollen wir sie auch initialisieren. In diesem Fall eines Integerarrays der Länge 99 belegen wir A mit dem 99-Tupel (nil,...,nil) von lauter nil's als Anfangswert. D.h. mit der Bereitstellung hat die Varaible A bereits einen vordefinierten Wert.

Es gibt natürlich auch kompliziertere Typen. Deklarieren wir A als einen array[1..99] of T und ist T bereits ein komplexer Typ (sagen wir ein array[1..88] of array[1..77] of integer), so müssen wir überlegen, was der Anfangswert von A sein soll. Wir setzen die Daten des letzten Typs (hier integer) auf nil, damit ist der ganze komplexe Typ festgelegt (hier ein 99-Tupel von 88-Tupeln von 77-Tupeln aus nil's).

Die Datenstruktur "Integer-Array" der Länge 99  besteht also aus der Menge der  99-Tupel von Integern, der Menge der  Integern selbst, einer Projektionsfunktion [], die einem Array und einer Position den entsprechenden Integer liefert (A[9]), einer Insertfunktion, die einem Tupel, einer Position und einem Wert das Tupel zuordnet, das man erhält, wenn man den Wert in diese Position einfügt (A[9]:=4),einer Initialisierungfunktion, die abfragt, ob eine Komponente des Arrays schon einen Wert ungleich nil  zugeordnet bekommen hat, also eine Funktion, die einem Tupel und einer Position einen Wert true oder false zuordnet und schließlich dem konstanten nicht initialisierten reinen nil-Tupel E = (nil,...,nil).
 

Statements	Ergebnis:
var A: array[1..99]         of integer	stellt eine freie Adresse bereit, die ein 99-Tupel von Integern aufnehmen kann. Die Adresse hat den Namen A. val(A) = (nil,...,nil)
A[9]:=4     x:=A[9] A[i]:=4	val(A[9]) = pr(9, val(A)) = 4. Außerdem ist das 99-Tupel val(A) geändert: an der Position 9 wurde eine 4 einschrieben val(x) = val(A[9])=pr(9, val(A)) = 4 val(A[i]) = pr(val(i), val(A)) = 4. Ebenso hat sich val(A) geändert

Man beachte, daß im letzten Statement eine Komponente des Arrays in der Adresse A durch Angabe der Integeradresse i selektiert wurde und nicht durch Angabe eines Integers. Diese Art der Adressierung, bei der nicht die Adresse selbst, sondern eine Adresse angegeben wird, in der die Adresse liegt, nennt man indirekte Adressierung. Die Benennung der Komponenten muß nicht durch Integer erfolgen, es kann auch jeder andere ordinale Datentyp sein.

Wir können die Datenstruktur Array[1..n] of W auch abstrakt definieren, wie folgt:
Sei A die Menge dieser Arrays, [1..n] die Menge der ersten n  natürlichen Zahlen und B = {true, false} die Menge der Wahrheitswerte und # eine universelle Konstante, die in jedem Typ vorkommt (und als undefiniert oder "Fehler" interpretiert werden kann) . Dann definieren wir die Datenstruktur (based on ([1..n], suc, 0) und (B, true, not, or, and)) mit den Trägermengen A, W , [1..n], B und den Operationen select: A x [1..n] --> W, insert: A x [1..n] x W --> A, isinit: A x [1..n] --> B und der Konstanten E (nicht initialisierter Array) mit Axiomen folgender Art:

    isinit(E, i) = not true,
    isinit( insert(A, i, a) , i ) = true,
    isinit( insert(A,j,b), i) = isinit( A, i ),  falls i ungleich j,
    insert( insert(A,i,b), i, a) = insert(A, i,a),
    insert( insert(A,j,b), i, a) = insert( insert(A, i,a), j, b ),  falls i ungleich j,
    isinit(A, i) = not true ==> select(A,i) = #
    select( insert(A,i,a), i ) =  a,
    select( insert(A,i,a), j ) =  select( A, j ), falls i ungleich j.

Die Axiome beschreiben, welche Terme der freien Termalgebra über den Operationen isinit, select und insert äquivalent sind, d.h. dasselbe Element in unserer Datenstruktur beschreiben. Faktorisieren wir die Termalgebra nach dieser Äquivalenzrealation, so bekommen wir ein Struktur, die isomorph ist zu unserer Datenstruktur. Zwei Terme sind äquivalent, wenn man sie durch Ersetzungen mithilfe obiger Gleichungen in einen gemeinsamen Term überführen kann.

"based on (IN,suc, 0) und (B, true, not, or, and)" soll heißen, daß wir hier die beiden angeführten Datenstrukturen benötigen, um unsere Datenstruktur Array (A, W, IN,  B, isinit, select, insert) zu definieren, wir diese also schon als definiert voraussetzen. Die Axiome dieser Datenstrukturen müßten eigentlich dazugeschrieben werden.
 

Der Datenstruktur "Record"

Ein Record ist wie ein Array ein Tupel von Daten mit dem Unterschied, daß die Komponenten nicht indirekt adressiert werden können, sondern mit konstanten Namen eines Aufzählungstyps, und daß die Komponenten verschiedenen Typ haben können.

Die Datenstruktur "Record" besteht aus einer definierten Klasse von Tupeln von Daten möglicherweise verschiedenen Typs (wobei die Indexmenge ein Aufzählungstyp ist), der Indexmenge, der Selektionsfunktion "." , die einem Datentupel und einem Komponentennamen (Index) das entsprechende Datum zuordnet (person.name), der Insertfunktion die einem Record, einem Index und einem Wert  einen neuen Record zuordnet, den man erhält, wenn man an der Indexstelle des alten Records diesen Wert einschreibt (person.name:=meier ) und der Isinitfunktion, welche zu einem Record und einem Index sagt, ob die entsprechende Stelle schon belegt wurde oder noch gleich nil  ist . Der Anfangswert nach der Deklaration ist ein Tupel von den Anfangswerten der jeweiligen Typen, die in den Komponenten des Tupesl zu stehen haben.
 

Statement

Ergebnis:

type karte=       record        name: string;        ort: string;        tel: integer;      end;   var person: karte;     person.name:=meier; person.ort :=cottbus person.tel := 12345

eine Adresstyp wird definiert und mit "Karte" benannt, der Tripel von Daten verschiedenen Typs enthalten kann. Die Komponenten haben die Namen "name", "ort" und "tel".       Eine freie Adresse mit Namen "person" vom Typ "Karte" mit dem Anfangswert (nil,nil,nil) wird bereitgestellt.  val(person.name) = pr(name, val(person)) = meier val(person.ort) = pr(ort, val(person)) = cottbus val(person.tel) = pr(tel, val(person)) = 12345

Datenstruktur Stack

Wie bei einem Array kann man mehrere Daten gleichen Typs zusammenfassen zu einer Reihe. Im Unterschied zum Array kann diese Reihe beliebig lang werden. Allerdings kann man nicht wie im Array auf jeden Wert zugreifen, indem man eine Position angibt. Man kann lediglich den letzten Wert der Reihe sehen, man kann diesen letzten Wert entfernen (löschen) und man kann an die Reihe einen Wert anhängen. Man nennt diese Struktur "Stack" oder "Stapel", weil man wie bei einem Kartenstapel nur die oberste Karte sehen und entfernen kann und eine neue Karte nur oben auflegen kann.

Formaler kann man sich einen Stack als eine Datenreihe, wie eine Zeichenreihe, vorstellen - ein Wort von Daten - an das man hinten ein Datum anhängen darf, dessen letztes Datum man löschen darf und und von dem man nur das letzte Datum identifizieren (auslesen) kann. Ein Stack vom Typ Integer ist also eine Reihe von Integern auf dem die Operationen isempty, top, pop und push ausgeführt werden können, wobei diese Funktionen wie folgt definiert sind:
(S sei immer ein Stack, d.h. eine Datenreihe, und A sei ein einzelnes Datum, SA sei die Reihe S, an die das Datum A gehängt wurde)
isempty(S) = true, wenn der Stack S leer ist, d.h. wenn er kein einziges Datum enthält.
top(SA) = A, d.h. top(S) liefert uns das oberste, sichtbare Datum von S, das Datum an der Spitze.
pop(SA) = S, d.h. pop(S) löscht gerade das Spitzendatum des Stacks S.
push(S,A) = SA, d.h. push(S,A) legt dem Stack S ein neues Spitzendatum A auf.

Abstrakt kann man die Datenstruktur D-Stack  based on (B, true, not, or, and) wie folgt definieren:
Wir haben die Trägermengen K (Menge der Stacks) , D die Menge der Daten, B (Menge Boolean ) und die Operationen isempty: K --> B, top: K --> D, pop: K --> D und push: K x D --> K und die Konstante  E (leerer Keller) und die Konstante # (Fehler oder undefiniert). Axiome sind:
    isempty(S) = true
    isempty(push(S,A)) = not true
    pop(E) = #,
    top(E) = #,
    pop( push(S,A) ) = S
    top( push(S,A) ) = A
 

Datenstruktur Pointer

In bestimmten Zusammenhängen nennt man Adressen auch Pointer, weil sie auf ihren Wert "zeigen". Entsprechend nennt man Adressvariablen, also Adressen, deren Wert Adressen sind, auch Pointervariable. Wir werden diesen Begriff aber zunächst meiden, um keine Verwirrung durch Begriffsvielfalt zu erzeugen.  Sei p eine Integeradressvariable. Der Befehl new(p) bewirkt, daß in die Adresse p eine freie Integeradresse gelegt wird. Die Selektionsfunktion ^  angewandt auf die Variable p - also der Ausdruck p^  - liefert uns die Integer-Adresse, die in der Adress-Variable p liegt.

Ist V die Menge (der Raum) aller Adressen (die man sich, wenn man will, auch durchnummeriert denken kann) und D die Menge aller Daten. Dann können wir eine Belegungsfunktion  b: V --> D definieren, die jeder Adresse ihren Wert zuordnet, die Funktion, die die Belegung der Adressen durch Werte beschreibt. Sei W die Menge aller dieser Belegungsfunktionen. Dann besteht die Datenstruktur aus den Belegungsfunktionen zusammen mit den Operationen ^  und new. Hierbei  ist die Selektionsfunktion ^ definiert durch ^(b,p) = b(p) und die Konstruktorfunktion durch  new(b,p) = b', wobei b' aus b entsteht, wenn man die Variable p mit einer Integeradresse belegt, die in b noch frei ist, d.h. den Wert #  hat, und diese Integeradresse mit dem Wert nil, womit sie in b' nicht mehr frei ist. Hierbei spielt es keine Rolle, ob man sich immer die erste freie Adresse in einer gedachten Nummerierung der Adressen nimmt oder mithilfe eines Auswahloperators irgendeine freie Adresse. Wo die Adresse in dem Adressraum V liegt, spielt für das Programm keine Rolle und ist durch das Programm auch nicht ausfindig zu machen.
 

Statements	Ergebnis:
var p,q : ^integer;	Zwei  freie Adressen mit den Namen p und q  vom Typ Integer-Adresse werden bereitgestellt. Diese beiden Adressen haben den Anfangswert nil.
new p;	eine freie Adresse vom Typ Integer wird bereitgestellt und in die Variable p gelegt. Sie ist jetzt unter p^ abrufbar. Die Adresse hat zunächst den Wert nil.
p^:=4;	val(val(p)) = 4
new p;	eine neue freie Adresse vom Typ Integer wird bereitgestellt und nun diese Adresse in die Variable p gelegt. Jetzt ist mit p^ diese Adresse gemeint.
p^:=x;	val(val(p)) =val(x)
y:=p^;	val(y) = val(val(p))
q:=p	val(q) = val(p), die Variablen p und q enthalten dieselbe Adresse
q^:=p^	val(val(q)) = val(val(p)), die möglicherweise verschiedenen Adressen in p und q enthalten denselben Wert.