/
Текст
1969 Г
математика
кибернетика
язык
АВТОМАТОВ
А. В. ШИЛЕЙКО,
доцент, кандидат технических наук
ЯЗЫК
АВТОМАТОВ
(Об алгоритмических языках для программирования
электронных вычислительных машшн)
Издательство «Знание» Москва 1969
ЬФОА
Ш58
ОТ АВТОРА
Эту маленькую брошюру ни в коем случае не следует рассматривать
как попытку систематического описания хотя бы одного из современных
символических языков или как руководство к их практическому
использованию. Еще в меньшей степени автор ставил себе целью изложить здесь
основы структурной или математической лингвистики. Единственная цель
брошюры — дать общее представление о современном состоянии
символических языков для программирования автоматов и некоторых главных
идеях, формирующихся в этой области. Автору хотелось сделать
понятными следующие два утверждения:
— даже самый примитивный язык автомата обладает, пусть в
зачаточной стадии, всеми характерными особенностями языка;
— .переход к языку более высокого уровня требует в общем случае не
усложнения автомата, а только сообщения этому автомату большего
количества сведений, причем эти сведения опять-таки требуют для своего
выражения специального языка.
Понять — в большой степени означает привыкнуть, поэтому автор
настойчиво советует читателю подробно разобрать все приводимые в
дальнейшем примеры, хотя на первых порах это будет требовать определенной
затраты труда, а главное — внимания.
ОГЛАВЛЕНИЕ
Стр.
Глава 1. Несколько слов о языке 3
Глава 2. Внутренний язык цифровой вычислительной
машины 8
Глава 3. Машинно-ориентированные языки .... 16
Глав.а 4. Простейшие проблемно-ориентированные
языки 27
Г л а в а 5. Язык АЛГОЛ-60 36
Глава 6. И еще несколько языков 46
Алексей Вольдемарович ШИЛЕЙКО
ЯЗЫК АВТОМАТОВ
Редактор В. Ю. Иваницшй
Художник Л. П. Ромасенко
Худож. редактор Е. Е. Соколов
Техн. редактор Е. М. Лопухова
Корректор Н. Д. Мелешкина
А 09038. Сдано в набор 15/V 1969 г. Подписано к печати 17/VII 1969 г.
Формат бумаги 60Х901,б. Бумага типографская N* 3. Бум. л. 1,5.
Печ. л. 3,0. Уч.-изд. л. 3,72. Тираж 35 700 экз. Издательство «Знание».
Москва, Центр, Новая пл., д. 3/4. Заказ 1214. Типография изд-ва
«Знание». Москва, Центр, Новая пл., д. 3/4.
Цена 9 коп.
3-3-14
Глава 1
Несколько слов о языке
Что та.кое язык? Еще несколько лет тому назад на такой
вопрос можно было дать единственный ответ: язык — это
средство общения людей. В настоящее время имеются
достаточные основания к тому, чтобы определять язык не только
как средство общения людей, но и как средство общения
между людьми и автоматами. Можно пойти даже несколько
дальше и говорить о существовании особых языков, на
которых автоматы общаются между собой.
Что такое общение? В процессе общения люди (и
автоматы) обмениваются информацией. Таким образом, мы
подходим к третьему, и самому существенному, вопросу: что такое
информация? Ответ на этот вопрос требует некоторой
подготовки.
Возьмем, например, слово «погода». Представим себе, что
мы очутились в мире, где погода никогда не меняется. Пусть
в этом мире повсюду и всегда светит солнце, температура
повсюду и всегда равна, окажем, +22°С, давление 760 мм
рт. ст., влажность 70%. Ясно, что в языке обитателей этого
мира не может быть слова «погода». Необходимость в
понятии «погода» возникает именно потому, что погода может
изменяться. В процессе общения друг с другом мы передаем
информацию о погоде, говоря, например, завтра будет
хорошая погода, сегодня после обеда обещали дождь и т. п.
Совершенно аналогичным образом, если бы, например, все
деревья были абсолютно похожи друг на друга и относились к
одному и тому же виду, во всех языках жителей Земли
отсутствовали бы такие слова, как липа, клен, сосна, а также
такие словосочетания, как «большое дерево», «ветвистое
дерево», «красивое дерево» и т. п. Наконец, если бы все люди
могли передвигаться только с одной строго определенной
скоростью в языках отсутствовали бы такие слова, как «бе-
з
жать», «скакать», «плестись». Перечень подобных примеров
можно продолжить сколь угодно далеко.
Потребность IB информации возникает в тех случаях,
когда «необходимо 'передать сведения об изменениях ib
окружающем нас мире или же, когда необходимо произвести акт
выбора среди некоторого разнообразия предметов или
понятий. Язык же в .любой из его форм и служит средством
выражения и передачи этих сведений. Не случайно (поэтому, как
бы ни отличались друг от друга различные языки по своему
словарному составу и (Грамматике, состав предложения
.практически -во всех языках, как в существующих ныне, так и в
существовавших ранее, один и тот же. Прежде всего в любом
языке имеются слова, обозначающие предмет, который
совершает или над которым совершается действие. Во-вторых,
это слова, обозначающие само действие. Наконец, имеются
группы слов, которые позволяют уточнять описания
предметов или действий, позволяют описывать условия, в .которых
совершается действие, или сообщать некоторые
дополнительные подробности. Существуют также вспомогательные слова,
часть слов или символы, отражающие некоторые правила, по
которым строится предложение.
Полный перечень слов некоторого данного языка
составляет его словарь. Чем больше слов, тем богаче словарь.
Известно, что по богатству словаря различные языки
достаточно сильно отличаются друг от друга. Поэтому возникает еще
один чрезвычайно важный вопрос: сколько же слов должно
быть в словаре? Развивая последовательно начатые нами
рассуждения, мы должны были бы ответить на этот вопрос
так: слов, обозначающих предметы, должно быть по
меньшей мере столько же, сколько различных предметов имеется
в окружающем нас мире, а слов, описывающих действия,
должно быть по меньшей мере столько же, сколько
различных действий может -совершаться. Однако окружающий нас
мир бесконечно разнообразен, и в каждом языке имеются
средства, позволяющие обозначать отдельные предметы или
действия, а также условия, в которых совершаются эти
действия, не одним словом, а несколькими словами, имеющими
между собой смысловую и грамматическую связь. Если
словарь содержит некоторый необходимый минимум слов, а в
рамках самого языка имеются правила, позволяющие
образовывать разнообразные словосочетания, то язык может быть
использован для описания всего многообразия окружающего
нас мира. Другое дело, что это не всегда оказывается
удобным. Поэтому обычно делается так. Каждый раз, когда
человек впервые сталкивается с не^топым неизвестным доселе
«предметом или явлением, он вначале описывает его
несколькими словами, а иногда и несколькими предложениями.
Если же это явление повторяется несколько раз и становится
обычным, то для его описания придумывается новое слово.
4
Важное свойство языка состоит в том, что всякий язык
динамичен, в нем «непрерывно происходят процессы рождения
новых 'Слов, а также отмирания и переосмысливания старых,
необхдоимооть в употреблении .которых отпаша.
Структурной единицей языка является слово. По
определенным (правилам слова объединяются в предложения.
Каждое предложение выражает отдельную законченную мысль.
С другой стороны, слова состоят из отдельных буке. Полный
перечень букв, используемых для построения слов в данном
языке, называется алфавитом этого языка. Структурно два
различных слова должны отличаться друг от друга хотя бы
одной буквой. Однако известно, что одно и то же слово очень
часто может выражать различные понятия, поэтому по
смыслу слова могут отличаться друг от друга не только тем, из
каких 'букв они состоят и в -каком порядке эти буквы
расположены, но и тем, в сочетании с какими другими словами
встречается данное слово.
/Важнейшим свойством языка является также его
динамичность, проявляющаяся прежде всего в непрерывном
обновлении словаря.
Перейдем теперь к языкам, которые служат для обмена
информацией между человеком и искусственно созданными
механизмами. Такие языки получили название формальных,
или символических. Начнем с рассмотрения какого-нибудь
очень простого ic/лучая. Возьмем, например, электрокар',
служащий для перевозки грузов в пределах, цеха или заводского
двора. Обычно такой электрокар в зависимости от положения
рычагов может либо оставаться неподвижным, либо
двигаться с постоянной скоростью (вперед, назад, направо или налево.
«Общение» человека с подобным механизмом сводится к
тому, 'Что человек отдает приказы, воспринимаемые и
исполняемые механизмами электрокара. В данном случае человек
отдает эти приказы не словами, а «жестами», передвигая
рычаги. Однако это обстоятельство не имеет для нас никакого
значения. Важно, что в рассматриваемом случае мы
пользуемся совершенно определенным языком. Этот язык состоит из
следующих приказов: стоп, ехать прямо, ехать назад, ехать
направо, ехать налево.
Отвлечемся сейчас от других особенностей этого
простейшего «языка» и попробуем решить следующую задачу.
Предположим, что мы хотим сконструировать электрокар, который
воспринимал бы приказы не в форме перемещения рычагов, а
как-нибудь иначе. Например, в форме символов, написанных
на бумаге, или в форме слов, передаваемых звуками голоса.
Ясно, что чем проще приказ, тем скорее он может быть понят
и выполнен. Поэтому наша задача будет состоять в том,
чтобы сконструировать* язык, позволяющий формулировать
приказы для электрокара в наиболее простой из всех возможных
форм.
5
Для того чтобы успешно решить поставленную задачу, нам
придется взглянуть на нее, как это ни странно, не с позиций
человека, а с позиции... электрокара. Пусть электрокар
снабжен некоторым еще неизвестным нам устройством,
воспринимающим приказы от человека. Цель этого устройства состоит
в том, чтобы «узнавать», каков будет очередной приказ,
причем делать это оно будет некоторым простейшим образом.
По существу, это устройство непрерывно как бы задает
человеку вопрос: что делать дальше? Ответ на этот вопрос
каждый раз заключается в выборе одной из пяти различных
возможностей — либо продолжать выполнение ранее отданного
приказа, либо перейти к выполнению о дню-го из четырех
других. Заметим, и это очень важно, что пока очередной приказ
не отдан, каждая из этих пяти возможностей совершенно
равноценна, т. е. у электрокара нет никаких оснований
предпочесть 'какую-нибудь одну из них остальным четырем.
Подобная ситуация напоминает довольно
распространенную задачу. Человеку предлагается выбрать один из
нескольких предметов. При этом ему разрешается ставить вопросы,
на .которые мож1но ответить либо «да», либо «нет».
Необходимо выбрать требуемый предмет, задав при этом
минимальное число вопросов. Решение может быть таким. Человек
делит .все -количество предметов на две по возможности равные
кучки, затем, указывая на одну из них, он задает вопрос:
здесь ли находится искомый предмет? Если ответ
положителен, то ту кучжу, на которую он указывал, а если ответ
отрицателен, то друлу/ю кучку следует снова разделить на две по
возможности равные части и юно в а задать тот же вопрос.
Процесс деления продолжается до тех пор, пока не останутся
только два предмета.
Воспользуемся этим приемом для конструирования языка.
Сначала выберем алфавит. Ясно, что простейшим будет
алфавит, состоящий вюего из двух букв. Пусть это будут,
например, буквы А и Б. Теперь расположим все понятия,
которые мы хотим выразить словами будущего языка, в
некотором порядке и перенумеруем их. Например, так: / — стоп,
2 — ехать вперед, 3 — ехать назад, 4 — ехать направо и
5 — ехать налево. Разделим все множество понятий
так, чтобы в первое подмножество попали понятия / и 2, а во
второе подмножество — понятия 3, 4 и 5. Условимся, что сло-
за, начинающиеся с буквы Л, отноштоя к первому
подмножеству, а слова, начинающиеся с буквы £, — ко второму.
Разделим теперь каждое из подмножеств снова на две части.
Используя уже введенное условие, получим следующие
слова: АА — стоп, АБ — ехать вперед и БА — ехать назад.
Осталась одна группа, содержащая два понятия. Разделим
эту группу снова на две части и получим слова: ББА —
ехать направо, БББ — ехать налево.
Мы получили язык, который, несмотря на всю свою при-
6
,митявность, обладает свойствами обычного языка-.
Действительно, он 'имеет свой алфавит, свой словарь и свою
грамматику, которая ограничивается в данном случае несколькими
простейшими правилами. Количество слов в словаре в
данном случае в точности равно количеству понятий, которые
необходимо выразить с помощью этого языка. Такой язык в
наибольшей гтепени приспособлен для автомата. Простейший
алфавит, слова, состоящие из наименьшего количества букв,
и, наконец, система простых и четких грамматических
правил — все это позволяет достаточно легко различать и
исполнять приказы. И, наконец, что самое главное, — каждое
олово в этом язььке имеет единственный и строго
определенный смысл. Поэтому для различения слов здесь нет
необходимости обращаться -к контексту.
При желании язык может быть легко расширен. Пусть,
например, движение вперед и назад может совершаться с
двумя различными скоростями. Тогда можно построить
следующий расширенный словарь:
А А — стоп;
АБА — ехать вперед медленно;
АББ — ехать вперед быстро;
БАА — ехать назад медленно;
БАБ — ехать назад быстро;
ББА — ехать направо;
БББ — ехать налево.
Получена также методика составления простейшего
машинного языка. Эта (методика состоит в .следующем:
— выбрать алфавит, состоящий из любых двух
различных символов (по причинам, которые будут ясны из
дальнейшего, удобнее всего выбирать алфавит, состоящий из
символов «О» и «1»);
— понятия, которые предполагается выражать средствами
данного языка, расположить в некотором порядке и
перенумеровать;
— образовать словарь языка путем последовательного
деления сначала всего множества понятий, а затем получаемых
подмножеств на две по возможности равные части.
Теперь мы достаточно подготовлены ,к конструированию
языков для таких сложных автоматов, какими являются
цифровые вычислительные машины.
7
Глава 2
Внутренний язык
цифровой вычислительной машины
Цифровые вычислительные машины по праву считаются сложнейшими
среди современных автоматов. Хорошо известны успехи, достигнутые
вычислительной техникой на пути автоматизации отдельных областей
интеллектуальной деятельности. Вычислительные машины способны решать
сложнейшие математические задачи. Они могут успешно применяться для
управления производственными процессами, для решения задач эконохми-
ки и планирования. С помощью вычислительных машин можно выполнять
переводы с одного языка на другой и составлять аннотации или
рефераты научных статей. Наконец, хорошо известны опыты по «обучению»
машин игре в шашки и шахматы. Все перечисленное относится к области
переработки информации. Поэтому естественно, что проблема общения
человека и вычислительной машины и в первую очередь проблема
создания языков, одинаково удобных как для машины, так и для человека,
играет первостепенную роль.
Несмотря на сложность решаемых задач, основная схема
вычислительной машины чрезвычайно проста. Независимо от типа, сложности,
размеров и других параметров, каждая цифровая вычислительная машина
состоит из четырех основных частей, как показано на рис. 1. Буквами
ЦП на этом рисунке
обозначено устройство,
называемое центральным
процессором. Это устройство
выполняет некоторые* простейшие
операции, такие, например,
как арифметические
действия (сложение, вычитание,
умножение, деление),
логические операции и
некоторые операции управления,
Все эти операции
осуществляются над двоичными
словами. «Словом» в
цифровой вычислительной
машине называется любая
последовательность,
составленная 'из расположенных в
любом порядке символов «О» и «:1b». Каждое слово имеет свой «формат»,
причем (форматом слова называется совокупность пустых мест или клеток»
называемых разрядными позициями., В каждой такой клетке может быть
записан либо один символ 0, либо один -символ 1. Количество разрядных
позиций IB формате называется длиной слова. В отдельных -случаях
машинное слово -может разделяться на несколько частей, называемых слогами,
или байтами.
Каждой разрядной позиции в формате присваивается определенный
смысл. Совокупность смыслов всех разрядных позиций определяет смысл
слова. Таким образом, смысл каждого символа 0 и 1 в слове определяется
как смыслом слова, так и тем местом или той разрядной позицией,
которую этот символ занимает в пределах 'слова. Например, формат
Знак 28 27 26 2'
°1
а2
*з
Ч
а5
а6
а7
Ч
а9
аю
8
где Ль а ,.. -— символы 0 и 1, имеет смысл целых чисел ]. Крайняя слева
разрядная позиция имеет смысл знака числа (О имеет смысл + , а 1
имеет смысл —). Крайняя справа разрядная позиция имеет смысл 2°, т. е.
единиц, .следующая за ней имеет смысл 21, т. е. двоек и т. д. Все число
формируется следующим образом:
± (а2Х28+а3Х27+а4Х26+а5 Х25 + а9Х24 + а7Х23+а8 Х22+а9Х21 + аИ)Х20).
Например, слово OlllOOlO'lOl, записанное в таком формате, есть не что
иное, как целое число +(256+128+16 + 4 + 1) или +405. Формат
Знак 2'1 2
-г
о-З
о-5
7-6
2~
— это формат дробных чисел или, как их иначе называют, чисел с
фиксированной запятой. Здесь снова крайняя слева разрядная позиция имеет
смысл знака. Предполагается, что запятая (двоичная) расположена правее
этой позиции. Слово ГЫООЮКМ, записанное в таком формате, имеет
l \ l \ \
_ '+ ~7^"^ "^7Г~*~ 77^+ Т7к\ »т- е- это с*™80 представляет собой
2 4 62. VZo 512''
дробное число — 0,7695078125.
Форматы, разделенные ра слоги, используются для представления
букв и символов. Обычно каждый такой слог имеет в длину восемь
разрядных позиций:
смысл
Признак' _
начала Контроль &ак
шва СУк6ь1
2*
Единица в крайней слева позиции имеет смысл начала группы -символов,
что соответствует заглавной букве в обычном написании. В следующую
за ней разрядную позицию записывается 0 или 1 таким образом, чтобы
общее количество единиц в слоге всегда было четным. Это позволяет
легко контролировать возможные ошибки. Единица в третьей 'слева
разрядной позиции является признаком буквы, а ноль — признаком цифры
или знака препинания. Наконец, единицы или нули в остальных пяти
разрядных позициях составляют целое чиспо, представляющее собой
порядковый номер буквы или символа. Например,
Л
а
б
в
г
я
10100000
01100000
00100001
ООЮООЮ
ошоооы
00М{1'Ы«'1
0
1
2
9
00000000
oioooaw
01000010
00001001
010100М
00010001
1 Т. е. целых чисел, записанных в двоичной системе счисления.
Подробнее о двоичной системе счисления см., например, Г. О. Ефремов.
Язык математических машин. М., «Знание», 1967.
1214-2
9
Таким образом, слово 'ЮЮЮЮШ'ЮШОЮиООЮ в только что
рассмотренном формате должно читаться как КОТ — читатель может проверить его
самостоятельно.
Мы видим, что одна и та же последовательность нулей и единиц
может иметь совершенно различный смысл. Для того чтобы правильно
прочесть машинное слово, .нужно знать не только саму последовательность
нулей и единиц, но и формат, в котором она записана.
Обычно результат каждой предыдущей операции сохраняется в
центральном процессоре. Поэтому, например, арифметическая операция
сложения выглядит следующим образом: «сложить новое число с числом,
хранящимся в центральном процессоре и представляющим собой результат
предыдущей операции». Результат этой новой операции сложения также
поступает в центральный процессор и заменяет собой ранее хранившийся
в нем результат предыдущей операции.
Буквами ЗУ на рис. 1 обозначено запоминающее устройство.
Запоминающее устройство используется для хранения всех данных, как-то:
программы решения задачи, исходных данных этой задачи, промежуточных
и окончательных результатов. Как мы вскоре увидим, в запоминающем
устройстве хранится также большой объем всевозможной служебной
информации. Запоминающее устройство состоит из отдельных ячеек, каждая
из которых может хранить одно машинное слово. Каждая такая ячейка
имеет свой порядковый номер, называемый также «адресом». В
запоминающем устройстве могут выполняться только следующие два вида
операций:
операция «запись», при этом в запоминающую ячейку с заданным
номером записывается слово, которое находится в этот момент на входе
запоминающего устройства. Предыдущее содержимое ячейки стирается.
Таким образом, если записываемое слово состоит из одних нулей, то
операция «запись» эквивалентна уничтожению (стиранию) содержимого
ячейки с данным номером;
операция «считывание», при этом слово, хранящееся в ячейке с
заданным номером, передается на выход запоминающего устройства. В го
же время оно сохраняется в ячейке и может быть использовано повторно.
Буквами У У на рисунке обозначено устройство управления. Задачей
этого устройства является организация вычислительного процесса.
Выполняемые в нем операции будут рассмотрены ниже.
Буквами УВВ на рис. 1 обозначены устройства ввода-вывода. Задача
этих устройств — обеспечить связь вычислительной машины с ^внешней
средой. Основные операции, выполняемые здесь, — это ввод исходных
данных и программ и вывод полученных результатов.
Теперь мы достаточно знаем об устройстве цифровой вычислительной
машины и можем приступить к конструированию языка для описания
вычислительного процесса. Как и в случае, рассмотренном в предыдущей
главе, такой язык будет состоять главным образом из различных
приказов. Пусть алфавит языка содержит, как ,и ранее, только два символа.
Для того чтобы сохранить единообразие с прочими машинными словами,
выберем в качестве таких символов 0 и 1. Подумаем теперь о словаре.
Каждое действие в машине выполняется над совершенно
определенным предметом, причем, как указывалось выше, таким предметом
является машинное слово. Следовательно, прежде всего нужно
каждому машинному слову присвоить определенное имя. На первый
взгляд задача представляется достаточно сложной, поскольку, как это
явствует из всего сказанного выше, трудно найти какие-либо
индивидуальные особенности у последовательностей нулей и единиц. Однако есть и
другая возможность. Вспомним, что каждое машинное слово хранится в
некоторой определенной ячейке запоминающего устройства. Номер, или
адрес, этой ячейки однозначно определяет хранящееся в ней слово.
Поэтому совершенно естественно в качестве имен машинных слов принять
номера тех ячеек, в которых они хранятся. Здесь мы поступаем точно так
же, как поступали в предыдущей главе. ^Мы располагаем понятия в не-
10
котором порядке, в данном случае в порядке расположения ячеек, в
которых хранятся машинные слова.
Чтобы в дальнейшем не путать их с машинным словом, слова
машинного языка, который мы собираемся ско-нструировать, будем
называть кодами. Итак, мы определили группу кодов, обозначающих
предметы, т. е. кодов, выполняющих в машинном языке функции
существительных. Для формирования этих кодов воспользуемся уже известными
приемами. Пусть, например, запоминающее устройство содержит 16 384 ячейки,
перенумерованные с номера 00000 до номера 16383. Поделим все эти
ячейки на две части и условимся, что коды, обозначающие ячейки с
номерами от 00000 до 08191, будут иметь 0 в качестве первого символа, а
коды, обозначающие ячейки с номерами от 08192 до 16383, — будут иметь
в качестве первого символа 1. Поделим каждую половину снова пополам,
введем аналогичные условия относительно второго символа кода и т. д.
Тогда, например, код 10010010100101 будет обозначать машинное слово,
хранящееся в ячейке № 09381 запоминающего устройства машины.
Заметим, что при таком способе построения записи все коды,
выполняющие функции существительного, будут содержать одинаковое
количество, а именно 14 символов. Такое количество оимволов в коде может
служить отличительным признаком 'существительного, что, как мы скоро
увидим, представляет определенное удобство.
Теперь нам нужны коды, которые обозначали бы само действие, т. е
коды, выполняющие функции глаголов. Для этого снова надо составить
перечень соответствующих понятий. Все выполняемые в машине операции
можно разделить на следующие четыре основные группы:
1) арифметические и логические операции;
2) операции управления;
3) операции передачи;
4) служебные операции.
Условимся, что коды первой группы будут начинаться с символов 00,
коды второй группы — с символов 01, коды третьей группы — с
символов 10 и коды четвертой группы — с символов «Ы. Длину кода-глагол.з
можно установить равной, скажем, пяти символам *. Причем пусть
последние три символа в коде обозначают порядковый номер операции в
пределах данной группы. Тогда для арифметических операций можно
установить:
00001 —сложить,
00010—вычесть,
ОООШЬ — умножить,
00100 — разделить.
В дальнейшем по мере необходимости мы будем расширять этот словарь.
Для кодов третьей группы также можно установить непосредственно:
10001—передать машинное слово из ЗУ в ЦП;
10010—передать машинное слово из ЦП <в ЗУ,
1001(1 — передать .машинное слово из ЗУ <в УВВ,
'1О1О0 — передать машинное слово из УВВ в ЗУ,
10101 —передать машинное слово из ЦП в УВВ.
Среди операций четвертой группы мы пока рассмотрим одну-единст-
венную операцию, а именно
1(1001 — остановить вычисления.
Операции второй группы требуют некоторых дополнительных
пояснений, поэтому мы вернемся к ним .в дальнейшем.
Займемся теперь правилами грамматики машинного языка. Эти
правила очень просты и сводятся к следующему:
'1) каждое предложение может состоять только из двух кодов —
одного существительного и одного глагола;
Ведь глаголов явно меньше, чем существительных.
11
2) глагол записывается всегда на первом месте, а существительное —
на втором;
3) каждое предложение .пишется с новой строки,
Типичное предложение ма машинном языке имеет вид:
00001,0000001 OHMIliOl,
что означает «к слову, хранящемуся в центральном процессоре, прибавить
слово, хранящееся в ячейке № 1$9 запоминающего устройства; результат
сохранить в центральном процессоре». Заметим, что поскольку каждый
код в машинном языке имеет строго определенную длину, а порядок
кодов в предложении строго определен правилами грамматики, здесь нет
необходимости в каких-либо знаках препинания <и даже в пробелах
между отдельными кодами. В дальнейшем предложения машинного языка мы
будем называть командами.
Попробуем теперь применить сконструированный нами язык для
описания процесса решения какой-либо математической задачи. Пусть,
например, задача состоит в том, чтобы вычислить многочлен
S=x4-fa3A:3+a2*2+aiX-fao (1)
Перепишем эту формулу так:
S=(((x+a3)x+a2)x+al)x+a0 (2)
Теперь видно, что процесс вычисления многочлена сводится к повторному
выполнению операций сложения и умножения.
Для того чтобы машина могла начать вычисления, необходимо
разместить исходные данные задачи, а именно числа х и а/ в какиих-либо
ячейках запоминающего устройства^ Пусть, например, для размещения
этих чисел мы выбрали ячейки с номерами от 100 до 104. Будем считать
также, что все эти числа дробные и, следовательно, могут быть
преобразованы в машинные слова, записанные в формате с фиксированной
запятой. Такое преобразование автоматически выполняется в УВВ машины и
не требует специальных указаний. Предположим, наконец, что в УВВ
машины исходные данные расположены в следующем порядке: х, а$, а2,
аь До- Тогда непосредственно можно написагь:
.101000000000Ш00100 х-100
1О10000000ООМОО1О1 а3- 101
loiooooooooaiiioono Д2-102
101000000000Ы001 111- ai — 103
IOIOOOOOOOOOIiIOIOOO a0-104
Справа даны комментарии, поясняющие смысл каждой команды. Символ
-> означает «передать в».
Написанное здесь представляет собой группу предложений (команд)
или абзац на языке машины. Такой абзац мы будем называть «блоком».
Смысл написанного состоит в том, что числа ху а3, а2, а\ и а0 оказываются
размещенными в ячейках запоминающего устройства с номерами 100,
101, 102, 103 и 104 соответственно. Теперь можно перейти к описанию
самого вычислительного процесса. Непосредственно из формулы (2)
получи см:
1О0010000О00ШЮО100 х ^ЦП
ooooiooooooomooioi <цп>+а3 - цп
000110000000L100100 <ЦП> Хх -* ЦП
000010000000Ш00110 <ЦП> + а2-+ЦП
0001<100000001100100 <ЦП> Хх -* ЦП
000010000000110011.1 <ЦП> + ах-+ЦП
000110O000OO1I1OO1O0 <ЦП> Хх - ЦП
00001000Q000110.1000 <ЦП> + а0-+ЦП
И здесь справа записаны комментарии. ЦП означает центральный
процессор, а <ЦП> означает «содержимое центрального процессора». Легко
видеть, что после выполнения последней команды данного абзаца содер-
1'2
жимое центрального процессора будет представлять собой окончательный
результат вычислений, т. е. число S. Теперь нужно это число вывести из
машины и остановить вычисления. Для этого напишем следующий абзац:
1010100000000000000 <ЦП> -+УВВ
1100100000000000000 СТОП
В процессе вывода соответствующее машинное слово автоматически
преобразуется в форму обычной десятичной дроби. Заметим, что в двух
последних командах на месте существительных стоят нули. Это означает,"
что при выполнении этих команд не требуется обращения к
запоминающему устройству.
Обратим теперь внимание на следующее очень важное обстоятельство.
Каждая команда, записанная на машинном языке, представляет собой
последовательность постоянной длины, состоящую из нулей и единиц, т е.
она имеет точно такой же вид, как машинное слово 'некоторого
специального формата. Команды действительно представляют собой машинные
слова и они хранятся в ячейках запоминающего устройства на равных
правах со всей прочей информацией. Это дает нам возможность присвоить
каждой команде имя, причем, как и прежде, именем команды мы будем
считать номер запоминающей ячейки, в которой она записана, или ее
адрес. В дальнейшем при написании текстов на машинном языке левее
каждой команды мы будем писать ее имя, отделяя его двоеточием. Имя
команды называется также «меткой». Метка — это особая грамматическая
категория, характерная для машинных языков.
Работа каждой вычислительной -машины подчиняется следующему
основному правилу: команды всегда выполняются в порядке своих адресов.
Это значит, что если в какой-то момент времени выполнялась команда,
хранящаяся в ячейке № k, то следующей будет выполняться команда,
хранящаяся в ячейке № (£+1). Это правила может нарушаться только
при выполнении операций управления.
Операции управления (операции второй группы) делятся на две
подгруппы. К первой из них относятся так называемые операции безусловной
передачи управления. Типичная операция безусловной передачи
управления имеет вид
ОГООО — следующей по порядку выполнять команду, имя которой
определяется существительным.
Сокращенно говорят также «передать управление в ячейку №...», что
означает то же самое.
Ко второй подгруппе относятся операции условной передачи
управления. Эти операции имеют вид:
0Ю0Г—передать управление в ячейку №..., если число в
центральном процессоре равно нулю,
О1010 — передать управление ib ячейку М..., если число в
центральном процессоре больше нуля,
010.Г1—передать управление в ячейку Л£..., если число в
центральном процессоре меньше нуля.
В каждом из трех рассмотренных случаев, если условие не
удовлетворяется, т. е. если число в центральном процессоре оказывается не
равным, не большим или не меньшим нуля соответственно, то команда просто
пропускается и вместо нее выполняется следующая по порядку команда.
Пользуясь операциями управления, можно в значительной степени
упростить тексты, написанные на машинном языке, и сделать их более
универсальными. В дальнейшем такие тексты мы будем называть
программами.
Рассмотрим, например, первый блок составленной выше программы.
Этот блок состоит из пяти команд, причем каждая из них содержит один
и тот же глагол, т. е. предусматривает выполнение одной и той же
операции. Существительное в каждой 'следующей команде отличается на
единицу от существительного предыдущей команды. Предположим также, что
к исходным данным задачи мы добавили числа 3, 5 и 1, которые в про-
13
цессе ввода будут преобразованы в машинные слова, записанные в
формате целых чисел. Другими словами, исходные данные в УВВ машины
присутствуют в такой последовательности: 3, 5, '1, х, аз, 02, а\> До- Тогда
мы можем написать следующий текст:
49 000000001(10011 : 1О1О000000001100001
50 00000000 lil 0010: 101О000000ОШШ00Ю
51 000000001.10001: 1010000000001100011
52\
53\
54
55\
3 -+97
5-+ 98
1 -+99
х -+ 100
ООООООООГ10101 : 1000100000000 МО 100
ООООООООЫОПО : ООООЮООООООЧЮООП
OOOOOOOOlilQliU : 10010000000001110100
00000000110100 : 1О100000000ОМО0100
взять содержимое
ячейки № 52,
прибавить к нему 1 и
передать
.результат снова в
ячейку № 52
00О000ОО111000: 1О0О1О0000ОО11000Ю <98>-+ ЦП
OOOOOOOOMilOOl : 00O1O000O0001100011 <ЦП>—<99> - ЦП
ООООООООЫЮЮ: 10010000000011000/10 <ЦП>-+98
000000001IU0IH: 1000100000001100010 <98> -+ ЦП
5L
57\
58
59\
6(Г— 00000О0ОМ 11,00: Ш01000000000П0100 если число<ДЯ>
больше 0,
передать управление в
ячейку М 52
Числа в левом столбце облегчают 'чтение меток. Сами метки расположены
левее команд и отделены от .них двоеточиями.
Смысл команд 49—52 этого блока не вызывает сомнений. В
результате выполнения этих команд числа 3, 5, 1 и х оказываются
размещенными 'в ячейках ЗУ, № 97, 98, 99 и 100 соответственно. В результате
выполнения команды 53 содержимое ячейки № 52, т. е. команда 52
передается .в центральный процессор. В результате выполнения команды 54 к
содержимому центрального процессора (т. е. к команде 52) добавляется
содержимое ячейки № 99, т. е число 1. В 'результате получается новая
команда, которая предусматривает передачу одного машинного слова из
УВВ в ячейку № 1013/. По команде 55 эта новая команда помещается в
ячейку на место ранее содержащейся там команды. Подобная
последовательность операции называется модификацией ко.ма.нд. По команде 56 в
центральный процессор передается содержимое ячейки № 98, т. е. число 5
По команде 57 из этого числа вычитается единица, по команде 58 число
5—1=4 передается в ячейку № 98, где оно замещает ранее
содержавшееся там число 5. По команде 59 содержимое ячейки М 98 передается
в центральный процессор. Наконец, по команде 60 число, хранящееся в
центральном процессоре, сравнивается с нулем. Если это число больше
нуля (что на самом деле имеет место), то команда 60 выполняется, и
следующей по порядку будет выполняться команда 52. Это
обстоятельство отмечено стрелкой.
Теперь снова выполняется последовательность команд 52—59. В
результате выполнения этой последовательности число а$ передается в
ячейку № 101. Затем содержимое ячейки № 52 снова заменяется и в ней
оказывается команда, предусматривающая передачу машинного слова в
ячейку № 102. Из содержимого ячейки № 98 снова вычитается Ь и оно
оказывается равным 3. Число '3 передается в центральный процессор и
выполняется команда 60. Так будет продолжаться до тех пор, пока не будет
выполнено ровно пять повторений. После этого число в ячейке № 98
окажется равным нулю, условие, заключенное в команде 60 не
удовлетворится, эта команда будет пропущена и машина перейдет к выполнению
команды 61.
На первый взгляд составленный блок кажется значительно сложнее
предыдущего блока ввода. Однако на самом деле это не так. Заметим
прежде всего, что этот блок универсален. Действительно, достаточно в
ячейку № 98 вместо числа 5 записать, например, число '1'500, как последо-
14
вательность команд 52—60 (повторится 1500 раз. Таким образом, с помощью
того же самого блока без каких-либо изменений можно ввести в машину
1500 (а в общем случае сколько угодно) машинных слов, разместив их
последовательно в ячейках ЗУ, начиная с ячейки № 100. Если бы мы
составляли блок ввода так, как это делалось раньше, то-он содержал бы
Ь500 команд. Составленный блок можно назвать стандартной программой
ввода. Теперь мы видим, что использование операции управления
позволяет не только значительно сократить программу, но и сделать ее
универсальной, или стандартной. В данном случае универсальность
программы состоит в том, что ее вид и количество команд не зависят от
количества вводимых чисел.
Применяя тот же метод, запишем остальные блоки программы:
61 0000000011МЮ1 : 1000100000001100100 <100>-* ЦП
62 OOOOOOOOdllПЬЮ: 1001000000001100000 <ЦП> -> 96
63 ОООО0000МШ1: И00О1О0000001100000 <96>-> ЦП
64 00000001000000: 000О10000000ШШ101 <ЦП> + <101>-+ ЦП
65 000000010000011: ОО0Ш1000000011100100 <ЦП>Х<100> -> ЦП
66 О00О0001000010: 1001000000001100000 <ЦП> -> 96
67 00000001000011 : 1000-100000001000000 <64> -> ЦП
68 000000О1О001О0: 0000100000001II00011 <ЦП> + <99> - ЦП
69 00000001000101ч ЮО1О000000ОЮ0О000 <ЦП> -» 64
70 00000001О00110 : 100010000000И100001 <97> -> ЦП
71 00000001000М1 : 00010000000011100011 <ЦП>—<99>-+ ЦП
72 00000001001000: ОЮЮООООООООШИИ если <ЦП> >0,
передать
управление в ячейку
№ 63
73 00000001001001 : 1О001000000011О0000 <96> -> ЦП
72 00000001001000 :'00001000000011101000 <ЦП> + <104>-> ЦП
75 • 000000010010,44 : 1О101О000000О0О0000 <ЦП>-> УВВ
76 000000011001(100: 1100 ЮООООООООООООО СТОП
Все команды этой программы снабжены исчерпывающими комментариями,
поэтому разобраться в их смысле мы предоставляем читателю.
Подведем теперь некоторые итоги. Мы сконструировали язык, с
помощью которого, как это было показано на примерах, можно описывать
вычислительные процессы, происходящие в машине. Можно отметить
следующие характерные особенности этого языка.
— Язык, достаточно универсален. Действительно, можно показать, что
с его помощью описывается процесс решения любой математической
задачи, а также большинства задач, вообще допускающих решение на
цифровой вычислительной 'машине. Если даже окажется, что для описания
какого-либо процесса в языке не хватает слов, то эти слова легко добавить,
не изменяя общей структуры языка и его грамматики.
— Язык удобен для машины. Действительно, наличие в алфавите
только двух символов позволяет легко интерпретировать эти символы с
помощью электрических сигналов. Структура кодов-существительных
позволяет легко организовать поиск нужной ячейки ЗУ путем
последовательных делений множества ячеек на две части. То же самое относится и к
кодам-глаголам. По первым двум символам кодов машина сразу может
определить, какие именно устройства должны участвовать ,в выполнении
данной операции. Например, символы 00 указывают, что в операции
участвуют только центральный процессор и запоминающее устройство.
Символы 01 указывают, что в выполнении операции участвует устройство
управления и т. д. Следующие три символа кода-глагола указывают
порядковый номер операции, причем здесь выбор производится среди
относительно небольшого числа возможностей. Наконец, каждое предложение
или команда, записанные на машинном языке, имеют формат машинного
слова и, следовательно, могут храниться в запоминающем устройстве
наряду со всей прочей информацией. Это позволяет выполнять операции над
15
командами, что, как мы видели, резко сокращает объем программ и
позволяет сделать их более универсальными.
— Язык неудобен для человека. Читатель уже успел в этом
убедиться, если он не поленился подробно разобрать приведенные выше примеры.
По существу, так и должно быть, тюскольку, конструируя язык, мы ставилв-
себе целью в возможно наибольшей степени удовлетворить потребности
автомата. Именно по этой причине языки подобного типа и получили
название внутренних языков машины. Язык служит прекрасным средством
передачи информации между устройствами машины, а также для
общения машин между собой, и в то же время он неудобен для общей
человека с машиной.
Отметим в заключение еще одну характерную особенность
сконструированного нами языка. Она состоит в том, что единственным средством
различения машинных слов служит имя этого слова, или номер
запоминающей ячейки, в которой она находится. Машине, по существу,
безразлично, над- какими именно словами она выполняет операции. Именно это
и определило способность цифровых вычислительных машин решать
исключительно широкий класс задач. Идея подобной организации машины и ее
внутреннего языка впервые была высказана Чарльзом Беббеджем еще во
второй половине прошлого века. Словарь машинного языка содержит в
себе полный перечень выполняемых машиной операций. Поэтому именно
словарь внутреннего языка машины, а не технические характеристики ее
определяет возможности машины в части решения тех или иных задач
Глава 3
Машинно - ориентированные языки
До сих пор лри конструировании языка мы заботились только об
удобствах автомата. Настала пора подумать и о человеке, который
управляет работой этого автомата, поэтому теперь мы будем совершенствовать
простейший язык, всячески приспособляя его к потребностям человека.
Первое, что бросается в глаза при рассмотрении материала
предыдущей главы, — это то, что читать текст, записанный только нулями и
единицами, чрезвычайно трудно. Оно и понятно! Человек с детства
привыкает к алфавиту родного языка и не столько к самому алфавиту, сколько
к большому разнообразию букв. В то же время чтение слова, состоящего,
скажем, из 36 букв, даже и а родном языке связано с известными
затруднениями. Поэтому мы начнем с того, что попробуем изменить алфавит.
Мы поймем, как это сделать, если опять несколько отвлечемся в сторону.
Взглянем еще раз на программу, приведенную на стр. 15. Эта
программа предусматривает выполнение некоторой последовательности операций
Операции выполняются над группой исходных машинных слов, и в
результате получается 'новое машинное слово — ответ задачи. А раз так,
то мы можем рассуждать следующим образом. Программа, скажем мы, —
это средство для переработки одного машинного слова или группы слов
в другое машинное слово или в другую группу слое.'Ранее нами
неоднократно подчеркивалось, что цифровая вычислительная машина способна
решать практически любую задачу. Отсюда можно сделать окончательный
вывод, что можно составить программу для переработки любой
последовательности нулей и единиц в любую другую последовательность нулей и
единиц.
Вспомним теперь, что буквы русского (а в общем случае и любого
другого) алфавита, а также арабские цифры представляются в машине
также с помощью последовательностей нулей и единиц, которые мы
назвали слогами. Предположим, что имеются программы, способные
переработать коды любой буквы п любой дифры в любые другие
последовательности нулей и единиц. Тогда мы можем поступить гак.
16
Рассмотрим, например, код операции «сложить». На внутреннем
языке машины этот код записывается как 0000lv. (Представим себе теперь
некоторый новый язык, алфавитом которого служат 32 заглавные буквы
русского алфавита и Ю арабских цифр — от 0 до 9. В этом языке слово
-«сложить» мы можем обозначать, например, одной буквой «С». Возникает
проблема перевода:
CV- 0000 Г.
Составим программу перевода и введем ее в ЗУ машины. За недостатком
места мы не будем приводить здесь эту программу, поскольку из всего
сказанного выше ясно, что ее можно составить. Пойдем лучше дальше.
Заменим машинный код 00010 (вычесть) одной буквой Б, составим
программу перевода и введем ее в машину. 'Поступим аналогичным образом
со всеми остальными кодами-глаголами.
Существительными во внутреннем языке машины служат порядковые
номера ячеек ЗУ, записанные в двоичной системе счисления. В новом
языке функции существительных будут выполнять по-прежнему порядковые
номера ячеек ЗУ, но записывать их мй будем в более привычной нам
десятичной системе счисления. Если в машинном языке
код-существительное имел всегда постоянную длину в 14 символов и это было его
отличительным признаком, то в новом языке код-существительное также будет
иметь постоянную длину, но в пять десятичных цифр. Например,
00000000110ИШ< *- -> 00055.
Таким образом, проблема перевода здесь сводится к переводу чисел из
десятичной системы счисления и двоичную с учетом правила о длине
каждого кода. Составим соответствующую программу и также поместим ее в
ЗУ машины.
Объединим теперь составленную в предыдущей главе универсальную
программу ввода с только что рассмотренными программами в одну
общую программу «ввода-перевода». Теперь мы имеем два языка. Оба они
имеют один и тот же словарь и Одну и ту же грамматику. Алфавит
первого языка состоит из двух букв 0 и 1, алфавит второго языка состоит из
32 русских заглавных букв и десяти арабских цифр. Первым языком по-
прежнему будет пользоваться машина как для внутренних потребностей,
так и при общении с другими машинами, а вторым языком будет
пользоваться человек при общении с машиной. Назовем этот язык машинно-
ориентированным. Смысл названия мы поясним позднее. Программа
ввода-перевода есть не что иное, как средство перевода с
машинно-ориентированного языка на внутренний язык машины. Для полноты картины
составим также программу «вывода-перевода», выполняющую обратные
функции, т. е. осуществляющую перевод с внутреннего языка машины на
машинно-ориентированный язык. Если эту программу также поместить в
ЗУ машины, то человек-оператор получит возможность вообще не знать
внутреннего языка машины и использовать для общения с ней только
машинно-ориентированный язык.
При заполнении графы «в машине» этой таблицы мы пользовались
правилами кодирования букв и цифр, изложенными на стр. 9. В графе
«смысл» Л означает адресную часть команды, т. е. ее существительное.
Остальные символы те же, что и ранее. Передача Л -> УУ означает, что
адрес (существительное) из данной команды передается в устройство
управления и используется там для обозначения запоминающей ячейки, в
которой хранится следующая команда. Из таблицы видно, что длина
каждого кода-существительного составляет ровно пять символов. Длина кода-
глагола может быть равна одному или двум символам, но в последнем
случае второй символ — обязательно цифра. Таковы правила кодов в
машинно-ориентированном языке. Эти правила позволяют значительно
легче разбивать команды на «члены предложения».
Приведем полностью словарь машинно-ориентированного языка:
1214—3
17
Код
внутреннего языка
машины
Код машинно-
ориентированного языка
в машине
.вне
машины
Смысл
00001
00010
00011
00100
01000
0И001
01010
01011
10001
1I0Q10
100М
Ю100
mioi»
1(1001
от 1
00000000000000!
до ,
liMMlllllllll
1 а) Коды-глаголы
10110001
ИШОООЮ
11110110
11100100
111ОН0100000000
ИШОШ0101000001
1110110101000010
11101110100000011
1010111101000001
ЮКШИ101000010
1010111.100000011
101011Ш101000100
1010111100000101
10111000
б)
Коды-существительные .
зооооооооооооооо
J0000O00O0O00O00
30000000
0100000100000110
000000110(1001000
ооооооп
с
в
У
я
но
HI
Н2
нз
П1
П2
пз
П4
П5
ш
00000
1Ш8в j
Сложить
Вычесть
Умножить
Разделить
\А ->УУ
Бели <ЦП>=0, Л-
Если <ЦП»0, A-+
Если <ДЯ><0, А -*
<ЗУ> - ЦП
<ЦП> - ЗУ
<ЗУ> -> УВВ
<УВВ> -> ЗУ
<ЦП>-+ УВВ
Стоп
Порядковые номера
ек (адреса) в ЗУ
шины
УУ
УУ
УУ
тче-
ма-
Уже из таблицы должно стать ясно, что пользоваться
машинно-ориентированным языком человеку должно быть значительно проще, чем
внутренним языком машины. Для того чтобы это утверждение стало еще
более очевидным, перепишем программу, приведенную на стр. 15 и .16, на
машинно-ориентированный 'ЯЗЫК.
00049: П400097
00050: П40009Г
00051 : П400099
00052: П400100
00053 :П 100052
00054 : С00099,
00055 : П200052
00056 :П 100098
00057 : В00099 ,
00058 : П200098
00059 :П 100098
00060: Н200052 '
000611 :П 100100
00062: П200096
,-> 00063 :П 100096
00064 : С00101
О0065:У0010О
00066: П200096
00067 :П 100064
00068: С00099
00069: П200064
00070 :П 100097
00071 : В00099
- 00072: Н200063
00073
00074
00075
00076
:П 100096
С0ОЮ4
П500000
ШООООО
При вводе этой программы в машину будет происходить
следующее. Пусть человек, пользуясь клавиатурой устройства ввода-вывода,
печатает, например, такое предложение: 00049: П4О0097. Специальный
механизм, имеющийся в устройстве -ввода-вывода, преобразует это
предложение в группу машинных слогов:
1ЮОООООЮООООООООООООООО10001 0000001001000Ю0101010ГШ
010001000000000000000 000000000000000100101000 Ml
(первый слог начинается
с 1, что обозначает начало предложения; прочесть это предложение можно
18
достаточно просто, если мысленно разделить его на отдельные слоги (по
восемь символов в каждом). Затем вступают в действие программы
ввода-перевода. Сначала, преобразуется метка, т. е. первые пять слогов 40
символов), что дает: 00000000110001 {число 49 в двоичной системе
счисления). Далее расшифровывается слог 00010010 (двоеточие), указывающий,
что все следующее за ним должно быть помещено после перевода в
ячейку № 493У. Наконец, последними переводятся остальные семь слогов, что
дает: 101000000000М00001, т. е. первую команду программы. Команда
помещается в ячейку Лг2 49, а машина приступает к переводу следующего
предложения, напечатанного к тому времени человеком. Когда программа
полностью введена — машина готова к решению задачи.
Здесь уместно остановиться и сделать некоторые наблюдения. Мы уже
набрали достаточно материала, чтобы заключить, что структура машинного
языка теснейшим образом связана как с устройством самой машины, так и с
информацией, накопленной в ее запоминающем устройстве. В частности,
переход от внутреннего языка к машинно-ориентированному языку оказался
возможным только после того, как мы ввели в машину специальную
информацию, которой в данном случае явилась программа ввода-перевода и
вывода-перевода. На первый взгляд сконструированный нами машинно-
ориентированный язык почти не отличается от внутреннего языка и
создает только некоторые удобства при написании и чтении программы.
Однако на самом деле сделан шаг, имеющий большое принципиальное
значение. Сущность его состоит в том, что если раньше мы общались с
машинной непосредственно, подчиняясь при этом всем ее особенностям, то
теперь мы ввели посредника между машиной и человеком. Роль такого
посредника (или, если угодно — переводчика) и играет программа ввода-
перевода и вывода-перевода. Заметим, и это особенно важно, что для
перехода к машинно-ориентированному языку не потребовалось вводить
никаких изменений в конструкцию машины. Мы только ввели в машину
дополнительную информацию, или, другими словами, «научили» ее
переводить с одного языка на другой. Если бы возникла необходимость
воспользоваться каким-либо другим машинно-ориентированным языком
(например, имеющим латинские буквы, а не русские), то это опять-таки не п>
требовало бы никаких изменений в конструкции машины. Нужно было бы
только ввести в машину другую программу-посредник.
А теперь воспользуемся полученными сведениями для дальнейшего
совершенствования машинно-ориентированного языка. Для этого нам
придется написать еще одну программу.
Пусть, например, нужно вьгчислись функцию е*, воспользовавшись еь
разложением в ряд Тейлора:
e*=iI1+JC+j£+ -£+... (3)
Перепишем формулу (3) в виде:
v * * ™ * JC XX X X
е-* =4-1. — + 1 • '— + 1- — • ■— " —•••+ (4)
112 12 3 '
Теперь ясно, что каждый член ряда получается из предыдущего в резуль-
х
тате умножения его на величину —, где f=0, Г, £, ... — номер члена.
i
Неясным остается вопрос, когда прекращать вычисления. Условимся, что
мы будем прекращать вычисления тогда, когда очередной вычисленный
член ряда окажется меньше уже накопленной суммы, например, в 106 раз.
Это даст нам определенную гарантию, что функция ех окажется
вычисленной по крайней мере с пятью верными десятичными цифрами.
Все эти соображения дают нам возможность непосредственно
составить программу. При составлении предыдущих программ мы поместили
число 1 в ячейку № 000099. Число 1 требуется при составлении
большинства программ, поэтому будем считать, что оно постоянно хранится в этой
ячейке. Будем считать также, что, например, в ячейке № 00300 постоянно
19
хранится число Юб. Наконец, мы не знаем, где хранится число х, т. е„
аргумент вычисляемой функции. Положим пока условно, что это число
хранится в ячейке М 00000. Тогда может быть написан сл_едующий-тек^т!
00270
00271
00272
00273
00274
00275
00276
00277
►00278
00279
00280
0028li
00282
00283
00284
00285
00286
00287 :
00288
00289
00290
-00291 :
00292 :
00293:
00294:
00295 :
00296 :
00297 :
00298 :
00299 :
:П 100000
: П200305
:Л100009
: П200301
:П10099
:П200302
: Ш 00099
: П200303
:П 100303
: У00305
:Д00301
: П200303
П100301)
С00099
П200301
П100302
C00303
П200302
П100303
П200304
П100304
Н200294
П200304
В00304
УООЗОО
П200304
П100302
В003О4
Н300278
П100302
х-+ ЦП
<ЦП> -00305
1-* ЦП
<ЦП> - 00301
1)- ЦП
<ЦП> - 00302
1 - ЦП
<ЦП> -> 00303
<00303> - ЦП
<ДЯ>Х<00305>
<ДЯ>/<00301>н
<ЦП> - 00303
<00301> -+ЦП
<ЦП> + <00О99>
<ЦП> - 00301
<00302> -> ЦП
<ДЯ> + <00303>
<ЦП> -> 00302
<00303> -> ЦП
<ЦП>-+ 00304
<00304> - ЦП
-+ЦП
► ЦП
-+ЦП
- ЦП
Если <ЦП»0, <00294>- УУ
<ЦП> - 00304
<ЦП>—<003О4>
<ЦЯ>Х<300> ->
<ЯЯ>-00304
<00302> - ЦП
<ЦП>—<00304>-
■+ЦП
ЦП
- ЦП
Если <ДЯ><0, <00278>- У У
<003О2> - ЦП
В правом столбце, 'как всегда, приведены комментарии. В результате
выполнения первых восьми команд число х оказывается помещенным в
ячейку № 00305, а число 1 оказывается помещенным в ячейки № 00301, 00302
и 00303. По команде 00278 содержимое ячейки 00303 передается в
.центральный процессор. В ячейке № 00303 будет храниться текущее
значение очередного члена ряда. (Поэтому следующие команды
предусматривают умножение содержимого этой ячейки на х и деление его «а величину
L Текущее значение величины i будет храниться в ячейке М 003V1.
Поэтому по команде 00282 содержимое этой ячейки передается в
центральный процессор, где к нему прибавляется единица и таким образом
подготавливается следующий цикл вычислений. В ячейке № 00302 будет
накапливаться текущее значение суммы членов ряда. По команде 00285
содержимое этой ячейки передается в центральный процессор, где к нему
прибавляется ранее вычисленное значение очередного члена ряда. Теперь
нужно решить вопрос о прекращении вычислений. Для этого текущее
значение очередного члена ряда из ячейки № 00303 передается в ячейку
№ 00304 и в центральный процессор. Если это значение положительно, то
команда 00291 передает управление в ячейку М 00294. В противном
случае содержимое ячейки № 00304 вычитается из нуля и его знак
изменяется на противоположный. Эти операции эквивалентны образованию модуля
от очередного значения члена ряда. По команде № 00294 полученная
величина модуля умножается на 106. По команде 00297 из накопленной
суммы вычитается модуль очередного члена, умноженный на Ю6. Если
полученная разность отрицательна, т. е. условие прекращения вычислений еще
не удовлетворяется, команда 00298 передает управление в ячейку М 00278
и цикл вычислений повторяется. В противном случае вычисленное
значение функции передается в центральный процессор.
20
Составленная нами программа позволяет вычислить функцию ех с
пятью верными десятичными цифрами. При этом имеется в виду, что
аргумент .функции должен храниться в ячейке М 00000, а сама функция
после вычисления остается в центральном процессоре.
Функция ех очень часто встречается при решении различных
математических задач. Поэтому нет никакого смысла каждый раз, когда
понадобится функция ех, составлять программу заново. Было бы гораздо
удобнее, если бы такая программа постоянно хранилась в ЗУ машины и
к ней можно было бы обращаться по мере необходимости. Подобные
программы получили название стандартных. Однако здесь мы наталкиваемся
на определенные трудности. Как мы уже убедились, программа
вычисления даже такой простой функции, как ех, занимает в общей сложности
36 ячеек. Программы вычисления более сложных функций займут
значительно больше ячеек, поэтому если все стандартные программы хранить
в оперативном ЗУ машины, то очень скоро это ЗУ окажется заполненным
до предела. Вторая трудность состоит в том, что программисту нужно
будет постоянно помнить, какие именно ячейки ЗУ заняты стандартными
программами, а какие можно использовать для решения очередных задач.
По указанным причинам запоминающие устройства современных
машин строятся по так называемому иерархическому принципу. Кроме
оперативной части, допускающей произвольное обращение к любой ячейке,
в состав ЗУ вводится так называемая внешняя память, обладающая
значительно большей емкостью и в то же время значительно меньшим
быстродействием. В силу последнего обстоятельства внешняя память не имеет
непосредственно связи с центральным процессором. Информация,
хранящаяся во внешней памяти, по мере необходимости передается в
оперативную часть, причем передаются не отдельные слова, а группы слов,
например, целые программы.
Внешняя память может быть с успехом использована для хранения
стандартных программ. Однако для этого нужно обеспечить легкость
передачи стандартных программ в любое место оперативной памяти. Кроме
того, емкость внешней памяти хотя и велика, но все же ограничена.
Поэтому следует принять все меры, чтобы стандартные программы
оказывались по возможности короче и занимали минимальное количество ячеек.
Итак, на нашем пути возникли две новые проблемы: обеспечить
простые средства для передачи групп слов между различными участками
памяти машины и обеспечить средства сокращения программ. Попробуем
решить эти проблемы путем дальнейшего усовершенствования машинно-
ориентированного языка. Для этого мы будем расширять его словарный
состав, вводя дополнительные слова, задача которых — частично
изменять и обогащать (модифицировать) смысловое содержание других слов,
т. е слова-прилагательные.
Машинные команды, которыми мы пользовались выше, можно в
общем виде представить следующим образом:
КА,
где К — это код операции (глагол), а А — адресная часть
(существительное).
Примем теперь следующую новую структуру команды:
KMIBA,
где К и А имеют тот же смысл, что и в предыдущем случае, а М, I и
В — это новые коды-прилагательные. Примем также следующий новый
формат машинного слова-команды:
К М I В А
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
21
Здесь внутри клеток помечены порядковые номера разрядов в слове, а
сверху указан их смысл. Как видно, коды М, I и В занимают
относительно небольшое количество разрядов.
Чтобы понять (назначение кодов / и Б, предположим, что мы
выделили в составе оперативной части ЗУ машины какую-то группу ячеек,
например, ячейки с номерами от 00000 до 00063 и условились не занимать
эти ячейки никакой информацией, связанной с решением задач. В этих
ячейках будут храниться специальные слова, называемые управляющими.
Условимся теперь, что код / всегда будет иметь смысл порядкового
номера (адреса) ячеек ic Лг° 00000 до № 00031. Этот код мы будем
называть индексом *. Условимся также, что слова, хранящиеся в этих ячейках,
будут иметь следующий 'формат
Знак 29 А 212° 21* S 22212°
шзш
\2Ж2Ш
16
15\14\
Другими словами, в каждой такой ячейке будут храниться два целых
числа А и 5. ,
Код В мы будем рассматривать как порядковый номер (адрес) ячеек
с М0003'2 и Аг° 00063. Этот код мы будем 'называть базой. В ячейках с
указанными номерами будут храниться управляющие слова, формат
которых:
2*5 у12 ?11
\ЗЩ
16
15\
14\
13\
12\
212°
т. е. неполноразрядные целые числа.
Установим теперь новые правила грамматики. При выполнении любой
арифметической или логической команды, а также команды передачи
выполняется следующее:
по адресу / из соответствующей ячейки извлекается управляющее
слово;
часть А этого слова прибавляется к части S\ полученная сумма,
S\ записывается на место S и прибавляется к адресной части А команды;
по адресу В извлекается содержимое соответствующей ячейки и
прибавляется к адресной части А команды.
Таким образом, истинная адресная часть (существительное) новой
команды представляет собой сумму четырех чисел: Л, А, 5 и Ь. Коды /
и В выполняют функции прилагательных, так как они частично изменяют
и уточняют смысл основного существительного. Выполнение, например,
команды сложения можно представить теперь символически следующим
образом:
CMIBA<Un> + <A+S1 + b> -+Щ1.
* Соответственно ячейки от № 00000 до № 00031 называются индекс-
регистрами.
22
Условимся, наконец, что в ячейке № 0000 всегда хранится 0. Поэтому
если на месте кодов I и В мы запишем нули, то к адресной части А
также будут прибавляться нули и в такой команде истинной адресной
частью будет само число А.
В связи с введением управляющих слов условимся вообще всякое
машинное слово рассматривать как состоящее из двух частей. Разряды слова
с номерами от 1 до 14 мы будем называть правой частью слова, а
разряды с номерами от 15 до 32 мы будем называть левой частью слова.
Тогда М можно присвоить следующий смысл. Если М равно 00, то команда
выполняется точно так же, как и раньше. Если М равно 01 {/), то
соответствующая операция выполняется только над левой частью 'слова.
Наконец, если М равно 10 (2), то соответствующая операция выполняется
только над правой частью слова. Из сказанного видно, что код. М
выполняет функции наречия. Он служит поясняющим кодом к -коду-глаголу.
Заметим, что на этот раз изменения машинно-ориентированного
языка потребовали внесения некоторых изменений в конструкцию машины,
поскольку сформулированные .выше новые правила грамматики требуют
выполнения дополнительных операций в центральном процессоре. Однако
эти изменения незначительны, а получаемый от них эффект, как мы вскоре
убедимся, очень велик.
Перепишем теперь составленную нами выше программу вычисления
функции ех на новый машинно-ориентированный язык (для удобства
отдельные коды каждой команды мы будем отделять друг от друга
пробелами):
800001 : П V 0 00 34 0О0О0 ВОООИб : П1 0 00 33 00032
800002 : Ш 0 00 33 00035 В00017 : С 0 00 33 00033
800003 : П1 0 00 00 ОО099 В0001-8: П2 0 00 33 00032
800004 : П2 0 00 33 00031 В00019 : Л Г 0 00 33 ОООЗЗ
В00005: П1 0 00 00 00099 В00020 : П2 0 00 33 00034
В00006: П2 0 00 33 00032 В00021 : Л Г 0 00 33 00034
800007 : П1' 0 00 00 00099 В00022: Н2 0 00 33 00023
800008 : П2 0 00 S3 ОООЗЗ В00023: П2 0 00 ЭЗ О0О34
В00009: П1 0 00 33 00033 ВООО04 : В 0 00 33 00034
В00010 : У 0 00 33 00035 В00025 : У 0 00 00 00300
ВО0ОИГ : Д 0 00 33 00031 В00026: П2 0 00 33 0О034
800012 : П2 0 00 33 00033 В00027 : П1< 0 00 33 00032
800013 : П1| 0 00 33 О0031 В000'28 : В 0 00 33 00034
800014 : С 0 00 00 00099 В00029: НЗ 0 00 33 00008
800015 : П2 0 00 33 0ОО31 ВО003О: П1 0 00 33 00032
В00031 : НО 0 00 00 46383
Буква В, с которой начинаются все метки, означает, что теперь программа
хранится во внешней части запоминающего устройства машины. Команда
ВОООЗ'1 безусловно передает управление после окончания выполнения
программы в ячейку Л£ 16383. Это — последняя ячейка ЗУ. Мы будем
называть ее ячейкой возврата. В остальном программа полностью совпадет с
программой, приведенной на стр. 21, и комментировать ее не имеет
смысла. Заметим только, что последняя программа 'может быть использована
для вычислений только после того, как она будет переведена в
оперативную часть памяти, а в ячейки Лг° 00033 и № 00034 будут помещены
соответствующие числа.
Условимся теперь, что любую стандартную программу мы будем
помещать для ее выполнения в ячейки оперативной ^асти ЗУ, начиная с
с № 16000. В соответствии с этим обогатим словарь
машинно-ориентированного языка новой командой
Пб MIBA <Л+51 + &>-^1Ш)0+51,
что означает: передать слово из ячейки № (A+A+S + b) оперативной
части ЗУ в ячейку № (16000+S1) оперативной части ЗУ. При составлении
этой команды мы воспользовались общим правилом, гласящим, что
средствами языка необходимо отражать только те явления, которые могут из-
1меняться. В частности, номер ячейки 16О00 не изменяется, и поэтому он
никак не отражен в данном предложении.
23
Теперь предположим, что стандартной .программе вычисления функции
ех соответствует управляющее слово следующей структуры:
Разряды 23—3'2 Разряды 15—28 Разряды 1—14
— '1'
количество команд
стандартной программы (31)
адрес первой команды
стандартной программы
(В00001)
Пусть это слово постоянно хранится, например, в ячейке М 00080. Кроме
того, пусть, например, в ячейке Л£ 00076 постоянно хранится число 16000
Пусть, наконец, адрес числа х (аргумента функции ех) находится в
ячейке № 00077, а в ячейку № 16383 помещена команда вида:
НО 0 00 00 Z,
где Z — пока неизвестный 1нам адрес. Тогда мы можем составить
программу:
00064 : П1 0 00 32 00000 <00080> -> ЦП
00065 : П2 ib 00 00 000011 <ЦП>Л-+ 00001
00066 : П2 2 00 00 00031 <ДЯ>„-> 00031
00067 : П6 0 01 31' 00000 <£00000+А+5 + 6> «- 1.6000 +Л+5
00068 : П Ь 2 00 00 000О1 «Ю001 > я-> ЦП
00069 : Н2 0 00 00 00067 Если <ЦП > 0, 00067 -» УУ
00070 : ПГ 0 00 00 00076 <00076> -> ЦП
00071': С 0 00 00 00033 <ЦП> + <00033> -> ЦП
00072 : П2 0 00 00 00033 <ЦП> -> 00ОЗЗ
00073 : П1 0 00 00 00077 <0О077> -> ЦП
00074 : П2 0 00 00 00034 <ЦП> -> 00034
00075 : НО 0 00 00 .16000 .16000 -> У У
Эта программа требует .подробных комментариев. По команде 00064
в центральный процессор передается содержимое ячейки ЗУ, адрес
которой хранится в ячейке М 00032. Предполагается, что в ячейку 00032
предварительно был помещен адрес (в данном случае 00080) управляющего
слова, структура которого была показана выше. Таким образом,
управляющее слово, являющееся представителем данной стандартной
программы, оказывается переданным в центральный процессор. По команде
00065 левая часть управляющего слова, т. е. часть, содержащая число
команд в стандартной программе, и число —4 передается в ячейку 00001.
При передаче эта часть сдвигается, т. е. количество команд занимает
разряды с 1 по 14, а число —1 — разряды с 15 по 24.
По команде 00066 в^ ячейку 000031 передается правая часть управляющего
слова, т. е. часть, содержащая адрес первой команды стандартной
программы во внешней части ЗУ. По команде 00067 последняя команда
стандартной программы передается из внешней части памяти в ячейку
№ 16000+N оперативной части памяти, где N — количество команд в
стандартной программе, уменьшенное на единицу. По команде 00068
правая часть содержимого ячейки № 00001, т. е. число «S1, передается га
центральный процессор. По команде 00069 (управление передается в ячейку
Л£ 00067, если содержимое центрального процессора больше нуля. Цикл
продолжается до тех пор, пока вся стандартная программа не окажется
полностью переданной в оперативную часть ЗУ. При этом первая команда
стандартной программы окажется в ячейке № 16000. Когда этот процесс
закончится, будет выполнена команда 00070, по которой содержимое
ячейки М 00076, т. е. целое число 'ЮООО, будет передано в центральный
процессор. По команде 00071 число 16 000 сложится с содержимым ячейки
№ 00033 и результат сохранится в центральном процессоре. Нормально
ячейка Л<? 00033 содержит нули, следовательно, в центральном процессоре
окажется число 16000. По команде 00072 это число будет передано в ячсй-
24
ку № 00033. Вспомним, что во многих командах стандартной программы
вычисления 'функции ех код В имеет значение 33. Следовательно, к
адресной части этих команд теперь будет прибавляться число 16 000. По
команде 00073 содержимое ячейки № 00077, т. е. адрес аргумента, будет
передано в центральный процессор. Этот адрес по команде 00074
передается в ячейку № 00034. Вспомним, что в первой команде стандартной
программы вычисления функции ех код В имеет значение 34, таким
образом, стандартная программа снабжена теперь истинным адресом
аргумента х. Наконец, по команде 00075 управление безусловно передается в
ячейку № 16000 и, начиная с этого момента, будет выполняться
стандартная программа. Когда выполнение стандартной программы закончится,
управление будет безусловно передано в ячейку возврата № 16383.
Рассмотренную программу можно назвать программой вызова
стандартной программы. Действительно, она осуществляет перепись
стандартной программы в оперативную часть ЗУ и снабжает стандартную
программу всей необходимой информацией. Заметим также, что все данные,
свидетельствующие о том, что речь идет именно о стандартной программе
вычисления функции ех, не содержатся в самой программе вызова. Они
заключены в управляющем слове и в ячейке № 00077. Поэтому
составленную программу можно назвать стандартной программой вызова
стандартных программ. Поскольку она является универсальной и может
быть использована для вызова любой стандартной программы, она будет
постоянно находиться в ячейках ic № 00064 по № 00075 оперативной
части ЗУ.
Теперь мы имеем следующее. Во внешней части ЗУ хранится
любое количество любых стандартных программ. Каждая из этих программ
имеет в оперативной части ЗУ своего «представителя» в виде
управляющего слова. Эти управляющие слова хранятся в раз и навсегда
отведенных для них ячейках. Кроме того, ячейки оперативной части ЗУ (начиная
с № 16000) отведены для размещения той стандартной программы,
которую необходимо выполнять по ходу решения задачи. Имеются некоторые
свободные ячейки, а именно: ячейка № 00077, отведенная для аргумента
функции, и ячейка возврата № 16383, а также некоторые ячейки, в
которых постоянно хранятся «константы», т. е. 1, Ш6 и т. д. Имеется, наконец,
стандартная программа вызова стандартной программы, размещенная в
раз и навсегда отведенных для нее ячейках.
При таких условиях, для того чтобы организовать выполнение данной
стандартной программы, необходимо только: а) записать в ячейку №00032
адрес управляющего слова — «представителя» данной стандартной
программы; б) записать в ячейку № 00077 адрес аргумента функции,
подлежащей вычислению; в) записать в ячейку № 16383 команду, по которой
будет осуществлен возврат после выполнения стандартной программы.
Все три последних действия могут быть выполнены по одной
команде. Рассмотрим, например, команду:
Z : EKMIBA.
Для человека эта команда означает: вычислить функцию ех от
аргумента х, адресом которого является число A+Sl + b, результат вычисления
хранить в центральном процессоре. Для машины эта же самая команда
имеет следующий смысл: а) число A+Sl + b пометить в ячейку
№ 00077; б) в ячейку № 00032 поместить число 00080 (адрес
управляющего слова — «представителя» стандартной программы ех)\ в) в ячейку
№ 16383 поместить команду НО 00 00 (Z+1), где Z — метка самой
команды ЕК\ т) передать управление в ячейку № 00064.
Такие команды, которые имеют различный смысл для машины и для
человека, получили название псевдокоманд. Для того чтобы отличать
псевдокоманды от обычных команд, мы будем записывать их код операции
двумя буквами.
Теперь мы в основном завершили конструирование
машинно-ориентированного языка. Окончательный словарь этого языка содержит теперь
коды-глаголы, в число которых входят все ранее рассмотренные колы
25
операций, включая код Пб, а также любое количество кодов
псевдоопераций, в число которых можно включить, 'например, ЕК — экспонента,
СИ — синус, КС — косинус, ТН — тангенс, ЛН — логарифм, а также
любые другие сложные операции. Заметим, что добавление к словарю HOj-
вого кода псевдооперации не требует никаких конструктивных изменений
в машине. Для этого нужно только ввести во внешнюю часть памяти
машины соответствующую стандартную программу, а в оперативную часть
памяти — управляющее слово — «представителя» этой стандартной
программы. Таким образом, машинно-ориентированный язык является языком
открытым, ©н может неограниченно обогащаться.
Кроме кодов-глаголов, в словарь машинно-ориентированного языка
входят коды-существительные, роль которых могут играть теперь адреса
запоминающих ячеек № 000200 до № 15999 (начальные и конечные
номера, как указывалось выше, мы зарезервировали для специальной
информации), коды-прилагательные (коды I я В) и, наконец, коды-наречия
(код М).
Значительно обогатились также правила грамматики
машинно-ориентированного языка. С другой стороны, структура предложения по-дрежнему
оказывается жесткой. Каждый член предложения имеет постоянную длину
и занимает в предложении строго определенное место. Эти ограничения
в известной степени уменьшают свободу пользования языком для человека,
и введены они .исключительно исходя из потребностей машины. Известное
неудобство вызывает также необходимость снабжать каждую команду
меткой. Последнее также имеет целью облегчить для машины ввод и
размещение программы. Все только что сказанное и явилось причиной тому,
что сконструированный нами язык получил название
машинно-ориентированного.
По сравнению с внутренним языком машинно-ориентированные языки
предоставляют человеку значительно больше удобства. Во-первых, при
пользовании такими языками человек имеет возможность оперировать с
привычным ему алфавитом, а также привычной записью чисел в
десятичной системе счисления. Во-'вторых, словарь машинно-ориентированного
языка может содержать любое количество достаточно сложных
псевдоопераций, что избавляет человека от необходимости каждый раз
составлять или хотя бы хранить соответствующие программы. Наконец,
в-третьих, наличие кодов-прилагательных в известной мере избавляет человека
от забот, связанных с размещением исходных данных и программ в
ячейках запоминающего устройства. Как мы увидим в дальнейшем, этот
процесс, получивший название «разметки» запоминающего устройства, может
быть полностью автоматизирован.
Все перечисленное достигнуто нами за счет того, что почти нэ
изменяя конструкции машины, мы резко повысили ее «интеллектуальный
уровень», введя напостоянно в запоминающее устройство большое
количество разнообразной информации. После того как были введены
стандартные программы, машина как бы выучила наизусть правила вычисления
некоторых функций. Заметим попутно, что перечень стандартных программ
отнюдь не ограничивается вычислением функций. Это могут быть,
например, программа для игры «в шашки, содержащая в себе правила
выполнения ходов и оценки игровых ситуаций, программа перевода с одного
языка на другой или что-либо иное. После того как были введены
программа вызова стандартных программ, управляющие слова и константы,
машина научилась самостоятельно пользоваться приобретенными
знаниями. Наконец, программы ввода-перевода и вывода-перевода обеспечили
машине возможность понимать машинно-ориентированный язык и
общаться на этом языке со своим оператором. Напомним здесь, что для
передачи информации внутри машины по-прежнему используется внутренний
язык и только он.
Вся перечисленная информация объединяется сейчас под общим
названием интерпретирующей системы. Для машин различных типов
составлено много интерпретирующих систем и некоторые из них оказываются
чрезвычайно сложными. Каждая интерпретирующая система порождает
26
свой собственный машинно-ориентированный язык. Такие языки часто
называют также автокодами. Интерпретирующие системы могут
обогащаться за счет введения новых стандартных программ и это, в свою
очередь, приводит к обогащению словаря соответствующего языка. С другой
стороны, всякое изменение интерпретирующей системы связано со
значительными трудностями. Поэтому совершенно естественным является
желание иметь для каждой машины некоторый, раз навсегда составленный
набор интерпретирующих систем, каждая из которых должна быть
наилучшим образом приспособлена к решению некоторого определенного
класса задач. Таким образом, мы впервые приходим к идее ориентации
интерпретирующей системы, а следовательно, и языка на некоторый
определенный класс задач.
Глава 4
Простейшие проблемно-ориентированные языки
Попробуем сконструировать язык, с помощью которого было бы
удобно описывать процессы вычисления по формулам. Такие процессы
встречаются особенно часто при инженерных расчетах.
До сих пор для описания языков мы пользовались обычным
(натуральным) русским языком. Однако по мере повышения требований к
самому языку повышаются требования и к средствам его описания. Поэтому
в дальнейшем нам будет удобнее пользоваться символами специального
языка, предназначенного для описания языков. Эти символы получили
название «металингвистических».
Понятия описываемого языка, или линвистические понятия,
заключаются в специальные скобки < >. Кроме того, используются следующие
символы:
: : = — означает по определению;
\ — или.
Если два 'или более языковых понятия записываются друг за другом без
какого-либо разделительного знака, то это означает, что они должны
следовать друг за другом в том порядке, в каком они записаны.
Воспользуемся теперь металингвистической символикой для описания
нового проблемно-ориентированного языка. Этот язык, или во всяком случае
очень похожий на него, называется ФОРТРАН. Название это
представляет собой сокращение двух английских слов FORmula TRANslation, т. е.
язык для перевода формул.
Начнем с алфавита:
<бу,ква> : : =A|B|ClD|5|F|QlHlI|J|K|L|M|NlO|P|Q|R|S|TlU|
V|W|X|Y|Z
<ц.ифра> : : =0| 1 | 2 | 3 | 4 1 5 | 6 1 7 1 8 | 9.
<аперация> : : =+ |—( * | / | **
<символ> : : = <буква>|<цифра>| <юперация>|.|, |: | ;| : =
Сразу видно, что металингвистическая еимволика достаточно проста и
удобна. Написанное выше означает, что алфавит языка включает в себя
26 заглавных"букв латинского алфавита, 10 арабских цифр от 0 до 9,
символы операций и некоторые знаки лрепинания. Отметим также методику,
принятую при описании языковых понятий. Сначала описываются более
простые понятия, а затем с помощью уже введенных описаний — более
сложные.
Следующим языковым понятием является идентификатор:
27
<идентификатор> : : =<:б,уква>/ <идентификатор>
<буква> < идентификатор > <цифра>.
Отметим принятый здесь рекурсивный 1 способ описания: по определению,
идентификатор — это просто одна буква или два символа —
идентификатор (т. е. буква) и буква (или цифра) — или три символа —
идентификатор (т. е. две буквы или буква и цифра) и буква (или цифра) и т. д
Другими словами, идентификатором может быть любая
последовательность, составленная из букв или цифр, при условии, что на первом месте
обязательно стоит буква. Например, все сочетания Н, X, Н581, TERM,
CURENT, VOLTAGE, SUM, SQL5Mi и т. д. являются идентификаторами,
а сочетание 5HPN4 не является идентификатором, .потому что на первом
месте здесь стоит цифра.
Идентификатор — это одно из основных понятий в
проблемно-ориентированном языке. Он представляет собой обобщение понятия адреса
Вспомним, как мы говорили во второй главе, что в машине предмет, над
которым выполняется действие, или машинное слово не имеет собственных
отличительных особенностей. Поэтому каждому машинному слову мы
присваивали имя, причем таким именем служил порядковый номер (или
адрес) ячейки запоминающего устройства В простейшем языке именами
машинных слов (существительными) были коды, состоящие из нулей и
единиц. В ходе дальнейшей эволюции эти коды были заменены десятичными
числами. Затем с введением индексных и базовых регистров .в качестве
имен машинных слов стали использоваться сложные сочетания (суммы).
Так мы постепенно подошли к понятию идентификаторов.
Идентификатор — это имя предмета, над которым выполняется действие. Как видно
из приведенного выше определения, идентификатор ни прямо, ни косвенно
не указывает адреса ячейки ЗУ. Однако имеется в виду, что в процессе
перевода с проблемно-ориентированного языка на
машинно-ориентированный (а затем на внутренний язык) каждому идентификатору будет
поставлен в соответствие адрес одной запоминающей ячейки или даже цз-
лая группа таких адресов.
Язык ФОРТРАН позволяет описывать в качестве предметов, над
которыми выполняются действия, значения, переменные и функции. Значения
бывают двух типов — целые и действительные:
<целое З1начение> : :=<«ц1ифра> | <делое значение>
<цифра>
<деиствительное 31начерние> : : =<целое з-начание>. <щиф-
ра>|Действительное значение> <цифра>.
Например: 25; 217; 51Ф; .21512; .7,11326; 21.512; 325 4153.
Как видно из описания и примеров, понятие значения совпадает с
обычными понятиями целых чисел, правильных и неправильных дробей, только
вместо десятичной запятой пишется точка, а ноль (целых) перед точкой не
пишется. Первая из этих двух особенностей объясняется тем, что в
Англии и США вообще вместо десятичной запятой используется точка. Кромз
того, в машинном языке по возможности каждый символ должен иметь
один-единственный смысл, а запятая в нем, как мы скоро увидим,
используется для других целей. Ноль перед точкой не пишется по соображениям
экономии.
При вводе в машину данных по программе ввода-перевода целые
значения переводятся в двоичную систему счисления и записываются в вид о
машинных слов в формате целых чисел. Действительные значения также
преобразуются в двоичную систему счисления и записываются в формате
с плавающей запятой.
Итак:
1 В данном случае рекурсивным называется такой способ определи
ния, когда новое понятие определяется через уже известное.
28
<значение> : : =<целое значение> | <дейст!Витель(ное зна-
чение>.
Переменные в языке ФОРТРАН делятся на два класса: простые
переменные и массивы. Каждый класс в свою очередь делится на два типа:
целые и действительные.
<целое> : : = 11 J | К | N | <целое> <цифра> | <целое>
< буква >.
Целые переменные описываются идентификаторами, у которых на первом
месте может стоять только одна из четырех букв: I, J, К или N.
<1дей!ствикгбльное> : : =
A|B]C|D|E|F|G|H|L|M|0|P|Q|R|S|T|U[V|W|X|Y|Z
<дейсшительное> <цифра>|<действительное> <буква>.
Действительные переменные описываются идентификаторами, у которых на
первом месте может ,стоять любая буква, кроме I, J, К Л N.
<ггростая -переме.Н1ная> : : =<целое>|<действитель1Ное>.
Массив описывает одну из некоторых упорядоченных групп
переменных. Пусть, например, имеется упорядоченная группа (строка) переменных:
$ь ^2, ..., 5/, ... sn. Тогда переменная из этой группы будет описана как
S (I). Другими словами,
<массив> : : = <идентиф'Икатор массива> (<целое>).
Имеется в виду, что при выполнении программы переменной I будет
присвоено некоторое значение, после чего вся конструкция будет представлять
собой имя переменной s/ из рассмотренной выше строки.
Вся строка целиком описывается с помощью специальной конструкции,
называемой описанием массива:
<олисание массива> : : = 01МЕН51(Ж<идентификатор
массива> (<целое значение>).
Например, запись DIMENSION М(ЮО) означает, что имеется строка,
состоящая из 100 переменных: ть т2, ..., тюо. Программа ввода-перевода
отведет для массива М 100 последовательных ячеек ЗУ, причем
идентификатору массива М будет поставлен в соответствие некоторый адрес &, а
запись M(N) будет означать то же самое, чтю и адрес & + N. Определим
теперь окончательно
<перемен1ная> : :=<п«ростая перемен'ная>| <массив>.
В языке ФОРТРАН описываются .следующие функции:
<функция> : .:=ABS(E)|ENT(E)(SQRT(E)[SIN(E)/
|COS (Е) | ARCTG (Е) / LN (E) j EXP (E).
Буквой Е обозначено здесь некоторое выражение (см. ниже). Функции
имеют следующий смысл. Если х ■— это значение выражения Е, то
ABS(E) —модуль (абсолютное значение) х.
ENT(E) —целая часть х.
SQRT(E) —квадратный корень х.
SIN(E) — синус х.
COS (Е) — косинус х.
ARCTG(E) —главное значение арктангенса х.
LN(E) — натуральный логарифм х.
ЕХР(Е) —экспоненциальная функция х.
29
С точки зрения машины функции -имеют тот же смысл, что и
псевдооперации в машинно-ориентированном языке.
Из значений, переменных, функций и операций составляются
выражения:
<опе,рация> : := + |—1*|/|**
<операнд> : : =<1пу€то>|<значе«ие>|<переменная>|
<«фуН'Кция>| (<выражеше>)
|<тер.м> : : = <операнд>|<терм>**<опера1Нд>
<мультипликативная операция> : : =*|/
<мультипликативный терм> : : = <тер<м>
<мультипликативный тер'мХмультипликативиая операция><терм>
<аддитивная операция> : : =+ —
<:ВЫ1раж©ние> : : = ^мультипликативный терм>| <выраже-
ниеХаддитивиая операцияХмультипликативный терм>.
Для формального определения понятия «выражение» нам пришлось ввести
ряд промежуточных языковых понятий: пусто, т. е. пустое (состоящее из
одних нулей) машинное слово, операнд, терм, мультипликативная
операция, мультипликативный терм, аддитивная операция, смысл которых ясен
из описания. Отметим снова рекурсивный характер металингвистических
описаний. В частности, само выражение здесь может входить в качестве
операнда в более сложные выражения.
Символы операций (в выражениях означают следующее: + сложить,
— вычесть, * умножить, / разделить, ** возвести в степень. Из
формального описания видно, что в первую очередь всегда выполняется операция
**, затем операции * или / и уже затем операции + или —. Если этих
правил оказывается недостаточно для задания требуемого .порядка
выполнения операций, пользуются скобками.. Например, в выражениях: А*В +
+ С**2; SQRT (A— B**3); A**2+'2*A*B+B**2; SIN (2*T)*SQRT*
*(ARCTGi(X — Y**!2)) 'порядок действия очевиден. В выражениях
P/2+SQRT((P/2)**2 —Q); (А+В)*(А— В); (((А4*Х+АЗ)*Х+А2)*
*Х+А0) порядок действий определяется скобками. Наконец, в
выражениях: + .2891; — 12.78; +Р/2 — 2179*Х(А— 1(2.56)**2 в качестве
первого операнда используется «пусто».
В машине всякое выражение имеет смысл приказа на выполнение
соответствующих операций. Мы же можем считать, чтв все операции уже
выполнены и вычислено одно определенное значение, которое мы и
принимаем за значение данного выражения. Следовательно, выражение, так
же как и идентификатор, может принимать различные значения,
определяемые значениями входящих в него операндов. С точки зрения функций,
выполняемых в предложении, выражение представляет собой имя
некоторого значения (машинного слова).
Особую грамматическую категорию, как и во всех предыдущих
языках, составляет метка
<-метка> : : = <|Цифра>| <.метка><<цифра>.
Перейдем теперь к рассмотрению средств описания действий.
Простейшими среди них являются операции. Однако, как правило, операции в
языке ФОРТРАН не имеют самостоятельного значения и используются
только при составлении выражений. Кроме операций, для описания
действий используются также операторы. Важнейшим среди них является
оператор присваивания:
<оператор присваивания> : : = : = .
Пусть А— это идентификатор, а Е — это некоторое выражение. Тогда
запись А : =Е будет означать присвоить идентификатору А значение
выражения Е. Оператор присваивания отражает одну очень важную характерную
особенность символических, языков, а именно — возможность просто опи-
30
сывать с их похмощью динамику развития процессов, происходящих в
машине. Действительно, как следует из сказанного выше; идентификатор
является именем машинного слова (или группы слов) и с этой точки
зрения он всегда имеет какое-либо значение. В частности, это значение может
быть равным нулю или же оно может быть неизвестно. Смысл оператора
присваивания состоит в том, что старое значение идентификатора
аннулируется и вместо этого идентификатору присваивается новое значение. При
выполнении оператора присваивания в данную ячейку (или ячейки) ЗУ
записывается новое машинное слово. Этот процесс аннулирования одного
машинного слова и записи на его место нового и отражает оператор
присваивания.
Кроме оператора присваивания, в языке ФОРТРАН имеются также
следующие операторы: оператор перехода, условный оператор, оператор
останова и оператор печати.
Оператор пе-рехода> : : =ООТО<метка>.
Оператор перехода определяет порядок чтения предложений. Смысл
записи GO TO 26 состоит, например, в том, что вслед за ней читается
предложение, помеченное меткой 26,
<условный оператор> : : =1р(<!выражение>) <метка>,
<метка>, <метка>.
Условный оператор также определяет порядок чтения предложений,
однако в данном случае этот порядок зависит от некоторого условия.
Например, запись: IF(QST — .25)5, 11, 18 означает: если значение выражения
QST —. 2Ъ меньше нуля, переходи к чтению предложения, помеченного
меткой 5. Если значение выражения QST — .25 равно нулю, переходи к
чтению предложения, помеченного меткой VI. Наконец, если значение
выражения QST —. 25 больше нуля, переходи к чтению предложения,
помеченного меткой '1'8.
<оператор останова> : : =STOP.
Оператор останова указывает на необходимость остановить вычисления.
<юператор шечати> : : =PRINT<MeTKa>, <идентифика-
тор >.
Оператор печати указывает на необходимость вывода из машины
некоторой группы цифр, букв или символов, представляющих собой значение
идентификатора. Что именно нужно печатать, определяется специальной
конструкцией, которая называется описанием формата. Описание формата
всегда снабжается меткой. Эта метка и входит в состав оператора печати.
Описания формата бывают двух типов. Первый из них
предусматривает печать некоторого текста, т. е. произвольной последовательности
символов.
«Описание формата> : : = Р01ШАТ(<целоезначение>
символов <текст>).
Например, запись FORMAT (35 символов ОШИБКА В ОПРЕДЕЛЕНИИ
ВЕЛИЧИНЫ СУММЫ) означает, что надо отпечатать текст, выделенный
заглавными буквами, всего 35 символов. Второй тип предусматривает
печать значения в форме с плавающей запятой.
Описание фо-р'мата> : : =РОНМАТ(Е<целое значение>,
<целое значение>).
Например, запись FORMAT (Ell. 6) означает, что число 41'2,34 должно
быть отпечатано в виде А12340Е+ОЗ, что означает 0,4Ч'234ОХ 10+°*.
Первое целое значение в описании определяет общее количество печатаемых
символов, а второе — количество десятичных знаков после точки.
31
В словарь языка ФОРТРАН входит еще одно слово END. Это
вспомогательное слово, определяющее конец программы.
Заметим, что обозначения операторов GO TO, FORMAT и т. д.
формально совпадают с определением идентификаторов. Это
последовательности букв, начинающиеся с буквы. Однако все сочетание STOP, FORMAT,
PRINT, ARCTG, GOTO, IF, SQRT, ABS, ENT, SIN, COS, LN, END, EXP
не являются идентификаторами. Это исключения из данного
грамматического правила.
Из отдельных слов языка ФОРТРАН составляются предложения. Эти
предложения называются фразами. В языке ФОРТРАН можно составлять
фразы различных типов, а именно: фраза присвоения, фраза перехода,
условная фраза, фраза печти, фраза останова, фраза описания формата.
Отдельные фразы объединяются в блоки. В пределах блока фразы отделяются
друг от друга точкой с запятой Каждый блок начинается с новой строки
и снабжается меткой.
Все сказанное выше представляет собой правила грамматики языка
ФОРТРАН. Очевидно, что эти правила значительно сложнее
соответствующих правил машинно-ориентированного языка.
Посмотрим теперь на примере, как описывается на языке ФОРТРАН
процесс вычислений. Пусть, например, необходимо вычислить следующую
формулу:
s = \nx+ Y*2 — у2 + ех s'mw, (5)
причем известно, что входящие в эту формулу переменные имеют
следующие значения: х=2Л598, #=17,3561, z = 9,7015, ш= 1,7030 (аргумент
функции SIN записывается в радианах). Соответствующая программа,
записанная на языке ФОРТРАН, будет иметь вид:
1 :Х: = 2Л598; Y:= 17.3561; Z: = 9.7015; W: = 1.7030;
2:S: = LN(X)+SQRT(X**2 — Y**2)+EXP(X)*SIN(W);
3: FORMAT (El 1,6);
4: PRINT 3,S; STOP; END.
Блок, помеченный меткой 1 (как и раньше, метка отделяется
двоеточием), предусматривает присваивание значений идентификаторам "X. Y, Z
и W. Блок, помеченный меткой 2, предусматривает вычисление выражения,
стоящего справа, и присваивание значения этого выражения
идентификатору S. Блок, .помеченный меткой 4, предусматривает печать значения
идентификатора S по формату, определяемому блоком 3, т. -е. с шестью
значащими цифрами после запятой. Затем производится останов машины.
Что же будет происходить в машине, когда она получит такую
программу? Прежде всего вступает в действие уже известная нам программа
ввода-перевода, flo этой программе все символы, участвующие в записи
текста на языке ФОРТРАН, будут преобразованы в форму машинных
слогов («см. ст. 9) и записаны в ЗУ машины последовательно один за
другим.
Затем вступает в действие программа распознавания идентификаторов.
По этой программе все машинные слоги один за другим поступают в
центральный процессор. Там последовательно производится сравнение
каждого предыдущего слога с каждым последующим. Если обнаруживается,
что слогу-букве предшествует, например, пробел или символ операции,
вырабатывается специальный сигнал начала идентификатора. Затем этот слог
и следующие за ним слоги, имеющие смысл букв или цифр, передаются в
ЗУ, где из них формируется одно машинное слово. Таким образом,
образуется перечень слов — предполагаемых идентификаторов. Дальше по той
же программе все эти слова сравниваются друг с другом. Если
обнаруживаются два одинаковых слова, то одно из них исключается из перечня.
Оставшиеся в перечне слова сравниваются со словарем
символов-операторов, Каждое слово, совпавшее с одним из символов-операторов, также
исключается из перечня. Оставшиеся в перечне слова представляют собой
полный список идентификаторов данной задачи.
32
Теперь вступает в действие программа присвоения адресов, ло
которой каждому идентификатору списка ставится в соответствие адрес
запоминающей ячейки. Если в процессе распознавания обнаружено, что данный
идентификатор является идентификатором массива, то ему ставится в
соответствие несколько последовательных адресов, число которых равно
целому значению, записанному в скобках после идентификатора массива.
Вслед за этим начинает действовать программа распознавания
операций. Снова все слоги исходного текста на языке ФОРТРАН передаются в
центральный процессор. Точно так же, как и в предыдущем случае, по
программе распознавания операций составляется перечень символов
операций, операторов и функций. Одновременно производится подсчет
открывающих и закрывающих скобок. С помощью этого подсчета, а также
известных правил устанавливается порядок выполнения операций, который
учитывается при составлении перечня. Затем каждому символу ставится
в соответствие операция или псевдооперация из словаря
машинно-ориентированного языка.
Теперь вступает в действие программа формирования команд.
Сформированные по этой программе команды и псевдокоманды записываются
в порядке их выполнения и снабжаются метками. На заключительном
этапе производится заполнение индексных и базовых регистров. Обычно
для этого .служит специальная стандартная программа. После завершения
выполнения программы формирования команд управление передает
интерпретирующей системе и начинается процесс, уже описанный в предыдущей
главе.
Все описанные выше программы объединяются под общим названием
компилирующей системы. Компилирующая система достаточно сложна и
поэтому мы не делаем здесь даже попытки расписать в командах хотя бы
отдельные фрагменты ее. С другой стороны, читатель уже достаточно
подготовлен и может представить себе в общих чертах, как работает та или
иная программа компилирующей системы. Основным залогом успеха здесь
является однозначность слов и строгость грамматических правил
проблемно-ориентированного языка. Как бы ни был сложен процесс компиляции,
каждый символ в языке имеет единственный, строго определенный символ,
а последовательности символов составляются так, что исключается
возможность какой-либо двусмысленности. Поэтому всегда могут быть
составлены соответствующие стандартные программы, с помощью которых
каждой фразе на языке ФОРТРАН будет поставлена в соответствие
программа на машинно-ориентированном языке. При этом программы
компилирующей системы представляют софой не что иное, как своеобразную
запись грамматических правил проблемно-ориентированного языка.
Компилирующая и интерпретирующая системы вместе называются
транслятором. Транслятор — это очень сложная система программ.
Различные трансляторы содержат в общей сложности от нескольких тысяч до
нескольких десятков тысяч машинных команд. Чем сложнее язык, тем
сложнее транслятор. Кроме программ, о которых говорилось выше, в
состав трансляторов включают обычно программы редактирования программ.
Задача программ редактирования состоит в том, чтобы улучшить качество
программ, получившихся после того, как компилирующая и
интерпретирующая системы закончили свою работу. Действительно, каждому тексту
на проблемно-ориентированном языке можно поставить в соответствие
несколько различных программ на внутреннем языке машины. Пусть,
например, некоторое выражение предусматривает многократное выполнение
операции сложения. Каждой отдельной операции сложения, вообще говоря,
нужно ставить в соответствие следующую стандартную программу:
k:Ul MIB А\
(& + 1):С Ml В А2
(k + 2) :П2 MIB A3
здесь А\ — адрес первого слагаемого, А2 — адрес второго слагаемого и
A3 —• адрес ячейки ЗУ, куда посылается результат. Простейшая
компилирующая система запишет подобные стандартные программы одну по
33
другой, и тогда, например, выражению Q1 + Q2— Q3 будет поставлен в
соответствие фрагмент программы
к,
(k+\)
(k+2)
(k + З)
(k + 4)
(k+5)
:П1
:C
:П2
:П1
:B
:П2
MIB
MIB
MIB
MIB
MIB
MIB
Ql
Q2
A3
A3
Q3
A3
Очевидно, что некоторые операции передачи, например,
(й + 2):.П2 Ml В A3
(k + З) :П1 Ml В A3
оказываются здесь лишними. Программа редактирования распознает эгл
лишние операции и исключает их из основной программы. Составленный
выше фрагмент после редактирования приобретает вид
&:П1 Ml В Q\
(А+1):С Ml В Q2
{k + 2) :B Ml В Q3
(k + З) :П2 MIB A3.
Таким образом, наличие программ редактирования позволяет получать
более простые и экономичные рабочие программы. С другой стороны,
программы редактирования резко усложняют транслятор.'Однако чем
сложнее транслятор, тем проще получаемые рабочие программы, и наоборот.
Заметим в заключение этой главы, что переход к новому проблемно-
ориентированному языку, также как и ранее, не потребовал внесения в
машину каких-либо конструктивных изменений. Вместо этого понадобилось
лишь составить и ввести новую систему программ, получившую название
компилирующей. Другими словами, машине были сообщены
дополнительные сведения. Теперь можно сказать, что машина обучена уже не только
правилам выполнения отдельных операций, но и достаточно сложным
правилам грамматики проблемно-ориентированного языка. Такое повышение
«интеллектуального уровня» машины позволяет общаться с ней на языке,
уже достаточно близко напоминающем обычный язык математики. Как
видно из рассмотренного здесь примера, текст на языке ФОРТРАН почти
не отличается от исходной записи формулы на языке математики.
Предусмотрены только необходимые меры, исключающие двусмысленность и
облегчающие работу программам ввода-перевода и распознавания. Так,
например, вместо обычного в математике символа оперции умножения
(• или +) введен символ*. Это исключает двусмысленность (точка имеет
здесь один определенный смысл) и не шозволяет путать символ X с
буквой X. Для операции возведения в степень использован символ **. Это
исключает для машины необходимость распознавать символы, написанные
над строкой, что, кстати говоря, очень неудобно и при перепечатке
текстов вручную на клавишной машинке. Замена символов функций и
операторов позволяет пользоваться алфавитом, содержащим меньшее количество
символов, что также представляет определенное удобство.
Наличие строгих грамматических правил позволяет легко осуществлять
контроль программ, составленных человеком. Например, если где-нибудь
в тексте встретится следующий фрагмент NQ := SUM-f .34..., т. е.
присвоение целой переменной действительного значения, то специальная
программа контроля лекго обнаружит это обстоятельство. Вычисления будут
приостановлены, и машина сообщит оператору о допущенной им ошибке
Такие программы контроля входят обязательной^составной частью во все
современные трансляторы.
34
Глава 5
Язык АЛГОЛ-60
Для иллюстрации возможностей сложных современных символических
языков мы опишем здесь некоторые особенности языка АЛГОЛ-60. Этот
язык разрабатывался группой специалистов в различных странах и з
I960 году на международной конференции был утвержден в качестве
международного языка для программирования и обмена программами. Как и
в случае ФОРТРАН, название АЛГОЛ представляет собой сокращение
двух английских слов Algorithic Language, что значит алгоритмический
язык. За последнее время язык АЛГОЛ неоднократно модернизировался.
Появились также «производные» языки: АЛГЭК, АЛГАМС и т. п.
Алфавит языка АЛГОЛ содержит всего Мб символов.
<буква> : : =А| В/С | Dt .. | Z)a /b/ic/d ].. . |z
<цифра> : : =0| 1| 2 | 3| 4 | 5 | 6 1 7 | 8| 9
<логическое значение> : : =true|false
<разделитель> : :=,|.| 10|: |; |U|step|until|while|comment]: =
<арифметическая операция> : : = + |— 1Х | / | ~r| t
<логическая операция> : : ~|=з|\/|ЛП
<операция отношения> : : =< |<[Н>|>|^
<01перация последовательности : : =go tojif |then|else|for|do
<скобка> : : = (| ) | [ | ] | « | » [begin |end
<описание> : : =own|boolean|integer|real|array|switch|
jprocedure
<спецификатор> : : = string]label|value
<сим-вол> : : = <буква> | <цифра> | <логичес.кое
значение > | <разделитель> ] <арифметический
оператор>| <логический оператор>( <опе-
ратор отношения>| <оператор последова*
тельности>| <скобка>| <описание> | <спе*
цификатор>.
Очевидно, что алфавит языка АЛГОЛ значительно богаче алфавита
языка ФОРТРАН. Здесь допускается использование как заглавных, так
и строчных букв. Из описания видно также, что записи вида: step, go to
array и т. п. воспринимаются не как последовательности букв, а как
одиночные символы. Это значит, что при вводе в машину программа ввода-
перевода переводит каждую такую запись не как последовательность
слогов, а как отдельный слог. При написании программ все эти символы
выделяются жирным шрифтом.
Значения на языке АЛГОЛ описываются в основном так же, как и в
ФОРТРАНе. С помощью разделителя ю имеется возможность записывать
значения в форме с плавающей запятой. Например: —2Г6ю+22, что
означает — 216Х10+22.
Идентификатор описывается так же и имеет тот же смысл, что и з
ФОРТРАНе. Только здесь первая буква не указывает на тип переменной.
Для обозначения типа существует специальная конструкция, называемая
описанием.
Выражения в языке АЛГОЛ делятся на три класса: арифметические,
булевы и выражения назначения. Арифметические выражения в свою
очередь делятся на простые и условные. Понятие простого арифметического
35
выражения в основном совпадает с понятием <выражение>,
определенном в предыдущей главе. Для операции умножения в языке АЛГОЛ
используется символ X. Для операции возведения в степень используется
символ t- Кроме того, в языке АЛГОЛ предусматривается еще одна
дополнительная операция деления нацело, которая обозначается
символом -К При делении нацело частное округляется до ближайшего целого
значения.
Булевыми называются выражения, которые могут принимать одно л*
двух возможных значений: true (истинно) или false (ложно). При этол!
имеется в виду, что в числе других переменных, которые описываются в
языке АЛГОЛ, 'имеются переменные (булевы), которые также могут
принимать только одно из двух возможных значений. Таким переменным
можно присваивать значения булевых выражений. Простейшее булево
выражение получается в том случае, если два арифметических выражения
связываются одной из операций отношения. Например, запись Л>В будет
иметь значение true, если значение выражения Л действительно больше
значения выражения В, и будет принимать значение false в противном
случае.
Два или более простейших булевых выражения могут объединяться в
более сложные выражения с помощью логических операций. Эти операции
имеют следующий смысл. Пусть В\ и В2 — это два простейших булевых
выражения. Тогда выражение "1 В\ будет иметь значение true в том л
только в том случае, если выражение Bi имеет значение false; выражение
В\ .А В2 будет иметь значение true в том и только в том случае, если оба
выражения и В\ и В2 имеют значение true, выражение Bi V B2—если хотя
бы одно из выражений В\ или В2 имеет значение true, выражение BiZD В2 —
если оба выражения В{ и В2 имеют значение false, либо выражение В\
имеет значение false, а выражение В2 имеет значение true, либо если оба
выражения В\ и В2 имеют значение true. Наконец, выражение В\ ~ В2 будет
иметь значение true, если оба выражения В\ и В2 имеют значение false
или значение true. Полное формальное описание простого булева
выражения имеет вид:
<отаошбние> : : =<арифметическое выражение> <опера-
ция отношения> <арифметическое вы-
ражение>
<1простейшее булево 1выражение> : : =<логическое значе-
1ние> | <перемен*
1ная> / < функция >
<отношение>|
| (<булево
выражение^ [ "1
^простейшее булево
выражение >
<булев фактор> : : =<лростейшее булево 1выражение>
|<-булев фактор> Л <простейшее
булево 'выражение>.
<булев терм> : : =<булев фактор > | <булев терм> V
<булев фактор>
<импликация> : : =<булев терм> |<импликация> =э <бу*
лев терм>
<|щростое булево выражение> : : = <имиликация>/ <>про-
стое булево выраже-
ште> = <И'мпликация>
Условное булево выражение описывается следующим образом:
36
<фрагмент if> : : = if < булево выражение>1Ьеп
<условное булево выражение> : : = <фрагме1нт if> <про-
стое булево выраже-
ние> else <булево
выражение >.
Другими словами, условное булево выражение имеет вид:
if В then Bi else B2.
Здесь В\ — простое булево выражение, а Вг — любое (простое или
условное) булево выражение. Если В имеет значение true, то все условное
выражение приобретает то же значение, что и В\. В противном случае все
условное выражение приобретает то же значение, что и В2:
<булево выражение> : : = <!простое булево выражение > |
| <условное булево выражение>
Условное арифметическое выражение описывается так:
<условное арифметическое выражен.ие> : :=<фрагмент
if><.npocToe арифметическое выражен-ие> else
<арифметическое выражение>.
Смысл здесь тот же, что и в случае условного булева выражения. Наконец,
<арифметическое выражение> : : = <Спростое
арифметическое выражен,ие>|<условное арифметическое
выражение^
Выражение назначения представляет собой обобщение понятия <мет-
ка>, рассмотренного в предыдущей главе. Вспомним, что метка входит
в состав фразы перехода или условной фразы и служит именем блока
программы, к выполнению которого нужно переходить либо безусловно,
либо при удовлетворении тех или иных условий. Выражение назначения
также служит для указания блока программы, к выполнению которого
нужно переходить. Другими словами, выражение назначения, как и всякое
выражение, может принимать различные значения, причем этими
значениями являются метки. Выражения назначения могут быть простые и
условные. Формальное описание выражения назначения имеет вид
<метка> : : =<идентификатор>| <целое значение>.
В отличие от ФОРТРАНа в АЛГОЛе меткой может быть идентификатор.
<инде1Нтификатор переключателя> : : = ^идентификатор >
<переключатель> : : = идентификатор переключателя>
[<арифметическое выражение>]
<0простое выражение назначения> : : =<метка> |
Переключатель^ |
(<выражение
назначения^
<условное выражение назначения> : : =<фрагмент if>
<простое
выражение назначе-
ния> else
^выражение назна-
че,ния>
<выражение назначения> : : =<!простое выражение назна-
37
чения>/<условное
выражение наз!начения>.
Из описания видно, что выражение назначения может быть либо
меткой (в этом случае мы приходим к тому же самому, что и в предыдущей
главе), либо переключателем. Переключатель представляет собой
своеобразную переменную с индексами. Например, SW{E) — это переключатель
Имеется в виду, что арифметическое выражение Е может принимать
только ограниченный набор целых значений. Каждому из значений выражение
Е соответствует одна определенная метка. Эти метки перечисляются з
описании переключателя, которое мы рассмотрим ниже.
Теперь можно переходить к рассмотрению операторов. Оператор
присваивания имеет тот же смысл, что и в предыдущей главе. Единственное
отличие состоит в том, что значение одного и того же выражения
(имеются в виду как арифметические, так и булевы выражения), может
присваиваться сразу нескольким идентификаторам. Тогда мы получаем
конструкцию вида
А :=55 : = QP : = TERM : = SQ64 : = £
т. е. значение выражения Е присваивается сразу всем идентификаторам:
Л, 55, QP, TERM и т. д.
Оператор перехода имеет следующую конструкцию:
<01ператор 'перехода> : : =£о1о<выраже!Ние 1наз1начен-ия>
и означает бузусловный переход к блоку программы, который
обозначается выражением назначения.
Интересной характерной особенностью языка АЛГОЛ является
наличие в нем так называемого оператора цикла. Оператор цикла указывает
на необходимость многократного выполнения некоторого следующего за
ним оператора, причем перед очередным повторением некоторой
«управляемой» переменной присваивается каждый раз новое значение. Эти значения
задаются специальным списком, который называется списком цикла.
Список цикла, в свою очередь, состоит иа отдельных элементов. Полное
формальное описание оператора цикла имеет вид:
<элемент списка цикла> : : =<арифметическое выраже-
Н'ие>|<арифметическое вы-
ражеяие> step <
арифметическое выражение>
until <арифметическое выра-
жение> | <арифметическое
выражение> while <буле-
во выражение>
<описок цикла> : : =<элемент списка цикла>| <список
цикла> , <злемент описка цикла>
<фрагмент for> : : = й>г<перемеяная> : : = <список цик-
ла> do
<опе-ратор цикла> : : = фрагмент for><o(nepaTop> ) <мет-
<ка> : <оператор цикла>.
Рассмотрим два примера. Запись
for v : = 0 step 2 until 200, X+Y — Z, 301, 304 do A
означает, что оператор А будет повторен всего 103 раза, причем
переменная v, входящая в 'состав оператора Л, будет принимать следующие
значения. Сначала ее значения будут определяться первым элементом списка
цикла. Запись 0 step 2 until 200 означает, что при первом выполнении
38
оператора А переменной v будет присвоено значение 0, затем перед
каждым новым выполнением это значение будет увеличиваться на 2 до тех
пор, пока оно не станет равным 200 (всего 101 раз). Затем
будет.использован второй элемент списка цикла, и переменная v примет значение
арифметического выражения X+Y — Z. Наконец, перед двумя последними
шагами оператора А переменная v примет значения 301 й 304.
for v : = x + i while v>ydo A
означает, что переменная v, входящая в состав оператора А, будет
принимать значения арифметического выражения x + i все время, пока булево
выр'ажение v>y будет сохранять значение true.
В языке АЛГОЛ описываются еще условные операторы, составные
операторы и блоки. Дадим формальное описание этих операторов:
<основ'Ной оператор> : : = <оператор присваивания>
|<оператор перехода>|
^пустой оператор> | <оператор
процедуры> | <метка> :
«Основной оператор>
<безуслов(НЫй олератор> : : =<осно'Вной олератор>| <опе^
ратор цикла> ) <составной
оператор>| <блок>
<0!ператор if> : : =фрагмент 1!><безусловный оператор> |
|<метка> : <оператор if>
<условный оператор> : : = <оператор if>( Оператор if>
else <оператор>
<01ператор> : : =<безусловный оператор>| <условный опе-
ратор>
<состав«ой элемент> : : =<0(ператор> end<onepaTop>;
<составной элемент>
<соста(В(Ной оператор> : : = begin <составной элемент>
|<метка> : <состав!НОЙ опе-
ратор>
<заголо'ВОК блока> : : = begin <описание> ] <заголовок
блока> ; <описа«ие>
<блок> : : =<заголовок блока> ; ^составной элемент> |
| <-метка> : <блок>.
Пустой оператор — это запись, не содержащая ничего, кроме метки.
Такой оператор может понадобиться при организации переходов.
Оператор процедуры будет рассмотрен ниже. Условный оператор использует уже
знакомый нам «фрагмент if» и ставит выполнение или невыполнение
некоторого оператора в зависимость от удовлетворения или неудовлетворения
некоторого условия. Здесь возможны две конструкции. Запись
if В then A
означает, что оператор А будет .выполнен в том случае, если булево
выражение В имеет значение true. Запись
if В then Ах else A2
означает, что если булево выражение В имеет значение true, то будет
выполнен оператор А\, а в противном случае оператор А2.
Составной оператор — это несколько записанных друг за другом и
39
разделенных знаками «;» операторов. Составной оператор заключается
между операторной скобкой begin и операторной скобкой end.
Блок содержит один или несколько операторов и так называемый
заголовок блока. Для тою чтобы точнее определить это последнее понятие,
нам надо рассмотреть еще одну грамматическую категорию языка АЛГОЛ,
а именно описания:
<описание> : : =<описание типа> | <описание ма-ссива>
/<0'писание переключателя>| <описание
■процедуры >.
Описание типа определяется следующим образом:
<список переменных> : : = <п.ростая переменная>| <про-
стая ,переме1нная> , <список етере-
мен!ных>
<тип> : := real [integer/boolean
<локальный -или собственный тип> : : = <тип> | own
<тип>
<описание типа> : : = <локальный или собственный тип>
< список 1перемшных>.
Локальный, или собственный тип используется тогда, когда надо
подчеркнуть, что данная переменная описывается только в пределах данного
блока. Описание массива имеет вид:
<нижняя граница > : : =<арифметическое выражеиие>
<верхняя граница> : : =<арифметическое выражение>
<пара лраниц> : : = <нижняя граница> : <>верхняя грани-
ца>
<список пар г.раниц> : : =<ш-ара границ>| <опиоок пар
границ> , <пара границ>
<фрагмент массива>: : = <идентификатор массива>[<спи-
сок пар 1границ>]<идентифика-
тор массива> , <фрагмент
массива >
<список массивов>: : = <фраг.мент массива>| <список мас-
сивов> , <фрагмент массива>
<описание массива> : : =аггау <список маосивов> <ло-
кальный или собственный тип>
array <список массивов>
Например, array А [0 : Гб, 0 : 1'5, 0: 10] означает множество
переменных Atjk, причем индекс i может принимать целые значения от 0 до 15,
индекс / может принимать целые значения от 0 до 1-5, а индекс k может
принимать целые значения от 0 до 10. array А, В [0 "~^~ 15, 0 "*" 15г
0 ч~ 10] означает два множества переменных A,j^ и £//#, у которых
индексы it j к k могут изменяться в указанных выше пределах Наконец,
real array U7[0:5, 0:10+*], £/[0:5, 0:7], integer array V[0:5, 0:5]
означает два массива действительных переменных Wi/ и Vи- и один
массив целых переменных V/j. /Индексы i у всех трех массивов могут
изменяться от 0 до 5 Индекс / у переменных Wу может изменяться от 0 до
-ГО+я. Индекс / у массива U может изменяться от 0 до 7. Индекс / у
массива V может изменяться от 0 до 5. Из формального описания
следует также, что массивы могут относиться к типу булевых (boolean).
Когда массив входит в состав арифметического, или булева, выражения
на месте пар границ записываются идентификаторы, принимающие
значения индексов
40
= <выражение
назначения^ |
Переключательный СЛИСОК> ,
<Выражение
назначения >
switch <индектификатор
переключателя> : = <пе-
.реключательный опи-
сок>.
Например, описание переключателя switch SH : =L1, L2, L3 содержит
три метки Ll, L2 и L3. Если арифметическое выражение (см. выше)
принимает значение 1, то соответствующее выражение назначения
обусловливает переход к выполнению блока программы, 'помеченного меткой Ы.
Если арифметическое выражение,принимает значение 2 тли 3, то
управление передается блокам L2 или L3 соответственно. Описание переключателя
switch SQ : =Ll, L2, SW [х f 2 — у] содержит две метки L\ и L2 и
выражение назначения (переключатель) SW [х \2 — у]. Если арифметическое
выражение принимает значения 1 или 2, то управление передается блокам
L:\\ (или L2. Если же арифметическое выражение принимает значение 3, то
вводится в действие переключатель SW [x f 2 — у], который должен
иметь самостоятельное описание.
Теперь мы переходим к рассмотрению одной из наиболее интересных
грамматических категорий языка АЛГОЛ — так называемой процедуре.
Описание процедуры имеет вид:
<формальный параметр > : ==<идентификатор>
<строка буйв> : : <(буква> | <строка )букв><|буква>
<разделитель •пара,метров> : : =, |) Строка букв>(
<список формальных па<раметров> : : =<формальный
параметр > | <формаль-
<ный параметр>
^разделитель
формальных
параметров Хформальный
параметр>
<совокупность формальных па<раметров> : : = < пусто >/ (
<описок формальных параметров>)
<>список идентификаторов> : : =<идентификатор> | <спи-
сок идентификаторов> ,
<'идентификато1р >
Совокупность значений> : : =<пусто> | value <описок
идентификаторов>;
<спецификатор> : : =string| <тип> | array { <тип>
array | label | switch | procedure | <тип>
procedure
<совокупность спецификац|ИЙ> : :=<пу,сто>|
Спецификатор Хсписок иден-
тификаторов> ; |
совокупность специфи-
Описания переключателей имеют вид:
<переключательный список> : :
<описание переключателя> :
41
каций> <специфика-
TQp > <СПИ€ОК ИД6Н-
тификаторов> ;
<заголовок процедуры > : : =<ид©нтификатор процедуры>
<совокупность формальных
параметров> ; <совокупность
значенийХсовокупность-
спецификаций^
<тело процедуры> : : =<оператор> | <,код>
<описание процеду)ры> : : ^procedure <заголовок строцеду-
ры> <тело |Процедуры> |
I <T*m>procedure <заголовок
процедуры Хтело
процедуры >.
Пусть, например, желательно составить стандартную программу
приближенного вычисления функции с помощью полиномов заданной степени
с заданными коэффициентами вида
Р = а0 + а1х+а2х2 + ... + апхп. (6)
Такая стандартная программа на языке АЛГОЛ будет иметь вид
описания процедуры
procedure polinom (P) от переменной (х) степени (power,
сое]] Н); value power; integer power; real array сое]]
[0 : power]; real P, x; begin integer i; i := power; P :==
сое]] [i]Xx; for i: = power — 1 step — 1 until 1 do
P :=(P +coeff [t\Xx;
i : = 0; P : = P + coeff[i] end.
Этот небольшой фрагмент позволяет нам проиллюстрировать многое
из того, что было сказано выше. Начнем то 'порядку. Первые две строки
представляют собой заголовок процедуры, а ггакже слово procedure, с
которого начинается всякое описание процедуры. Затем следует
идентификатор процедуры, в качестве которого было выбрано сочетание букв
polinom, что в то же самое время говорит о назначении процедуры. После
идентификатора до первого символа «;» следует совокупность формальных
параметров. Между первым и вторым 'параметрами, а также между
вторым и третьим введены разделители формальных параметров : ) от
переменной ( и ) степени (. Заметим, что в разделителе можно использовать
также буквы русского алфавита. Это можно делать потому, что
разделители такой конструкции не переводятся машиной (машина воспринимает
всю конструкцию как один-единственный символ «,»). С другой стороны,
в юписание процедуры вводятся дополнительные .пояснения относительно
смысла формальных параметров. Здесь уместно сказать также 'несколько
слов о самом 'понятии «формальный параметр». Как уже говорилось,,
описание процедуры мы составляли с целью обеспечить возможность
приближенно вычислять различные функции. Если понадобится на самом деле
выполнить такие вычисления, то аргумент функции совсем не обязательно
будет обозначаться буквой х, а сумма полинома — буквой Р. На место
коэффициентов полинома а/ (в описании процедуры мы заменили их
идентификатором массива coeff) будут подставлены реальные значения.
Наконец, будет введено реальное значение степени полинома. Таким
образом, идентификаторы Р, х, power и coeff в описании процедуры не имеют
самостоятельного смысла. Они только занимают места, на которые при
действительном вычислении функции будут подставлены так называемые
фактические параметры, т. е. идентификаторы, которые могут принимать
42
значение функции, значение аргумента этой функции и т. п. Если с
помощью той же процедуры потребуется вычислить другую функцию, то на
места формальных параметров будут подставлены другие фактические
параметры.
За совокупность формальных параметров следует совокупность
значений. В данном ^случае описывается только одно значение, а именно power.
Спецификатор value означает, что на место формального параметра power
каждый раз будет подставляться не переменная, а значение. Далее до
конца строки следует совокупность спецификаций. Из этой части описания
следует, что переменная power относится к типу целых, переменных Р и х
относятся к типу действительных и, кроме того, имеется массив
действительных переменных сое\\, у которых значения индекса изменяются от
нуля до некоторого целого числа, представляющего собой значение
идентификатора power. На этом заканчивается заголовок процедуры.
Тело процедуры, как и следует из приведенного выше формального
описания, представляет собой оператор, точнее, один из конкретных видов
оператора, а именно блок.
Блок начинается с заголовка блока, который, в свою очередь, (см
стр. 40) начинается с операторной скобки begin. Затем следует описание.
В данном случае описывается один-единственный идентификатор i,
который относится к типу целых. Переменная i участвует только в
промежуточных вычислениях и поэтому нет необходимости описывать ее в
заголовке процедуры.
После заголовка блока следует составной элемент. Первый оператор
этого элемента предусматривает присвоение переменной i значения power,
т. е. степени полинома. Затем переменной Р присваивается значение
переменной х, умноженной на элемент массива с индексом i, т. е. в данном
случае на коэффициент ап- Далее следует оператор цикла (см. стр. 39).
Этот оператор предусматривает повторение следующего за ним оператора
несколько раз подряд, причем в первый раз переменной i будет присвоено
значение power — 1, затем это значение каждый раз будет уменьшаться
на единицу до тех пор, пока значение переменной i не станет равным 1.
Оператор, следующий за оператором цикла, предусматривает вычисление
очередного значения суммы полинома и присвоение этого значения
переменной Р. В последней строке переменной i присваивается значение 0 и
вычисляется окончательное значение полинома (см. соотношение (й) на
стр. 12). Блок заканчивается операторной скобкой end.
Из сказанного ясно, что в состав описания процедуры, кроме
перечисления и описания формальных параметров, входит также и сама
программа вычислений. Описания процедур совместно со всеми остальными
описаниями входят в заголовок программ (см. стр. 44). Если в заголовке
некоторой программы имеется описание данной процедуры и если в
каком-то месте программы оказывается необходимым воспользоваться данной
процедурой (т. е. в данном случае вычислить полином), то для этой цели
используется оператор процедуры. Формальное описание оператора
процедуры имеет вид:
«Ссписок фактических параметров> : : =<фактический
параметр^ <описок фактических параметровХразде-
литель -параметровХфактический .параметр>
<оператор процедуры> : : = «^идентификатор процедуры>
идентификатор процедуры> (<список фактических
параметров>).
Пусть, например, при составлении некоторой программы в
определенном месте необходимо .вычислить функцию S=sha и для вычисления этой
функции мы хотим воспользоваться суммой ряда
с , а3 , а5 , а7 , а9 /7Ч
О — аН Ч 1 Ь -—... (7)
43
Тогда, если только в заголовке этой программы имеется описание
процедуры polinom, и, кроме того, в запоминающем устройстве машины
хранится массив coeff [i] с элементами 0, 1, 0, d/Э!, О, 1/5!, О, 1/7!, О, J'/9!, то для
выполнения таких вычислений достаточно записать в соответствующем
месте программы оператор процедуры:
polinom (S) от переменной {alfa) ютепени (9, coeff [/]).
Когда этот оператор будет выполнен, переменной 5 будет присвоено
значение sha.
Возможность введения процедур — это одно из важнейших свойств
языка АЛГОЛ. Оно делает этот язык открытым, т. е. позволяет каждому
программисту расширять язык по своему усмотрению, добавляя описания
процедур и вводя операторы этих процедур в состав основного словаря
языка. Возможно также создание различных диалектов, т. е.
самостоятельных языков, составленных частично из символов АЛГОЛа и частично
из операторов процедур. Понятие процедуры в языке АЛГОЛ
эквивалентно понятию стандартной программы в машинно-ориентированном языке.
Следовательно, мы снова получили новое качество, которое проявляется
в данном случае в возможности расширения .проблемно-ориентированного
языка.
В языке АЛГОЛ имеется также ряд стандартных функций
<стандартная функция> : : =abs (Е) ] sign (Е) \ entier (E) \
\sqrt (Е) \sin (E)\cos\E)\arctg (E) In (Е)\ехр (E).
Здесь Е — это некоторое арифметическое выражение. Перечисленные
функции имеют следующий смысл. Если выражение Е имеет значение х, то
abs (Е) — модушь (абсолютное значение) х
( +1, если л;>0 ]
sign (E) I 0, если л: = 0 | для типа integer,
1 ■— 1, если л;<0 J
entier (E) —щелая часть значения х,
sqrt (Е) — квадратный корень из х,
sin (Е) — синус х,
cos (E) — косинус х,
arctg (E) —главное значение арктангенса'л:,
In (Е) —натуральный логарифм х,
ехр (Е) —экспоненциальная функция х (ех).
Теперь можно определить
<функция> : : =<оператор 1процедуры> | <стандартная
функция >.
В языке АЛГОЛ предусмотрено также средство введения в состав
программ любых пояснительных текстов. Для этого используется
специальный разделитель comment, а вся (конструкция имеет овид:
comment <любая последовательность символов, не
содержащая точки с запятой> ;
При переводе вся эта конструкция воспринимается машиной как один-
единственный символ «;». На этом формальное описание языка АЛГОЛ
можно считать законченным.
Приведем теперь несколько примеров програМхМ
begin real р, q, d; integer i; real array root 1, root 2 [0 : 1];
d:=ip!2) f 2-q; *: = 0;
root 1 [i]: = ifd>0 then — p 12 +sqrt (d) else — p/2;
root 2 [f]: = if d>0 then — p/2 — sqrt (d) else — p/2;
44
root 1 [i] : = if d<0 then sqrt(abs(d)) else 0;
root 2 W : = if d<0 then - sqrt(abs(d))else 0 end.
Эта программа иллюстрирует использование условных арифметических
выражений. Программа предусматривает вычисление корней квадратного
уравнения x2+px+q=0. Поскольку корни могут быть как
действительными, так и комплексными числами, каждый из них представляется в форме
массива root[\\y состоящего из двух компонент с индексами 0 и 1.
Индексом 0 помечена действительная часть корня, а индексом 1 — мнимая.
Если корень действительный, то мнимая часть полагается равной 0. В
остальном программа не требует пояснений.
begin real x, term, summ, q,ex; integer i;
term : = summ : = q := 1; for i : = 1, i+ 1 while q>w — 12 do;
begin term : = xXterm/i; summ : = summ + term;
щ : = abs (term/summ) end
ex : = summ end.
Эта программа предусматривает вычисление функции ех=ех по формуле
(4) с точностью до 10—12. В ней использована одна из форм оператора
цикла.
Приведем в заключение еще следующую программу:
begin integerN, i; real л;1, x2t 61, 62, all, a 12, a21, a22, ql, q2,
rl, r2, si, s2, XP\, XP2\ comment вычисления производятся по
одной из двух систем рекуррентных формул х ^ = (&1—
— а12Хр~~1))1ап, х^ =<(62 — а2Хх^)1а22 или xM=(b2 —
— а22Х^~~1))1а2и x!f>—\b\—a\\X^)lax2, если при вычислениях
по одной из систем разность двух последующих приближений оказывается
больше .разности двух .предыдущих приближений, то переходят к
вычислениям по другой системе формул, вычисления заканчиваются когда разность
двух последовательных приближений оказывается меньше 10—6;
real array pi, p2 [О : 2]; switch SW\ : = L2, LI; switch SW2 : =
= L1, L2;
xQ :=.l;
LI : N := 0; for i : = 0 step 1 until 2 do
begin xl :=(bl—a\2Xx2)lall; x2 := (62 — a2lX*l)/a22;
pil[i] := abs(xl); p2[t\ : = abs(x2); goto L3 end
L2 : N : = 1; for i : = 0 step 1 until 2 do
begin x\ :=>(62 —a22X*2)/a21; x2 := (61 — allX*l)/al2;
pl[i] : = abs(xl)\ p2[i\: = abs(x2)\ goto L3 end
L3:/: = 0; ql : = pl[/]; q2:=p2[([\ /: = 1; rl :=pl[t]; r2:=p2[fj;
i:=2;5l:=plM;52: = p2[t];
if(a6s(rl—sl)>a6s(?l —rl))V (abs(r2 — s2)^abs(q2 —
— г 2)) then
goto W1[W] else if(afts(rl —sl)>,0 —6) V (л^(г2—s2)>
>io—6) then
goto W2J7V] else do
XP1 :=jcl; XP2:=*2 end.
45
Программа предусматривает решение системы уравнений
Г anxi + ai2X2 = bi ^
1 a2\Xi + a22X2:=b2
методом итераций. После каждых трех итераций производится контроль-
сходимости. Бели обнаружено, что решение расходится , переходят к
вычислениям по другой системе формул. Необходимые пояснения даны в
заголовке программы с помощью конструкции comment. Программа
иллюстрирует также способы использования меток и переключателей. На этом
мы закончим рассмотрения языка АЛГОЛ.
Глава 6
И еще несколько языков
Материал двух предыдущих глав позволяет нам теперь сделать
некоторые обобщения. Начнем с того, что пробуем сформулировать ряд
важнейших на наш взгляд характерных особенностей
проблемно-ориентированного языка.
Имя предмета, над которым выполняется действие, претерпело даже
на страницах этой брошюры значительную эволюцию, в результате которой
при описании проблемно-ориентированных языков мы пришли в конце к
понятию идентификатора. Идентификатор — это любая последовательность
символов, в том числе и последовательность, имеющая определенный
смысл в натуральном языке.' С этой точки зрения понятие идентификатора
практически не отличается от привычного нам понятия слова (или точне<\
существительного). С другой стороны, идентификатор по-прежнему в
большинстве случаев представляет собой имя машинного слова (или группы
слов), хранящегося я данной ячейке ЗУ. Все это означает, что, находясь
на уровне проблемно-ориентированного языка, все заботы о выборе
конкретных номеров запоминающих ячеек мы полностью перекладываем, если
можно так выразиться, на плечи автомата. Человеку остается только
следить за тем, чтобы различные предметы назывались различными
идентификаторами. Аналогичная проблема имеет место и в случае натуральных
языков.
В проблемно-ориентированных языках сколь угодно длинные
последовательности отдельных операций могут объединяться в выражения или в
более сложных случаях — в операторы и блоки. Это означает, что забогу
об установлении правильной последовательности выполнения отдельных
операций мы также полностью перекладываем на плечи автомата. Человек
должен только следить за тем, чтобы составляемые им программы не
содержали противоречий и подчинялись правилам грамматики выбранноге
проблемно-ориентированного языка. Даже последнее условие не так уж
важно, поскольку подавляющее большинство допущенных грамматических
ошибок будет выявлено программой контроля, а сам текст будет
направлен автору для исправления.
Наличие в -языке средств описания массивов, а также выражений
назначения позволяет организовывать процессы комплексной обработки
сложных конструкций, состоящих из многих машинных слов. Такие
конструкции обычно называют списками. При обработке списков большая
часть организационной работы также выполняется автоматами.
Условные выражения позволяют автомату самостоятельно принимать
решения в тех случаях, когда вычислительный процесс может развиваться
по нескольким различным путям.
Введение такой грамматической категории, как описание, делает
проблемно-ориентированный язык «образным». В то же время это означает,
что забота о выборе формата, причем не только формата отдельных
машинных слов, но в отдельных случаях и формата программ и, списков,
перекладывается на плечи автомата.
46
Наконец, процедуры делают язык динамичным. Здесь открывается
возможность непрерывного обновления состава языка, а также
отпочкования от основного языка различных диалектов.
Бее перечисленные особенности присущи каждому
проблемно-ориентированному языку, но в различной степени. Удельный вес в использовании
тех или иных языковых средств зависит от ориентации языка. Например,
язык АЛГОЛ ориентирован на решение научных задач. Поэтому наиболее
развитыми в нем оказываются средства составления арифметических
выражений и процедур. С другой стороны, средства обработки длинных
последовательностей, данных развиты относительно слабо.
6 качестве примера языка другой ориентации можно привести язык
КОБОЛ (Common Business Oriented Language), ориентированный на ре-
решение экономических задач. Малый объем брошюры не позволяет нам
дать даже поверхностного описания этого языка, отметим здесь только
наиболее характерные его особенности.
Язык КОБОЛ, так же, как и язык АЛГОЛ, построен на латинском
алфавите, хотя в данном случае это не имеет никакого значения,
поскольку КОБОЛ не является утвержденным международным языком.
Идентификатором в языке КОБОЛ может быть не только любое сочетание букв
или цифр, но и сочетание отдельных фрагментов, написанных через тире.
Например, запись ТОВАР — НА СКЛАДЕ воспринимается машиной как
отдельный идентификатор. Это дает возможность описывать почти все
переменные словами, имеющими конкретный смысл в натуральном языке.
Значения в языке КОБОЛ могут иметь не только смысл чисел, но и смысл
понятий. Так, например, переменная ФАБРИКА в языке КОБОЛ можег
принимать значения ОБУВНАЯ, ШВЕЙНАЯ, МОСКОВСКАЯ и т. д.
Значения, имеющие смысл понятий, носят >в языке КОБОЛ специальное
название литералов.
Роль символов операций в языке КОБОЛ могут играть не только
знаки «+», «—» и т. д., но и сочетания букв: ПЛЮС, МИНУС и т. д.
Например, арифметическое выражение может иметь следующий вид:
УМНОЖИТЬ ЗАКАЗАННОЕ — КОЛИЧЕСТВО НА ЦЕНУ — ТОВАРА
ПОЛУЧАЯ ОБЩУЮ — ЦЕНУ. При составлении условных выражений
допускаются пропуски отдельных операндов. Условное выражение может
иметь, например, вид: А РАВНО В к С ИЛИ МЕНЬШЕ Д что
эквивалентно следующему выражению на языке АЛГОЛ: \{А = В ЛА = С) V А<
<D. В остальном выражения, операторы и блоки на языке КОБОЛ
составляются ino тем же правилам, что и ,в АЛГОЛе.
Наиболее развитую часть языка |КОБОЛ составляют описания. Здесь
имеется возможность описывать не только отдельные переменные, но и
форматы сложных записей. При этом вводится специальное понятие
уровня, с помощью которого указывается на то обстоятельство, что некоторая
данная запись является составной частью другой, более сложной записи.
Кроме описания данных, в языке КОБОЛ предусмотрены также средства
описания оборудования, которое должно участвовать /в решении задач.
(Все эти особенности приводят к тому, что текст на языке КОБОЛ
практически почти не отличается от текста на натуральном языке.
Принимаются только специальные меры, обеспечивающие однозначность каждого
описываемого понятия. Читатель, прошедший с нами весь путь, начиная
от простейших языков, хорошо понимает, что в этом нет ничего
необычного. Просто транслятор языка КОБОЛ должен содержать еще большее
количество различных стандартных программ по сравнению, скажем, с
транслятором, предназначенным для перевода на внутренний язык машины
текстов, записанных на АЛГОЛе.
Существуют языки, в еще большей степени приспособленные для
обработки списковых структур. В их числе в первую очередь можно назвать
языки ЛИСП и СПЛ. На сегодня во всем мире насчитывается около 800
различных символических языков и число их непрерывно растет.
Существуют языки более специализированные, обеспечивающие максимум удобств
при решении одного узкого класса задач, и языки универсальные
(например, АЛГОЛ), позволяющие, хотя и с меньшими удобствами, описывать
47
большинство вычислительных процессов, которые встречаются на практике.
Стремление к получению максимума удобств приводит к увеличению
количества различных языков, а это, в свою очередь, выдвигает
самостоятельную проблему, которую можно назвать проблемой свавилонской
башни». Действительно, если имеется, скажем N различных языков и М
различных типов машин, то Для того, чтобы каждая из машин могла
«разговаривать» на каждом языке, необходимо NxM трансляторов, а это
требует огромных затрат труда.
В настоящее время наметились два пути решения этой проблемы.
Первый из них состоит в попытках создания единого промежуточного
языка, который не был бы ориентирован ни на конкретный класс задач,
ни на конкретный тип машины, но был бы удобен для составления
трансляторов. Подобный язык, разработанный в нашей стране, получил
название АЛМО. При наличии универсального промежуточного языка
достаточно составить только N трансляторов для перевода с каждого из других
языков на промежуточный язык и М трансляторов для перевода с
промежуточного языка на внутренний язык машины каждого типа. Всего нужно
N+M трансляторов, что, конечно, значительно меньше, чем NxM.
Второй путь состоит в создании так называемых метаязыков,
основывающихся на группе диалектов. Каждый диалект не представляет собой
язык в полном смысле этого слова, а только часть языка с ярко
выраженной специализацией. Метаязык поэтому содержит в своем составе
общую часть, т. е. именно то, что отсутствует в каждом из диалектов, а
также специальные средства, позволяющие объединять несколько
диалектов в единый язык. Примером такого языка может служить
разработанный норвежскими учеными язык СИМУЛА-67. Время покажет, какое из
направлений конструирования языков окажется более плодотворным.
УВАЖАЕМЫЕ ТОВАРИЩИ!
ИЗДАТЕЛЬСТВО «ЗНАНИЕ» ПРЕДЛАГАЕТ ВАМ СЕРИЮ
ПОДПИСНЫХ НАУЧНО-ПОПУЛЯРНЫХ БРОШЮР «ФИЗИКА,
АСТРОНОМИЯ».
ИЗ БРОШЮР ДАННОЙ СЕРИИ ЧИТАТЕЛЬ УЗНАЕТ ОБО
ВСЕМ НОВОМ, О ПОСЛЕДНИХ ДОСТИЖЕНИЯХ (В ОБЛАСТИ
АСТРОНОМИИ, ФИЗИЧЕСКОЙ НАУКИ, ОСВОЕНИЯ
КОСМИЧЕСКОГО ПРОСТРАНСТВА.
БРОШЮРЫ НАПИСАНЫ НА ВЫСОКОМ НАУЧНОМ
УРОВНЕ, ИХ АВТОРЫ — ВИДНЫЕ УЧЕНЫЕ И СПЕЦИАЛИСТЫ.
В 1970 ГОДУ ПОДПИСЧИКИ СЕРИИ ПОЛУЧАТ 12
БРОШЮР, СРЕДИ НИХ:
Петров Г. П., академик. Космические
исследования в СССР.
Г и н з б у р г В. Л., академик. Пульсары.
Смородин-с кий Я. А., профессор, доктор
физ.-мат. наук. Успехи голографии.
Ленинские премии физикам и астрономам.
Сборник.
СЕРИЯ «ФИЗИКА, АСТРОНОМИЯ» В КАТАЛОГЕ
«СОЮЗПЕЧАТИ» РАСПОЛОЖЕНА В РАЗДЕЛЕ «НАУЧНО-
ПОПУЛЯРНЫЕ ЖУРНАЛЫ» ПОД РУБРИКОЙ
«БРОШЮРЫ ИЗДАТЕЛЬСТВА «ЗНАНИЕ». ИНДЕКС СЕРИИ 70072.
ПОДПИСНАЯ ЦЕНА НА ГОД 1 РУБ. 08 КОП.
Издательство «ЗНАНИЕ»