Tutoriel pour apprendre le langage Scala par l'exemple

Scala est fourni avec un interpréteur qui peut être considéré comme une calculatrice améliorée. L'utilisateur interagit avec cette calculatrice en tapant des expressions et la calculatrice renvoie les résultats des évaluations et leurs types. Voici un exemple :

scala> 87 + 145
res0: Int = 232

scala> 5 + 2 * 3
res1: Int = 11

scala> "hello" + " world !"
res2: java.lang.String = hello world !

On peut également nommer une sous-expression et réutiliser ensuite ce nom à la place de l'expression :

scala> def scale = 5
scale: Int

scala> 7 * scale
res3: Int = 35

scala> def pi = 3.141592653589793
pi: Double

scala> def radius = 10
radius: Int

scala> 2 * pi * radius
res4: Double = 62.83185307179586

Les définitions sont introduites par le mot réservé def ; elles créent un nom qui désigne l'expression qui suit le signe =. L'interpréteur répond en indiquant ce nom suivi de son type.

L'exécution d'une définition comme def x = e n'évalue pas l'expression e. Celle-ci sera évaluée à chaque fois que x sera utilisée. Scala permet également de définir une valeur avec val x = e : cette définition évalue la partie droite e lors de son exécution. Toute utilisation de x sera ensuite remplacée par la valeur précalculée de e afin que l'expression n'ait pas besoin d'être réévaluée.

Comment sont évaluées les expressions ? Une expression formée d'opérateurs et d'opérandes est évaluée en appliquant de façon répétée les étapes de simplification suivantes :

• prendre l'opération la plus à gauche ;
• évaluer ses opérandes ;
• appliquer l'opérateur aux valeurs obtenues pour ces opérandes.

Un nom défini par def est évalué en remplaçant le nom par sa partie droite (non évaluée). Un nom défini par val est évalué en remplaçant le nom par la valeur de sa partie droite. Le processus d'évaluation s'arrête lorsque l'on a obtenu une valeur, c'est-à-dire une donnée comme une chaîne, un nombre, un tableau ou une liste.

Voici les étapes de l'évaluation d'une expression arithmétique.

(2 * pi) * radius
(2 * 3.141592653589793) * radius
6.283185307179586 * radius
6.283185307179586 * 10
62.83185307179586

Ce processus de simplification par étapes des expressions en valeur est appelé réduction.

Avec def, nous pouvons également définir des fonctions avec des paramètres :

scala> def square(x: Double) = x * x
square: (Double)Double

scala> square(2)
res0: Double = 4.0

scala> square(5 + 3)
res1: Double = 64.0

scala> square(square(4))
res2: Double = 256.0

scala> def sumOfSquares(x: Double, y: Double) = square(x) + square(y)
sumOfSquares: (Double,Double)Double

scala> sumOfSquares(3, 2 + 2)
res3: Double = 25.0

Les paramètres des fonctions sont placés après le nom de la fonction et sont toujours placés entre parenthèses. Chaque paramètre est associé à un type qui est indiqué après le nom du paramètre et le caractère deux-points. Ici, nous n'avons besoin que de types numériques de base, comme scala.Double, qui décrit les nombres flottants en double précision. Scala définit des alias pour certains types standard : vous pouvez donc écrire les types numériques comme en Java - double, par exemple, est un alias du type Scala.Double et int est un alias de Scala.Int.

Les fonctions avec des paramètres sont évaluées comme les opérateurs dans les expressions. Les arguments de la fonction sont d'abord évalués (de gauche à droite), puis l'appel de fonction est remplacé par sa partie droite et, en même temps, tous ses paramètres formels sont remplacés par les arguments effectifs correspondants.(2)

sumOfSquares(3, 2+2)
sumOfSquares(3, 4)
square(3) + square(4)
3 * 3 + square(4)
9 + square(4)
9 + 4 * 4
9 + 16
25

Cet exemple montre que l'interpréteur réduit les arguments des fonctions en valeurs avant de réécrire l'application de la fonction. On aurait pu choisir d'appliquer la fonction aux paramètres non réduits, ce qui aurait donné la suite de réductions suivante :

