Programmierparadigmen #

aus SPEKTRUM DER WISSENSCHAFT · Juni 2007

Auch diese Seite ist an eine Vorlesung der Universität angelehnt. In dieser Vorlesung geht es um die Verschiedenen Konzepte der Programmiersprachen. Die Programmiersprachen die in der Vorlesung besprochen wurden, sind Prolog, Ruby und Haskell. Zu den einzelnen Programmiersprachen wird im laufe der Näher eingegangen. Weitere Thema der Veranstalltung sind Grammatiken und EBNF.

Der Wikipediaartikel über Programmiersprachen enthält eine Auflistung von verschiedenen Sprachen. Die Programmiersprachen können in verschiedene Gruppen unterteilt werden.

imperative Sprachen	Frotran Cobol C Pascal Ada	Wort-für-Wort Verarbeitung auf einem in kleine Einheiten gegliederten Speicher. Programmieren durch Veränderung des Speicherzustandes mit Hilfe von Wertzuweisungen. maschienenorientierte Daten- und Programmstrukturen, relativ dicht an den Möglichkeiten der von Neumann-Maschine
objektorientierte Sprachen	Simula Smalltak C++ Java
logische Sprachen	Prolog
funktionale Sprachen	Lisp Miranda Haskell	Funktionen sind Objekte erster Klasse, sie können als Parameter übergeben und als Resultat zurückgegeben werden. Baukastenprinzip zur Konstruktion von Funktionen höheren Typs, Funktionale konstruieren Funktionen auf der Basis andere Funktionen. Referentielle Transparenz ist ein geschlossener Ausdruck der immer den gleichen Wert, unabhängig von Ort im Programm und Zeit in der Ausführung, hat. Polymorphie in funktionalen Sprachen besagt, dass eine Funktion keinen festen Typ haben muss und dennnoch wohlgetypt sein kann. Innerhalb einer Klasse von Typen lässt sich ein allgemeinster Typ inferieren. Funktionale sind praktisch immer polymorph. Grundprinzipien: nur Ausdrücke, keine Anweisungen keine Zuweisungen, da kein Speichermodell für Variablen. Rekursion als zentrale Kontrollstruktur für Widerhollungen.
Skriptsprachen	Perl Javascript Python Ruby
Auszeichnungssprachen	SGML HTML-1 XML HTML-4

Die verschiedenen Paradigmen können dem Link entnommen werden. Weiter ist zur deklarativen Programmierung folgendes zu sagen, dass der Programmierer spezifiert, welche Fragen er gelöst sehen möchte, aber nicht, wie sie gelöst werden sollen. Es gibt keine ausgezeichnete Richtung in der Berechnung, gebundene Parameter stellen Eingaben dar, ungebundene die Ausgaben. Die Programmausführung wird als Ableitungs- bzw. Beweisprozeß gesehen. Der Programmierer gibt Behauptungen ein, diese werden vom System verifiziert oder falsifiziert. Es werden die Bedingungen angegeben, unter denen die Behauptung wahr ist. Fazit: Im Gegensatz zu dem imperativen Paradigma, bei dem das WIE im Vordergrund steht, fragt man in der deklarativen Programmierung nach dem WAS, das berechnet werden soll. Es wird also nicht mehr der Lösungsweg programmiert, sondern nur noch angegeben, welches Ergebnis gewünscht ist.

Syntax und Semantik #

Syntax	Struktur der Sprache Zeichensatz / Alphabet Grundelemente: Lexeme - Tokens Strukturelle 'Wohlgeformtheit' von Programmen bzw. Programmteilen
Semantik	Bedeutung von Programmen Bedeutung im Verständnis des Programmierenden Ergebnis der Abarbeitung auf einer Maschine (objektiv, 'operationale Semantik') Einhaltung von Typrestriktionen und speziellen Randbedingungen (Vermeidung der Division durch 0) Erfüllung eines Kontraktes (Ein-/Ausgabebedingungen) -> Programmverifikation

Grammatiken #

Syntaxdiagramm-Generator aus EBNF

