Archives pour la catégorie Scala

La récursion terminale

La récursion terminale fait partie de la panoplie des outils d’un langage fonctionnel, même si elle peut être implémentée dans n’importe quel langage.

La récursion terminale est la capacité du compilateur à transformer une fonction récursive en une itération, c’est à dire une boucle. Pour que cela soit possible, il faut que l’appel récursif soit la dernière instruction de la méthode à être évaluée.

L’exemple ultra-classique du calcul de la factorielle

Voyons cela sur l’exemple récursif par excellence : le calcul de la factorielle, écrit en Scala :

def factorielle(n: Int): Int = {
  if (n < 2) 1
  else n * factorielle(n - 1)
}
factorielle(5)

La fonction ci-dessus est bien récursive, et visuellement, l’appel récursif est bien à la fin de la fonction. Mais cet appel récursif n’est pas la dernière instruction de la fonction, puisqu’il faut encore effectuer la multiplication une fois qu’on a obtenu la valeur de factorielle(n - 1).

C’est assez facile de transformer cette fonction pour que la récursion soit terminale :

def factorielle(n: Int, resultat: Int): Int = {
  if (n < 2) resultat
  else factorielle(n - 1, resultat * n)
}
factorielle(5, 1)

Le compilateur Scala va transformer cette fonction récursive en une boucle, équivalente au code suivant :

def factorielle(n: Int, resultat: Int) = {
  var valeur = n
  var res = resultat
  while (valeur >= 2) {
    res = res * valeur
    valeur = valeur - 1
  }
  res
}

Détails Scala

Vous allez me dire que ce 2e argument, la valeur de départ qu’il faut mettre à 1, vous gêne. Moi aussi. De plus, il y a d’autres petites choses à faire, et nous allons régler tout ça.

En Scala, on peut annoter une méthode avec @tailrec, ce qui fait que la compilation échoue si la méthode n’est pas récursive terminale. Vous avez ainsi la certitude qu’elle sera optimisée. De plus, une simple méthode d’une classe, pour avoir cette annotation, ne doit pas pouvoir être remplacée en dérivant la classe. C’est pourquoi le compilateur demande à ce que la méthode soit private ou final. En Scala, il est aussi possible de définir une méthode à l’intérieur d’une autre, ce qui règle ce problème. Il faut de plus définir le type du résultat de la méthode. Le moteur d’inférence de type de Scala ne s’en sort pas sinon. Tout ça mis ensemble pour le calcul de la factorielle donne :

def factorielle(n: Int): Int = {
  import scala.annotation.tailrec

  @tailrec
  def fact(n: Int, resultat: Int): Int =
    if (n < 2) resultat
    else fact(n - 1, resultat * n)

  fact(n, 1)
}
factorielle(5)

J’ai aussi mis le import à l’intérieur de la méthode, mais vous pouvez le déplacer en début du fichier.

Intérêts

Il y a plusieurs intérêts à utiliser la récursion terminale lorsque c’est possible. D’abord, cela permet d’écrire du code sans utiliser de variables mutables.

Ensuite, cela permet de comprendre très simplement ce qui est fait, parce que le corps de la méthode ne traite toujours qu’une seule itération. Il n’y a aucun code pour gérer l’ensemble des itérations.

Avec la récursion terminale, on profite des avantages de la récursivité, sans les inconvénients.

Exemple : donner n nombres dont le total donne m

Un dernier exemple : vous devez fournir une liste de n nombres au hasard dont le total donne m. Aucun nombre ne doit être égal à 0, mais plusieurs de ces nombres peuvent être égaux. Voici comment vous pourriez l’écrire :

def listeNombres(combien: Int, total: Int): List[Int] = {
  val random = new scala.util.Random()
  @scala.annotation.tailrec
  def hasard(n: Int, listeTrouve: List[Int]): List[Int] =
    if (n == 0) listeTrouve
    else {
      val i = random.nextInt(total - 2) + 1
      if (listeTrouve.contains(i)) hasard(n, listeTrouve)
      else hasard(n - 1, i +: listeTrouve)
    }

  val intervalles = hasard(combien - 1, List(total)).sorted

  @scala.annotation.tailrec
  def calcDiff(
    precedent: Int, aTraiter: List[Int], resultat: List[Int]): List[Int] =
    if (aTraiter.size == 0) resultat
    else calcDiff(
      aTraiter.head, aTraiter.tail, resultat :+ (aTraiter.head - precedent))

  nombres(0, intervalles, List())
}

listeNombres(4, 100).foreach(println)

