Exos de PAS

Ceci est une tentative de créer des nouveaux types d'exercices de Scala à faire en classe, au-delà des choix multiples. Le but est de créer des exos challengeants qui pousse à l'esprit critique et la réflexion, à lire du code et trouver des détails, pour développer un modèle mental solide du langage.

Vue d'ensemble

Actuellement, on trouve des exercices sur les sujets suivants

Lazylist

Objectif: arriver à imaginer plus concrètement ce que l'évaluation paresseuse signifie vraiment où suivre l'exécution est beaucoup plus ardu.

Important à savoir: LazyList.from(n: Int) retourne une lazylist infinie de nombre entiers commençant par n.

TODO: utiliser d'autres formes d'initialisations de LazyList.

1 Comportement des Lazylist

1.1

Qu'affiche ce code ?

val list = LazyList.from(1)
val result = list
    .map(_ + 1)
    .filter(_ > 3)
    .take(7).map(n => print(s"$n "))
print("done")
Solution

Elle affiche juste done, aucun map filter ou take ne s'effectue comme toutes les méthodes sont lazy.

1.2

1.2.1 Qu'affiche ce code ?

  val list = LazyList.from(1)
  val result = list
      .map(_ + 1)
      .take(4)
      .filter(_ > 3)
      .toList
      .map(n => print(s"$n "))
  print("done")
Solution

Elle affiche juste 4 5 done.

1.2.2

Quelle est la première méthode non lazy qui déclenche l'usage des méthodes lazy ?

Solution

C'est la méthode toList qui va lire la liste donnée par le filter jusqu'à arriver à la fin, filter a son tour va déclencher la génération du take et du map.

1.3

Ce code a un petit soucis à l'exécution, peux-tu l'imaginer et expliquer le problème ?

val list = LazyList.from(1)
val result = list
  .dropWhile(_ < 10)
  .map(_ * 3)
  .toList
print("done")
Solution

La LazyList étant infinie, la création de la List via le toList ne se finira jamais car nous n'avons pas défini de limite dans le nombre d'éléments ou une autre contraintes qui permettrait de s'arrêter à un moment. On aurait pu utiliser take ou définir une LazyList finie.

1.4 - Un simple aller-retour

Qu'affiche ce morceau de code ?

val list = LazyList.from(2)
val result = list.map(n => {print(s"m$n "); n}) // affiche m3 quand n vaut 3
val result2 = result.take({print("take "); 3})
val result3 = result2.filter(n => {print(s"f$n "); n > 2})  // affiche f3 quand n vaut 3
result3.toList.map(n => print(s"$n "))
Solution 
take m2 f2 m3 f3 m4 f4 3 4

