it-swarm-eu.dev

Scala ressources de programmation de type

Selon cette question , le système de type de Scala est Turing complet . Quelles ressources sont disponibles pour permettre à un nouvel arrivant de profiter de la puissance de la programmation au niveau du type?

Voici les ressources que j'ai trouvées jusqu'à présent:

Ces ressources sont excellentes, mais j'ai l'impression de manquer les bases, et donc je n'ai pas de base solide sur laquelle bâtir. Par exemple, où existe-t-il une introduction aux définitions de type? Quelles opérations puis-je effectuer sur les types?

Existe-t-il de bonnes ressources d'introduction?

102
dsg

Présentation

La programmation au niveau du type présente de nombreuses similitudes avec la programmation traditionnelle au niveau de la valeur. Cependant, contrairement à la programmation au niveau de la valeur, où le calcul se produit au moment de l'exécution, dans la programmation au niveau du type, le calcul se produit au moment de la compilation. J'essaierai de faire des parallèles entre la programmation au niveau de la valeur et la programmation au niveau du type.

Paradigmes

Il existe deux paradigmes principaux dans la programmation au niveau du type: "orienté objet" et "fonctionnel". La plupart des exemples liés à partir d'ici suivent le paradigme orienté objet.

Un bon exemple assez simple de programmation au niveau du type dans le paradigme orienté objet peut être trouvé dans apocalisp implémentation du calcul lambda , reproduit ici:

// Abstract trait
trait Lambda {
  type subst[U <: Lambda] <: Lambda
  type apply[U <: Lambda] <: Lambda
  type eval <: Lambda
}

// Implementations
trait App[S <: Lambda, T <: Lambda] extends Lambda {
  type subst[U <: Lambda] = App[S#subst[U], T#subst[U]]
  type apply[U] = Nothing
  type eval = S#eval#apply[T]
}

trait Lam[T <: Lambda] extends Lambda {
  type subst[U <: Lambda] = Lam[T]
  type apply[U <: Lambda] = T#subst[U]#eval
  type eval = Lam[T]
}

trait X extends Lambda {
  type subst[U <: Lambda] = U
  type apply[U] = Lambda
  type eval = X
}

Comme on peut le voir dans l'exemple, le paradigme orienté objet pour la programmation au niveau du type se déroule comme suit:

  • Premièrement: définir un trait abstrait avec différents champs de type abstrait (voir ci-dessous pour ce qu'est un champ abstrait). Il s'agit d'un modèle pour garantir que certains champs de types existent dans toutes les implémentations sans forcer une implémentation. Dans l'exemple du calcul lambda, cela correspond à trait Lambda Qui garantit que les types suivants existent: subst, apply et eval.
  • Ensuite: définir des sous-portraits qui étendent le trait abstrait et implémenter les différents champs de type abstrait
    • Souvent, ces sous-portraits seront paramétrés avec des arguments. Dans l'exemple du calcul lambda, les sous-types sont trait App extends Lambda Qui est paramétré avec deux types (S et T, les deux doivent être des sous-types de Lambda), trait Lam extends Lambda Paramétré avec un type (T) et trait X extends Lambda (Qui n'est pas paramétré).
    • les champs de type sont souvent implémentés en se référant aux paramètres de type du sous-portrait et en référençant parfois leurs champs de type via l'opérateur de hachage: # (qui est très similaire à l'opérateur point: . pour les valeurs ). Dans le trait App de l'exemple de calcul lambda, le type eval est implémenté comme suit: type eval = S#eval#apply[T]. Il s'agit essentiellement d'appeler le type eval du paramètre du trait S et d'appeler apply avec le paramètre T sur le résultat. Remarque: S est garanti d'avoir un type eval car le paramètre spécifie qu'il s'agit d'un sous-type de Lambda. De même, le résultat de eval doit avoir un type apply, car il est spécifié comme étant un sous-type de Lambda, comme spécifié dans le trait abstrait Lambda .

Le paradigme fonctionnel consiste à définir de nombreux constructeurs de type paramétré qui ne sont pas regroupés en traits.

