Tutoriel pour apprendre le langage Scala par l'exemple

Nous voyons normalement le monde comme un ensemble d'objets, dont certains ont un état qui change au cours du temps. Généralement, l'état est associé à un ensemble de variables qui peuvent être modifiées au cours d'un calcul. Il existe également une notion plus abstraite de l'état, qui ne fait référence à aucune construction particulière d'un langage de programmation : un objet a un état si son comportement est influencé par son histoire.

Un compte bancaire, par exemple, a un état, car la question « puis-je retirer 100 € » peut avoir des réponses différentes au cours de la durée de vie de ce compte.

En Scala, l'état modifiable est construit à partir des variables. Une définition de variable s'écrit comme une définition de valeur, mais est introduite par var au lieu de val. Les deux définitions suivantes, par exemple, introduisent et initialisent deux variables, x et count :

var x: String = "abc"
var count     = 111

Comme une définition de valeur, une définition de variable associe un nom à une valeur, mais, dans le cas d'une définition de variable, cette association peut être ensuite modifiée par une affectation, qui s'écrit comme en C ou en Java :

x = "hello"
count = count + 1

En Scala, toute variable doit être initialisée lors de sa définition. L'instruction var x: Int;, par exemple, n'est pas considérée comme une définition de variable, car il manque l'initialisation (6). Si l'on ne connaît pas, ou que l'on ne veut pas connaître, la valeur d'initialisation adéquate, on peut utiliser un joker :

val x: T = _

qui initialisera x avec une valeur par défaut (null pour les types référence, false pour les booléens et la version appropriée de 0 pour les types valeurs numériques). Les objets du monde réel avec un état sont représentés en Scala par des objets ayant des variables dans leurs membres. Voici par exemple une classe représentant un compte bancaire :

class BankAccount {

    private var balance = 0

    def deposit(amount: Int) {
        if (amount > 0) balance += amount
    }

    def withdraw(amount: Int): Int =
        if (0 < amount && amount <= balance) {
            balance -= amount
            balance
        } else error("insufficient funds")
}

Cette classe définit une variable balance contenant la balance courante d'un compte. Les méthodes deposit et withdraw modifient la valeur de cette variable par des affectations. Vous remarquerez que balance est privée - elle ne peut donc pas être accédée directement depuis l'extérieur de la classe BankAccount.

Pour créer des comptes, on utilise la notation classique de création d'objets :

val myAccount = new BankAccount

Exemple 11-1-1 : Voici une session scala qui manipule des comptes bancaires.

scala> :l bankaccount.scala
Loading bankaccount.scala...
defined class BankAccount
scala> val account = new BankAccount
account: BankAccount = BankAccount\$class@1797795
scala> account deposit 50
res0: Unit = ()
scala> account withdraw 20
res1: Int = 30
scala> account withdraw 20
res2: Int = 10
scala> account withdraw 15
java.lang.Error: insufficient funds
    at scala.Predef$error(Predef.scala:74)
    at BankAccount$class.withdraw(<console>:14)
    at <init>(<console>:5)
scala>

Cet exemple montre qu'appliquer deux fois la même opération (withdraw 20) à un compte donne des résultats différents. Les comptes sont donc des objets avec état.

Identité et changement. Les affectations posent de nouveaux problèmes lorsque l'on veut savoir si deux expressions « sont identiques ». Lorsque les affectations sont exclues et que l'on écrit :

val x = E; val y = E

où E est une expression quelconque, on peut raisonnablement supposer que x et y sont identiques. On aurait donc pu également écrire :

val x = E; val y = x

(Cette propriété est généralement appelée transparence référentielle). En revanche, si l'on autorise l'affectation, ces deux suites de définitions sont différentes. Considérez les définitions suivantes, par exemple :

val x = new BankAccount; val y = new BankAccount

Pour savoir si x et y sont identiques, nous devons être plus précis dans ce que nous entendons par « identique ». La signification de ce mot est capturée par la notion d'équivalence opérationnelle qui, de façon informelle, peut se décrire comme suit.

Supposons que nous ayons deux définitions de x et y. Pour tester si x et y définissent la même valeur, nous devons :

