Au fil des flows

2juin/140

Implementer ContinueWith pour les Rx Extension .Net

Posted by Fabien Arcellier

En ce moment, j'utilise beaucoup la librairie Rx Extension pour ma mission actuelle. Il s'agit d'un client lourd en WPF et .NET 4. Pour les requetes vers notre backend, nous avons choisi un schéma orienté flux pour requêter de manière plus naturelle des données sur un backend exposant certains de nos services en WCF.

Il nous a fallu à un moment synchroniser 2 requêtes. Je n'ai pas trouvé dans les Rx extensions de méthode permettant de rendre séquentiel le post traitement de 2 flux. L'opérateur Join s'en rapproche mais s'appuie sur une fenêtre temporelle.

Pour résoudre ce cas, j'ai décidé de coder un opérateur WaitOnceFor. Pour déclencher l'envoi d'un evenement (et d'un seul) du flux 1, j'attends de recevoir celui du flux 2.

var observable1 = Observable.CreateAsync<...>(...);
var observable2 = Observable.CreateAsync<...>(...);

observable1.WaitOnceFor(observable2).Subscribe(v => { "J'ai reçu mon signal" });

Pourquoi WaitOnceFor ?

J'aurai pu l'appeller ContinueWith ou ContinueAfter. Je cherchai effectivement un comportement proche du ContinueWith qu'offre les Tasks.

La nature des Rx Extension est cependant très différent du système de Task. Un IObservable représente pas une valeur comme le ferait une tache mais une suite de valeurs. Les opérateurs doivent tenir compte de cette nature et justement l'opérateur que je propose va à contre courant.

Si je l'avais appellé ContinueWith or ContinueAfter, j'aurai du implémenter un opérateur fonctionnant sur une suite d'événement. Dans mon cas, c'est un appel asynchrone qui fonctionne exactement sur le modèle d'une Task, à part que je veux profiter de l'Async Pattern. N'etant pas en .Net 4.5, je n'avais pas la possibilité de m'appuyer sur le mécanisme async/await

Le code

Voici la solution que je vous propose. C'est une méthode d'extension. Si other est de valeur null, ça signifie que je n'ai pas besoin de l'attendre, donc je forward directement l'observable source.

Elle est loin d'être parfaite. Voici le snippet.WaitOnceFor

/// Send a single signal when events of both IObservable where sent at least once
/// case 1 :
/// source : --- 1 --- 2 --- 3 --- 4
/// other  : ------------------ 1 ---
/// Result : ------------------ 1 ---
///
/// case 2:
/// source : ------------------ 1 ---
/// other  : --- 1 --- 2 --- 3 --- 4-
/// Result : ------------------ 1 ---
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source"></param>
/// <param name="other"></param>
/// <returns></returns>
public static IObservable<T> WaitOnceFor<T, K>(this IObservable<T> source, IObservable<K> other)
{
    if (other == null)
        return source;

    return Observable.Create<T>((IObserver<T> observer) =>
    {
        bool sourceDone = false;
        bool otherDone = false;
        T value = default(T);
        Action<T> trycomplete = (T val) =>
        {
            if (otherDone == true && sourceDone == true)
            {
                observer.OnNext(val);
                observer.OnCompleted();
            }
        };

        var d2 = source.Take(1).Subscribe(r =>
        {
            sourceDone = true;
            value = r;
            trycomplete(value);
        });

        var d1 = other.Take(1).Subscribe(r =>
        {
            otherDone = true;
            trycomplete(value);
        });

        return Disposable.Create(() =>
        {
            d1.Dispose();
            d2.Dispose();
        });
    });
}
Remplis sous: Non classé Aucun commentaire
10déc/131

Decouvrir le SDK Intel Perceptual Computing

Posted by Fabien Arcellier

Cet article est une copie de celui que j'ai rédigé sur l'intel developer zone.

J ai eu la chance grâce à BeMyApp et Intel d avoir accès a la camera Creative Senz3d. Je vous invite dans ce billet de blog à découvrir les possibilités que ce système autorise.

La réalité augmentée en est a ses balbutiements. vous pouvez noter 2 courants complémentaires :

  • le premier, amener le digital dans le réel,
  • la second, amener le réel dans le digital

