Что конкретно означает выразительная сила?

Выразительная сила определяется Википедией как:

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

Относятся ли «идеи» к вещам (операциям, структурам, алгоритмам и т. Д.?), Которые мы можем передать машине ? Или это относится к «человеческим» понятиям, которые можно уловить и передать с помощью языка другим людям?

Как оценивается и измеряется выразительная сила?

Например, если бы мы взяли язык, подобный JavaScript, и наложили странное ограничение на имена переменных, например, переменная должна быть 8-значным числом, которому предшествует подчеркивание, совпадение/^_[0-9]{8}$/ , потеряем ли мы выразительную силу?

Или это только абсурдно и раздражает?

Чтобы уточнить:

Выразительная сила измеряется общими идеями языка:

• целые числа и строки
• петли
• условными

Или количество конкретных , уникальных идей, которые язык может представлять:

• целые числа 1, 2 ... 2 ^ 32
• строки, содержащие "что говорит лиса?" и "тьфу тьфу тьфу тьфу тьфу тьфу пау"
• за каждую лягушку в моей коллекции лягушек
• если лягушка является зеленый или что - то , то что - то сделать

Matthias Felleisen (1991) - «Экспрессивная сила языков программирования» . Содержит математически строгое определение выразительности языка.

Интуитивно понятно, что если каждая программа, которая может быть написана на языке A, также может быть написана на языке B только с локальными преобразованиями, но есть некоторые программы, написанные на языке B, которые не могут быть написаны на языке A без изменения их глобальной структуры (т.е. чисто локальные преобразования), то язык Б является более выразительным , чем язык А .

Хорошим свойством этого определения является то, что оно допускает возможность того, что существуют пары языков, в которых есть программы на X, которые не могут быть выражены на Y, и программы на Y, которые не могут быть выражены на X , и, следовательно, языки различны, но ни язык более выразителен, чем другой. Это хорошо согласуется с нашим реальным опытом существования некоторых языков, которые хороши в одних вещах, и некоторых, которые хороши в других вещах, и ни один из них не является "лучше", чем другие.

Выразительная сила определяется Википедией как:

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

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

Относятся ли «идеи» к вещам (операциям, структурам, алгоритмам и т. Д.?), Которые мы можем передать машине? Или это относится к «человеческим» понятиям, которые можно уловить и передать с помощью языка другим людям?

Это относится к тому, что можно выразить на этом языке, рассматривая его как нечто само по себе.

Например, (я буду использовать javascript повсеместно для моих примеров, потому что ваш вопрос указывает, что это один из языков, которые вы знаете), рассмотрим выражение javascript:

var x = 3 + 4;

Это означает, что вычисляется сумма значений 3 и 4 и значение, связанное с меткой xв заданной области пространства имен.

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

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

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

Термин «выразительная сила» может использоваться в широком смысле. Это может означать меру идей, выражаемых на этом языке:

• независимо от легкости (теоретическая выразительность)

• кратко и с готовностью (практическая выразительность)

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

В неформальных дискуссиях термин часто относится ко второму смыслу или обоим. Это часто бывает при обсуждении языков программирования. Были предприняты усилия, чтобы формализовать эти неформальные использования термина

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

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

Например, если бы мы взяли язык, подобный JavaScript, и наложили странное ограничение на имена переменных, например, переменная должна представлять собой 8-значное число, которому предшествует подчеркивание, совпадение /^_[0-9]{8}$/, потеряли бы мы выразительную силу?

По формальному определению мы не утратили выразительной силы: мы ограничены 100 000 000 переменных, но если бы нам действительно было нужно, мы могли бы обойти это, создав объекты для хранения большего количества переменных во вновь созданном пространстве имен. Таким образом, любая программа, написанная сегодня на javascript, может быть переписана в этой новой форме, поэтому они одинаково выразительны.

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

Стоит также отметить, что люди неформально рассматривают вещи, которые не являются строго частью языка вообще. Рассмотрим изменения в Javascript от его создания до сегодняшнего дня.

По наиболее формальному определению, выразительность практически не изменилась; В конце концов, для начала это был полный Тьюринг.

По более неформальному определению, оно стало значительно более выразительным в некоторых вещах, таких как манипулирование массивами, обработка исключений и (возможно, больше всего) в включении регулярных выражений. Они не делают ничего, что не могло быть сделано в javascript раньше, хотя они часто могут делать что-то в несколько строк и время выполнения в секунду, что потребовало бы килобайт кода для записи в javascript1.0 и долгое время для запуска.

По гораздо более неформальному определению, опять же, по сравнению с первым использованием javascript в браузерах (возможность изменять значения входных данных формы, в document.writeто время как страница сначала анализируется и перемещается на новое место или возвращается назад или вперед в истории, но довольно больше ничего) к тому, что сегодня (в состоянии изменить практически все на странице, в том числе на основе данных от серверных вызовов), абсолютно необъятно, хотя большая часть этого относится не к javascript, а к объектным моделям и API, сделанным доступны, а не язык (например, vbscript в IE извлекли выгоду из этих изменений в равной степени).

