Expressie probleem - Expression problem

Het expressieprobleem is een uitdagingsprobleem in programmeertalen dat betrekking heeft op de uitbreidbaarheid en modulariteit van statisch getypeerde data-abstracties. Het doel is om een ​​data-abstractie te definiëren die uitbreidbaar is, zowel in zijn representaties als in zijn gedrag, waarbij men nieuwe representaties en nieuw gedrag kan toevoegen aan de data-abstractie, zonder bestaande code opnieuw te compileren, en met behoud van statische typeveiligheid (bijv. geen casts) . Het bracht tekortkomingen in programmeerparadigma's en programmeertalen aan het licht en het is nog steeds niet definitief opgelost, hoewel er veel voorgestelde oplossingen zijn.

Geschiedenis

Philip Wadler formuleerde de uitdaging en noemde het "The Expression Problem" in reactie op een discussie met het Programming Languages ​​Team (PLT) van Rice University . Hij citeerde ook drie bronnen die de context voor zijn uitdaging definieerden:

Het probleem werd voor het eerst waargenomen door John Reynolds in 1975. Reynolds besprak twee vormen van gegevensabstractie: door de gebruiker gedefinieerde typen, die nu bekend staan ​​als abstracte gegevenstypen (ADT's) (niet te verwarren met algebraïsche gegevenstypen ) en procedurele gegevensstructuren. , die nu worden begrepen als een primitieve vorm van objecten met slechts één methode. Hij voerde aan dat ze complementair zijn, in die zin dat door de gebruiker gedefinieerde typen kunnen worden uitgebreid met nieuw gedrag, en procedurele gegevensstructuren kunnen worden uitgebreid met nieuwe representaties. Hij besprak ook gerelateerd werk dat teruggaat tot 1967. De conclusies van Reynold op basis van deze vroege analyse bleken echter volkomen verkeerd: hij schreef dat het toevoegen van een tweede methode aan een object "meer een hoogstandje is dan een voorbeeld van duidelijke programmering, " die het objectgeoriënteerde paradigma en zijn grote succes volledig miste. Hij geloofde ook dat de twee vormen van data-abstractie "inherent verschillend en complementair zijn".

Vijftien jaar later, in 1990, paste William Cook Reynolds baanbrekende idee toe in de context van objecten en abstracte gegevenstypen, die beide enorm waren gegroeid. Cook identificeerde de matrix van representaties en gedragingen die impliciet zijn in een data-abstractie, en besprak hoe ADT's zijn gebaseerd op de gedragsas, terwijl objecten zijn gebaseerd op de representatie-as. Hij geeft een uitgebreide bespreking van het werk aan ADT's en objecten die relevant zijn voor het probleem. Hij beoordeelde ook implementaties in beide stijlen, besprak uitbreidbaarheid in beide richtingen en identificeerde ook het belang van statisch typen. Het belangrijkste was dat hij situaties besprak waarin er meer flexibiliteit was dan Reynolds dacht, inclusief internalisering en optimalisatie van methoden.

Op ECOOP '98, Shriram Krishnamurthi et al. presenteerde een ontwerppatroonoplossing voor het probleem van het gelijktijdig uitbreiden van een expressiegerichte programmeertaal en zijn toolset. Ze noemden het het 'expressiviteitsprobleem' omdat ze dachten dat ontwerpers van programmeertalen het probleem konden gebruiken om de expressieve kracht van hun creaties te demonstreren. Voor PLT was het probleem opgedoken in de constructie van DrScheme, nu DrRacket , en ze losten het op via een herontdekking van mixins . Om te voorkomen dat een programmeertaalprobleem wordt gebruikt in een paper over programmeertalen, hebben Krishnamurthi et al. gebruikten een oud geometrieprogrammeerprobleem om hun patroongeoriënteerde oplossing uit te leggen. In gesprekken met Felleisen en Krishnamurthi na de ECOOP-presentatie begreep Wadler de PL-gerichte aard van het probleem en hij wees erop dat Krishnamurthi's oplossing een cast gebruikte om Java's typesysteem te omzeilen. De discussie ging verder over de typen mailinglijst, waar Corky Cartwright (Rice) en Kim Bruce (Williams) lieten zien hoe typesystemen voor OO-talen deze cast zouden kunnen elimineren. Als reactie formuleerde Wadler zijn essay en stelde de uitdaging: "of een taal het expressieprobleem kan oplossen, is een opvallende indicator van zijn vermogen tot expressie." Het label "uitdrukkingsprobleem" woordspelingen op expression = "hoeveel kan uw taal uitdrukken" en expression = "de termen die u probeert te vertegenwoordigen zijn taaluitdrukkingen".

Anderen ontdekten samen varianten van het uitdrukkingsprobleem rond dezelfde tijd als de PLT van Rice University, met name Thomas Kühne in zijn proefschrift, en Smaragdakis en Batory in een parallel ECOOP 98-artikel.

In sommige vervolgwerkzaamheden werd het expressieprobleem gebruikt om de kracht van programmeertaalontwerpen te demonstreren.

Het expressieprobleem is ook een fundamenteel probleem in het ontwerp van multidimensionale Software Product Lines en in het bijzonder als een toepassing of speciaal geval van FOSD Program Cubes .

Oplossingen

Er zijn verschillende oplossingen voor het expressieprobleem. Elke oplossing varieert in de hoeveelheid code die een gebruiker moet schrijven om ze te implementeren, en de taalfuncties die ze nodig hebben.

Voorbeeld

Probleembeschrijving

We kunnen ons voorstellen dat we niet de broncode hebben voor de volgende bibliotheek, geschreven in C# , die we willen uitbreiden: 

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();
}

