Как проверить / доказать ортогональность языка программирования?

Я знаю концепцию ортогональности, но есть ли способ проверить / доказать это с точки зрения языка программирования?

Например, в C # можно использовать publicили staticдля сигнатуры метода. Вы можете использовать один или оба, и они не будут мешать друг другу, поэтому они ортогональны друг другу, верно?

У меня вопрос, как мне узнать об остальных функциях, особенно о функциях, которые не связаны друг с другом?

Все ли функции должны сосуществовать / складываться вместе?

Есть ли язык программирования, который на 100% ортогональн?

Я не уверен, что ортогональность может служить полезной или действительной метрикой в ​​случае языков высокого уровня общего назначения, таких как C #, потому что это требует различия между «операциями» и «операндами» - небольшими частями языка, которые нелегко различимы в таких языках высокого порядка, как C #.

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

В этом отношении я бы предпочел проверить ортогональность Common Intermediate Language, используя в качестве цели компилятор C # язык Stack Machine, а не сам C #.

Если вы действительно заинтересованы в ортогональности C #, и я не ошибаюсь здесь (для любых целей), я бы предложил взглянуть на некоторые алгоритмы генетического программирования . Вы можете использовать их для создания различных программ из заданного набора ключевых слов (даже бессмысленных), и вы можете просто автоматически проверить, являются ли они компилируемыми. Это поможет вам автоматически увидеть, какие элементы языка можно объединить, и получить некоторые аспекты вашей метрики ортогональности.

Термин «ортогональность» - это термин непрофессионала для точного математического понятия: языковые термины образуют начальную алгебру (см. Ее в Википедии).

Это в основном означает «есть соответствие 1-1 между синтаксисом и значением». Это означает: есть только один способ выразить вещи, и, если вы можете поместить какое-то выражение в определенное место, то вы можете поместить и любое другое выражение там.

Другой способ думать об «ортогональности» состоит в том, что синтаксис подчиняется принципу подстановки. Например, если у вас есть оператор со слотом для выражения, тогда любое выражение может быть помещено туда, и результат все еще остается синтаксически допустимой программой. Кроме того, если вы замените

Я хочу подчеркнуть, что «значение» не подразумевает вычислительный результат. Ясно, что 1 + 2 и 2 + 1 оба равны 3. Однако термины различны и подразумевают другое вычисление, даже если оно имеет одинаковый результат. Значение отличается, так же как два алгоритма сортировки различны.

Возможно, вы слышали об «абстрактном синтаксическом дереве» (AST). Слово «абстрактный» здесь означает именно «ортогональный». Технически большинство АСТ на самом деле не абстрактны!

Возможно, вы слышали о языке программирования "C"? Обозначение типа C не является абстрактным. Рассматривать:

int f(int);

Итак, вот объявление функции, возвращающее тип int. Тип указателя на эту функцию определяется как:

int (*)(int)

Обратите внимание, вы не можете написать тип функции! Обозначение типа C - отстой! Это не абстрактно. Это не ортогонально. Теперь предположим, что мы хотим создать функцию, которая принимает вышеуказанный тип вместо int:

int (*) ( int (*)(int) )

Все хорошо .. но .. что если мы хотим вернуть это вместо:

int (*)(int) (*) (int)

Woops! Недействительным. Давайте добавим парены:

(int (*)(int)) (*) (int)

Woops! Это тоже не работает. Мы должны сделать это (это единственный способ!):

typedef int (intintfunc*) (int);
intintfunc (*)(int)

Теперь все в порядке, но использование typedef здесь плохо. С отстой. Это не абстрактно. Это не ортогонально. Вот как вы делаете это в ML, а именно:

 int -> (int -> int)

Мы осуждаем C на уровне синтаксиса.

Хорошо, теперь давайте выпустить C ++. Мы можем исправить вышеуказанную глупость с помощью шаблонов и получить обозначение, подобное ML (более или менее):

fun<int, int>
fun< fun<int,int>, int>

но действительная система типов в корне неверна ссылками: если Tэто тип, то есть T&ли тип? Ответ неопределенный: на уровне синтаксиса, если у вас есть тип U = T &, тогда U & разрешен, но это просто означает T &: ссылка на ссылку является исходной ссылкой. Это отстой! Это семантически нарушает требование уникальности. Хуже того, T & & не допускается синтаксически: это нарушает принцип замещения. Таким образом, ссылки на C ++ нарушают ортогональность двумя различными способами, в зависимости от времени привязки (анализ или анализ типов). Если вы хотите понять, как это сделать правильно ... с указателями проблем нет!