Formale Grammatik Dangling Else

BNF #

'Kontextfreie' Grammatiken

 Terminal := "a", "b", "c"
 nicht Terminal := <A>,<B>,<C>,<N>

Grammatik:

 <N> ::= "a" <A> "b" <B> <C> "c"

EBNF #

POSTANSCHRIFT = ANREDE NAME ANSCHRIFT [LAND].
NAME = [TITEL] VORNAME ZUNAME.
ANSCHRIFT = (STRAßE | POSTFACH) PLZ ORT.
STRAßE = STRAßENNAME HAUSNUMMER.
POSTFACH = INSTITUTION "Postfach" POSTFACHNUMMER.
ANREDE = "Herrn" | "Frau".
TITEL = "Dr." | "Prof." | "Dipl.-Ing.".
VORNAME = "Hans" | "Fritz" | "Erna" | "Anneliese".
ZUNAME = "Müller" | "Schmidt" | "Meier" | "Wollenbrink".
STRAßENNAME = "Heideweg" | "Straußenstr." | "Blumenstraße" | "Jahnstr.".
HAUSNUMMER = "1" | "2" | "3" | "4" | "5".
INSTITUTION = "Universität" | "Anwaltskammer" | "Ministerium" | "Polizei".
PLZ = "12345" | "17437" | "23412" | "43523".
ORT = "Duisburg" | "Essen" | "München" | "Berlin" | "Hamburg".
POSTFACHNUMMER = "90 42 35" | "43 63 21" | "54 65 91" | "12 64 75".
LAND = "DEUTSCHLAND" | "ÖSTERREICH" | "SCHWEIZ" | "POLEN" | "FRANKREICH".

Quadrupel-Notation: 

G= (N,E,P,S)
N = (POSTANSCHRIFT,NAME,ANSCHRIFT,STRAßE,POSTFACH,
ANREDE,TITEL,VORNAME,ZUNAME,SRAßENNAME,HAUSNUMMER,
INSTITUTION,PLZ,ORT,POSTFACHNUMMER,LAND)

E= ('Herrn','Frau','Dr.','Prof.','Dipl.-Ing.','Hans',
'Fritz','Erna','Anneliese','Müller','Schmidt',
'Meier','Wollenbrink','Heideweg','Straußenstr.'
,'Blumenstraße','Jahnstr.','1','2','3','4','5',
'Universität','Anwaltskammer','Ministerium','Polizei',
'12345','17437','23412','43523','Duisburg','Essen',
'München','Berlin','Hamburg','90 42 35','43 63 21',
'54 65 91','12 64 75','DEUTSCHLAND','ÖSTERREICH',
'SCHWEIZ','POLEN','FRANKREICH')

S=POSTANSCHRIFT

P= (
POSTANSCHRIFT = ANREDE NAME ANSCHRIFT [LAND];
NAME = [TITEL] VORNAME ZUNAME;
ANSCHRIFT = (STRAßE | POSTFACH) PLZ ORT;
STRAßE = STRAßENNAME HAUSNUMMER;
POSTFACH = INSTITUTION "Postfach" POSTFACHNUMMER;
ANREDE = "Herrn" | "Frau";
TITEL = "Dr." | "Prof." | "Dipl.-Ing.";
VORNAME = "Hans" | "Fritz" | "Erna" | "Anneliese";
ZUNAME = "Müller" | "Schmidt" | "Meier" | "Wollenbrink";
STRAßENNAME = "Heideweg" | "Straußenstr." | "Blumenstraße" | "Jahnstr.";
HAUSNUMMER = "1" | "2" | "3" | "4" | "5";
INSTITUTION = "Universität" | "Anwaltskammer" | "Ministerium" | "Polizei";
PLZ = "12345" | "17437" | "23412" | "43523";
ORT = "Duisburg" | "Essen" | "München" | "Berlin" | "Hamburg";
POSTFACHNUMMER = "90 42 35" | "43 63 21" | "54 65 91" | "12 64 75";
LAND = "DEUTSCHLAND" | "ÖSTERREICH" | "SCHWEIZ" | "POLEN" | "FRANKREICH";
)

