Typinferenz für andere zwingende Anweisungen als Zuweisung

10

Auf meiner Suche nach Forschungsarbeiten über Typensysteme für imperative Sprachen finde ich nur Lösungen für eine Sprache mit veränderlichen Referenzen, aber ohne echte imperative Kontrollstrukturen wie zusammengesetzte Operatoren, Schleifen oder Bedingungen.

Es ist also nicht klar, wie eine imperative Sprache mit partieller Typinferenz wie http://rust-lang.org implementiert werden kann.

In den Veröffentlichungen werden parametrisierte Typen nicht erwähnt, z. B. List of aweil parametrisierte Typen eine triviale Erweiterung des Hindley-Milner-Typsystems darstellen. Nur der Vereinigungsalgorithmus sollte erweitert werden, und der Rest der Inferenz funktioniert unverändert. Zuweisungen können jedoch nicht trivial hinzugefügt werden, da Paradoxe auftreten. Daher müssen spezielle Techniken wie die Einschränkung des ML-Werts angewendet werden.

Können Sie Artikel oder Bücher empfehlen, die ein Typensystem für eine Sprache mit Imperativschleifen, Bedingungen, E / A und zusammengesetzten Anweisungen beschreiben?

nponeccop
quelle
4
Ich bin mir nicht sicher, ob ich die Quelle Ihrer Frage verstehe, teilweise weil Standard ML tatsächlich zusammengesetzte Operatoren, Schleifen und Bedingungen hat (einzeiliges Beispiel :) let val x = ref 9 in while !x>0 do (print (Int.toString (!x)); x := !x-1) end. Ist die Antwort, die Sie auf der Ebene einer Forschungsfrage suchen, "Anwenden von in Caml / SML entwickelten Techniken, einschließlich der Werteinschränkung"?
Rob Simmons
Die Frage war: "Welche Artikel über die für Caml / SML entwickelten Techniken empfehlen Sie?"
Nponeccop
Ok - ich hatte das herausgefunden und wollte gerade versuchen, meinen letzten Satz zu bearbeiten, um zu sagen: "Ist das, was Sie suchen, eine zugängliche Referenz für die Inferenz vom Typ Hindley-Milner, wie sie in ML verwendet wird?" Und dann habe ich das 5-Minuten-Bearbeitungslimit erreicht :-)
Rob Simmons

Antworten:

14

Wenn Sie nach einer ordentlichen, funktionalen Referenz zur Typinferenz suchen, bin ich ein bisschen parteiisch gegenüber Gundry, McBride und McKinnas 2010 "Typinferenz im Kontext ", obwohl dies möglicherweise kein guter Leitfaden für tatsächlich vorhandene Implementierungen ist .

Ich denke, ein Teil der Antwort ist, dass es jenseits der Wertebeschränkung wirklich nicht so schwierig ist, die Inferenz des Hindley-Milner-Typs an imperative Sprachen anzupassen: Wenn Sie e1; e2als syntaktischen Zucker für (fn _ => e2) e1und while e1 do e2als syntaktischen Zucker für definieren whiledo e1 (fn () => e2), wo whiledoist ein regulärer rekursive Funktion

fun whiledo g f = if g then (f (); whiledo g f) else ();

dann wird alles gut funktionieren, einschließlich Typinferenz.

Was die Wertebeschränkung betrifft, die eine spezielle Technik ist, mag ich die folgende Geschichte; Ich bin mir ziemlich sicher, dass ich es von Karl Crary abgeholt habe. Betrachten Sie den folgenden Code, den Sie aufgrund der Werteinschränkung nicht in ML schreiben können:

let
   val x: 'a option ref = ref NONE
in
   (x := SOME 5; x := SOME "Hello")  
end

Vergleichen Sie es mit dem folgenden Code, der völlig unproblematisch ist:

let
   val x: unit -> 'a option ref = fn () => ref NONE
in
   (x () := SOME 5; x () := SOME "Hello")  
end

Wir wissen , was das zweite Beispiel macht: es schafft zwei neue ref Zellen enthält NONE, dann setzt SOME 5in der ersten (ein int option ref), dann setzt SOME "Hello"in der zweiten (a string option ref).

xxα.ref(option(α))xΛα.ref[α](NONE)

Dies würde darauf hinweisen, dass ein "gutes" Verhalten des ersten Beispiels darin besteht, sich genauso zu verhalten wie das zweite Beispiel - das Lambda auf Typebene zwei verschiedene Male instanziieren. Das erste Mal instanziieren wir xmit int, was dazu führt, dass x [int]eine Referenzzelle gehalten wird NONEund dann SOME 5. Das zweite Mal instanziieren wir xmit string, was x [string]zu einem ( anderen! ) Referenzzellen-Holding führen wird NONEund dann SOME "Hello". Dieses Verhalten ist "korrekt" (typsicher), aber es ist definitiv nicht das, was ein Programmierer erwarten würde, und deshalb haben wir die Wertbeschränkung in ML, um zu vermeiden, dass Programmierer mit dieser unerwarteten Art von Verhalten umgehen.

Rob Simmons
quelle
1
Ihre Desugared-Version von e1; e2enthält eine nicht übereinstimmende Klammer und ein Semikolon (das definiert werden soll). Meinten Sie (fn _ => e2) e1?
Tsuyoshi Ito
Richtig, Tsuyoshi: behoben.
Rob Simmons
Ihr letzter Absatz sagt im Grunde: Die (Betriebs-) Semantik und das Typensystem stimmen nicht überein, man muss repariert werden, und wir entscheiden uns, letzteres zu reparieren.
Radu GRIGore
Radu: Klar, ich stimme dieser Zusammenfassung zu.
Rob Simmons
3

Die Doktorarbeit von Xavier Leroy ist ein guter Anfang.

Dominic Mulligan
quelle
1
Die Arbeit behandelt nicht Imperativschleifen, Bedingungen, E / A und zusammengesetzte Anweisungen, oder? Der Hauptgrund für meine Frage war, dass ich keine Artikel zu diesen Themen finden konnte. Papiere über Schreibaufgaben sind reichlich vorhanden.
Nponeccop
0

Es tut mir leid, dass ich meine eigene Frage beantwortet habe, aber die fragliche Referenz ist

Ein Vorschlag für Standard ML , Milner, 1983

Teil 6 "Standard Derived Forms" befasst sich ziemlich ausführlich mit dem Desugaring von imperativen Konstrukten. Und bis jetzt ist es die früheste Referenz dieser weitgehend offensichtlichen Transformationen, die ich finden konnte.

nponeccop
quelle