М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 5

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

Текст из файла (страница 5)

Машины Тьюринга чрезвычайно просты; если воспользоваться синтак­сисом языка С, то объявления данных будут выглядеть так:

char tape[...];

int current = 0;

где лента (tape) предполагается бесконечной. Программа состоит из любого числа операторов вида:

L17: if (tape[currentj == 'g') {

tape[current++] = 'j'i

goto L43;

}

Оператор машины Тьюринга выполняется за четыре следующих шага.

• Считать и проверить символ в текущей ячейке ленты.

• Заменить символ на другой символ (необязательно).

• Увеличить или уменьшить указатель текущей ячейки.

• Перейти к другому оператору.

Согласно Тезису Черча — Тьюринга, любое вычисление, которое действи­тельно можно описать, может быть запрограммировано на этой примитивной машине. Интуитивная очевидность Тезиса опирается на два утверждения:

• Исследователи предложили множество моделей вычислений, и было до­казано, что все они эквивалентны машинам Тьюринга.

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

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

1.9. Упражнения

1. Опишите, как реализовать компилятор для языка на том же самом язы­ке («самораскрутка»).

2. Придумайте синтаксис для APL-подобного языка для матричных вы­числений, используя обычные символы.

3. Составьте список полезных команд над строками и сравните ваш список со встроенными командами языков Snobol и Icon.

4. Составьте список полезных команд над множествами и сравните ваш список со встроенными командами языка SETL.

5. Смоделируйте (универсальную) машину Тьюринга на нескольких язы­ках программирования.

Глава 2

Элементы

языков программирования

2.1. Синтаксис

Как и у обычных языков, у языков программирования есть синтаксис:

Синтаксис языка (программирования) — это набор правил, которые опре­деляют, какие последовательности символов считаются допустимыми вы­ражениями (программами) в языке.

Синтаксис задается с помощью формальной нотации.

Самая распространенная формальная нотация синтаксиса — это расширен­ная форма Бекуса — Наура (РБНФ). В РБНФ мы начинаем с объекта самого верхнего уровня, с программы, и применяем правила декомпозиции объектов, пока не достигнем уровня отдельного символа. Например, в языке С синтак­сис условного оператора (if-оператора) задается правилом:

if-onepamop :: = if (выражение) оператор [else оператор]

Имена, выделенные курсивом, представляют синтаксические категории, а имена и символы, выделенные полужирным шрифтом, представляют факти­ческие символы, которые должны появиться в программе. Каждое правило содержит символ «:: =», означающий «представляет собой». Прочие символы используются для краткости записи:

[ ] Не обязательный {} Ноль или более повторений | Или

Таким образом, else-оператор в if-операторе не является обязательным. Использование фигурных скобок можно продемонстрировать на (упрощен­ном) правиле для объявления списка переменных:

Объявление-переменной ::= спецификатор-типа идентификатор {, идентификатор};

Это читается так: объявление переменной представляет собой специфика­тор типа, за которым следует идентификатор (имя переменной) и необяза­тельная последовательность идентификаторов, предваряемых запятыми, в конце ставится точка с запятой.

Правила синтаксиса легче изучить, если они заданы в виде диаграмм (рис. 2.1). Круги или овалы обозначают фактические символы, а прямоугольники — синтаксические категории, которые имеют собственные диаграммы.

.

Последовательность символов, получаемых при последовательном прохожде­нии пути на диаграммах, является (синтаксически) правильной программой.

Хотя многие программисты страстно привязаны к синтаксису опреде­ленного языка, этот аспект языка, пожалуй, наименее важен. Любой разумный синтаксис легко изучить; кроме того, синтаксические ошибки об­наруживаются компилятором и редко вызывают проблемы с работающей программой. Мы ограничимся тем, что отметим несколько возможных син­таксических ловушек, которые могут вызвать ошибки во время выполнения программы:

Будьте внимательны с ограничениями на длину идентификаторов. Ес­ли значимы только первые 10 символов, то current_winner и current _width будут представлять один и тот же идентификатор.

Многие языки не чувствительны к регистру, то есть СЧЕТ и счет пред-ставляют одно и то же имя. Язык С чувствителен к регистру, поэтому эти имена представляют два разных идентификатора. При разработке чувст­вительных к регистру языков полезно задать четкие соглашения по ис­пользованию каждого регистра, чтобы случайные опечатки не приводи­ли к ошибкам. Например, по одному из соглашений языка С в програм­ме все записывается на нижнем регистре за исключением определенных имен констант, которые задаются на верхнем регистре.

Существуют две формы комментариев: комментарии в языках Fortran, Ada и C++ начинаются с символа (С, - -, и //, соответственно) и распро­страняются до конца строки, в то время как а языках С и Pascal коммента­рии имеют как начальный, так и конечный символы: /* ... */ в.С и (* ... *) иди {...} в Pascal. Вторая форма удобна для «закомментаривания» неис-пользуемого кода (который, взможнo, был вставлен для тестированя), но при этом существует опасность пропустить конечный символ, в результате чего будет пропущена последовательность операторов:

/* Комментарий следовало бы закончить здесь

а = b + с; Оператор будет пропущен

/*...*/ Здесь конец комментария

Остерегайтесь похожих, но разных символов. Если вы когда-либо изуча­ли математику, то вас должно удивить, что знакомый символ «=» ис­пользуется в языках С и Fortran как оператор присваивания, в то время как новые символы «==» в С и «.eq.» в Fortran используются в качестве операции сравнения на равенство. Стремление написать:

if(a=b)...

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

В качестве исторического прецедента напомним известную проблему с синтаксисом языка Fortran. Большинство языков требует, чтобы слова в программе отделялись одним или несколькими пробелами (или другими пробельными символами типа табуляции), однако в языке Fortran пробель­ные символы игнорируются. Рассмотрим следующий оператор, который определяет «цикл до метки 10 при изменении индекса i от 1 до 100»:

do 10 i = 1,100

Если запятая случайно заменена точкой, то этот оператор становится на самом деле.оператором присваивания, присваивая 1.100 переменной, имя которой образуется соединением всех символов перед знаком «=»:

do10i = l.TOO

Говорят, эта ошибка заставила ракету взорваться до запуска в космос!

2.2. Семантика

Семантика — это смысл высказывания (программы) в языке (программи­рования).

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

The pig is in the pen. (Свинья в загоне.)

The ink is in the pen. (Чернила в ручке.)

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

Формализованная нотация семантики языков программирования выходит за рамки этой книги. Мы только кратко изложим основную идею. В любой точ­ке выполнения программы мы можем описать ее состояние, определяемое: (1) указателем на следующую команду, которая будет выполнена, и (2) содержимым памяти программы. Семантика команды задается описанием изменения состо­яния, вызванного выполнением команды. Например, выполнение:

а:=25

заменит состояние s на новое состояние s', которое отличается от s только тем, что ячейка памяти а теперь содержит 25.

Что касается управляющих операторов, то для описания вычисления используется математическая логика. Предположим, что мы уже знаем смыслы двух операторов S1 и S2 в произвольном состоянии s. Обозначим это с по­мощью формул р (S1, s) и р (S2, s) соответственно. Тогда смысл if-оператора:

if С then S1 elseS2

задается формулой:

(C(s)=>p(S1,s))&((-C(s)=>p(S2,s))

Если вычисление С в состоянии s дает результат истина, то смысл if-опера­тора такой же, как смысл S1; в противном случае вычисление С дает результат не истина и смысл if-оператора такой же, как у S2.

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

Проверяется условие после if; если результат — истина, выполняется сле­дующий после then оператор, иначе выполняется оператор, следующий за else.

Формализация семантики языков программирования дает дополнитель­ное

преимущество — появляется возможность доказать правильность про­граммы. По сути, выполнение программы можно формализовать с помощью Кксиом, которые описывают, как оператор преобразует состояние, удовлетво­ряющее утверждению (логической формуле) на входе, в состояние, которое Удовлетворяет утверждению на выходе. Смысл программы «вычисляется» пу-тем построения входных и выходных утверждений для всей программы на ос­нове утверждений для отдельных операторов. Результатом является доказа­тельство того, что если входные данные удовлетворяют утверждению на входе, то выходные данные удовлетворяют утверждению на выходе.

Конечно, «доказанную» правильность программы следует понимать лишь относительно утверждений на входе и выходе, поэтому не имеет смысла доказывать, что программа вычисляет квадратный корень, если вам нужна программа для вычисления кубического корня! Тем не менее верификация про­граммы применялась как мощный метод проверки для систем, от которых требуется высокая надежность. Важнее то, что изучение верификации поможeт вам писать правильные программы, потому что вы научитесь мыслить, исходя из требований правильности программы. Мы также рекомендуем изучить и использовать язык программирования Eiffel, в который включена под­держка утверждений (см. раздел 11.5).

2.3. Данные

При первом знакомстве & языками программирования появляется тенденция сосредоточивать внимание на действиях: операторах или командах. Только изучив и опробовав операторы языка, мы обращаемся к изучению поддержки, которую обеспечивает язык для структурирования данных. В современных взглядах на программирование, особенно на объектно-ориентированное, опе­раторы считаются средствами манипулирования данными, использующимися для представления некоторого объекта. Таким образом, следует изучить аспек­ты структурирования данных до изучения действий.

Программы на языке ассемблера можно рассматривать как описания действий, которые должны быть выполнены над физическими сущностями, такими как ячейки памяти и регистры. Ранние языки программирования продолжили эту традицию идентифицировать сущности языка, подобные переменным, как слова памяти, несмотря на то, что этим переменным припи­сывались математические атрибуты типа целое. В главах 4 и 9 мы объясним, почему int и float — это не математияеское, а скорее, физическое представле-

ние памяти.

Теперь мы определим центральную концепцию программирования:

Тип — это множество значений и множество операций над этими значениями.

Правильный смысл int в языке С таков: int — это тип, состоящий из конеч­ного множества значений (количестве примерно 65QOQ или 4 миллиардов, в зависимости от компьютера) и набора операций (обозначенньгх, +, < =, и т.д.) над этими значениями. В таких современных языках программирования, как Ada и C++, есть возможность создавать новые типы. Таким образом, мы боль­ше не ограничены горсткой типов, предопределенных разработчиком языка; вместо этого мы можем создавать собственньхе типы, которые более точно.со-ответствуют решаемой задаче.

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

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

Значение. Простейшее неопределяемое понятие.

Литерал. Конкретное значение, заданное в программе «буквально», в виде последовательности символов, например 154, 45.6, FALSE, 'x', "Hello world".

Представление. Значение, представленное внутри компьютера конкретной строкой битов. Например, символьное значение, обозначенное 'х', мо­жет представляться строкой из восьми битов 01111000.

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

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

Объект. Объект — это переменная или константа.

Характеристики

Список файлов книги