Herr  <<-- nicht in EBNF Herrn | Frau wäre OK
Hans Schmidt
Heideweg 3
12345 Hamburg
SCHWEIZ

Syntaxdiagramme #

Axiomatische Semantik #

• Weakest precondtions (schwächste Voraussetzung -> End-Bedingung)

Für alle z aus Z mit P(z) gilt: wenn S nach Start in z terminiert, so gibt es ein z' aus Z der Art, dass nach Beendigung von S Q(z,z') gilt.

  (*) {P} S {Q}
  {P} := Startbedingung
  S   := Programm(-teil)
  {Q} := Endbedingung

  {x-y >0} x=x-y; {x>0} und damit aber auch ...
  {x>y} x = x-y; {x>=0}

  Beweis: {x>y} {x-y >0} x = x-y; {x>=0} {x>0}

Variablen, Bindung, Typisierung #

Eine Variable hat zumindes folgende Verbindung.

Eine Variable, hat/nimmt einen Wert an. Ein Wert steht in einer Speicherzelle. Eine Variable bezieht sich auf eine Speicherzelle. Eine Variable hat einen Bezeichner (Namen). Eine Variable hat eine Gültigkeit ('scpoe' wie global / lokal und damit auch eine Lebensdauer). Eine Variable hat einen Typ.

Bezeichner sollte/muss eindeutig sein. Unterscheidbar (Namensräume), mit der Einschränkung keine reservierten Wörter verwenden (Sonderzeichen?).

  <Name>-<Referenz>-<Wert>
  Typ   - Adresse  - Speicher

  Vereinbarung: int x=0;

Art der Variablen	Lebensdauer in der Ausführung
globale Variable Klassenvariable	während der Programmausführung
Parametervariable lokale Variable	während eines Aufrufes (innerhalb des (bestimmten) Bereiches)
Objektvariable	bis zur Vernichtung des Objektes

public class Hello {
  private double x,y; // Klassenvariable
  public void op1(){
    int y,z; // lokale Variablen
    y =24;
    x = 17.5; // Wert der Klassenvariablen ändern
    ...
  }
  
  public void op2(){
    int x; // lokale Variablen, wobei x hier die Klassenvariable verdekt
    x = 10;
    y = x/2;
  }
  ...
}

static scope versus dynamic scope #

static scope

• wird zur Compilezeit ausgewertet.
• Compiler freundlich
• Überschaubarkeit, auch bezüglich Nebenwirkungen

dynamic scope

• wird zur Laufzeit ausgewertet.
• ferwendung von Variablen aus einem 'Arbeitskontext' heraus

int x = 0;
int f() {return x;}
int g() {int x =1; return f();}



g() --> ?

für static scope ist:  g() = 0
für dynamic scope ist: g() = 1

Typen #

  Die Typisierung ist die Einschränkung von Variablenwerten auf bestimmte Grundmengen (Typen).

Zu den einfachen Typen zählen

• ganze Zahlen
  • Java
    byte, short, int, long
  • C++
    short, int, long int, unsigned
  • Modula-2
    INTEGER, CARDINAL
• Wahrheitswerte
  • Java
    boolean = {true,false}
  • C
    wird durch einen Int repräsentiert.
• Zeichen eines Zeichensatzes
  • C/C++, Java
    char
• Aufzählungstypen (enumeration)
  • PASCAL
    Farbe = (rot,blau,gelb)
  • C
    typedef enum {rot,blau, gelb} Farbe;

Zusammengesetzte Typen

• einfache Mengen
• kartesisches Produkt
  Verbunde(records); Reihung (arrays);
• Vereinigung
• Funktion
• Potenzmenge

Typwandlung #

ausweitend	vom Spezialfall zur Allgemeinheit
einengend	von Allgemeinheit zum Fall
implizit	geht nur bei ausweitenden Umwandlungen
explizit	geht nur mit einem type cast

