Ressources de programmation de type Scala

102

Selon cette question , le système de type de Scala est Turing complet . Quelles ressources sont disponibles pour permettre à un nouveau venu 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 que je manque les bases et que je n'ai donc pas de base solide sur laquelle construire. 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?

scala types dsg
la source
Personnellement, je trouve que l'hypothèse que quelqu'un qui veut faire de la programmation au niveau du type dans Scala sait déjà comment faire de la programmation dans Scala tout à fait raisonnable. Même si cela signifie que je ne comprends pas un mot de ces articles que vous avez liés :-)
Jörg W Mittag

Réponses:

140

Aperçu

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. Je vais essayer de faire des parallèles entre la programmation au niveau de la valeur et la programmation au niveau du type.

Paradigmes

Il existe deux principaux paradigmes 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 l' implémentation par apocalisp du calcul lambda , reproduite 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éfinissez un trait abstrait avec divers champs de type abstrait (voir ci-dessous ce qu'est un champ abstrait). Il s'agit d'un modèle pour garantir que certains types de champs existent dans toutes les implémentations sans forcer une implémentation. Dans l'exemple de calcul lambda, ce qui correspond à trait Lambdace que les garanties qui existent les types suivants: subst, applyet eval.
  • Suivant: 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 de calcul lambda, les sous-types sont trait App extends Lambdaparamétrés avec deux types ( Set T, les deux doivent être des sous-types de Lambda), trait Lam extends Lambdaparamétrés 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 parfois en référençant leurs champs de type via l'opérateur de hachage: #(qui est très similaire à l'opérateur point: .pour les valeurs). En trait Appde l'exemple de calcul lambda, le type evalest mis en œuvre comme suit: type eval = S#eval#apply[T]. Il s'agit essentiellement d'appeler le evaltype du paramètre du trait Set d'appeler le applyparamètre avec Tle résultat. Remarque, il Sest garanti d'avoir un evaltype car le paramètre spécifie qu'il s'agit d'un sous-type de Lambda. De même, le résultat de evaldoit avoir un applytype, 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 types paramétrés 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 de type: trait C { type X }
  • types dépendant du chemin
    • C.x (référençant la valeur du champ / la fonction x dans l'objet C)
    • C#x (référençant le type de champ x dans le trait C)
  • signature de fonction (pas d'implémentation)
    • niveau de valeur: def f(x:X) : Y
    • niveau de type: 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 de type: type f[x <: X] = x
  • conditionnels
  • vérifier l'égalité
    • niveau de valeur: a:A == b:B
    • niveau de type: implicitly[A =:= B]
    • value-level: se produit dans la JVM via un test unitaire à l'exécution (c'est-à-dire pas d'erreurs d'exécution):
      • in essense est une affirmation: assert(a == b)
    • type-level: se produit dans le compilateur via une vérification de type (c'est-à-dire pas d'erreurs de compilateur):
      • est essentiellement une comparaison de type: par exemple implicitly[A =:= B]
      • A <:< B, compile uniquement si Aest un sous-type deB
      • A =:= B, compile uniquement si Aest un sous-type de Bet Best un sous-type deA
      • A <%< B, ("visible en tant que") compile uniquement si Aest visible en tant que B(c'est-à-dire qu'il y a une conversion implicite de Aen un sous-type de B)
      • un 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 pas être instanciés directement ou via une sous-classe anonyme. Il est donc courant d'utiliser nullcomme valeur d'espace réservé lors d'un calcul au niveau de la valeur en utilisant un type d'intérêt:

    • Par exemple val x:A = null, où Aest le type qui vous tient à cœur

  • En raison de l'effacement de type, les types paramétrés se ressemblent tous. De plus, (comme mentionné ci-dessus) les valeurs avec nulllesquelles vous travaillez ont tendance à être toutes , et donc conditionner le type d'objet (par exemple via une déclaration 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 implicits.

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 encodage 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ù Aest 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 différents nombres naturels pour une référence plus pratique. Exemple:

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

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

Maintenant, supposons que nous voulions définir une fonction au niveau de la valeur def toInt[T <: Nat](v : T)qui prend une valeur d'argument,, vqui se conforme Natet renvoie un entier représentant le nombre naturel encodé dans vle type de. Par exemple, si nous avons la valeur val x:_3 = null( nullde type Succ[Succ[Succ[_0]]]), nous voudrions toInt(x)retourner 3.

Pour l'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 TypeToValuepour chacun Natde _0jusqu'à (par exemple) _3, et chacun stockera la représentation de la valeur du type correspondant (c'est TypeToValue[_0, Int]-à- dire stockera la valeur 0, TypeToValue[Succ[_0], Int]stockera la valeur 1, etc.). Remarque, TypeToValueest paramétré par deux types: Tet VT. Tcorrespond au type auquel nous essayons d'attribuer des valeurs (dans notre exemple, Nat) et VTcorrespond 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 toIntcomme suit:

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

Pour comprendre comment toIntfonctionne, 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 ttvde type TypeToValue[_0, Int](puisque zest de type _0). Il trouve l'objet _0ToInt, il appelle la getValueméthode de cet objet et le 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.

Voyons maintenant toInt(y). Cette fois, le compilateur recherche un argument implicite ttvde type TypeToValue[Succ[_0], Int](puisque yest 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, a TypeToValueoù le premier paramètre de type en a un de moins Succ[_]). Le compilateur fournit _0ToInt(comme cela a été fait dans l'évaluation toInt(z)ci - dessus) et succToIntconstruit un nouvel TypeToValueobjet avec une 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érifier 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 en sorte que deux types Aet Bque vous souhaitez vérifier soient égaux. Vérifiez ensuite que la compilation suivante:

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

Ressources supplémentaires

L'ensemble des constructions disponibles se trouve dans la section des types du manuel de référence 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 dans scala.

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

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, HList, etc. C'est un projet de Jesper Nordenberg (son blog) .

Le Michid (blog) a quelques exemples impressionnants de la programmation au niveau du type à Scala (d'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.)

dsg
la source
12

En plus des autres liens ici, il y a aussi mes articles de blog sur la méta-programmation au niveau du type dans Scala:

Michid
la source
Je voulais juste dire merci pour le blog intéressant; Je le suis depuis un moment et surtout le dernier article mentionné ci-dessus a affiné ma compréhension des propriétés importantes qu'un système de type pour un langage orienté objet devrait avoir. Donc merci!
Zach Snow
4

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

Vasil Remeniuk
la source