Problème d'expression - Expression problem

Le problème d'expression est un problème de défi dans les langages de programmation qui concerne l'extensibilité et la modularité des abstractions de données statiquement typées. Le but est de définir une abstraction de données extensible à la fois dans ses représentations et ses comportements, où l'on peut ajouter de nouvelles représentations et de nouveaux comportements à l'abstraction de données, sans recompiler le code existant, et tout en conservant la sécurité de type statique (par exemple, pas de transtypage) . Il a exposé des lacunes dans les paradigmes de programmation et les langages de programmation , et il n'est toujours pas définitivement résolu, bien qu'il existe de nombreuses solutions proposées.

Histoire

Philip Wadler a formulé le défi et l'a nommé « Le problème de l'expression » en réponse à une discussion avec l'équipe des langages de programmation (PLT) de l'Université Rice . Il a également cité trois sources qui ont défini le contexte de son défi :

Le problème a été observé pour la première fois par John Reynolds en 1975. Reynolds a discuté de deux formes d'abstraction de données : les types définis par l'utilisateur, qui sont maintenant connus sous le nom de types de données abstraits (ADT) (à ne pas confondre avec les types de données algébriques ) et les structures de données procédurales , qui sont maintenant compris comme une forme primitive d'objets avec une seule méthode. Il a fait valoir qu'ils sont complémentaires, en ce que les types définis par l'utilisateur pourraient être étendus avec de nouveaux comportements, et les structures de données procédurales pourraient être étendues avec de nouvelles représentations. Il a également discuté des travaux connexes remontant à 1967. Cependant, les conclusions de Reynold basées sur cette première analyse se sont avérées complètement fausses : " qui a complètement raté le paradigme Orienté Objet et son grand succès. Il pensait également que les deux formes d'abstraction de données "sont intrinsèquement distinctes et complémentaires".

Quinze ans plus tard, en 1990, William Cook appliqua l'idée séminale de Reynold dans le contexte des objets et des types de données abstraits, qui s'étaient tous deux considérablement développés. Cook a identifié la matrice de représentations et de comportements qui sont implicites dans une abstraction de données et a expliqué comment les ADT sont basés sur l'axe comportemental, tandis que les objets sont basés sur l'axe de représentation. Il fournit une discussion approfondie du travail sur les ADT et les objets qui sont pertinents pour le problème. Il a également passé en revue les implémentations dans les deux styles, discuté de l'extensibilité dans les deux sens et a également identifié l'importance du typage statique. Plus important encore, il a discuté des situations dans lesquelles il y avait plus de flexibilité que Reynolds ne le pensait, y compris l'internalisation et l'optimisation des méthodes.

Lors de l'ECOOP '98, Shriram Krishnamurthi et al. a présenté une solution de modèle de conception au problème de l'extension simultanée d'un langage de programmation orienté expression et de son ensemble d'outils. Ils l'ont surnommé le "problème d'expressivité" parce qu'ils pensaient que les concepteurs de langages de programmation pourraient utiliser le problème pour démontrer le pouvoir expressif de leurs créations. Pour PLT, le problème était apparu dans la construction de DrScheme, maintenant DrRacket , et ils l'ont résolu via une redécouverte de mixins . Pour éviter d'utiliser un problème de langage de programmation dans un article sur les langages de programmation, Krishnamurthi et al. utilisé un ancien problème de programmation géométrique pour expliquer leur solution orientée motif. Lors de conversations avec Felleisen et Krishnamurthi après la présentation de l'ECOOP, Wadler a compris la nature centrée PL du problème et il a souligné que la solution de Krishnamurthi utilisait un cast pour contourner le système de types de Java. La discussion s'est poursuivie sur la liste de diffusion des types, où Corky Cartwright (Rice) et Kim Bruce (Williams) ont montré comment les systèmes de types pour les langages OO pourraient éliminer cette distribution. En réponse, Wadler a formulé son essai et a énoncé le défi, « si une langue peut résoudre le problème d'expression est un indicateur saillant de sa capacité d'expression. » L'étiquette "problème d'expression" cale sur expression = "combien votre langage peut-il exprimer" et expression = "les termes que vous essayez de représenter sont des expressions linguistiques".

D'autres ont co-découvert des variantes du problème d'expression à peu près au même moment que le PLT de l'Université Rice, en particulier Thomas Kühne dans sa thèse, et Smaragdakis et Batory dans un article parallèle de l'ECOOP 98.

Certains travaux de suivi ont utilisé le problème d'expression pour montrer la puissance des conceptions de langage de programmation.

Le problème d'expression est également un problème fondamental dans la conception d'une gamme de produits logiciels multidimensionnelle et en particulier en tant qu'application ou cas particulier des cubes de programme FOSD .

Solutions

Il existe différentes solutions au problème d'expression. Chaque solution varie en fonction de la quantité de code qu'un utilisateur doit écrire pour les implémenter et des fonctionnalités de langage dont elles ont besoin.

Exemple

Description du problème

On peut imaginer qu'on n'a pas le code source de la bibliothèque suivante, écrite en C# , que l'on souhaite étendre : 

public interface IEvalExp
{
    int Eval();
}

