Typinferenz für andere zwingende Anweisungen als Zuweisung

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?

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$\forall \alpha. \mbox{ref}(\mbox{option}(\alpha))$x$\Lambda \alpha. \mbox{ref}[\alpha](\mbox{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.

Die Doktorarbeit von Xavier Leroy ist ein guter Anfang.

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.