|<- |[[cours 1]] ->|
====== les langages de programmation ======

===== introduction =====

==== Ce qu'ils sont ====

Langages de programmation servent à exprimer des algorithmes dans un langage **formel** compréhensible **par des machines**. (En opposition à par le passé avant les ordinateur où on les exprimait dans un langage naturel à l'intention des humains). En soi concevoir des algorithmes n'est en effet pas nouveau (<-2500).

Exemple en Égypte, scribes en mésopotamie ne connaissaient pas le théorème de pytagore mais avait un algorithme pas très loin pour calculer l'hypothénuse d'un triangle rectangle → Prendre les côtés → les élever au carré → prendre la racine carré de cela.

Au moment ou on a du passer d'algorithmes exécutés par des humains à des algorithmes exécutés par des humains, le langage pour les exprimer à du changer. Jusqu'au milieu du 20e siècle : pouvaient être exprimés en langage naturel interprétable par des humains, après : langage formel.

Écrire un texte lu par la machine : langage formel. Existant avant l'ordinateur même si bien moins utilisé. Ex : langage musical, grammaire de précision des corrections pour lunettes.

langage formel != langage de programmation

HTML : langage formel de description de document mais pas de programmation car ne permet pas de décrire des algorithmes.

Double contrainte :
  - langage lisible par une machine (cela en fait un langage formel)
  - doit également être lisible par un être humain

L'histoire de la programmation c'est comment on est passé de langage bas-niveau à haut-niveau, se rapprochant du langage naturel.

Note : Haut et bas niveau : selon le degré de rapprochement/éloignement du langage naturel.

Programme de quelques lignes à des millions. Avant la programmation objets constitués de beaucoup moins d'élément -> avec, saut dans la complexité

==== principes communs ====

+ de 2000

Organisés autour de principes communs : affectation, boucle, cellule, passage par référence

Note perso : et les paradigmes ?

Langues naturelles : article, pronom, verbe, temps, mode, aspect, conjugaison, déclinaison

"Quand il y a un nouveau langage que vous devez apprendre, vous posez tout de suite les bonnes questions, comment est-ce qu'on fait une affectation, comment est-ce qu'on fait une boucle, comment on alloue une cellule, une fois que vous avez compris tout ça vous avez déjà une bonne compréhension du langage de programmation, il vous reste plus qu'à vous concentrer peut-être sur certaines spécificités de ce langage là par rapport à d'autre"

"Le but d'un court comme celui-là n'est pas de comprendre les idiotismes de Java ou Caml, **idiotisme veut dire particularité**, c'est de comprendre les principes autours desquels ces langages sont organisés, et pour cela apprendre un seul langage ne suffit pas. Par exemple si vous n'apprenez que Java, vous ne serez pas capable de voir quels sont les idiotismes de Java et quels sont les principes universels réalisés dans Java." Obligatoire de comparer pour dégager les principes universels (il ne s'agit pas non plus de savoir programmer dans différents langages à la fin du cours, un peu comme en grammaire comparée ou l'on compare plein de langues sans les parler).

===== objectifs =====

  * Apprendre à programmer en **Java**
  * Comprendre les **principes** (comparaison avec Caml et C)
  * Commencer à apprendre les outils qui permettent de décrire la **signification** des programmes
  * Apprendre les **algorithmes de base** sur les listes, les arbres et les tableaux

===== Le noyau impératif =====

==== Qu'est-ce ? ====

Un ensemble de construction qu'on retrouve dans quasiment tous les langages de programmation :

  * l'affectation
  * la déclaration de variable
  * la séquence
  * le test
  * la boucle

==== l'affectation ====

=== forme générale ===

<code>x = t;
x = 3 + y</code>

**x** variable et **t** expression

variable : un mot d'une ou plusieurs lettre (n: je trouve ça vraiment pas top comme définition !)

expression : formée à partir des constantes et des variables avec des opérations (+,-,*,/,%,…)

<code>
//Caml
x := 3 + !y // voir plus loin pour le !
// C : comme en Java
</code>

Ce qu'il se passe quand on exécute x = t;

On met la **valeur** de **t** dans cette case

La valeur antérieur est oubliée

Expressions : 3, 5 + 3, y + 3
Valeurs (nombres entiers) : 3, 8, 10
État: ensemble des valeurs des variables à un instant donné (contre-proposition : ensemble des valeurs en mémoire à un instant donné).

=== la déclaration de variable ===

Fait un exemple avec des boites sorties pour l'affectation en disant qu'il aurait faut avant d'assigner, mettre les boites sur la table, le déclaration.

Assignation : sortir la boite et lui associer un nom.

Avant de pouvoir utiliser la variable x, il faut la déclarer.

Associer le nom x à une des cases de la mémoire

<code>
{int x = t; p}
{int x = 5; x = 3 + y;}
</code>

Expression t : valeur initale (optionnelle)
Instruction p : portée de la variable x

En Caml: let x = ref 5 in p
En C : comme en Java

Une boite n'est jamais vide

**int** : nombres entiers compris entre -2^31 et 2^31 -1

Outre **int**, trois autres intervalles **byte**(2^12 possibilités),**short**(2^32),**long**(2^64)

Autres types :
  * **booleans** (false, true)
  * flottants: **float** (nombres à virgule)
  * caractères **char**(**'g'**)

Donc :
  * huit **types primitifs** : en java 4 pour les entiers, 2 pour les flottants, 1 pour les booléens, 1 pour les caractères
  * types composites (à suivre) : **String**(**"Bonjour"**)

**{T x = t; p}**

**Quand on aborde un nouveau langage de programmation, un des trucs que l'on doit comprendre, c'est quels sont les types primitifs**.


===Les variables finales et les variables mutables===

Une autre précision qu'on peut donner quand on va déclarer une variable, c'est la déclarer comme finale, c'est à dire en s'engageant à ne jamais l'affecter.

déclaration d'une variable, engagement à ne jamais l'affecter

**{final T x - 5; p}**

**final int x = 5; y = x + 3;}**

