Les expressions régulières.

Expressions régulières.

Une petite digression sur les expressions régulières, aussi appelées expressions rationnelles ou regex..
Les expressions régulières correspondent à un mini langage bien spécifique qui est le langage des automates. Ici automate  est utilisé au sens mathématique  du terme. Dans un "automate fini déterministe", un mot u est reconnu si il fait passer l'automate d'un état initial à son état final.
Les expressions régulières sont utilisées en programmation pour reconnaître des motifs particuliers. Ainsi  les mots "unix" et "linux" sont reconnus par un automate dont le langage est  "*n.x" . "*n.x" est une expression régulière.

Construction d'expressions régulières:

en ligne: var regex = /test/igm ;
à l'aide d'un constructeur: var regex = new RegExp("test","igm");

En pratique 6 méthodes javascript permettent d'utiliser les expressions régulières

- 2 sont des méthodes de l'objet Regexp exec et test:

var regex = /t(r+)/ig ; // objet RegExp
regex.exec("Do it or not but there is no try"/* optionnel: , ig */);
regex.test("Try it or not");//true or false

- 4 sont des méthodes de l'objet String: match, search, replace, split.

str.match(regex);
str.search(regex);// retourne un entier
str.replace(regex,replacement ); // replacement un entier ou une fonction..
str.split(regex);// renvoi une liste.

En pratique de nombreux sites expliquent la formation d'une expression régulière, c'est un outil très puissant en programmation car il permet de selectionner rapidement et avec précision des éléments donnés dans un texte.

Ce qui est un peu plus intéressant est la notion d'alphabet et d'automate qui est à la base des moteurs d'expressions régulières. Bien sûr, il est probable que les implémentations de javascript utilisent une bibliothèque C d'expressions régulières.

Automate fini déterministe:

Un AFD définit sur un alphabet A de la manière suivante:
{Q, q0 , F, delta}
Q : est l'ensemble fini des états de l'automate.
q0: est l'état initial de l'automate.
F: est l'ensemble des états finals. F est inclus dans Q .
delta : est une fonction de transition de Q*A -> Q, telle que delta(q,c)-> q'
ou encore qui permet de passer d'un état q à un état q' lors de la lecture du caractère c.

Programmation d'un automate fini déterministe en javascript:

//Objet AFD, si on se contente de numéroter les états de l'automate:
var alpha ={ initial, final, transitions }
//où initial est un entier, 
//final est la liste des états finaux, 
//transitions est une liste de tableaux associatifs

Exemple de lecture d'un mot .

function calcul(alpha, q, mot){
 var n= mot.length;
 function avancer(q,i){
  if(i==n)return q ;
  if(typeof alpha.transitions[i])[mot[i]] =="undefined" ) throw "blocage";
  avancer( (alpha.transitions[i])[mot[i]] , i+1); 
 }
}
//exemple automate à 3 états, 0->1->2
// alphabet a,b 
var alpha ={
 initial: 0, 
 finals: [2], 
[{a:1, b:0},{a:0,b:2},{a:1, :b:2}]
}

Exercice: Tracez le schéma de cet automate et trouvez les mots qu'il reconnait en sachant que sont état final est l'état 2 et l'état initial l'état 0.

Réponse:
/b*a(aa)*b+(ab+)*/

Tié puissant mon fils!

Paradigme diviser pour régner

Pour continuer sur la voie de la récursion et de l'algorithmique, une petite illustration du principe de Machiavel "Diviser pour régner" ou encore en anglais "Divide and Conquer"...
Comment calculer la puissance n de x ?
Je vois tout de suite les malins qui répondent qu'il y a une fonction toute prête x^n ! Oui mais comment peut-on le faire sans cette fonction.
Première solution, naïve :

var pow = function(x,n){ return n==1 && x || x * pow(n-1,x) ;}
pow(2,10);// 1024

Mais si on réfléchit, il faut faire n calculs pour obtenir le résultat, y a-t-il une solution pour effectuer moins de calculs?
Evidemment la solution c'est diviser pour régner..