Met behulp van deze bibliotheek kunnen we de rekenkundige uitdrukking 1 + 2 uitdrukken zoals we deden in VoorbeeldOne.AddOneAndTwo() en kunnen we de uitdrukking evalueren door .Eval() aan te roepen . Stel je nu voor dat we deze bibliotheek willen uitbreiden, het toevoegen van een nieuw type is eenvoudig omdat we met een objectgeoriënteerde programmeertaal werken . We kunnen bijvoorbeeld de volgende klasse maken: 

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();
    }
}

Als we echter een nieuwe functie over het type willen toevoegen (een nieuwe methode in C# -terminologie ), moeten we de IEvalExp- interface wijzigen en vervolgens alle klassen wijzigen die de interface implementeren. Een andere mogelijkheid is om een ​​nieuwe interface te maken die de IEvalExp- interface uitbreidt en vervolgens subtypes te maken voor de klassen Lit , Add en Mult , maar de expressie die wordt geretourneerd in VoorbeeldOne.AddOneAndTwo() is al gecompileerd, dus we kunnen de nieuwe functie over het oude type. Het probleem is omgekeerd in functionele programmeertalen zoals F#, waar het gemakkelijk is om een ​​functie over een bepaald type toe te voegen, maar het uitbreiden of toevoegen van typen moeilijk is.

Probleem Oplossing met behulp van objectalgebra

Laten we de originele bibliotheek opnieuw ontwerpen met uitbreidbaarheid in gedachten, gebruikmakend van de ideeën uit de paper Extensibility for the 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));
}

We gebruiken dezelfde implementatie als in het eerste codevoorbeeld, maar voegen nu een nieuwe interface toe die de functies over het type bevat, evenals een fabriek voor de algebra. Merk op dat we nu de uitdrukking in VoorbeeldTwo.AddOneToTwo() genereren met behulp van de ExpAlgebra<T> -interface in plaats van rechtstreeks van de typen. We kunnen nu een functie toevoegen door de ExpAlgebra<T> interface uit te breiden , we zullen functionaliteit toevoegen om de uitdrukking af te drukken: 

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();
}

Merk op dat we in VoorbeeldThree.Print() een uitdrukking afdrukken die al is gecompileerd in VoorbeeldTwo , we hoefden geen bestaande code te wijzigen. Merk ook op dat dit nog steeds sterk getypt is, we hebben geen reflectie of casting nodig. Als we de PrintFactory() zouden vervangen door de ExpFactory() in de VoorbeeldThree.Print() zouden we een compilatiefout krijgen omdat de .Print() methode niet bestaat in die context.

Zie ook

Referenties

Externe links