public class Lit: IEvalExp
{
    public Lit(int n)
    {
        N = n;
    }

    public int N { get; }

    public int Eval()
    {
        return N;
    }
}

public class Add: IEvalExp
{
    public Add(IEvalExp left, IEvalExp right)
    {
        Left = left;
        Right = right;
    }

    public IEvalExp Left { get; }

    public IEvalExp Right { get; }

    public int Eval()
    {
        return Left.Eval() + Right.Eval();
    }
}

public static class ExampleOne
{
    public static IEvalExp AddOneAndTwo() => new Add(new Lit(1), new Lit(2));
    public static int EvaluateTheSumOfOneAndTwo() => AddOneAndTwo().Eval();
}

En utilisant cette bibliothèque, nous pouvons exprimer l'expression arithmétique 1 + 2 comme nous l'avons fait dans ExampleOne.AddOneAndTwo() et pouvons évaluer l'expression en appelant .Eval() . Imaginons maintenant que nous souhaitions étendre cette bibliothèque, l'ajout d'un nouveau type est facile car nous travaillons avec un langage de programmation orienté objet . Par exemple, nous pouvons créer la classe suivante : 

public class Mult: IEvalExp
{
    public Mult(IEvalExp left, IEvalExp right)
    {
        Left = left;
        Right = right;
    }

    public IEvalExp Left { get; }

    public IEvalExp Right { get; }

    public int Eval()
    {
        return Left.Eval() * Right.Eval();
    }
}

Cependant, si nous souhaitons ajouter une nouvelle fonction sur le type (une nouvelle méthode dans la terminologie C#), nous devons changer l' interface IEvalExp , puis modifier toutes les classes qui implémentent l'interface. Une autre possibilité consiste à créer une nouvelle interface qui étend l' interface IEvalExp , puis à créer des sous-types pour les classes Lit , Add et Mult , mais l'expression renvoyée dans ExampleOne.AddOneAndTwo() a déjà été compilée, nous ne pourrons donc pas utiliser le nouvelle fonction sur l'ancien type. Le problème est inversé dans les langages de programmation fonctionnels comme F# où il est facile d'ajouter une fonction sur un type donné, mais l'extension ou l'ajout de types est difficile.

Problème Solution en utilisant l'algèbre d'objets

Redessinons la bibliothèque originale avec l'extensibilité à l'esprit en utilisant les idées de l'article Extensibilité pour les masses. 

public interface ExpAlgebra<T>
{
    T Lit(int n);
    T Add(T left, T right);
}

public class ExpFactory: ExpAlgebra<IEvalExp>
{
    public IEvalExp Lit(int n)
    {
        return new Lit(n);
    }

    public IEvalExp Add(IEvalExp left, IEvalExp right)
    {
        return new Add(left, right);
    }
}

public static class ExampleTwo<T>
{
    public static T AddOneToTwo(ExpAlgebra<T> ae) => ae.Add(ae.Lit(1), ae.Lit(2));
}

Nous utilisons la même implémentation que dans le premier exemple de code mais ajoutons maintenant une nouvelle interface contenant les fonctions sur le type ainsi qu'une fabrique pour l'algèbre. Notez que nous générons maintenant l'expression dans ExampleTwo.AddOneToTwo() en utilisant l' interface ExpAlgebra<T> au lieu de directement à partir des types. Nous pouvons maintenant ajouter une fonction en étendant l' interface ExpAlgebra<T> , nous allons ajouter une fonctionnalité pour imprimer l'expression : 

public interface IPrintExp: IEvalExp
{
    string Print();
}

public class PrintableLit: Lit, IPrintExp
{
    public PrintableLit(int n): base(n)
    {
        N = n;
    }

    public int N { get; }

    public string Print()
    {
        return N.ToString();
    }
}

public class PrintableAdd: Add, IPrintExp
{
    public PrintableAdd(IPrintExp left, IPrintExp right): base(left, right)
    {
        Left = left;
        Right = right;
    }

    public new IPrintExp Left { get; }

    public new IPrintExp Right { get; }

    public string Print()
    {
        return Left.Print() + " + " + Right.Print();
    }
}

public class PrintFactory: ExpFactory, ExpAlgebra<IPrintExp>
{
    public IPrintExp Add(IPrintExp left, IPrintExp right)
    {
        return new PrintableAdd(left, right);
    }

    public new IPrintExp Lit(int n)
    {
        return new PrintableLit(n);
    }
}

public static class ExampleThree
{
    public static int Evaluate() => ExampleTwo<IPrintExp>.AddOneToTwo(new PrintFactory()).Eval();
    public static string Print() => ExampleTwo<IPrintExp>.AddOneToTwo(new PrintFactory()).Print();
}

Notez que dans ExampleThree.Print() nous imprimons une expression qui a déjà été compilée dans ExampleTwo , nous n'avons pas eu besoin de modifier le code existant. Notez également que cela est encore fortement typé, nous n'avons pas besoin de réflexion ou de coulée. Si nous remplaçons PrintFactory() par ExpFactory() dans ExampleThree.Print(), nous obtiendrons une erreur de compilation car la méthode .Print() n'existe pas dans ce contexte.

Voir également

Les références

Liens externes