On cherche d’abord n-1 nombres différents, compris entre 1 et m-1 inclus, avec la méthode récursive hasard. On trie cette liste et on y ajoute 0 et m, ce qui définit n intervalles dont le total est m. On crée ensuite la liste des nombres demandés avec une 2e méthode récursive calcDiff, qui calcule les différences.

Covariance, contravariance et invariance

Dans les langages orientés objets, utilisant les types génériques, il peut être utile de comprendre les aspects concernant la variance. Nous allons voir du code Java pour commencer, puis j’expliquerai comment Scala résout le problème que nous allons rencontrer en Java.

Covariance en Java

Voici d’abord la hiérarchie de classes utilisées dans les exemples de cet article :

   - D
 /
A - B - C

A est à la racine. B et D dérivent de A. C dérive de B.

Les génériques sont utilisées par toutes les classes conteneurs : listes, tableaux, ensemble ou map.

B[] tableauB = new B[3];
tableauB[0] = new B();
tableauB[1] = new C();
A[] tableauA = tableauB;

Le code ci-dessus fonctionne sans problème, comme on s’y attends. On peut évidemment ajouter un B à un tableau de B. C étant un sous-type de B, on peut l’ajouter aussi à un tableau de B.

La 4e ligne fonctionne à cause de la covariance. Cela signifie que puisque B est un sous-type de A, alors tableau de B est un sous-type de tableau de A.

Continuons. Puisque D est un sous-type de A, il est possible d’ajouter un D à un tableau de A, tout comme nous avons ajouté un C à un tableau de B :

tableauA[2] = new D();

Tout ça semble bien naturel, et le compilateur Java accepte ce code sans aucun souci. Mais il y a un gros problème. En effet, nous avons créé un tableau de B au départ, auquel nous avons fini par ajouter un objet de type D. Ça ne devrait pas être possible. Java résout ce problème en ajoutant du code pour vérifier la compatibilité des types à chaque fois qu’un objet est ajouté à un tableau. Cette dernière ligne de code génère l’exception ArrayStoreException, au moment de son exécution.

Solutions possibles

Le problème vient du fait que les tableaux sont à la fois mutables et covariant. Régler un seul de ces 2 aspects suffit pour détecter les problèmes au moment de la compilation.

Si le tableau était non mutable, on ne pourrait pas y ajouter de nouveaux éléments et le problème serait résolu.

B[] tableauB = new B[] { new B(), new C() };

Si le tableau est invariant au lieu de covariant, il n’y aurait pas de problème non plus, puisqu’on ne pourrait pas affecter un tableau de B à un tableau de A. Remarquer que le fait que le tableau soit invariant n’empêche pas d’y ajouter des objets ayant un sous-type de B.

La variance en Scala

En Scala, il y a 2 versions de chaque conteneur, l’une est mutable, l’autre ne l’est pas. Il est très rare qu’on utilise les conteneurs mutables, la programmation fonctionnelle incite à n’utiliser que des objets non mutables.

Les conteneurs mutables sont invariants. Lancez la REPL scala, pour tester le code qui suit. Nous allons utiliser les tableaux dans les exemples, mais le principe reste le même pour les autres conteneurs.

class A()
class B() extends A()
class C() extends B()
class D() extends A()
val tableauB = Array(new B(), new C())

Si nous tentons maintenant de changer le type de ce tableau, nous allons obtenir une erreur de compilation :

val tableauA: Array[A] = tableauB
<console>:11: error: type mismatch;
 found   : Array[B]
 required: Array[A]
Note: B <: A, but class Array is invariant in type T.
You may wish to investigate a wildcard type such as `_ <: A`. (SLS 3.2.10)
       val tableauA: Array[A] = tableauB
                                ^

Il est quand même possible d’ajouter un élément à un conteneur immutable. La raison simple est qu’une nouvelle collection est créée, incluant ce nouvel élément.

val tableau2 = tableauB :+ new B()
tableau2: Array[B] = Array(B@e3a7be4, C@51b12677, B@219bbd08)

Contravariance

Mais là où cela devient intéressant, c’est que l’argument de la méthode d’ajout d’un élément (:+) est contravariant. Cela signifie qu’il est possible d’ajouter un objet d’un type qui est un sur-type de B (A dans notre exemple) :

val tableau3 = tableauB :+ new A()
tableau3: Array[A] = Array(B@e3a7be4, C@51b12677, A@55bce7e2)