Explication de l'exécution et affichage étape par étape.

  1. map, filter n'évalue rien du tout comme leur paramètre sont en call by name (Rien tant qu'on appelle pas la méthode toList.)
  2. La méthode take qui prend un Int en paramètre (c'est un call by value normal), on va donc évaluer son paramètre, cette expression va afficher le mot take et retourner 3
  3. Le toList va trigger une génération de la liste result3 fournie par le filter, qui va lui même lire la liste donnée par take et qui va lui même lire la liste donnée par map. map va demander la suite de la liste de from qui va donner 2.
  4. map doit ensuite appliquer sa fonction, d'où l'affichage de m2
  5. cette valeur passe le take qui n'a plus que 2 éléments à laisser passer avant d'indiquer la fin de la liste
  6. le filter doit maintenant appliquer sa fonction et affiche f2
  7. le toList construit sa List[Int] et demande l'élément suivant jusqu'à arriver à LazyList.empty. Ce qui fait les mêmes allers retours que précédemment pour chercher le 3 et le 4, d'où m3 f3 m4 f4.
  8. Les allers retours s'arrête dès que take a traité 3 éléments, le filter n'a retourné que les 2 derniers (le 3 et le 4)
  9. Notre liste est donc List(3, 4), celle ci passe dans le map final ce qui affiche 3 4 à la fin

2 Code équivalent ?

Ce code

val list = LazyList.from(2)
val result = list.map(_ + 5)
val result2 = result.take(3)
val result3 = result2.filter(_ > 2)
result3.toList

est-il équivalent en terme de résultat et d'exécution à cette autre code ?

val list = LazyList.from(2)
val result = list
  .map(_ + 5)
  .take(3)
  .filter(_ > 2)
  .toList
Solution

Oui c'est équivalent, stocker les résultats intermédiaires peut paraitre "forcer" l'évaluation des listes mais non, cela reste des LazyList qui sont sauvées dans chaque variable result et évaluées le plus tard possible.

3 Nombre de valeurs dans une fonction intermédiaire

Combien de fois est appelé la fonction passé à filter ? Dit autrement, combien de lignes filtered something affiche ce code ?

val list = LazyList.from(0)
val result = list
  .map(_ + 3)
  .take(100)
  .filter(n => {println("filtered something"); n > 5})
  .take(4)
  .toList
Solution

7 fois. Le toList qui lance la génération via le take qui va continuer demander à filter jusqu'à avoir eu 4 éléments. Le filter va fail 3 fois (pour n = 3, 4, 5) puis réussir sur n = 6, 7, 8, 9. Le filter aura donc traité 3 + 4 = 7 valeurs.

Si tu as répondu 100, attention le take est lazy, il ne va pas générer une liste de 100 valeurs avant de continuer, il ne genère que sur demande du filter.

4 Compter les appels et déduire le résultat

4.1 Combien de fois est appelé la fonction passé à filter ? Dit autrement, combien de lignes filtered something affiche ce code ?

val list = (1 to 10).to(LazyList)
val result = list
.filter(n => {println("filtered something"); n > 7 })
.take(6)
.toList
Solution

10 fois. Le take continuera à demander à filter de travailler.

4.2 Question facile: Donne les valeurs de la List finale result, séparé par des espaces.

Solution 
8 9 10

(1 to 10) signifie une liste des éléments 1,2,3...10. La take a du s'arrêter a 3 éléments comme filter a retourné une LazyList.empty après que la queue de la LazyList a retourné une LazyList.empty après avoir donné 10 éléments.

5 Comprendre des erreurs de compilation, initialisation de LazyList

En écrivant ce morceau de code:

val list   = LazyList.cons(2, LazyList(12, LazyList.empty))
val result = list.dropWhile(_ < 10)

Nous obtenons cette erreur de compilation

[error] ./Main.scala:5:16
[error] value < is not a member of LazyList[Nothing] | Int
[error]     .dropWhile(_ < 10)
[error]                ^^^

Nous avons pourtant bien respecté la signature de apply du cons, un Int puis une LazyList. Explique en 1-2 phrases pourquoi cette erreur et comment la corriger ?

def apply[A](hd: => A, tl: => LazyList[A]): LazyList[A]
Solution

En fait list vaut LazyList(2, 12, LazyList.empty) au lieu de LazyList(2, 12)

L'erreur provient de la queue de la liste définie comme une lazylist contenant un Int et une LazyList vide (du type List[Nothing]), list est au final une LazyList[LazyList[Nothing] | Int], et l'erreur nous indique que l'opérateur < n'est pas disponible sur les LazyList !

Il faut donc corriger l'oubli de l'opérateur cons à la place pour avoir à nouveau une LazyList[Int] sur le 2ème argument.

val list   = LazyList.cons(2, LazyList.cons(12, LazyList.empty))

Future

1 Découverte des futures

1.1

Etant donnée le code suivant

@main def hello(): Unit = {
  println("Go")
  for i <- 1 to 3 do Future { println("o") }
  println("End")
}

On lance le programme une première fois et on obtient le code suivant.

Go
End

Pourquoi il n'y a-t-il pas d'affichage des o ?

Solution

Parce que l'ordonnanceur des tâches asynchrone a choisi d'exécuter d'abord la tâche principal (d'où le End final) et ensuite le programme a quitté sans attendre les futures lancées.

On aurai pu mettre un Thread.sleep par exemple pour attendre volontairement un certain temps.

1.2

Etant donnée le code suivant

@main def hello(): Unit = {
  println("Go")
  for i <- 1 to 3 do Future { println("o") }
  println("End")
}

Coche toutes les exécutions possibles du programme

A

Go
o
o
End
o

B

Go
o
End

C

o
Go
End

D

Go
o
o
End

F

End
Go
o
o
o

G

Go

H

Go
ooo


End
Solution

