LaTeX-examples/documents/Programmierparadigmen/Programmiersprachen.tex

%!TEX root = Programmierparadigmen.tex
\chapter{Programmiersprachen}
Im folgenden werden einige Begriffe definiert anhand derer
Programmiersprachen unterschieden werden können.

\begin{definition}\xindex{Programmiersprache}\xindex{Programm}%
    Eine \textbf{Programmiersprache} ist eine formale Sprache, die durch eine
    Spezifikation definiert wird und mit der Algorithmen beschrieben werden
    können. Elemente dieser Sprache heißen \textbf{Programme}.
\end{definition}

Ein Beispiel für eine Sprachspezifikation ist die \textit{Java Language Specification}.\footnote{Zu finden unter \url{http://docs.oracle.com/javase/specs/}} Obwohl es kein guter Stil ist, ist auch
eine Referenzimplementierung eine Form der Spezifikation.

Im Folgenden wird darauf eingegangen, anhand welcher Kriterien man 
Programmiersprachen unterscheiden kann.

\section{Abstraktion}
Wie nah an den physikalischen Prozessen im Computer ist die Sprache?
Wie nah ist sie an einer mathematisch / algorithmischen Beschreibung?

\begin{definition}\xindex{Maschinensprache}\xindex{Befehlssatz}%
    Eine \textbf{Maschinensprache} beinhaltet ausschließlich Instruktionen, die direkt
    von einer CPU ausgeführt werden können. Die Menge dieser Instruktionen 
    sowie deren Syntax wird \textbf{Befehlssatz} genannt.
\end{definition}

\begin{beispiel}[Maschinensprachen]
    \begin{bspenum}
        \item \xindex{x86}x86: 
        \item \xindex{SPARC}SPARC:
    \end{bspenum}
\end{beispiel}

\begin{definition}[Assembler]\xindex{Assembler}%
    Eine Assemblersprache ist eine Programmiersprache, deren Befehle dem
    Befehlssatz eines Prozessor entspricht.
\end{definition}

\begin{beispiel}[Assembler]%
    Folgendes Beispiel stammt von \url{https://de.wikibooks.org/wiki/Assembler-Programmierung_für_x86-Prozessoren/_Das_erste_Assemblerprogramm}:
    \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=firstp.asm]{nasm}{scripts/assembler/firstp.asm}
\end{beispiel}

\begin{definition}[Höhere Programmiersprache]\xindex{Programmiersprache!höhere}%
    Eine Programmiersprache heißt \textit{höher}, wenn sie nicht ausschließlich
    für eine Prozessorarchitektur geschrieben wurde und turing-vollständig ist.
\end{definition}

\begin{beispiel}[Höhere Programmiersprachen]
    Java, Python, Haskell, Ruby, TCL, \dots
\end{beispiel}

\begin{definition}[Domänenspezifische Sprache]\xindex{Sprache!domänenspezifische}%
    Eine domänenspezifische Sprache (engl. domain-specific language; kurz DSL) 
    ist eine formale Sprache, die für ein bestimmtes Problemfeld 
    entworfen wurde.
\end{definition}

\begin{beispiel}[Domänenspezifische Sprache]
    \begin{bspenum}
        \item HTML
        \item VHDL
    \end{bspenum}
\end{beispiel}

\section{Paradigmen}
Die grundlegendste Art, wie man Programmiersprachen unterscheiden
kann ist das sog. \enquote{Programmierparadigma}, also die Art wie
man Probleme löst.

\begin{definition}[Imperatives Paradigma]\xindex{Programmierung!imperative}
    In der imperativen Programmierung betrachtet man Programme als
    eine folge von Anweisungen, die vorgibt auf welche Art etwas 
    Schritt für Schritt gemacht werden soll.
\end{definition}

\begin{definition}[Prozedurales Paradigma]\xindex{Programmierung!prozedurale}
    Die prozeduralen Programmierung ist eine Erweiterung des imperativen
    Programmierparadigmas, bei dem man versucht die Probleme in 
    kleinere Teilprobleme zu zerlegen.
\end{definition}

\begin{definition}[Funktionales Paradigma]\xindex{Programmierung!funktionale}
    In der funktionalen Programmierung baut man auf Funktionen und
    ggf. Funktionen höherer Ordnung, die eine Aufgabe ohne Nebeneffekte
    lösen.
\end{definition}

Haskell ist eine funktionale Programmiersprache, C ist eine
nicht-funktionale Programmiersprache.

Wichtige Vorteile von funktionalen Programmiersprachen sind:
\begin{itemize}
    \item Sie sind weitgehend (jedoch nicht vollständig) frei von Seiteneffekten.
    \item Der Code ist häufig sehr kompakt und manche Probleme lassen
          sich sehr elegant formulieren.
\end{itemize}

\begin{definition}[Logisches Paradigma]\xindex{Programmierung!logische}
    In der logischen Programmierung baut auf der Unifikation auf.\todo{genauer!}
\end{definition}

\section{Typisierung}
Eine weitere Art, Programmiersprachen zu unterscheiden ist die stärke
ihrer Typisierung.

\begin{definition}[Dynamische Typisierung]\xindex{Typisierung!dynamische}
    Bei dynamisch typisierten Sprachen kann eine Variable ihren Typ ändern.
\end{definition}

Beispiele sind Python und PHP.

\begin{definition}[Statische Typisierung]\xindex{Typisierung!statische}
    Bei statisch typisierten Sprachen kann eine niemals ihren Typ ändern.
\end{definition}

Beispiele sind C, Haskell und Java.

\section{Kompilierte und interpretierte Sprachen}
Sprachen werden überlicherweise entweder interpretiert oder kompiliert,
obwohl es Programmiersprachen gibt, die beides unterstützen.

C und Java werden kompiliert, Python und TCL interpretiert.

\section{Dies und das}
\begin{definition}[Seiteneffekt]\xindex{Seiteneffekt}\index{Nebeneffekt|see{Seiteneffekt}}\index{Wirkung|see{Seiteneffekt}}%
    Seiteneffekte sind Veränderungen des Zustandes.\todo{Das geht besser}
\end{definition}

Manchmal werden Seiteneffekte auch als Nebeneffekt oder Wirkung bezeichnet.

\begin{definition}[Unifikation]\xindex{Unifikation}%
    Die Unifikation ist eine Operation in der Logik und dient zur Vereinfachung
    prädikatenlogischer Ausdrücke.
    Der Unifikator ist also eine Abbildung, die in einem Schritt dafür sorgt, dass
    auf beiden Seiten der Gleichung das selbe steht.
\end{definition}

\begin{beispiel}[Unifikation\footnotemark]
    Gegeben seien die Ausdrücke
    \begin{align*}
        A_1 &= \left(X, Y, f(b) \right)\\
        A_2 &= \left(a, b, Z \right)
    \end{align*}
    Großbuchstaben stehen dabei für Variablen und Kleinbuchstaben für atomare 
    Ausdrücke.

    Ersetzt man in $A_1$ nun $X$ durch $a$, $Y$ durch $b$ und in $A_2$ 
    die Variable $Z$ durch $f\left(b\right)$, so sind sie gleich oder 
    \enquote{unifiziert}. Man erhält

    \begin{align*}
        \sigma(A_1) &= \left(a, b, f(b) \right)\\
        \sigma(A_2) &= \left(a, b, f(b) \right)
    \end{align*}

    mit
    \[\sigma = \{X \mapsto a, Y \mapsto b, Z \mapsto f(b)\}\]
\end{beispiel}

\begin{definition}[Allgemeinster Unifikator]\xindex{Unifikator!allgemeinster}%
    Ein Unifikator $\sigma$ heißt \textit{allgemeinster Unifikator}, wenn 
    es für jeden Unifikator $\gamma$ eine Substitution $\delta$ mit
    \[\gamma = \delta \circ \sigma\]
    gibt.
\end{definition}

\begin{beispiel}[Allgemeinster Unifikator\footnotemark]
    Sei
    \[C = \Set{f(a,D) = Y, X = g(b), g(Z) = X}\]
    eine Menge von Gleichungen über Terme.

    Dann ist 
    \[\gamma = [Y \text{\pointer} f(a,b), D \text{\pointer} b, X \text{\pointer} g(b), Z \text{\pointer} b]\]
    ein Unifikator für $C$. Jedoch ist
    \[\sigma = [Y \text{\pointer} f(a,D), X \text{\pointer} g(b), Z \text{\pointer} b]\]
    der allgemeinste Unifikator. Mit
    \[\delta = [D \text{\pointer} b]\]
    gilt $\gamma = \delta \circ \sigma$.
\end{beispiel}
\footnotetext{Folie 268 von Prof. Snelting}

\begin{algorithm}[h]
    \begin{algorithmic}
        \Function{unify}{Gleichungsmenge $C$}
        \If{$C == \emptyset$}
            \State \Return $[]$
        \Else
            \State Es sei $\Set{\theta_l = \theta_r} \cup C' == C$

            \If{$\theta_l == \theta_r$}
                \State \Call{unify}{$C'$}
            \ElsIf{$\theta_l == Y$ and $Y \notin FV(\theta_r)$}
                \State \Call{unify}{$[Y \text{\pointer} \theta_r] C'$} $\circ [Y \text{\pointer} \theta_r]$
            \ElsIf{$\theta_r == Y$ and $Y \notin FV(\theta_l)$}
                \State \Call{unify}{$[Y \text{\pointer} \theta_l] C'$} $\circ [Y \text{\pointer} \theta_l]$
            \ElsIf{$\theta_l == f(\theta_l^1, \dots, \theta_l^n)$ and $\theta_r == f(\theta_r^1, \dots, \theta_r^n$}
                \State \Call{unify}{$C' \cup \Set{\theta_l^1 = \theta_r^1, \dots \theta_l^n = \theta_r^n}$}
            \Else
                \State fail
            \EndIf
        \EndIf
        \EndFunction
    \end{algorithmic}
\caption{Klassischer Unifikationsalgorithmus}
\label{alg:klassischer-unifikationsalgorithmus}
\end{algorithm}

Dieser klassische Algorithmus hat eine Laufzeit von $\mathcal{O}(2^n)$ für folgendes
Beispiel:

\[f(X_1, X_2, \dots, X_n) = f(g(X_0, X_0), g(X_1, X_1), \dots, g(X_{n-1}, X_{n-1}) )\]

Der \textit{Paterson-Wegman-Unifikationsalgorithmus}\xindex{Paterson-Wegman-Unifikationsalgorithmus} ist deutlich effizienter.
Er basiert auf dem \textit{Union-Find-Algorithmus}\xindex{Union-Find-Algorithmus}.


\footnotetext{\url{https://de.wikipedia.org/w/index.php?title=Unifikation\_(Logik)&oldid=116848554\#Beispiel}}