C est au travers du SDK Intel Perceptual Computing que je vous propose d explorer cette seconde voie. Même si il est compatible avec une simple Webcam, vous aurez besoin de la camera Creative Senz3d pour en tirer pleinement partie, notamment pour la capture des gestes, la suppression de l'arrière plan, ...

01-materiel

Remplis sous: Non classé Lire la suite
9déc/130

Forcer Visual studio a s’attacher au programme qui se lance avec une ligne de programmation

Posted by Fabien Arcellier


protected override void OnStartup(StartupEventArgs e)
{
  if (e.Args.Contains<string>("-d"))
  {
    System.Diagnostics.Debugger.Launch();
  }

  base.OnStartup(e);
}

Quand vous lancez l'application en ajoutant -d à la ligne de commande et que Visual Studio est installé, vous obtenez la fenêtre suivante :

Remplis sous: Non classé Aucun commentaire
8avr/135

Construire un outil pour visualiser et calculer une expression mathématique en C# (Partie 2 / 4)

Posted by Fabien Arcellier

Comment interpréter une expression mathématique ? J'avais débuté un premier billet, il y'a un peu plus d'un an sur le sujet. Finalement, je ne l'avais pas concrétisé.

J'ai été récemment challengé sur le sujet. Sur le coup, je n'ai pas pu amené une réponse convaincante. J'avais la démarche dans les grandes lignes mais pas la réalisation. J'ai donc décidé de rouvrir ce projet et de le poursuivre sans me référer dans un premier temps à la littérature.

Ce code effectue 2 opérations de manière séquentielles :
- Transformer une chaine de caracteres en une liste de tokens
- Transformer une liste de tokens en arbre syntaxique

Transformer l'expression en tokens

