Portée des variables au service de la POO

Portée des variables au service de la POO

> Tutoriel LeekScript

Cette page est valable uniquement pour le LS1.0, en LS1.1 les classes sont directement utilisables : Les Classes et Objets

Dans cette article, nous allons créer de la pseudo POO (Programmation Orienté Objet), étant donné que le LeekScript n'est pas un langage orienté objet. Dans un premier temps, je vais introduire la notion de POO, puis je vous expliquerais comment fonctionne la portée des variables. Afin de ne pas être trop théorique, nous allons programmer une structure appeler "Arbre Binaire de Recherche", c'est une structure optimisée pour l'insertion ordonnée et la recherche.

Notion de POO

Cette notion est très importante si vous commencez à vous intéresser à d'autres langages comme le C (++/#), le PHP, le Java, etc. C'est une nouvelle façon de construire ses programmes. Elle introduit les objets. Vous savez sûrement ce que c'est dans la vie de tous les jours, c'est quelque chose de transformable/manipulable, mais en programmation on nomme "objet" une structure constituée de variables et de fonctions appelées '''attributs et méthodes'''. Prenons l'exemple d'une voiture, elle est caractérisée par une vitesse, une accélération (ne rentrons pas non plus dans le détail) ainsi que des actions comme tourner, accélérer, freiner... Voici comment nous pourrions représenter notre voiture :

Cela permet d'avoir un code structuré et propre. Mais aussi de simplifier l'utilisation d'actions composées d'instructions complexes qui seront cachés à l'utilisateur. Une autre chose très importante en POO, c'est le principe d’encapsulation... Tous les attributs et méthodes n'ont pas à être manipulés pas l'utilisateur qui pourrais "casser" l'objet si il ne vérifie pas tel ou tel choses. Imaginons que l'utilisateur modifie la vitesse de notre voiture en cours de jeu et ne prenne pas en compte l'inertie ou autre chose, la voiture aurait des comportements bizarres, et encore ceci n'est qu'une modification mineure. L'encapsulation est donc le principe de rendre des parties de l'objet invisible à l'utilisateur, on appelle cela des attributs/méthodes privés, au contraire si l'utilisateur à la possibilité d'utiliser des attributs/méthodes, celle-ci sont publiques.

Les définitions de ces objets sont appelés "classes", on les utilise en créant une nouvelle instance de la classe comme avec un type normal (nombres, tableaux, strings...). C'est juste que dans la plus part des compilateurs (pour ne pas dire tous) cette instanciation est implicite : var a = 5; crée une variable de l'objet nombre avec la valeur '5'. Je parle d'objets nombres par abus de langage. Une différence avec la POO sont les fonctions appliqués à une variable :

var a = 1;

//Sans POO

add(a, 1); // defini par function (@obj, nbr) { obj += nbr; }

// POO

a.add(1); // defini par method add (nbr) { this += nbr; }

La fonction 'add' prend en paramètre un nombre à ajouter. La différence entre les deux versions est le contexte, dans le premier cas 'add' ne sait pas à quel objet appliquer ces instructions, il lui faut une référence vers ce nombre (le paramètre 'obj'). Alors que dans la seconde fonction, c'est une méthode. Elle connais donc l'objet qui doit être modifiés puisque 'add' appartient à 'a'. Remarque : La syntaxe est totalement arbitraire, il faut juste comprendre le principe.

Pour infos, 'add' est publique si vous avez suivi puisque l'utilisateur peut appeler la fonction.

Portée des variables

Vous avez sûrement déjà utilisé les variables globales, elle vous permettent de garder des informations entre les tours et de pouvoir y accéder partout dans votre code. Ce qui les différencies des variables "locales" est leurs "portée". Prenons le code suivants :

global _global;

function testPortee () { var localFunction; }

var localMain;

Chacune des variables ci-dessus ont une portée différente : _global est accessible partout sur tous les tours, localMain est accessible uniquement dans le bloc principale (pas dans les fonctions), localFunction n'est accessible que dans la fonction "testPortee". La portée s'applique aussi aux fonctions, en effet testPortée est accessible tous les tours de partout, alors qu'une fonction anonyme n'est accessible que dans l'espace ou elle a vue le jour (comme une variable).

La portée d'une variable s'applique à tous les blocs ( symbole des blocs : '{' et '}' ). Ainsi une variable créée dans un if, un while, un do/while, un for n'est pas accessible en dehors de celui-ci :