Практически нет реальных языков ортогональных. Даже Схема, которая претендует на большую ясность выражения, - нет. Однако многие хорошие языки могут быть оценены как имеющие «достаточно близкие к ортогональным признакам свойства», и это хорошая рекомендация для языка, применяемого как к синтаксису, так и к базовой семантике.

Доказательство ортогональности доказывает отрицание. Это означает, что у вас нет конструкций, которые не являются ортогональными, а это значит, что гораздо проще доказать, что что-то не ортогонально, чем есть.

На практике большинство людей говорят об ортогональности языков программирования в терминах степеней, а не о том, полностью ли они ортогональны или нет. Когда знание о чем-то в одном контексте переводится в другой и «делает то, что вы ожидаете», этот язык считается более ортогональным. LISP считается очень ортогональным, потому что все является списком, но я не думаю, что можно сказать, что он на 100% ортогональный из-за некоторых избыточностей, которые облегчают его использование. С ++ считается не очень ортогональным, потому что есть много маленьких "ошибок", где он не совсем работает так, как вы думаете.

Предупреждение, я ничего не знаю об этой теме.

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

Для C # я бы предположил, что он ортогональн, поскольку большинство синтаксических приемов ( foreachприходит в голову) являются просто интерфейсом к специально сформированным версиям базовой конструкции ( foreachпревращается в forциклы). В целом, язык действительно поддерживает единовременные действия, хотя синтаксический сахар предоставляет дополнительные способы их выполнения. И, наконец, все это сводится к MSIL(или как это называется в наши дни) и MSIL, скорее всего, ортогонально.

Если вы сделаете оговорку, что синтаксический сахарный материал по сути является «оберткой», делая «трудный путь», вы можете проанализировать различные особенности языка, исключив сахар, и посмотреть, есть ли какие-либо конструкции, которые действительно перекрываются. Если нет, я думаю, вы могли бы объявить язык ортогональным.

Мои два цента.

У меня вопрос, как мне узнать об остальных функциях, особенно о функциях, которые не связаны друг с другом?

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

Это все. Это довольно больно делать.

Все ли функции должны сосуществовать / складываться вместе?

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

Все структуры данных работают со всеми примитивными типами. Все операторы выражений работают со всеми типами. Это общие определения ортогональности. Но вы можете хотеть больше (или меньше)

Иногда, однако, есть особые случаи из-за операционных систем или устаревших библиотек, которые не являются ортогональными.

Кроме того, некоторые типы не совсем совместимы. Например, Python позволяет сравнивать два словарных объекта для «упорядочивания». Но толкового определения «упорядочения» среди словарей практически нет. Python определяет один, но это довольно спорно. В этом особом случае словари не проходят тест на ортогональность?

Насколько ортогональна "достаточно ортогональна"? Что вам нужно увидеть, чтобы быть довольным степенью ортогональности в вашем языке.

Список неортогональных функций действительно длинный в большинстве языков программирования, например

• анонимные классы конфликтуют с java отражением
• конфликт между типом и стиранием типов с использованием java-отражения
• массивы несколько отличаются от других объектов из-за их особого типа, даже если они являются объектами.
• методы static и instance не совпадают, например, вы не можете переопределить статический метод
• вложенный класс - это запоздалая мысль
• влияние динамической и статической типизации на стратегию отправки сообщений (см., например, этот крайний случай в C #)
• и т.п.

Это лишь немногие, которые приходят мне в голову, но есть много других, а также на других языках.

Трудно гарантировать, что нет тонкого вмешательства между языковыми функциями. Как указывает CAR Hoare в своей статье «Советы по проектированию языка программирования»:

Часть языкового дизайна состоит из инноваций. Эта деятельность приводит к новым языковым возможностям в изоляции. Самая сложная часть языкового дизайна заключается в интеграции : выбор ограниченного набора языковых функций и их полировка до тех пор, пока в результате не получится согласованная простая структура, которая не имеет более грубых краев.

Вероятно, хорошим шагом для повышения ортогональности является объединение понятий (это идет в направлении ответа @ karl-bielfeld). Если все, например, список или объект, скорее всего, будет меньше конфликтов. Или вместо того, чтобы использовать вложенный класс в последующем, сделайте его основным элементом.

Большинство работ по языкам программирования доказывают определенные свойства языка (например, правильность типа) в подмножестве («ядре») языка, который формализован. Здесь мы должны сделать обратное, доказать, что все функции составлены безопасно. Кроме того, это означает, что нужно определить, что значит «сочинять». Это значит «бежать»? (В этом случае ссылка выше о граничном случае с динамической и статической типизацией является безопасной). Это значит быть "безопасным"? Означает ли это быть предсказуемым с точки зрения разработчика?

Все это очень интересно, но и очень сложно.