Alles ist eine Funktion: Rückblick auf David Beazleys SICP-Kurs

Rückblick auf David Beazley und den SICP-Kurs: Eine Woche Erfahrung

Hier werden die Erfahrungen mit David Beazleys SICP-Kurs Ende 2022 geteilt. Es gibt zwar viele kostenlose Materialien, aber Daves Kurs war besonders effektiv, weil er bestimmte Themen auswählte und sie tiefgehend erklärte.

Ausgangspunkt

Der SICP-Kurs wurde in der Sprache Scheme durchgeführt. Hier wurde zur Erklärung des grundlegenden Substitutionsmodells ein einfacher Scheme-Interpreter in Python implementiert.

Grundlagen der Sprache Scheme

• Primitive: Grundlegende Werte (z. B. Ganzzahlen)
• Operatoren: Grundoperationen wie +, -, *, / werden in Präfixnotation verwendet
• define: Variablendefinition

> (define x 2)  
> (+ x 3) ; Ergebnis: 5  

• if: Bedingungsausdruck
• lambda: Definition anonymer Funktionen

> ((lambda (x) (* x x)) 3) ; Ergebnis: 9  

Scheme-Interpreter in Python

Mit Python wurde ein einfacher Interpreter implementiert, der Scheme-Code auswertet. Die Grundoperationen wurden als Python-Funktionen definiert.

definitions = {  
    "+": lambda x, y: x + y,  
    "*": lambda x, y: x * y,  
}  

Beispiel:

> evaluate(("+", 2, 3)) # Ergebnis: 5  

Enthalten waren außerdem die Implementierung von define und lambda sowie die Verarbeitung des Bedingungsausdrucks if.

Substitutionsmodell

Das Substitutionsmodell ist eine einfache Art, Programme zu interpretieren: Variablen werden beim Auswerten durch Werte ersetzt. Sobald jedoch Zuweisung (assignment) hinzukommt, funktioniert dieses Modell nicht mehr.

Zustand

Ein Beispiel dafür, wie das Substitutionsmodell zusammenbricht, ist Zuweisung (assignment). Wenn man etwa den Kontostand eines Bankkontos modelliert, wird mit set! eine Variable aktualisiert.

(define balance 100)  
  
(define (withdraw amount)  
  (set! balance (- balance amount))  
  balance)  

In diesem Fall kann das Substitutionsmodell den Kontostand vor und nach der Änderung nicht unterscheiden.

Daher wird ein Umgebungsmodell (Environment) benötigt. Variablen werden innerhalb einer Umgebung definiert, und jede Prozedur besitzt ihre eigene Umgebung.

Streams

Eine weitere Möglichkeit, Zustand zu modellieren, sind Streams. Mit lazy evaluation können Streams auch zukünftige Werte modellieren.

Endlosschleifen und Auswertungsreihenfolge

Unterschiede in der Auswertungsreihenfolge: Die meisten Sprachen verwenden applicative-order evaluation und werten zuerst die Argumente aus.

> (square (+ 1 2)) ; Ergebnis: 9  

Bei normal-order evaluation wird die Auswertung der Argumente jedoch verzögert, bis sie tatsächlich benötigt werden. Dadurch lassen sich Endlosschleifen vermeiden.

> (define (p) (p))  
> (define (test x y) (if (= x 0) 0 y))  
> (test 0 (p)) ; Bei normal-order wird 0 zurückgegeben, bei applicative-order entsteht eine Endlosschleife  

Lambda-Kalkül und Church-Zahlen

Mit Church-Encoding lassen sich Zahlen als Prozeduren darstellen. Das ist ein wichtiges Konzept der funktionalen Programmierung.

(define (zero f) (lambda (x) x))  
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))  

• zero ist eine Funktion, die ihr Argument unverändert zurückgibt (die identity-Funktion).
• increment wendet einen Funktionsaufruf einmal zusätzlich an.

Beispiel

> ((zero (lambda (x) (+ x 1))) 0) ; Ergebnis: 0  
> (((increment zero) (lambda (x) (+ x 1))) 0) ; Ergebnis: 1  

