Универсальные языки программирования

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

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

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

Скелетный язык

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

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

Конечно же, транслятор нашего скелетного языка должен уметь отличать имена переменных от других элементов. Это делается за счет разработки синтаксиса скелетного языка таким образом, чтобы роль любого терма определялась исключительно синтаксисом. Для этой цели мы принимаем, что имена переменных должны начинаться с буквы английского алфавита, за которой может следовать любая комбинация букв и цифр (от 0 до 9). Следовательно, в качестве имен переменных можно использовать строки XYZ, B747, abcdefghi и X5Y, тогда как имена 2G5,1о и х.у недопустимы.

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

11.3.2 Существуют ли инопланетяне?

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

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

Каждый из трех операторов присваивания требует изменения содержимого переменной, используемой в операторе. Первый из них позволяет помещать в переменную строку нулей. Его синтаксис:

clear name;

где name — любое имя переменной.

Оставшиеся операторы присваивания являются антиподами:

incr name:

и

deer name:

Здесь name также является любым именем переменной. Первый из этих операторов увеличивает значение указанной переменной на единицу. Термин i ncr (increment) обозначает интерпретацию битовой последовательности как целого двоичного числа и изменение последовательности, чтобы она представляла целое значение на единицу больше. Например, если с переменной Y до выполнения оператора incr Y:

была связана последовательность 101, то после выполнения оператора значение переменной Y представляет последовательность 110. То есть к значению переменной Y была добавлена единица.

В свою очередь, оператор deer (decrement) используется для уменьшения значения указанной переменной на единицу. Исключением является лишь случай, когда значение переменной равно нулю, тогда оператор не изменяет значения. Таким образом, если до выполнения оператора deer Y:

с переменной Y было связано значение 101, то после его выполнения это значение равно 100. Если же значение переменной Y было равно нулю перед выполнением оператора, оно не изменится и останется равным нулю.

В скелетном языке есть только одна управляющая структура, представленная парой операторов while-end. Последовательность операторов while name not 0 do:

end:

(где name — это любое имя переменной) обозначает, что любой оператор или набор операторов между словами while и end выполняется до тех пор, пока значение переменной name не станет равным нулю. Более точно, когда структура while-end появляется во время выполнения программы, значение указанной переменной сначала сравнивается с нулем. Если оно равно нулю, структура пропускается и выполнение продолжается с оператора, следующего за end. Если же значение переменной не равно нулю, выполняется последовательность операторов внутри структуры while-end, и управление возвращается оператору while, после чего снова выполняется сравнение. Обратите внимание, что часть ответственности за управлению еиклом лежит на программисте, который должен явно изменять значение переменной в теле цикла, чтобы избежать бесконечного выполнения цикла. Например, последовательность

incr X:

while X not 0 do;

incr Z; end:

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

clear Z:

while X not 0 do;

incr Z:

deer X: end;

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

Обратите внимание, что операторы while и end должны всегда использоваться в паре, причем первым должен идти оператор whi I e. Однако пара операторов while-end может появиться среди инструкций, которые повторяются внутри другой пары while-end. В таком случае разбиение на пары операторов while и end выполняется путем просмотра написанной программы от начала до конца и соотнесения каждого оператора end с ближайшим предшествующим оператором while, для которого пара еще не найдена. Хотя этого не требует синтаксис, мы часто используем отступы для улучшения читаемости подобных структур.

Приведем последний пример. Последовательность инструкций (листинг 11.1) приводит к тому, что произведение значений переменных X и Y присваивается переменной Z, а побочным эффектом программы является изменение значения X, если оно не равно нулю. (Структура while-end, которой управляет переменная W, восстанавливает исходное значение переменной Y.)

Листинг 11.1. Программа на скелетном языке для умножения X на Y

clear Z:

while X not 0 do: clear W:

while Y not 0 do; incr Z; incr W; deer Y: end;

while W not 0 do; incr Y; deer W: end; deer X; end;

Программирование на скелетном языке

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

Для начала заметим, что при помощи комбинации операторов присваивания данной переменной можно назначить любое значение (любую битовую комбинацию). Например, следующая последовательность присваивает комбинацию битов 11 (бинарное представление 3) переменной X, для чего сначала удаляет ее предыдущее значение и затем увеличивает значение на единицу три раза:

i

clear X; incr X: incr X;

incr X;

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

clear Z:

while X not 0 do:

incr Z:

deer X; end;

передает значение, связанное с X, в переменную Z. Однако у этой программы есть побочный эффект — она разрушает исходное значение X. Чтобы исправить эту ошибку, мы можем ввести вспомогательную переменную, которой присвоим в начале программы рассматриваемое значение. Затем эта вспомогательная переменная будет использоваться как источник данных, из которого мы восстановим исходную переменную, одновременно помещая нужное значение в целевую переменную. Таким образом, присваивание переменной Tomorrow значения переменной Today можно выполнить при помощи последовательности команд, приведенных в листинге 11.2.

Листинг 11.2. Реализация команды «скопироватьToday в Tomorrow» на скелетном языке

clear Aux; clear Tomorrow; while Today not 0 do;

incr Aux;

deer Today: end; while Aux not 0 do;

incr Today;

incr Tomorrow;

deer Aux; end;

Мы будем использовать синтаксис copy namel to name2;

(где namel и name2 — имена переменных) для краткого обозначения структуры операторов, приведенной в листинге 11.2. Поэтому, хотя в скелетном языке не существует явной команды копирования, мы будем писать программы так, как если бы она существовала, понимая, что для преобразования таких неформальных программ в настоящие программы на скелетном языке нам понадобится заменить операторы сору на эквивалентные структуры while-end с использованием вспомогательной переменной, имя которой не встречается где-либо еще в программах.