sumOfSquares(3, 2+2)
square(3) + square(2+2)
3 * 3 + square(2+2)
9 + square(2+2)
9 + (2+2) * (2+2)
9 + 4 * (2+2)
9 + 4 * 4
9 + 16
25

Cette seconde évaluation est appelée appel par nom alors que la première est appelée appel par valeur. Pour les expressions qui n'utilisent que des fonctions pures et qui peuvent donc être réduites par le modèle de substitution, les deux approches donnent le même résultat final.

L'appel par valeur a l'avantage d'éviter de répéter l'évaluation des paramètres alors que l'appel par nom permet d'éviter l'évaluation des paramètres lorsque le paramètre n'est pas utilisé par la fonction. Généralement, l'appel par valeur est plus efficace que l'appel par nom, mais son évaluation peut provoquer une boucle sans fin là où un appel par nom se serait terminé. Considérons, par exemple, ces deux fonctions :

scala> def loop: Int = loop
loop: Int

scala> def first(x: Int, y: Int) = x
first: (Int,Int)Int

L'appel first(1, loop) avec un appel par nom produira 1 alors qu'avec un appel par valeur il se réduira éternellement en lui-même et l'évaluation ne se terminera donc jamais :

first(1, loop)
first(1, loop)
first(1, loop)
...

Scala utilise par défaut l'appel par valeur, mais bascule vers l'appel par nom si le type du paramètre est précédé du symbole =>.

scala> def constOne(x: Int, y: => Int) = 1
constOne: (Int,=> Int)Int

scala> constOne(1, loop)
res0: Int = 1

scala> constOne(loop, 2)        // boucle infinie
^C                              // Stoppe l'exécution avec Ctrl-C

Le if-else de Scala permet de choisir entre deux options. Sa syntaxe est identique au if-else de Java, mais, là où la structure de Java ne peut être utilisée que comme une alternative entre instructions, celle de Scala permet de choisir entre deux expressions. C'est la raison pour laquelle le if-else de Scala permet également de remplacer les expressions conditionnelles … ? … : … de Java.

scala> def abs(x: Double) = if (x >= 0) x else -x
abs: (Double)Double

Les expressions booléennes de Scala sont semblables à celles de Java : elles sont formées à partir des constantes true et false, des opérateurs de comparaison, de la négation booléenne ! et des opérateurs booléens && et ||.

Nous allons maintenant illustrer les éléments du langage que nous venons d'apprendre par un programme un peu plus intéressant. Nous allons écrire une fonction

def sqrt(x: Double): Double = ...

qui calcule la racine carrée de x.

Une méthode classique pour calculer les racines carrées est celle de Newton, qui consiste à réaliser des approximations successives. On part d'une approximation initiale y (y = 1, par exemple) puis on améliore progressivement cette approximation en prenant la moyenne de y et x/y. Les trois colonnes suivantes, par exemple, indiquent les valeurs de y, celles du quotient x/y et de leurs moyennes pour les premières approximations de la racine carrée de 2 :

1         2/1 = 2             1.5
1.5       2/1.5 = 1.3333      1.4167
1.4167    2/1.4167 = 1.4118   1.4142
1.4142    ...                 ...
y         x/y                 (y + x/y)/2

Nous pouvons implémenter cet algorithme en Scala à l'aide d'un ensemble de petites fonctions qui, chacune, représente l'un des éléments de cet algorithme. Commençons par définir une fonction qui itère à partir d'une approximation pour arriver à un résultat :

def sqrtIter(guess: Double, x: Double): Double =
    if (isGoodEnough(guess, x)) guess
    else sqrtIter(improve(guess, x), x)

Vous remarquerez que sqrtIter s'appelle récursivement. Les boucles des programmes impératifs peuvent toujours être modélisées par des appels récursifs dans un programme fonctionnel.

Notez également que la définition de sqrtIter indique le type du résultat, après la liste des paramètres. C'est obligatoire pour les fonctions récursives. Pour les autres, c'est facultatif : le vérificateur de type le déduira à partir de la partie droite de la fonction. Cependant, même pour les fonctions non récursives, il est généralement conseillé de préciser explicitement le type du résultat, car cela contribue à mieux documenter cette fonction.

