Was ist abhängige Eingabe?

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!

Bedenken Sie Folgendes: In allen anständigen Programmiersprachen können Sie Funktionen schreiben, z

def f(arg) = result

Hier fnimmt ein Wert argund berechnet einen Wert result. Es ist eine Funktion von Werten zu Werten.

In einigen Sprachen können Sie jetzt polymorphe (auch als generische) Werte definieren:

def empty<T> = new List<T>()

Hier emptynimmt ein Typ Tund berechnet einen Wert. Es ist eine Funktion von Typen zu Werten.

Normalerweise können Sie auch generische Typdefinitionen haben:

type Matrix<T> = List<List<T>>

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:

type BoundedInt(n) = {i:Int | i<=n}

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:

def min(i : Int, j : Int) : BoundedInt(j) =
  if i < j then i else j

Hier hängt der Ergebnistyp der Funktion vom tatsächlichen Argumentwert jund damit von der Terminologie ab.

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:

Die Funktion fdarf nur gerade Ganzzahlen als Eingabe verwenden.

Ohne abhängige Typen könnten Sie so etwas tun:

def f(n: Integer) := {
  if  n mod 2 != 0 then 
    throw RuntimeException
  else
    // do something with n
}

Hier kann der Compiler nicht erkennen, ob er ntatsächlich gerade ist, dh aus Sicht des Compilers ist der folgende Ausdruck in Ordnung:

f(1)    // compiles OK despite being a logic error!

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:

def f(n: {n: Integer | n mod 2 == 0}) := {
  // do something with n
}

Hier nist vom abhängigen Typ {n: Integer | n mod 2 == 0}. Es könnte hilfreich sein, dies laut vorzulesen

n ist ein Mitglied einer Menge von ganzen Zahlen, so dass jede ganze Zahl durch 2 teilbar ist.

In diesem Fall würde der Compiler zur Kompilierungszeit einen logischen Fehler erkennen, an den Sie eine ungerade Zahl übergeben haben, fund die Ausführung des Programms an erster Stelle verhindern:

f(1)    // compiler error

Hier ist ein anschauliches Beispiel unter Verwendung von Scala- Pfad-abhängigen Typen, wie wir versuchen könnten, Funktionen zu implementieren, fdie 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 nin der Art des Wertes erscheint, proofnämlich n.IsEven.type:

def f(n: Integer)(implicit proof: n.IsEven.type)
      ^                           ^
      |                           |
    value                       value

Wir sagen, Typ n.IsEven.type hängt vom Wert ab, n daher der Begriff abhängige Typen .

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):

IIMap::iterator i = foo.begin();
bar.erase(i);

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. ;-);

Zitieren des Buches Typen und Programmiersprachen (30.5):

Ein Großteil dieses Buches befasste sich mit der Formalisierung von Abstraktionsmechanismen verschiedener Art. In der einfach typisierten Lambda-Rechnung haben wir die Operation formalisiert, einen Begriff zu nehmen und ein Subterm zu abstrahieren, wodurch eine Funktion erhalten wurde, die später instanziiert werden kann, indem sie auf verschiedene Begriffe angewendet wird. In System Fhaben wir die Operation betrachtet, einen Begriff zu nehmen und einen Typ zu abstrahieren, um einen Begriff zu erhalten, der durch Anwenden auf verschiedene Typen instanziiert werden kann. ImλωWir haben die Mechanismen des einfach typisierten Lambda-Kalküls „eine Ebene höher“ zusammengefasst, indem wir einen Typ genommen und einen Unterausdruck abstrahiert haben, um einen Typoperator zu erhalten, der später durch Anwenden auf verschiedene Typen instanziiert werden kann. Eine bequeme Denkweise für all diese Formen der Abstraktion sind Ausdrucksfamilien, die durch andere Ausdrücke indiziert werden. Eine gewöhnliche Lambda-Abstraktion λx:T1.t2ist eine Familie von Begriffen, [x -> s]t1die durch Begriffe indiziert sind s. In ähnlicher Weise ist eine Typabstraktion λX::K1.t2eine Familie von Begriffen, die nach Typen indiziert sind, und ein Typoperator ist eine Familie von Typen, die nach Typen indiziert sind.

• λx:T1.t2 Familie von Begriffen, die durch Begriffe indiziert sind

• λX::K1.t2 Familie von Begriffen, die nach Typen indiziert sind

• λX::K1.T2 nach Typen indizierte Typenfamilie

Wenn wir uns diese Liste ansehen, ist klar, dass es eine Möglichkeit gibt, die wir noch nicht in Betracht gezogen haben: Familien von Typen, die durch Begriffe indiziert sind. Diese Form der Abstraktion wurde auch ausführlich unter der Rubrik abhängiger Typen untersucht.