Comment est-ce possible ? Tout simplement parce que la nouvelle collection créée a changé de type. Ce n’est plus un Array[B] mais un Array[A]. Et comme A est un sur-type de B, cette nouvelle collection peut bien sûr contenir des objets de type B (ou de ses sous-types).

En fait, on peut même ajouter n’importe quel type à une collection, le résultat étant une collection du sur-type commun à tous les objets de la nouvelle collection. Un tel type existe toujours, puisque en Scala, la racine de la hiérarchie est Any (même pour les types primitifs).

class E()
val tableau4 = tableauB :+ new E()
tableau4: Array[Object] = Array(B@e3a7be4, C@51b12677, E@7430bc45)

val tableau5 = tableauB :+ 1
tableau5: Array[Any] = Array(B@e3a7be4, C@51b12677, 1)

Ce n’est pas du tout recommandé, parce qu’on ne peut pas faire grand chose avec une collection de Object ou de Any.

Conclusion

Utiliser des objets immutables a bien des avantages, n’est-ce-pas ? Il existe des règles claires pour les endroits où il faut utiliser la covariance, la contravariance ou l’invariance. Mais je ne vais pas entrer dans ces détails, et vous n’avez pas besoin de les connaître. Sachez qu’en Scala, les collections respectent ces règles et ne vous poserons pas de problème.

Les nombres rationnels : premier code Scala

3 niveaux de maîtrise de Scala

Martin Odersky, le créateur de Scala, a définit 3 niveaux de maîtrise du langage. Le 1er niveau peut être vu simplement comme un « meilleur Java », et les idées sont très facile à maîtriser pour un développeur Java. Ci-dessous est créée une classe qui montre quelques concepts simples pour introduire le langage.

REPL

Scala dispose d’une REPL. Cela signifie Read-Eval-Print-Loop, soit en français Lire-Évaluer-Écrire-Recommencer. C’est un outil en ligne de commande qui permet d’exécuter directement du code Scala, sans avoir à passer par la phase de compilation. Cet outil se lance avec la commande scala sans argument. Le code qui suit peut être directement copié dans la REPL.

Les nombres rationnels

Les nombres rationnels sont ceux qui s’écrivent comme un quotient de 2 entiers relatifs, noté a/b. a est nommé le numérateur et b le dénominateur. Par exemple : 1/2, -3/5, 1234/3, ou encore 10/1.

class Rationnel(val numerateur: Int, val denominateur: Int)

Cette unique ligne suffit pour définir la classe, avec les 2 champs, qui sont publics et non modifiables. On peut maintenant écrire

val r = new Rationnel(1, 2)
println("Numérateur = " + r.numerateur)

val définit une valeur immutable, aussi bien dans le constructeur de la classe que lors de la création du rationnel r. Le constructeur par défaut est celui avec les arguments juste après le nom de la classe. Il n’y a pas de point-virgule (;), qui seraient nécessaire en Java, mais sont optionnels en Scala.

Le type de r est déterminé automatiquement par le compilateur, en fonction du type de la partie droite. Cette détection du type par le compilateur est très puissante, et permet de réduire énormément le code à saisir. On aurait pu écrire

val r : Rationnel = new Rationnel(1234, 3)

Le mot clé val définit une valeur immutable. Écrire ensuite r = new Rationnel(10, 1) génère une erreur de compilation. Le mot clé var permet de définir une variable que l’on peut réassigner.

Version améliorée de la classe

Voici une 2e version de la classe.

case class Rationnel(numerateur: Int, denominateur: Int) {
  def this(n: Int) = this(n, 1)
  val reel = numerateur.toFloat / denominateur
  println("valeur réelle = " + reel)
  override def toString = numerateur.toString + " / " + denominateur
}
val negatif = Rationnel(-3, 5)
val dix = new Rationnel(10)
println(dix.toString)

Un constructeur auxiliaire a été définit. Les constructeurs auxiliaires doivent toujours référencer un autre constructeur, et en bout de chaîne il doit y avoir le constructeur par défaut. Le corps du constructeur est le contenu de la classe lui-même. Ici est définit puis affichée la valeur reel, dans le constructeur.

Le mot def définit une fonction ou une méthode.

toString surcharge la méthode sans argument bien connue des classes Java. Les parenthèses pour l’appel de la méthode sont optionnelles. Du coup, lors de son utilisation, il n’est plus possible de faire la différence entre l’accès à un membre, et l’appel d’une méthode sans paramètre. Cette idée se base sur le fait que dans la programmation fonctionnelle, on cherche à n’utiliser que des objets immutables. Donc les méthodes renvoient toujours la même valeur avec les mêmes paramètres d’entrée. Savoir si on utilise une méthode ou directement un membre n’a donc plus d’importance.