La seconde étape consiste à définir les deux fonctions appelées par sqrtIter : une fonction pour améliorer l'approximation et une fonction de test isGoodEnough pour terminer la chaîne des appels récursifs :

def improve(guess: Double, x: Double) =
    (guess + x / guess) / 2
def isGoodEnough(guess: Double, x: Double) =
    abs(square(guess) - x) < 0.001

Enfin, la fonction sqrt elle-même est définie par une application de sqrIter :

def sqrt(x: Double) = sqrtIter(1.0, x)

Exercice 4-4-1 : Le test isGoodEnough n'est pas très précis pour les petits nombres et pourrait provoquer une boucle sans fin pour les très grands nombres (pourquoi ?). Proposez une autre version de isGoodEnough qui résout ces problèmes.

Exercice 4-4-2 : Faites la trace de l'exécution de l'expression sqrt(4).

Le style de programmation fonctionnelle encourage la construction de nombreuses petites fonctions auxiliaires. Dans le dernier exemple, l'implémentation de sqrt utilise les fonctions auxiliaires sqrIter, improve et isGoodEnough. Ces fonctions n'ont un intérêt que pour l'implémentation de sqrt. Il est préférable que les utilisateurs ne puissent pas y accéder directement.

Nous pouvons imposer cette restriction (et éviter la pollution de l'espace de noms) en incluant ces fonctions auxiliaires dans la fonction appelante :

def sqrt(x: Double) = {
    def sqrtIter(guess: Double, x: Double): Double =
        if (isGoodEnough(guess, x)) guess
        else sqrtIter(improve(guess, x), x)
    def improve(guess: Double, x: Double) =
        (guess + x / guess) / 2
    def isGoodEnough(guess: Double, x: Double) =
        abs(square(guess) - x) < 0.001 sqrtIter(1.0, x)
}

Dans ce code, les accolades { … } délimitent un bloc. En Scala, les blocs sont eux-mêmes des expressions : chaque bloc se termine par une expression résultat qui définit sa valeur. Cette expression résultat peut être précédée de définitions auxiliaires, qui ne seront visibles que dans le bloc.

Dans un bloc, chaque définition doit être suivie d'un point-virgule qui sépare cette définition des définitions suivantes ou de l'expression résultat. Toutefois, ce point-virgule est inséré implicitement à la fin de chaque ligne, sauf dans les cas suivants :

1. La ligne se termine par un point ou par un opérateur infixé qui ne peut pas apparaître à la fin d'une expression ;
2. La ligne suivante commence par un mot qui ne peut pas débuter une expression.
3. Nous sommes entre des parenthèses ( … ) ou des crochets, qui ne peuvent pas contenir plusieurs instructions.

Les exemples suivants sont donc tous corrects :

def f(x: Int) = x + 1;
f(1) + f(2)

def g1(x: Int) = x + 1
g(1) + g(2)

def g2(x: Int) = {x + 1}; /* ";"  obligatoire */ g2(1) + g2(2)
def h1(x) =
  x +
  y
h1(1) * h1(2)

def h2(x: Int) = (
  x         // Parenthèses obligatoires, sinon un point-virgule
  + y       // serait inséré après le x
)
h2(1) / h2(2)

Scala utilise les règles de portée habituelles des blocs. Un nom défini dans un bloc externe est également visible dans un bloc interne à condition qu'il n'y soit pas redéfini. Cette règle permet de simplifier notre exemple sqrt, car nous n'avons plus besoin de passer x en paramètre aux fonctions imbriquées puisqu'il sera toujours visible en tant que paramètre de la fonction externe sqrt. Voici le code simplifié :

def sqrt(x: Double) = {
    def sqrtIter(guess: Double): Double =
        if (isGoodEnough(guess)) guess
        else sqrtIter(improve(guess))
    def improve(guess: Double) =
        (guess + x / guess) / 2
    def isGoodEnough(guess: Double) =
        abs(square(guess) - x) < 0.001
    sqrtIter(1.0)

Considérons la fonction suivante, qui calcule le plus grand diviseur commun de deux nombres :

def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

Avec notre modèle de substitution pour l'évaluation des fonctions, l'évaluation de gcd(14, 21) sera :

     gcd(14, 21)
→    if (21 == 0) 14 else gcd(21, 14 % 21)
→    if (false) 14 else gcd(21, 14 % 21)
→    gcd(21, 14 % 21)
→    gcd(21, 14)
→    if (14 == 0) 21 else gcd(14, 21 % 14)
→  → gcd(14, 21 % 14)
→    gcd(14, 7)
→    if (7==0) 14 else gcd(7, 14 % 7)
→  → gcd(7,14 % 7)
→    gcd(7, 0)
→    if(0 = =0) 7 else gcd(0, 7 % 0)
→  → 7

Comparez cette évaluation avec celle d'une autre fonction récursive, factorielle :

def factorielle(n: Int): Int = if (n == 0) 1 else n * factorielle(n - 1)

L'appel factorielle(5) s'effectue de la façon suivante :

        factorielle(5)
→       if (5 == 0) 1 else 5 * factorielle(5 - 1)
→       5 * factorielle(5 - 1)
→       5 * factorielle(4)
→ ... → 5 * (4 * factorielle(3))
→ ... → 5 * (4 * (3 * factorielle(2)))
→ ... → 5 * (4 * (3 * (2 * factorielle(1))))
→ ... → 5 * (4 * (3 * (2 * (1 * factorielle(0))))
→ ... → 5 * (4 * (3 * (2 * (1 * 1))))
→ ... → 120

On note une différence importante entre ces deux séquences de réécriture : les termes de la séquence de réécriture de gcd ont toujours la même forme. À mesure que l'évaluation progresse, leur taille est limitée par une constante. Dans l'évaluation de factorielle, par contre, nous obtenons des chaînes d'opérandes de plus en plus longues qui sont ensuite multipliées dans la dernière partie de l'évaluation.

Bien que les véritables implémentations de Scala ne fonctionnent pas en réécrivant les termes, elles devraient avoir le même comportement en termes d'espace d'exécution que ces séquences de réécriture. Dans l'implémentation de gcd, on note que l'appel récursif est la dernière action réalisée dans l'évaluation du corps. On dit aussi que gcd est « récursive terminale ». Le dernier appel d'une fonction récursive terminale peut être implémenté par un saut revenant au début de cette fonction. En outre, les paramètres de cet appel peuvent écraser les paramètres de l'instance courante de gcd si bien qu'ici, on n'a pas besoin d'un nouvel espace de pile. Les fonctions récursives terminales sont donc des processus itératifs qui peuvent s'exécuter dans un espace d'exécution constant.

L'appel récursif dans factorielle, par contre, est suivi d'une multiplication. Il faut donc allouer un nouveau cadre de pile pour l'instance récursive de factorielle et le désallouer lorsque cette instance se sera terminée. Notre formulation actuelle de factorielle n'est pas récursive terminale et, pour s'exécuter, a besoin d'un espace proportionnel à son paramètre d'entrée.

Plus généralement, si la dernière action d'une fonction est un appel à une autre fonction ou à la même fonction, il suffit d'un seul cadre de pile pour les deux fonctions. Ces appels sont appelés « appels terminaux » et peuvent, en principe, toujours réutiliser le cadre de pile de la fonction appelante. Cependant, certains environnements d'exécution (c'est le cas de la machine virtuelle Java) ne disposent pas des primitives permettant de réutiliser un cadre de pile pour optimiser les appels terminaux. On exige par conséquent uniquement d'une implémentation de production de Scala qu'elle puisse réutiliser le cadre de pile d'une fonction récursive terminale directe, dont la dernière action consiste à s'appeler elle-même. Les autres appels terminaux peuvent également être optimisés, mais cela est propre à l'implémentation et donc non garanti.

Exercice 4-6-1 : Écrivez une version récursive terminale de factorielle.