• exécuter les définitions suivies par une séquence quelconque S d'opérations impliquant x et y et observer les éventuels résultats ;
• puis, exécuter les définitions avec une autre séquence S' produite à partir de S en renommant en x toutes les occurrences de y dans S ;
• si le résultat de S' est différent, alors x et y le sont sûrement aussi ;
• par contre, si toutes les paires de séquences {S, S'} possibles produisent le même résultat, alors x et y sont identiques.

Autrement dit, l'équivalence opérationnelle considère que deux définitions x et y définissent la même valeur si aucun test ne permet de les distinguer. Dans ce contexte, un test est formé de deux versions d'un programme quelconque utilisant soit x soit y.

Testons donc si :

val x = new BankAccount; val y = new BankAccount

définissent des valeurs x et y identiques. Voici à nouveau les définitions, suivies d'une séquence de test :

> val x = new BankAccount
> val y = new BankAccount
> x deposit 30
30
> y withdraw 20
java.lang.RuntimeException: insufficient funds

Renommons maintenant en x toutes les occurrences de y dans cette séquence :

> val x = new BankAccount
> val y = new BankAccount
> x deposit 30
30
> x withdraw 20
10

Les deux résultats étant différents, nous avons donc établi que x et y ne sont pas identiques. En revanche, si nous définissons :

val x = new BankAccount; val y = x

aucune séquence d'opérations ne permet de distinguer x et y, qui sont donc identiques ici.

Affectation et modèle de substitution. Ces exemples montrent que notre précédent modèle de substitution ne peut plus être utilisé pour les calculs. Avec ce modèle, nous pouvions toujours remplacer un nom de valeur par l'expression qui lui était liée :

val x = new BankAccount; val y = x

Ici, le x dans la définition de y pouvait être remplacé par new BankAccount. Mais nous venons de voir que cette modification menait à un programme différent. Le modèle de substitution n'est donc plus valide dès que l'on ajoute l'affectation.

Scala dispose des boucles while et do-while de C et Java. Il possède également une instruction if dont la partie else est facultative et d'une instruction return qui termine immédiatement la fonction qui l'invoque. Tout ceci permet donc d'écrire un programme dans un style impératif classique. La fonction suivante, par exemple, calcule le n^e puissance du paramètre x en utilisant une boucle while et un if sans clause else :

def power(x: Double, n: Int): Double = {
    var r = 1.0
    var i = n
    var j = 0
    while (j < 32) {
        r = r * r
        if (i < 0)
            r *= x
        i = i << 1
        j += 1
    }
    r
}

Ces structures de contrôle impératives sont présentes dans le langage pour des raisons de commodité, mais elles auraient pu être absentes, car elles peuvent être implémentées uniquement à l'aide de fonctions. Développons, par exemple, une implémentation fonctionnelle de cette boucle while. whileLoop est une fonction qui doit prendre deux paramètres : une condition de type Boolean et une commande de type Unit. Ces deux paramètres doivent être passés par nom, afin qu'ils soient évalués à chaque itération. Ceci nous conduit donc à la définition suivante :

def whileLoop(condition: => Boolean)(command: => Unit) {
    if (condition) {
        command; whileLoop(condition)(command)
    } else ()
}

Notez que whileLoop est récursive terminale : elle utilise donc une taille de pile constante.

Exercice 11-2-1 : Écrivez une fonction repeatLoop qui devra s'appliquer de la façon suivante :

repeatLoop { command } ( condition )

Peut-on également obtenir une syntaxe de boucle de la forme repeatLoop { command } until ( condition ) ?

Certaines structures de contrôle de C et Java n'existent pas en Scala : il n'y a ni break ni continue pour les boucles. Il n'y a pas non plus de boucles for au sens de Java - elles ont été remplacées par la construction for que nous avons présentée dans la section 10.4Boucles for.

Nous allons maintenant construire un simulateur de circuits logiques pour montrer comment combiner efficacement affectations et fonctions d'ordre supérieur.

Cet exemple est tiré du livre d'Abelson et Sussman, Structure and Interpretation of Computer Programs - 2^e édition (MIT Press, 1996). Nous étendrons leur code de base (écrit en Scheme) par une structure orientée objet qui permet de réutiliser le code au moyen de l'héritage. Cet exemple montre également comment structurer et construire des programmes de simulation d'événements discrets.

Nous commencerons par un petit langage permettant de décrire les circuits logiques. Un circuit est composé de connexions et de portes. Les connexions transportent les signaux qui sont transformés par les portes. Les signaux seront représentés par les booléens true et false.

Les portes de base sont :

• inverseur, qui applique une négation logique à un signal ;
• une porte et, dont la sortie est la conjonction de ses entrées ;
• une porte ou, dont la sortie est la disjonction de ses entrées.

Toutes les autres portes peuvent être construites à partir de ces trois portes de base.

Lorsque ses entrées sont modifiées, la sortie d'une porte n'est elle-même modifiée qu'après un certain délai.

Langage pour les circuits numériques. Nous décrivons les éléments d'un circuit logique par un ensemble de classes et de fonctions Scala.

Il faut d'abord une classe Wire pour pouvoir construire des connexions :

val a = new Wire
val b = new Wire
val c = new Wire

Puis, nous avons besoin des procédures suivantes :

def inverter(input: Wire, output: Wire)
def andGate(a1: Wire, a2: Wire, output: Wire)
def orGate(o1: Wire, o2: Wire, output: Wire)

qui « créent » les portes de base dont nous avons besoin (sous forme d'effets de bord). Les portes plus complexes peuvent être construites à partir de ces trois procédures. Par exemple, pour construire un demi-additionneur, nous pouvons écrire :

def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) {
    val d = new Wire
    val e = new Wire
    orGate(a, b, d)
    andGate(a, b, c)
    inverter(c, e)
    andGate(d, e, s)
}

Cette abstraction peut elle-même servir à construire un additionneur, par exemple :

def fullAdder(a: Wire, b: Wire, cin: Wire, sum: Wire, cout: Wire) {
    val s = new Wire
    val c1 = new Wire
    val c2 = new Wire
    halfAdder(a, cin, s, c1)
    halfAdder(b, s, sum, c2)
    orGate(c1, c2, cout)
}

La classe Wire et les fonctions inverter, andGate et orGate représentent donc un petit langage permettant aux utilisateurs de définir des circuits logiques. Nous allons maintenant les implémenter afin de pouvoir simuler le fonctionnement de circuits. Ces implémentations reposent sur une API simple et générale pour la simulation d'événements discrets.

L'API de simulation. La simulation d'événements discrets réalise des actions définies par l'utilisateur à des instants précis. Une action est représentée par une fonction qui ne prend pas de paramètre et renvoie un résultat Unit :

type Action = () => Unit

Ici, le temps sera simulé ; il ne s'agit pas du temps réel d'une horloge.

Une simulation concrète sera représentée par un objet qui hérite de la classe abstraite Simulation dont la signature est la suivante :

abstract class Simulation {
    def currentTime: Int
    def afterDelay(delay: Int, action: => Action)
    def run()
}

Ici, currentTime renvoie le temps courant, simulé sous la forme d'un entier. afterDelay planifie une action pour qu'elle s'exécute après un délai par rapport à currentTime et run exécute la simulation jusqu'à ce qu'il n'y ait plus d'actions à réaliser.

La classe Wire. Une connexion doit fournir trois actions de base :

• getSignal: booléen renvoyant le signal courant sur la connexion ;
• setSignal(sig: Boolean): fixe le signal de la connexion à sig ;
• addAction(p: Action): attache la procédure p indiquée aux actions de la connexion.

Toutes les actions attachées s'exécuteront à chaque fois que le signal de la connexion change.

Voici une implémentation possible de la classe Wire :

class Wire {
    private var sigVal = false
    private var actions: List[Action] = List()
    def getSignal = sigVal
    def setSignal(s: Boolean) =
        if (s != sigVal) {
            sigVal = s
            actions.foreach(action => action())
        }
    def addAction(a: Action) {
        actions = a :: actions; a()
}

L'état d'une connexion est représenté par deux variables privées. sigVal contient le signal courant et actions représente les procédures actuellement attachées à la connexion.

La classe Inverseur. Un inverseur est implémenté en installant une action sur sa connexion d'entrée - l'action qui place la négation du signal d'entrée sur le signal de sortie. Cette action doit prendre effet InverterDelay unités de temps après la modification de l'entrée :

def inverter(input: Wire, output: Wire) {
    def invertAction() {
        val inputSig = input.getSignal
        afterDelay(InverterDelay) { output setSignal !inputSig }
    }
    input addAction invertAction
}

La classe ET. Les portes ET sont implémentées de la même façon que les inverseurs. L'action d'une telle porte consiste à mettre sur sa connexion de sortie la conjonction de ses signaux d'entrée AndGateDelay unités de temps après que l'une de ses entrées a changé :

def andGate(a1: Wire, a2: Wire, output: Wire) {
    def andAction() {
        val a1Sig = a1.getSignal
        val a2Sig = a2.getSignal
        afterDelay(AndGateDelay) { output setSignal (a1Sig & a2Sig) }
    }
    a1 addAction andAction
    a2 addAction andAction
}

Exercice 11-3-1 : Proposez une implémentation de orGate.

Exercice 11-3-2 : Un autre moyen de définir une porte OU consiste à combiner des inverseurs et des portes ET. Définissez une fonction orGate en termes de andGate et inverter. Quel est le délai de cette fonction ?

La classe Simulation. Il reste simplement à implémenter la classe Simulation et nous aurons terminé. Le principe est de maintenir un agenda d'actions à réaliser dans un objet Simulation. Cet agenda est représenté par une liste de paires d'action et de moment où ces actions doivent s'exécuter. Cette liste est triée, de sorte que les actions à exécuter en premier soient les premières de la liste.

abstract class Simulation {
    case class WorkItem(time: Int, action: Action)
    private type Agenda = List[WorkItem]
    private var agenda: Agenda = List()

Cette classe utilise également une variable privée curtime pour mémoriser l'instant actuel (simulé).

private var curtime = 0

L'appel de la méthode afterDelay(delai, bloc) insère l'élément WorkItem(currentTime + delai, () => bloc) au bon endroit dans la liste d'agenda.

private def insert(ag: Agenda, item: WorkItem): Agenda =
    if (ag.isEmpty || item.time < ag.head.time) item :: ag
    else ag.head :: insert(ag.tail, item)

def afterDelay(delay: Int)(block: => Unit) {
    val item = WorkItem(currentTime + delay, () => block)
    agenda = insert(agenda, item)
}

L'appel de la méthode run supprime les éléments de l'agenda et exécute leurs actions, jusqu'à ce que l'agenda soit vide :

private def next() {
    agenda match {
        case WorkItem(time, action) :: rest =>
            agenda = rest; curtime = time; action()
        case List() =>
    }
}

def run() {
    afterDelay(0) { println("*** simulation started ***") }
    while (!agenda.isEmpty) next()
}

Exécution du simulateur. Pour exécuter le simulateur, nous avons besoin de pouvoir inspecter les modifications des signaux sur les connexions. C'est ce que fait la fonction probe :

def probe(name: String, wire: Wire) {
    wire addAction { () =>
        println(name + " " + currentTime + " new_value = " + wire.getSignal)
    }
}

Pour voir le simulateur en action, définissons maintenant quatre connexions et testons deux d'entre elles :

scala> val input1, input2, sum, carry = new Wire

scala> probe("sum", sum)
sum 0 new_value = false

scala> probe("carry", carry)
carry 0 new_value = false

Définissons ensuite un demi-additionneur qui relie ces connexions :

scala> halfAdder(input1, input2, sum, carry)

Enfin, configurons à true les signaux sur les deux entrées et lançons la simulation :

scala> input1 setSignal true; run
*** simulation started ***
sum 8 new_value = true

scala> input2 setSignal true; run
carry 11 new_value = true
sum 15 new_value = false

Ce chapitre a présenté les instructions permettant de modéliser l'état en Scala - variables, affectations et structures de contrôle impératives. L'état et l'affectation compliquent notre représentation mentale des calculs ; on perd notamment la transparence référentielle. En revanche, les affectations nous fournissent de nouvelles façons de formuler élégamment les programmes. Comme toujours, c'est la situation qui dictera le choix entre une programmation purement fonctionnelle et une programmation avec des affectations.