Programmiersprachen.tex 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338
  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. Programmiersprachen können anhand der Art ihrer Typisierung unterschieden werden.
  101. \begin{definition}[Typisierungsstärke]\xindex{Typisierungsstärke}%
  102. Es seien $X, Y$ Programmiersprachen.
  103. $X$ heißt stärker typisiert als $Y$, wenn $X$ mehr bzw. nützlichere Typen hat als $Y$.
  104. \end{definition}
  105. \begin{beispiel}[Typisierungsstärke]
  106. Die stärke der Typisierung ist abhängig von dem Anwendungszenario. So hat C im
  107. Gegensatz zu Python, Java oder Haskell beispielsweise keine booleschen Datentypen.
  108. Im Gegensatz zu Haskell hat Java keine GADTs\footnote{generalized algebraic data type}.
  109. \end{beispiel}
  110. \begin{definition}[Polymorphie]\xindex{Polymorphie}%
  111. Ein Typ heißt \textbf{polymorph}, wenn er mindestens einen Parameter hat.
  112. \end{definition}
  113. \begin{beispiel}[Polymorphie]
  114. In Java sind beispielsweise Listen polymorph:
  115. \inputminted[numbersep=5pt, tabsize=4]{java}{scripts/java/list-example.java}
  116. \end{beispiel}
  117. \begin{definition}[Statische und dynamische Typisierung]\xindex{Typisierung!statische}\xindex{Typisierung!dynamische}%
  118. \begin{defenum}
  119. \item Eine Programmiersprache heißt \textbf{statisch typisiert}, wenn eine
  120. Variable niemals ihren Typ ändern kann.
  121. \item Eine Programmiersprache heißt \textbf{dynamisch typisiert}, wenn eine
  122. Variable ihren Typ ändern kann.
  123. \end{defenum}
  124. \end{definition}
  125. Beispiele für statisch typisierte Sprachen sind C, Haskell und Java.
  126. Beispiele für dynamisch typisierte Sprachen sind Python und PHP.
  127. \goodbreak
  128. Vorteile statischer Typisierung sind:
  129. \begin{itemize}
  130. \item \textbf{Performance}: Der Compiler kann mehr Optimierungen vornehmen.
  131. \item \textbf{Syntaxcheck}: Da der Compiler die Typen zur Compile-Zeit überprüft,
  132. gibt es in statisch typisierten Sprachen zur
  133. Laufzeit keine Typfehler.
  134. \end{itemize}
  135. Vorteile dynamischer Typisierung sind:
  136. \begin{itemize}
  137. \item Manche Ausdrücke, wie der Y-Combinator in Haskell, lassen sich nicht
  138. typisieren.
  139. \end{itemize}
  140. Der Gedanke bei dynamischer Typisierung ist, dass Variablen keine Typen haben.
  141. Nur Werte haben Typen. Man stellt sich also Variablen eher als Beschriftungen für
  142. Werte vor. Bei statisch typisierten Sprachen stellt man sich hingegen Variablen
  143. als Container vor.
  144. \begin{definition}[Explizite und implizite Typisierung]\xindex{Typisierung!explizite}\xindex{Typisierung!implizite}%
  145. Sei $X$ eine Programmiersprache.
  146. \begin{defenum}
  147. \item $X$ heißt \textbf{explizit typisiert}, wenn für jede
  148. Variable der Typ explizit genannt wird.
  149. \item $X$ heißt \textbf{implizit typisiert}, wenn der Typ einer
  150. Variable aus den verwendeten Operationen abgeleitet werden kann.
  151. \end{defenum}
  152. \end{definition}
  153. Sprachen, die implizit typisieren können nutzen dazu Typinferenz.
  154. Beispiele für explizit typisierte Sprachen sind C, C++ und Java.
  155. Beispiele für implizit typisierte Sprachen sind JavaScript, Python, PHP und Haskell.
  156. Mir ist kein Beispiel einer Sprache bekannt, die dynamisch und explizit typisiert
  157. ist.
  158. Vorteile expliziter Typisierung sind:
  159. \begin{itemize}
  160. \item \textbf{Lesbarkeit}
  161. \end{itemize}
  162. Vorteile impliziter Typisierung sind:
  163. \begin{itemize}
  164. \item \textbf{Tippfreundlicher}: Es ist schneller zu schreiben.
  165. \item \textbf{Anfängerfreundlicher}: Man muss sich bei einfachen Problemen
  166. keine Gedanken um den Typ machen.
  167. \end{itemize}
  168. \begin{definition}[Duck-Typing und strukturelle Typisierung]\xindex{Duck-Typing}\xindex{Typisierung!strukturelle}%
  169. \begin{defenum}
  170. \item Eine Programmiersprache verwendet \textbf{Duck-Typing}, wenn die Parameter einer
  171. Methode nicht durch die explizite Angabe von Typen festgelegt werden, sondern
  172. durch die Art wie die Parameter verwendet werden.
  173. \item Eine Programmiersprache verwendet \textbf{strukturelle Typisierung}, wenn die
  174. Parameter einer Methode nicht durch die explizite Angabe von Typen
  175. festgelegt werden, sondern explizit durch die Angabe von Methoden.
  176. \end{defenum}
  177. \end{definition}
  178. Strukturelle Typsierung wird auch \textit{typsicheres Duck-Typing} genannt.
  179. Der Satz, den man im Zusammenhang mit Duck-Typing immer höhrt, ist
  180. \enquote{When I see a bird that walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck.}
  181. \begin{beispiel}[Strukturelle Typisierung]
  182. Folgende Scala-Methode erwartet ein Objekt, das eine Methode namens \texttt{quack}
  183. besitzt:
  184. \inputminted[numbersep=5pt, tabsize=4]{scala}{scripts/scala/duck-typing-example.scala}
  185. Diese Funktion ist vom Typ \texttt{(duck: AnyRef{def quack(value: String): String})Unit}.
  186. \end{beispiel}
  187. \section{Kompilierte und interpretierte Sprachen}
  188. Sprachen werden überlicherweise entweder interpretiert oder kompiliert,
  189. obwohl es Programmiersprachen gibt, die beides unterstützen.
  190. C und Java werden kompiliert, Python und TCL interpretiert.
  191. \section{Dies und das}
  192. \begin{definition}[Seiteneffekt]\xindex{Seiteneffekt}\index{Nebeneffekt|see{Seiteneffekt}}\index{Wirkung|see{Seiteneffekt}}%
  193. Seiteneffekte sind Veränderungen des Zustandes eines Programms.
  194. \end{definition}
  195. Manchmal werden Seiteneffekte auch als Nebeneffekt oder Wirkung bezeichnet.
  196. Meistens meint man insbesondere unerwünschte oder überaschende Zustandsänderungen.
  197. \begin{definition}[Unifikation]\xindex{Unifikation}%
  198. Die Unifikation ist eine Operation in der Logik und dient zur Vereinfachung
  199. prädikatenlogischer Ausdrücke.
  200. Der Unifikator ist also eine Abbildung, die in einem Schritt dafür sorgt, dass
  201. auf beiden Seiten der Gleichung das selbe steht.
  202. \end{definition}
  203. \begin{beispiel}[Unifikation\footnotemark]
  204. Gegeben seien die Ausdrücke
  205. \begin{align*}
  206. A_1 &= \left(X, Y, f(b) \right)\\
  207. A_2 &= \left(a, b, Z \right)
  208. \end{align*}
  209. Großbuchstaben stehen dabei für Variablen und Kleinbuchstaben für atomare
  210. Ausdrücke.
  211. Ersetzt man in $A_1$ nun $X$ durch $a$, $Y$ durch $b$ und in $A_2$
  212. die Variable $Z$ durch $f\left(b\right)$, so sind sie gleich oder
  213. \enquote{unifiziert}. Man erhält
  214. \begin{align*}
  215. \sigma(A_1) &= \left(a, b, f(b) \right)\\
  216. \sigma(A_2) &= \left(a, b, f(b) \right)
  217. \end{align*}
  218. mit
  219. \[\sigma = \{X \mapsto a, Y \mapsto b, Z \mapsto f(b)\}\]
  220. \end{beispiel}
  221. \begin{definition}[Allgemeinster Unifikator]\xindex{Unifikator!allgemeinster}%
  222. Ein Unifikator $\sigma$ heißt \textit{allgemeinster Unifikator}, wenn
  223. es für jeden Unifikator $\gamma$ eine Substitution $\delta$ mit
  224. \[\gamma = \delta \circ \sigma\]
  225. gibt.
  226. \end{definition}
  227. \begin{beispiel}[Allgemeinster Unifikator\footnotemark]
  228. Sei
  229. \[C = \Set{f(a,D) = Y, X = g(b), g(Z) = X}\]
  230. eine Menge von Gleichungen über Terme.
  231. Dann ist
  232. \[\gamma = [Y \text{\pointer} f(a,b), D \text{\pointer} b, X \text{\pointer} g(b), Z \text{\pointer} b]\]
  233. ein Unifikator für $C$. Jedoch ist
  234. \[\sigma = [Y \text{\pointer} f(a,D), X \text{\pointer} g(b), Z \text{\pointer} b]\]
  235. der allgemeinste Unifikator. Mit
  236. \[\delta = [D \text{\pointer} b]\]
  237. gilt $\gamma = \delta \circ \sigma$.
  238. \end{beispiel}
  239. \footnotetext{Folie 268 von Prof. Snelting}
  240. \begin{algorithm}[h]
  241. \begin{algorithmic}
  242. \Function{unify}{Gleichungsmenge $C$}
  243. \If{$C == \emptyset$}
  244. \State \Return $[]$
  245. \Else
  246. \State Es sei $\Set{\theta_l = \theta_r} \cup C' == C$
  247. \If{$\theta_l == \theta_r$}
  248. \State \Call{unify}{$C'$}
  249. \ElsIf{$\theta_l == Y$ and $Y \notin FV(\theta_r)$}
  250. \State \Call{unify}{$[Y \text{\pointer} \theta_r] C'$} $\circ [Y \text{\pointer} \theta_r]$
  251. \ElsIf{$\theta_r == Y$ and $Y \notin FV(\theta_l)$}
  252. \State \Call{unify}{$[Y \text{\pointer} \theta_l] C'$} $\circ [Y \text{\pointer} \theta_l]$
  253. \ElsIf{$\theta_l == f(\theta_l^1, \dots, \theta_l^n)$ and $\theta_r == f(\theta_r^1, \dots, \theta_r^n$}
  254. \State \Call{unify}{$C' \cup \Set{\theta_l^1 = \theta_r^1, \dots \theta_l^n = \theta_r^n}$}
  255. \Else
  256. \State fail
  257. \EndIf
  258. \EndIf
  259. \EndFunction
  260. \end{algorithmic}
  261. \caption{Klassischer Unifikationsalgorithmus}
  262. \label{alg:klassischer-unifikationsalgorithmus}
  263. \end{algorithm}
  264. Dieser klassische Algorithmus hat eine Laufzeit von $\mathcal{O}(2^n)$ für folgendes
  265. Beispiel:
  266. \[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}) )\]
  267. Der \textit{Paterson-Wegman-Unifikationsalgorithmus}\xindex{Paterson-Wegman-Unifikationsalgorithmus} ist deutlich effizienter.
  268. Er basiert auf dem \textit{Union-Find-Algorithmus}\xindex{Union-Find-Algorithmus}.
  269. \footnotetext{\url{https://de.wikipedia.org/w/index.php?title=Unifikation\_(Logik)&oldid=116848554\#Beispiel}}