Algorithmes fonctionnels en javascript sous la forme de cours et d'exercices. Utilisation de js dans un contexte de liste, de map, list_it. Inspiré de caml. A lire à l'envers...

mardi 9 septembre 2008

Listes et pseudo listes en javascript.

Nous avons vu qu'un tableau en javascript a une longueur variable et qu'il existe des fonctions pour retirer le dernier élément du tableau ( pop) ou le premier élément (unshift). Nous avons choisi d'utiliser plus souvent pop car cette fonction ne fait que diminuer la taille du tableau sans avoir à re-numéroter chaque élément du tableau, comme l'aurait imposé un shift.
On peut donc considérer qu'un tableau se comporte comme une liste....
Mais qu'est-ce qu'une liste ? : C'est une collection d'éléments qui s'empilent les uns dernières les autres et dont ont peut en enlever qu'un seul à la fois. C'est donc une pile, à l'image d'une pile d'assiettes, la dernière assiette empilée, sera la première assiette extraite (Last in, first out ) ou LIFO. L'autre variante de structure de données étant la file d'attente: le premier entré sera le premier sortie (First In, First Out) FIFO .Cette structure pourrait être obtenue à l'aide des fonctions shift/ unshift.

Traitement des listes:


Tester si un élément est présent dans une liste.



// Méthode récursive:
function exists (liste, e){
return (liste.length===0)? false: e===liste.pop() || exists(liste,e) ;
}
// Attention exists récursive consomme la liste !

Méthode itérative:

function exists (liste, e){
for(var i=0; i< liste.length; i++)
if(liste[i]==e) return true ;
return false;
}

Une façon élégante est d'utiliser apply (ou list-it du caml ) vu précédemment:

function apply(f, l, n){
for(var i=0; i< l.length ; i++){ n= f( l[i], n ); }
return n;
}
// ici on peut alors écrire:
var exists = function(l,e){
return apply( function(element, boolean){ return (element===e || boolean) ; }, l, false ) ;
};

Union de listes


Comment faire l'union de deux listes ? C'est à dire tous les éléments de deux listes, sans répéter les éléments présents dans l'une et l'autre des deux listes ?

//union [1;2;3;3;4] [2;3;4;5;5] récursive :

function union(l1,l2){
if (l2.length ===0) return l1;
var e = l2.pop();
return exists(l1,e) ? union(l1,l2): union(l1.push(e),l2);
}
union([1,2,3,4], [2,3,4,5,5]); //[1, 2, 3, 4, 5]

Retrait d'un ou plusieurs éléments d'une liste


Comment retirer un élément d'une liste ?
Méthode récursive:

function retrait(l, e){
if(l.length == 0) return [];
var c = l.pop();
if( e===c) return l ;
var lb=retrait(l,e);
return lb.push(c) && lb; // lb.push(c) renvoie la longueur de la liste, donc on renvoi la liste.
}
retrait([1,3,4,5],4);

retrait itératif: utilisation de la fonction splice:

function retrait(l,e){
for(var i=0; i< l.length; i++){
if(l[i]==e)
l.splice(i,1); // retire en position i la longueur l ;
}
return l;
}
retrait([1,2,3,4,5],3);//[1, 2, 4, 5]

Idem à l'aide de la fonctionnelle apply :

function retrait(liste, e) {
return apply(
function(element, liste){
return element===e ? liste:(liste.push(element) &&liste) ;
}
, liste , [] );
}
retrait([1,3,6,7] , 3) ; // [1,6,7]

Filtrer suivant un prédicat: sélectionner les éléments correspondant à un prédicat dans une liste.



// filtrer selon un prédicat en mode récursif:
function filtre(pred,l){
if( l.length ===0) return [];
var e = l.pop();
if( !pred(l.pop()) )
return filtre(pred,l);
var suite = filtre(pred,l); // recursion ici
return suite.push(e) && suite;
}

filtre(function(e){ return e>3 ; },[2,3,4,3,5]) ;



Note sur la syntaxe liste.push(element) && liste .


Normalement liste.push renvoi la longueur de la nouvelle liste, ce qui semble plutôt inutile. D'où cette syntaxe javascript qui
permet de renvoyer la liste après concaténation.

Décomposition d'un entier

Aplatir une liste:


Parfois il est utile de réduire un tableau contenant soit des tableaux soit des éléments, par un tableau simple ne contenant que des éléments.

