= Programmierparadigmen =

''aus SPEKTRUM DER WISSENSCHAFT · Juni 2007'' %%quote
Das ist wahr, aber was speziell mich begeistert,
ist die Einheitlichkeit der Notation.
Alles wird auf dieselbe Weise erledigt,
man muss sich also nicht viel merken.
(Was ich lieber verschweige, ist die
Überfülle an Klammern in Lisp (die einige Leute ärgert).
(Was die Welt braucht (meiner Meinung nach) ist nicht 
(eine Lisp-Variante (mit weniger Klammern)), 
sondern (eine gewöhnliche Schriftsprache (mit mehr)).))
%%

Auch diese Seite ist an eine Vorlesung der [Universität|http://www.uni-due.de/] angelehnt. In dieser Vorlesung geht es um die Verschiedenen Konzepte der Programmiersprachen. Die Programmiersprachen die in der Vorlesung besprochen wurden, sind [Prolog|http://www.swi-prolog.org/], [Ruby|http://www.ruby-lang.org/] und [Haskell|http://www.haskell.org/]. Zu den einzelnen Programmiersprachen wird im laufe der Näher eingegangen. Weitere Thema der Veranstalltung sind Grammatiken und [EBNF|Wikipedia:EBNF].

Der Wikipediaartikel über [Programmiersprachen|Wikipedia:Programmiersprache] 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| Wikipedia: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|Wikipedia:Programmiersprache#Programmierparadigmen] können dem Link entnommen werden. Weiter ist zur [deklarativen Programmierung|Wikipedia:Deklarative_Programmiersprache] 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 |http://www-cgi.uni-regensburg.de/~brf09510/syntax.html]

[Formale Grammatik| Wikipedia:Formale_Grammatik]
[Dangling Else| Wikipedia:Dangling_Else]

=== [BNF|Wikipedia:Backus-Naur-Form] ===
'Kontextfreie' Grammatiken

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

Grammatik: 
   
 <N> ::= "a" <A> "b" <B> <C> "c"
 
=== [EBNF|Wikipedia:Erweiterte_Backus-Naur-Form] ===

{{{

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 ==

  
[{Tag JensKapitza}]