Deck de flashcards

1. CM1 — Intro Scala

Une fonction pure, c'est…

Une fonction sans effet de bord. Résultat dépendant uniquement des paramètres en entrée. Toujours la même sortie pour les mêmes entrées.

Différence val / var ?

val = immuable (≡ final Java). var = mutable. La PF favorise val.

lazy val ?

Évaluation reportée au premier usage réel. Ensuite, la valeur calculée est conservée.

Sommet et bas de la hiérarchie Scala ?

Sommet : Any (parent de AnyVal et AnyRef). Bas : Nothing (sous-type de toute classe).

Option[T] ?

Ajouter la valeur « pas de valeur » au type T. Deux constructions : Some(x) ou None. Remplace les exceptions et le null.

Cinq transformations impératif → fonctionnel ?

Variable → Constante · Instruction → Expression typée · Procédure → Fonction pure · Boucle → Récursivité · Toute fonction est une expression typée.

Que renvoie 1 / 2 en Scala ?

0 : Int (division entière, comme en Java). Pour obtenir 0.5 : 1.toDouble / 2.

Tail-recursive ?

Fonction récursive telle que tout appel récursif est un appel direct de la fonction. Le compilateur peut éliminer la pile : pas de stack overflow.

2. CM2 — Fonctions

Aller au chapitre complet ↗

Fonction d'ordre supérieur ?

Une fonction qui prend une fonction en paramètre ou qui retourne une fonction. Ex : map, filter, fold.

Currification ?

Transformer une fonction à n arguments en une chaîne de fonctions à 1 argument. f(a, b) devient f(a)(b). Permet l'application partielle.

Application partielle ?

Fixer certains paramètres d'une fonction pour obtenir une nouvelle fonction des paramètres restants.

Syntaxe d'une lambda Scala ?

(x: Int) => x + 1 ou plus court _ + 1. L'underscore remplace un paramètre unique.

Anonyme vs nommée ?

Anonyme : (x) => x * 2. Nommée : def double(x: Int) = x * 2. La nommée est réutilisable, l'anonyme est in-line.

Récursion mutuelle ?

Deux fonctions qui s'appellent l'une l'autre. Ex : even appelle odd et inversement. À déclarer avec def, pas val.

Fonction foldLeft ?

Parcourt une collection en accumulant : List(1,2,3).foldLeft(0)(_ + _) renvoie 6. Sa généralisation est l'évaluation gauche-droite.

3. CM3 — POO Scala

Aller au chapitre complet ↗

class vs case class ?

case class génère automatiquement : equals, hashCode, toString, copy, apply, déstructuration via pattern matching, immutabilité par défaut.

object en Scala ?

Un singleton instancié automatiquement. Remplace les méthodes/champs statiques de Java. Utilisé pour les utilitaires et les companion objects.

Companion object ?

Un object portant le même nom qu'une classe, dans le même fichier. Peut accéder aux membres privés de la classe. Sert à définir apply, unapply, factories.

trait ?

Équivalent des interfaces Java + implémentation par défaut. Une classe peut mixer plusieurs traits avec with.

Pattern matching ?

Construction x match { case ... => ... }. Plus puissant que le switch : déstructure des types, capture des variables, gère les Options/Listes.

Héritage Scala

class Etudiant(nom: String, id: Int) extends Personne(nom). Une seule classe parente, plusieurs traits. override def pour redéfinir.

sealed ?

Empêche toute extension hors du fichier courant. Garantit l'exhaustivité d'un pattern matching : le compilateur prévient si un cas manque.

4. CM4 — Collections

Aller au chapitre complet ↗

Immutable vs mutable ?

Par défaut, les collections Scala sont immutables. Les versions mutables vivent dans scala.collection.mutable (à importer).

List ?

Liste chaînée immutable. :: pour préfixer, ::: pour concaténer. O(1) en tête, O(n) ailleurs.

Vector ?

Structure arborescente immutable à accès quasi-constant par index. Bon compromis général.

Set / Map immutables ?

Set(1, 2, 3), Map("a" -> 1, "b" -> 2). Opérations renvoient une nouvelle collection (structural sharing).

map, filter, flatMap ?

map : transforme chaque élément. filter : garde ceux qui matchent. flatMap : map + concaténation (utile pour Option/List).

