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

 (ezzeriesa.notion.site)
2 Punkte von GN⁺ 2024-11-18 | 1 Kommentare | Auf WhatsApp teilen

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.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-11-18
Meinungen auf Hacker News

  • Zur Warnung: Wer tief in SICP/Lisp/Scheme eintaucht, kann seine Art, über Programmierung nachzudenken, verändern – und solche intellektuellen Anregungen sind immer willkommen.
    Wenn man diese Ideen jedoch vollständig auf eine objektorientierte Codebase überträgt, wirkt das meist kontraproduktiv oder stößt im Team auf Widerstand.
    Nach Lisp kann man zum Beispiel versucht sein, jede for-Schleife durch forEach zu ersetzen oder alles zu map/reduce-Ketten umzubauen. Wenn die Sprache funktionale Programmierung aber nicht wirklich vollständig annimmt, kann das sowohl Lesbarkeit als auch Performance schaden.
    Am Ende erdet einen die Erinnerung daran, dass veränderlicher Speicher und CPUs den Code ausführen. Heutzutage halte ich datenorientiertes Design und eine auf die Hardware-Realität abgestimmte „mechanische Empathie“ im Alltag für praktischer als abstrakte Konzepte wie Church-Zahlen.

    • Ich halte Unveränderlichkeit für sicherer.
      Je weniger Seiteneffekte, desto vorhersehbarer ist der Code, und Objektorientierung wird oft auch dort eingesetzt, wo einfache Funktionen ausreichen würden.
      In der Spieleentwicklung, wo es viele Berechnungen und riskanten Code gibt, passt Objektorientierung ziemlich gut. In der Webentwicklung wirkt funktionale Programmierung dagegen viel natürlicher, und bei SaaS ermöglichen Sprachen wie Elixir zuverlässigeren, fehlerärmeren und besser testbaren Code.
    • Es gibt ja auch Dinge wie das Common Lisp Object System.
      Außerdem gab es Sachen wie forEach und map/reduce bereits in Smalltalk-Collections, und auch wenn sie keine erstklassige Syntax waren, wurden sie nach Object Pascal und C++ übernommen.
      Weil der zugrunde liegende Speicher veränderlich ist, haben auch Sprachen der ML-Familie Mechanismen für Mutation, wenn man sie wirklich braucht.
    • Die einzige Art, wie CPUs Kontrollfluss implementieren, ist im Grunde goto, aber goto ist noch unbeliebter als Lisp.
      Noch merkwürdiger ist, dass Caches für Performance auf modernen CPUs unverzichtbar sind, es aber immer noch keine Sprache gibt, die die Speicherhierarchie als First-Class Citizen behandelt.
      Am nächsten kommt dem wohl Linux-artiges C, in dem Unterstriche wie ein Meer überlaufen.

  • Es bietet einen guten Einstieg darin, Zustand mit reinen Funktionen zu codieren.
    Tatsächlich gibt es noch viel mehr rein funktionale Codierungen für alle möglichen Daten wie Bäume, Integer, Summentypen/Produkttypen, Bilder, Monaden usw.
    Die Codierung kann etwas verwirrend sein, ist aber zugleich elegant und klein.
    Eine funktionale Implementierung der Maybe-Monade in JavaScript sieht zum Beispiel so aus:
    Nothing = nothing => just => nothing
    Just = v => nothing => just => just(v)
    pure = Just
    bind = mx => f => mx(mx)(f)
    evalMaybe = maybe => maybe("Nothing")(v => "Just " + v)
    console.log(evalMaybe(bind(Nothing)(n => pure(n + 1)))) // Nothing
    console.log(evalMaybe(bind(Just(42))(n => pure(n + 1)))) // Just 43

    • Eine solche Implementierung lässt sich aus dem Rekursionsprinzip des jeweiligen Typs ableiten.
      data Maybe a = Nothing | Just a
      foldMaybe :: (Unit -> r) -> (a -> r) -> Maybe a -> r
      Die beiden Higher-Order Functions, die man an foldMaybe übergibt, entsprechen jeweils Nothing und Just.
      Allerdings ist die Nothing-Seite der Genauigkeit halber in einer Form mit zusätzlichem Unit-Parameter gehalten.
    • Man kann es so sehen, dass ein induktiver Typ in den Typ seiner Rekursorfunktion umgewandelt wird.
      In der Typentheorie ist das ziemlich cool, für praktische Programmierung aber nicht besonders gut.
    • Mathematisch mag es elegant sein, aber wenn es über eine Sprache vermittelt wird, die ohne Sortierung oder interne Rechtfertigung nur aus dem ASCII-Zeichensatz besteht, ist es optisch ziemlich schmerzhaft.
    • Kurz gesagt: Der untypisierte Lambda-Kalkül ist Turing-vollständig.

  • Ich habe mir früher die echte SICP-Vorlesung angesehen, also die MIT-OCW-Aufzeichnung von 1986.
    Sie wird oft für ihre hohe Informationsdichte gelobt, aber tatsächlich geht ziemlich viel Zeit verloren: durch Fragen und Antworten mit Studierenden, dadurch, dass der Dozent Aufmerksamkeit auf Versuche lenkt, im Hörsaal eine „Multimedia“-Präsentation zu machen, und dadurch, dass der gesamte Unterrichtsplan im Voraus nicht vollständig durchstrukturiert war und Fragen daher nicht proaktiv abgefangen wurden.
    Auch die Zeit, die fürs Schreiben an die Tafel draufgeht, summiert sich erheblich.
    Natürlich kann man über die Reihenfolge des Materials beliebig streiten und sie neu anordnen, und irgendwann plane ich auch, selbst eine Videoreihe zu erstellen, die diese Inhalte so erklärt, wie es meinem eigenen Gefühl entspricht.
    Ich finde es erfreulich, dass diese Vorlesung eine modernere Sprache wie Python verwendet und trotzdem die Wurzeln beizubehalten scheint; außerdem ist Python eine praktische Multi-Paradigma-Sprache, und ich denke, dass die Leute die Ausdruckskraft durch funktionale Idiome nicht ausreichend anerkennen, auch wenn es keine vollständige Reinheit ist.

    • In dieser Vorlesung wird zunächst Scheme in Python implementiert und danach Scheme erneut in Scheme.
      Meiner Ansicht nach kann und sollte Python aus dieser Vorlesung herausgenommen werden.
      Python hat eine sehr schwache Unterstützung für funktionale Programmierung.
      Listen basieren nicht auf cons, Lambdas sind stark eingeschränkt, Pattern Matching ist furchtbar und nicht ausdrucksbasiert, und auch die Namespaces sind seltsam.
      Python ist kaum als moderne Sprache zu betrachten, sondern steckt in den 1990ern fest; es ist nur gewachsen, weil es eine ordentliche C-API hat, leider auf Kosten besserer Sprachen.
    • Funktionale Programmierung in Python ist ziemlich schwach, und in diesem Punkt halte ich JavaScript sogar für besser.
      Weil es keine Tail-Call-Optimierung gibt, brauchen einige Code-Übungen völlig andere Lösungen als in Scheme.
      Wenn 1:1 übersetzter Code fehlschlägt, muss der Dozent den Studierenden dann sagen, sie sollten es einfach glauben, weil es wegen der gewählten Sprache so funktioniert, oder soll man alles als Problem betrachten, bei dem der Stack externalisiert werden muss, und es entsprechend lösen?
      SICP gewaltsam in Python hineinzupressen wirkt ziemlich töricht.
    • Es gibt auch die Vorlesungen der ArsDigita University.
      Die Website ist inzwischen offline, aber auf archive.org kann man die Vorlesungen ansehen.
      https://en.m.wikipedia.org/wiki/ArsDigita#ArsDigita_Foundati...
      https://archive.org/details/arsdigita_01_sicp/
      Sie verkauften einen USB-Stick mit dem gesamten Curriculum; es wäre wirklich schön, wenn jemand ein ISO davon hochladen würde.
      https://web.archive.org/web/20190222145553/aduni.org/drives/
    • Das Problem mit Python und den meisten Nicht-Lisp-Sprachen ist, dass sie es nicht leicht machen, Programme wie Daten zu behandeln.
      Dinge, die sich in Scheme einfach ausdrücken lassen, werden in anderen Sprachen zu komplizierten Übungsaufgaben.
      Statt sich auf die zugrunde liegenden Konzepte zu konzentrieren, konzentrieren sich die Studierenden auf Details der Implementierungssprache, um die man sich in Scheme nicht kümmern müsste.

  • Als ich zum ersten Mal gesehen habe, wie cons/car/cdr mit Lambdas implementiert wurden, wirkte das wie Magie.
    Letztlich sehe ich darin aber den Nachweis, dass die Sprach-Laufzeitumgebung Key/Value-Dictionaries implementiert und man diese Implementierung nutzen kann, um andere Datenstrukturen zu bauen.

    • Die Destructuring-Logik von Elixir finde ich viel interessanter, und die abgeschwächte Version in ES6 halte ich für deutlich praktischer.
      In Elixir kann man von vorn so viel herausnehmen, wie man möchte.
    • Man braucht keine Key/Value-Dictionaries, sondern nur Pointer.
      Eine Closure ohne Verhalten ist nur ein Pointer auf die geschlossenen Variablen, und eine Closure mit zwei Pointern ist ein Paar, aus dem man car und cdr erhalten kann.
      Die Laufzeitumgebung muss ermöglichen, dass die referenzierten Objekte auch außerhalb ihrer Definition verwendet werden können, daher braucht es Escape-Analyse, Garbage Collection usw., aber kein Dictionary.

  • Kürzlich bin ich beim Theorem Proving auf die Idee gestoßen, dass man, um Dinge wie 0 != 1 zu beweisen, mit Church-Encoding allein nicht auskommt, sondern induktive Datentypen braucht.
    Ich habe dazu grob etwas hier abgelegt, zusammen mit einer separaten Kritik an SICP: https://intellec7.notion.site/Drinking-SICP-hatorade-and-why...
    Ich möchte die Grenzen der Sichtweise „Alles ist einfach eine Funktion“ besser verstehen.

    • Wenn es andere konkrete Fakten gibt, die man über Ungleichheit nutzen kann, scheint man 0 ≠ 1 beweisen zu können.
      Man kann aus dem Theorem f = g -> f x = g x folgern, rechts eine Ungleichheitstatsache erzeugen und dann die Kontraposition nehmen.
      Die Aussage, dass sich Ungleichheit zwischen Church-Zahlen ohne andere Fakten über Ungleichheit nicht direkt beweisen lässt, scheint mir zu stimmen.
      Bei induktiven Datentypen hingegen kann das Beweissystem bei zwei konkreten Instanzen desselben induktiven Typs die äußerste Anwendung des Konstruktors rekursiv entfernen und Gleichheit oder Ungleichheit direkt „beobachten“.
    • Für Theorem Proving braucht man Sigma-Typen und Pi-Typen sowie irgendeine Form von Gleichheitsbegriff.
      Ich frage mich, ob sich das mit Scott-Encoding oder Church-Encoding erreichen lässt.
    • Korrigierter Link: https://goosetaco.notion.site/Drinking-SICP-hatorade-and-why...

  • Das Buch selbst wird hier bereits diskutiert: https://news.ycombinator.com/item?id=42157558
    Ich frage mich, ob es einen Grund gibt, warum der Link nicht zum Anfang dieser Seite führt, sondern zu der Diskussion weiter unten.
    Vielleicht könnte man diesen Beitrag mit der bestehenden Diskussion zusammenführen.

  • David Beazley ist in der Python-Welt eine ziemlich legendäre Figur, und diese Vorlesung wirkte zunächst wie eine überraschende Idee, aber nach etwa zwei Sekunden Nachdenken fühlte sie sich wie die perfekte Kombination an, also habe ich mich für die nächste Vorlesung angemeldet.
    Der Kern ist, dass diese Form wohl das künftige Gesicht der kontinuierlichen Weiterbildung für Software Engineers sein wird.

    • Wenn Kapitel 5 zur Kompilierung nicht behandelt wurde, dann wurde der beste Teil von SICP ausgelassen.

  • Im Code des Abschnitts „the substitution model“ gibt es einen Tippfehler.
    ("+", ("fib", ("-", "n", 2)), ("fib", ("-", "n", 1))),
    Definiert ist fibonacci, und fib ist nicht definiert; daher sollten die beiden fib-Aufrufe eindeutig fibonacci sein.
    Der Code im tatsächlichen GitHub-Repository ist korrekt: https://github.com/savarin/pyscheme/blob/0f47292c8e5112425b5...

  • Ich halte SICP für großartig.
    Allerdings bin ich, je mehr ich gelernt und mich mit Mathematik beschäftigt habe, immer näher zu dem Schluss gekommen, dass Relationen der grundlegendere primitive Begriff sind.
    Jede Funktion lässt sich als eingeschränkte Form einer Relation ausdrücken, aber das Umgekehrte gilt nicht ohne erheblichen zusätzlichen Apparat.
    Relationale Datenbanken und SQL sind zwar die bekanntesten und erfolgreichsten Beispiele für relationales Programmieren, doch dieses Gebiet halte ich weiterhin für weitgehend unerforscht.
    Mein Interesse gilt derzeit weniger dem Entwurf von Programmiersprachen als vielmehr der Vermittlung mathematischer Grundlagen an sehr kleine Kinder.
    Seltsamerweise ist es viel einfacher, Prädikate wie „groß“ als einstellige Relation und „größer als“ als zweistellige Relation zu lehren, als dieselben Konzepte über Funktionen zu erfassen.

  • Die Sichtweise „Alles ist eine Funktion“ ist mir zu stark vereinfacht und oft nicht hilfreich, daher mag ich sie nicht besonders.
    Es gibt zum Beispiel Funktionen, die nicht in Cache, RAM, Festplatte usw. passen; Funktionen, bei denen die Big-O-Komplexität explodiert, etwa bei N-way-JOINs oder bei Suche/Matching; und Funktionen mit Seiteneffekten einschließlich Nicht-Idempotenz.
    Kaum jemand denkt über Seitenkanalangriffe auf Funktionen nach.
    Es gibt auch nichtdeterministische Funktionen, die von Datum, Uhrzeit, Dauer usw. abhängen, und Funktionen können mittendrin fehlschlagen oder auch nicht graceful failen.
    Ebenso kann man schwer annehmen, dass sie keine Ressourcen verbrauchen, die andere „Funktionen“ beeinflussen, die einen gemeinsamen Ressourcenpool nutzen.
    Funktionsargumente können beliebig groß oder komplex sein, aber in der Realität gibt es Grenzen; dann braucht man Pointer und danach wieder Remote-Referenzen wie Web oder Festplatte.
    Sagt mir bitte, wann ich aufhören soll; ich könnte noch lange weitermachen.

    • Übermäßige Vereinfachung kann manchmal hervorragend sein.
      In diesem Fall ist das Lambda-Kalkül-Modell die Grundlage des „Alles ist einfach eine Funktion“-Ansatzes und ein gutes Berechnungsmodell, weil es sehr einfach ist und sich im Vergleich zu Turingmaschinen usw. leichter handhaben und durchdenken lässt.
      Deshalb liegt es den meisten computerbasierten Logik- und Beweissystemen zugrunde.
    • Vieles davon kann als Funktion modelliert werden, und man muss es in der Praxis nur so schreiben.
      Wenn eine Funktion Ressourcen benötigt, lässt man sie diese Ressourcen verlangen; wenn sie von Datum/Uhrzeit abhängt, lässt man sie davon abhängen; wenn sie einen nichtdeterministischen Wert zurückgibt, lässt man sie einen nichtdeterministischen Wert zurückgeben.
      Einer der Gründe, warum der funktionale Programmieransatz glänzt, ist, dass er einen zwingt, solche Dinge ernst zu nehmen.
      Wenn man implizit gemeinsam genutzte Ressourcen verwenden will, muss man sie modellieren; und eine „Funktion“, die von implizit geteilten Ressourcen abhängt, wird ausdrücklich von einer echten Funktion unterschieden.
    • Die Hälfte dessen, was hier Funktion genannt wurde, ist in Wirklichkeit keine Funktion, und auch in der Welt der funktionalen Programmierung würden viele es nicht Funktion nennen.
      Es ist eher eine Prozedur.
      Eine Funktion ist eine Prozedur, aber nicht jede Prozedur ist eine Funktion.
    • Für theoretische Zwecke halte ich das für die einzige Hoffnung.