Programmiersprachen - Konzepte, Strukturen und Implementierung in Java

Cover......Page 1
Programmiersprachen\rKonzepte, Strukturen und\rImplementierung in Java......Page 4
ISBN 9783827428509......Page 5
Inhaltsverzeichnis......Page 6
Kaffee oder Tee?......Page 14
Die t.Sprachen......Page 15
Die Java-Implementierung......Page 18
Ockhams Rasiermesser......Page 19
Leserkreis......Page 20
Webseite zum Buch......Page 21
Danksagung......Page 22
KAPITEL 1 t.Zero: Deklarative Programmierung......Page 24
1.1.1 Zahlen......Page 25
1.1.2 Funktionen......Page 26
1.1.4 Rekursion......Page 28
1.1.5 Fehler......Page 29
1.2 Beispiele......Page 30
1.2.1 Zahlenspielereien......Page 31
1.2.2 Größter gemeinsamer Teiler......Page 32
Heronsches Verfahren......Page 33
Ganzzahlige Quadratwurzel......Page 34
1.2.4 Primzahlen......Page 35
1.2.5 Potenzen......Page 36
Die Formel von Borwein-Bailey-Plouffe......Page 38
Verbesserung durch Runden und Endrekursion......Page 39
Die Zahl e......Page 40
Steuerung der Genauigkeit......Page 41
Beschleunigung der Konvergenz......Page 42
1.2.8 Logarithmus......Page 43
1.3.1 Sprachumfang und Programmierstil......Page 45
1.3.2 Probleme des deklarativen Programmierstils......Page 47
1.4.1 Lexikalische Struktur......Page 48
1.4.2 Syntax......Page 49
1.4.3 Semantik......Page 51
1.5.1 Die Read-Eval-Print-Schleife......Page 52
Die Auswertung von Zahlen und Namen......Page 53
Die Auswertung von Listen......Page 54
Aktive oder passive Auswertung?......Page 56
2.1 Lisp......Page 58
2.2.1 Listen......Page 59
2.2.2 Symbole, Quotierung und Binden......Page 62
2.2.3 Typen......Page 64
2.2.4 Funktionen......Page 66
2.2.5 Bedingte Ausdrücke......Page 67
Länge einer Liste......Page 68
Maximum einer Liste von Zahlen......Page 69
Das gemeinsame Schema......Page 70
Vereinigung......Page 71
Zerlegung......Page 72
Umkehren mit join......Page 73
Insertsort......Page 75
Quicksort......Page 76
Mergesort......Page 77
2.3.5 Quotierung......Page 78
Der Operator quote......Page 79
Nachträgliche Quotierung......Page 80
Mehrere Operanden......Page 81
Funktionsausdrücke......Page 83
Ableitung unärer Funktionsausdrücke......Page 84
Ableitung binärer Funktionsausdrücke......Page 85
Vereinfachung von Funktionsausdrücken......Page 86
2.4 Datenabstraktion......Page 89
Unäre Zahldarstellung......Page 90
Rechenoperationen......Page 91
Stellenwertsysteme......Page 92
Andere Zahldarstellungen......Page 94
Abstraktionsebenen......Page 95
Eine Schnittstelle für Mengen......Page 96
Implementierung durch Listen......Page 98
Gleichheit von Mengen......Page 99
Implementierung von Mengen durch Binärbäume......Page 101
Zweidimensionale Darstellung von Binärbäumen......Page 105
Balancierte Binärbäume......Page 106
2.5 m.Lisp – ein metazirkuläres Lisp......Page 109
2.5.1 Der m.Lisp-Interpreter im Überblick......Page 110
Die ”Read-Eval-Print-Schleife“......Page 111
Umgebungen......Page 112
Operatoren......Page 113
2.5.2 Auswertung: eval und apply......Page 114
Anwendung von Prozeduren......Page 115
Anwendungsbeispiele......Page 117
2.5.3 Metazirkuläre Anwendung von m.Lisp......Page 119
2.5.4 Statischer und dynamischer Scope......Page 120
2.6.1 Initialisierungsdateien......Page 123
Pakete für Syntax und Semantik......Page 125
Die Schnittstelle Expr......Page 126
Beispiel: Der leere Ausdruck......Page 127
2.6.3 Die abstrakte Klasse Procedure......Page 128
Die Klassenstruktur des Interpreters......Page 129
Die abstrakte Klasse Operator......Page 130
Die konkreten Operatorklassen......Page 131
Die Implementierung des Operators op......Page 132
Die Operatortabelle......Page 133
2.6.5 Laufzeitprüfungen......Page 135
2.6.6 Listen......Page 136
Die generische Klasse LinkList......Page 137
Die Klasse List......Page 138
KAPITEL 3 t.Pascal: Imperative Programmierung......Page 142
3.1.1 Rechnen mit Zuständen......Page 143
3.1.2 Pascal......Page 144
3.2.1 Arrays und Records......Page 145
3.2.2 Variablen......Page 147
3.2.3 Schleifen......Page 148
3.2.4 Blöcke......Page 149
3.2.5 Sprungbefehle......Page 151
3.2.6 Sonstiges......Page 153
3.3.1 Ducci-Folgen......Page 155
Vektoren......Page 156
Matrizen......Page 158
Ducci-Folgen......Page 160
Insertsort......Page 162
Quicksort......Page 163
3.3.4 Neue Typen: Komplexe Zahlen......Page 165
Der Typ Complex......Page 166
Typsicherheit......Page 168
Listen als Record-Typ......Page 169
Alte und neue Listen......Page 170
3.3.6 Manipulationen an Listen......Page 171
Mutation von Listen mit setcar und setcdr......Page 172
Der Datentyp Stack......Page 174
Der Datentyp Queue......Page 176
Schlangen und dynamische Arrays......Page 179
3.4 Die Harvard-Maschine......Page 182
3.4.1 Befehlssatz......Page 183
Erzeugung der Rechnerkomponenten......Page 184
Implementierung von Programm- und Datenspeicher......Page 185
Der Interpreter f¨ur die Maschinensprache......Page 186
3.4.3 Beispielprogramm......Page 188
3.5.1 Die Klasse Record und der Operator record......Page 189
3.5.2 Die Operatoren block und var......Page 192
3.5.3 Weitere Operatoren und Initialisierung......Page 193
Die Erzeugung von Arrays......Page 194
4.1 Funktionen als Daten erster Klasse......Page 196
4.2.1 Funktionen......Page 197
Funktionen mit variabler Argumentzahl......Page 198
Die Bestandteile einer Funktion......Page 199
Bindungsrahmen......Page 200
Die Erweiterung von Umgebungen......Page 201
Der Typ eines Kontexts......Page 202
Beispiel: Das Makro time......Page 203
Makroexpansion......Page 204
4.2.4 Exceptions......Page 205
Der Operator tail......Page 207
Der Operator eval......Page 208
Der Protokoll-Modus......Page 209
Was es noch gibt......Page 210
Collatz-Folgen......Page 212
4.3.2 Anwenden von Funktionen auf Listen und Arrays......Page 213
Funktionale Kombination......Page 214
4.3.3 Erweitern von Funktionen......Page 215
Fold für Arrays: reduce......Page 216
Vararg-Funktionen und fold......Page 218
4.3.4 Komposition und Iteration von Funktionen......Page 219
Die numerische Berechnung von Ableitungen......Page 220
Die Erzeugung von Polynomen......Page 222
Maximum......Page 223
Makros haben dynamischen Scope......Page 224
While-Schleife......Page 225
Vararg-Makros und das Makro COMMENT......Page 226
Boolesche Verknüpfungen als Vararg-Makros......Page 227
Das Makro defmacro......Page 228
Der aktuelle Kontext......Page 229
Rekursive Makros......Page 230
4.4.1 Kontexterzeugung mit let......Page 232
4.4.2 Anonyme rekursive Funktionen......Page 233
4.5 Funktionen als Objekte......Page 235
4.5.2 Stack-Objekte......Page 236
4.5.3 Iteratoren und Mengen......Page 239
4.6.1 Endrekursion......Page 242
4.6.2 Der Auswertungsstack......Page 244
4.6.3 Endständigkeit......Page 247
Wann ist eine Funktion endrekursiv?......Page 248
Türme von Hanoi......Page 250
McCarthys 91-Funktion......Page 251
4.6.4 Die Konstruktion endrekursiver Funktionen......Page 252
Das allgemeine Schema......Page 253
Berechnung von Summen......Page 254
Endrekursion vorwärts und rückwärts......Page 255
Endrekursive Funktionen f¨ur Listen......Page 256
4.7.1 Umgebungen und zugehörige Operatoren......Page 258
Die Klasse Frame......Page 259
Die Klasse Env......Page 260
Operatoren, die auf Umgebungen zugreifen......Page 262
Die Klasse Function......Page 264
Der Operator function......Page 265
Die Klasse Makro......Page 266
Tracing von Funktionen und Makros......Page 267
Der Protokoll-Modus und die Klasse EvalStack......Page 269
Die Klasse Alarm......Page 270
Die Operatoren throw und catch......Page 271
4.7.5 Die Verarbeitung von Tail Calls......Page 272
Die Klasse TailCall......Page 273
Änderungen an der Klasse Function......Page 274
Änderungen an der Schnittstelle Expr......Page 275
Änderungen an der Klasse List......Page 276
Änderungen an der Klasse Procedure......Page 277
4.7.6 Der Operator part......Page 278
Selektiver Zugriff......Page 279
5.1 Der Lambda-Kalkül......Page 280
5.1.2 Reduktion......Page 281
Currying......Page 283
5.2.2 Boolesche Werte......Page 284
5.2.3 Church-Listen......Page 285
Addition und Multiplikation......Page 286
Subtraktion......Page 287
5.3.1 Primitive Rekursion......Page 288
5.3.2 Bedingte Ausdrücke und Rekursion......Page 289
Die Elimination von Rekursion......Page 290
Entfernen von mehrfacher und indirekter Rekursion......Page 292
Rekursion und Fixpunkteigenschaft......Page 293
5.4.1 Funktionale Programmierung ohne Funktionen......Page 295
5.4.2 Der Fixpunkt-Kombinator......Page 296
6.1.1 Grundkonzepte......Page 298
”Mein erstes t.Java-Programm“......Page 299
6.2.1 Klassen......Page 301
6.2.2 Objekte......Page 303
Klassen als Objekte......Page 304
Methodendeklaration......Page 305
Methodenaufruf......Page 306
Konstruktoren......Page 307
Klassenmethoden und -variablen......Page 308
Duck Typing......Page 309
Tracing von Methodenaufrufen......Page 310
6.3.1 Dynamische Arrays......Page 311
6.3.2 Turingmaschinen......Page 314
Fleißige Biber......Page 315
Die Klasse Table......Page 316
Die Klasse Tape......Page 318
Die Klasse Head......Page 319
Die Klasse Beaver......Page 320
6.3.3 Private Attribute und Methoden......Page 322
Privatheit in Java......Page 323
Zugriffsschutz durch Delegation......Page 324
Zugriffsschutz durch Typprüfung......Page 325
Elementklassen......Page 326
Lokale Klassen......Page 328
Anonyme Klassen......Page 329
6.4.1 Der Typ Stream......Page 330
Filtern von Strömen......Page 333
Der Strom der Primzahlen......Page 334
Erweitern von Funktionen auf Ströme: map und bimap......Page 336
Kartesisches Produkt von Strömen......Page 337
6.4.3 Die Thue-Morse-Folge......Page 338
Laziness......Page 341
Die Klasse Stream......Page 342
Laziness und Nebenwirkungen......Page 344
6.4.5 Die Java-Klasse Stream......Page 345
Objekte und Klassen......Page 347
Operatoren......Page 348
Der Operator new......Page 349
Die Konstruktoren der Klasse Obj......Page 350
Die Methode apply......Page 351
Der Auswertungskontext......Page 352
Objekte als Ausdrücke......Page 353
Aufgaben einer t.Java-Klasse......Page 355
Die Attribute von ClassObj......Page 356
Konstruktoren......Page 357
Der Operator class......Page 358
Die t.Java-Klasse Class......Page 359
Methodenmanagement......Page 360
6.5.4 Die Klasse Method......Page 361
Methoden sind Funktionen......Page 362
Der Operator method......Page 363
7.1 Einführung......Page 364
Ein Syllogismus in t.Prolog......Page 365
7.1.2 Familienbeziehungen......Page 366
Anfragen mit Ausgabe......Page 367
Rekursiv definierte Verwandschaftsbeziehungen......Page 368
Die Regel print......Page 369
7.1.3 Färbung von Graphen......Page 370
Zirkelschlüsse......Page 371
7.2.2 Resolution......Page 372
Beispiel: Resolution ohne Unbestimmte......Page 373
7.2.3 Substitution......Page 375
7.2.4 Unifikation......Page 376
Der Unifikationsalgorithmus......Page 377
7.3.1 Unbestimmte und Terme......Page 379
Der Operator unify......Page 380
7.3.3 Regelbasen......Page 381
7.3.4 Regeln......Page 383
7.3.5 Anfragen......Page 385
7.3.6 Escape nach t.Scheme......Page 386
Escape mit einem Argument......Page 387
Escape mit zwei Argumenten......Page 388
Halbwahrheiten......Page 389
7.3.7 Der Cut-Mechanismus......Page 390
7.3.8 Wildcards......Page 391
7.3.9 Schleifenerkennung......Page 392
Der Occurs-Check......Page 393
Weitere Beispiele......Page 394
Unifikation von mehr als zwei Termen......Page 395
Das Anwachsen von Termen bei der Unifikation......Page 396
Faktensammlungen......Page 397
Rekursive Regeln......Page 400
Wolf, Ziege und Kohlkopf......Page 401
Labyrinthe......Page 403
Das Sportlerrätsel......Page 405
Das Zebrarätsel......Page 407
Listen......Page 410
Umkehren von Listen......Page 411
Permutationen......Page 412
Sortieren......Page 413
Suchbäume......Page 415
7.4.6 Das Acht-Damen-Problem......Page 416
7.4.7 Arithmetik in t.Prolog......Page 418
Ein Münzproblem......Page 419
Cuts an der richtigen Stelle setzen......Page 421
Negation......Page 422
Unbestimmte und Terme......Page 424
Regeln......Page 425
Zusammenfassung......Page 426
7.5.2 Unifikation und die Klasse Indeterminate......Page 427
7.5.3 Die Klasse Substitution......Page 428
Die Klasse Rule......Page 429
Interner Regelname und die Speicherung von Regeln......Page 430
Resolution......Page 432
Kopien von Regeln......Page 433
Escape und Cut......Page 434
Abbruch von Endlosrekursion und Schleifenerkennung......Page 435
ANHANG A Installation......Page 438
ANHANG B Quellcode......Page 440
B.1.1 Die Klassen Token und Lexer......Page 441
B.1.2 Die Klasse Parser......Page 443
B.1.3 Die Klasse Interpreter......Page 445
B.1.4 ”Odds and ends“: Die Klasse Sys......Page 446
B.2 Das Paket expressions......Page 448
Klassendiagramm......Page 449
B.3 Initialisierungsdateien......Page 450
B.4 Beispieldateien......Page 451
Literaturverzeichnis......Page 454
Stichwortverzeichnis......Page 458