Уолтер Брайт использовал слово "избыточность"... или "Что это значит?"

Итак, я читаю это интервью с Уолтером Брайтом о языке D в Побитом (http://www.bitwisemag.com/copy/programming/d/interview/d_programming_language.html), и я сталкиваюсь с этим на самом деле интересная цитата о разборе языка:

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

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

Я едва могу окутать голову в последнюю часть, где он упоминает, что возможно иметь язык, в котором "любая случайная последовательность символов является допустимой программой". Меня учили, что есть три типа ошибок: синтаксический, run-time и semantic. Существуют ли языки, в которых единственно возможные ошибки являются семантическими? Есть такая сборка? Как насчет машинного кода?

Ответы

Ответ 1

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

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

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

Ответ 2

Я сосредоточусь на том, почему (я думаю) Вальтер Брайт считает, что избыточность - это хорошо. В качестве примера возьмем XML. Этот фрагмент:

<foo>...</foo>

имеет избыточность, закрывающий тег является избыточным, если вместо этого использовать S-выражения:

(foo ...)

Это короче, и программисту не нужно вводить foo чаще, чем необходимо, чтобы понять этот фрагмент. Меньше избыточности. Но у него есть минусы, как пример из http://www.prescod.net/xml/sexprs.html:

(document author: "[email protected]"
    (para "This is a paragraph " (footnote "(better than the one under there)" ".")
    (para "Ha! I made you say \"underwear\"."))


<document author="[email protected]">
<para>This is a paragraph <footnote>(just a little one).</para>
<para>Ha! I made you say "underwear".</para>
</document>

В обоих случаях отсутствует конечный тег/закрывающий палец для сноски. Версия xml недействительна, как только синтаксический анализатор видит </para>. Выражение S-Expression недействительно только в конце документа и только в том случае, если в другом месте у вас нет ненужного закрывающего пара. Таким образом, избыточность помогает, в некоторых случаях, вызывать то, что имел в виду писатель (и указывать на ошибки в его способе выражения этого).

Ответ 3

nglsh nclds ll srts из xtr ltrs t mk it ezr t read

Ответ 4

Хорошо, использовать пример из С# (так как я не знаю D). Если у вас есть класс с абстрактным методом, сам класс должен быть помечен как абстрактный:

public abstract class MyClass
{
    public abstract MyFunc();
}

Теперь было бы тривиально, чтобы компилятор автоматически маркировал MyClass как абстрактный (то есть способ, которым С++ обрабатывает его), но в С# вы должны делать это явно, чтобы ваши намерения были ясными.

Аналогично методам virtual. В С++, если объявить виртуальным в базовом классе, метод будет автоматически виртуальным во всех производных классах. В С# метод должен, тем не менее, быть явно помеченным override, поэтому нет путаницы в том, что вы хотели.

Ответ 5

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

В bash (shell script) он выглядит так:

if [ cond ]; then
  stmts;
elif [ other_cond ]; then
  other_stmts;
else
  other_other_stmts;
fi

в C (w/одиночные записи, без фигурных скобок):

if (cond)
  stmt;
else if (other_cond)
  other_stmt;
else
  other_other_stmt;

Вы можете видеть, что в bash в выражении if имеется гораздо больше синтаксической структуры, чем в C. Фактически, все структуры управления в bash имеют свои собственные ограничители (например, if/then/fi, for/do/done, case/in/esac,...), тогда как в C используется фигурная скобка везде. Эти уникальные разделители устраняют смысл кода и тем самым обеспечивают контекст, из которого интерпретатор/компилятор может диагностировать условия ошибки и сообщать об этом пользователю.

Есть, однако, компромисс. Программисты обычно предпочитают краткий синтаксис (a la C, Lisp и т.д.) Для подробного синтаксиса (a la Pascal, Ada и т.д.). Однако они также предпочитают описательные сообщения об ошибках, содержащие номера строк/столбцов и предлагаемые разрешения. Эти цели, конечно, расходятся друг с другом - вы не можете иметь свой торт и есть его (по крайней мере, сохраняя внутреннюю реализацию компилятора/интерпретатора просто).

Ответ 6

Это означает, что синтаксис содержит больше информации, чем необходимо для кодирования рабочей программы. Примером могут служить прототипы функций. Как показывает нам K & R C, они избыточны, потому что компилятор может просто позволить вызывающему абоненту нажимать любые аргументы, которые вы хотите включить, а затем позволить функции вызывать правильные аргументы. Но С++ и другие языки требуют их, потому что они помогают компилятору проверить, что вы правильно вызываете функцию.

Другим примером является требование объявить переменные перед их использованием. Некоторые языки имеют это, в то время как другие - нет. Это явно избыточно, но часто помогает предотвратить ошибки (например, орфографические ошибки, используя удаленную переменную).

Ответ 7

Я думаю, что лучшим примером избыточности является что-то вроде int a[10] =. На этом этапе компилятор знает, что должно получиться дальше, инициализатор массива int и может вызвать соответствующее сообщение об ошибке, если последующее не является инициализатором массива int. Если в синтаксисе языка указано, что что-то может следовать за int a[10], компилятору будет сложнее разобраться с проблемами.

Ответ 8

то любая случайная последовательность символов является допустимой программой.

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