Язык программирования, где каждое выражение имеет смысл

В соответствии с рекомендацией я публикую это из Переполнения стека .

Недавно я думал о следующей проблеме.

Рассмотрим код для стандартного "Hello world!" программа:

main()
{
    printf("Hello World");

}

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

main(5
{
    printf("Hello World");

}

Теперь к актуальному вопросу. Существует ли язык программирования, где каждая возможная комбинация символов - то есть каждое выражение - имеет смысл? Я попытался придумать какое-то решение и придумал два:

1. Постфикс с ограниченным количеством переменных. По сути, все переменные уже определены до того, как вы напишите какой-либо код, и вам придется работать только с ними. Теоретически вы можете выполнить произвольное количество операций, сформировав цепочку из множества простых программ, каждая из которых передает результаты другим. Код можно записать в виде последовательности символов в постфиксной нотации;

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

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

У кого-нибудь есть другие идеи, как решить эту проблему?

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

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

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

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

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

$n$$n$

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

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

Разработка языка программирования, в котором каждое выражение имеет смысл способом «вы можете его выполнить», не особенно полезна. Хороший язык программирования - это не просто язык, на котором обезьяна может печатать на клавиатуре и написать правильную программу, а тот, где программист может легко написать программу, которую они намеревались написать. Написание действительных программ - не сложная часть программирования: сложная часть - написание программы, которая выполняет то, что от нее ожидали. Отказ от явно некорректных программ очень полезен в этом отношении.

Другим способом решения этой проблемы является полное определение семантики всех возможных входных данных, включая указание того, какие ошибки времени компиляции, загрузки или времени выполнения должны генерироваться для каждого ввода, если таковые имеются. То есть «отмена программы после печати Syntax error at line 42в стандартном потоке ошибок» является частью определенной семантики языка. Каждое выражение «имеет смысл» в том смысле, что оно имеет определенное значение. Это полезный смысл? Возможно - в конце концов, если программа явно неправильна, отклонение это полезно.

Проверьте Jot , полный по Тьюрингу язык, основанный на комбинаторной логике, где каждая последовательность из 0 и 1 (включая пустую последовательность) является допустимой программой.

Один хороший пример - пробелы . В собственном языке допустимы любые комбинации операторов. Операторы: пробел, табуляция и новая строка (в частности, "\ n"). Все остальные персонажи считаются комментариями .

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

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

Во - первых , аллюзия Cort Аммона к генетике пятно на: преобразования программы в вопросе (заменив )на 5) можно увидеть , как мутации . Этот вид манипуляции распространен в области эволюционных вычислений ; в частности, генетические алгоритмы выполняют такие преобразования над строками , в то время как генетическое программирование преобразует программы . В любом случае мы обычно хотим присвоить значение каждой возможности, так как это даст наиболее компактное пространство поиска.

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

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

• Если есть какая-то структура в языке, например. мы можем присвоить значение подстрокам, это может быть потеряно при переводе в натуральные числа. В этом случае мы можем предпочесть использовать строки, чтобы рассуждать и преобразовывать подстроки локально, а не представлять целую программу как число. Это аналогично тому, как мы можем предпочесть использовать побитовые операции над целыми числами, а не арифметическими выражениями, когда каждый бит имеет индивидуальное значение. Это в основном обобщение эволюционного сценария.
• Мы можем создавать программы по запросу; например, мы могли бы начать выполнение программы, которая полностью не определена, и генерировать (например, случайным образом) отдельные инструкции (например, символы), когда / если указатель инструкции достигает их. Это распространено в алгоритмической теории информации, где программа представляет собой ленту Тьюринга, и ее цель - охарактеризовать поведение случайно сгенерированных программ. Например, мы можем сформулировать Соломонова перед произвольными строками как вероятность того, что универсальная машина Тьюринга со случайной лентой выведет эту строку.

Что касается примеров языков, многие эволюционные вычислительные системы основаны на языках стека, таких как семейство Push . Они, как правило, допускают произвольные потоки токенов (которые мы могли бы представлять как отдельные символы). Иногда (как в примере с Brainfuck в BrainSlugs83) существуют ограничения на балансировку скобок; Однако, мы можем связать это с саморазграничны программами , в том , что строка , как [не может быть действительной программой , но она является действительным префиксом программы . Если мы представим, что компилятор / интерпретатор читает исходный код из stdin, то он не будет отклонять строку наподобие этого [, он просто будет ждать большего ввода, прежде чем продолжить.

Такие языки, как двоичная комбинаторная логика и двоичное лямбда-исчисление, возникли непосредственно из работы над алгоритмической теорией информации, например. от http://tromp.github.io/cl/cl.html

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

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

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

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

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

Это достигается с помощью этих двух простых методов:

1. Все команды, которые он понимает, представляют собой один байт (в BF все они, например, одиночные символы ASCII *).

2. Все символы, которые он не понимает, он отбрасывает как комментарии.

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

*: Оказывается, что не все команды BF представляют собой один байт ASCII, т. Е. Квадратные скобки ДОЛЖНЫ совпадать, так что язык там не соответствует первым критериям. - Но любой язык, который соответствует обоим критериям, будет соответствовать тому, о чем просит ФП.