(streng) typisiert #

 TODO es gibt streng Typisierte und auch nicht stren Typisierte Sprachen

 streng: Haskell, Java
 nicht streng: Ruby, Python

Ausdrücke, Befehle, Kontrollstrukturen #

Ausdrücke (expressions) #

Arithmetische Ausdrücke

  x + y; y^2 = 2y; ; y = sin(x);

Aussagenlogische Ausdrücke

  a und b; wenn a dann b; a oder nicht b;

Operatoren, Präzedenz #

  x = 1
  x = ++x -1 --> x == 1, weil <==> x = (x+1)-1
  ++x ist also von R->L ausgewertet. Meist wird aber immer von L->R ausgewertet.

Befehle (statements) #

  x := x + y  # Zuweisung (assignment-statement)

Sequenzen und Kontrollstrukturen #

• IF <BED> THEN <ANW> ELSE <ANW2>

Prozeduren und Parameterübergabe #

• Call by value
  • Der Wert wird bei einer Übergabe Kopiert.
    x = 1; f(x);
    x hat immer noch den Wert 1,egal was in f damit gemacht wird.
• Call by reference
  • Der Wert wird als Referenz übergeben.
    x=1; f(x);
    f arbeitet mit dem einem x, die Ausgabe von x hängt von f ab.
• Call by value/return
  • Erzeugt zunächst einmal ein Kopie, jedoch wird am ende der Funktion der Wert wieder zurück gegeben.
    x=1; f(x,x);
    Der Wert hängt vo f ab, jedoch sind beide Parameter ersteinmal ein Kopie. Was x nun nach f für einen Wert hat, hängt ab von der implementierung. Zueinem ist es die Letzte Zuweisung, oder auch möglich der letzte Parameter hällt den Wert bei.

Funktionale Abstraktion #

Einführung in Haskell #

Rekursion als die Kontrollstruktur.

Buildin Funktions

• 3 * 5 = 15
• 4 ^ 2 = 16
• "Ich" ++ " " ++ "mag dich"
• pi
• sin pi /2 = 1.0
• not (3 > 5) = True
• succ 5 = 6
• round 6.59 = 7
• gcd 21 14 = 7
• length "hallo" = 5
• even 42 = True

Typen #

• Int, ganze Zahlen (30 Bit Genauigkeit)
• Integer, ganze Zahlen
• Float, Gleitkommazahl mit einfacher Genauigkeit
• Double, Gleitkommazahl
• Rational, Bruchzahl ohne Rundungsfehler
• Tupel (42,'a',True)
  Verschiedene Typen, jedoch feste Länge
• Listen 1,2,3
  nur ein Typ, Länge variable

Haskell kann je nach Funktion die Signatur automatisch erkennen.

-- Type-Definition
data Point = Pt { pontx, pointy :: Float}

pointx :: Point -> Float
pointy :: Point -> Float

--          Signatur
absPoint :: Point -> Float
absPoint p = sqrt (pointx p * pointx p + pointy p * pointy p)

-- Muster (Fallunterscheidung)
sum_list [] = 0
sum_list (x:xs) = x + sum_list xs

f 1 = 1
f n = n * f(n-1)
-- oder auch 
f n = if (n==1)
        then 1
        else n * f(n-1)
-- oder auch 
f n 
 | n == 1 = 1
 | otherwise = n * f(n-1) 


--     x für das gilt; wenn y:= 5 dann gilt: sum_list [1,4,9,16,25]
sum_squares y = sum_list [x * x | x <- [1..y] ]

Collatz-Reihe in Haskell #

next :: Int->Int
next x
    | mod x 2 == 0 = div x 2
    | otherwise    = 3 * x+1
    
steps :: Int->Int
steps 1 = 1
steps x = steps(next x)

stepsl :: Int->[Int]
stepsl 1 = [1]
stepsl x = x:stepsl(next x)

Typinferenz: flexible Typisierung #

Rekursion und Listen #

Objektorientierung #

Kapselung #

Polymorphismus #

Vererbung #

Objektorientierung im Vergleich (Überblick) #