For-comprehension ?

for (x <- xs; y <- ys if cond) yield expr. Sucre syntaxique pour flatMap + filter + map.

Tuple ?

Conteneur hétérogène fixe : val t = (1, "hello", 3.14). Accès par ._1, ._2, ._3. Jusqu'à 22 éléments.

Stream / LazyList ?

Liste paresseuse — les éléments sont calculés au besoin. Permet des séquences infinies. LazyList remplace Stream depuis Scala 2.13.

5. CM5 — Complexité

Aller au chapitre complet ↗

Big-O — définition formelle

$f(n) = O(g(n))$ ssi $\exists c, n_0 : \forall n \geq n_0, f(n) \leq c \cdot g(n)$. Borne supérieure asymptotique.

Complexités classiques par ordre croissant ?

$O(1) \subset O(\log n) \subset O(n) \subset O(n \log n) \subset O(n^2) \subset O(2^n) \subset O(n!)$

Tri rapide vs tri fusion ?

Tri fusion : $O(n \log n)$ garanti, mais $O(n)$ d'espace. Tri rapide : $O(n \log n)$ en moyenne, $O(n^2)$ au pire, en place.

Récurrence — exemple ?

Tri fusion : $T(n) = 2T(n/2) + O(n)$ → $O(n \log n)$ par théorème maître.

Théorème maître ?

Pour $T(n) = aT(n/b) + f(n)$, compare $f(n)$ avec $n^{\log_b a}$. Trois cas selon que $f$ est plus petit / égal / plus grand.

Complexité moyenne vs pire cas

Pire cas : borne supérieure sur tous les inputs. Moyenne : espérance sur une distribution d'inputs. Quicksort : moyen $O(n \log n)$, pire $O(n^2)$.

Complexité amortie ?

Coût moyen sur une séquence d'opérations. Ex : ArrayBuffer.append = $O(1)$ amorti même si certains appels coûtent $O(n)$ (doublement du tableau).

6. CM6 — Akka (acteurs)

Aller au chapitre complet ↗

Acteur ?

Entité de calcul concurrent avec : un état privé, une boîte aux lettres de messages, un comportement qui traite les messages un par un.

Modèle d'acteurs vs threads ?

Pas de mémoire partagée → pas de race conditions. Communication exclusivement par messages immutables envoyés via !. Évite mutex et deadlocks.

Envoi de message ?

acteur ! message — asynchrone, fire-and-forget. ? pour ask (renvoie un Future).

receive ?

Méthode partielle qui définit le comportement : pattern matching sur les types de messages. Un message non matché va dans la dead letter queue.

Système d'acteurs ?

Container hiérarchique de tous les acteurs (ActorSystem). Crée et supervise les acteurs racines. Un acteur est créé par system.actorOf(Props[MonActeur]).

Supervision ?

Chaque acteur a un parent qui décide quoi faire quand un enfant crashe : resume, restart, stop, ou escalate au sien.

"Let it crash" ?

Philosophie Akka : au lieu de défendre chaque appel par try/catch, laisser l'acteur planter et laisser le superviseur le redémarrer proprement.

Acteur distant ?

L'adresse d'un acteur (ActorRef) est transparente : local ou distant. Akka gère le routage. Permet la scalabilité horizontale.

★ Bonus — Réseaux de Petri

Aller à l'annexe complète ↗

Réseau de Petri

Graphe biparti orienté avec places (cercles), transitions (barres) et jetons. Modélise les systèmes concurrents et la synchronisation.

Transition tirable ?

Une transition est tirable si chacune de ses places en entrée contient au moins un jeton (ou le nombre exigé par le poids de l'arc).

Tirer une transition ?

Retire un jeton de chaque place en entrée + dépose un jeton dans chaque place en sortie. Un coup atomique.

Marquage ?

L'état du réseau : nombre de jetons dans chaque place. Représenté par un vecteur $M = (m_1, m_2, \ldots, m_p)$.

Trois propriétés clés

Vivant (toute transition peut toujours être tirée), borné (nombre de jetons par place limité), réinitialisable (on peut revenir au marquage initial).

Pourquoi à l'examen Scala ?

L'exercice 1 garanti par la prof porte sur Petri. Modélisation de la concurrence : producteur/consommateur, sections critiques, dîner des philosophes.