**final int x = 5; x = 3;}** incorrecte

Variable non finale : mutable

En Caml **let x = 5 in p** et non **let x = ref 5 in p**

**y := x + 3** et non **y := !x + 3** quand **x** est finale

En C, **const** au lieu de **final**.

Je cite : « En français ça s'appelle une constante ça s'appelle pas une variable finale » **MERCI ALBERT**

==== la séquence ====

La construction la plus simple des langages de programmation

**{p1 p2}**

**{x = 1; y = x + 1;}**

Quand on exécute cette instruction, on exécute p1 puis p2

En Caml: **p1; p2**

En C : comme en Java

==== le test ====

if (b) p1 else p2

if (x < 0) y = -1; else y = 1;

quand on exécute cette instruction, on calcule la valeur de **b**.

Si c'est **true** on exécute **p1** si c'est **false** on exécute p2.

En Caml: **if b them p1 else p2**

En C : comme en Java

==== la boucle ====

**while (b) p**

**while (x < 1000) x = x * 2;**

Quand on exécute cette instruction : on calcule la valeur de b, si c'est false on a terminé, si c'est true, on exécute p et on recommence.

Notation finie pour une instruction infinie.

en Caml : **while b do p;** En C : comme en Java.

==== les instruction d'entrée et de sortie en java ====

=== sortie ===

systel.out.print(x); // Écrire x

systel.out.println(); // retour chariot, revenir à la ligne

systel.out.println(x); // les deux

=== entrée ===

En Java c'est complexe parce que la technique est devenu complexe (plus juste lire le clavier mais des fluxs sur réseaux complexes)

Ppl.lireInt (); // outil dev pour polytech et ses étudiants

==== Le fonction ∑ ====

liaison tardive ?

Ce qui se passe quand on exécute l'instruction i

**x = t;** : « On met la valeur de **t** dans la case **x** »

Description en langue naturelle rapidement complexe et confuse (déjà : **while**)

On finit par donner des exemples (… qui couvrent des cas simples)

  * **comment écrire un interpréteur / compilateur ?**
  * **comment raisonner à propos d'un programme ?**
  * **comment analyser automatiquement un programme ?**

