Programmiersprachen.tex 9.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238
  1. %!TEX root = Programmierparadigmen.tex
  2. \chapter{Programmiersprachen}
  3. \begin{definition}\xindex{Programmiersprache}\xindex{Programm}%
  4. Eine \textbf{Programmiersprache} ist eine formale Sprache, die durch eine
  5. Spezifikation definiert wird und mit der Algorithmen beschrieben werden
  6. können. Elemente dieser Sprache heißen \textbf{Programme}.
  7. \end{definition}
  8. 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
  9. eine Referenzimplementierung eine Form der Spezifikation.
  10. Im Folgenden wird darauf eingegangen, anhand welcher Kriterien man
  11. Programmiersprachen unterscheiden kann.
  12. \section{Abstraktion}
  13. Wie nah an den physikalischen Prozessen im Computer ist die Sprache?
  14. Wie nah ist sie an einer mathematisch / algorithmischen Beschreibung?
  15. \begin{definition}\xindex{Maschinensprache}\xindex{Befehlssatz}%
  16. Eine \textbf{Maschinensprache} beinhaltet ausschließlich Instruktionen, die direkt
  17. von einer CPU ausgeführt werden können. Die Menge dieser Instruktionen
  18. sowie deren Syntax wird \textbf{Befehlssatz} genannt.
  19. \end{definition}
  20. \begin{beispiel}[Maschinensprachen]
  21. \begin{bspenum}
  22. \item \xindex{x86}x86
  23. \item \xindex{SPARC}SPARC
  24. \end{bspenum}
  25. \end{beispiel}
  26. \begin{definition}[Assembler]\xindex{Assembler}%
  27. Eine Assemblersprache ist eine Programmiersprache, deren Befehle dem
  28. Befehlssatz eines Prozessor entspricht.
  29. \end{definition}
  30. \begin{beispiel}[Assembler]%
  31. Folgendes Beispiel stammt von \url{https://de.wikibooks.org/wiki/Assembler-Programmierung_für_x86-Prozessoren/_Das_erste_Assemblerprogramm}:
  32. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=firstp.asm]{nasm}{scripts/assembler/firstp.asm}
  33. \end{beispiel}
  34. \begin{definition}[Höhere Programmiersprache]\xindex{Programmiersprache!höhere}%
  35. Eine Programmiersprache heißt \textit{höher}, wenn sie nicht ausschließlich
  36. für eine Prozessorarchitektur geschrieben wurde und turing-vollständig ist.
  37. \end{definition}
  38. \begin{beispiel}[Höhere Programmiersprachen]
  39. Java, Python, Haskell, Ruby, TCL, \dots
  40. \end{beispiel}
  41. \begin{definition}[Domänenspezifische Sprache]\xindex{Sprache!domänenspezifische}%
  42. Eine domänenspezifische Sprache (engl. domain-specific language; kurz DSL)
  43. ist eine formale Sprache, die für ein bestimmtes Problemfeld
  44. entworfen wurde.
  45. \end{definition}
  46. \begin{beispiel}[Domänenspezifische Sprache]
  47. \begin{bspenum}
  48. \item HTML
  49. \item VHDL
  50. \end{bspenum}
  51. \end{beispiel}
  52. \section{Paradigmen}
  53. Eine weitere Art, wie man Programmiersprachen unterscheiden
  54. kann ist das sog. \enquote{Programmierparadigma}, also die Art wie
  55. man Probleme löst.
  56. \begin{definition}[Imperatives Paradigma]\xindex{Programmierung!imperative}%
  57. In der \textit{imperativen Programmierung} betrachtet man Programme als
  58. eine Folge von Anweisungen, die vorgibt auf welche Art etwas
  59. Schritt für Schritt gemacht werden soll.
  60. \end{definition}
  61. \begin{beispiel}[Imperative Programmierung]
  62. In folgenden Programm erkennt man den imperativen Programmierstil vor allem
  63. an den Variablenzuweisungen:
  64. \inputminted[numbersep=5pt, tabsize=4]{c}{scripts/c/fibonacci-imperativ.c}
  65. \end{beispiel}
  66. \begin{definition}[Prozedurales Paradigma]\xindex{Programmierung!prozedurale}%
  67. Die prozeduralen Programmierung ist eine Erweiterung des imperativen
  68. Programmierparadigmas, bei dem man versucht die Probleme in
  69. kleinere Teilprobleme zu zerlegen.
  70. \end{definition}
  71. \begin{definition}[Funktionales Paradigma]\xindex{Programmierung!funktionale}%
  72. In der funktionalen Programmierung baut man auf Funktionen und
  73. ggf. Funktionen höherer Ordnung, die eine Aufgabe ohne Nebeneffekte
  74. lösen.
  75. \end{definition}
  76. \begin{beispiel}[Funktionale Programmierung]
  77. Der Funktionale Stil kann daran erkannt werden, dass keine Werte zugewiesen werden:
  78. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/fibonacci-akk.hs}
  79. \end{beispiel}
  80. Haskell ist eine funktionale Programmiersprache, C ist eine
  81. nicht-funktionale Programmiersprache.
  82. Wichtige Vorteile von funktionalen Programmiersprachen sind:
  83. \begin{itemize}
  84. \item Sie sind weitgehend (jedoch nicht vollständig) frei von Seiteneffekten.
  85. \item Der Code ist häufig sehr kompakt und manche Probleme lassen
  86. sich sehr elegant formulieren.
  87. \end{itemize}
  88. \begin{definition}[Logisches Paradigma]\xindex{Programmierung!logische}%
  89. Das \textbf{logische Programmierparadigma} baut auf der formalen Logik auf.
  90. Man verwendet \textbf{Fakten} und \textbf{Regeln}
  91. und einen Inferenzalgorithmus um Probleme zu lösen.
  92. \end{definition}
  93. Der Inferenzalgorithmus kann z.~B. die Unifikation nutzen.
  94. \begin{beispiel}[Logische Programmierung]
  95. Obwohl die logische Programmierung für Zahlenfolgen weniger geeignet erscheint,
  96. sei hier zur Vollständigkeit das letzte Fibonacci-Beispiel in Prolog:
  97. \inputminted[numbersep=5pt, tabsize=4]{prolog}{scripts/prolog/fibonacci.pl}
  98. \end{beispiel}
  99. \section{Typisierung}
  100. Eine weitere Art, Programmiersprachen zu unterscheiden ist die Stärke
  101. ihrer Typisierung.
  102. \begin{definition}[Dynamische Typisierung]\xindex{Typisierung!dynamische}%
  103. Bei dynamisch typisierten Sprachen kann eine Variable ihren Typ ändern.
  104. \end{definition}
  105. Beispiele sind Python und PHP.
  106. \begin{definition}[Statische Typisierung]\xindex{Typisierung!statische}%
  107. Bei statisch typisierten Sprachen kann eine niemals ihren Typ ändern.
  108. \end{definition}
  109. Beispiele sind C, Haskell und Java.
  110. \section{Kompilierte und interpretierte Sprachen}
  111. Sprachen werden überlicherweise entweder interpretiert oder kompiliert,
  112. obwohl es Programmiersprachen gibt, die beides unterstützen.
  113. C und Java werden kompiliert, Python und TCL interpretiert.
  114. \section{Dies und das}
  115. \begin{definition}[Seiteneffekt]\xindex{Seiteneffekt}\index{Nebeneffekt|see{Seiteneffekt}}\index{Wirkung|see{Seiteneffekt}}%
  116. Seiteneffekte sind Veränderungen des Zustandes eines Programms.
  117. \end{definition}
  118. Manchmal werden Seiteneffekte auch als Nebeneffekt oder Wirkung bezeichnet.
  119. Meistens meint man insbesondere unerwünschte oder überaschende Zustandsänderungen.
  120. \begin{definition}[Unifikation]\xindex{Unifikation}%
  121. Die Unifikation ist eine Operation in der Logik und dient zur Vereinfachung
  122. prädikatenlogischer Ausdrücke.
  123. Der Unifikator ist also eine Abbildung, die in einem Schritt dafür sorgt, dass
  124. auf beiden Seiten der Gleichung das selbe steht.
  125. \end{definition}
  126. \begin{beispiel}[Unifikation\footnotemark]
  127. Gegeben seien die Ausdrücke
  128. \begin{align*}
  129. A_1 &= \left(X, Y, f(b) \right)\\
  130. A_2 &= \left(a, b, Z \right)
  131. \end{align*}
  132. Großbuchstaben stehen dabei für Variablen und Kleinbuchstaben für atomare
  133. Ausdrücke.
  134. Ersetzt man in $A_1$ nun $X$ durch $a$, $Y$ durch $b$ und in $A_2$
  135. die Variable $Z$ durch $f\left(b\right)$, so sind sie gleich oder
  136. \enquote{unifiziert}. Man erhält
  137. \begin{align*}
  138. \sigma(A_1) &= \left(a, b, f(b) \right)\\
  139. \sigma(A_2) &= \left(a, b, f(b) \right)
  140. \end{align*}
  141. mit
  142. \[\sigma = \{X \mapsto a, Y \mapsto b, Z \mapsto f(b)\}\]
  143. \end{beispiel}
  144. \begin{definition}[Allgemeinster Unifikator]\xindex{Unifikator!allgemeinster}%
  145. Ein Unifikator $\sigma$ heißt \textit{allgemeinster Unifikator}, wenn
  146. es für jeden Unifikator $\gamma$ eine Substitution $\delta$ mit
  147. \[\gamma = \delta \circ \sigma\]
  148. gibt.
  149. \end{definition}
  150. \begin{beispiel}[Allgemeinster Unifikator\footnotemark]
  151. Sei
  152. \[C = \Set{f(a,D) = Y, X = g(b), g(Z) = X}\]
  153. eine Menge von Gleichungen über Terme.
  154. Dann ist
  155. \[\gamma = [Y \text{\pointer} f(a,b), D \text{\pointer} b, X \text{\pointer} g(b), Z \text{\pointer} b]\]
  156. ein Unifikator für $C$. Jedoch ist
  157. \[\sigma = [Y \text{\pointer} f(a,D), X \text{\pointer} g(b), Z \text{\pointer} b]\]
  158. der allgemeinste Unifikator. Mit
  159. \[\delta = [D \text{\pointer} b]\]
  160. gilt $\gamma = \delta \circ \sigma$.
  161. \end{beispiel}
  162. \footnotetext{Folie 268 von Prof. Snelting}
  163. \begin{algorithm}[h]
  164. \begin{algorithmic}
  165. \Function{unify}{Gleichungsmenge $C$}
  166. \If{$C == \emptyset$}
  167. \State \Return $[]$
  168. \Else
  169. \State Es sei $\Set{\theta_l = \theta_r} \cup C' == C$
  170. \If{$\theta_l == \theta_r$}
  171. \State \Call{unify}{$C'$}
  172. \ElsIf{$\theta_l == Y$ and $Y \notin FV(\theta_r)$}
  173. \State \Call{unify}{$[Y \text{\pointer} \theta_r] C'$} $\circ [Y \text{\pointer} \theta_r]$
  174. \ElsIf{$\theta_r == Y$ and $Y \notin FV(\theta_l)$}
  175. \State \Call{unify}{$[Y \text{\pointer} \theta_l] C'$} $\circ [Y \text{\pointer} \theta_l]$
  176. \ElsIf{$\theta_l == f(\theta_l^1, \dots, \theta_l^n)$ and $\theta_r == f(\theta_r^1, \dots, \theta_r^n$}
  177. \State \Call{unify}{$C' \cup \Set{\theta_l^1 = \theta_r^1, \dots \theta_l^n = \theta_r^n}$}
  178. \Else
  179. \State fail
  180. \EndIf
  181. \EndIf
  182. \EndFunction
  183. \end{algorithmic}
  184. \caption{Klassischer Unifikationsalgorithmus}
  185. \label{alg:klassischer-unifikationsalgorithmus}
  186. \end{algorithm}
  187. Dieser klassische Algorithmus hat eine Laufzeit von $\mathcal{O}(2^n)$ für folgendes
  188. Beispiel:
  189. \[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}) )\]
  190. Der \textit{Paterson-Wegman-Unifikationsalgorithmus}\xindex{Paterson-Wegman-Unifikationsalgorithmus} ist deutlich effizienter.
  191. Er basiert auf dem \textit{Union-Find-Algorithmus}\xindex{Union-Find-Algorithmus}.
  192. \footnotetext{\url{https://de.wikipedia.org/w/index.php?title=Unifikation\_(Logik)&oldid=116848554\#Beispiel}}