Comparaison entre la programmation au niveau de la valeur et la programmation au niveau du type

  • classe abstraite
    • niveau de valeur: abstract class C { val x }
    • niveau-type: trait C { type X }
  • types dépendant du chemin
    • C.x (Référence à la valeur/fonction du champ x dans l'objet C)
    • C#x (Faisant référence au type de champ x dans le trait C)
  • signature de fonction (pas d'implémentation)
    • niveau de valeur: def f(x:X) : Y
    • type-level: type f[x <: X] <: Y (cela s'appelle un "constructeur de type" et se produit généralement dans le trait abstrait)
  • mise en œuvre de la fonction
    • niveau de valeur: def f(x:X) : Y = x
    • niveau-type: type f[x <: X] = x
  • conditionnelles
  • vérification de l'égalité
    • niveau de valeur: a:A == b:B
    • niveau-type: implicitly[A =:= B]
    • niveau de valeur: se produit dans la JVM via un test unitaire lors de l'exécution (c'est-à-dire sans erreur d'exécution):
      • in essense est une assertion: assert(a == b)
    • type-level: se produit dans le compilateur via une vérification de type (c'est-à-dire aucune erreur de compilation):
      • est essentiellement une comparaison de types: par ex. implicitly[A =:= B]
      • A <:< B, Compile uniquement si A est un sous-type de B
      • A =:= B, Compile uniquement si A est un sous-type de B et B est un sous-type de A
      • A <%< B, ("Visible en tant que") ne se compile que si A est visible en tant que B (c'est-à-dire qu'il y a une conversion implicite de A en un sous-type de B)
      • n exemple
      • plus d'opérateurs de comparaison

Conversion entre types et valeurs

  • Dans de nombreux exemples, les types définis via des traits sont souvent à la fois abstraits et scellés, et ne peuvent donc ni être instanciés directement ni via une sous-classe anonyme. Il est donc courant d'utiliser null comme valeur d'espace réservé lors d'un calcul au niveau de la valeur en utilisant un certain type d'intérêt:

    • par exemple. val x:A = null, Où A est le type qui vous tient à cœur
  • En raison de l'effacement des types, les types paramétrés se ressemblent tous. De plus, (comme mentionné ci-dessus), les valeurs avec lesquelles vous travaillez ont tendance à être toutes null, et donc le conditionnement sur le type d'objet (par exemple via une instruction de correspondance) est inefficace.

L'astuce consiste à utiliser des fonctions et des valeurs implicites. Le cas de base est généralement une valeur implicite et le cas récursif est généralement une fonction implicite. En effet, la programmation au niveau du type fait un usage intensif des implicites.

Considérez cet exemple ( tiré de metascala et apocalisp ):

sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat

Ici, vous avez un codage peano des nombres naturels. Autrement dit, vous avez un type pour chaque entier non négatif: un type spécial pour 0, à savoir _0; et chaque entier supérieur à zéro a un type de la forme Succ[A], où A est le type représentant un entier plus petit. Par exemple, le type représentant 2 serait: Succ[Succ[_0]] (Successeur appliqué deux fois au type représentant zéro).

Nous pouvons alias divers nombres naturels pour une référence plus pratique. Exemple:

type _3 = Succ[Succ[Succ[_0]]]

(C'est un peu comme définir un val comme résultat d'une fonction.)

Supposons maintenant que nous voulions définir une fonction de niveau de valeur def toInt[T <: Nat](v : T) qui prend une valeur d'argument, v, conforme à Nat et retourne un entier représentant le nombre naturel encodé dans le type de v. Par exemple, si nous avons la valeur val x:_3 = null (null de type Succ[Succ[Succ[_0]]]), Nous voudrions que toInt(x) renvoie 3.

Pour implémenter toInt, nous allons utiliser la classe suivante:

class TypeToValue[T, VT](value : VT) { def getValue() = value }

Comme nous le verrons ci-dessous, il y aura un objet construit à partir de la classe TypeToValue pour chaque Nat de _0 À (par exemple) _3, Et chacun stocker la représentation de valeur du type correspondant (c'est-à-dire que TypeToValue[_0, Int] stockera la valeur 0, TypeToValue[Succ[_0], Int] stockera la valeur 1, etc.). Remarque, TypeToValue est paramétré par deux types: T et VT. T correspond au type auquel nous essayons d'assigner des valeurs (dans notre exemple, Nat) et VT correspond au type de valeur que nous lui attribuons ( dans notre exemple, Int).

Maintenant, nous faisons les deux définitions implicites suivantes:

implicit val _0ToInt = new TypeToValue[_0, Int](0)
implicit def succToInt[P <: Nat](implicit v : TypeToValue[P, Int]) = 
     new TypeToValue[Succ[P], Int](1 + v.getValue())

Et nous implémentons toInt comme suit:

def toInt[T <: Nat](v : T)(implicit ttv : TypeToValue[T, Int]) : Int = ttv.getValue()

Pour comprendre comment toInt fonctionne, considérons ce qu'il fait sur quelques entrées:

val z:_0 = null
val y:Succ[_0] = null

Lorsque nous appelons toInt(z), le compilateur recherche un argument implicite ttv de type TypeToValue[_0, Int] (Puisque z est de type _0) . Il trouve l'objet _0ToInt, Il appelle la méthode getValue de cet objet et récupère 0. Le point important à noter est que nous n'avons pas spécifié au programme quel objet utiliser, le compilateur l'a trouvé implicitement.

Considérons maintenant toInt(y). Cette fois, le compilateur recherche un argument implicite ttv de type TypeToValue[Succ[_0], Int] (Puisque y est de type Succ[_0]). Il trouve la fonction succToInt, qui peut renvoyer un objet du type approprié (TypeToValue[Succ[_0], Int]) Et l'évalue. Cette fonction elle-même prend un argument implicite (v) de type TypeToValue[_0, Int] (C'est-à-dire un TypeToValue où le premier paramètre de type a un de moins Succ[_]) . Le compilateur fournit _0ToInt (Comme cela a été fait dans l'évaluation de toInt(z) ci-dessus), et succToInt construit un nouvel objet TypeToValue avec la valeur 1. Encore une fois, il est important de noter que le compilateur fournit toutes ces valeurs implicitement, car nous n'y avons pas accès explicitement.

Vérification de votre travail

Il existe plusieurs façons de vérifier que vos calculs au niveau du type font ce que vous attendez. Voici quelques approches. Faites deux types A et B, que vous voulez vérifier sont égaux. Vérifiez ensuite que la compilation suivante:

  • Equal[A, B]
  • implicitly[A =:= B]

Vous pouvez également convertir le type en valeur (comme indiqué ci-dessus) et effectuer une vérification d'exécution des valeurs. Par exemple. assert(toInt(a) == toInt(b)), où a est de type A et b est de type B.

Ressources supplémentaires

L'ensemble complet des constructions disponibles peut être trouvé dans la section types de le scala (pdf) .

Adriaan Moors a plusieurs articles académiques sur les constructeurs de types et des sujets connexes avec des exemples de scala:

Apocalisp est un blog avec de nombreux exemples de programmation au niveau du type en scala.

ScalaZ est un projet très actif qui fournit des fonctionnalités qui étendent l'API Scala en utilisant diverses fonctionnalités de programmation au niveau du type. C'est un projet très intéressant qui a un grand nombre de suivis .

MetaScala est une bibliothèque de niveau type pour Scala, comprenant des méta types pour les nombres naturels, les booléens, les unités, la HList, etc. C'est un projet de Jesper Nordenberg (son blog) .

Michid (blog) a quelques exemples impressionnants de programmation au niveau du type dans Scala (à partir d'une autre réponse):

Debasish Ghosh (blog) a également des articles pertinents:

(J'ai fait des recherches sur ce sujet et voici ce que j'ai appris. Je suis encore nouveau dans ce domaine, veuillez donc signaler toute inexactitude dans cette réponse.)

140
dsg
12
michid
6
GClaramunt
5
Kenji Yoshida

Scalaz a du code source, un wiki et des exemples.

4
Vasil Remeniuk