Le plus remarquable ici, est l’ajout du mot clé case. Cela définit ce qu’on appelle de manière très originale une case class. Elle a de nombreuses propriétés intéressantes :
– les méthodes equals, hashCode et toString sont définies par défaut, en utilisant les valeurs du constructeurs par défaut.
– lors de la création d’un objet avec le constructeur par défaut, le mot clé new n’est plus nécessaire, grâce à l’utilisation de la fonction apply dans l’objet compagnon (voir ci-dessous).
– les arguments du constructeur sont des val par défaut. Ce mot clé est optionnel.

Objet compagnon

L’objet compagnon d’une classe sert à définir toutes les méthodes static en Java.

Voici comment ajouter une méthode dans l’objet compagnon, pour simplifier aussi la création des entiers, ainsi que la création d’une constante.

case class Rationnel(val numerateur: Int, val denominateur: Int) {
  def this(n: Int) = this(n, 1)
}
object Rationnel {
  def apply(n: Int) = new Rationnel(n, 1)
  val un = Rationnel(1)
}
println(Rationnel.un.toString)

Les méthodes apply qui sont définies dans l’objet compagnon sont particulières, parce qu’elles peuvent être appelées en utilisant simplement le nom de la classe. Ainsi ces 2 lignes sont équivalentes :

val moinsUn = Rationnel(-1)
val moinsUn = Rationnel.apply(-1)

Conclusion

Voilà la présentation de quelques concepts simples, qui font de Scala un langage compact et très lisible, sans même utiliser l’aspect fonctionnel du langage. La classe Rationnel ci-dessus est bien sûr entièrement compatible avec Java.

Scala, c’est quoi ?

Présentation

Définir Scala se fait par rapport à Java.

Scala est un langage qui se compile pour la JVM. Il a un typage statique et intègre 2 paradigmes : la programmation orientée objet, et la programmation fonctionnelle. Le langage a été conçu à l’École polytechnique fédérale de Lausanne (EPFL) par Martin Odersky, qui a conçu les génériques pour Java, et a écrit la base du compilateur Java actuel.

Le langage date de 2001. La première version publique date de 2003. Aujourd’hui, il est utilisé par des entreprises mondiales, par exemple Twitter ou The Guardian. Martin Odersky travaille pour la société Typesafe, dont le but est de développer, promouvoir et offrir des services autour de Scala. Le langage a quitté le monde académique pour entrer dans le monde industriel il y a quelques années déjà.

Compatibilité Scala / Java

Les classes Java sont utilisables en Scala, et réciproquement. Cela signifie qu’en Scala, il est possible d’utiliser les nombreuses librairies Java existantes, y compris la librairie standard Java.

Il est aussi possible d’utiliser en Java une librairie écrite en Scala. Un excellent exemple est Akka, qui implémente le modèle d’acteur, pour la programmation concurrente.

Une fois le code Scala compilé, on obtient des fichiers jar, qui se comportent comme n’importe quelle librairie Java. Il n’y a plus aucune différence, du point de vue de la JVM. Il y a évidemment la librairie standard Scala, qui s’ajoute nécessairement à votre projet.

Programmation fonctionnelle

Le grand intérêt de Scala est l’introduction de la programmation fonctionnelle. Avec les autres améliorations syntaxiques par rapport à Java, cela permet d’écrire beaucoup moins de code, pour exprimer les mêmes besoins, tout en restant très lisible. Certes, il faut apprendre les bases de la programmation fonctionnelle, mais cela vient vite — ce n’est pas plus compliqué que d’apprendre à utiliser une nouvelle librairie Java.

Les outils

Il y a quelques années encore, un gros reproche que l’on faisait à Scala est le manque d’outils de développement par rapport à Java. Il est clair que ces outils sont très nombreux pour Java, et que l’attente des développeurs est hautes sur ce sujet. Cela a été la priorité de la société Typesafe, qui a amélioré le plugin Scala de Eclipse. Il a aujourd’hui un très bon niveau. Il existe aussi un excellent plugin pour IntelliJ IDEA. Personnellement, j’utilise ensime pour Emacs.

Introduction dans un projet existant

Une idée pour introduire doucement Scala dans un projet existant, est de le cantonner à l’écriture des tests JUnit. On peut ainsi apprivoiser le langage, sans impact sur le code en production. Mais attention, une fois qu’on y a goûté, c’est très difficile de revenir en arrière.