Kann mir jemand das abhängige Tippen erklären? Ich habe wenig Erfahrung mit Haskell, Cayenne, Epigram oder anderen funktionalen Sprachen. Je einfacher die Begriffe, die Sie verwenden können, desto mehr werde ich es zu schätzen wissen!
83
Antworten:
Bedenken Sie Folgendes: In allen anständigen Programmiersprachen können Sie Funktionen schreiben, z
Hier
f
nimmt ein Wertarg
und berechnet einen Wertresult
. Es ist eine Funktion von Werten zu Werten.In einigen Sprachen können Sie jetzt polymorphe (auch als generische) Werte definieren:
Hier
empty
nimmt ein TypT
und berechnet einen Wert. Es ist eine Funktion von Typen zu Werten.Normalerweise können Sie auch generische Typdefinitionen haben:
Diese Definition nimmt einen Typ an und gibt einen Typ zurück. Es kann als eine Funktion von Typ zu Typ angesehen werden.
Soviel zu dem, was gewöhnliche Sprachen bieten. Eine Sprache wird als abhängig typisiert bezeichnet, wenn sie auch die vierte Möglichkeit bietet, nämlich Funktionen von Werten bis zu Typen zu definieren. Mit anderen Worten: Parametrisieren einer Typdefinition über einen Wert:
Einige Mainstream-Sprachen haben eine gefälschte Form davon, die nicht zu verwechseln ist. In C ++ können Vorlagen beispielsweise Werte als Parameter annehmen, sie müssen jedoch bei der Anwendung Konstanten zur Kompilierungszeit sein. Nicht so in einer wirklich abhängigen Sprache. Zum Beispiel könnte ich den obigen Typ wie folgt verwenden:
Hier hängt der Ergebnistyp der Funktion vom tatsächlichen Argumentwert
j
und damit von der Terminologie ab.quelle
BoundedInt
Beispiel nicht tatsächlich ein Verfeinerungstyp? Das ist 'ziemlich nah', aber nicht genau die Art von 'abhängigen Typen', die z. B. Idris zuerst in einem Tutorial über dep.typing erwähnt.Abhängige Typen ermöglichen die Beseitigung größerer logischer Fehler beim Kompilieren . Um dies zu veranschaulichen, betrachten Sie die folgende Spezifikation der Funktion
f
:Ohne abhängige Typen könnten Sie so etwas tun:
Hier kann der Compiler nicht erkennen, ob er
n
tatsächlich gerade ist, dh aus Sicht des Compilers ist der folgende Ausdruck in Ordnung:Dieses Programm würde ausgeführt und dann zur Laufzeit eine Ausnahme auslösen, dh Ihr Programm hat einen logischen Fehler.
Abhängige Typen ermöglichen es Ihnen, viel ausdrucksvoller zu sein und so etwas zu schreiben:
Hier
n
ist vom abhängigen Typ{n: Integer | n mod 2 == 0}
. Es könnte hilfreich sein, dies laut vorzulesenIn diesem Fall würde der Compiler zur Kompilierungszeit einen logischen Fehler erkennen, an den Sie eine ungerade Zahl übergeben haben,
f
und die Ausführung des Programms an erster Stelle verhindern:Hier ist ein anschauliches Beispiel unter Verwendung von Scala- Pfad-abhängigen Typen, wie wir versuchen könnten, Funktionen zu implementieren,
f
die eine solche Anforderung erfüllen:case class Integer(v: Int) { object IsEven { require(v % 2 == 0) } object IsOdd { require(v % 2 != 0) } } def f(n: Integer)(implicit proof: n.IsEven.type) = { // do something with n safe in the knowledge it is even } val `42` = Integer(42) implicit val proof42IsEven = `42`.IsEven val `1` = Integer(1) implicit val proof1IsOdd = `1`.IsOdd f(`42`) // OK f(`1`) // compile-time error
Der Schlüssel ist zu bemerken, wie Wert
n
in der Art des Wertes erscheint,proof
nämlichn.IsEven.type
:Wir sagen, Typ
n.IsEven.type
hängt vom Wert ab,n
daher der Begriff abhängige Typen .quelle
f(random())
Kompilierungsfehler auftreten?f
auf einen Ausdruck würde erfordern, dass der Compiler (mit oder ohne Ihre Hilfe) bereitstellt, dass der Ausdruck immer gerade ist, und es gibt keinen solchen Beweis dafürrandom()
(da er tatsächlich ungerade sein kann), weshalb erf(random())
nicht kompiliert werden kann.Wenn Sie C ++ kennen, können Sie leicht ein motivierendes Beispiel liefern:
Nehmen wir an, wir haben einen Containertyp und zwei Instanzen davon
typedef std::map<int,int> IIMap; IIMap foo; IIMap bar;
und betrachten Sie dieses Codefragment (Sie können annehmen, dass foo nicht leer ist):
Dies ist offensichtlicher Müll (und beschädigt wahrscheinlich die Datenstrukturen), aber es wird eine gute Typprüfung durchführen, da "Iterator in foo" und "Iterator in bar" vom gleichen Typ sind
IIMap::iterator
, obwohl sie semantisch völlig inkompatibel sind.Das Problem ist , dass ein Iteratortyp nicht sollte nur auf dem Behälter hängt Art , aber in der Tat auf dem Behälter Objekt , dh es sollte einen „nicht-statischen Member - Typ“ sein:
foo.iterator i = foo.begin(); bar.erase(i); // ERROR: bar.iterator argument expected
Ein solches Merkmal, die Fähigkeit, einen Typ (foo.iterator) auszudrücken, der von einem Begriff (foo) abhängt, ist genau das, was abhängige Typisierung bedeutet.
Der Grund, warum Sie diese Funktion nicht oft sehen, ist, dass sie eine große Dose Würmer öffnet: Sie geraten plötzlich in Situationen, in denen Sie zum Zeitpunkt der Kompilierung prüfen müssen, ob zwei Typen gleich sind, und zwei Ausdrücke beweisen müssen sind äquivalent (ergibt zur Laufzeit immer den gleichen Wert). Wenn Sie die Liste der abhängig typisierten Sprachen von Wikipedia mit der Liste der Theorembeweiser vergleichen, stellen Sie möglicherweise eine verdächtige Ähnlichkeit fest. ;-);
quelle
Zitieren des Buches Typen und Programmiersprachen (30.5):
quelle