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

Question

Ist eine statisch typisierte vollständige Lisp-Variante möglich? Macht es überhaupt Sinn, dass so etwas existiert? Ich glaube, eine der Tugenden der Lisp-Sprache ist die Einfachheit ihrer Definition. Würde das statische Schreiben dieses Kernprinzip kompromittieren?

Answer 1

Meine Antwort, ohne ein hohes Maß an Vertrauen ist wahrscheinlich. Wenn Sie beispielsweise eine Sprache wie SML betrachten und diese mit Lisp vergleichen, ist der funktionale Kern der beiden fast identisch. Daher scheint es nicht so, als hätten Sie große Schwierigkeiten, eine Art von statischer Typisierung auf den Kern von Lisp anzuwenden (Funktionsanwendung und Grundwerte).

Ihre Frage sagt voll obwohl, und wo ich sehe, einige der Probleme kommen in ist der Code-als-Daten-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 Repräsentation seines Typs ist), und dann betrachten wir diesen Ausdruck als einfache ol Daten, was genau ist dann der Typ von T hier? Nun, es ist eine Art! Eine Art ist eine höhere, Auftragsart, so lassen Sie uns fortfahren gerade und etwas darüber sagen, dass in unserem Code:

E : T :: K 

Sie können sehen, wo ich mit diesem gehe. Ich bin mir sicher, dass es durch die Trennung der Typinformationen vom Code möglich wäre, diese Art von Selbstreferentialität der Typen zu vermeiden, jedoch würde dies die Typen nicht sehr "lispeln" lassen. Es gibt wahrscheinlich viele Möglichkeiten, obwohl es für mich nicht offensichtlich ist, welches das Beste wäre.

EDIT: Oh, also mit ein wenig Googeln, fand ich Qi, die Lisp sehr ähnlich zu sein scheint, außer dass es statisch getippt ist. Vielleicht ist es ein guter Ort, um zu sehen, wo sie Änderungen vorgenommen haben, um die statische Eingabe dorthin zu bekommen.

Answer 2

Ja, es ist sehr möglich, obwohl ein Standard-HM-style-Typ-System in der Regel die falsche Wahl für die meisten idiomatischen Lisp/Scheme-Code ist. Eine neuere Sprache, die ein "Full Lisp" (mehr wie Scheme, eigentlich) mit statischer Typisierung ist, siehe Typed Racket.

Answer 3

Dylan: http://visualization.dylan-user.org/diploma.pdf

Answer 4

Wenn alles, was Sie wurde Sprache eine statisch typisierte wolltest, dass wie Lisp sah man das tun könnte ziemlich leicht, durch einen abstrakten Syntaxbaum definiert, für die verwendete Sprache und dann Zuordnung, den ASTS S-Ausdrücke. Ich glaube jedoch nicht, dass ich das Ergebnis Lisp nennen würde.

Wenn Sie etwas wollen, das Lisp-y-Eigenschaften neben der Syntax hat, ist es möglich, dies mit einer statisch typisierten Sprache zu tun. Es gibt jedoch viele Eigenschaften, die für Lisp schwierig zu erreichen sind. Betrachten wir zur Veranschaulichung die Listenstruktur selbst, die cons genannt wird, die den primären Baustein von Lisp bildet.

Aufruf der Cons eine Liste, obwohl (1 2 3) wie eins aussieht, ist ein bisschen falsch. Zum Beispiel ist es überhaupt nicht vergleichbar mit einer statisch getippten Liste, wie C++ std::list oder Haskells Liste. Dies sind eindimensionale verkettete Listen, in denen alle Zellen vom selben Typ sind. Lisp erlaubt glücklich (1 "abc" #\d 'foo). Selbst wenn Sie Ihre Static-typed-Listen so erweitern, dass sie Listen von Listen abdecken, erfordert der Typ dieser Objekte, dass jedes Element der Liste eine Unterliste ist. Wie würdest du ((1 2) 3 4) in ihnen darstellen?

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

Wie würden Sie eine solche Struktur in einer statisch typisierten Sprache modellieren? Lassen Sie sich versuchen, es in Haskell, die ein extrem leistungsfähiges und präzises statisches Typsystem hat:

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

Ihr erstes Problem sein wird, der Umfang des Atom-Typs. Natürlich haben wir uns nicht für einen Atom-Typ entschieden, der genügend Flexibilität bietet, um alle Arten von Objekten abzudecken, die wir in Kondensstreifen herumschleppen wollen. Anstatt zu versuchen, die oben aufgelistete Atom-Datenstruktur zu erweitern (die man deutlich sehen kann, ist sie spröde), haben wir 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 

Aber das wird nicht funktionieren, weil es alle Atome in dem Baum erfordert der gleichen Typ zu sein. Wir wollen, dass sie sich von Blatt zu Blatt unterscheiden können. Ein besserer Ansatz erfordert die Verwendung von Haskell Existenzquantoren:

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

Aber jetzt Sie zum Kern der Sache kommen. Was können Sie mit Atomen in dieser Art von Struktur tun? Welche Struktur haben sie gemeinsam, die mit Atomic a modelliert werden könnte? Welche Sicherheitsebene ist bei einem solchen Typ gewährleistet? Beachten Sie, dass wir unserer Typklasse keine Funktionen hinzugefügt haben, und das hat einen guten Grund: Die Atome haben in Lisp nichts gemeinsam. Ihr Supertyp in Lisp wird einfach t (d. H. Oben) genannt.

Um sie zu verwenden, müssten Sie mit Mechanismen dynamisch den Wert eines Atoms auf etwas, das Sie tatsächlich verwenden können, erzwingen. Und an diesem Punkt haben Sie im Grunde ein dynamisch typisiertes Subsystem in Ihrer statisch typisierten Sprache implementiert! (Man kann nicht umhin, eine mögliche logische Folge Greenspun's Tenth Rule of Programming beachten.)

Bitte beachte, dass Haskell bietet Unterstützung für solche nur ein dynamic subsystem mit einem Obj Typ, verwendet in Verbindung mit einem Dynamic Typ und einem Typeable class unserer Atomic Klasse zu ersetzen, die ermöglichen, Beliebige Werte, die mit ihren Typen gespeichert werden sollen, und ausdrückliche Nötigung von diesen Typen. Das ist die Art von System, das Sie verwenden müssen, um mit Lisp-Cons-Strukturen in ihrer vollen Allgemeinheit zu arbeiten.

Sie können auch einen anderen Weg gehen und ein statisch typisiertes Subsystem in eine im Wesentlichen dynamisch typisierte Sprache einbetten. Dies ermöglicht Ihnen den Vorteil der statischen Typprüfung für die Teile Ihres Programms, die von strengeren Typanforderungen profitieren können. Dies scheint der Ansatz zu sein, der zum Beispiel in der beschränkten Form von CMUCL precise type checking verwendet wird.

Schließlich gibt es die Möglichkeit, zwei separate Subsysteme zu haben, dynamisch und statisch typisiert, die Contract-style-Programmierung verwenden, um den Übergang zwischen den beiden zu navigieren. Auf diese Weise kann die Sprache Lisp-Verwendungen Rechnung tragen, bei denen die Überprüfung des statischen Typs eher ein Hindernis als eine Hilfe wäre, sowie Anwendungen, bei denen eine Überprüfung des statischen Typs vorteilhaft wäre. Dies ist der Ansatz von Typed Racket, wie Sie aus den folgenden Kommentaren sehen können.