if (true) { var localIf = 0;// Creation de localIf } // Fin de vie de localIf

debug(localIf); // Erreur : (localIf) variable ou fonction inconnue

for (var i = 0; i

Terminologie

Nœud : L'arbre est composé de nœuds qui contiennent une valeur ainsi qu'une référence vers un nœud à droite et un nœud à gauche pouvant être nul Racine : C'est tout simplement le nœud qui n'as pas de parent Parent: Chaque nœud ne possède qu'un seule parent, c'est le nœud qui le pointe Enfants : Ce sont les nœuds qui sont pointés par le nœud courant Feuilles : Nœuds sans enfants Nœuds internes : Un nœud interne est un nœud qui n’est pas une feuille Successeur : Le minimum de l'arbre gauche du nœud Prédécesseur : Le maximum de l'arbre droit du nœud Dans l'image ci-dessus :

8 est la racine de l'arbre 3, 6, 10 et 14 sont des nœuds internes 1, 4, 7 et 13 sont des feuilles 3 est le parent de 1 et 6 14 est un enfant de 10 Le successeur de 8 est 13 Le prédécesseur de 8 est 7

Syntaxe utilisé pour les pseudo-codes :

Paramètre d'entrée

Attributs de l'objet courant

Méthode statique (utilisable hors de toutes classes)

Attributs et méthodes d'un nœud

Insertion

Maintenant, nous allons nous intéresser aux principaux algorithmes des ABR. L'insertion d'un nœud en est un.

Dans le cas ou l'arbre est vide : il suffit d'attribuer cette valeur comme racine. Dans le cas où il y a un ou plusieurs nœuds : On parcours l'arbre à partir de la racine, si la valeur est supérieur on se déplace à gauche sinon à droite On répète l'opération jusqu'à ne plus pouvoir : l'enfant ciblé est vide. Il y a deux méthodes, par (La Récursivité) ou itérativement, dans le second cas, l'arbre principal (celui qui contient la référence à la racine) possède une méthode qui va parcourir l'arbre jusqu'à obtenir le bon emplacement. Nous allons utiliser la récursivité, i.e. chaque nœud possède une méthode qui délègue l'insertion dans un de ces enfants sauf si il est vide, dans ce cas il insère le nœud. Voici le Pseudo-code d'insertion en récursif (La Récursivité) :

// Méthode de l'arbre principal : appelé par l'utilisateur METHODE Insertion (valeur : nombre) SI EstVide (racine) racine Pouvoir instancier une classe Avoir des attributs publiques et privés Avoir des méthodes publiques et privées

Dans quel cas est-il possible de créer de nouvelles variables sans faire appel aux tableaux ? (Car les tableaux sont trop coûteux) Les fonctions, il faut utiliser des fonctions pour créer des nouvelles variables :

function new_Object () { var attribut; }

Avec une tel fonction à chaque appel, une nouvelle variable est crée mais elle n'est pas accessible directement en dehors de la fonction. Pour résoudre ce problème il faut renvoyer soit une référence vers la variable (mais si notre objet en contient plus, ça coince), soit en renvoyant une fonction ou un tableau.

function new_Object () { var privateAttribut; var publicAttribut; var privateMethod; var publicMethod;

return @( function (/* Que mettre ?/) {/ Que mettre ?/} ); // OU return @ [/ Que mettre ? */]; }

var obj = new_Object();

Parce que j'aime pas les tableaux à cause de leurs coût, j'utiliserai sauf cas contraire des fonctions anonymes. 'obj' est maintenant une instance de 'Object', mais pour l'instant il ne peut pas se modifier, car la fonction ne fait rien... Si maintenant, on renvoie une fonction anonyme qui modifie nos attributs :

function new_Object () { // ... (je ne vais pas tout remettre à chaque fois)

return @( function () { publicAttribut = 1; } ); }

var obj = new_Object(); // obj est donc une fonction anonyme

// obj := // privateAttribut = null // publicAttribut = null; // privateMethod = null; // publicMethod = null;

obj(); // Appel de la fonction créé dans new_Object

// obj := // privateAttribut = null // publicAttribut = 1; // privateMethod = null; // publicMethod = null;

Remarque : ':=' veut dire 'par définition égale à', je l'utiliserai pour vous montrer les valeurs de ses attributs

Si vous avez suivi, il est possible de modifier les attributs car la fonction "se souvient" de son contexte, i.e. lors de l'appel à la fonction par 'obj()', la fonction est exécuté comme si elle se trouvais encore dans la fonction ou les attributs sont accessibles.

Seulement, pour l'instant on ne choisi pas ce que l'on veut modifier et comment. Très simple : il suffit de passer en paramètre à notre fonction anonyme une commandes :

function new_Object () { // ... return @( function (@cmd) { if (cmd === "Modifie !") publicAttribut = 1; }); }

var obj = new_Object();

obj("Modifie !");

// obj := // publicAttribut = 1; // ...

Et voila ! Si la commande est bien "Modifie !", alors la valeur de 'publicAttribut' sera mis à 1. Le second problème est comment choisir la valeur à attribués à 'publicAttribut' ? On ne peut pas mettre simplement plusieurs paramètres à la fonction retournés car ce n’est pas très flexible, imaginons on utilise un objet dans notre programme, rajouter un paramètre à cette fonction entraînerai un bug à tout notre code... On peut cependant retourner une autre fonction qui prend en paramètre une valeur à attribué à 'publicAttribut' :

function new_Object () { // ... return @( function (@cmd) { if (cmd === "Modifie !") return function (@value) { publicAttribut = value; }; }); }

Que l'on pourra appeler de cette façon :

var obj = new_Object();

var mod_obj = obj("Modifie !"); // retourne une fonction qui prend un paramètre mod_obj(5); // Modifie l'attribut de obj

//Simplifier en : obj("Modifie !")(5);

De cette façon, il est possible de faire de l'encapsulation, puisque de base tout est privé, et à l'aide de commandes rendre des méthodes publiques. Pour informations il n'est pas possible de rendre des attributs publiques, il faut obligatoirement passer par des getteurs/setteurs, i.e. :

function new_Object () { var attribut; return @( function (@cmd) { if (cmd === "SetAttribut") return function (@value) { attribut= value; }; if (cmd === "getAttribut") return @attribut; }); }

Remarque : Il faut noter qu'il est possible d'obtenir une référence à un attribut via un return si et seulement si l'attribut contient un tableau ou une string (cf : Comportement du @ ).

Idée d'optimisations

Commande donnée en paramètre

---

Lorsque vous envoyer une commande à cotre objet : obj("commande"); , celui est envoyé en donnée brute, le '@' qui est utilisé dans la signature de la fonction return function (@cmd) { /* ... */ } retire 1 opération, mais le transfert coûte toujours 1 opération, pour réduire ce coût, il faut passer une variable (Comportement du @). Dans notre cas, on va utiliser des constantes, en LS on utilise des globals.

global setAttribut = 0; // A chaque constante, il faut modifie la valeur contenu

var obj = new_Object();

obj(setAttribut); // Coute 1 opération pour l'appel à la fonction au lieu de 2

De plus cela permet d'avoir l’auto complétion

Remarque : Attention, lors de l'utilisation de plusieurs classes, de ne pas créer deux globals du même nom, soit vous préfixez vos cst par des initiales en rapport à votre objet, soit vous réunissez toutes vos constantes et vous les réutilisez.

Dichotomie

--- Ce deuxième point est plus complexe. Il permet de réduire le coût moyen de l'appel à une méthode. Pour l'instant, nous utilisons une suite de 'if' pour sélectionner la bonne méthode en fonction. Pour cela nous allons introduire le concept de dichotome. Pour ceux qui n'ont jamais vu ce principe, imaginez vous en train de jouer au jeu du plus ou moins. vous devez trouvez un nombre choisie aléatoirement dans un intervalle, en moins de coups possibles. La meilleurs des technique est de séparer l'intervalle en deux, proposer ce nombre au milieu, puis recommencer avec le nouvel intervalle.

Pour utiliser cette technique vous devez avoir intégré les constantes pour les commandes. Chaque constante doit être un entier naturel qui se suit à moins que vous aimiez la difficulté.

Ainsi il est possible à l'aide de ternaire d’utiliser la technique de dichotomie :

function new_Object () { return @( function (@cmd) { return @( cmd < 4 ? cmd < 2 ? // 4/2 cmd < 1 ? // 2/2 CMD_0 : CMD_1 : cmd < 3 ? // 2 + 1 CMD_2 : CMD_3 : cmd < 6 ? // 4 + 4/2 cmd < 5 ? // 4 + 2/2 CMD_4 : CMD_5 : cmd < 7 ? // 4 + 2 + 1 CMD_6 : CMD_7 ); }); }

Voici un exemple, c'est un peu compliqué à expliquer, il faut suivre les conditions, chaque CMD_X p-e remplacé par une fonction à renvoyé ou un attribut. La recherche de la commande prendre donc toujours 3 opérations, alors qu'avec des 'if' il prendra entre 1 et 8 opérations soit en moyenne 4.5 opérations. Pour savoir le nombre d'étage de votre dichotomie, il faut calculer : ceil(log2(n)), par exemple pour n = 11 : log2(11) = 3.46 (arrondie) soit ceil(3.46) = 4 étages, votre première conditions sera : cmd < 2^(4-1) .

Limite de la technique : Si vous ne le savez pas, l'accès à un tableau coûte 5 opérations, chaque condition coûte 1 opération, on peut donc determiner un nombre maximum de méthode soit 2^5 = 32. ''i.e.'' Si vous avez autant ou moins de 16 méthodes, utilisez la dichotomie, sinon utilisez les tableaux de cet façon :

function new_Object () { var this =@ [ 0 : CMD_0, 1 : CMD_1, 2 : CMD_2, 3 : CMD_3, 4 : CMD_4, 5 : CMD_5, 6 : CMD_6, 7 : CMD_7, //etc... ]; return @( this ); }

Beaucoup plus simple je vous l'accorde mais priorité à l'optimisation.

Création d'ABR en LeekScript

A vos éditeurs !

Structuratio

Pour commencer, nous allons déterminer un cahier des charges afin de savoir comment organiser nos structures, il nous faut : Pour l'utilisateur :

Invisible pour l'utilisateur :

Structure de la classe ABR (arbre) :

Structure de la classe Nœud :

Je n'ajoute pas la fonction Successeur car celle-ci n'est utile que dans le cadre de suppression et elle ne répond pas aux attentes (il faut le parent).

Création de la Classe BST

Pour cela nous allons reprendre la structure utilisé ici.

// Ajouter les constantes, nous ajouterons la dichotomie plus tard // Je les préfixes pour éviter des conflits global ABR_Search = 0; global ABR_Insert = 1; global ABR_Remove = 2;

function new_BST () { // La racine de l'arbre (' = null' ne sert à rien) // Une autre méthode pourrais consister a passer en argument de new_BST une valeur pour racine, et créer le nœud avec cette valeur var _racine = null;

return @( function (@cmd) { // Chacune des fonctions ont besoins d'une valeur, il faut donc renvoyer une fonction anonyme qui nécessite un paramètre if (cmd === ABR_Search) return @(function (@v) {

}); if (cmd === ABR_Insert) return @(function (@v) {

}); if (cmd === ABR_Remove) return @(function (@v) {

}); }); }

Création de la Classe Node

Nous avons besoins que cette classe ne soit pas accessible par l'utilisateur. Pour cela il faut que la classe soit une fonction appartenant à la classe BST :

function new_BST () { var new_Node = function (@_value) { // On demande un paramètre car il faut une valeur pour notre nœud obligatoirement // Pas besoin de faire var v = value; car la variable est déjà créé en tant que paramètre ce qui ne change rien // on ajoute les enfants var _leftChild; var _rightChild;

return @( function (@cmd) { // Même cas, il faut renvoyer une fonction anonyme qui nécessite un paramètre if (cmd === ABR_Search) return @(function (@v) {

}); if (cmd === ABR_Insert) return @(function (@v) {

}); if (cmd === ABR_Remove) return @(function (@v) {

}); }); };

// Le reste de la fonction BST ci-dessous }

Toutes les structures sont construites il nous manque plus que les algos

Rechercher

Pour cette méthode, j'utiliserai l'algorithme étudié plus tôt.

// Classe BST : // ... if (cmd === ABR_Search) return @(function (@v) { // Possible de faire un ternaire mais ne change pas les performances dans ce cas if (_racine === null) return @false; else return @_racine(ABR_Search)(v); }); // ...

// Classe Node : // ... if (cmd === ABR_Search) return @(function (@v) { if (_value < v) { if (_leftChild === null) return @false; else return @_leftChild(ABR_Search)(v); } else if (_value === v) return @true; else { if (_rightChild === null) return @false; else return @_rightChild(ABR_Search)(v); } }); // ...

Insertion

Pour cette méthode, j'utiliserai l'algorithme étudié plus tôt.

// Classe BST : // ... if (cmd === ABR_Insert) return @(function (@v) { if (_racine === null) _racine = new_Node(v); else _racine(ABR_Insert)(v); }); // ...

// Classe Node : // ... if (cmd === ABR_Insert) return @(function (@v) { if (_value < v) { if (_leftChild === null) _leftChild = new_Node(v); else _leftChild(s)(v); } else { if (_rightChild === null) _rightChild = new_Node(v); else _rightChild(s)(v); } }); // ...

La traduction en LS est vraiment simple. Mais les choses se compliquent avec la suppression... [ En cours de rédaction par Le Gentleman ... ]