Nécéssité d'une description mathématique du langage pour évacuer les ambiguités.

=== L'état ===

Ensemble des valeurs des variables à un instant donné

Ensemble infini Var dont les éléments sont appelés **variables**

ensemble Val : [-2^32, 2^31 -1} W {False, true} W …

Un **état** est une fonction d'une partie finir de **Var** dans **Val**

e.g. : [x = 1, y = 4]

attention : pas 1 = x

exécuter une instruction : transformer l'état.

La signification des instructions d'un langage est définie par une fonction ∑ :

**∑(i,s) = s'**

e.g. : ∑( x = 3; , [x = 1, y = 4] ) = [x = 3,y = 4]

Ici i *(x = 3)* est appliqué à s *[x = 1, y = 4]* et donne *[x = 3,y = 4]*

=== La décomposition de l'état ===

Utile pour plus tard : (illisible) s = m o e ???, l'environnement et la mémoire

{{ :livres:principes_des_langages_de_programmation:capture_d_e_cran_2016-07-13_a_13.24.23.png |}}

Ensemble intermédiaire **Ref** des références

**∑(i,e,m) = m'**

∑( x = 3; , [x = r1, y = r2], [r1 = 1, r2 = 4] ) = [r1 = 3,r2 = 4]

Décomposé de deux fonction, une première qui a une variable associe une référence, et une deuxième qui associe une référence à une valeur.

Exemple, s'il fait 14° à Paris, quel température de la capitale de la France ? La même car « Paris » et « capitale de la France » font référence au même objet.

Environnement, Mémoire : l'exécution d'une instruction ne change jamais l'environnement, elle ne change que la mémoire. Très important car l'environnement dégage à la compilation, ne reste que la mémoire au moment de l'exécution.

<code>
┏━━┓┏━━┓
┃ a ┃┃ x  ┃ identificateurs
┗━━┛┗━━┛
┏━━━━━┓
┃ ┏━┓  ┃
┃ ┃ 3┃  ┃ valeur (3) dans boite
┃ ┗━┛  ┃
┗━━━━━┛

Boite = référence

Environnement = mettre nom (identificateur à la boite)

Mémoire = mettre valeur dans la boite

état = boite + nom + valeur
</code>

== cas des variables finales ==

final int x = 3; p

au lieu d'associer **x** à **r** dans **e** et **r** à **3** dans **m**

on associe **x** à **3** dans **e** (la mémoire est ce qui peut changer)

Ref ⊆ Val

{{ :livres:principes_des_langages_de_programmation:capture_d_e_cran_2016-07-13_a_14.42.54.png |}}

« L'environnement ne change pas, la mémoire c'est ce qui change lors de l'exécution du programme, du coup je veux associer la valeur 3 à x dans e, j'veux qu'ça soit dans l'environnement, pas une boite dans la mémoire (…) l'environnement associe à une référence, ou bien à une valeur »

Les références se sont des valeurs comme les autres : Ref ⊆ Val

du coup les références c'est un sous-ensemble des valeurs comme sur schéma ci-dessous :

{{ :livres:principes_des_langages_de_programmation:capture_d_e_cran_2016-07-13_a_14.42.54.png |}}

Comme une variable finale/constante ne voit pas son identificateur lié à différentes valeurs on associe directement et définitivement les deux.

=== La valeur d'une expression en Caml et en C ===

**x = t;**

« On met la valeur de **t** dans la case **x** »

  - Θ (n,e,m) = n
  - Θ (n,e,m) = m(e(x)) si x est mutable
  - Θ (n,e,m) = e(x) si x est finale
  - Θ (t + u,e,m) = Θ(t,e,m) + Θ(u,e,m)
  - idem pour les autres opérations

Caml : 

  - Θ (n,e,m) = (x)

Que x soit finale ou mutable

  - Θ (!t,e,m) = m(Θ(t,e,m))

x + 1 en Java, **!**x + 1  en Caml

C : comme Java

=== L'éxécution dune instruction : la déclaration et l'affectation

la ????m + (r - v) coîncide avec m sauf en r ou elle vaut v

(pas continué à prendre note dès -16:19)