Iteration vs. Rekursion

Scheme verwendet statt einer for-Schleife Rekursion, um wiederholte Aufgaben auszuführen.

Rekursionsbeispiel: Fakultät

(define (factorial n)  
  (if (= n 1)   
    1   
    (* n (factorial (- n 1)))))  

Dieser rekursive Aufruf kann durch die Nutzung des Stacks viel Speicher verbrauchen.

Tail-Call-Optimierung

Scheme reduziert den Speicherverbrauch durch Tail-Call-Optimierung. Dadurch verhält sich der Ablauf wie ein iterativer Prozess.

(define (factorial n)  
  (define (iter product counter)  
    (if (> counter n)  
        product  
        (iter (* product counter) (+ counter 1))))  
  (iter 1 1))  

Abschluss

David Beazleys Kurs behandelt ausgewählte Kernkonzepte aus SICP in großer Tiefe. Besonders hilfreich war er dabei, verschiedene Programmierparadigmen wie funktionale Programmierung, Lambda-Kalkül und Auswertungsreihenfolgen zu verstehen.

Zitat von Knuth

Wenn man nur Theorie studiert, bedeutet das, dass es Zeit ist, sich auf die praktische Seite zu konzentrieren; und wenn man nur praktisch arbeitet, bedeutet das, dass es Zeit ist, sich auf die theoretische Seite zu konzentrieren.

[GN⁺]

Hacker-News-Kommentare

• Die SICP-Vorlesungen haben eine hohe Informationsdichte, benötigen aber durch die Fragen und Antworten der Studierenden sowie die Nutzung der Tafel viel Zeit. Auch die Reihenfolge der Vorlesungen ließe sich möglicherweise neu strukturieren. Ich plane persönlich eine neue Videoserie.

  • Die SICP-Vorlesungen verwenden moderne Sprachen wie Python und bewahren dennoch ihre ursprüngliche Intention.
  • Python ist als Multi-Paradigmen-Sprache äußerst ausdrucksstark.

• Es wird vorgestellt, wie sich Zustand als reine Funktion kodieren lässt. Es gibt verschiedene rein funktionale Kodierungen für unterschiedliche Daten.

  • Kodierungen können verwirrend sein, sind aber elegant und prägnant.
  • Es wird ein Beispiel gezeigt, wie sich die Maybe-Monade in JavaScript funktional implementieren lässt.

• Durch den URL-Anker/Hash des Blogposts landete ich direkt beim Postskriptum, was verwirrend war.

• Die Implementierung von cons/car/cdr mit Lambdas wirkte beim ersten Mal wie Magie. Das zeigt, dass die Sprachlaufzeit ein Schlüssel/Wert-Wörterbuch implementieren muss.

• David Beazley ist eine legendäre Figur in der Python-Welt, und diese Vorlesung war zunächst überraschend, erschien dann aber schnell als perfekte Kombination. Ich habe mich für die nächste Vorlesung angemeldet.

  • Das zeigt, wie kontinuierliche Weiterbildung für Softwareingenieure aussehen könnte.

• Ich bin auf das Konzept gestoßen, dass induktive Datentypen notwendig sind. Allein mit Church-Kodierung lassen sich keine Aussagen wie 0 != 1 beweisen.

  • Entsprechende Inhalte wurden in Notion veröffentlicht.

• Der Artikel selbst war interessant, aber die Navigation auf der Seite war schwierig. Mit den Pfeiltasten der Tastatur ließ sich nicht scrollen.

• Im Code im Abschnitt „Alternatives Modell“ gibt es einen Tippfehler. Statt fib sollte fibonacci verwendet werden. Der Code im GitHub-Repository ist korrekt.

• Es gibt einen Link zu einer laufenden Diskussion über das Buch. Ich frage mich, warum der Link direkt zur Diskussion am Seitenende führt und ob das in eine andere Diskussion integriert werden könnte.

• Ein YouTube-Link wurde bereitgestellt