Проблема выражения

Проблема выражений — это сложная проблема в языках программирования , которая касается расширяемости и модульности абстракций статически типизированных данных. Цель состоит в том, чтобы определить абстракцию данных, которая является расширяемой как в своих представлениях, так и в своем поведении, где можно добавлять новые представления и новое поведение к абстракции данных без перекомпиляции существующего кода и при этом сохраняя статическую безопасность типов (например, без приведения типов). . Постановка задачи обнажает недостатки парадигм программирования и языков программирования , и по состоянию на 2023 год до сих пор считается нерешенной, хотя существует множество предлагаемых решений.

История

Филип Уодлер сформулировал задачу и назвал ее «Проблема выражения». в ответ на обсуждение с командой языков программирования Университета Райса (PLT) . Он также процитировал три источника, которые определили контекст его проблемы:

Эту проблему впервые заметил Джон Рейнольдс в 1975 году. Рейнольдс обсудил две формы абстракции данных: определяемые пользователем типы, которые теперь известны как абстрактные типы данных (ADT) (не путать с алгебраическими типами данных ), и процедурные структуры данных, которые теперь понимаются как примитивная форма объектов. только одним методом. Он утверждал, что они дополняют друг друга, поскольку пользовательские типы могут быть расширены за счет нового поведения, а процедурные структуры данных могут быть расширены за счет новых представлений. Он также обсудил соответствующую работу, начиная с 1967 года. Пятнадцать лет спустя, в 1990 году, Уильям Кук применил идею Рейнольдса в контексте объектов и абстрактных типов данных, которые значительно выросли. Кук определил матрицу представлений и поведений, которые неявно присутствуют в абстракции данных, и обсудил, как АТД основаны на оси поведения, а объекты — на оси представления. Он подробно обсуждает работу над ADT и объектами, имеющими отношение к проблеме. Он также рассмотрел реализации в обоих стилях, обсудил расширяемость в обоих направлениях, а также отметил важность статической типизации. Самое главное, он обсудил ситуации, в которых было больше гибкости, чем Рейнольдс рассмотрел, в том числе, интернализацию и оптимизацию методов.

На ECOOP '98 Шрирам Кришнамурти и др. представил решение шаблона проектирования проблемы одновременного расширения языка программирования, ориентированного на выражения, и его набора инструментов. Они назвали это «проблемой выразительности», поскольку считали, что дизайнеры языков программирования могут использовать эту проблему, чтобы продемонстрировать выразительную силу своих творений. Для PLT проблема проявилась при создании DrScheme, теперь DrRacket , и они ее решили. посредством повторного открытия миксинов . Чтобы избежать использования проблемы языка программирования в статье о языках программирования, Кришнамурти и др. использовали старую задачу по программированию геометрии, чтобы объяснить свое решение, ориентированное на шаблоны. В беседах с Феллейзеном и Кришнамурти после презентации ECOOP Вадлер понял PL-ориентированную природу проблемы и отметил, что решение Кришнамурти использовало приведение для обхода системы типов Java. Обсуждение продолжилось в списке рассылки типов, где Корки Картрайт (Райс) и Ким Брюс (Уильямс) показали, как системы типов для объектно-ориентированных языков могут устранить это приведение. В ответ Уодлер сформулировал свое эссе и поставил задачу: «Может ли язык решить проблему выражения, является важным показателем его способности к выражению». Ярлык «проблема с выражением» представляет собой каламбур на выражение = «насколько может выразить ваш язык» и выражение = «термины, которые вы пытаетесь представить, являются языковыми выражениями».

Другие варианты проблемы экспрессии открыли примерно в то же время, что и PLT Университета Райса, в частности Томас Кюне. в своей диссертации, а Смарагдакис и Баторий в параллельной статье ECOOP 98.

В некоторых последующих работах проблема выражений использовалась для демонстрации возможностей языков программирования.

Проблема выражения также является фундаментальной проблемой при проектировании многомерной линейки программных продуктов и, в частности, как приложение или частный случай программных кубов FOSD .

Решения

Существуют различные решения проблемы экспрессии. Каждое решение различается объемом кода, который пользователь должен написать для его реализации, а также требуемыми языковыми функциями.

• Множественная отправка
• Синтаксис Ruby § Открытые классы
• Копроизведения функторов ​
• Типовые классы
• Без тегов-финал / Объектные алгебры
• Полиморфные варианты

Пример

Описание проблемы

Мы можем представить, что у нас нет исходного кода следующей библиотеки, написанной на C# , которую мы хотим расширить:

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

Используя эту библиотеку, мы можем выразить арифметическое выражение 1 + 2 как мы это сделали в ExampleOne.AddOneAndTwo() и может оценить выражение, вызвав .Eval(). Теперь представьте, что мы хотим расширить эту библиотеку. Добавить новый тип легко, поскольку мы работаем с объектно-ориентированным языком программирования . Например, мы можем создать следующий класс:

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

Однако, если мы хотим добавить новую функцию к типу (новый метод в терминологии C#), нам придется изменить IEvalExp интерфейс, а затем измените все классы, реализующие этот интерфейс. Другая возможность — создать новый интерфейс, расширяющий IEvalExp интерфейс, а затем создайте подтипы для Lit, Add и Mult классы, но выражение, возвращаемое в ExampleOne.AddOneAndTwo() уже скомпилирован, поэтому мы не сможем использовать новую функцию поверх старого типа. Проблема обратная в языках функционального программирования, таких как F# , где легко добавить функцию к заданному типу, но расширить или добавить типы сложно.

Решение проблемы с использованием объектной алгебры

Давайте перепроектируем исходную библиотеку с учетом расширяемости, используя идеи из статьи « Расширяемость для масс».

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

Мы используем ту же реализацию, что и в первом примере кода, но теперь добавляем новый интерфейс, содержащий функции над типом, а также фабрику для алгебры. Обратите внимание, что теперь мы генерируем выражение в ExampleTwo.AddOneToTwo() используя ExpAlgebra<T> интерфейс вместо непосредственно из типов. Теперь мы можем добавить функцию, расширив ExpAlgebra<T> интерфейс, мы добавим функциональность для печати выражения:

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

Обратите внимание, что в ExampleThree.Print() мы печатаем выражение, которое уже было скомпилировано в ExampleTwoнам не нужно было изменять какой-либо существующий код. Обратите также внимание, что это все еще строго типизировано, нам не нужно отражение или приведение типов. Если бы мы заменили PrintFactory() с ExpFactory() в ExampleThree.Print() мы получим ошибку компиляции, поскольку .Print() метод не существует в этом контексте.

См. также

• Применение программных кубов FOSD
• Общее программирование
• POPLmark вызов

Внешние ссылки

• Проблема выражения, Филип Уодлер .
• Проблема выражений» « Лекция: Ральф Ламмель .
• Лекции C9: Доктор Ральф Ламмель — Продвинутое функциональное программирование — Проблема выражения на канале 9 .
• Независимо расширяемые решения проблемы выражения, Маттиас Зенгер и Мартин Одерски, EPFL Лозанна .