Eine homoikonische Python-Sprache

 (substack.com/aljamal)
2 Punkte von GN⁺ 2024-05-13 | 2 Kommentare | Auf WhatsApp teilen
  • Die Homoikonizität von Lisp ist die Eigenschaft, Code und Daten in derselben Form zu behandeln; wenn man das klassische „Lisp in Lisp“ nach Python überträgt, wird diese Idee in einer vertrauteren Syntax sichtbar
  • Ursprünglich besaß Lisp sowohl die Code-Darstellung M-expression als auch die Daten-Darstellung S-expression, und „Lisp in Lisp“ implementiert ein S-expression-Lisp mit M-expression
  • Die Python-Version stellt S-expressions als Python-Listen dar und überträgt M-expressions in Funktionsaufrufe und bedingte Anweisungen, sodass sich der Interpreter ohne separaten Parser aufbauen lässt
  • Der erste Interpreter basiert auf Listen-Primitive-Operationen wie atom, eq, car, cdr, cons, append; für die Unterstützung von lambda kommen assoc, pairlis und eine Umgebungsliste hinzu
  • eval nimmt einen Ausdruck und eine Umgebung gemeinsam entgegen, verarbeitet Variablenbindungen und verknüpft über pairlis und assoc Argumente und Werte nach dem Prinzip des dynamischen Scopes

Die von Lisp gezeigte Einheit von Code und Daten

  • Lisp hinterließ Anfang der 1960er Jahre durch John McCarthys Lisp paper und das Lisp 1.5 manual viele Ideen, die auch Jahrzehnte später noch gültig sind
  • Im Zentrum davon steht die Homoikonizität
    • In gewöhnlichen Sprachen wird Code als Folge von Operationen verstanden, die auf Daten wirken
    • Lisp behandelt Code und Daten in derselben Form und verwischt damit die Grenze zwischen Operatoren und Operanden
  • Alan Kay nannte den „Lisp in Lisp“-Code unten auf Seite 13 des Lisp-1.5-Manuals „Maxwell's Equations of Software“
    • Darin steckt sinngemäß die Einsicht, dass wenige Zeilen Code die gesamte Welt des Programmierens enthalten können

Wie „Lisp in Lisp“ nach Python übertragen wird

  • Ziel ist es, den klassischen „Lisp in Lisp“-Code in Python neu zu schreiben und dabei den Geist des Originals so weit wie möglich zu bewahren
  • Lisp besitzt zwei Arten syntaktischer Darstellung
    • M-expression: Code-Darstellung, kurz für meta
    • S-expression: Daten-Darstellung, kurz für symbolic
    • Beide Darstellungen sind semantisch gleichwertig
  • Der bestehende „Lisp in Lisp“-Code ist in M-expression geschrieben und implementiert ein S-expression Lisp
  • In der Python-Implementierung werden Lisp-S-expressions als Python-Listen dargestellt
    • Lisp ist die Abkürzung für „List Processing“ und arbeitet um die eine Datenstruktur Liste herum
    • Python-Listen eignen sich als Darstellung, um Lisp-S-expressions zu emulieren
  • M-expressions werden in Python-Code-Strukturen wie Funktionsaufrufe und Bedingungen übersetzt
    • Dank dieses Mappings lässt sich ein Interpreter ohne String-Manipulation oder einen separaten Parser bauen

Der erste Interpreter aus Listen-Primitive-Operationen

  • Eine Lisp-Implementierung braucht einige Grundfunktionen, die von außerhalb der Sprache bereitgestellt werden
  • In der Python-Implementierung wurden folgende Listen-Primitive-Operationen verwendet
    • atom(x): prüft, ob x eine Liste ist
    • eq(x,y): prüft, ob x und y gleich sind
    • car(x): das erste Element einer Liste
    • cdr(x): der Rest einer Liste
    • cons(x,y): fügt ein Atom an eine Liste an
    • append(x,y): hängt zwei Listen aneinander
  • Mit Ausnahme einiger rekursiver Primitive konnte mit Llama3-70b über Groq schnell ein Interpreter gebaut werden, der eine Teilmenge des „Lisp in Lisp“-Codes ausführt
  • Im Beispiel verhalten sich Python-Listen wie S-expressions
  • Der vollständige Code ist in github gists verfügbar

