It-Signal - Programmation fonctionnelle

class: center, middle, normal

name: title

.title[Programmation fonctionnelle]

.author[.nolink[[Maxime Werlen](https://plus.google.com/+MaximeWerlen?rel=author")]]

---
class: center, middle
name: license

.small[.nolink[La présentation "Programmation fonctionnelle</a>" de <a xmlns:cc="http://creativecommons.org/ns#" href="http://maxime.werlen.fr/mwerlen.html" property="cc:attributionName" rel="cc:attributionURL">Maxime Werlen</a> est mis à disposition selon les termes de la <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International</a>.]]

.small[Source : <a xmlns:dct="http://purl.org/dc/terms/" href="http://maxime.werlen.fr/presentations/progfun.html" rel="dct:source">http://maxime.werlen.fr/presentations/progfun.html</a>]

???
* Savoir qu'il existe plusieurs paradigmes de programmation
* Savoir les différentier
* La théorie de la programmation fonctionnelle
* Savoir reconnaitre et utiliser les principaux pattern de la programmation fonctionnelle
* Voir la progfun dans la vraie vie

---
layout: true
class: center, middle, inverse

---
# Un peu d'histoire

???
#Programmation fonctionnelle

# Un ordinateur c'est quoi ?

---
layout: true
class: center, top, normal

---
# Architecture de Von Neumann

!["Schéma de l'architecture de Von Neumann"](http://upload.wikimedia.org/wikipedia/commons/thumb/0/01/Von_Neumann_architecture_fr.svg/420px-Von_Neumann_architecture_fr.svg.png)

???
## 1945 - Architecture Von Neumann

Ordinateur = machine à calculer
* faire des opérations (Unité arithmétique)
* traiter des données (IO)
* Enchainer les opérations (unité de contrôle)

→ Ca exécute une suite d'instructions : le programme

---
layout: true
class: center, middle, inverse

---

# C'est quoi un programme ?

---
layout: true
class: left, top, normal
---
## 1940 - Assembleur

```no-highlight
section .data                                 ; Variables initialisées
        Buffer:           db 'Bonjour', 10    ; En ascii, 10 = '\n'.
        BufferSize:     equ $-Buffer          ; Taille de la chaine

section .text                                 ; Le code source
        global _start                         ; Entrée du programme

_start:                                       ; Entrée du programme

mov eax, 4                            ; Appel de sys_write
        mov ebx, 1                            ; Sortie standard STDOUT
        mov ecx, Buffer                       ; Chaine à afficher
        mov edx, BufferSize                   ; Taille de la chaine
        int 80h                               ; Interruption du kernel

mov eax, 1                            ; Appel de sys_exit
        mov ebx, 0                            ; Code de retour
        int 80h                               ; Interruption du kernel

```

→ Exécution séquentielles d'opérations de déplacement et de calcul

???
## 1940 - Assembleur

* Déplacement d'octets en mémoire
* Calcul mathématique

---
## 1950 - Fortran

```no-highlight
 C     FORTRAN IV WAS ONE OF THE FIRST PROGRAMMING
 C     LANGUAGES TO SUPPORT SOURCE COMMENTS
 C     6 IS THE LINE PRINTER NUMBER
 C     7 REFERS TO THE WRITE STATEMENT
*       WRITE (6,7)
*     7 FORMAT(13H HELLO, WORLD)
       STOP
       END
```

→  Apparition d'opérations de plus haut niveau, compilé en assembleur

???
## 1950 - Fortran

* Impression d'une phrases sur une sortie standard
* Plus vraiment des mathématique
* Encapsulation d'un comportement

---
## 1958 - Algol

```no-highlight
BEGIN
  FILE F(KIND=REMOTE);
*  EBCDIC ARRAY E[0:11];
  REPLACE E BY "HELLO WORLD!";
  WRITE(F, *, E);
END.
```

→  Utilisation de données typées

???
## 1958 - Algol
*  Utilisation de données typées
*  Abstraction complète de la mémoire
*  Moins de lien avec les mathématiques

---
## Fin des années 60

### Langages structurés autours de nouveaux paradigmes
  - Les langages procéduraux (Pascal, C...)
  - Les langages orientés objet (Simula/SmallTalk)
  - Les langages logiques (Prolog)
  - Les langages fonctionnels (ML, Caml, F#)

???
## Langage structuré :
* Eloignement des mathématiques (calcul des x décimales de PI, balistique...)
* gestion moins physique des informations

* Les GOTO disparaissent (déplacement du pointeur d'instruction)
* Les fonctions prennent de l'importance

---
layout: true
class: center, middle, inverse

---
# Comparons ces paradigmes

???

# L'histoire

---
layout: false
## Langage procédural : Pascal (1970)

```no-highlight
program HelloWorld(output);
begin
writeln ('Hello World');
readln;
end.
```

→ Suppression des GOTO 
→ Suite d'instructions organisées en procédures

???

## Langage procédural : Pascal (1970)

→ L'objectif du programme est d'effectuer une suite d'instruction pour produire des effets

→ Suppression des GOTO 
→ Suite d'instructions organisées en procédures

* Possiiblité de faire des boucles...
* On ne gère pas la mémoire directement (emplacements...)

---
## Langage orienté objet : Simula (1967)

```no-highlight
*Class Rectangle (Width, Height); Real Width, Height;
*                                ! Class with two parameters;
 Begin
    Real Area, Perimeter;       ! Attributes;

Procedure Update;           ! Methods (Can be Virtual);
    Begin
      Area := Width * Height;
      Perimeter := 2*(Width + Height)
    End of Update;

Boolean Procedure IsSquare;
      IsSquare := Width=Height;

Update;                     ! Life of rectangle started at creation;
    OutText("Rectangle created: "); OutFix(Width,2,6);
    OutFix(Height,2,6); OutImage
 End of Rectangle;
```

→ Apparition des objets (classes...) 
→ Les objets proposent des méthodes à appliquer à l'objet

???
## Langage orienté objet : Simula (1967)

* La papy de Java (1995)

→ Objectif : décrire un ensemble d'objet décrivant un modèle et effectuer des opérations pour modifier l'état du modèle (qui représente le modèle).

Par exemple dans DICT.fr, on créé un objet document lorsque l'utilisateur envoie un doc, on lui rattache une objet envoi et on modifie les propriété lorsque les status changent.

* Des objets encapsulent les données qui sont organisées dans des structures complexes
* On appliques des méthodes sur l'objet (différent de on calcule quelque chose avec un objet en entrée)

---
## Langage logique : Prolog (1972)

```no-highlight
mother_child(trude, sally).

father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).

sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).

parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).
```
```no-highlight
*?- sibling(sally, erica).
*Yes
```

→ Programmation complètement déclarative 
→ Enonciation des faits et les règles : les relations entre les objets 
→ Moteur d'interrogation des données

- Utilisé principalement en intelligence artificielle

???
## Langage logique : Prolog (1972)

→ Programmation complètement déclarative (pas d'instructions) 
→ Enonciation des faits et les règles : les relations entre les objets 
→ Moteur d'interrogation des données

- Utilisé principalement en intelligence artificielle
- Un ovni

---
## Langage fonctionnel : ML (1973)

```
fun fact n = let
 fun fac 0 = 1
 | fac n = n * fac (n - 1)
 in
 if (n < 0) then raise Fail "negative argument"
 else fac n
 end
```

→ Langage déclaratif 
→ Pas d'assignation de variables 
→ Récursivité 
→ Fonctions d'ordres supérieur

- Utilisé principalement pour de la recherche théorique

???
## Langage fonctionnel : ML (1973)

ML = MetaLanguage

* Pas de données mutables (pas d'assignations)
* On définit les données plutôt que de spécifier la suite d'insctruction nécessaire à son calcul
* Pas (peu) de boucles, mais de la récursivité (une boucle c'est un compteur mutable)
* Apparition des functions d'odres supérieures, les fonctions de fonctions.

Jusqu'à récemment utilisé principalement pour de la recherche théorique mais ça peut avoir d'autres usages.
Maintenant que Java adopte des patterns fonctionels, ça vaut le coup de regarder de plus près.

Pour info, Java est un language objet qui commence à adopter des patterns fonctionnels
et Scala est un language hybride à la fois fonctionnel et objet.

---
layout: false
class: middle, inverse, bigText

> "La programmation fonctionnelle est un paradigme de programmation qui considère le calcul en tant qu'évaluation de fonctions mathématiques."

Source : [Wikipedia](https://fr.m.wikipedia.org/wiki/Transparence_r%C3%A9f%C3%A9rentielle)

---
layout: false
class: bigText

##Programmation fonctionnelle pure
* Tout est fonction
* Pas d'affectation (mutation de variable)
* Transparence référentielle

???
→ Facilite grandement les tests et la réutilisabilité 
→ Language plus proche des spécifications : on explique ce que ça doit faire, pas comment le faire 
→ Parallélisation plus simple

Mais pas évident pour certains problèmes (gestion d'état...) comme l'informatique de gestion.

##Programmation fonctionnelle impure
* Affectations possibles
* Possibilité de travailler en orienté objet
* Utilisation de programmation impérative et fonctionnelle dans le même language
* Limiter au maximum les effets de bords

???

<hr/>
→ Java 8 
→ Scala

---
layout: true
class: center, middle, inverse, bigText
---
name: functions

#Tout est fonction

???

Voyons quelques grand principes de la programmation fonctionnelle.

---

#C'est quoi une fonction ?
---

#Fonction

> Relation qui, à chaque élément de son ensemble de départ, associe au plus une image.

# x → f(x)

# f : x → (4 × x) + 2

---
layout: false
class: bigText

# Transparence référentielle

> "La transparence référentielle est une propriété des expressions d'un langage de programmation qui fait qu'une expression peut être remplacée par son résultat sans changer le comportement du programme."

Source : [Wikipedia](https://fr.wikipedia.org/wiki/Transparence_r%C3%A9f%C3%A9rentielle)

---
class: bigTex2t

# Transparence référentielle

```java
Si      f = x → g(x) + g(x)
Alors   f = x → 2 × g(x)
```

Sauf si

```java
int n = 2;
int g(int x) {
    n = n + x;
    return n;
}
```

```java
        f¹(3) = g(3) + g(3) = 5 + 8 = 13
        f²(3) = 2 × g(3) = 2 × 5 = 10
```

→ Pas d'effet de bord 
→ Pas d'assignation

???

→ Préfigure CQRS (Command and Query Resposibility Segregation) 
→ Possibilité de faire de l'évaluation lazy (mot clé Scala)

---
#Lazyness

```scala
scala> val x = { println("compute X"); 15 }
compute X
x: Int = 15

scala> lazy val y = { println("compute Y"); 13 }
y: Int = <lazy>

scala> x
res2: Int = 15

scala> y
compute Y
res3: Int = 13

scala> y
res4: Int = 13
```

Source : [Stackoverflow](http://stackoverflow.com/questions/7484928/what-does-a-lazy-val-do)

???

Si on est certain qu'une fonction donnera toujours le même résultat, pas besoin de l'évaluer plusieurs fois, ni de l'évaluer prématurément.

En scala, mot clé lazy obligatoire.

PS : super le REPL en Scala (ça arrive en Java 9)

---
# Stream

Scala :

```scala
scala> val stream = (1 to 100000000).toStream
stream: scala.collection.immutable.Stream[Int] = Stream(1, ?)
```

???
Possibilité de faire une collection de longueur infinie sans saturer la mémoire.
Chaque itération sera évaluée uniquement lorsque nécessaire

? = non évalué

Java :

```java
IntStream.iterate(0, i -> i + 1)
        .limit(10000000)
        .forEach(System.out::println);
```

???

Possible aussi en java

---
# Les fonctions d'ordre supérieur
## En paramètre
Java:
```java
static int maMethode(IntBinaryOperator op){
    return op.applyAsInt(5, 10);
}
```
Scala:
```scala
def maMethode(uneFonction: (int, int) => int) {
    return uneFonction(5,10);
}
```
Javascript:
```javascript
app.get('/', function(req, res) {...});
```

???
Scala : structural Typing (static - à la compilation)  != Duck typing (dynamic - au runtime)

---
# Les fonctions d'ordre supérieur
## En retour
Java:
```java
public IntFunction<int> createAdder(int step){
 IntFunction<int> addFunction = (a) -> {return a+step};
 return addFunction;
}
IntFunction<int> addOne = createAdder(1);
addOne(4) //5
```
Scala:
```scala
def createAdder(step: Integer) = (a: Integer) => {a + step};
val addOne = createAdder(1);
addOne(4)
```
Javascript:
```javascript
function createAdder(step) {
 return function(a){return a+step;}
}
var addOne = createAdder(1);
addOne(4) //5
```

---
# Le currying

Scala:
```scala
def createAdder(step: Integer) = (a: Integer) => {a + step};
val addOne = createAdder(1);
addOne(4)
```

```scala
def createAdder(step: Integer) = (a: Integer) => {a + step};
createAdder(1)(4) //5
```

???

Exemple d'un regex pattern matcher, pour permettre la réutilisation de le regex compilée.
```
Regex.match(".*(\d).*")(toto)
```

---
# La récursivité

```
n! = 1 x 2 x 3 x 4 x .... x n-1 x n
```

Sans récursivité :
```java
int factor = 1;
for (int i=1; i<=number; i++) {
 factor = factor*i;
}```

Avec récursivité :
```scala
def factorial(n: BigInt): BigInt = { 
 if (n <= 1)
 1 
 else 
 n * factorial(n - 1)
}
```

???

Récursivité bien sur possible en java aussi, mais sans tail recursion on finit rapidement avec un stackoverflow.

La tail récursion permet de garder le même contexte (la même stack) dans une boucle de récursion ou l'appel se fait en fin de boucle.

---
layout: true
class: center, middle, inverse, bigText
---
name: types

#Tout est typé

???

Voyons quelques grand principes des languages fonctionnels matures (oui donc pas JS).

---

#C'est quoi un type ?
---

#Type

> Un type définit les valeurs que peut prendre une donnée, ainsi que les opérateurs qui peuvent lui être appliqués.

Source : [Wikipedia](https://fr.wikipedia.org/wiki/Type_%28informatique%29)

---
layout: false

# Les types riches

## Either

```scala
def divideXByY(x: Int, y: Int): Either[String, Int] = {
  if (y == 0) Left("Dude, can't divide by 0")
    else Right(x / y)
}
  
// a few different ways to use Either, Left, and Right
println(divideXByY(1, 0)) // Dude, can't divide by 0
println(divideXByY(1, 1)) // 1
divideXByY(1, 0) match {
  case Left(s) => println("Answer: " + s)
  case Right(i) => println("Answer: " + i)
}
```
???

Exemples sur : https://tersesystems.com/2012/12/27/error-handling-in-scala/

---
# Les types riches

## Option
```scala
def inverse(x: Double): Option[Double] = {
  if (x != 0) {
    Some(1 / x)
  } else {
    None
  }
}
```
???

Comme en Java mais très utilisé. Le NullPointerException n'existe pas.

---
# Les types riches

## Try

```scala
object Test extends App {

def readTextFile(filename: String): Try[List[String]] = {
    Try(Source.fromFile(filename).getLines.toList)
  }

val filename = "/etc/passwd"
  readTextFile(filename) match {
    case Success(lines) => lines.foreach(println)
    case Failure(f) => println(f)
  }
}
```

???

Le Try est executé au moment ou il est nécessaire et géré localement et explicitement.
Pas moyen de ne pas le gérer.
C'est parfois frustrant.

---
# Les structures immuables

```scala
var mutableVar = 1;
mutableVar = 2;

val immutableVar = 1;
immutableVar = 2; //Error
```

???
→ Facilite la parallélisation du programme sur plusieurs CPU

```scala
scala> val vec = Vector(1, 2, 3)
vec: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)
scala> vec updated (2, 4)
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4)
scala> vec
res1: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)
```

???
Source : http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html

---
# Les case class

```scala
case class Livre(titre: String, isbn: String)

val book = Livre("The Hitchhiker's Guide to the Galaxy",42)
println(book.isbn) // 42

val copy = Livre("The Hitchhiker's Guide to the Galaxy",42)
book == copy // true
```

???
Pas de boilerplate
Automatiquement deep-copie, comparaison...

Lombok dans le language.

Voir l'article : http://blog.xebia.fr/wp-content/uploads/2017/04/programmez-206-avril17-2.pdf

---
# Les sealed class

Scala
```scala
sealed trait Color
case object Blue extends Color
case object Red extends Color
```

Scala
```scala
sealed trait Tree
case object Empty extends Tree
case class Node(v: Int, left: Tree, right: Tree) extends Tree
```

???

Devrait arriver avec Java 10, petit copieur

---

# Les sealed class

Scala
```scala
sealed trait Tree
case object Empty extends Tree
case class Node(v: Int, left: Tree, right: Tree) extends Tree
```

Java 10
```java
sealed interface Tree { }
data class Empty() implements Tree {}
data class Node(Int v, Tree left, Tree right) implements Tree {...}
```

---
# Pattern Matching

Java 8
```java
  public int fact(int n) {
    int result;
    if (n == 0) {
      result =  1;
    } else {
      result =  n * fact(n - 1);
    }
    return result;
  }
```

Scala
```scala
  def fact(n: Int): Int = n match {
    case 0 => 1
    case n => n * fact(n - 1)
  }
```

???
Bonne nouvelle ça arrive en Java 10 !

---
# Pattern Matching

Java 10
```java
  public int fact(int n) {
    return exprswitch (n) {
      case 0 -> 1
      case int i -> i * fact(i - 1)
    };
  }
```

Scala
```scala
  def fact(n: Int): Int = n match {
    case 0 => 1
    case n => n * fact(n - 1)
  }
```

???

Petit copieur ce Java...
Source : http://cr.openjdk.java.net/~briangoetz/amber/pattern-match.html

---
# Pattern Matching + sealed class

---
layout: false
class: middle, inverse, bigText

> "Functional programming is expression-oriented programming. A functional program is not a sequence of instructions, but a single, referentially transparent expression. Computation proceeds by substitution."

.small[Source : [Guerrilla Guide to Pure Functional Programming](http://jvmblog.com/post/35474017210/guerrilla-guide-to-pure-functional-programming)]

---
#Comment travailler sans assignations ?

<Insérer quelques exemples>

---
layout: true
class: center, middle, normal

---
#Merci de votre attention

---
layout: false
class: left, middle, normal

# Sources
- ["Programmation Fonctionnelle en HOPE"](http://www.labri.fr/perso/billaud/travaux/hope.pdf) par Michel Billaud
- ["The Guerilla Guide to Functional Programming"](https://docs.google.com/file/d/0B6Pvyu_QqshwYmU1OTg0OGEtMTMwMC00YmQ3LWIxY2MtYzdiMDNiM2QzNjZh/edit?hl=en) par Runar Oli Bjarnason
- ["Functional Programming is the new black"](https://speakerdeck.com/elise_huard/functional-programming-is-the-new-black)  par Elise Huard
- [La page wikipedia sur la programmtion fonctionnelle](http://fr.wikipedia.org/wiki/Programmation_fonctionnelle)
- ["Un article de Xebians dans le Programmez n°206 d'avril 2017"](http://blog.xebia.fr/wp-content/uploads/2017/04/programmez-206-avril17-2.pdf)
- Extraits trouvés sur Internet de _Scala Cookbook: Recipes for Object-Oriented and Functional Programming 1st Edition_ par Alvin Alexander