La solution est A, B, D. Le reste est faux parce que Go doit être avant End, End est forcément affiché, et Go est forcément après un premier o. La H est fausse car le println imprime le o et le \n d'un seul coup, ils ne peuvent pas donc être fait de manière séparée.

Si on le compile nativement ce fichier Main.scala

scala-cli package --power Main.scala --native

et qu'on l'exécute 100 fois avec un petit utilitaire xtimes (créé pour le cours de PCO), on peut voir que même si certaines sont beaucoup rares que d'autres, toutes les ordres d'exécutions des futures sont possibles et qu'on a aucune garantie sur l'exécution et quelle future pourra se terminer ou non.

> xtimes 100 ./hello
Results
 7 times
Go
o
o
End
o

 2 times
Go
o
End

89 times
Go
o
o
End

1 time
Go
o
o
End
o

1 time
Go
End

1.3

Citer les 3 états possible des futures.

Solution
  • En cours
  • Terminé avec succès
  • Terminé avec échec

1.4

Quel est le problème dans ce morceau de code ? Donner le nom de ce qui est fait et expliquer quelle autre approche corrige le problème.

import scala.concurrent.*
import scala.concurrent.ExecutionContext.Implicits.global

// A slow function running "tool --version" and extracting the version number
def getInstalledSoftwareVersion(tool: String): Future[String] = ???

@main def hello(): Unit =
  val f1 = getInstalledSoftwareVersion("sbt")
  while !f1.isCompleted do Thread.sleep(100)
  val version = f1.value // Note: simplified version
  println(s"sbt version $version is installed !")
Solution

Le problème c'est qu'on fait de l'attente active, on attend activement que la Futur se finisse, ce qui retire tout l'intérêt de son exécution asynchrone qui permet de faire autre chose. Autant lancer le travail sans Future à ce moment là. A la place on ne va pas attendre dessus mais directement définir ce qui se passe quand la future sera en état terminé.

2 Imaginer l'exécution

2.1

Etant donnée ce code, quelles affirmations sont garanties ?

import scala.concurrent.*
import scala.concurrent.ExecutionContext.Implicits.global

@main def hello(): Unit = {
  Future { print("A ") }.map { x => print("B ") }
  Future { print("C ") }.map { x => print("D ") }
  Thread.sleep(200)
}
  1. L'affichage donne A B C D
  2. Le code affiche forcément les 4 lettres
  3. A s'affiche avant B
  4. B s'affiche avant C
  5. A s'affiche avant D
  6. C s'affiche avant D
  7. La future avec A commence avant celle pour C
Solution

La solution est 3 et 6. Tout le reste est faux. Pour la 2, on pourrait voir dans un cas extrême un ordonnancement qui ne lance pas une des futures avant 200ms. Le programme quitterait après avoir affiché seulement 3 lettres.

En pratique on voit que l'ordonnancement est très souvent fait dans l'ordre "logique" imaginé.

> xtimes 1000 ./hello
Results
 7 times A C B D
 4 times C A B D
985 times A B C D
 4 times A C D B

Ran 1000 times './hello', found 4 unique outputs

2.2

Cet output est-il déterministe ? (en considérant que le temps en sleep est suffisant pour que toutes les futures se soient lancées).

  val f1 = Future { print("A ") }
  val f2 = f1.map { x => print("B ") }
  val f3 = f1.map { x => print("C ") }
  val f4 = f2.map { x => print("D ") }
  Thread.sleep(100)
Solution

Non, les 2 map sur f1 font qu'on ne peut pas savoir si C ou B s'affiche d'abord.

2.3

Cet output est-il déterministe ? (en considérant que le temps en sleep est suffisant pour que toutes les futures se soient lancées).

  val f1 = Future { throw Exception("oups "); print("hey ") }
    .map(_ => print("yo "))
    .recover(e => print("error: " + e.getMessage()))
  Thread.sleep(100)

Si oui donne l'output, sinon explique pourquoi ce n'est pas déterministe.

Solution

C'est déterministe, et l'output est error: oups

2.4

Qu'affiche ce bout de code ?

  val f1 = Future { print("hey "); 2 }
    .recover(e => { print("error"); 4 })
    .map(x => print(s"ok $x"))
  Thread.sleep(100)
Solution

Le recover ne s'étant pas lancé, le valeur de résultat de la première future contient toujours 2, cette valeur est récupérée dans le x du map.