Erweiterung für lambda und Rekursion

  • In der ersten Implementierung fehlt die wichtige Funktion lambda
    • lambda ist in Lisp die wichtigste Methode, um anonyme Funktionen zu definieren und aufzurufen
    • Ohne lambda lässt sich in Lisp keine Rekursion implementieren
    • Ohne Rekursion wird nicht die Mindestanforderung der Turing-Vollständigkeit erreicht, also die Fähigkeit, alles Berechenbare zu berechnen
  • Um lambda einzufügen, wurden assoc(x,y) und pairlis(x,y) ergänzt
    • assoc(x,y) ist ein als Liste implementierter Schlüssel/Wert-Lookup auf Basis einer Assoziationsliste
    • pairlis(x,y) bündelt zwei Listen ähnlich wie zip(x,y) in Python
  • Ursprüngliches Lisp musste selbst einfache lineare Scans per Rekursion verarbeiten
    • Der Grund ist, dass es im ursprünglichen Lisp keine Schleifen gab
    • In der Python-Übersetzung lassen sich assoc und pairlis mit List Comprehensions knapper ausdrücken
  • Bei der Verarbeitung von COND wird das ursprüngliche evcon in eine Schleife übersetzt, und bei der Verarbeitung von LAMBDA wird dieselbe Methode auf evlis angewendet

Umgebungsliste und dynamischer Scope

  • Die ursprüngliche eval-Funktion in Lisp nimmt zwei Argumente entgegen
    • Das erste Argument ist das auszuwertende S-expression
    • Das zweite Argument ist eine Umgebungsliste aus Schlüssel/Wert-Einträgen
  • Die Umgebung hält bei der Verarbeitung von LAMBDA die Variablenbindungen aufrecht
    • Wenn eine Funktion die Variable x hat und Daten eingesetzt werden, verknüpft pairlis das Symbol x mit den Daten
    • Die verknüpften Werte werden in der Umgebungsliste gespeichert oder ihr hinzugefügt
    • Wenn x benötigt wird, findet assoc es in der Umgebung und setzt es wieder in den Ausdruck ein
  • Diese Art der Bindung wird dynamischer Scope genannt
  • Die endgültige Implementierung ist eine Übertragung des ursprünglichen „Lisp in Lisp“ nach Python und umfasst im letzten Beispiel auch die Ausführung von lambda

Verwandte Beiträge