На мой взгляд, последнее использование настолько неформально, что не совсем правильно, но это проблема неформальных определений.

По формальному определению, это действительно не стало более выразительным вообще.

Я не думаю, что правила именования переменных действительно отражают то, что подразумевается под «выразительностью». Я думаю, что «выразительность» относится к более фундаментальным вещам. Рассмотрим C # с Linq против C # до Linq, например. После добавления Linq стало возможным писать SQL-подобные запросы непосредственно в C #. Это намного более элегантно, чем предыдущие альтернативы, например, помещать SQL в строковые литералы и затем передавать его на сервер, или перебирать коллекцию, используя «for».

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

Как указано в статье Википедии, выразительная сила относится к набору программ, которые могут быть выражены на языке. Все, что вы считаете «языком программирования» (JavaScript, LISP, C #, Perl и т. Д.), По существу завершено по Тьюрингу, что означает, что они могут выражать все, что называется «вычислимым».

Однако должно быть совершенно ясно, что регулярные выражения не так выразительны, как обычный язык программирования. Кроме того, подстановочные знаки оболочки несколько менее выразительны, чем регулярные выражения.

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

Существует более простой и прямой способ понять выразительную силу, но сначала нам нужно установить, что мы подразумеваем под языками. Есть две дисциплины, которые изучают языки: лингвистика и автоматы. Оба согласились бы, что язык - это набор слов (конечных последовательностей), построенный из некоторого конечного алфавита с использованием конкатенации. Как правило, интересные языки (под интересными я имею в виду такие языки, которые мы можем интерпретировать полезным способом) также имеют набор правил, которые определяют, какие слова есть в языке, а какие нет. Обратите внимание, что выразительность может существовать только при наличии интерпретации.

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

Не вводите в заблуждение при использовании слова. Java-программа - это слово в языке Java (хотя оно может занимать несколько файлов, содержащих несколько строк символов, разделенных пробелами).

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

• Давайте определим язык A как все формулы, включающие сложение целых чисел.

• Давайте определим язык B как язык всех формул, включающих умножение целых чисел.

В обоих случаях мы запрещаем использование элемента идентичности. Таким образом, язык A содержит слова «1 + 1», «1 + 2», «1 + 3», «2 + 3» и так далее. Язык B содержит слова «2 * 2», «2 * 3», «2 * 4», «3 * 4» и так далее. Мы также назначаем обычные интерпретации для «*» и «+» (сложение целых чисел и умножение целых чисел) для соответствующих символов. Таким образом, интерпретация «1 + 1» равна 2, а интерпретация «2 * 2» - 4.

Теперь обратите внимание, что язык A является строго более выразительным, чем язык B, поскольку в целых числах верно, что умножение может быть приведено как повторное сложение, но в общем случае нет способа представить сложение как умножение.

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

TLDR: если функция отсутствует, но может быть выражена другими способами, это не является недостатком выразительности. Если вы можете представить алгоритм в своем уме или даже реализовать его на одном языке, но другой язык каким-то образом структурирован таким образом, что делает невозможным реализацию алгоритма, это проблема выразительности *.

Ограничения именования переменных не уменьшают выразительность (если только имен не так мало, что они не могут больше выражать все алгоритмы, и нельзя имитировать переменные с помощью чего-то вроде массивов + индексов).

Простой пример недостатка выразительной силы таков: вы должны do_homeworkи bring_down_trash. Это легко написать в коде:

do_homework();
bring_down_trash();

Это решение выглядит довольно простым, но на самом деле do_homeworkи bring_down_trashнеупорядоченным, можно также написать:

bring_down_trash();
do_homework();

Что в равной степени неточно, потому что это не говорит о том, что мы не собирались исполнять приказ. Мы также не хотим использовать темы. Мы хотим сказать что-то вроде этого:

compiler_or_interpreter_pick_one(
    {
        do_homework();
        bring_down_trash();
    },
    {
        bring_down_trash();
        do_homework();
    }
);

Насколько я знаю, это очень сложно и невозможно выразить любым языком программирования.

Пример, который не дает мне покоя, состоит в том, что в Java невозможно иметь массив объектов. Вы можете создать массив указателей на объекты, но с разным размером памяти (эффективность речи).

Возьмем пример из другого ответа : C ++ не поддерживает добавление методов к классу или экземпляру . Это правда, однако, это не ограничивает выразительность C ++.

struct Extensible{
    std::vector<std::function<void(Extensible *)>> instanceExtensions;
    static std::vector<std::function<void(Extensible *)>> classExtensions;
};

Это класс, в который вы можете добавлять, удалять и вызывать произвольное количество функций-членов для экземпляров и класса. Технически C ++, вероятно, более выразителен в этом отношении, чем языки программирования, которые фактически поддерживают эту функцию, потому что в C ++ вы можете выбрать, как хранить функции (вектор против массива против forward_list).

* В некоторых языках отсутствует выразительность как особенность. Как правило, они делают невозможным писать бесконечные циклы. Это может решить проблему остановки и позволить автоматическое подтверждение правильности.