hey ok 2

2.5

Qu'affiche ce bout de code ?

  val f1 = Future { print("hey "); throw Exception("aii") }
    .recover(e => { print("error "); 4 })
    .map(x => print(s"ok $x"))
  Thread.sleep(100)
Solution 
hey error ok 4

Le recover définit une nouvelle valeur de résultat de la future à 4, ce qui explique sa récupération dans le map.

3 Types de futures

  val f0 = Future { List(1, 2, 3, 4) }
  val f1 = Future { print("hey ") }
  val f2 = Future { false }
  val f3 = f1.map(x => Future { true })
  val f4 = f2.flatMap(x => Future { if x then 2 else 5 })
  val f5 = f2.recoverWith(e => Future { e.getMessage() })
  val f6 = f0.map(_ => { throw Exception("oupsi"); 32 }).recover(e => e.getMessage())

3.1 Type de f0 ?

Solution 
Future[List[Int]]

3.2 Type de f1 ?

Solution 
Future[Unit]

3.3 Type de f2 ?

Solution 
Future[Boolean]

3.4 Type de f3 ?

Solution 
Future[Future[Boolean]]

3.5 Type de f4 ?

Solution 
Future[Int]

3.6 Type de f5 ?

Ca se corse attention...

Solution 
Future[Boolean | String]

3.7 Type de f6 ?

Solution 
Future[Int | String]

Même si la callback du map va dans tous les cas jeter un exception, le type de résultat Int reste à prendre en compte. Le type de retour de recover impacte le type de la future puisqu'elle passe dans l'état réussi à ce moment.

TODO: encore des exos de type sur les For comprehensions avec des Future

4 Code équivalent ?

Le code précédent

  Future { print("hey "); throw Exception("aii") }
    .recover(e => { print("error "); 4 })
    .map(x => print(s"ok $x"))
  Thread.sleep(100)

et cette version avec map et recover inversé

  Future { print("hey "); throw Exception("aii") }
    .map(x => print(s"ok $x"))
    .recover(e => { print("error "); 4 })
  Thread.sleep(100)

et cette troisième version

  val f1 = Future { print("hey "); throw Exception("aii") }
  f1.map(x => print(s"ok $x"))
  f1.recover(e => { print("error "); 4 })
  Thread.sleep(100)

sont-elles équivalentes en terme d'output ?

Solution

Non, la première version affiche

hey error ok 4

et la deuxième et la troisième version affiche

hey error

Pourquoi ? Dans la première, recover retourne une nouvelle future qui réussit après s'être "récupérée", et comme le map définit une callback à lancer si la future réussit elle est lancée également. Dans la 2ème version, la première future échoue donc map ne se lance pas, mais la future retournée par map transmet l'échec et cet échec est traité par recover. La troisième définit 2 autres callback sur la future originale, seulement celle du recover se lance.

5 Autres méthodes

5.1

Le code suivant

import scala.concurrent.*
import scala.concurrent.ExecutionContext.Implicits.global

@main def hello(): Unit =
  val f1 = Future { 1 }.map(x => Future {x + 2}).map(println)
  Thread.sleep(1000)

affiche Future(Success(3)), on aimerait qu'elle affiche 3 à la place. Change ce code pour que ça marche.

Solution 
import scala.concurrent.*
import scala.concurrent.ExecutionContext.Implicits.global

@main def hello(): Unit =
  val f1 = Future { 1 }.flatMap(x => Future {x + 2}).map(println)
  Thread.sleep(1000)

Il suffit d'utiliser flatMap qui va flatten la future de future en une future simple. Ainsi la future qui sort de flatMap est une Future[Int], ce qui nous permet d'avoir un Int qui arrive sur le println.

5.2

Comment refactoriser ce map et recover avec une seule méthode de Future ?

import scala.concurrent.*
import scala.concurrent.ExecutionContext.Implicits.global

@main def hello(): Unit =
  val f1 = Future { 1 }
    .map(x => println(s"Got $x"))
    .recover(e => println("Got an error sorry: " + e.getMessage()))
  Thread.sleep(1000)
Solution

Quand on veut traiter d'un coup le cas de succès et d'échec, on peut utiliser Future.transform

import scala.concurrent.*
import scala.concurrent.ExecutionContext.Implicits.global
import scala.util.*

