Qu'est-ce que frappe dépend?

Question

Quelqu'un peut-il expliquer à taper dépend de moi? J'ai peu d'expérience dans Haskell, Cayenne, épigramme, ou d'autres langages fonctionnels, de sorte que le plus simple des termes que vous pouvez utiliser, plus je l'apprécierai!

Answer 1

Considérez ceci:. Dans toutes les langues de programmation décent, vous pouvez écrire des fonctions, par exemple

def f(arg) = result

Ici, f prend une valeur arg et calcule une valeur result. Il est une fonction des valeurs à des valeurs.

Maintenant, certaines langues vous permettent de définir des valeurs polymorphes (alias génériques):

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

Ici, empty prend un type T et calcule une valeur. Il est fonction de types de valeurs.

En général, vous pouvez aussi avoir des définitions de type générique:

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

Cette définition prend un type et il retourne un type. Il peut être considéré comme une fonction de types de types.

Voilà pour ce qui offrent des langues ordinaires. Une langue est appelée dépendamment si typée il offre également la possibilité 4, à savoir la définition des fonctions de valeurs types. En d'autres termes, une définition de paramétrage de type sur une valeur:

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

Certaines langues traditionnels ont une certaine forme de faux de ce qui est de ne pas confondre. Par exemple. en C ++, les modèles peuvent prendre des valeurs en tant que paramètres, mais ils doivent être des constantes de compilation lors de l'application. Mais pas dans un langage vraiment dépendamment typé. Par exemple, je pouvais utiliser le type ci-dessus comme ceci:

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

Ici, le type de résultat de la fonction dépend sur la valeur de l'argument réel j, donc la terminologie.

Answer 2

Si vous connaissez C ++ il est facile de donner un exemple motivant:

Le mot Let nous avons un certain type de conteneur et deux instances de celui-ci

typedef std::map<int,int> IIMap;
IIMap foo;
IIMap bar;

et considérez ce fragment de code (vous pouvez supposer foo est non vide):

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

est une ânerie évidente (et corrompt probablement les structures de données), mais il va taper-vérifier très bien depuis « iterator dans foo » et « iterator dans la barre » sont du même type, IIMap::iterator, même si elles sont totalement incompatibles sémantiquement.

La question est qu'un type iterator ne doit pas dépendre uniquement sur le conteneur type mais en fait sur le conteneur objet , à savoir qu'il devrait être un « non type de membre statique ":

foo.iterator i = foo.begin();
bar.erase(i);  // ERROR: bar.iterator argument expected

Une telle caractéristique, la capacité d'exprimer un type (foo.iterator) qui dépend d'un terme (foo), est exactement ce que les moyens de frappe à charge.

La raison pour laquelle vous ne voyez pas souvent cette fonction est parce qu'il ouvre un grand bidon de vers: vous vous retrouvez soudainement dans des situations où, pour vérifier au moment de la compilation si deux types sont les mêmes, vous finissez par avoir à prouvent deux expressions sont équivalentes (toujours obtenir la même valeur lors de l'exécution). Par conséquent, si vous comparez wikipedia des langues dépendamment tapées avec son liste des expérimentateurs théorème vous pouvez remarquer une similitude suspecte. ; -)

Answer 3

Types de charge permettent plus ensemble de erreurs logiques à éliminer à compilation . Pour illustrer ce qui suit considèrent que les spécifications sur la fonction f:

Fonction f doit prendre que même entiers en entrée.

Sans les types dépendants que vous pourriez faire quelque chose comme ceci:

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

Ici, le compilateur ne peut détecter si n est en effet même, qui est, du point de vue du compilateur l'expression suivante est ok:

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

Ce programme courir et puis lancer exception lors de l'exécution, qui est, votre programme a une erreur logique.

Maintenant, types dépendants vous permettent d'être beaucoup plus expressif et vous permettrait de écrire quelque chose comme ceci:

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

Ici n est de {n: Integer | n mod 2 == 0} de type dépendant. Il pourrait aider à lire à haute voix

n est un membre d'un ensemble de nombres entiers tels que chaque entier est divisible par 2.

Dans ce cas, le compilateur détecter au moment de la compilation d'une erreur logique où vous avez passé un nombre impair à f et empêcherait le programme à exécuter en premier lieu:

f(1)    // compiler error

---

Voici un exemple illustratif en utilisant Scala types en fonction de chemin de la façon dont nous pourrions tenter fonction la mise en œuvre f satisfaire une telle exigence :

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

La clé est d'avis comment la valeur apparaît de n dans le type de valeur proof à savoir n.IsEven.type:

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

Nous disons type n.IsEven.type dépend de la valeur n d'où le terme dépendants types .

Answer 4

Types Citant les livres et langages de programmation (30.5):

Une grande partie de ce livre a été concerné par l'abstraction formalisant mécanismes de diverses sortes. Dans le lambda-calcul simplement typé, nous officialisé l'opération de prendre un terme et abstraire un sous-terme, ce qui donne une fonction qui peut ensuite être instancié par l'appliquer à des termes différents. En SystemF, nous avons considéré la le fonctionnement de prendre un terme et abstraire un type qui donne un terme qui peut être instancié en l'appliquant à différents types. Inλω, nous récapitulé les mécanismes du lambda-calcul « un simplement typé niveau supérieur, » prendre un type et abstraire une sous-expression pour obtenir un opérateur de type qui peut ensuite être instancié en l'appliquant à différents types. Une façon pratique de penser à toutes ces formes de abstraction est en termes de familles d'expressions, indexées par d'autres expressions. Une λx:T1.t2 d'abstraction lambda ordinaire est une famille de termes [x -> s]t1 indexés par des termes s. De même, une abstraction de type λX::K1.t2 est une famille de termes indexés par types, et un opérateur de type est une famille de types indexés par types.

• famille λx:T1.t2 des termes indexés par des termes

• famille λX::K1.t2 des termes indexés par types

• famille λX::K1.T2 des types indexés par types

En regardant cette liste, il est clair qu'il ya une possibilité que nous n'avons pas encore envisagé: les familles de types indexés par des termes. Cette sous forme d'abstraction a également été étudiée en profondeur, sous la La rubrique des types dépendants.