Einführung in Ruby #

Funktionen und Closures in Ruby #

Logisch-relationale Programmierung #

Grundlagen #

Einführung in Prolog #

% permutation sort --> n!
% 1 2 3
% 1 3 2
% 2 1 3
% 2 3 1
% 3 1 2
% 3 2 1
permutiere([],[]).
permutiere(List,[E|PList]) :-
    loesche(E,List,RList),permutiere(RList,PList).
    
% loesche erstes element
loesche(X,[X|Xs],Xs).
% suche element Y und lösche es
loesche(Y,[X|Xs],[X|NewXs]) :-
    loesche(Y,Xs,NewXs)
    
% leer ist sortiert    
sortiert([]).
% 1 element ist sortiert    
sortiert([X]).
% wenn X1 < X2 dann ist es sortiert, wenn es für den rest auch gilt.
sortiert([X1,X2|Xs]) :-
    X1 =< X2, sortiert([X2|Xs]).    

perm_sort(List,SortList) :-
    permutiere(List,SortList),sortiert(SortList).

Perfekte Zahl #

Eine natürliche Zahl wird vollkommene Zahl (auch perfekte Zahl) gennant, wenn sie genauso groß ist wie die Summe ihrer positiven echten Teiler (d.h. aller Teiler außer sich selbst)

% prolog ist eine logische programmiersprache 
% in diesem programm wird ein mathematosches 
% problem gelöst, welches die perfekte zahl
% sucht. eine zahl ist perfekt, wenn gilt:
% -------------------------------------------
% 1: X ist eine Zahl
% 2: X hat natürliche Teiler
% 3: Die Summe aller Teiler ohne die Zahl selbst
%  ist die zahl X

% dieser ausdruck prüft die obrigen bedingungen, d.h
% ein , ist einem logischem UND ähnlich
perfekt(X) :-
  zahl(X),
  teiler(X,TL),
  sum_list(TL,N),
  % um aretmetische funktionen auszuwerten
  % wird =:= verwendet. weil:
  % = eine unifizierung bewirgt. 
  % ! F(X,6) = F(9,Z) --> X=9 , Z=6 
  N =:= X.

% in dieser sprache wird rekursion verwendet!
% die liste [X|Xs] ist wie bei haskel 
% X ist der listenkopf und Xs ist der rest der
% liste.
sum_list([],0).
sum_list([X|Xs],Sum) :-
  sum_list(Xs,Sum_Xs),
  % will man eine zuweisung machen nutzt man das 
  % wort is, da = schon vergeben ist und eine unifizirung
  % macht.
  Sum is X + Sum_Xs.


teiler(X,P) :-
  % ein set der folgende bedingungenn prüft.
  % T ist eine Variable für die gilt:
  % 1: T ist eine zahl
  % 2: T ist kleiner als das argument X
  setof(T, (zahl(T),T < X, teilt(T,X)), P).

% Y|X
teilt(Y,X) :-
  % hier wir der teiler geprüft,
  % Y ist nur dann teiler wenn eine 
  % Division ohne rest möglich ist
  0 =:= X mod Y.
 
zahl(Z) :-
  % um nich all zu viel und zu lange
  % zu warten werden nur zahlen 
  % in dem bereich 1 .. 1000 geprüft
  zahl_von_bis(1,1000,Z).

% pattern matching
% wenn dieses muster vorkommt ...
zahl_von_bis(M,N,M) :-
	M<N.
zahl_von_bis(N,N,N).
zahl_von_bis(M,N,Z) :-
  M<N,
  M1 is M+1,
  zahl_von_bis(M1,N,Z).
 
% weitere anmerkungen zu prolog
% in prolog werden argumente (vgl. parameter in 
% Funktionalen oder Objektorientierten sprachen)
% verwendet. da funktoren keine werte zurück geben
% muss ein rückgabe parameter benutzt werden. 
% andere sprachen kennen dafür schlüsselworte wie out

Mustervergleich / Unifikation #

Listen und Rekursion #

Nichtdeterminismus #