2 Kommentare

 
GN⁺ 2024-05-13
Hacker-News-Kommentare

  • Wenn man sich für ein einfaches und schnelles Python-artiges Skripting-Lisp interessiert, sind Hy und Janet als Sprachen im Clojure-Stil einen Blick wert.

    1. Hy(https://hylang.org/): Kompiliert zu Python-Bytecode, ist in der Regel langsamer als Python, aber mit allen Python-Bibliotheken kompatibel.
    2. Janet(https://janet-lang.org/): Eine sehr leichte eingebettete VM im Lua-Stil von rund 1 MB, bei ähnlichen Operationen ungefähr doppelt so schnell wie Python, und C-Interoperabilität ist sehr einfach.
    • Für schnelles Python-artiges Skripting gibt es auch https://github.com/ciel-lang/ciel, ein Common Lisp mit Batteries Included.
      Es wird als Binary für einen schnellen Start bereitgestellt und enthält auch Bibliotheken für Alltagsaufgaben.
      Für die Richtung CL↔Python ist auch https://github.com/CodyReichert/awesome-cl?tab=readme-ov-fil... sehenswert.
    • Hy ist langsamer als Python? Zumindest bei der Laufzeit sollte das nicht so sein.
      Ich bin Hy-Maintainer, und wenn man einen nennenswerten Performance-Unterschied sieht, ist das ein Bug.
      1. Basilisp(https://github.com/basilisp-lang/basilisp): „Ein Clojure-kompatibler-ish Lisp-Dialekt für Python 3.8+“
    • Das mag wie eine Marotte wirken, aber Lisp fühlte sich für mich wegen der unvermeidlichen umschließenden Klammern immer wie eine Sprache, die Widerspruch herausfordert, an.
      M-Expressions vermeiden diese Falle, daher frage ich mich, ob es je eine echte Sprache gab, die die Homoikonizität und konzeptionelle Eleganz von Lisp beibehielt, aber solche Klammern nicht verlangte.
    • https://github.com/yaml/yamlscript
      Genau das, was man denkt. Die Erklärung ist auch sehr direkt: „Program in YAML“
      Mehr muss man kaum sagen.

  • Moment, ist das nicht einfach nur ein in Python implementiertes Lisp?
    Es scheint kein homoikonisches Python zu sein, wie der Titel andeutet — übersehe ich etwas?

    • Nach Greenspuns zehntem Gesetz stimmt das: https://en.m.wikipedia.org/wiki/Greenspun's_tenth_rule
    • Ich war auch ziemlich begeistert, weil ich dachte, es sei ein homoikonisches Python, mit dem ich Kollegen Lisp nutzen lassen könnte, ohne sie dazu bringen zu müssen, Lisp zu akzeptieren, aber nein, es war einfach Lisp.
    • Sieht so aus. Ich war neugierig, weil ich dieses homoikonische Python sehen wollte, weiß aber nicht einmal, ob das möglich ist.
      Dafür müsste die Python-Syntax aus Tupeln, Listen und Dictionaries bestehen, und der Interpreter müsste sie direkt auswerten.
    • Was ist der Unterschied?

  • Als weitere funktionale Sprache, die sich kompakt in Python implementieren lässt, gibt es den Binary Lambda Calculus.
    Ein großer Teil des Codes behandelt das reine Ein-/Ausgabe-Modell von BLC, und für Variablen-Lookups wird statt einer Assoziationsliste ein Umgebungs-Array per de-Bruijn-Indizes indiziert.
    Auf derselben Seite gibt es auch Implementierungen in neun weiteren Sprachen, und der Selbstinterpreter von BLC ist mit 232 Bit (29 Byte) inklusive Parser und Tokenizer am kompaktesten.
    [1] https://rosettacode.org/wiki/Universal_Lambda_Machine#Python

  • Im MIT-Grundlagenkurs Programmierung müssen alle Studierenden einen Lisp-Interpreter in Python schreiben.
    Das ist ein Überbleibsel aus der Zeit, als der Kurs tatsächlich in Lisp gehalten wurde.
    https://py.mit.edu/spring24

    • Ähnlich musste ich in einem Kurs an der Uni einen grundlegenden Lisp-Interpreter in Lisp implementieren.

  • Ich habe etwas Ähnliches einmal mit JS-Listen gemacht: https://github.com/andrelaszlo/js-lisp

  • Es ist irgendwie lustig und ironisch, dass moderne Sprachen nach Jahrzehnten die erstaunlichen Fähigkeiten von Lisp wiederentdecken.
    Vor ein paar Tagen blieb ein Python-Programm stehen, das 9 Stunden lang meine Home-Server-API aufgerufen hatte, und ich war ziemlich genervt. Es waren ähnliche API-Aufrufe, und ich rief ein LLM mit vordefinierten Prompt-Templates und Syntaxbeschränkungen auf.
    Ich wollte den Programmzustand speichern und beenden, bevor ich die verbleibenden Iterationen separat laufen lasse, aber ich fand keine Möglichkeit, den laufenden Python-Code zu ändern oder Variablen zu inspizieren, und verlor am Ende 9 Stunden Arbeit.
    Ein paar Tage später sah ich https://malisper.me/debugging-lisp-part-1-recompilation/ und war erstaunt, dass Common Lisp solche Funktionen schon vor Jahrzehnten direkt in die Sprache eingebaut hatte. Dasselbe gilt für andere Features wie das wohl mächtigste Makro-System.

    • Es ist nicht überraschend, dass moderne Sprachen nach Jahrzehnten Lisp-Features wiederentdecken. Die Lisp-Familie gehört zu den flexibelsten und ausdrucksstärksten Sprachen überhaupt.
      Aber genau das ist auch das Problem. Sie ist zu ausdrucksstark.
      Lisp erinnert mich immer an visuelle Mixed-Media-Kunst: Ausdrucksfreiheit wirkt großartig, aber am Ende fallen die Ergebnisse oft schwächer aus als bei traditionellerer Kunst mit nur einem Medium. Das zeigt, dass Beschränkungen des Mediums genauso wichtig sind wie Ausdruckskraft.
    • Um den Zustand zumindest teilweise zu inspizieren, kann man Py-spy oder Pystack verwenden.
      Oder auch https://github.com/malor/cpython-lldb.
      Weitere Möglichkeiten: https://github.com/albertz/pydbattach/
    • Bei Prozessen, die mehrere Stunden laufen, sollte man die Arbeit auf die Festplatte speichern und darauf vorbereitet sein, ab dem Unterbrechungspunkt neu zu starten.
    • Wurde keine Exception ausgelöst?

  • Inwiefern ist diese Implementierung eigentlich homoikonisches Python?

  • Gibt es ein Lisp mit einem Typsystem, das die Tendenz von Lisp, bei größeren Programmen schwer lesbar zu werden, einigermaßen in den Griff bekommt?
    Auch wenn es kein Typsystem ist, würde mich interessieren, ob es andere Mittel gibt, diese Eigenschaft zu zähmen.
    Metaprogrammierung ist wirklich großartig, aber manchmal liest es sich wie das abstruseste abstrakte Haskell, das ich je gesehen habe, nur ohne Typsignaturen als Orientierungshilfe.
    Ich halte Typsysteme und Linter für die besten Werkzeuge, um Code automatisch zu bändigen, aber ich kann mir schwer vorstellen, wie man die Tendenzen in Lisp-Projekten eindämmen kann, ohne genau das einzuschränken, weshalb man sich überhaupt für Lisp entscheidet.

    • Wenn es um Lisp mit Typsystem geht, fällt mir Common Lisp ein.
      SBCL, das der De-facto-Standardimplementierung wohl am nächsten kommt, ist bei Typprüfungen zur Compile-Zeit tatsächlich ziemlich gut.
      Wenn man zum Beispiel nach (declare (type String a b)) (+ a b) schreibt, meldet es eine Warnung, dass der abgeleitete Typ von A STRING ist, aber NUMBER sein müsste.
      Der Hauptgrund, warum ich von Scheme zu CL gewechselt bin, war diese Typprüfung, und danach bin ich wegen kleiner, aber großartiger Features wie Restarts und continuable asserts geblieben.
    • Die freundliche und leicht zugängliche Option ist Typed Racket, die mächtige, aber komplexe Option ist Shen.
    • https://en.wikipedia.org/wiki/Dylan_(programming_language)

  • Ausdrucksorientiertes Python wäre viel besser als das heutige Python.
    Darum geht es in diesem Artikel zwar nicht, trotz dessen, was der Titel andeutet, aber als Erklärung von Lisp ist er gut.

    • Ausdrucksorientiertes Python wäre einfach nicht mehr Python.
      Das wäre zwar in Ordnung, aber „Ausdrücke als Syntax zweiter Klasse zu behandeln“ ist eine ziemlich grundlegende und absichtliche Entscheidung. Das Design soll es Entwicklern, die Klammer-Suppe schreiben wollen, bewusst schwer machen.
      Deshalb sind lambda: und := absichtlich unbeholfen, um ihren Einsatz zu bremsen, und man kann auch keine anonymen Funktionen schreiben.
      Python ist eine Sprache, die sagt: Wenn du etwas Cleveres machen willst, dann mach es mit Iteratoren statt mit aufrufbaren Objekten.

  • Ich wünschte, alles hätte Lisp-artige Syntaxlosigkeit.
    Für mich ist das besser, und zum Glück ist das in CL leicht zu erreichen.
 
kayws426 2024-05-13

Ein in Python eingebetteter Lisp-Dialekt
https://hylang.org/