Informatik 1 (Winter 2024/25) PDF

01 Informatik 1 01 – Scheme: Ausdrücke, Auswertung und Abstraktion Winter 2024/25 Torsten Grust Universität Tübingen  02 1 ┆ DrRacket Willkommen! Wir werden in dieser Informatik 1 d...

01 Informatik 1 01 – Scheme: Ausdrücke, Auswertung und Abstraktion Winter 2024/25 Torsten Grust Universität Tübingen  02 1 ┆ DrRacket Willkommen! Wir werden in dieser Informatik 1 die Programmiersprache Scheme einsetzen. Programmierumgebung für Scheme: DrRacket, frei verfügbar für macOS , Linux , Windows  Download: http://tiny.cc/Racket (Version 8.14 oder höher) 1. HelpDeutsche Benutzeroberfläche für Racket  2. Racket neu starten 3. SpracheSprache auswählen…: SdP! - AnfängerOK  4. SpracheTeachpack hinzufügenimage.rktOK   03 DrRacket: Definition + Interaktion  04 2 ┆ Scheme: Funktionsanwendung nutzt Präfixnotation Die Anwendung von Funktionen wird in Scheme auschliesslich in Präfixnotation durchgeführt: Mathematik Scheme 44 − 2 (- 44 2) f(x,y) (f x y) √81 (sqrt 81) ⎣x⎦ (floor x) 9² (expt 9 2) 3! (! 3) Allgemein: Anwendung einer Funktion + auf , Argumente via (+ -./012,3₁ -./012,3₂ … -./012,3ₙ).  05 Scheme: Ausdrücke und Auswertung (+ 40 2) und (odd? 42) sind Beispiele für Ausdrücke, die bei Auswertung einen Wert liefern (Notation: ⇝): (+ 40 2) ⇝ 42 (odd? 42) ⇝ #f  ⇝: Durch Auswertung (auch: Reduktion oder Evaluation) führt Scheme Programme aus  06 DrRacket: Interaktionsfenster ≡ REPL DrRackets Interaktionsfenster realisiert einen interaktiven read-eval-print loop (REPL): 1. Liest Ausdruck (read), 2. wertet diesen mittels ⇝ aus (eval), 3. gibt den resultierenden Wert aus (print). !"#$ "%#& '!()*  07 3 ┆ Scheme: Literale Literale stehen für einen konstanten Wert (auch: Konstante) und sind nicht weiter reduzierbar: Literal #t #f true, false, Wahrheitswerte "Zelda" "x" "" Zeichenketten (auch: Strings) 0 1904 -42 007 ⎫ 0.42 3.1415 -273.15 ⎬ exakte Zahlen 1/2 3/4 -1/10 ⎭ #i1.4142 #i-1.0 inexakte Zahlen  Bilder  08 4 ┆ Scheme: Zusammengesetzte Ausdrücke Die Auswertung zusammengesetzter Ausdrücke vollzieht ⇝ in mehreren Schritten (Steps), von “innen nach aussen”. Die Auswertung stoppt, sobald keine weitere Reduktion mehr möglich ist: (+ (+ 20 20) (+ 1 1)) ⇝ (+ 40 (+ 1 1)) ⇝ (+ 40 2) ⇝ 42 ─────── ───── ────── A B parallele Reduktion wäre OK ── ≡ wird als nächstes reduziert  09 Scheme: Zusammengesetzte Ausdrücke Beispiel: Auswertung des zusammengesetzten mathematischen Ausdrucks 2 − 1 + 3. Die Mathematik benötigt neben “Punkt-vor-Strich” weitere Konventionen, die Zweideutigkeiten im Ausdruck auflösen:   ⋱ ⋰ 1. Rechts-tief geklammert: 2 - (1 + 3) = -2 2. Links-tief geklammert: (2 - 1) + 3 = 4 ⋰ ⋱   Scheme ist explizit und unterscheidet Varianten 1. und 2. …  10 Scheme: Arithmetik mit exakten vs. inexakten Zahlen 1. Exakte Zahlen:  2. Inexakte Zahlen:  (+ 0.1 0.2)  (+ #i0.1 #i0.2)  ⇝ 0.3  ⇝ #i0.30000000000000004  Schemes interne Darstellung von inexakten Zahlen #i… ist kompakt und Arithmetik ist sehr effizient, kann aber zu Ungenauigkeiten führen. Insbesondere können Tests auf Gleichheit unerwartet ausfallen: (= (+ #i0.1 #i0.2) 0.3) ⇝ #f. !  11 5 ┆ Scheme: Namen und Bindungen Ein Wert kann an einen Namen (auch: Identifier) gebunden werden: (JKLMNK OP 2) OP: Identifier, 2: Ausdruck Erlaubt die konsistente Wiederverwendung und dient der Selbstdokumentation von Programmen. Achtung: (define …) ist eine sogenannte Spezialform. Insbesondere besitzt diese Spezialform keinen Wert, sondern einen Effekt: der Name OP wird an den Wert von Ausdruck 2 gebunden.  12 DrRacket: Komplexere Programme im Definitionsfenster Sobald Programme komplexer werden (und mehrere Bindungen mittels define enthalten), gehören diese in DrRackets oberes Definitionsfenster: 1. Programm im Definitionsfenster konstruieren. 2. Gleichwertig: RacketStart | Button [Start ] | ⌘R 3. Ausgabe der Werte der reduzierten Ausdrücke in REPL. Alle gebundenen Namen sind auch in der REPL verfügbar. Das Programm im Definitionsfenster kann mittels DateiDefinitionen speichern (⌘S) in einem Racket-File (Dateiendung.rkt) gespeichert werden.  13 Scheme: Namen Namen (Identifier) können in Scheme fast beliebig gewählt werden, solange 1. die Zeichen ( ) [ ] { } " , ' ` ; # | \ nicht vorkommen, 2. der Namen nicht einem numerischen Literal gleicht, 3. kein Whitespace (Space, Tab, Return) enthalten ist, und 4. der Name nicht bereits an einen Wert gebunden ist ( Groß-/Kleinschreibung ist in Namen nicht relevant). Beispiel: Damit ist euro->us$ ein gültiger Identifier. Euro->US$ ist als Identifier identisch.  14 6 ┆ Scheme: Ausdrücke mit “Löchern” ⬚ Ausdruck mit “Loch” ⬚: Setze Wert ein, erhalte auswertbaren Ausdruck ⋰ (* ⬚ (* 135 minutes-in-a-day)) Scheme markiert solche “Löcher” mittels lambda: ┌╌╌╌╌╌╌╌╌┐ ┆ X (lambda (⬚) (* ⬚ (* 135 minutes-in-a-day))) (lambda (days) (* days (* 135 minutes-in-a-day)))  15 Scheme: Lambda-Abstraktion Eine Lambda-Abstraktion (auch: Funktion) erlaubt die Formulierung eines Ausdrucks 2, in dem mittels Parametern Yᵢ von konkreten Werten abstrahiert wird: [\]\^K_K] ───── (c\^dJ\ (Y₁ Y₂ …) 2) e fg^hL, enthält Vorkommen von Y₁, Y₂, … (lambda …) ist eine Spezialform. Der Wert der Lambda- Abstraktion ist #. (Darauf kommen wir zurück.)  16 Scheme: Lambda? λ? (What the heck?) “ In Russel and Whitehead's “Principia Mathematica” the notation for for the function f with f(y) = 2y+1 is 2ŷ+1. [Alonzo] Church originally intended to use the notation ŷ.2y+1. The typesetter could not position the hat on top of the y and placed it in front of it, resulting in ∧ y.2y+1. Then another typesetter changed it to λy.2y+1. ” — Henk Barendregt, The Impact of Lambda Calculus in Logic and Computer Science (1997)  17 7 ┆ Scheme: Funktionsanwendung (Applikation) Die Anwendung (auch: Applikation) einer Lambda-Abstraktion führt zur Ersetzung (unten: ) aller Vorkommen der Paramater Yᵢ im Rumpf 2 durch die angegebenen Argumente. Die Anwendung von Funktion + auf Argument j wird — wie gewohnt — mittels Juxtaposition notiert: (+ j). kgNl_MmN n]og^KN_ ──────────────────────────────────────────── X ((lambda (days) (* days (* 135 minutes-in-a-day))) 365)  ⇝ (* 365 (* 135 minutes-in-a-day))  ⇝ (* 365 (* 135 1440))  ⇝ (* 365 194400)  ⇝ 70956000  18 Beispiel: Das Parkplatzproblem Erinnert euch: Anzahl der PKWs r(,,.) auf einem Parkplatz mit , Fahrzeugen und. Rädern: r(,,.) = (. - 2 × ,) / 2. Eine mögliche Definition der Funktion r in Scheme: (define parking-lot-cars (lambda (n r) (/ (- r (* 2 n)) 2))) In der REPL: (parking-lot-cars 6 16) ⇝ 2 ; 2 Autos + 4 Motorräder  19 8 ┆ Scheme: Kommentare " Fokus nur auf den Code von parking-lot-cars: Was genau ist n? Was genau bezeichnet Parameter r? Wie ist das Ergebnis der Funktion zu interpretieren? Kommentare annotieren Programme, um solche Fragen zu klären. In Scheme leitet ein Semikolon (;) einen Kommentar ein, der bis zum Zeilenende reicht und vom System bei der Auswertung vollkommen ignoriert wird.  Funktionsdefinitionen sollte eine ein- bis zweizeilige Kurzbeschreibung als Kommentar vorangestellt werden.  20 Kommentare… “ Programs must be written for people to read, and only incidentally for machines to execute. ” — H. Abelson and G. Sussman, The Structure and Interpretation of Computer Programs “ Real programmers don't comment their code. If it was hard to write, it should be hard to understand. ” — Tom van Vleck  21 9 ┆ Scheme: Signaturen Eine Signatur prüft, ob ein Name OP an einen Wert einer angegebenen Sorte tO/ gebunden wird: (: OP tO/) (: …) ist eine Spezialform mit Effekt: Signaturüberprüfung. Racket kennt eine Reihe eingebauter Signaturen: Signatur %&' akzeptierte Werte natural ℕ₀ (natürliche Zahlen mit 0) integer ℤ (ganze Zahlen) rational ℚ (rationale Zahlen, Brüche) real ℝ (reelle Zahlen) number ℂ (komplexe Zahlen, umfasst ℕ₀, ℤ, ℚ, ℝ) boolean #t, #f (Wahrheitswerte, Booleans) strings Zeichenketten image Bilder  22 Scheme: Signaturen für Funktionen Funktionssignaturen der Form (… -> …) spezifizieren Signaturen sowohl für die Parameter Y₁, Y₂, …, Yₙ als auch für den Resultatwert einer Funktion: (tO/-Y₁ tO/-Y₂ … tO/-Yₙ -> tO/-.2t0{3) Signaturen werden bei jeder Anwendung der zugehörigen Funktion erneut überprüft: Passt das Ote Argument zur Signatur tO/-Yᵢ und passt das Resultat der Funktion zu tO/-.2t0{3? Signaturverletzungen werden von DrRacket protokolliert, aber das Programm wird weiter ausgeführt. !  23 10 ┆ Scheme: Testfälle Testfälle dokumentieren das erwartete Ergebnis eines Ausdrucks nach Auswertung: (check-expect 2₁ 2₂) ; ergibt !₁ den erwarteten Wert !₂? (check-expect …) ist Spezialform mit folgendem Effekt: 1. Werte Ausdruck 2₁ aus, 2. teste ob der erhaltene Wert der Erwartung (= Wert des Ausdrucks 2₂) entspricht, 3. protokolliere positive/negative Testergebnisse.  Stelle Funktionsdefinitionen direkt mehrere Testfälle für interessante Argumente (bspw. Randfälle) voran.  24 11 ┆ Scheme: Konstruktionsanleitung für Funktionen  Zusammen ergeben diese Elemente von Scheme eine erste Konstruktionsanleitung für eine Funktion +: ; …   Kurzbeschreibung (Kommentar) (: + (… -> …))   Funktionssignatur (|}K|l-K~hK|_ (+ …) …)   Testfälle für + ⋮  (|}K|l-ÄM_}MN (+ …) …)  (JKLMNK +   Definition von + (c\^dJ\ (Y₁ Y₂ …)  …))   Funktionsrumpf programmieren Im Laufe des Semesters werden wir diese Konstruktionsanleitung systematisch verfeinern.