Ist eine statisch typisierte vollständige Lisp-Variante möglich?

107

Ist eine statisch typisierte vollständige Lisp-Variante möglich? Ist es überhaupt sinnvoll, dass so etwas existiert? Ich glaube, eine der Tugenden einer Lisp-Sprache ist die Einfachheit ihrer Definition. Würde statische Typisierung dieses Kernprinzip beeinträchtigen?

Lambda der Vorletzte
quelle
10
Ich mag die Freiform-Makros von Lisp, aber ich mag die Robustheit des Haskell-Typsystems. Ich würde gerne sehen, wie ein statisch typisierter Lisp aussieht.
Mcandre
4
Gute Frage! Ich glaube, shenlanguage.org macht das. Ich wünschte, es wäre mehr Mainstream geworden.
Hamish Grubijan
Wie macht man symbolisches Computing mit Haskell? (Löse 'x' (= (+ xy) (* xy))). Wenn Sie es in eine Zeichenfolge einfügen, erfolgt keine Überprüfung (im Gegensatz zu Lisp, bei dem Makros zum Hinzufügen von Überprüfungen verwendet werden können). Wenn Sie algebraische Datentypen oder Listen verwenden ... Es wird sehr ausführlich sein: lösen (Sym "x") (Gl. (Plus (Sym "x") (Sym "y")) (Mult (Sym "x") (Sym "y")))
aoeu256

Antworten:

57

Ja, das ist sehr gut möglich, obwohl ein Standard-HM-System normalerweise die falsche Wahl für den meisten idiomatischen Lisp / Scheme-Code ist. Unter Typed Racket finden Sie eine aktuelle Sprache, die ein "Full Lisp" (eigentlich eher wie "Scheme") mit statischer Typisierung ist.

Eli Barzilay
quelle
1
Das Problem hierbei ist, welche Art von Liste den gesamten Quellcode eines typisierten Schlägerprogramms ausmacht.
Zorf
18
Das wäre normalerweise so Sexpr.
Eli Barzilay
Aber dann kann ich coerce :: a->bin Bezug auf die Bewertung schreiben . Wo ist die Typensicherheit?
ssice
2
@ssice: Wenn Sie eine untypisierte Funktion verwenden, wie evalSie das Ergebnis testen müssen, um zu sehen, was herauskommt, was in Typed Racked nichts Neues ist (dasselbe Angebot wie bei einer Funktion, die einen Union-Typ von Stringund verwendet Number). Ein impliziter Weg, um zu sehen, dass dies möglich ist , ist die Tatsache, dass Sie eine dynamisch typisierte Sprache in einer HM-statisch typisierten Sprache schreiben und verwenden können .
Eli Barzilay
37

Wenn Sie nur eine statisch typisierte Sprache wollten, die wie Lisp aussah , können Sie dies ziemlich einfach tun, indem Sie einen abstrakten Syntaxbaum definieren, der Ihre Sprache darstellt, und diesen AST dann S-Ausdrücken zuordnen. Ich glaube jedoch nicht, dass ich das Ergebnis Lisp nennen würde.

Wenn Sie etwas möchten, das neben der Syntax auch Lisp-y-Eigenschaften aufweist, können Sie dies mit einer statisch typisierten Sprache tun. Es gibt jedoch viele Eigenschaften von Lisp, aus denen sich nur schwer nützliche statische Eingaben ableiten lassen. Schauen wir uns zur Veranschaulichung die Listenstruktur selbst an, die als Nachteile bezeichnet wird und den Hauptbaustein von Lisp bildet.

