Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17




НазваниеСодержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17
страница74/78
Дата конвертации11.12.2012
Размер5.58 Mb.
ТипРеферат
1   ...   70   71   72   73   74   75   76   77   78

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


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

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

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

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


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

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

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

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

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


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

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

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

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 с использованием вспомогательной переменной, имя которой не встречается где-либо еще в программах.

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


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

incr X:

выполняет вычисление той же функции (функции следования), которая вычисляется машиной Тьюринга в примере из раздела 11.2. Действительно, она увеличивает на единицу значение, присвоенное переменной X. Аналогично, если считать переменные X и Y входами, а переменную 1 — выходом программы

copy Y to Z; while X not 0 do;

incr Z;

deer X; end;

то можно сказать, что она выполняет функцию сложения.

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

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

Хотя скелетный язык неудобно применять в реальных условиях, подобные ему языки широко применяются в теории вычислительной техники. Например, в приложении Д мы используем скелетный язык в качестве инструмента для исследования вопроса об эквивалентности итеративных и рекурсивных структур, поднятого в главе 4. Мы узнаем, что наше предположение об их эквивалентности на самом деле подтверждается.
1   ...   70   71   72   73   74   75   76   77   78

Похожие:

Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconОсновы работы с Sharepoint в какое место веб-страницы разрешается вставить новую веб-часть (в браузере)?
В какое представление веб-страницы будут вноситься изменения, если выбрать команду Настроить эту страницу?
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВведение в физику и технологию элементной базы ЭВМ и компьютеров
Введение   8
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСодержание
Содержание размещают после титульного листа отчёта (как правило, на стр. 2). Слово «Содержание» рас­полагают посередине страницы...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСоздание веб-страницы в простом текстовом редакторе
Давайте создадим  веб-страницу. Для этого нужно напечатать ее исходный код в простом текстовом редакторе  блокнот
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЗагрузка uploading теория
После того как набор html страниц веб-сайта создан. Все они связаны между собой с помощью ссылок. Страницы наполнены контентом. Таким...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЛитература 153 Алфавитный указатель 155 Предисловие редактора русского издания Глубокоуважаемые коллеги! Содержа­ние этой книги значительно шире и глуб­же, нежели заявлено в ее названии. Я бы назвала ее «Лечение и реставрация молочных зубов»
Предисловие редактора русского издания 6 Введение 9 Предисловие 11 Благодарности 13
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 icon        Информатика  Системы счисления и  арифметические основы эвм  
Введение   
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЯндекс - поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости, картинки, статьи
Яндекс — поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости,...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Разместите кнопку на своём сайте:
kak.znate.ru


База данных защищена авторским правом ©kak.znate.ru 2012
обратиться к администрации
KakZnate
Главная страница