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.
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 #

Grammatiken #

Syntaxdiagramm-Generator aus EBNF

Formale Grammatik Dangling Else

BNF #

 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 #

Variablen, Bindung, Typisierung #

Variablen und Parameter #

Sichtbarkeit #

Typsysteme: einfache und zusammengesetzte Datentypen #

statische und dynamische Typbindung #

Ausdrücke, Befehle, Kontrollstrukturen #

Ausdrücke (expressions) #

  x + y

Befehle (statements) #

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

Sequenzen und Kontrollstrukturen #

Prozeduren und Parameterübergabe #

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 #

% 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 #