var power = function(x,n){
if(n ==1 ) return x ;
 if(n%2 ==0){ 
  var powbis = power(x,n/2) ;
  return powbis * powbis;
 }
 else{
  var powpair = power(x, n-1) ;
  return x * powpair
 }
}

Dans cette solution pour faire:
power(2,10), on calcul d'abord power(2,5)* power(2,5) puis
power(2,5) est obtenu en calculant x*power(2,4) ;
power(2,4) est obtenu en calculant power(2,2) * power(2,2 ) ;
power(2,2) est obtenu en calculant power(2,1) * power(2,1) ;
On a donc effectué 5 calculs, là où la solution naïve aurait effectué 10 calculs.
D'accord, c'est pas un super génial, surtout pour le calcul de puissance qui pourrait être encore optimisé. Cette solution illustre le principe et montre qu'il ne faut pas se jeter immédiatement sur la solution naïve d'un problème. En pratique, utilisez l'opérateur ^, qui est probablement très optimisé.

Javascript récursif, suite

Suite de Fibonacci:

La suite de fibonacci a été étudiée par le grand Léonard de Vinci... est définie ainsi:

f(0) = 0 , f(1)= 1  et f( et  f(n)= f(n-1)+f(n-2) ;

Programmez cette suite..
Vous avez probablement écrit l'algorithme naïf:

function fibo(n){ return (n<2) ? n : (fibo(n-1)+ fibo(n-2)); }
fibo(10);

Or cet algorithme recalcule à chaque fois fibo et ne met pas en mémoire les résultats précédents: une solution plus efficace consiste garder en mémoire les deux précédents résultats et de les échanger à l'aide des arguments d'appel de la fonction:

// avec une cloture:
function fib(n){
    if(n<=1) return n;
    function f(p , pp){
        n--;
        return (n==0)? pp : f(p+pp, p);
     }
    return f(1,1);
}

ou encore:

function fib(n){
    function f(p ,pp,n){
        return (n<=2)? p :f(p+pp, p ,--n);
     }
    return f(1,1,n);
}
//ici la récursion utilise les arguments pour obtenir le résultat final, 
// et n est incrémenté à la façon d'une boucle for.

Les accros du récursif pourront peut-être écrire:

function fibo(n){
    var f0=0, f1=1 , f ;
    if(n<2) return n ;
    for(i=2 ; i  <= n ; i++){
        f=f1 +f0 ;
        f0 =f1 ;
        f1 =f ;
    }
    return f;
}

fibo(10);

Programmation dynamique et clôture en javascript

Douglas Crockford propose dans son livre une version utilisant la programmation dynamique avec un tableau dans une "cloture" (en anglais "closure"), il nomme cette technique la "memoization"...

// Le but: f(0) = 0 , f(1)= 1  et f(n)= f(n-1)+f(n-2) ;

var fibodougcrock = function(){
   var memo =[0,1] ; // variable cloturée = inaccessible hors de la fonction.
   var fibo = function(n){
                      if(n<2) return n ;
                      if(memo[n]) return memo[n];
                      memo[n]= fibo(n-1) + fibo(n-2) ;
                      return memo[n] ;
   }
   return fibo ;
}

var myFibo = fibodougcrock() ;
myFibo(20); 

L'intérêt de cette dernière version est son caractère dynamique les calculs précédents sont mis en mémoire, de façon à ne faire qu'une fois le calcul pour chaque n. Cela coûte un peu de mémoire mais rend le calcul possible.
Par ailleurs, le tableau memo est une variable cloturée ( closure en anglais), cette variable ne peut être modifiée que par la fonction elle même, elle n'est pas atteignable par le code javascript, elle est donc protégée et isolée dans sa fonction. Mais, d'autre part, elle réserve la mémoire pour le tableau mémo dans son enclos, qui ne sera pas libérée tant qu'il y aura des références à fibodougcrock dans le programme.
Les clôtures sont intéressantes en javascript car elles permettent l'encapsulation des données, notion si chère aux programmeurs objets. Mais elles sont aussi dangereuses, car il est possible de créer des clôtures sans le savoir avec une fuite de mémoire...Il est donc plus important de les reconnaître que de les utiliser.

Recursion suite: Algorithme d'Euclide et Tours de Hanoi

Algorithme d'Euclide:

L'algorithme d' Euclide permet de déterminer le pgcd de la manière suivante:
- pgcd(a, a) = a,
- pgcd(a, b) = pgcd(a − b, b) si a > b ou pgcd(a, b − a) si a

Programmez l'algorithme d'Euclide de façon récursive.
Nota bene une autre méthode pour calculer l'algorithme d'Euclide est l'opérateur modulo "%"
pgcd (a,b) = b si a%b == 0 , ou sinon (a%b) % b ;

function pgcd(a,b){
 return  a>b && pgcd(a-b, b)|| a<b && pgcd(a,b-a) || a===b && a ; 
}
//Et avec l'opérateur modulo :
function pgcd(a,b){      
   return  a>b && a%b>0 && pgcd(b,a%b) || (b>a)&& pgcd(b,a) || a%b===0 && b ;
}
pgcd(2736,486144);//30

Ici on utilise volontairement les expressions javascripts pour raccourcir l'écriture, ce qui n'est pas forcément toujours à conseiller. Pour les matheux, un problème plus complexe est de calculer les coefficients de Bezout, Ces coefficients sont très utiles dans le cryptage des données.

Tours de Hanoi :

Voici (enfin) l'incontournable problème qui illustre la récursivité, ce problème a été inventé au début du siècle par un mathématicien français afin d'illustrer la résolution d'un problème par récursivité.
Attention, essayez de comprendre ce problème et sa solution... c'est un problème fondamental, il vous permettra de comprendre les autres solutions par récurrence même si vous avez étudié la récurrence dans vos études !
Dans un temple bouddhiste, à Hanoi 3 mâts sont disposés en ligne l'un à côté de l'autre. Sur le mât de gauche sont empilés des disques d'or très lourds, percés au centre, de diamètre variable, et ordonnés du plus grand au plus petit.
Un moine est chargé de transférer ces disques sur le troisième piquet à droite, avec cependant un impératif: il ne doit jamais déposer un disque d'un diamètre supérieur aux disques précédents sur un mât donné.
La légende dit que la fin du monde surviendra lorsque le moine aura terminé son travail...
Pouvez vous programmer un mode d'emploi pour aider notre moine dans sa tache interminable ? Il faut écrire un programme qui donne
hanoi( ndisques, "gauche", "droite", "milieu")
qui permet à notre moine de savoir de transférer ndisques de gauche à droite, en s'aidant du mât du milieu .

Réponse:
Le principe de récurrence dit que si vous pouvez le faire pour 1 élément et si vous savez passer de l'élément n à n-1 alors vous savez résoudre le problème ! ....
Ainsi on suppose que vous savez passer une colonne de n-1 disques de gauche au milieu ou à droite.. comment passer une colonne de n disques de gauche à droite :
passer une colonne entière de n-1 disques de gauche au milieu, // vous prétendez que vous savez le faire
passer le disque large de la base de gauche à droite // vous savez le faire pour de bon !
puis repasser la colonne de n-1 disques du milieu à gauche... // vous prétendez savoir le faire

var r=[];  // le résultat sera dans un tableau .
function hanoi (n,g,d,m){
    if(n==0) return r ;
    hanoi(n-1, g,m,d);
    r.push( "Faire passer le disque de " + g  + " à   " + d );
    hanoi(n-1,m,d,g) ;
 }
hanoi(10,'Gauche', 'Droite', 'Milieu') ;
r ;

Le programme des tours de Hanoi, n'est pas un simple jeu ni un puzzle, c'est l'illustration même de la récursivité. Votre travail ici est de passer de n disques à n-1 disques , d'une part et d'autre part de savoir quand cela doit s'arrêter, ici lorsqu'il n'y a plus de disque à déplacer. C'est tout .
Prenez donc le temps de comprendre ce programme il vous permettra de comprendre la magie de la récursion. C'est particulièrement utiles dans les programmes du type anagrammes ou comptage des parties d'un ensemble.

Fonctions en javascript

Particularité des Fonctions:

Les fonctions sont des éléments de "première classe", une fonction est un type comme un autre, on peut donc l'échanger à l'aide de son nom ou la retourner.
Pour l'exécuter il faudra utiliser l'opérateur double parenthèse ( ) avec éventuellement des arguments à l'intérieur, on peut ainsi écrire:

var hello = function(){ return "hello";} 
div.onclick = hello ; 

Ainsi la fonction hello sera exécutée seulement lors du clic de la souris sur l'élément div. Mais la variable hello, du type fonction, peut être manipulée comme toute autre variable. En fait ici on assigne à la variable "hello" une fonction anonyme .
Attention, le mot clé var permet de désigner la portée de la variable déclarée, ainsi si hello est déclarée à l'intérieur d'une autre fonction, elle ne sera pas accessible hors de cette fonction, d'où l'intérêt de cette notation. Si var est omis, alors la portée devient globale même à l'intérieur d'une fonction. Si vous scriptez une page web, le contexte global correspond à l'objet window.
On peut également écrire les fonctions façon java:

function hello(){ return "hello" ;} // comme en java ou php

L'inconvénient ici c'est que la fonction risque d'être écrite dans un contexte global, ce qui doit être banni car il y a risque de collision avec d'autres variables importées par d'autres scripts.
Il existe en outre une façon spéciale de construire une fonction en utilisant le mot clé Function et du constructeur "new" :

var add = new Function("x", "y", "return x+y") ;
add('Hello ', 'World' );// "Hello World"

Dans cette dernière syntaxe, le dernier argument de "Function " est le type retourné. Une des utilisation possible de Function est de décoder des objets transmis suivant la notation JSON par exemple:

var monobjet = "{ langage: 'java' , annee: 1995} " ;// un objet javascript au format JSON.
var obj = Function( "return "+ monobjet)() ;// remarquez l'exécution à l'aide de () ;
obj.annee; //1995

On peut également créer une fonction anonyme et l'exécuter immédiatement à l'aide de l'opérateur () ce qui permet à l'interpréteur javascript de ne pas la garder en mémoire :

(function(){ return "hello world";})() // la fonction est anonyme, elle est exécutée immédiatement.

Une dernière variante consiste à nommer une fonction anonyme qui devient moins anonyme mais ce qui permet de l'appeler récursivement :

(function facto (n){    if (n == 1) return 1 ;
else return n* facto(n-1) ;})(5) ; // 5*4*3*2*1= 120 

Valeur retournée par une fonction le mot clé "return " :

Si le mot clé "return" est oublié la fonction retourne par défaut : "undefined".
Par ailleurs il existe des erreurs de conception du langage, ainsi on peut écrire:

if( a==2) return true ; else return false ; //correct

ou

return (a==2)? true : false ; //équivalent

mais pas:

(a==2)? return true: return false; // erreur

ni

(return a==2 || return false) ; // erreur écrire: return (a==2 || 'false' )

En effet l'instruction "return ..." n'est pas évaluée ce qui empêche ce genre d'idiome très utilisé en Perl.

Séparateur de ligne le point-virgule facultatif ; :

Il faut également faire attention au caractère facultatif du point virgule, javascript remplace un retour à la ligne par un point virgule, dans ce cas:

return
true

retourne "undefined" car il est interprété comme return; true ;

Arguments des fonctions, methodes apply et call :

Lors de la définition des fonctions, il est habituel de désigner les arguments de fonctions dans la double parenthèse, or il faut savoir que ces arguments sont facultatifs et qu'ils sont repris par javascript dans un tableau spécial toujours disponible nommé arguments,

function somme(){
var resultat=0 ;
for(var i=0; iresultat += arguments[i] ;
return resultat ;
}
somme(1,3,4); // 8

Attention! Ce tableau arguments, par erreur de conception du langage n'est pas un vrai tableau et il sera parfois nécessaire de le transformer en véritable tableau, en le dupliquant et en utilisant la méthode nouveauTableau = Array.slice(arguments) ;

Apply et call :

On peut parfois appeler une fonction par apply ou call de cette façon:

somme.apply(this, [1,3,4]);
var maximum = Math.max.apply(this,[5,3,10,5]);
var monTableau = [1,4,42,10,7] ;
var maximum = Math.max.apply(null,monTableau);
maximum ; //42

• le premier argument de correspond à l'objet sur lequel est appelé la fonction.
  
• le second argument est un tableau.

On peut également utiliser call, on écrit alors:

somme.call(this, 1,3,4) ; // identique à somme(1,3,4)

Nous avons donc vu ici plusieurs méthodes pour créer une fonction dans un contexte différent des objets .
Le problème du mot clé "return" qui peut être omis.
La variable cachée arguments et les méthodes "apply et call" pour utiliser un nombre indéfini d'arguments.
On voit donc que l'écriture classique des fonctions javascript façon java est le résultat d'un
camouflage de variable et de méthodes.

Les six types en javascript

Javascript est un langage très peu typé avec seulement 6 types:

1. "boolean",
   
2. "number",
   
3. "string" ,
   
4. "object" ,
   
5. "function" ,
   
6. "undefined" .

Ces types peuvent être mis en évidence par l'opérateur unaire (un seul argument) typeof, l'opérateur double parenthèse ( ) après typeof est facultatif.
Voici quelques exemples dans la console Firebug:

>>> typeof(1==2); // "boolean"
>>> typeof 'hello'; //"string"
>>> typeof({reel: 3, imaginaire:1}); //"object"
>>> typeof [1,3,4] //"object"
>>> typeof (alert) //"function"
>>> typeof(5); ///"number"
>>> typeof(function(){return 0}); //"function"
>>> typeof(variable_inconnue); //"undefined"
>>> typeof null ; // "object" !! le type null c'est à dire rien est "object"!
>>> typeof typeof ; // erreur !



Attention :
Il est remarquable que le type "null" est considéré comme un objet alors que lorsqu'une variable est inconnu elle prend la valeur "undefined".

Conversion des types renvoyés par les opérateurs booléens:

Le typage est très particulier et se fait à la volée ainsi un "booléen" devient "number" voire "string " ou "objet" lorsque les précédents éléments sont évalués vrais.

>>> 1==1&&2 ; //2
>>> 1==2||3||4==4 ; // 3 : premier élément vrai retrouvé
>>> typeof(1==1&&2); //"number" 2
>>> typeof !!1 ; //"boolean" traduit un entier en booléen



Les valeurs fausses ou "faussées" :

Certaines valeurs renvoient false, "falsy values ":

1. 0 ,
2. "" ,
3. NaN,
   
4. null et
   
5. undefined.

Et toutes les autres valeurs sont considérées comme vrai.

if(0){ true; }else{ false;} // false;
"hello" && true ; // true;


Expressions idiomatiques et usages en javascript:

Ainsi, pour comprendre les expressions javascript il faut étudier le type retourné par une expression booléenne.
L'évaluation paresseuse du "ou" || fait que le premier élément renvoyé est le premier élément vrai.

Ainsi on trouve des lignes de code ressemblant à cela :
return a||"non trouvé" ; qui permet de renvoyer l'élément a s'il existe..



Problème de l'opérateur == :

L'opérateur double égal provoque une contrainte de type (en anglais "type coercion" ) ainsi on obtient des résultats étonnants avec l'utilisation de cet opérateur :
1 == true ; // true !
false==0 ; // true!

Ainsi l'opérateur = = risque de transformer le type et de poser des problèmes de débuggage inattendus ! Le même problème se pose avec l'opérateur !=
Douglas Crockford propose de bannir cet opérateur et d'utiliser l'opérateur triple égal qui réalise une véritable comparaison booléenne :

false === 0 ; // false ;
1=== true ; // false