Die Nachteile als Liste zu bezeichnen, obwohl es so (1 2 3)aussieht, ist eine Fehlbezeichnung. Zum Beispiel ist es überhaupt nicht vergleichbar mit einer statisch typisierten Liste wie der von C ++ std::listoder Haskell. Dies sind eindimensionale verknüpfte Listen, in denen alle Zellen vom gleichen Typ sind. Lisp erlaubt gerne (1 "abc" #\d 'foo). Selbst wenn Sie Ihre statisch typisierten Listen auf Listenlisten erweitern, erfordert der Typ dieser Objekte, dass jedes Element der Liste eine Unterliste ist. Wie würden Sie ((1 2) 3 4)in ihnen vertreten?

Lisp-Konsen bilden einen binären Baum mit Blättern (Atomen) und Zweigen (Konsen). Außerdem können die Blätter eines solchen Baumes überhaupt einen atomaren (Nicht-Nachteile) Lisp-Typ enthalten! Die Flexibilität dieser Struktur macht Lisp so gut im Umgang mit symbolischen Berechnungen, ASTs und der Transformation von Lisp-Code selbst!

Wie würden Sie eine solche Struktur in einer statisch typisierten Sprache modellieren? Versuchen wir es in Haskell, das über ein äußerst leistungsfähiges und präzises statisches Typsystem verfügt:

type Symbol = String
data Atom = ASymbol Symbol | AInt Int | AString String | Nil
data Cons = CCons Cons Cons 
            | CAtom Atom

Ihr erstes Problem wird der Umfang des Atom-Typs sein. Es ist klar, dass wir keinen Atom-Typ mit ausreichender Flexibilität ausgewählt haben, um alle Arten von Objekten abzudecken, die wir in Kegeln herumschleudern möchten. Anstatt zu versuchen, die Atom-Datenstruktur wie oben aufgeführt zu erweitern (was Sie deutlich sehen können, ist spröde), nehmen wir an, wir hatten eine magische Typklasse Atomic, die alle Typen unterschied, die wir atomar machen wollten. Dann könnten wir versuchen:

class Atomic a where ?????
data Atomic a => Cons a = CCons Cons Cons 
                          | CAtom a

Dies funktioniert jedoch nicht, da alle Atome im Baum vom gleichen Typ sein müssen. Wir möchten, dass sie sich von Blatt zu Blatt unterscheiden können. Ein besserer Ansatz erfordert die Verwendung von Haskells existenziellen Quantifizierern :

class Atomic a where ?????
data Cons = CCons Cons Cons 
            | forall a. Atomic a => CAtom a 

Aber jetzt kommen Sie zum Kern der Sache. Was kann man mit Atomen in dieser Art von Struktur machen? Welche Struktur haben sie gemeinsam, mit der modelliert werden könnte Atomic a? Welches Maß an Typensicherheit ist Ihnen bei einem solchen Typ garantiert? Beachten Sie, dass wir unserer Typklasse keine Funktionen hinzugefügt haben, und es gibt einen guten Grund: Die Atome haben in Lisp nichts gemeinsam. Ihr Supertyp in Lisp wird einfach t(dh oben) genannt.

Um sie zu verwenden, müssten Sie Mechanismen entwickeln, um den Wert eines Atoms dynamisch auf etwas zu zwingen, das Sie tatsächlich verwenden können. Und zu diesem Zeitpunkt haben Sie im Grunde ein dynamisch typisiertes Subsystem in Ihrer statisch typisierten Sprache implementiert! (Man kann nicht anders, als eine mögliche Folge von Greenspuns zehnter Programmierregel zu bemerken .)

Beachten Sie, dass Haskell ein solches dynamisches Subsystem mit einem ObjTyp unterstützt, der in Verbindung mit einem DynamicTyp und einer typisierbaren Klasse verwendet wird , um unsere AtomicKlasse zu ersetzen , sodass beliebige Werte mit ihren Typen gespeichert werden können, und expliziten Zwang von diesen Typen zurückzwingt . Dies ist die Art von System, die Sie benötigen würden, um mit Lisp-Cons-Strukturen in ihrer vollen Allgemeinheit zu arbeiten.

Sie können auch in die andere Richtung gehen und ein statisch typisiertes Subsystem in eine im Wesentlichen dynamisch typisierte Sprache einbetten. Dies bietet Ihnen den Vorteil einer statischen Typprüfung für die Teile Ihres Programms, die strengere Typanforderungen nutzen können. Dies scheint der Ansatz zu sein, der beispielsweise in der begrenzten Form der präzisen Typprüfung von CMUCL verfolgt wird .

Schließlich besteht die Möglichkeit, zwei separate Subsysteme zu haben, die dynamisch und statisch typisiert sind und die vertragliche Programmierung verwenden, um den Übergang zwischen beiden zu steuern. Auf diese Weise kann die Sprache die Verwendung von Lisp berücksichtigen, bei der die statische Typprüfung eher ein Hindernis als eine Hilfe darstellt, sowie Anwendungen, bei denen die statische Typprüfung vorteilhaft wäre. Dies ist der Ansatz von Typed Racket , wie Sie den folgenden Kommentaren entnehmen können .

Owen S.
quelle
16
Diese Antwort leidet an einem grundlegenden Problem: Sie , dass statische Typsysteme gehen davon müssen HM-Stil sein. Das Grundkonzept, das dort nicht ausgedrückt werden kann und ein wichtiges Merkmal des Lisp-Codes ist, ist die Subtypisierung. Wenn Sie sich typisierte Schläger ansehen, werden Sie feststellen, dass sie leicht jede Art von Liste ausdrücken können - einschließlich Dinge wie (Listof Integer)und (Listof Any). Natürlich würden Sie vermuten, dass Letzteres nutzlos ist, weil Sie nichts über den Typ wissen, aber in TR können Sie es später verwenden, (if (integer? x) ...)und das System wird wissen, dass xes sich um eine Ganzzahl im 1. Zweig handelt.
Eli Barzilay
5
Oh, und es ist eine schlechte Charakterisierung von typisiertem Schläger (die sich von unsoliden Typsystemen unterscheidet, die man an einigen Stellen finden würde). Typed Racket ist eine statisch typisierte Sprache ohne Laufzeitaufwand für typisierten Code. Mit Racket können Sie weiterhin Code in TR und einen Code in der üblichen untypisierten Sprache schreiben. In diesen Fällen werden Verträge (dynamische Überprüfungen) verwendet, um typisierten Code vor dem möglicherweise schlecht benommenen untypisierten Code zu schützen.
Eli Barzilay
1
@Eli Barzilay: Ich habe gelogen, es gibt vier Teile: 4. Es ist interessant für mich, wie sich der branchenübliche C ++ - Codierungsstil allmählich von der Subtypisierung zu Generika entwickelt hat. Die Schwäche ist, dass die Sprache keine Hilfe bietet, um die Schnittstelle zu deklarieren, die eine generische Funktion verwenden soll. Etwas, bei dem Typklassen sicherlich helfen könnten. Außerdem kann C ++ 0x Typinferenz hinzufügen. Nicht HM, nehme ich an, sondern in diese Richtung kriechen?
Owen S.
1
Owen: (1) Der Hauptpunkt ist, dass Sie Subtypen benötigen , um die Art des Schreibens von Code-Lisper auszudrücken - und das können Sie bei HM-Systemen einfach nicht. Daher müssen Sie für jede Verwendung benutzerdefinierte Typen und Konstruktoren verwenden macht das Ganze viel umständlicher zu bedienen. Bei typisierten Schlägern war die Verwendung eines Systems mit Untertypen eine Folge einer absichtlichen Entwurfsentscheidung: Das Ergebnis sollte in der Lage sein, die Typen eines solchen Codes auszudrücken, ohne den Code zu ändern oder benutzerdefinierte Typen zu erstellen.
Eli Barzilay
1
(2) Ja, dynamicTypen werden in statischen Sprachen als eine Art Problemumgehung immer beliebter, um einige der Vorteile dynamisch typisierter Sprachen zu nutzen, wobei der übliche Kompromiss zwischen diesen Werten so gewickelt wird, dass die Typen identifizierbar sind. Aber auch hier macht getippter Schläger einen sehr guten Job darin, ihn innerhalb der Sprache bequem zu machen - die Typprüfung verwendet das Auftreten von Prädikaten, um mehr über die Typen zu erfahren. Sehen Sie sich beispielsweise das typisierte Beispiel auf der Schlägerseite an und sehen Sie, wie string?eine Liste von Zeichenfolgen und Zahlen auf eine Liste von Zeichenfolgen "reduziert" wird.
Eli Barzilay
10

Meine Antwort ohne ein hohes Maß an Vertrauen ist wahrscheinlich . Wenn Sie sich beispielsweise eine Sprache wie SML ansehen und sie mit Lisp vergleichen, ist der Funktionskern jeder Sprache nahezu identisch. Infolgedessen scheint es nicht so, als hätten Sie große Probleme, eine Art statische Typisierung auf den Kern von Lisp anzuwenden (Funktionsanwendung und primitive Werte).

Ihre Frage ist jedoch vollständig , und wo ich sehe, dass einige der Probleme auftreten, ist der Code-as-Data-Ansatz. Typen existieren auf einer abstrakteren Ebene als Ausdrücke. Lisp hat diese Unterscheidung nicht - alles ist "flach" in der Struktur. Wenn wir einen Ausdruck E: T betrachten (wobei T eine Darstellung seines Typs ist) und diesen Ausdruck dann als einfache alte Daten betrachten, was genau ist dann der Typ von T hier? Nun, es ist eine Art! Eine Art ist eine höhere Ordnungsart. Lassen Sie uns also einfach etwas dazu in unserem Code sagen:

E : T :: K

Sie könnten sehen, wohin ich damit gehe. Ich bin sicher, dass es durch Trennen der Typinformationen vom Code möglich wäre, diese Art der Selbstreferenzialität von Typen zu vermeiden, aber dies würde die Typen in ihrem Geschmack nicht sehr "lispeln" lassen. Es gibt wahrscheinlich viele Möglichkeiten, dies zu umgehen, obwohl mir nicht klar ist, welche die beste wäre.

EDIT: Oh, also mit ein bisschen googeln habe ich Qi gefunden , das Lisp sehr ähnlich zu sein scheint, außer dass es statisch typisiert ist. Vielleicht ist es ein guter Ort, um zu sehen, wo sie Änderungen vorgenommen haben, um die statische Eingabe dort zu erhalten.

Gian
quelle
Es scheint, dass die nächste Iteration nach Qi Shen ist , die von derselben Person entwickelt wurde.
Diagon
4

Dylan: Erweiterung des Dylans-Typsystems für eine bessere Typinferenz und Fehlererkennung

Rainer Joswig
quelle
Der Link ist tot. Aber auf jeden Fall ist Dylan nicht statisch typisiert.
Björn Lindqvist
@ BjörnLindqvist: Dieser Link führte zu einer These über das schrittweise Tippen von Dylan.
Rainer Joswig
1
@ BjörnLindqvist: Ich habe auf ein Übersichtspapier verlinkt.
Rainer Joswig
Das schrittweise Tippen zählt jedoch nicht als statisches Tippen. Wenn dies der Fall wäre, wäre Pypy statisch typisiertes Python, da es auch eine schrittweise Eingabe verwendet.
Björn Lindqvist
2
@ BjörnLindqvist: Wenn wir statische Typen durch schrittweise Eingabe hinzufügen und diese während der Kompilierung überprüft werden, handelt es sich um statische Eingabe. Es ist nur nicht so, dass das gesamte Programm statisch typisiert ist, sondern Teile / Regionen. Homes.sice.indiana.edu/jsiek/what-is-gradual-typing 'Die schrittweise Eingabe ist ein Typensystem, das ich 2006 mit Walid Taha entwickelt habe und mit dem Teile eines Programms dynamisch und andere Teile statisch eingegeben werden können.'
Rainer Joswig