@main def hello(): Unit =
  val f1 = Future { 1 }
    .transform {
      case Success(x) => println(s"Got $x"); Success(())
      case Failure(e) => println("Got an error sorry: " + e.getMessage()); Success(())
    }
  Thread.sleep(1000)

TODO: faire checker l'implémentation à la prof

6 méthodes et concepts avancées

6.2 On vous attend depuis une heure

Au lieu d'attendre un temps arbitraire comme ici 3 secondes, comment afficher "done" seulement quand les 3 futures suivantes sont-elles finies tout en gardant leur parallélisation ?

  val f1 = Future { Thread.sleep(1000); println("good") }
  val f2 = Future { Thread.sleep(2000); println("good") }
  val f3 = Future { Thread.sleep(1500); println("good") }
  Thread.sleep(3000)
  println("done")

Note: garde le Thread.sleep à la toute fin

Solution

On peut utiliser Future.sequence qui crée une nouvelle future qui se termine lorsque toutes les futures de la liste sont terminées.

import scala.concurrent.*
import scala.concurrent.ExecutionContext.Implicits.global

@main def hello(): Unit =
  val f1 = Future { Thread.sleep(1000); println("good") }
  val f2 = Future { Thread.sleep(2000); println("good") }
  val f3 = Future { Thread.sleep(1500); println("good") }
  Future.sequence(List(f1, f2, f3)).map(_ => println("done"))
  Thread.sleep(3000)

6.2 Fais de beaux rêves

Imaginons que la JVM lance ce code avec 5 threads natifs pour exécuter ces 7 futures, combien de temps prendra l'exécution total ?

  val f1 = Future { Thread.sleep(2000) }
  val f2 = Future { Thread.sleep(2000) }
  val f3 = Future { Thread.sleep(2000) }
  val f4 = Future { Thread.sleep(2000) }
  val f5 = Future { Thread.sleep(2000) }
  val f6 = Future { Thread.sleep(1000) }
  val f7 = Future { Thread.sleep(1000) }

Donner un temps approximatif en secondes (nombre entier). Note: Thread.sleep prend un temps en millisecondes en entrées.

Solution

1 seconde. Attention ce n'est pas 3 secondes.

Les Thread.sleep vont juste faire endormir la future, c'est à dire le thread virtuel géré dans la JVM. Cela ne n'endort pas le thread natif qui exécute le code d'une future, quand celle-ci s'endore celui-ci peut continuer de travailler. Ainsi toutes les futures seront lancées, elles s'endormiront toute à peu près en même temps, et se réveilleront également quasiment ensemble. Quand les 5 premières futures s'endorment les threads natifs peuvent gérer les futures 6 et 7.

6.3 J'ai bien tenté...

Explique avec tes propres mots ce que permet de répresenter le type Try et les différentes valeurs et types possibles.

TODO explication

6.4 J'ai bien cherché...

Donne 2 exemples d'équivalents du type Try de Scala dans d'autres languages!

Solution

En Rust, le type Result avec le type du résultat et type de l'erreur sont génériques.

enum Result<T, E> { Ok(T), Err(E) }

En Haskell, le type Either permet de représenter une valeur parmi 2 possibilités. On met généralement l'erreur à gauche et le résultat à droite (parce que le résultat is right -> est correct).

data Either a b = Left a | Right b

Même le C++ a un std::expected

template< class T, class E >
class expected;

6.5 Et pourquoi pas ?

Pourquoi on utilise Try et pas juste Option ?

Solution

Option permet de stocker qqch ou rien, tandis que Try stocke un résultat ou une erreur. Cela permet d'avoir des détails sur l'erreur contrairement à Option, dont l'absence de valeur ne signifie pas forcément une erreur et si c'était le cas on ne pourrait pas préciser de message ou d'informations de contexte sur None.

TODO: plus d'exos avec des estimations de temps passée pour mieux comprendre la parallélisation, inclure des listes de futures

7 Compte les futures

Il est parfois difficile de s'y retrouver dans toutes ces futures... essayons d'identifier où elles sont créées et combien on en trouve au total.

TODO: 2-3 exos là dessus

future.filter ->

refactoring entre différentes méthodes comme lexo de flatmap + filter+ recover refactor avec transformWith, transform.