// Fonction flatten:
function flatten(a,r){
if(a.length == 0) return r;
var cur= a.shift();
cur instanceof Array && flatten(cur,r) || r.push(cur) ;
return flatten( a, r);
}
flatten([1,3,4,[5,6]],[]);
// En évitant d'initialiser le tableau à []:


Décomposition d'un entier:


Savez vous combien de façons existe-t-il d'écrire une addition dont le résultat est 5 ?
[11111], [1112],[1,2,2],[3,2],[11,3],[1,4],[5] : 7

D'une façon général, utilisez la récursion pour calculer le nombre de façons d'écrire un nombre ?

Indice :
Pour écrire une addition dont la somme est n, à l'aide d'un entier inférieur à q, on peut écrire alors
n = q +(n-q) ;
Il y aura donc (n-q) décompositions possibles pour écrire les décompositions dont au moins un élément est de valeur q et les autres de valeur inférieure à q.
On peut également dire que pour avoir toutes les décompositions de n avec des éléments dont la valeur est inférieure à q; il faut rajouter toutes les décompositions de n avec un élément de valeur q-1;

On peut donc écrire
toutesDec(n,q)= toutesDec(n,q-1)+ toutesDec(n-q,q) ;
Par ailleurs,

  • il n'existe qu'une décomposition de n avec q=1

  • 0 décompositions avec q<=0 ou n<0 ;

  • On suppose également qu'il n'y a qu'une décomposition de n=0 avec q>0 correspondant au cas de la décomposition de n par lui meme; exemple ttes Dec(0,5) = 1 car cela correspond au cas ou= toutesDec(n-q,q) ou n=q ,


Réponse:

function toutesDec(n,q){
if(n==0) return 1;
if(n<=0 || q<=0) return 0;
if(q==1) return 1;
return toutesDec(n,q-1)+toutesDec(n-q, q) ;
}

toutesDec( 12,12) ; //77



On peut aller plus loin en écrivant ces décompositions:
Attention ne lisez pas tout de suite la solution... c'est quand même pas super simple !
Un truc important js n'est pas typé, donc pensez type à chaque retour de valeur, dans ma solution, chaque valeur retournée correspond à un tableau de tableaux ou plutôt une liste de listes.

// instructions de débuggage:
function clear(){document.body.innerHTML="";}
function d(m){ document.body.innerHTML += '
'+m.toString()+'
' ;}

function toutesDec(n,q){
if(n&tl;q) return toutesDec(n,n);
if(n <= 0 || q <= 0 ) return [[]];
if(q==1){
var r= [];
for(var i=0; i < n;i++) r.push(1);
return [r];
}
var suite = toutesDec(n-q, q) ;
var listeb = map(suite, function(sousliste){ sousliste.push(q); return sousliste;}) ;
var listea = toutesDec(n,q-1) ;
return listea.concat(listeb);

}
dolist= function(l,f ){ for(var i in l){ f(l[i]);} };
dolist(toutesDec( 10,4),d);


A vous d'inventer des problèmes plus compliqués encore, cette fonction est appelée "petite fonction de Ramanujan"
grand mathématicien du début du 20ème siècle.

Fonctions récursives sur les listes,

Fonctions récursives sur les listes:


Nous appellerons une liste tout tableau javascript, en effet un tableau javascript a une taille qui varie de façon dynamique. Contrairement aux listes Caml qui ne peuvent qu'extraire le premier élément de la liste, nous allons travailler sur le dernier élément du tableau. En effet, retirer le dernier élément (pop)est moins coûteux en calcul que retirer le premier(shift), une des raisons simple est que javascript n'aura pas besoin de renuméroter les éléments après pop() , ce qu'il aurait fait après shift() .

Fonction map :

Pourquoi à chaque fois refaire une boucle for ... puisqu'on est en programmation fonctionnelle il est plus simple de passer par une boucle générique map. On peut donner une première version de map :

function map(liste, fonction){
var resultat=[] ;
for(var i = 0 ; i < liste.length; i++){ resultat.push(fonction(liste[i]) );}
return resultat ;
}
//Calcul des carrés d'une liste;
map([1,3,5],function(x){ return x*x})) // Pour chaque élément (x) de la liste on retourne x*x ;[1,9,25]

On peut également, programmer un map récursif:

function map(l,f){
var r=[]
function aux(l, f){
if(l.length==0) return r ;
r.push(f(l.pop()))
return aux(l,f)
}
return aux(l,f).reverse();
}
map([1,3,5],function(x){ return x*x}) ;