J'ai modifié la classe pour tokenizer le code que j'avais écrit. Les changements sont :
- Le type des tokens sont un enum (au lieu d'une chaine de texte)
- Les fonctions ne sont plus encodées en dur dans le tokenizer

Voici la nouvelle classe Tokenizer

    public class Tokenizer
    {
        const int EXPRESSION_SIZE_MAX = 256;

        public TokenList Transform(string equation)
        {
            TokenList token_list = new TokenList();
            char[] equation_chars = equation.ToCharArray();
            char[] temp_value = new char[EXPRESSION_SIZE_MAX];
            int temps_value_boundary = 0;
            bool is_number = false;
            bool is_function = false;

            for (int i = 0; i < equation_chars.Length; i++)
            {
                Debug.Assert(!(is_function == true && is_number == true));
                char character = equation_chars[i];

                if (is_number == true && ((character < '0' || character > '9') && character != '.'))
                {
                    string temp_value_string = new String(temp_value).Replace('\0',' ').Trim();
                    token_list.Add(new Token(TokenType.VALUE, temp_value_string, i - 1 - temp_value_string.Length));
                    Array.Clear(temp_value, 0, temp_value.Length);
                    is_number = false;
                }
                else if (is_function == true && (character == '('))
                {
                    string temp_value_string = new String(temp_value).Replace('\0', ' ').Trim(); ;
                    token_list.Add(new Token(TokenType.FUNCTION, temp_value_string, i - 1 - temp_value_string.Length));
                    Array.Clear(temp_value, 0, temp_value.Length);
                    is_function = false;
                }

                if (i >= EXPRESSION_SIZE_MAX && (is_function == true || is_number == true))
                {
                    string temp_value_string = new String(temp_value);
                    Console.Error.WriteLine(String.Format("Expression overflow {0}, maximum {1} characters", temp_value_string, EXPRESSION_SIZE_MAX));
                    Array.Clear(temp_value, 0, temp_value.Length);
                }

                if (equation_chars[i] == '(')
                {
                    token_list.Add(new Token(TokenType.OPEN_BLOCK, "(", i));
                }
                else if (equation_chars[i] == ')')
                {
                    token_list.Add(new Token(TokenType.CLOSE_BLOCK, ")", i));
                }
                else if (equation_chars[i] == ',')
                {
                    token_list.Add(new Token(TokenType.NEXT_ARGUMENT, ",", i));
                }
                else if (equation_chars[i] == '+' || equation_chars[i] == '-' ||
                    equation_chars[i] == '*' || equation_chars[i] == '/')
                {
                    token_list.Add(new Token(TokenType.OPERATOR, equation_chars[i].ToString(), i));
                }
                else if (!is_function && ((character >= '0' && character <= '9') || character == '.'))
                {
                    is_number = true;
                    temp_value[temps_value_boundary] = character;
                    temps_value_boundary++;
                }
                else if (character != ' ')
                {
                    is_function = true;
                    temp_value[temps_value_boundary] = character;
                    temps_value_boundary++;
                }
                else if (is_function && character == ' ')
                {
                    Console.Error.WriteLine(String.Format("Tokenization failed, function {0} can be followed by ( without space", new String(temp_value)));
                }
            }

            if (is_number == true)
            {
                string temp_value_string = new String(temp_value).Replace('\0', ' ').Trim();
                token_list.Add(new Token(TokenType.VALUE, temp_value_string, equation_chars.Length - 1 - temp_value_string.Length));
            }
            else if (is_function == true)
            {
                Console.Error.WriteLine(String.Format("Tokenization failed, function {0} must be followed by (.", new String(temp_value)));

            }

            return token_list;
        }
    }

Parser l'expression mathematique

Une fois que vous obtenez une liste de tokens, il vous faut construire la représentation interne des données.

Voici un exemple de ce que nous cherchons à obtenir :

Par exemple, si nous souhaitons évaluer cette expression, nous aurons qu'à effectuer un parcours suffixe des noeuds.

Voici la classe qui a la tache de transformer une liste de tokens en arbre :

namespace MathParser
{
    public class Parser
    {
        private Dictionary<string, int> m_priorityOperator;
        private Stack<SyntaxNode> m_stackBlock;
 
        public Parser()
        {
            this.m_priorityOperator = new Dictionary<string, int>();
            this.m_priorityOperator.Add("()", 0);
            this.m_priorityOperator.Add("*", 1);
            this.m_priorityOperator.Add("/", 1);
            this.m_priorityOperator.Add("+", 2);
            this.m_priorityOperator.Add("-", 2); 

            this.m_stackBlock = new Stack<SyntaxNode>();
        }

        public SyntaxNode Parse(TokenList list)
        {
            SyntaxNode root = new SyntaxNode(SyntaxNodeType.Block, "");
            SyntaxNode current = root;
            if (list.Count == 0)
                return null;

            foreach (Token token in list)
            {
                switch (token.Type)
                {
                    case TokenType.OPEN_BLOCK:
                        current.createChild(SyntaxNodeType.Block, "()");
                        current = current.LastChild;
                        this.m_stackBlock.Push(current);
                        break;
                    case TokenType.CLOSE_BLOCK:
                        current = this.m_stackBlock.Pop();
                        current = current.Parent;
                        if (current.Type == SyntaxNodeType.Function)
                            current = current.Parent;
                        break;
                    case TokenType.NEXT_ARGUMENT:
                        current = this.m_stackBlock.Pop();
                        current = current.Parent;
                        current.createChild(SyntaxNodeType.Block, "");
                        current = current.LastChild;
                        this.m_stackBlock.Push(current);
                        break;
                    case TokenType.FUNCTION:
                        current.createChild(SyntaxNodeType.Function, token.Value);
                        current = current.LastChild;
                        break;
                    case TokenType.OPERATOR:
                        current.createChild(SyntaxNodeType.Operator, token.Value);
                        current = resolveOperatorNode(current);
                        break;
                    case TokenType.VALUE:
                        current.createChild(SyntaxNodeType.Number, token.Value); 
                        break;                        
                }
            }

            return root;
        }

        /// <summary>
        /// Resolve the operator position in the syntax tree
        /// </summary>
        /// <param name="current">current node</param>
        /// <returns></returns>
        private SyntaxNode resolveOperatorNode(SyntaxNode current)
        {
            SyntaxNode created_node = current.LastChild;
            current.Pop();
            int priority_created_node = this.m_priorityOperator[created_node.Value];

            while (current.Parent != null &&
                current.Type == SyntaxNodeType.Operator &&
                priority_created_node >= this.m_priorityOperator[current.Value])
            {
                current = current.Parent;
            }

            current.Push(created_node);
            this.moveLastOperatorAsParent(current);

            return current.LastChild;
        }

        /// <summary>
        /// Move the last child of a node N-Aire tree (current) as parent
        /// of the last 2 nodes
        /// +
        /// -> 5
        /// -> 3
        /// -> *
        /// 
        /// will given
        /// +
        /// -> 5
        /// -> *
        /// ->-> 3 
        /// </summary>
        /// <param name="current"></param>
        private void moveLastOperatorAsParent(SyntaxNode current)
        {
            int count_initial = current.Count;

            SyntaxNode operator_node = current.LastChild;
            current.Pop();
            SyntaxNode value_node = current.LastChild;
            current.Pop();
            operator_node.Push(value_node);
            current.Push(operator_node);

            Debug.Assert(current.Count == count_initial - 1);
        }
    }
}

L'un des points clef est la gestion des blocs. Pour cela, la classe Parser s'appuie sur une pile. Chaque fois qu'un bloc est ouvert, on vient empiler le contexte courant. Il est surement possible d'avoir une plus fonctionnelle et de s'appuyer sur une fonction récursive.

Cette classe s'appuie sur un arbre N-Aire. Pourquoi pas un simple arbre binaire ? Nous souhaitions pouvoir interpréter des fonctions. Une fonctions peut prendre N arguments.

Cette manière de procéder complique un peu le code. J'ai fait le choix que la classe SyntaxNode qui représente un noeud, interagisse avec ses enfants que sous la forme d'une pile. Le parser ne peut que empiler ou dépiler des enfants. J'ai trouvé que ça simplifier le niveau de cohésion de l'algorithme.

Voici la classe SyntaxNode :

namespace MathParser
{
    public enum SyntaxNodeType { Block, Operator, Operation_Mult, Number, Function }

    public class SyntaxNode
    {
        private Stack<SyntaxNode> m_children;
        private SyntaxNode m_parent;
        private SyntaxNodeType m_type;
        private string m_value;

        public SyntaxNode(SyntaxNodeType type, string value)
        {
            this.m_value = value;
            this.m_type = type;
            this.m_children = new Stack<SyntaxNode>();
        }

        /// <summary>
        /// 
        /// </summary>
        public SyntaxNode Parent
        {
            get
            {
                return this.m_parent;
            }
            set
            {
                this.m_parent = value;
            }
        }

        public SyntaxNodeType Type
        {
            get
            {
                return this.m_type;
            }
        }

        public string Value
        {
            get
            {
                return this.m_value;
            }
        }

        /// <summary>
        /// Gets the last child of Syntax Node
        /// </summary>
        public SyntaxNode LastChild
        {
            get
            {
                return this.m_children.First();
            }
        }

        /// <summary>
        /// Gets the first child of Syntax Node
        /// </summary>
        public SyntaxNode FirstChild
        {
            get
            {
                return this.m_children.Last();
            }
        }

        public int Count
        {
            get
            {
                return this.m_children.Count;
            }
        }

        public void createChild(SyntaxNodeType type, string value)
        {
            SyntaxNode child = new SyntaxNode(type, value);
            child.Parent = this;
            this.m_children.Push(child);
        }

        /// <summary>
        /// Gets an enumerator for the list syntax node
        /// </summary>
        /// <returns></returns>
        public IEnumerable<SyntaxNode> children()
        {
            return this.m_children;
        }

        public void Push(SyntaxNode node)
        {
            node.Parent = this;
            this.m_children.Push(node);
        }

        /// <summary>
        /// 
        /// </summary>
        public void Pop()
        {
            Debug.Assert(this.m_children.Count > 0);
            this.m_children.Pop();
        }
    }
}

Voici le résultat de l'exécution du programme :

Je met en téléchargement l'archive qui contient le code source : Outil C# permettant de parser une expression

Il est possible d'utiliser cet outil comme librairie :

Tokenizer tokenizer = new Tokenizer();
Parser parser = new Parser();
TokenList list = tokenizer.Transform("5+4");
SyntaxNode node = parser.Parse(list);

Il manque le support de plusieurs opérateurs (comme ^ pour les puissances, les modulo, les nombres négatifs). Ce code ne gère pas non plus les cas d'erreurs (2 opérateurs ne peuvent pas se suivre, ...)

Pour conclure

Ce code n'est pas la solution idéale. Cependant, je l'ai testé sur plusieurs expressions mathématiques sans trouver de problème. Je l'ai écrit sans me référer à la littérature.

Pour conclure sur une vrai solution

Si vous cherchez à écrire un programme capable d'évaluer des expressions sans passer par un outil tout fait, l'algorithme Shunting yard de Dijkstra s'y prête bien.

Cet algorithme part d'une idée simple. Notre façon d'écrire une expression mathématique n'est pas celle que nous utilisons pour l'évaluer. L'algorithme réordonne les éléments de l'expression en se basant sur les priorités des opérateurs pour qu'il soit évaluable par une machine qui se contenterait de lire chaque élément les uns à la suite des autres.

L'expression initial est transformée, par cet algorithme en Reverse Polish Notation (Postfix expression).

Remplis sous: Non classé 5 Commentaires
1avr/130

Jouons avec la physique : Simulateur de tissu

Posted by Fabien Arcellier

Il y'a peu, je suis tombé sur une démonstration HTML5 où l'on manipule un tissu à l'aide de la souris. J'ai été surpris par un fait, outre que ce soit du JavaScript, le code source de cet exemple faisait moins de 300 lignes.

Surprenant, comment en 350 lignes, ce code exécute cette simulation avec une telle fluidité ?
Au final, j'ai trouvé quelques réponses dans les commentaires de Reddit. Cet exemple utilise pour ses calculs l'algorithme Intégration de Verlet et un système de contrainte assez simple.

Voulant comprendre le fonctionnement de ce code, je l'ai porté en C++ en utilisant le framework Qt. Cette implémentation n'est pas optimisée. Par exemple, je traite les coordonnées x et y comme 2 champs de structure là où je pourrai les traiter sur la forme d'un tableau 2D. Il est possible qu'à l'avenir, je refactore ce code pour pouvoir utiliser cet exemple dans un environnement 3D comme Openglide. Je suis conscient que le code reste très monolithique. Le calcul et le rendu se font dans les mêmes classes.

Vous pouvez télécharger le code de ce portage sur GitHub.

Integration de Verlet

Comment transmettre le mouvement ? Pour ceux qui ont quelques restes de mécanique, vous pensez de suite, Newton, vecteur, application d'une ou plusieurs forces, accélération, intégrales, équation différentielle ... De suite ça parait très compliqué.

Il existe un algorithme offrant une facilité d'utilisation pour le calcul de déplacement. Cet algorithme c'est l'intégration de Verlet.
Au lieu de s'appuyer sur une équation différentielle position actuelle, vitesse et accélération, cet algorithme s'appuie sur une équation différentielle ayant trois arguments la position actuelle, la position précédente et l'accélération.

/*!
 * Methode qui calcule la nouvelle position du point en s'appuyant sur l'intégration de Verlet
 */
void Point::Update(qreal delta)
{
    // On applique la gravité
    this -> AddForce(0, this -> m_gravity * this -> m_mass);

    qreal vx = this -> m_x - this -> m_px;
    qreal vy = this -> m_y - this -> m_py;

    // Verlet integration equation
    delta *= delta;
    qreal nx = this -> m_x + vx + this -> m_ax * delta;
    qreal ny = this -> m_y + vy + this -> m_ay * delta;

    this -> m_px = this -> m_x;
    this -> m_py = this -> m_y;
    this -> m_x = nx;
    this -> m_y = ny;

    this -> m_ax = 0;
    this -> m_ay = 0;
}

Comment la souris interagit t'elle avec le tissu ?

Dans la méthode UpdateMouse, l'algorithme d'origine compare la position actuelle de la souris avec la position précédente et se sert de cette différence pour établir une vitesse. Est ce une bonne vision de la réalité ?

J'ai fait un choix légèrement différent du code d'origine, finissant sur la même conclusion.

J'utilise la position précédente et actuelle de la souris pour appliquer une accélération :

this -> AddForce((this -> m_mouse -> x - this -> m_mouse -> px) * 1000,
                             (this -> m_mouse -> y - this -> m_mouse -> py) * 1000);

Pourquoi 1000 ? La force de la gravité est fixée à 900 dans ce modèle (normalement, 9,81m/s²). J'ai choisi un coefficient qui avait un impact. Je ne pourrai pas expliquer ce choix en m'appuyant sur la mécanique.

On résout l'effet de cette force au travers de l'intégration de Verlet.

void Point::UpdateMouse()
{
    Q_CHECK_PTR(this -> m_mouse);
    if (this -> m_mouse -> down == false)
    {
        return;
    }

    qreal diff_x = this -> x() - this -> m_mouse -> x;
    qreal diff_y = this -> y() - this -> m_mouse -> y;
    qreal distance = qSqrt(diff_x * diff_x + diff_y * diff_y);
    if (this -> m_mouse -> button == Qt::LeftButton)
    {
        if (distance < this -> m_mouseInfluence)
        {
            this -> AddForce((this -> m_mouse -> x - this -> m_mouse -> px) * 1000,
                             (this -> m_mouse -> y - this -> m_mouse -> py) * 1000);
        }
    }
    else if (distance < this -> m_mouseCut)
    {
        this -> ClearConstraint();
    }
}

J'ai rajouté quelques interactions au clavier (sur les lettres Q,Z,D,S) :

void Point::UpdateKeyboard()
{
    if (this -> m_keyboard->keyup_down)
    {
        this -> AddForce(0, -2000);
    }

    if (this -> m_keyboard-> keydown_down)
    {
        this -> AddForce(0, 2000);
    }

    if (this -> m_keyboard -> keyright_down)
    {
        this -> AddForce(2000, 0);
    }

    if (this -> m_keyboard -> keyleft_down)
    {
        this -> AddForce(-2000, 0);
    }
}

Resolution des contraintes entre les mailles

La résolution de contrainte se fait dans la classe Constraint. Voici l'illustration de ce qui se passe :

void Constraint::Solve()
{
    qreal diff_x = this -> m_p1 -> x() - this -> m_p2 -> x();
    qreal diff_y = this -> m_p1 -> y() - this -> m_p2 -> y();
    qreal distance = qSqrt(diff_x * diff_x + diff_y * diff_y);
    qreal diff_distance = (this -> m_length - distance)/distance;


    // Il ne devrait jamais y avoir rupture (800 - 30)/(30)
    if (diff_distance > this -> m_tearDistance)
    {
        this -> m_p1 -> RemoveConstraint(this);
    }

    // scalar_1 is the ratio from p1 mass in comparaison with the p1 mass + p2 mass
    qreal scalar_1 = ((1 / this -> m_p1 -> mass()) / (1 / this -> m_p1 -> mass() + 1 / this -> m_p2 -> mass()));
    qreal scalar_2 = 1 - scalar_1;

    // Find a way to use directly arithmetic operation
    qreal x1_new = this -> m_p1 -> x() + diff_x * scalar_1 * diff_distance;
    this -> m_p1 -> setX(x1_new);
    qreal y1_new = this -> m_p1 -> y() + diff_y * scalar_1 * diff_distance;
    this -> m_p1 -> setY(y1_new);

    qreal x2_new = this -> m_p2 -> x() - diff_x * scalar_2 * diff_distance;
    this -> m_p2 -> setX(x2_new);
    qreal y2_new = this -> m_p2 -> y() - diff_y * scalar_2 * diff_distance;
    this -> m_p2 -> setY(y2_new);
}

Conclusion

Je ne connaissai pas ces algorithmes. Ce sont des outils surprenants, je les imaginai bien plus complexe. Ils n'ont pas vocation à faire de la simulation physique mais offre des possibilités surprenantes. J'ai la sensation d'être devant un univers immense et j'hésite où poser le pied après.

En savoir plus

Remplis sous: Non classé Aucun commentaire