On voit ici que le map n'est pas adapté à la programmation récursive, en effet, l'utilisation du pop impose en fin de récursion un renversement du tableau..De plus pop() consomme la liste donnée en argument.
Nous utiliserons donc la solution itérative, à l'aide d'une boucle for pour la suite.

Intérêt de la fonction map


Map permet d'être beaucoup plus concis:
Initialiser un tableau:

map(new Array(100), function(){ return 0 ;});
map(new Array(100),Math.random);

Fonction do_list :


Parfois, et même souvent, il est inutile de retourner un tableau. On n'a besoin que d'appliquer la fonction sur tous les éléments du tableau en utilisant "l'effet de bord" (c'est à dire les conséquences de la fonction et non son type retourné).
Nous proposons alors la fonction do_list :

 function do_list(liste, f){  for(var i=0; i< liste.length; i++) f(liste[i]); }


Utilisation des fonctionnelles map et do_list


Filtrer une liste suivant un prédicat:

map([1,5,9], function(x){ if(x<5) return x ;}); // renvoi [1,undefined,undefined]

var r=[] ;
do_list([1,5,9], function(x){ if(x<5) r.push(x) ;});
r; // renvoi [1] // Le résultat attendu.



Fonction list_it ou apply ;


Il est habituel d'utiliser des fonctions binaires à deux arguments, par exemple add(1,2) utilise deux arguments. Il est souvent utile d'appliquer successivement à chaque élément d'une liste, la fonction a deux arguments du résultat courant et de l'élément suivant. Par exemple si on désire obtenir la somme d'une liste on part de l'élément neutre (0 pour l'addition) et on ajoute successivement les éléments de cette liste.


// solution récursive :
function list_it(f, l, n){ return l.length===0? n : f(l.pop(),list_it(f,l,n)); }//


  • f est une fonction binaire à deux arguments,
  • l est la liste à traiter
  • n est le résultat courant


Attention cette solution consomme la liste, ce qui peut être intéressant en terme de gestion de la mémoire. On peut donc proposer une solution itérative à l'aide d'une boucle for:

function apply(f, l, n){
for(var i=0; i< l.length ; i++){ n= f( l[i], n ); }
return n;
}

En général le premier élément courant fournit à la fonction est un élément neutre pour la fonction donnée. Par exemple, -Infinity pour la fonction Math.max, 0 pour l'addition ou 1 pour la multiplication.
Programmer le maximum d'une liste à l'aide de list_it :
 list_it(Math.max , [1,3,2,9,3] , -Infinity ); //9,
list_it(Math.max , map(new Array(100), Math.random) , -Infinity ); // 0.99
//Programmer la somme des éléments d'une liste:
var sum = function(a,b){ return a+b;} ;
list_it(sum,[3,5,7], 0) ; // 15
//Programmer une fonction qui filtre une liste suivant un prédicat :
var r=[] ;
list_it(
function(x,tableau){ if(x<0.1) return tableau.push(x) ;}, // la fonction
map(new Array(100),Math.random), // le tableau à traiter
[] // la fonction de départ.
) ;

Malheureusement, cela ne fonctionne pas car la valeur retournée par tableau.push est un entier, il s'agit d'un défaut du langage; voici la bonne version:

list_it(
function(x,tableau){ if(x<0.1) tableau.push(x); return tableau ;},
map(new Array(100),Math.random),
[]) ;
//[0.02288494476776548, 0.04436209344039965, 0.08676040302532284, 0.04035038420070758,
// 0.02041697086984784, 0.06553779951155114, 0.0869513935206444]


Programmer une fonction qui teste si un prédicat est juste dans une liste donnée:
Cette fonction recherche si il existe un élément égal à 3 dans le tableau. On utilise en valeur de retour l'élément neutre pour le || c'est à dire false:

list_it(function(a,b){ return a===3||b},[1,3,5],false);  //


Parties d'un ensembles


Programmer une fonction qui renvoie toutes les partie d'un ensemble, cet ensemble étant représenté par une liste:
exemple:
parties(['a','b']);
//[[], ["a"], ["b"], ["a", "b"]]
Réponse:

function parties(l){
if(l.length===0) return [[]];
var e= l.pop();
var p = parties(l);
var suite=map(p,function(sousliste){ var r= sousliste.slice(); r.push(e); return r});
return p.concat(suite) ;
}
parties([1,3,4]);//[[], [1], [3], [1, 3], [4], [1, 4], [3, 4], [1, 3, 4]]
parties(map(new Array(10),Math.random)).length; //1024 soit deux puissance n, le nombre de parties d'un ensemble

Nb: notez dans la fonction map les 3 instructions successives: slice: permet d'obtenir une copie de la sous liste passée en argument, en effet elle est passée sous la forme d'une référence (une adresse en mémoire de la liste) et pour l'utiliser sans la modifier il faut d'abord en faire une copie grâce à sousliste.slice.
Par ailleurs, il n'est pas possible de renvoyer r.push(e) en effet, r.push(e) renvoi la nouvelle longueur de liste, toujours le même défaut de conception de javascript.

Programmer une fonction qui renvoi les anagrammes d'une liste :



//Anagrammes d'un mot
function anag(l){
if(l.length<=1) return [l] ;
var c = l .pop() ; // c est un élément
var ll = anag(l) ; // ll est une liste de liste,

var resultat = [];
for(var i= 0; i < ll.length ;i++){
inject(ll[i],c, resultat) ;
}
return resultat ;

function inject(liste,element, r){
var nl= liste.length +1 ;
for(var i=0; i< nl; i++){
var temp= new Array(nl);
temp[i]= element;
for(var j=0; j < liste.length ; j++){
temp[(i+j+1)% nl] = liste[j];
}
r.push(temp);
}
return
}
}
anag('mot'.split(''));
map(anag('mot'.split('')), function(l){ return l.join('');});

//tom,mto,omt,tmo,otm,mot

lundi 8 septembre 2008

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.

dimanche 7 septembre 2008

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.

mercredi 3 septembre 2008

Des exercices !

Le mieux pour apprendre les particularités d'un langage c'est de s'exercer, voici quelques exercices d'algorithmique qui permettront de se familiariser avec la programmation fonctionnelle et récursive en javascript.

Calculer de la dérivée d'une fonction f en un point x à l'aide de l'approximation dx.
On pourra écrire: dérivée( f, x, dx).
var dérivée= function(f,x,dx){
return (f(x+dx)-f(x))/dx ;

var carré = function(x){ return x*x ;}
dérivée(carré,30,0.0000001); ///f'(x^2)=2x (réponse 60)


Version 2 : renvoyer la fonction dérivée :

var dérivée =function(f,dx){
return function(x){ (f(x+dx)-f(x))/dx} ;
}

Avez vous remarqué qu'ici on renvoi non pas un nombre mais une fonction ?,

dérivée(carré, 0.001)(3);

Ou encore :

var dérivée = function(dx){
return function(f){
return function(x){
return (f(x+dx)-f(x))/dx} ;
}
}
// n'oubliez pas les return !!

Dans cette dernière version on peut parler de "curryfication", terme utilisé en hommage à Haskell Curry précurseur avec Alonzon Church du lambda calcul, et qui avait montré cette possibilité , l'opérateur () ne se prête pas tellement à une curryfication systématique des fonctions comme en Caml mais il est souvent intéressant cependant de renvoyer une fonction en résultat.

On peut ainsi écrire:

var fprime = function(f){ return dérivée(0.001)(f) ; }
var sinprime = fprime(Math.sin) ;
var cosprime = fprime(Math.cos) ;
var carreprime = fprime(function(x){return x*x;}) ;

Pour être utilisé ultérieurement :

sinprime(Math.PI) ;// 0.99



Récursion :

La récursion est très peu utilisée par les programmeurs java ou C, souvent à raison car ces programmes sont fondamentalement procéduraux. Par contre le javascript se prête très bien à la programmation récursive, et la récursion permet de traiter des problèmes avec souvent beaucoup plus de facilité que le traitement procédural, il faudra par contre faire attention à ne pas compromettre la puissance de la machine par des récursions imbriquées.

On s'échauffe avec ce petit problème :
Créer une fonction récursive qui calcule le nombre de chiffres d'un entier :

function nchiffres(n) { 
return n<10&&1 || 1+ nchiffres( Math.floor(n/10) ) ;
}


Remarquez la syntaxe qui permet de s'affranchir du if/else et qui n'est à pas nécessairement à considérer comme un exemple de programmation à suivre!

Tableaux et objets en javascript:

Tableaux et objets et javascript :


A Objets :


Un objet est une collection de données ordonnées en paires propriété: valeur , une valeur peut elle même être un autre objet, les objets peuvent être ainsi imbriqués, lors de l'utilisation de javascript dans une fenêtre de navigateur, l'objet par défaut est window.
Un objet peut être définit de plusieurs façons:

  1. A l'aide du mot new, il est possible de déclarer un simple : monObjet = new Object() ;
  2. Ou encore à l'aide d'une notation JSON : monObjet={} ;
  3. Ou encore une variable peut se transformer en objet var monObjet ; monObjet.quantité = 2 ;
  4. Enfin à l'aide d'un tableau associatif monObjet['quantite' ] est strictement identique à monObjet.quantite ;

Ces objets peuvent contenir un nombre illimité de propriétés, ces propriétés peuvent être de tout type, y compris fonction, ainsi on peut définir un objet animal :

animal ={}
animal.nom = 'chien' ;
animal.son = 'aboyer' ;
animal.sonne = function(){ return 'ouah-ouah' ;} / / cette fonction est appelée méthode car elle est appelée dans le contexte de l'objet animal.

Cet objet aurait pu être écrit directement en notation JSON:
animal={nom: chien, son: 'aboyer', sonner= function(){return 'ouah-ouah';} };

"Classe" d'objets :


Une classe d'objets est un ensemble d'objets qui possèdent des propriétés communes, on pourra ainsi effectuer des traitements en série, en appelant la même propriétés et la même fonction (on parle plutôt de méthode dans le cadre d'un objet) pour chaque objet. Un élément d'une classe d'objet est appelé une instance de cette classe. Une fonction d'un objet est appelée "méthode" .
On crée une classe d'objet grâce à une fonction, un nouvel élément d'une classe de l'objet est crée grâce au mot-clé "new" devant la fonction,
exemple :

gisc = new President ( 'Giscard D\'Estaing ', 'Valery' , 1974, 1981 ) ;
mimi = new President('Mitterrand', 'François', 1981,1995) ;

Nous avons ainsi crée deux objets Présidents, habituellement la convention est de créer des objets à l'aide d'une fonction dont le premier caractère est en majuscule de façon à distinguer une classe d'objet d'une fonction.

Définition d'une "classe":


La fonction qui sert à définir une classe utilise le mot-clé this pour définir la propriété de la classe, par exemple :

function President( nom , prenom, debut, fin){
this.nom = nom ;
this.prenom = prenom ;
this.debut = debut;
this.fin = fin ;
this.duree = function(){ return (fin-debut)+ " ans" ; }
}

On peut donc utiliser une même méthode duree pour tous les présidents. En javascript la notion de classe peut être contestée par les puristes, en effet une fonction d'un objet peut être réutilisée par un autre objet dans un contexte complètement différent (rappelez vous les instructions apply et call pour chaque fonction, le premier argument de apply et de call étant l'objet sur lequel on applique la fonction, ce qui permet à un objet d'emprunter la fonction d'un autre objet )

Tableaux


Les tableaux sont des objets, la différence avec l'objet c'est que le nom de la propriété est toujours un entier, et qu'il existe une propriété "length" qui permet de connaître la taille maximale de l'objet :
Là encore plusieurs façons de définir l'objet tableau existe :
-notation JSON:

monTableau =[] ; monTableau[0] = 'Chien', monTableau[1]= 'Chat' ;
-ou équivalent: monTableau = ['Chien', 'Chat'] ;

Il n'est pas nécessaire de définir à l'avance la taille du tableau, même si cela est possible:
-monTableau = new Array(2) ; // est équivalent à [undefined, undefined] ;


Un tableau s'apparente finalement plus à une pile ou une file suivant la façon dont ont le traite, on peut ajouter un élément en bout de tableau avec la méthode .push( , , ...) et retirer le dernier élément du tableau à l'aide de la méthode pop() .
Ainsi :

t =[ 2,3] ; // le tableau est initialisé,
t.push(5); // t vaut maintenant [2,3,5], la valeur renvoyée est bizarrement t.length, ce qui n'est en général pas utile et ce qui est à mon avis une erreur de conception, t.push() aurait du renvoyer un tableau, on peut pallier à cela en écrivant l'expression suivante:
t.push(qqchose) && t; // permet de renvoyé un nouveau tableau.
t.pop() ; // renvoi le dernier élément du tableau ici , 5
t.push(5,7,11,13,17,19,23) // permet d'obtenir : [2,3, 5,7,11,13,17,19,23]

De la même façon on peut utiliser les instructions shift et unshift pour ajouter et retirer le premier élément d'un tableau.
L'instruction concat : permet de concaténér les tableaux.

La méthode slice : renvoie une tranche de tableau sans modifier le tableau d'origine:

t.slice[indice-de-debut-inclus , indice-de-fin-noninclus]
t =[0,1,2,3,4,5,6,7];
r =t.slice(1,3); // r vaut [1,2] mais t n'est pas modifié

Si la fin est omise elle vaut alors t.length ;

La méthode splice: permet de découper une tranche également mais le deuxième argument correspond au dernier indice du tableau, d'autre part, la valeur renvoyée est une tranche qui est retirée du tableau.

r.splice[indice-début-inclus, nombre-d-elements-à-retirer]
t =[0,1,2,3,4,5,6,7];
r =t.splice(1,1); // r vaut [1] et t; // [0, 2, 3, 4, 5, 6, 7]

Copie de tableaux:


Il manque cependant une méthode !! il est en effet impossible de copier un tableau d'objets ou de tableaux, en effet seules les références sont copiées, c'est à dire l'adresse en mémoire des données.

a=[1] ; b=[2] ; c=[3] ;
t =[a, b, c];
r = t; // r et t se réfèrent à la même adresse mémoire, si on modifie l'un on modifie l'autre.
r[0] = 'yes';
t; // t vaut [ 'yes',[2],[3]]

Pour cela on utilise la méthode slice() ; sans argument qui renvoie une copie du tableau.

a=[1] ; b=[2] ; c=[3] ;
t =[a, b, c];
r=t.slice();
r[0] = 'yes';
t; //[[1], [2], [3]]

Bon, d'accord jusque là c'est rébarbatif, mais on passe bientôt à la pratique...

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

Comment apprendre et tester le javascript ?

Le problème: comment tester des morceaux de code en Javascript sans avoir à recharger la page ?

Une seule bonne réponse: le couple Firefox et Firebug.

Courrez vite télécharger Firebug et éteignez moi tous les autres navigateurs ! Une fois installé ouvrez Firefox créez un nouvel onglet (CTRL-T) puis en bas à gauche, cliquez sur cet horrible cafard et entrez dans Firebug... Vous pouvez déjà taper des commandes javascript dans la ligne de commande située en bas à côté de l'invite de commande à 3 chevrons >>> , mais attendez, il y a mieux !
Cliquez sur le menu options de firebug et cochez la case "agrandir la ligne de commande".

Vous disposez désormais d'un panneau situé sous votre page web, divisé verticalement en 2 :
- à droite, vous pouvez taper un code, - à gauche les valeurs retournées par ce code.

Tapez par exemple:

function hello(w){ return "Hello "+ w ;}

hello("World");

et vous aurez ainsi crée un premier programme.
Pour l'exécuter, vous pouvez cliquer sur le bouton exécuter. Personnellement j'utilise le raccourci clavier CTRL-Entrée pour exécuter.

De cette manière vous avez une interface très simple, qui vous permet de tout tester, voire de modifier votre page à la volée...

Présentation

Bonjour, voici mon blog, j'ai un peu hésité entre le faire en anglais ou en français mais mon niveau d'anglais était trop faible et tant pis, pour ceux qui ne parlent pas notre langue... je ne suis pas certain qu'ils perdront quelque chose...

Bon, l'idée c'est de montrer que le javascript est un langage fabuleux, qui s'apparente étonnamment au Caml et qu'il permet une programmation récursive très intéressante. Oh bien sûr, le langage est plein de défauts, le principal étant qu'il est implanté essentiellement dans Firefox et Internet Explorer où il est interprété depuis un programme écrit en C.. L'idéal serait de recréer un langage complet, avec bytecode et qui s'auto-compilerait ou qui serait interprété..
En fait le Javascript est :
  • Fonctionnel : les fonctions sont des valeurs de première classe, c'est à dire qu'elles peuvent être retournées en résultat et passés en argument à d'autre fonctions.
  • A gestion automatique de la mémoire... avec le problème compliqué des clôtures.
  • Faiblement typé : il n'existe que 6 types principaux.
  • Interprété: surtout au niveau des navigateurs
Maintenant interactif grâce à Firebug.. il existe d'ailleurs en préparation des extensions qui permettront une coloration syntaxique de la ligne de commande dans firebug, "Rainbow for Firebug "
Par ailleurs, il présente un mécanisme de classes assez sophistiqué qui utilise entre autre le prototype, et qui est très différent des classes classiques telles qu'on les connaît en Java ou C++.

L'idée de ce blog, si je continue, est de créer quelques exercices de programmation en js, un peu pour faire connaissance avec le langage, un peu pour moi ... un peu parce que j'ai l'impression que javascript est un ocaml déguisé et qu'il fallait bien que quelqu'un en parle...Identificateurs Technorati : , , , , , ,