Основы программирования. Часть I [Андрей Александрович Тюгашев] (pdf) читать онлайн

А.А. Тюгашев
ОСНОВЫ ПРОГРАММИРОВАНИЯ
Часть I

Санкт-Петербург
2016

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
УНИВЕРСИТЕТ ИТМО

А.А. Тюгашев
ОСНОВЫ ПРОГРАММИРОВАНИЯ
Учебное пособие. Часть I.

Санкт-Петербург
2016

А.А. Тюгашев. Основы программирования. Часть I. – СПб: Университет
ИТМО, 2016. – 160 с.
Учебное пособие содержит теоретический материал и лабораторный практикум
для изучения дисциплины «Основы программирования». Представлен
панорамный взгляд на предметную область, с представлением не только
традиционной императивной, но и функциональной, и логической парадигм
программирования, исторической ретроспективы и связи с другими областями
информатики. Приводится сравнение программирования на языках высокого и
низкого уровней (ассемблер). Несмотря на обзорный характер, после прочтения
и прохождения входящего в книгу лабораторного практикума студент будет
способен писать программы средней сложности на языках С/С++. Книга
содержит и специальные главы, посвященные жизненному циклу программных
средств современной ИТ-индустрии, проблеме ошибок в программах и методах
верификации программного обеспечения, стилю программирования.
Учебное пособие адресовано студентам, обучающимся в ИТМО на кафедре
КОТ по направлению 09.03.02
«Информационные системы и технологии»;
преподавателям, ведущим теоретические и лабораторные занятия по курсу
«Основы программирования». В то же время издание может представлять
интерес для школьников, студентов средних специальных заведений и
широкого круга читателей, заинтересованных в освоении основ
программирования.
Рекомендовано к печати Ученым советом факультета КТиУ 08.12.2015 г.,
протокол №10.

Университет ИТМО – ведущий вуз России в области информационных и

фотонных технологий, один из немногих российских вузов, получивших в 2009
году статус национального исследовательского университета. С 2013 года
Университет ИТМО – участник программы повышения конкурентоспособности
российских университетов среди ведущих мировых научно-образовательных
центров, известной как проект «5 в 100». Цель Университета ИТМО –
становление
исследовательского
университета
мирового
уровня,
предпринимательского по типу, ориентированного на интернационализацию
всех направлений деятельности.
 Университет ИТМО, 2016
 А.А. Тюгашев, 2016

3

Оглавление
Введение ............................................................................................................... 5
Базовые понятия ............................................................................................... 8
История развития языков программирования ................................................ 16
Императивное программирование................................................................... 31
Описание фон-неймановской архитектуры ................................................. 31
Базовые понятия и конструкции императивных языков ............................ 34
Условный оператор и оператор выбора .................................................... 38
Повторное исполнение — рекурсия и итерация ...................................... 41
Структурное программирование................................................................ 45
Исключения .................................................................................................. 47
Процедурное программирование ............................................................... 48
Структуры данных в программировании..................................................... 51
Простые типы данных ................................................................................. 53
Составные типы данных ............................................................................. 58
Структурирование программ, принцип модульности ............................... 72
Язык программирования Си .......................................................................... 74
Основные понятия языка программирования Си..................................... 82
Принципы ввода-вывода в языке Cи ......................................................... 87
Структурирование программ на языке Си ................................................ 90
Структуры данных и управления языка программирования Си ............ 92
Обработка текстовых строк ........................................................................ 99
Использование параметров функции main()........................................... 101
Работа с файлами ....................................................................................... 102
Сумма нечетных на языке Си ................................................................... 106
Сортировка массивов ................................................................................ 108
Система управления базой данных о студентах..................................... 110
Особые возможности Си........................................................................... 112
Достоинства и недостатки языка Си ....................................................... 120
Язык ассемблера (автокод) .......................................................................... 122

4

Сумма нечетных на ассемблере ............................................................... 135
Макросы в ассемблере .............................................................................. 139
Введение в объектно-ориентированное программирование на примере С++............. 142
Достоинства и недостатки ООП .................................................................... 157
Список литературы ......................................................................................... 159

5

Введение
Данное пособие — не учебник по одному из популярных языков
программирования. Прочитав его, Вы не станете профессионалом в C# или
Java, использующим полученные навыки для поиска наиболее выгодных
предложений на рынке труда. Книга не предназначена также для обучения
методологии программирования на уровне, превышающем начальный. В
ней нет описаний методов написания эффективных алгоритмов,
построения пользовательских интерфейсов, доступа к базам данных и пр.,
хотя косвенно эти темы в ней освещаются. Цель – освещение базовых
принципов современного программирования, с примерами на языках Си и
С++ и небольшим введением в функциональное (Лисп), логическое
(Пролог) и визуальное программирование.
В настоящее время насчитывается около восьми
программирования, причем одни не похожи на другие.

тысяч

языков

Во введении можно долго рассуждать о об исторической ретроспективе
предмета, о его связи со смежными дисциплинами, значимости для жизни
современного общества и т. д. Все эти аспекты важны, но, как
представляется автору, в самом начале лучше погрузить читателя в суть
того, что ему предстоит изучать. Получить представление о предмете
может помочь набор примеров — семантически эквивалентных программ
(подробнее о том, что такое синтаксис и семантика, будет рассказано
далее), которые делают одно и то же, будучи исполненными на ЭВМ,
оснащенной соответствующими средствами. Выглядят программы на этих
языках по-разному. Следуя примеру Лоуренса Теслера [1, стр. 76],
используем для иллюстрации не банальный пример «Здравствуй, мир!», а
программу,
имеющую
(условно)
прикладное
значение —
подсчитывающую сумму нечетных чисел, входящих в последовательность
целых чисел. Итак, перейдем к примерам.
Программа на языке BASIC:
10 DIM T(100)
20 INPUT N
30 FOR I=1 TO N
40 INPUT T(I)
50 NEXT I
60 GOSUB 110
70 PRINT "СУММА НЕЧЕТНЫХ=" S
80 GOTO 200
110 REM подпрограмма
120 S=0
130 FOR I=1 TO N

6

140 IF NOT ODD(T(I)) THEN GOTO 160
150 S=S+T(I)
160 NEXT I
170 RETURN
200 END

Программа на языке COBOL:
DATA DIVISION.
WORKING-STORAGE SECTION.
01 NUMERIC-VARIABLES USAGE IS COMPUTATIONAL.
02 NUMBERS PICTURE 9999 OCCURS 100 TIMES INDEXED BY I.
02 N PICTURE 999.
02 SUM PICTURE 99999.
02 HALFC PICTURE 9999.
02 MODC PICTURE 9.
PROCEDURE DIVISION.
EXAMPLE
MOVE
MOVE
MOVE
MOVE

23 TO NUMBERS (1)
34 TO NUMBERS (2)
7 TO NUMBERS (3)
9 TO NUMBERS (4)

MOVE 11 TO NUMBERS (5)
MOVE 5 TO N
PERFORM SUMNECH.
SUMNECH
MOVE 0 TO SUM
PERFORM ANALIS-1 VARYING I FROM 1 BY 1 UNTIL I>N
ANALIS-1
DIVIDE 2 INTO NUMBERS (I) GIVING HALFC REMAINDER MODC
IF MODC IS EQUAL TO 1 ADD NUMBERS(I) TO SUM.

Программа на языке APL:
∇ СУМ←СУМНЕЧЕТ ЧИСЛА

∇ СУМ←+(2|ЧИСЛА)/ЧИСЛА

вызов: СУМНЕЧЕТ 2 3 3 4 7 9

7

Программа на языке Форт:
: СУМНЕЧЕТ
0 SWAP 0
DO
SWAP DUP 2 MOD
IF +
ELSE DROP
THEN
LOOP
Вызов: 2 3 3 4 7 9 СУМНЕЧЕТ

Программа на языке Лисп:
(DEFUN СУМНЕЧЕТ(ЧИСЛА)
(COND
((NULL ЧИСЛА) 0)
((ODD (CAR ЧИСЛА)) (+ (CAR ЧИСЛА)(СУМНЕЧЕТ(CDR ЧИСЛА))))
(T (СУМНЕЧЕТ (CDR ЧИСЛА))))))

Программа на языке ассемблера микропроцессора Motorola 68000:
СУМНЕЧЕТ MOVE.L
(A7)+,A2 Адрес возврата из стека в A2
MOVE.L
(A7)+,A1 Адрес первого числа => A1
MOVE.W
(A7)+,D1 Заслать n в D1
CLR.W D2
Обнулить D2
JMP
СЧЕТЧИК Перейти в конец цикла n=0?
ЦИКЛ
BTST
0,1(A1) Если число по адресу А1 четное…
BEQ.S СЛЕД
…перейти к метке СЛЕД
ADD.W (A1),D2 …иначе прибавить число к D2
СЛЕД
ADDQ.W
#2,A1 Взять в А1 адрес следующего числа
СЧЕТЧИК DBF
D1,ЦИКЛ Уменьшить D1,пока не -1 => на ЦИКЛ
MOVE.W
D2,-(A7) Занести сумму нечетных в стек
JMP
(A2)
Перейти по адресу возврата

Программа на языке Пролог:
sumnech([X|Xs],S):-odd(X),sumnech(Xs,S1),S is S1+X.
sumnech([X|Xs],S):-sumnech(Xs,S),\+ odd(X).
sumnech([],0).
odd(X):-integer(X),X rem 2 =:= 1.

8

Программа на визуальном
разработки HiAsm (рис. 1).

языке

программирования

российской

Рис. 1

Автор надеется: читатель не без интереса просмотрел приведенные
программы и обратил внимание на то, что они заметно различаются по
длине, стилю и внешнему виду вообще…
Целью настоящей книги является дать читателю представление о
«ландшафте» предметной области, относящейся к программированию
ЭВМ, описать некоторые базовые понятия, обрисовать историю данной
предметной области и ее перспективы. Есть даже приложение о
эзотерических языках.
ЗАМЕЧАНИЕ
Во введении и далее по тексту книги приняты следующие обозначения.
Ключевые понятия, на которые стоит обратить внимание, набраны курсивом.
Для примеров программ используется моноширинный шрифт. То, что выдает
машина в ходе исполнения программ, набрано жирным моноширинным
шрифтом.

Базовые понятия
Цзы Лу спросил: «Вэйский правитель
намеревается привлечь вас к управлению
государством. Что вы сделаете прежде всего»?

9

Учитель ответил: «Необходимо начать с
исправления имен».
Цзы Лу спросил: «Вы начинаете издалека.
Зачем нужно исправлять имена?»
Учитель сказал: «Как ты необразован, Ю!
Благородный муж проявляет осторожность по
отношению к тому, чего не знает. Если имена
неправильны, то слова не имеют под собой
оснований. Если слова не имеют под собой
оснований, то дела не могут осуществляться.
Если дела не могут осуществляться, то ритуал
и музыка не процветают. Если ритуал и
музыка не процветают, наказания не
применяются надлежащим образом. Если
наказания не применяются надлежащим
образом, народ не знает, как себя вести.
Поэтому благородный муж, давая имена,
должен произносить их правильно, а то, что
произносит, правильно осуществлять. В
словах благородного мужа не должно быть
ничего неправильного»
Легенда о Конфуции
Базовые понятия данного, казалось бы, технического узкоспециального
курса принуждают обратиться к проблемам весьма глубоким и
иллюстрируемым далекими от техники примерами, могущими показаться
забавными.
Но обращаясь к основам — чтобы понять, что такое язык
программирования, нужно выяснить сначала, что такое язык и что такое
программирование.
ЗАМЕЧАНИЕ
Парадоксальным образом базовое понятие курса — язык — определяется само
через себя, образуя «странную петлю» [2].

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

10

программирование, стохастическое программирование. Все они не имеют
непосредственного отношения к тому, о чем мы станем говорить . Но
вернемся к программированию, являющемуся предметом рассмотрения в
настоящей книге. В толковых словарях можно найти такие его
определения:
«раздел прикладной математики и вычислительной
техники, разрабатывающий методы составления
программ для ЭВМ»;
«вид деятельности, необходимый для организации
решения различных задач на ЭВМ…»;
«процесс создания компьютерных программ».
Мы
будем
использовать
следующее
рабочее
определение:
«Программирование — процесс создания или модификации программ для
ЭВМ». Слово «рабочее» означает, что определение не претендует на
абсолютную истину (ее знает лишь Бог), но вполне пригодно для целей
нашего рассмотрения.
Обратим внимание на то, что ключевым понятием здесь является ЭВМ
(электронная вычислительная машина), или, используя англицизм, —
компьютер.
ЗАМЕЧАНИЕ
При этом имеются в виду машины с дискретными состояниями [3], или
цифровые вычислительные машины — ЦВМ.

Разобравшись немного с тем, что такое программирование, попробуем
перейти к понятию язык. Что же это — язык? Вновь заметим, внеся в
рассмотрение долю здорового юмора, что в русском языке слово «язык»
имеет несколько значений. Это часть тела человека или животного
(недурного вкуса при правильном приготовлении). И элемент колокола. И
пленный враг, имеющий важные сведения, во время войны. Но нас
интересует иное значение. Что говорится по этому поводу в толковых
словарях? Язык — это:
«система знаков
информацию»;

(звуков,

сигналов),

передающих

«система фонетических, лексических, грамматических
средств, являющихся орудием выражения мыслей,
чувств,
волеизъявлений,
служащая
важнейшим
средством общения людей».

11

К сожалению, мы сталкиваемся здесь с отсылками к таким важнейшим и
глубоким понятиям, как знак (символ) и информация. Более того, можно
заметить, что приведенные определения небезупречны. В самом деле,
инопланетяне,
обладающие
разумом, —
пресловутые
зеленые
человечки, — разве мы вправе отказать им в наличии собственного языка,
служащего средством общения? Или можем ли мы отрицать наличие у
животных неких видов сигналов, служащих орудием выражения их
чувств?
В определениях есть отсылка к понятию информация. Что мы можем
считать информацией? Если мы знаем, какая будет завтра погода, дает ли
это нам возможность не промокнуть и не замерзнуть, правильно
одевшись? Видимо, дает, и это — информация, полезная и ценная.
Получить ее мы можем, прослушав прогноз по радио (устная речь) или
прочитав на экране коммуникатора (письменная речь).
Заметим, однако, что если у передачи не будет слушателя, обладающего
разумом
и
целенаправленным
поведением, —
назовем
его
интеллектуальным агентом, — она останется чередой звуков разной
частоты и вряд ли заслуживает полноценного права зваться информацией.
ЗАМЕЧАНИЕ
Вопрос о сути понятия «интеллект» остается открытым, пока неизвестно,
возможно ли построить интеллект искусственный, не уступающий
человеческому.

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

сигнальные флаги и огни на флоте;



бой часов на Спасской башне Кремля;



иероглифы у древних египтян и современных китайцев;



языки математических и химических формул;



язык электрических принципиальных схем;



пароль и отзыв у разведчиков;



язык нот для записи музыкальных произведений;



язык жестов у глухих;



и

даже

азбука Брайля для слепых и слабовидящих, использующих тактильные
ощущения, и т. д.

12

Согласно преданию, индейцы в древности передавали друг другу вести,
зажигая костры на вершинах гор. Вероятно, читатели слышали о языке
цветов (имеются в виду не краски, а цветы, из которых формируют
букеты, — здесь мы опять сталкиваемся с проблемой значения слов).
Языки можно разделить на естественные (возникшие и развивающиеся
без некоего целенаправленного замысла или проекта) и искусственные.
Примером искусственного (созданного человеком, причем используемого
в технических устройствах) языка может служить азбука Морзе.
ЗАМЕЧАНИЕ
Безусловно, к искусственным относятся и языки программирования.

Понятие языка неразрывно связано с понятием символа. Значительная
часть языков,, в том числе языков программирования, используют в
качестве своих базовых составляющих цепочки символов (идущих
последовательно один за другим знаков). Что же это — знак? Рассмотрим в
качестве примера знак Р.
Что это? Русская буква «эр»? Латинская буква «пэ»? Греческая буква
«ро»? Или обозначение давления (если, например, символ встретился в
записи физического закона)? Или обозначение фосфора при записи
химической реакции? Автомобилисты могут вспомнить о столь
дефицитной в больших городах стоянке. Мы начинаем чувствовать нечто
важное, глубокое, характеризующее символ и язык вообще. А именно,
формальный (синтаксический), содержательный (семантический) и
прагматический аспекты этого феномена.
Внешний вид символов и способы их сочетания при записи послания
образуют первый — формальный — уровень языка. Но есть еще и
значение символа. Говорят, что знак обозначает денотат.
А есть еще и смысл записанного на языке послания для получателя!
Лучше понять это позволит следующий пример. Предположим, вы —
зеленый человечек, брат по разуму из системы Эпсилон Эридана.
Высадившись на Земле, вы находите листок бумаги — записку на русском
языке: «Даша любит Петю». Что можно извлечь из этой записки?
Безусловно, вы понимаете, что планета населена разумными существами,
обладающими письменностью. Далее можете отметить наличие в записке
линейной последовательности символов разного размера, разделенных
пробелами. Некоторые символы повторяются, другие — нет. Видимо, это
все. Проведен анализ послания с синтаксической, или формальной, точки
зрения. Далее. Предположим, что записку находит кто-то из читающих порусски. Какие он сделает выводы? Существует некая особа женского пола
по имени Даша, и она неравнодушна к мужчине или мальчику по имени

13

Петя. Это уже понимание значения символов, или семантический анализ.
После этого он без особых эмоций отложит записку в сторону или
выбросит.
И лишь один-единственный Ваня, найдя эту записку в определенном
месте, плача, рвет на себе волосы. А вот это уже — прагматический
аспект, или смысл послания для получателя.
Вернемся к значению символов. Предположим, мы имеем дело с записью
2 ∙ 2=
Какой символ (или символы) уместно поставить в конце? 4? А может быть,
10? Будет ли запись 2 ∙ 2=10 правильной? Зависит ли это от используемой
системы счисления?
А может ли быть «правильной» запись 2 ∙ 2=1022 или это исключено?
Представим себя на месте приказчика на небольшом свечном заводике
(или менеджера, выражаясь по-современному). Предположим, мы хотим
записать в блокнот наблюдение, что двое рабочих за две смены
изготавливают 1022 свечи. Становится ли в этом случае приведенная
запись осмысленной (допустимой)?
Вернемся, однако, к языкам программирования. Ясно, что на этих языках
записывают не произвольную информацию, а целенаправленные
предписания, направленные на решение некоторой задачи. Подобного рода
предписания называют еще алгоритмами (слово происходит от прозвища
древнеарабского математика Аль-Хорезми, жившего в городе Хорезме и
описавшего в том числе правила производства арифметических действий
над числами в индийской — привычной нам — записи). Программа
представляет собой алгоритм решения задачи, записанный на понятном
ЭВМ языке. Поэтому языки программирования некоторое время назад
иногда называли алгоритмическими языками. Собственно, название
одного из широко известных языков — ALGOL — получено как
сокращение от ALGOrithmic Language (по-русски — алгоритмический
язык, Алгол).
ЗАМЕЧАНИЕ
Метод решения задачи может быть записан разными способами.

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

14

английски»! Мне захотелось понять, что же главнее, язык или мысли?» [2].
Карлу V Габсбургу, императору Священной Римской империи,
приписывают высказывание: «Если бы я хотел говорить с мужчинами, я
говорил бы по-французски, если бы я хотел говорить с женщинами, я
использовал бы итальянский, если бы я хотел говорить с моей лошадью, я
бы говорил на немецком, если бы я хотел говорить с Богом, я бы говорил
по-испански».
Физики, математики, химики, ботаники и даже астрологи для описания
своих задач и методов их решения используют специфичные языки,
удобные в каждом конкретном случае. Жан-Луи Лорьер отмечает [4], что
привычный всем со школы современный язык математики, кажущийся
столь логичным и естественным, рождался в муках на протяжении
тысячелетий. В современном виде он существует совсем недавно, причем в
некоторых разделах науки (скажем, в математической логике, где можно
для обозначения одного и того же действия встретить запись и →, и ⊃, и
⇒) до сих пор не существует единой общепринятой системы обозначений!
Вычисления в Древнем Египте или Вавилоне были гораздо более
громоздкими и трудоемкими просто в силу используемых форм записи.
Для примера Лорьер приводит два математических выражения — в записи
Франсуа Виета (1540–1603):
 H in B 


− F in D  aequebitur A
 −F + D 



и принятой сейчас:
ay − by
= x.
b+ y

Контрольные вопросы и упражнения
1. Что такое программирование?
2. Что такое язык?
3. В чем заключается разница между естественным и искусственным
языками?
4. Какие языки, используются в искусстве, технике, других областях?
Приведите свой пример.
5. Что такое знак (символ)?
6. В чем заключается синтаксический аспект языка?
7. В чем заключается семантический аспект языка?

15

8. В чем заключается прагматический аспект языка?
9. Каковы функции различных языков?

16

История развития языков
программирования
При формулировании понятия «программирование» мы упоминали о том,
что здесь подразумевается подготовка программ для ЭВМ, или
компьютера. Попробуем рассказать подробнее, что под этим понимается.
Компьютер — некая машина, способная выполнять различные действия в
соответствии с заложенной в нее программой. Именно программа
определяет возможность полезного применения ЭВМ, без нее она остается
практически ненужной грудой «железа» — проводов, микросхем,
пластмассы. Благодаря возможности менять исполняемые программы,
закладываемые в память машины без изменения ее электронной схемы,
мы получаем удивительное и не характерное для ранее созданных
человеком машин свойство — универсальность, то есть способность одной
и той же машины выполнять разные функции.
Программа представляет собой некую систематизированную совокупность
инструкций (команд), которые входят в перечень доступных (исполнимых)
для конкретной ЭВМ. Набор доступных команд (система команд)
современного компьютера обычно довольно примитивен и состоит из
элементарных действий, подобных сложению или пересылке данных,
производимых над содержимым ячеек памяти ЭВМ. Потрясающе, но
именно выполнение большого (действительно большого!) количества этих
элементарных действий в нужном порядке позволяет современным ЭВМ
вычислять траектории полета космических аппаратов к Юпитеру, весьма
правдоподобно имитировать сражение на Курской дуге, обыгрывать
чемпиона мира по шахматам, анализировать тайны мира элементарных
частиц и выполнять иные столь же сложные задачи.
Программист — человек, занятый программированием, иными словами —
маг и чародей, который способен заставить компьютер выполнять все
перечисленное (и еще то, что пока не заставили выполнить компьютер, но
замысел чего уже появился в голове читателя). Но, конечно, любой маг
должен знать нужные заклинания. В нашем случае заклинания — это
языки программирования, на которых составляются программы.
К какому моменту можно отнести появление первого программируемого
компьютера (подчеркнем это слово, поскольку машины для автоматизации
счета известны с глубокой древности — вспомним абак, но управление
процессом вычислений производилось вручную)? Первым программистом
в истории человечества часто называют леди Лавлейс, составившую для
так называемой аналитической машины Чарльза Бэббиджа несколько
предписаний, в том числе самое сложное, с вложенными циклами (причем

17

Ада Лавлейс, фактически, и ввела такое фундаментальное понятие
программирования, как цикл!), по расчету чисел Бернулли.
Справедливости ради отметим, что аналитическая машина существовала
лишь в проекте. Основывалась она не на электричестве, а на механических
узлах и должна была оснащаться паровым двигателем (да, именно это
было вершиной техники в 1830-е годы, когда создавался этот выдающийся
проект). Однако если бы машина была построена, она стала бы первым
программируемым компьютером. Для ввода программы в машину
предполагалось использовать карты с отверстиями (перфокарты), подобно
тому, как программируются узоры, создаваемые на ткацком станке.
Фактически, программа Ады Лавлейс (кстати, в честь этой хрупкой
женщины назван язык программирования, разработанный по заказу
министерства обороны США) представляет собой набор карт, а не некую
запись в виде текста.
Заметим, что к числу гениальных прозрений леди Лавлейс следует отнести
и то, что она предвидела возможность машины оперировать не только
числами, но и произвольными объектами, выраженными, например,
алгебраически в символьной форме (то есть то, что ныне называется
символическими вычислениями, или компьютерной алгеброй), и даже
звуками, представляемыми нотами.
Тем не менее машина Бэббиджа не была построена. В какой же стране и
когда появился действительно функционировавший компьютер? Был он
электронным или механическим? И какой язык программирования
применялся? Из одной книги по информатике в другую кочует
укоренившийся миф, гласящий, что страна — США, машина —
электронная, а год — 1946-й. Это не соответствует действительности. Еще
в 1938 году немецкий инженер Конрад Цузе построил Z1 — первую из
трех модификаций своей вычислительной машины. Элементной базой
служили списанные с телефонной станции реле — фактически, машина
была электромеханической. Программа должна была задаваться с
помощью ленты с отверстиями — перфоленты.
Однако Цузе, как и леди Лавлейс за век до него, увлекла идея создания
универсальной машины, способной решать задачи не только
вычислительные, но и из других областей. Он назвал этот свой проект
логической машиной. Жаль, что она, как и аналитическая машина
Бэббиджа, так и не была построена (правда, по чертежам и записям
Бэббиджа базовые части аналитической машины были реализованы
энтузиастами позже, уже в XX веке).
В 1945 году, по окончании Великой Отечественной войны, Цузе переехал
из Берлина в Баварские Альпы, где и занялся определением языка для
будущей логической машины. Язык, названный им Plankalkül (по-русски

18

произносится «планкалкюль», приблизительно означает «планирующее
исчисление»), фактически, представляет собой языком программирования
высокого уровня с такими современными чертами:


наличие повторно вызываемых функций;



встроенные типы данных;



массивы;



аналог условного оператора;



аналог оператора assert;



исключения;



цикл ПОКА.

Аналога оператора безусловного перехода GOTO в языке не было — в
полном соответствии с разработанными спустя десятилетия строгими
принципами структурного программирования!
Весьма любопытной особенностью языка Plankalkül являлась двумерная
запись программы, что роднит его с некоторыми современными так
называемыми эзотерическими языками (BeFunge и пр.) и, вероятно, может
рассматриваться как признак его более высокого уровня (!), но весьма
усложняет построение транслятора. Однако, по крайней мере, для
подмножества (причем линеаризованного) оригинального языка —
Plankalkül 2000, энтузиастами компилятор (на машинный код современной
ЭВМ)
был
создан,
как
и
эмулятор
машины
(см.
http://www.zib.de/zuse/Inhalt/Programme/Plankalkuel/PlankalkuelReport/Plankalkuel-Report.htm).

Далее приводится пример программы на этом языке (сортировка):
P6 sort (V0[:6.8.0]) => R0[:6.8.0]
W1[0](4)[
V0[i0:8.0] => Z0[i0:8.0]
1 => Z4[:32.0]
W1[1](i0)
[
(V0[i0:8.0] < Z0[i1:8.0]) & (Z4[:32.0]=1) →
[
i0-i1 => Z1[:32.0]
W1[2](Z1[:32.0])
[
i0 — i2 — 1 => Z3[:32.0]
i0 — i2 => Z2[:32.0]

19

Z0[Z3[:32.0]:8.0] => Z0[Z2[:32.0]:8.0]
]
V0[i0:8.0] => Z0[i1:8.0]
0 => Z4[:32.0]
]
]
]
END

Цузе и сам предполагал создать автоматический преобразователь (аналог
современных трансляторов с языков высокого уровня в машинный код)
программы на Plankalkül в исполнимую на его предполагаемой машине
перфоленту, но это не было им воплощено в реальность. Однако Цузе
составил 49 страниц программ на Plankalkül для оценки шахматных
позиций.
На заре вычислительной техники программы вводились в память ЭВМ с
пульта, перемычками или тумблерами. Программа писалась в машинных
кодах — а память ЭВМ и тогда, и сейчас может хранить лишь двоичные
представления. Пример программы в машинном коде (это настоящий код
архитектуры PDP-11/СМ ЭВМ, предполагающий прибавление 64 к
содержимому первого регистра процессора):
0110010111000001
0000000000000100
0000000000000000

К сожалению, машинный язык весьма неудобен для человека,
которомуприходилось запоминать, какие команды кодируются какими
последовательностями нулей и единиц, в ячейках с какими номерами
хранятся промежуточные результаты вычислений и пр. Неудивительно,
что программирование было занятием непростым, доступным немногим, в
программы по невнимательности вносилось большое количестве ошибок.
ЗАМЕЧАНИЕ
Машинные коды можно
поколения.

считать

языками

программирования

первого

Итак, имелась проблема: пропасть между сложностью решаемых задач и
примитивностью машинных команд [5]. Забегая вперед, заметим, что с
развитием языков программирования проблема эта окончательно не
исчезла, она лишь перешла на другой уровень.
Потом возникла идея: использовать при записи вместо неудобных и
трудных для запоминания кодов мнемонические обозначения команд,
после чего специальные люди-кодировщики по таблицам соответствия
переводили программу в машинный код. Большой скачок в

20

программировании произошел, когда машине доверили выполнение такого
перевода с помощью специальной системной программы (ассемблера).
Кроме того, стало возможно обозначать ячейки не конкретными адресами
в памяти (фактически, номерами ячеек), а символическими именами и
потом ссылаться на них в программе. Саму технологию и используемый
язык программирования назвали автокодом, или тоже ассемблером.
Термин ассемблер произошел от английского слова assembler, так
называли сборщик частей в одно целое, в данном случае — сборщик
программы. Процесс сборки называется ассемблированием. Слово
«автокод» можно расшифровать как «автоматическое кодирование в
машинных кодах».
ЗАМЕЧАНИЕ
Уже этот подход стали называть автоматическим программированием [5]. Та
же ситуация повторилась при появлении языков третьего поколения.

Соответственно, язык ассемблера отнесем ко второму поколению языков
программирования.
Представленная ранее в машинных кодах программа на языке ассемблера
выглядит значительно понятнее (по-английски ADD означает «сложить»,
HALT — «стоп»):
ADD
HALT

#100, R1

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

Был ли минус при переходе от машинного кода к ассемблеру? Да. Дело в
том, что программа на автокоде непонятна самой машине и для ее
использования
необходимо
наличие
специальной
программыпереводчика — ассемблера. Данная программа способна построить
программу в машинном коде по представленному на ее вход тексту с
мнемоническими обозначениями команд.
В то же время при решении задачи программист все равно принужден
мыслить в терминах машины. Иными словами, ассемблер, как и машинный
код, остается языком так называемого низкого уровня. Неудивительно, что
уровень машины человек — с высоты своего положения царя зверей —

21

считает низким! Впрочем, если серьезно, дело еще и в уровне абстракции.
Следует отметить еще одно важное обстоятельство. Программы на
ассемблере не были переносимыми — при смене используемой ЭВМ
(например, покупке у другого производителя, более мощной и надежной, с
иным набором машинных команд) программы, разработанные с
использованием команд предыдущей машины, становились практически
бесполезными и все надо было переписывать заново!
Возникает резонный вопрос: а почему машины и их языки столь
примитивны? Ответ прост: проще, дешевле и надежнее сделать их именно
такими. Впрочем, неоднократно делались попытки создать машину с
аппаратной поддержкой более развитого и сложного языка. Так, созданный
в СССР компьютер «Эльбрус» в качестве ассемблера использовал язык
высокого уровня Эль-76.
ЗАМЕЧАНИЕ
Архитектура суперЭВМ «Эльбрус» поддерживала указание на уровне машины
типа хранимого в ячейке памяти значения.

Микропроцессор Intel 432 — еще один пример, когда усложнялся
машинный язык, в частности, команды поддерживали обработку сложных
структур данных. Существовали и Лисп-машины с аппаратной
реализацией данного функционального языка, ориентированного на
обработку списков. Тем не менее широкого распространения данный
подход не получил, и «центр тяжести» в согласовании сложных задач и
примитивных машинных команд остается в области программной
реализации.
Очередная революция в языках программирования произошла, когда
появились языки программирования высокого уровня, или третьего
поколения. В них характерные для машины понятия, такие как ячейки
памяти или простейшие операции суммирования чисел в ячейках памяти,
заменялись абстрактными переменными и довольно сложными
выражениями, похожими на используемые в математике формулы
(неудивительно, что первый язык программирования высокого уровня так
и назвали — Фортран, от слов «формульный транслятор»).
ЗАМЕЧАНИЕ
Весьма любопытно, что Фортран жив и успешно используется до сих пор,
например, в научных расчетах — конечно, развиваясь и вбирая новшества в
программировании (были выпущены стандарты Фортран 77 и Фортран 90).
Объясняется это, в частности, большим объемом наработанных эффективных
библиотек программ, которые нет смысла переписывать на другие языки, но не
только этим — например, в язык изначально встроена поддержка комплексных
чисел, чего нет во многих современных языках.

22

При создании языков высокого уровня делалась попытка выразить в языке
суть алгоритма решения задачи, абстрагированного от мелких деталей
реализации на той или иной ЭВМ, что нашло свое отражение в названии
еще одного знаменитого языка программирования — Алгол (от англ.
algorithmic language — алгоритмический язык).
Более того, по крайней мере в некоторой степени (поскольку все же
нюансы реализации на разных платформах различались) программы на
языках высокого уровня стали переносимыми. Для того чтобы программу
можно было использовать на некоторой ЭВМ (с произвольной системой
команд), достаточно было наличия для нее транслятора (программыпереводчика) с соответствующего языка высокого уровня в машинный код.
При наличии трансляторов для разных архитектур теоретически
становится возможным написать и отладить программу на одной ЭВМ, а
затем перенести ее на другую и там использовать.
Естественно, к минусам данной технологии можно отнести необходимость
предварительной разработки транслятора. При этом он может относиться к
одной из двух разновидностей: компиляторы и интерпретаторы. Разница
между ними заключается в следующем. Компилятор принимает на вход
всю программу на языке высокого уровня целиком и в результате процесса
трансляции строит так называемый объектный модуль, содержащий
машинный код, понятный процессору целевой ЭВМ. Интерпретатор
переводит программу на языке высокого уровня построчно, при этом для
каждой строки исходной программы создает некоторое внутреннее
представление на специальном промежуточном языке, которое
направляется специальной машине времени исполнения, или виртуальной
машине (Virtual Machine). Эта машина немедленно исполняет полученное
предписание.
И у компиляторов, и у интерпретаторов есть достоинства и недостатки.
К достоинствам компилятора относится в первую очередь то, что
полученный машинный код может непосредственно исполняться на
данной ЭВМ, при этом наличия компилятора в момент выполнения не
требуется. Выполнение же происходит на максимально возможной
скорости. Однако в случае необходимости внесения в программу
изменения, даже минимального, потребуется произвести перекомпиляцию
исходного текста полностью, даже если он насчитывает десятки тысяч
строк!
Интерпретатор переводит программу построчно, поэтому он удобен для
отладки программы, когда постоянно происходят уточнения и изменения и
нужно быстро увидеть, как поведет себя откорректированная программа. К
недостаткам интерпретатора относится то, что, поскольку программа
исполняется интерпретатором, а не непосредственно процессором, во-

23

первых, скорость выполнения программы существенно ниже, чем при
компиляции (обычно в 10–20 раз), а во-вторых, требуется наличие машины
времени выполнения в памяти.
ЗАМЕЧАНИЕ
В настоящее время существуют так называемые «компиляторы-на-лету» (Just
In Time — JIT), например, в Java-программировании. Они позволяют сократить
потери времени из-за использования режима интерпретации с порядков до
двух-трех раз.

В то же время скомпилированная программа в машинном коде —
аналогично программе на ассемблере — может исполняться лишь на
архитектурно совместимой ЭВМ. А для интерпретируемого языка
(например, Java) достаточно установки на данный компьютер машины
времени исполнения (в случае Java — JVM (Java Virtual Machine)), после
чего на ней теоретически могут быть исполнены любые программы на
данном интерпретируемом языке (лозунг Java — Write Once Run
Everywhere — «написав раз, запускаешь везде!»). Среди языков
программирования высокого уровня Бейсик, Лисп, Java, Питон, Форт
обычно реализуются как интерпретаторы, а Фортран, Си, С++, Паскаль,
Модула-2 — как компиляторы, хотя это правило не является
обязательным.
Программирование на языках высокого уровня гораздо удобнее для
человека, чем в терминах машины. В результате появления Фортрана и
Кобола программирование стало доступным широкому кругу
специалистов. Неудивительно, что языки программирования высокого
уровня стали бурно развиваться. В настоящее время известно более 8000
языков программирования.
Несмотря на наличие такого большого количества языков, лишь некоторые
из них массово применялись, породили многочисленных потомков или
оказали существенное влияние на систему понятий и дальнейшее развитие
предметной области. Наиболее известными и/или оказавшими влияние на
теорию и практику развития программирования языками являются
(приведены язык-родоначальник и созданные затем на его основе версии и
языки-потомки):


Фортран — Фортран IV — Фортран 77 — Фортран 90;



Кобол;



Алгол — Алгол 60 — Алгол 68;



Симула — Симула-67;



Smalltalk;



PL/I — PL/M;

24




BASIC — GW-Basic — Turbo Basic — Quick Basic — Visual Basic;
Паскаль — Модула — Модула-2 — Оберон — Active Oberon —
Компонентный Паскаль — Zonnon;



Ада — Ада 83 — Ада 95 — Ада 2012;



(BCPL — B ) — С — Objective C — C++ — Java — C# — C11;



APL — K — J;



Лисп — Scheme — Common Lisp — Clojure — AutoLisp;



ML — Standard ML — Ocaml — F# — LazyML — Miranda — Haskell —
Curry;



Planner — QA4 — Popler — Conniver — QLisp;



Пролог — Parlog — Mercury — Oz — Fril — P#;



Форт;



Клу.

Большинство известных языков программирования используют в качестве
основы для наименования ключевых слов английский язык (впрочем,
недавно появились сообщения о создании языка программирования,
основанного на арабской письменности с ее записью справа налево). Для
русскоязычного читателя немаловажным может оказаться вопрос:
существуют ли языки программирования, ориентированные на русскую
лексику? Весьма серьезным предубеждением против нашей родины
является почему-то имеющееся у некоторых программистов мнение, что
их не существует.
Нет, естественно, они существуют. Отвлечемся при этом от простого
перевода известных языков, изначально основанных на английской
лексике, на русский (а подобный перевод производился не раз, например,
для таких языков, как Алгол, Ада или Пролог). Поговорим об изначально
разработанных на основе русских слов языках. Во-первых, существовали
(и существуют, естественно, не столь широко известные, но используемые
в специальных и военных приложениях — и, если подумать, становится
ясно, что иначе просто нельзя) русские автокоды для отечественных ЭВМ.
А их было создано немало, в том числе выдающихся, например БЭСМ-6,
имеющих оригинальную архитектуру и превосходящих иностранные
аналоги своего времени.
Если говорить о языках высокого уровня, то еще в начале 1960-х годов
появился ЛЯПАС (логический язык для представления алгоритмов
синтеза), трансляторы с которого были созданы практически для всех
активно используемых в СССР ЭВМ («Урал», БЭСМ, серий ЕС ЭВМ и СМ
ЭВМ). Уникальная разработка (фактически, первый в мире персональный

25

компьютер) «МИР», произведший сенсацию на международной выставке в
Лондоне и закупленный IBM в 1967 году, программировался на языках
Алмир-65 и Аналитик. Они были реализованы аппаратно, но фактически
представляли собойязыки высокого (или даже сверхвысокого) уровня за
счет поддержки абстрактных типов данных, вычислений в произвольных
алгебрах, аналитических преобразований. Весьма интересна диалоговая
система программирования ДССП, ориентированная на стек и словарную
организацию, подобно языку Форт, но с рядом отличий, ведущих свою
родословную от первой в мире троичной ЭВМ «Сетунь».
Замечательным оригинальным языком, который обладает весьма
интересными возможностями, а по своему стилю был даже выделен Н. Н.
Непейводой [6] наряду с Прологом в группу «языков сентенциального
программирования», является созданный В. Турчиным в СССР в 1966 году
РЕФАЛ (Рекурсивных Функций Алгоритмический язык).
Специально для поддержки преподавания информатики в средних школах
в свое время был создан весьма интересный и мощный язык РАПИРА.
Очень интересна и система КуМир, включающая не просто язык, но целую
учебную среду разработки программ. Ведутся работы над основанными на
русских ключевых словах языках программирования и в настоящее время.
Назовем всего несколько: встроенный язык системы управления
предприятием 1С, языки Глагол, Пифагор, Фактор.
Помимо языков программирования, предназначенных для последующего
перевода и исполнения вычислительной машиной (процессором), в
литературе выделяют в обособленную группу так называемые скриптовые
языки, или языки сценариев. К этой группе относят, например, такие
популярные языки, как Perl, PHP, JavaScript, BASH, и другие. Под
сценарием подразумевается некий набор действий, исполняемых
операционной системой, браузером или иным подобным программным
компонентом. При этом скрипт (программа на языке сценариев)
интерпретируется соответствующим компонентом. Типичный пример –
язык командной строки, с помощью которого можно задать операции над
файлами в указанной папке.
У пытливого читателя, возможно, уже возник вопрос: что пришло — и
пришло ли — на смену языкам программирования высокого уровня, или
языкам третьего поколения? Многие создаваемые в настоящее время языки
их создатели относят к четвертому поколению (а наиболее нескромные —
даже к пятому, но это не является общепринятой точкой зрения).
К направлениям исследований и разработок в области
программирования четвертого поколения могут быть отнесены:


проблемно-ориентированные языки программирования;

языков

26



декларативный подход к программированию;



языки визуального (графического) программирования;



использование в программировании подмножеств естественного языка.

Проблемно-ориентированные (или предметно-ориентированные) языки
программирования
(англ.
DSL —
Domain
Specific
Language)
подразумевают, что в языке наряду с универсальными управляющими
конструкциями и типами данных присутствуют встроенные средства для
описания понятий, характерных для конкретной предметной области, для
решения задач которой предназначается данный язык. Предметноориентированные языки программирования используются в различных
сферах — атомной энергетике, космических исследованиях, радиотехнике
и пр. Далее приводится пример программы на проблемноориентированном языке, транслятор с которого был разработан автором в
ходе автоматизации программирования бортовых алгоритмов управления
реального времени для космических аппаратов:
t11:=(a003=0)=>f005+(a003=1)=>f200
t12:=(a004=0)=>f006+(a004=1)=>f201
t9:=t11CHt12
t13:=f003CHf004
t111:=(a003=0)=>f015+(a003=1)=>f210
t112:=(a004=0)=>f016+(a004=1)=>f211
t91:=t111CHt112
t10:=t13CHt91
t8:=(a002=0)=>t9+(a002=1)=>t10
t6:=f101->t8
t18:=f009CHf010
t19:=((f011->f012)->f014)
t17:=t18->t19
t15:=f103->t17
t16:=f007CHf008
t14:=f102->t16
t7:=t14CHt15
t5:=t6CHt7
t4:=f002CHt5
t3:=f111CHf100
t2:=t3->t4
endtxt
f200=f220
f005=f015
f006=f016
end

27

Весьма популярны встроенные проблемно-ориентированные языки в
мощных информационных системах. Яркий пример — системы
автоматизации управления предприятием, в которых поддерживаются
такие понятия, как документ, бухгалтерский счет, проводка и пр.
Встроенный язык программирования системы SAP/R3 называется ABAP,
язык белорусской системы «Галактика» — VIP, есть свой язык в известном
в нашей стране пакете 1C. Система автоматизации проектирования
AutoCAD позволяет писать дополнительные приложения на специально
адаптированной версии языка программирования Лисп — AutoLiSP. В
системе управления базами данных Oracle для написания программ
применяется язык PL/SQL. Все это позволяет значительно быстрее и
удобнее создавать прикладные программы и повысить качество
разработки.
Декларативный подход к программированию означает, что с программиста
снимается обязанность подробного инструктирования ЭВМ, как именно
решать задачу (пошагового описания алгоритма), вместо чего ему
необходимо лишь выполнить постановку задачи некоторым формальным
образом, задав существующие ограничения, то есть описать, что требуется
получить в качестве результата. Происходит переход от «Как?» к «Что?».
Декларативный подход является попыткой воплощения идеальной
технологии программирования, в качестве которой может быть
рассмотрена такая технология, когда по некоторому довольно
неформальному
описанию
задачи
автоматически
генерируется
синтаксически и семантически корректная программа решения. Поиск
решения при этом возлагается на встроенную в систему программирования
«машину вывода». Ярким примером декларативного подхода являются и
языки семейства SQL – языки запросов к базам данных, в которых
описывается, что нам надо извлечь из базы, а система управления базой
данных сама осуществляет все необходимые для этого действия.
ЗАМЕЧАНИЕ
В некотором смысле можно провести аналогию между исполнителем (в
качестве которого выступает процессор, виртуальная машина, иногда — робот)
в императивных языках и «машиной вывода», являющейся более
«интеллектуальной» версией исполнителя.

Еще одно достоинство декларативных языков — пригодность для
формальных рассуждений, которые, в частности, могли бы поднять методы
обеспечения надежности и безошибочности в программировании на новый
уровень (известно, что тестирование может помочь обнаружить ошибки в
программах, но не может гарантировать их отсутствия). К сожалению,
существующие методы формального анализа программ чрезвычайно
трудоемки. Много усилий было направлено на создание более простых и

28

строгих языков, а также совершенствование методов анализа, но
результаты не обнадеживают.
Декларативная программа обладает также следующим преимуществом.
Она может быть подвергнута логическому анализу в своих собственных
понятиях, для чего не требуется привлечение дополнительных
формализмов, таких как предикаты на состояниях. Более того, возникает
возможность создания инструментальных средств, позволяющих
автоматизировать процессы анализа, преобразования и синтеза программ.
Появление таких средств может в корне изменить программирование. При
программировании на традиционном (императивном) языке у
программиста нет иного выбора, кроме как вникать в низкоуровневые
подробности выполнения программ. В декларативных языках логика и
управление отделены друг от друга. Декларативную программу проще
написать и, что немаловажно, проще понять, чем эквивалентную
императивную программу. Помимо этого возникает возможность
переложить ответственность за реализацию порядка выполнения операций
на компьютер. Более того, становится возможным использовать
нетривиальные алгоритмы планирования вычислений, такие как
недетерминированные, «ленивые» и параллельные подходы.
К сожалению, универсального решения, позволяющего решать подобным
образом произвольные задачи, не существует, иначе отпала бы
необходимость в программировании и программистах. Тем не менее в
конкретных предметных областях при наличии заранее подготовленных
программных модулей, из которых может быть «собрана» требуемая
программа решения, декларативный подход возможен. Довольно
успешными реализациями декларативного подхода можно считать язык
логического программирования Пролог, основанный на выводе в логике
предикатов, а также, как уже говорилось, SQL — язык запросов к
реляционным СУБД.
Идея визуального программирования, также называемого графическим,
сводится к тому, что написание программы как текста заменяется в том
или ином масштабе ее изображением в виде графической диаграммы
(рисованием).
В
современных
системах
программирования
просматривается тенденция к развитию средств, позволяющих
программисту при создании программы оперировать не текстовыми,
синтаксическими
конструкциями,
а
графическими
образами.
Традиционный термин «писать программу» при этом трансформируется в
«построить, проектировать программу». Описываться при этом могут
самые разные аспекты программного комплекса. Такое богатство средств
визуального представления обусловило возникновение некоторых
трудностей при определении понятия визуального, или графического
программирования. Существуют следующие варианты: «использование

29

графических средств разработки и визуальной метафоры при создании
программного
обеспечения»
(Microsoft),
«программирование,
предусматривающее создание приложений с помощью наглядных
средств», «графический язык программирования — любой язык
программирования, в котором программы задаются путем графического
манипулирования элементами взамен текстового манипулирования ими»
(Википедия) и пр. Визуальное представление обладает рядом
значительных преимуществ перед текстовым представлением, в частности,
высокой наглядностью и удобством для человека, что позволяет достичь
ряда целей, в том числе сокращения трудоемкости разработки, повышения
качества и надежности создаваемых программ. В настоящем учебнике
визуальным языкам программирования посвящена отдельная глава.
Попытки использования естественного языка в программировании имеют
довольно долгую историю. С самого появления ЭВМ весьма
привлекательной является идея общения с компьютером на обычном
человеческом языке — русском, английском, японском и т. д.
Действительно, как было бы здорово, придя с занятий, сказать домашнему
компьютеру: «Рассчитай мне курсовую по физике!» — и получить готовый
результат. Однако все усилия в этом направлении, несмотря на постоянно
появляющиеся заявления вроде «еще чуть-чуть», «через пять лет» и т. д.,
не принесли решающего успеха. Это не кажется удивительным, если
вспомнить, что, как показано еще в классической работе А. Тьюринга [3],
создание компьютера, способного общаться на произвольные темы на не
специально усеченной версии естественного языка, эквивалентно
созданию искусственного интеллекта в полном смысле слова — машины,
не уступающей разуму человека. Да и вопрос о самой принципиальной
возможности создания искусственного интеллекта остается открытым.
К сожалению, естественный язык неполон, неточен, избыточен, и
неоднозначен [4]. Тем не менее предпринят ряд успешных попыток
применения некоторых ограниченных подмножеств естественного языка в
определенных предметных областях (запросы к базам данных,
искусственные миры, к примеру, мир кубиков [2]). Как правило, в таких
случаях предложения должны строиться по заранее предписанным
правилам, а передаваемый смысл — соответствовать некоторой точно
определенной системе понятий.
Контрольные вопросы и упражнения
1. В чем заключаются особенности программируемых ЭВМ по сравнению
с другими машинами?
2. Что называется системой команд компьютера?
3. Опишите возможности машины Беббиджа и программы Ады Лавлейс.

30

Когда была написана первая программа?
4. В какой стране и когда был построен первый компьютер?
5. Что представляет собой язык Plankalkül, разработанный К. Цузе?
6. Сколько языков программирования насчитывается сегодня? Многие ли
активно используются? Выскажите свое мнение о причинах.
7. Перечислите преимущества и недостатки — программирования в
машинных кодах.
8. Перечислите преимущества и недостатки — программирования на
ассемблере.
9. Перечислите преимущества и недостатки программирования на языках
высокого уровня.
10.Существуют
ли
основанные
на
русской
лексике
программирования? Приведите примеры таких языков.

языки

11.В чем разница между интерпретатором и компилятором? Перечислите
их преимущества и недостатки.
12.Каковы основные направления исследований в области языков
программирования четвертого поколения?
13.Что такое предметно-ориентированные языки программирования?
Перечислите их достоинства и недостатки.
14.Сколько поколений языков программирования известно по состоянию
на 2013 год?
15.В чем состоит сущность декларативного подхода к программированию?
16.В чем состоят основная идея и преимущество визуального языка?
17.В чем заключаются особенности естественных языков? Что такое
неполнота, неоднозначность, избыточность?
18.Перспективен ли естественный язык для постановки задач ЭВМ?
Почему? Обоснуйте свое мнение.

31

Императивное программирование
После рассмотрения предыстории перейдем к более подробному описанию
существующих и используемых сейчас языков программирования.
Заметим, что они довольно сильно различаются между собой в
зависимости от используемых базовых теоретических положений — так
называемой модели вычислений.
Большинство языков традиционно принадлежат к так называемой
императивной модели. В силу этого их иногда называют традиционными.
Не совсем точным термином, однако используемым в сходном значении,
является процедурное программирование.
Рассмотрим императивную модель более подробно. Она тесно связана с
внутренним устройством большинства современных ЭВМ — так
называемой фон-неймановской архитектурой.
ЗАМЕЧАНИЕ
В основе названия лежит исторический казус. Математик Джон фон Нейман не
является изобретателем данной архитектуры — документ, в котором она
описана, был издан под его научной редакцией. Впоследствии это стало даже
предметом судебного разбирательства в США, в результате чего были
защищены авторские права Эккерта и Моучли — конструкторов ЭВМ
UNIVAC.

Описание фон-неймановской архитектуры
Устройство обычного современного компьютера представлено на рис. 2.

ЦП

ОЗУ

Рис. 2

32

Его ключевыми элементами являются:


память — оперативное запоминающее устройство (ОЗУ);



центральный процессор (ЦП);



арифметико-логическое устройство (АЛУ),
базовые операции преобразования данных;



устройство управления (УУ);



счетчик команд (СК);



устройства ввода-вывода.

способное

выполнять

Память компьютера представляет собой линейный набор однородных
пронумерованных ячеек. АЛУ и УУ — важнейшие узлы центрального
процессора (ЦП), представляющего собой «мозг» ЭВМ. Еще один
принципиально важный элемент ЦП — так называемый счетчик команд —
специальный регистр, находящийся в процессоре, который содержит адрес
(номер) ячейки памяти, хранящей следующую команду, подлежащую
исполнению.
Команды и данные кодируются двоичными кодами и хранятся в одной и
той же памяти. Универсальное двоичное представление означает, что по
содержимому ячейки априори нельзя сказать, хранится ли в ней число,
символ или команда. Команда может содержать несколько битов,
отведенных под код действия — К (например, 110 — сложение), адрес
первого операнда (оп1), например, слагаемого — А1, и адрес второго
операнда (оп2) — А2. Данная особенность архитектуры позволяет
создавать самомодифицирующиеся программы, изменяющие собственные
команды — преобразующие их подобно данным (примером являются так
называемые полиморфные вирусы или некоторые задачи «олимпиадного
программирования»). Но у этой архитектуры есть и недостаток с точки
зрения
безопасности —
программа
при
выполнении
может
непреднамеренно или целенаправленно (вредоносные программы)
разрушить саму себя или другие программы, находящиеся в памяти! От
подобного недостатка избавлена, например, архитектура отечественных
суперЭВМ «Эльбрус» [7], в которой каждая ячейка снабжается
специальным тегом, содержащим тип хранимой информации (кстати, в
этом компьютере аппаратура поддерживала язык программирования
высокого уровня Эль-76).
Все вычисления машины с фон-неймановской архитектурой выполняются
централизованно — в АЛУ под управлением УУ. Рассмотрим цикл работы,
связанный с выполнением очередной команды.
Команда извлекается из памяти, передается в процессор, где декодируется
(дешифрируется) устройством управления. Из памяти с использованием

33

адресов, указанных в команде (например, А1 и А2), извлекаются операнды.
УУ побуждает АЛУ выполнить операцию в соответствии с
дешифрированным кодом операции К. Результаты операции пересылаются
в память — по адресу, указанному в команде. После этого значение
счетчика команд автоматически увеличивается — на следующем цикле
извлечению из памяти подлежит следующая команда. Процесс
повторяется.
В случае необходимости программа может продолжиться с другой
команды, используются особые команды переходов, изменяющие значение
счетчика команд принудительно. Команда перехода может быть
безусловной или условной. Условная команда перехода модифицирует
значение счетчика команд лишь в случае наличия того или иного
выставляемого АЛУ флага, говорящего о том, что результат предыдущей
операции, например, равен нулю или отрицателен.
В архитектуре фон Неймана есть узкое место — канал обмена процессора
с памятью, о чем говорил в своей лекции при вручении премии Тьюринга
ее лауреат, создатель языка программирования Фортран Джон Бэкус. Чем
больше число объектов, с которыми оперирует программа, — данных и
разнообразных операций над ними, — тем больше времени требуется,
чтобы найти решение: приходится на каждом шаге передавать
информацию от процессора в память и обратно. Так что какими бы
скоростными не были процессор и память, общее быстродействие будет
зависеть от возможностей канала обмена.
Анализируя работу фон-неймановской машины, подчеркнем еще раз
следующие важнейшие моменты.






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

ЗАМЕЧАНИЕ
Описанная организация вычислительного процесса — вовсе не единственно
возможная. Так, в процессорах ARM, применяемых в смартфонах и
планшетных ЭВМ, у команд — не только команд условного перехода —
имеется набор флагов, дающих возможность проверить на каждом шаге

34

состояние вычислительного процесса и обусловить этим выполнение или
невыполнение данной команды. Аналог подобного подхода на более высоком
уровне программирования — таблицы решений [8]. Спроектированный и
построенный в 1946 году в Великобритании Аланом Тьюрингом компьютер
ACE включал в команду адрес следующей подлежащей исполнению команды.

Все же можно с полным основанием назвать описанную модель
вычислений традиционной — именно так работает подавляющее
большинство современных ЭВМ и именно на нее ориентированы
большинство из существующих языков программирования.
Контрольные вопросы и упражнения
1. Что входит в понятие модели вычислений?
2. Почему архитектура большинства современных компьютеров носит имя
фон Неймана? Заслуженно ли это?
3. Опишите основные элементы «фон-неймановской» архитектуры ЭВМ.
В чем ее недостатки?
4. Процедурная,
императивная
и
программирования — это одно и то же?
5. Из каких этапов
компьютера?

состоит

цикл

традиционная
работы

парадигмы

«фон-неймановского»

6. Существуют ли альтернативные архитектуры ЭВМ? В чем их
преимущества и недостатки?
7. Представьте себя инженером-конструктором компьютера. Как бы вы
построили ЭВМ?

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



…


В некоторых языках программирования операторы нумеруются.

35

Пример на языке Бейсик:
10 INPUT "Введите A и B";A,B
20 D=A+B
30 PRINT "Сумма введенных чисел равна",D

Данная программа может быть исполнена интерпретатором Бейсика,
позволяя подсчитать сумму двух введенных чисел. Номер строки
позволяет ссылаться (продолжить исполнение с нее) на строку с
определенным номером.
Пример на языке Бейсик:
GOTO 20

Сейчас, однако, нумерация строк — скорее анахронизм. Вместо них
используется аппарат меток, являющихся необязательным, но
допустимым префиксом строки программы, что позволяет нарушить
естественный ход выполнения программы, выполнив переход к метке.
Пример на языке Си:
goto label;

Пример на языке Java:
break label;

Пример на ассемблере PDP-11:
BR MET

ЗАМЕЧАНИЕ
В некоторых из современных языков высокого уровня переходы считаются
злом, метки в них могут принципиально отсутствовать.

Приведенная программа выглядит вполне лаконично и исчерпывающе.
Однако в большинстве современных языков, включая языки ассемблера,
помимо собственно перечня выполняемых действий программа в
обязательном порядке содержит еще несколько секций, или разделов
(имеющих свое предназначение блоков текста).
Часто требуется указать имя программы, после чего используются
ключевые слова наподобие begin и end.
Пример на языке Паскаль:
PROGRAM MYPROGRAM;
BEGIN
(* программа *)
END MYPROGRAM.

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

36

классами в зависимости от языка. Каждая подпрограмма, в свою очередь,
имеет свое собственное имя, начало и конец.
Современные программы, как правило, являются частью некоторого
программного комплекса и взаимодействуют с другими его элементами.
Даже простая программа обычно использует стандартные так называемые
библиотечные модули, позволяющие решать типовые задачи, например
вычислять синус, без необходимости каждый раз изобретать велосипед. В
связи с этим в программе чаще всего есть блок, в котором описано, каким
образом программа взаимодействует с другими (какие библиотечные
модули импортируются и откуда, какой интерфейс имеет программа). В
интерфейсной части обычно описывается, какие данные поступают на вход
и какие получаются в результате выполнения программы или
подпрограммы.
Описание обрабатываемых данных является важнейшей частью
программы во многих языках программирования. Известно высказывание
известного швейцарского ученого Никлауса Вирта: «Программы =
Алгоритмы + Структуры данных» [9]. Поэтому помимо собственно
действий, отражаемых алгоритмической частью (она еще может
называться процедурной), программа содержит объявление данных,
которые подлежат обработке. В простейшем случае это перечисление всех
встречающихся в дальнейшем переменных с указанием их типов.
Перечисленные непроцедурные, или декларативные, части программы
чаще всего находятся в ее начале, а также в начале каждой подпрограммы.
Иногда декларативная часть выносится (не полностью) в исходные файлы
специального типа.
Но вернемся к процедурной части. Именно она содержится внутри
функций и процедур и называется телом функции, чем подчеркивается
отличие от заголовка подпрограммы, включающего имя и список входных
и выходных данных.
Несмотря на то что изначально в некоторых языках допускалось
использование строго одного оператора в строке и значение имела даже
позиция (колонка), в которой он начинался, а в языках ассемблера до сих
пор принят принцип «одна строка — одна команда», большинство
современных языков программирования допускают запись в одной строке
нескольких операторов:
; ;

…


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

37

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

Рис. 3

При выполнении каждого встреченного в строке императивной программы
предписания некоторым образом меняется состояние ЭВМ (содержимое
ячеек памяти). При этом можно сказать, что мы имеем фокус управления,
находящийся при выполнении программы в том или ином известном месте
и определяющий, какое действие будет выполняться следующим.
Какие виды операторов встречаются в программах? Фундаментальное
значение в императивной парадигме программирования имеет так
называемый оператор присваивания, меняющий значение некоторой
переменной в памяти ЭВМ. Приведем примеры операторов присваивания
из разных языков программирования.
Пример на языке Бейсик:
LET X=X+1

Пример на языке Фортран:
A=B+C

Пример на языке Си:
b=sin(x)+cos(x)/(-2)*y;

Пример на языке РАПИРА:
К*СУММАНАЛОГА → M;

Оператор присваивания имеет две части. В одной из них содержится имя

38

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

Условный оператор и оператор выбора
Если бы все программы были линейными (их операторы выполнялись
строго в однажды заданном порядке, без альтернатив), их возможности
были бы сильно ограниченными. Несомненно, реальные задачи могут
содержать множество альтернатив, и хочется, чтобы программа могла
обрабатывать разные случаи и ситуации (вспоминая русские сказки:
«направо пойдешь — коня потеряешь», «налево пойдешь…» и пр.). В
языках программирования с этой целью используются условный переход,
условный оператор и оператор выбора.
Условный оператор — конструкция, позволяющая поставить выполнение
тех или иных действий в зависимость от выполнения некоторых условий.
Различают несколько форм условного оператора. Обычный вариант,
содержащий записываемоме по правилам языка программирования
условие, имеет две разновидности полную и сокращенную. В полной форме
указывают два действия — первое, подлежащее выполнению, если условие
выполняется, и второе — выполняемое, если условие ложно.
Пример на языке Паскаль:
IF D>=0 THEN VYCHKORNI()
ELSE WRITELN('Действительных корней у данного уравнения нет');

В некоторых языках (например, Nemerle, какой-то из форм, сокращенной
или полной, может не быть).
Графически условный оператор принято изображать в виде ромба, в
котором записывается условие, а из боковых углов исходят линии,
соответствующие ветвям выполнения ДА и НЕТ (рис. 6). На блок-схеме
видно условие P (предикат) и два действия, S1 и S2, подлежащие
выполнению при истинности и ложности условия.

39

Да

Рис. 4

В сокращенной форме условного оператора приводится лишь действие,
которое необходимо выполнить в ситуации, когда условие истинно. В
противном случае просто ничего не выполняется, лишь происходит
передача управления следующему по порядку записи программы
оператору.
Пример на языке РАПИРА:
ЕСЛИ ОСТДЕНЕГ>0 ТО ВЫДАТЬ_ДЕНЬГИ();

В качестве условия P могут выступать переменная специального
логического типа или некоторое выражение, могущее быть истинным или
ложным, например, в случае сравнения двух величин.
Условие в операторе может быть и сложным, в нем могут присутствовать
логические связки И, ИЛИ, НЕ.
В некоторых языках программирования применяется условный переход. В
этом случае действием является передача управления оператору с
заданным номером или помеченному указанной в операторе условного
перехода меткой. В следующем примере в качестве действия,
выполняемого при истинности условия, использован оператор перехода
goto.
Пример на языке Си:
if (summaБ: А-Б→A !
А=Б: 0 → Б !

ВСЕ

А0, факториал
нуля принимается равным единице.
ЗАМЕЧАНИЕ
Чтобы рекурсия не продолжалась вечно, необходима проверка так называемого
условия останова рекурсии, или граничного условия.

Пример рекурсивного вычисления факториала на языке Си:
/* Рекурсивное вычисление факториала */
long int fac(int N)
{
if (N==0) return 1;
if (N>18) {printf("Слишком большое число!\n\a");return -1;};
return N*fac(N-1);
}

Через рекурсию определяются знаменитые числа Фибоначчи, менее
известные числа Люка и многие другие замечательные математические

42

объекты, что позволяет писать для их вычисления лаконичные и
прозрачные по смыслу программы.
ЗАМЕЧАНИЕ
Часто рекурсивные программы весьма лаконичны, непосредственно передают
смысл задачи, изящны по сравнению с решающими ту же задачу
итеративными.

Любопытно, что формула для прямого вычисления чисел Фибоначчи и
Люка тесно связана с понятием золотого сечения, по мнению многих,
являющегося воплощением красоты и гармонии. Не связано ли это
магическим образом с красотой рекурсивных программ?
Следует отметить, что вызов подпрограммы — это некоторое количество
дополнительных действий, причем на каждый рекурсивный вызов для
запоминания точки возврата требуется некоторое количество оперативной
памяти. При чрезмерно большой глубине рекурсии может наступить
ошибка типа «переполнение стека вызовов». В отличие от этого поддержка
итерации в ЭВМ архитектуры фон Неймана более проста и естественна. В
некоторых языках программирования (Кобол, Бейсик, Фортран ранних
версий) рекурсивные вызовы запрещены.
В других языках, напротив, отсутствует поддержка итерации, и
реализовать повторное выполнение одних и тех же действий можно только
с использованием рекурсии. Большинство современных языков
программирования допускает применение как итерации, так и рекурсии.
Конструкции, обеспечивающие итерацию, называются циклическими
конструкциями. Примером может служить цикл ПОКА, обеспечивающий
выполнение S, пока выполняется логическое условие P. Цикл ПОКА
представлен на рис. 5.

Рис. 5

43

Действие S1 называют телом цикла. ПОКА еще называют циклом с
предусловием. Обратим внимание на следующие важные моменты:




Цикл с предпроверкой может быть не выполнен ни разу — в случае,
если условие P изначально ложно.
При выполнении цикла программа может войти в бесконечное
исполнение в случае, если условие P изначально истинно, а выполнение
тела цикла не влияет на истинность условия. Эта ситуация называется
зацикливанием.

Пример на языке Си:
/* Умножение на два и печать значения, пока не дойдем до тысячи */
while (a18) {printf("Слишком большое число!\n\a");return -1;};
i=F=1;
while (iСЧ ВСЕ
ВСЕ;

Структурное программирование
В данной главе активно использовались рисунки для иллюстрирования
различных операторов
языков программирования. Графические
обозначения соответствуют языку блок-схем алгоритмов и программ.
Обратите внимание на то, что действия представлены прямоугольными
блоками. А также на то, что у каждой иллюстрирующей использование
оператора схемы был только один вход и один выход. Представим теперь,
что мы эту схему обвели прямоугольной рамкой. У рамки будет одна
входящая линия сверху и одна выходящая — снизу. Если теперь заменить
прямоугольный блок построенным блоком в рамке, вы поймете идею так
называемого строгого структурного программирования.
Структурное программирование запрещает использование произвольных
переходов к метке, за счет чего программа приобретает более
упорядоченный характер, что, с точки зрения апологетов данного подхода,
позволяет создавать более качественные и надежные программы.
Программы, изобилующие командами безусловного перехода GOTO, в
логике которых из-за этого практически невозможно разобраться,
получили в среде сторонников структурного программирования обидное
прозвище спагетти.
Теоретической основой структурного программирования принято считать
принципы, изложенные в классической работе Бома и Джакопини. Эта
работа на итальянском языке была опубликована в 1965 году, а в
английском переводе — в 1966 году. В соответствии с так называемой
структурной теоремой, сформулированной и доказанной в работе, всякая
программа может быть построена с использованием только трех основных
типов блоков — линейного, условного и циклического.
ЗАМЕЧАНИЕ
Существует также строгое теоретическое доказательство того, что цикла
ПОКА и последовательной композиции достаточно для написания программы
с произвольной по сложности логикой.

46

У структурного программирования есть и критики, в основном среди
практикующих программистов. Они (например, Кнут [10]) указывают на
то, что с использованием операторов безусловного перехода goto во
многих случаях удается писать более эффективные программы. Типичная,
хотя и не единственная ситуация — необходимость обеспечить выход из
глубины вложенных один в другой циклов.
ЗАМЕЧАНИЕ
Существует строгое теоретическое доказательство того, что последовательной
композиции и условного перехода достаточно для написания программы с
произвольной по сложности логикой.

Разумно, видимо, не доходя до фанатизма, для получения более
упорядоченных и понятных программ применять как идеи структурного
программирования, так и в оправданных случаях — условные и
безусловные переходы.
Мы рассмотрели основные виды операторов современных императивных
языков программирования высокого уровня:


оператор присваивания;



условный оператор и оператор выбора;



операторы циклов.

Особняком стоит вызов подпрограммы (процедуры, функции). В
некоторых языках для этого используется специальный оператор, в
других — просто записывается имя функции или процедуры со списком
параметров.
Какие еще операторы встречаются в программах? Пустой оператор,
который ничего не делает, зато может быть помечен и на него может быть
передано управление. Во многих языках имеются операторы ввода-вывода,
позволяющие обмениваться информацией с оператором. В примерах
использован оператор языка Бейсик PRINT, выводящий данные на экран
(некоторые языки, например Си, не содержат встроенных операторов
ввода-вывода, для обмена информацией применяются библиотечные
функции, в частности printf()).
Упоминали мы также операторы безусловного и условного перехода к
метке. Наряду с операторами цикла, условным оператором и оператором
выбора они являются управляющими, то есть используемыми для
изменения порядка выполнения действий в программе.
Использование лишь конструкций, допустимых с точки зрения
структурного программирования, вынуждает применять вспомогательные
операторы. Так, имеется оператор прерывания текущей итерации цикла и

47

переход к следующей, не доходя до конца тела цикла в тексте (continue
в Си). Есть оператор, прерывающий выполнение текущего структурного
блока и вызывающий продолжение исполнения программы с места начала
следующего блока в тексте программы (break в Си).

Исключения
Одной из популярных современных идей, относящихся к механизмам
управления выполнением императивных программ, являются так
называемые исключения. При выполнении программы возможны
различные нештатные ситуации (в вычислениях — попытка деления на
ноль, переполнение и пр., при работе с файлами — запись на защищенный
диск, при поиске данных — отсутствующая запись и т. д.). Подобные
случаи традиционно отслеживались с помощью условного оператора и
оператора выбора. В наихудшем варианте, если программист не учел
возможности возникновения непредвиденной ситуации, происходит
«вылет» из программы в операционную систему, часто с
невразумительным сообщением об ошибке, да еще и на английском языке.
Механизм исключений предназначен специально для выявления
нештатных вариантов исполнения. Блок с исключениями выглядит при
этом следующим образом:
Попытайся
Начало-блока-с-исключениями
{

Если (условие 1 ) создай исключение 1
Если (условие 2 ) создай исключение 2
…
Если (условие n ) создай исключение n
}
В-случае-Ошибки 1 выполни
В-случае-Ошибки 2 выполни
…
В-случае-Ошибки n выполни
Конец-блока-с-исключениями

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

48

исключений (которые обычно возникают по причинам, не связанным
прямо с выполняемым кодом), для обработки синхронных исключений она
малопригодна. Обработка без возврата заключается в том, что после
выполнения обработки исключения управление передается в некоторое
заранее заданное место программы и с него продолжается исполнение. То
есть при возникновении исключения команда, во время работы которой
оно возникло, заменяется безусловным переходом к заданному оператору.
Пример на языке C#:
try
{
result = SafeDivision(a, b);
Console.WriteLine("{0} деленный на {1} = {2}", a, b, result);
}
catch (DivideByZeroException e)
{
Console.WriteLine("Попытка деления на ноль!");
}

ЗАМЕЧАНИЕ
По многим свойствам исключения в языках программирования походят на
прерывания,
относящиеся
к
механизмам
реализации
управления
вычислительным процессом, в частности, в операционных системах ЭВМ.

Процедурное программирование
Базовыми действиями в императивном программировании остаются
присваивание и вызов подпрограммы. В свое время использование
подпрограмм стало одной из основополагающих идей и даже получило
самостоятельное название — программирование с использованием
процедур, или процедурное программирование.
Процедурное
программирование
дает
возможность
повторного
использования кода и в некотором смысле реализует принцип матрешки.
Процедура — блок, который раскрывается в другом месте, а из данной
программы лишь вызывается (указанием ее имени).
ЗАМЕЧАНИЕ
Процедурное программирование — лишь одна из вариаций древнейшего
принципа решения сложных задач «разделяй и властвуй!». Принцип
заключается в разбиении сложной задачи на менее сложные подзадачи, каждая
из которых либо также разбивается на еще более простые, либо решается
доступными средствами.

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

49

исходными текстами, классы, пакеты, процедуры, модули, функции,
пространства имен и т. д. (это зависит от языка, в некоторых из них
возможны несколько вариантов разбиения). Пока будем использовать для
всех них единый термин — модуль (в обобщенном смысле).
В программировании используются несколько принципов разделения
программы на модули. Один из них требует, чтобы размер каждой
отдельной процедуры (функции, класса) был обозримым, не превышая,
скажем, двух стандартных страниц. Другие обоснованные соображения
деления программы на модули основываются на функциональной
законченности, или разбиении программы на части в соответствии с
выполняемыми самостоятельными функциями. При этом руководствуются
принципами сильной связи внутри модуля и слабой связи между
модулями (которая тем не менее должна быть достаточной для решения
программой поставленных перед нею задач). Слабая взаимозависимость
модулей позволяет более удобно заменять версию данного модуля в случае
необходимости (нахождение и исправление ошибки или доработка
программы) и распределеять задачи программирования в коллективах — а
современные программы часто создаются десятками, а то и сотнями
разработчиков.
ЗАМЕЧАНИЕ
Поскольку вызов процедуры требует некоторых затрат времени процессора и
памяти, иногда целесообразна замена некоторых процедур малого размера так
называемыми встроенными (inline) функциями. Фактически, процедура
превращается в дублирующиеся в нескольких местах блоки команд, что
позволяет повысить скорость исполнения программы.

Иногда в языках программирования используются так называемые
замыкания — фактически, вспомогательные функции, определяемые и
используемые внутри родительской функции и использующие ее
локальные переменные, а не только своипеременные-параметры. В
программе замыкание выглядит как функция, находящаяся целиком в теле
другой функции. При этом вложенная функция содержит ссылки на
переменные внешней. Каждый раз при выполнении родительской функции
происходит создание нового экземпляра внутренней функции с новыми
ссылками на переменные внешней функции. При этом ссылки на
переменные внешней функции действительны до тех пор, пока работает
вложенная функция, даже если внешняя функция закончила работу.
Пример на языке PHP:
function outer($x) //Определение внешней функции
{
$y=2; //Локальная переменная внешней функции

50

функции

$inner=function ($a) use ($x, $y) //Определение внутренней
{
$b=4; //Локальная переменная внутренней функции
/* А дальше складываются переменные внутренней и
* внешней функций, как будто все они локальные
* переменные внутренней функции
*/
$res=$x+$y+$a+$b;
echo $res; //Результат 10 в нашем примере.
};
$inner(3); //Вызов внутренней функции

}
outer(1);

Механизм замыканий тесно связан с лямбда-функциями (безымянными
функциями,
использующими
текущий
контекст
программы).
Первоначально они нашли широкое применение в функциональном
программировании (языки Лисп — см. соответствующий раздел настоящей
книги, Хаскелл, Scheme), но затем получили распространение и в языках
императивной парадигмы (Ruby, PHP, Питон и др.).
Пример на языке Питон:
(lambda x: x*2)(3) →

6

Контрольные вопросы и упражнения
3. Как выглядит императивная программа?
4. В чем назначение номеров строк в программе? В чем назначение меток?
5. Что такое процедурная и декларативная секции программы?
6. Что такое линейная программа? Приведите примеры.
7. В чем состоят функции и какова структура оператора присваивания?
8. В чем заключается назначение и какова структура условного оператора?
9. В чем заключается назначение, каковы варианты и структура оператора
выбора?
10.Каким образом можно организовать повторение одних и тех же
действий в программе?
11.Что такое рекурсия? В чем назначение граничного условия в
рекурсивных программах?
12.Что такое итерация? В чем преимущества и недостатки итерации по
сравнению с рекурсией?

51

13.Какие
виды
операторов
программирования?

циклов

существуют

в

языках

14.В чем заключаются особенности цикла ПОКА? Приведите пример
применения.
15.В чем заключаются особенности цикла ДО? Приведите пример
применения.
16.В чем заключаются особенности цикла ДЛЯ? Приведите пример
применения.
17.В чем заключаются особенности цикла ДЛЯ … ИЗ? Приведите пример
применения.
18.В чем заключаются особенности цикла ПОВТОР N РАЗ. Приведите
пример применения.
19.В чем заключается теорема Бома —Джакопини?
20.В чем заключается основная идея структурного программирования?
Согласны ли вы с ней?
21.Какие существуют дополнительные виды операторов управления в
программах? Приведите примеры их использования.
22.Зачем нужно повторное использование кода?
23.В чем заключается принцип встраиваемых функций (inline). Каковы
условия их применения? Приведите пример.
24.Что такое исключения в программах? Зачем нужен механизм
исключений? Приведите пример использования механизма исключений.
25.Какие виды исключений в программах вы знаете? Какие
альтернативные способы обработки нештатных ситуаций можете
предложить?
26.Что такое замыкание? Всегда ли создается экземпляр замыкания при
выполнении родительской функции? Существует ли связь между
замыканиями и лямбда-функциями?

Структуры данных в программировании
Программы
данных.

=

Алгоритмы

+

Структуры

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

52

как и в каком порядке происходит обработка, структуры данных должны
четко описывать, что именно обрабатывается, — и на это описание
затрачивается значительная часть усилий программиста. И если, как
говорит Никлаус Вирт, программы — это алгоритмы плюс структуры
данных, в языках программирования должны быть средства описания
алгоритмов и средства описания данных.При этом то, насколько удобно и
эффективно можно описать данные, зависит от встроенных в язык
программирования возможностей.
Некоторые языки программирования требуют, чтобы до их использования
все переменные, аргументы и возвращаемые значения функций и процедур
были объявлены с указанием типа (Алгол, Ада, Паскаль, С/C++). Другие
(Лисп, РАПИРА, PHP) этого не требуют, переменная в них приобретает
тип в зависимости от первого присвоенного ей значения. При этом в
большинстве языков программирования переменные могут иметь только
один тип во все время их существования. Но в некоторых тип может
меняться во время исполнения программы. В первом случае говорят о
статической, во втором — о динамической типизации.
Языки программирования могут быть как с явной, так и с неявной
системой типов. В первом случае четко фиксируется, к какому типу
относится та или иная переменная или константа, во втором об этом
отдельно речь не идет, тем не менее данные обычно обрабатываются поразному. И у первого, и у второго подхода имеются как достоинства, так и
недостатки. Динамическая неявная типизация расширяет возможности
использования переменных и избавляет программиста от хлопот,
связанных с объявлением и контролем соответствия типов. Кроме того,
данный подход позволяет создавать более универсальные и проще
интегрируемые программные модули. Однако это требует от программиста
большей ответственности, поскольку во время выполнения программы
возможны неожиданности вроде попыток перемножить две строки или
разделить число на логическое значение. При статической типизации такие
ошибки обнаружились бы на этапе компиляции. И чем больше размер
программы, тем более острой становится эта проблема.
В некоторых языках само имя переменной свидетельствует о типе
переменной. Например, в некоторых диалектах Бейсика имя переменной
A% свидетельствует, что она целочисленная, а A$ — что строковая. В
языке Perl переменная в зависимости от типа получает значок перед
именем: для скалярных переменных это $, для массивов — @, для
ассоциативных массивов — %.
ЗАМЕЧАНИЕ
Переменная в императивных языках программирования фактически является
синонимом ссылки на объект, способный в различные моменты времени

53

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

Контрольные вопросы
1. Почему нужны возможности
программирования?

описания

данных

в

языках

2. В чем заключается разница между статической и динамической
типизацией? Какие существуют способы неявного задания типа данных
в языках программирования.
3. Как влияет вариант типизации на надежность программ?

Простые типы данных
Под простыми, или базовыми, типами данных в языках программирования
понимаются объекты (переменные или константы), которые не имеют
доступной программисту внутренней структуры.
В различных языках имеются разные наборы встроенных базовых типов
данных. Так, в Си он минимален — целое число, число с плавающей
точкой, одиночный символ. В С++ уже есть специальный логический тип с
допустимыми значениями лишь ИСТИНА и ЛОЖЬ (true и false).
Любопытно, что в первом языке программирования высокого уровня
Фортран, изначально предназначавшемся для научных расчетов, в базовый
набор типов данных входят комплексные числа.
Числа в языках программирования
Начнем рассмотрение с наиболее распространенного и имеющегося
практически во всех языках программирования типа данных — целых
чисел. При объявлении переменных используются следующие ключевые
слова:


int — языки Си, С++, Java и др.;



integer — Паскаль, Модула, Алгол, Ада, Фортран и др.

ЗАМЕЧАНИЕ
Настоящих, в математическом смысле чисел в программах нет. В ЭВМ,
имеющих ограниченную память, непредставимы не только действительные
числа произвольной точности, но и целые, которые теоретически могут иметь
бесконечно большое значение. В языках программирования используют
приближения понятия числа с помощью заданного в системе количества битов.
Если при выполнении вычислений должно быть получено большее число, чем
допускает данный тип, происходит ошибка переполнения.

В некоторых языках существует тип для неотрицательных целых
(натуральных) чисел, например cardinal в Модуле. В других допустимо

54

перед наименованием целого типа указывать модификатор, указывающий,
например, что число заведомо неотрицательное (unsigned), — это
позволит за счет использования знакового разряда тем же набором бит
представить число большей абсолютной величины. Допустимы и другие
модификаторы, позволяющие при необходимости увеличить или
уменьшить отводимое под хранение переменной число двоичных разрядов.
Возможная реализация целочисленных типов в Си и диапазоны значений
(в большинстве современных реализаций следует умножить приводимые
значения на два, поскольку они ориентированы изначально на 32разрядную архитектуру):
int
16 бит
unsigned int 16 бит
short int
8 бит
unsigned short 8 бит
long int
32 бит
unsigned long 32 бит

-32768..+32767
0..65535
-128..+127
0..+255
-2147483648..+2147483647
0..+4294967295

Достаточно интересно, что в языке Си допустимо использование
префиксов signed и unsigned без идущего затем указания типа.
Например, описание переменной а как int a будет полностью
эквивалентно описанию signed int a и даже просто signed a;
Размер в битах прямо связан с тем, что для представления двух
альтернатив — 0 и 1 — достаточно одного двоичного разряда, четырех —
двух разрядов, и вообще n бит дают возможность представления 2n
различных кодов.
В Паскаль-семействе языков, а также Фортране, Алголе и Аде для
обозначения целого типа используется ключевое слово integer (в Аде
наименования типов пишутся с прописной буквы, в Фортране — часто
полностью прописными).
Для действительных чисел используются различные наименования их
приближений в языках программирования:


real — Паскаль, Модула, Оберон, Алгол, Фортран и др.;



float — Си, С++, Java, C#, Ада и др.

Небезынтересное название типа данных число с плавающей точкой
(float) связано со следующим. При записи чисел в нормализованной
экспоненциальной форме — а именно в ней хранится в двоичном виде в
памяти число данного типа — происходит перемещение запятой (в
англоязычных странах для отделения целой части от дробной используется
точка) — она «переплывает» с места на место. Например, 1255,1
представляется как 1,2551 · 103.

55

В памяти при нормализованном представлении типа float хранится
двоичное число — мантисса с фиксированным числом битов и отдельно
порядок — аналогично фиксированное количество битов. Для больших
чисел может применяться тип данных с удвоенной длиной мантиссы,
например double в Cи, C++, Java или DOUBLE PRECISION в Фортране.
Какие операции в языках программирования могут использоваться для
чисел? Как и следовало ожидать, это арифметические действия (сложение,
вычитание, умножение и деление) и сравнение. Для чисел допустимы
следующие виды сравнения: больше, меньше, равно, не равно, меньше или
равно, больше или равно. Результатом сравнения может быть специальная
переменная логического типа. В некоторых языках (Си, С++, PL/I, Java,
Ruby, C#, Паскаль) к числам применяются также побитовые логические
операции — сдвиг, И, НЕ, ИЛИ, исключающее ИЛИ.
ЗАМЕЧАНИЕ
Не следует проверять на равенство вещественные переменные типов float или
double, поскольку операция эта точная, а в памяти хранятся и получаются при
вычислениях на компьютере лишь приближенные значения. Для проверки на
равенство данных этого типа можно сравнивать модуль разности чисел с
некоторым положительным допуском ε.

Следующий важный тип данных — логический. Он может называться:


LOGICAL — в Фортране;



bool — в С++, С#;



boolean — в Паскале, Аде, Java и др.

В большинстве языков допустимые значения для логического типа носят
наименования false и true. Логические переменные могут
использоваться в условных операторах. К ним применимы операции
сравнения на равенство, а также (не побитовые) логические операции И,
НЕ, ИЛИ.
Переменная может использоваться для хранения одиночного символа.
Этот тип данных называется:



char — в Си, С++, С#, Java, Паскале и др.;
сharacter — в Фортране, Аде (см. уточнение о регистре символов) и
др.

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

56

Во многих языках программирования переменная может связываться с
целой строкой символов, среди них есть как языки со строгой статической
явной типизацией, так и иные — Бейсик, PHP, Лисп, С++, Python,
РАПИРА, Пролог и др. Стоит еще раз отметить, что Фортран — первый из
созданных языков программирования высокого уровня — имеет весьма
развитую систему типов и по этому критерию превосходит многие более
поздние языки. В нем можно использовать то же ключевое слово для
описания строк, например объявить переменную CHARACTER*20 для
хранения строки из 20 символов.
К строкам обычно применимы операции сравнения на равенство и
неравенство, а также слияние — конкатенация (так называется действие,
при котором строка приписывается в конец другой). Во многих языках
есть операция взятия символа с указанным порядковым номером. Могут
присутствовать операции определения длины строки, вырезания подстроки
из строки (РАПИРА, С++) и др.
Отдельным и весьма важным моментом является преобразование типов
данных. Допустимо ли в рамках одного выражения использовать
переменные, относящиеся к различным типам данных? Во многих
ситуациях это представляется полезным, несмотря на пользу строгого
контроля типов для надежности программ. Действительно, весьма логично
и интуитивно хочется считать допустимой запись, когда в ходе операции
деления целых чисел результат сохраняется в переменной с плавающей
точкой. Явно ничего страшного не произойдет, если мы к вещественному
числу прибавим целое.
В языках программирования выделяют явное и неявное преобразования
типов. Неявное преобразование выполняется системой с использованием
встроенных правил. Явное преобразование задает программист, используя
соответствующий синтаксис языка программирования, например:
x = (int)d * 10 + y;
/* преобразование типа в Си */
y = static_cast(65534);
// преобразование в С++

Контрольные вопросы
1. Возможно ли полноценное представление математического понятия
числа в ЭВМ? Почему?
2. Как представляются целые числа в памяти ЭВМ?
3. Как представляются дробные числа в памяти компьютера? Откуда
произошло название типа данных с плавающей запятой?
4. Какие операции над числами допустимы в языках программирования?
5. Понятие и назначение логического типа данных. Примеры.

57

6. Что такое символьный тип данных, допустимые операции, строковый
тип?
7. Зачем нужно преобразование типов данных в программах? Приведите
примеры.
Указатели
В ряде языков программирования, например Си, Паскаль, С#, допустимо
использование так называемых указателей. Они относятся к еще одной
разновидности встроенных типов данных. Указатель — константа или
переменная, задающая адрес в памяти, где располагаются некоторые
другие объекты (данные, функция).
Допустимо, в частности, объявить некую переменную, которая будет
указывать на находящееся в памяти целое.
Пример на языке С++:
int* pA; // переменная pA указывает на целое число

Теперь можно присваивать переменной-указателю значение ссылки (адрес)
целого и после этого обращаться к объекту в памяти через указатель на
него.
Пример на языке С++:
int a=10;
pA=&a; // pA теперь указывает на a
*pA=100; // эта запись присваивает переменной a значение 100

Смешивать типы при использовании указателей в общем случае
недопустимо. Ссылки могут использоваться и для составных структур
данных, в частности, они активно применяются при обработке массивов и
списков.
В языках программирования встречается предопределенное наименование
для пустой ссылки — указателя, еще не связанного с каким-либо объектом
в памяти, часто это NULL или NIL.
Контрольные вопросы
1. Что такое указатели? Приведите пример их использования в языках
программирования.
2. Что такое пустой указатель?
Перечисления

58

В некоторых языках программирования допускается задание так
называемых перечислений. Бывает удобно называть объекты в программе
привычными именами, а не раз и навсегда заданными наименованиями
типов. Перечисления отвечают указанной потребности, например:
Type DAY=(Monday,Tuesday, Wednesday,Thursday, Friday, Saturday,
Sunday); (* Паскаль*)
type Cardsuit is (clubs, diamonds, hearts, spades); -- Ада
enum MyColors {Red = 100, Green = 110, Blue = 120} // C#

В них явным образом указывается набор значений, допустимых для данной
переменной, — фактически, создается новый тип данных. После его
введения допускается объявление переменной данного типа наряду с
базовыми, например:
MyColors cwet=Green; // С#

Обычно при компиляции значения перечислений представляются целыми
числами. В зависимости от языка программирования представление может
быть либо полностью скрыто от программиста, либо доступно ему,
например, путем принудительного преобразования значения типа
«перечисление» к значению типа «целое число», либо даже управляемо
явно, как показано в примере.
При попытке присвоить переменной перечислимого типа значение, не
указанное при его определении, будет выдаваться ошибка. Это позволяет
еще более повысить надежность программ по сравнению с простой
статической типизацией. Перечислимый тип используется довольно
широко и воспринимается как сама собой разумеющаяся особенность
современных языков программирования. Тем не менее не обходится без
критики со стороны теоретиков и практиков программирования. При
разработке языка программирования Оберон перечислимые типы попали в
список особенностей, которые были удалены из него. Никлаус Вирт,
разработчик языка, назвал следующие причины: «Во все возрастающем
числе программ непродуманное использование перечислений… приводит
к демографическому взрыву среди типов, что, в свою очередь, ведет не к
ясности программ, а к многословию».
ЗАМЕЧАНИЕ
Добавление типов данных к базовому набору является частью концепции
абстрактного типа данных, более подробно рассмотренной в разделе,
посвященном объектно-ориентированному программированию.

Составные типы данных
Составные типы данных подразумевают некую внутреннюю структуру,

59

обычно представляя собой соединение элементов базовых типов,
выполненное с использованием предопределенных правил. Элементами
составных структур данных, в свою очередь, часто могут быть сложные
структуры.
Начнем рассмотрение с наиболее популярной структуры, имеющейся
почти во всех языках программирования, — массивов.
Массивы
Массив —
это
проиндексированный
(в
простейшем
случае
пронумерованный) набор однородных элементов. Объявление массива в
различных языках программирования может выглядеть так:
10 DIM A(10) 'Бейсик — одномерный массив из 10 элементов
DIMENSION A(20), B(20,100), C(0:10) ! Фортран — три массива
Var Vector = array [1..10] of integer;(*Паскаль,с заданием границ*)
int a[12][2]; /* Си — двумерный массив */
int[,] mass = new int[4,5]; /* C# — двумерный массив */

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

и

Массивы могут быть статическими и динамическими (последние
разрешены далеко не во всех языках программирования, но имеются,
например, в Фортране). При объявлении статического массива
программист должен заранее знать его размер. Если это невозможно (Си,
Паскаль и пр.), приходится выделять память с запасом — столько, чтобы
ее заведомо хватило для целей программы. Динамический массив — это
массив, размер которого определяется при выполнении программы, тогда
же происходит и выделение памяти под него.
В некоторых языках программирования индекс может изменяться лишь в
пределах от единицы до N (Бейсик) или от нуля до N – 1 (Си. Это
обусловлено смещением элемента от адреса начала массива в памяти,
причины подробнее рассмотрены в посвященном этому языку разделе.). В
других, например Паскале и Фортране, допускается устанавливать
произвольные границы изменения индекса для каждого измерения.
ЗАМЕЧАНИЕ
В некоторых языках программирования, например Си, строки реализованы как
одномерные массивы данных символьного типа.

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

60

недопустимо. Некоторые языки программирования, такие как APL и его
потомки K и J, изначально ориентированы на обработку массивов, в них
операции применимы к целому массиву (ко всем элементам). Например,
можно сложить два массива или найти сумму элементов с помощью
операции, записываемой одним знаком.
В некоторых языках программирования помимо обычных массивов
применяются так называемые ассоциативные массивы, в которых в
качестве индекса может использоваться не только целое число, но и
значение произвольного типа данных. Точнее говоря, ассоциативный
массив представляет собой набор пар вида (ключ, значение) и
поддерживает операции добавления пары, а также поиска и удаления по
ключу (индексу). В некоторых языках поддержка ассоциативных массивов
встроена в язык, в других — нужно использовать стандартную библиотеку.
Примеры описаний ассоциативных массивов:
map book; //объявление язык С++, библиотека STL
$names["Петров"]="Петр"; // обращение в языке PHP, фамилия — ключ
print $hash{'cat'}; # язык Perl

Ассоциативный массив может быть и многомерным. Многомерные
ассоциативные
массивы
могут
содержать
несколько
ключей,
соответствующих конкретному индексу ассоциативного массива.
Пример многомерного ассоциативного массива на языке PHP:


Контрольные вопросы
1. Что такое массив?
программирования.

Приведите

примеры объявления в языках

2. Что такое одномерный и многомерный массивы? Приведите примеры
использования.
3. Что такое статический и динамический массивы? Какие преимущества
и недостатки имеют динамические структуры данных?
4. В чем заключаются особенности структуры данных с произвольным
доступом?

61

5. Что такое ассоциативный массив? Приведите пример использования.
Списки
Следующей важнейшей структурой данных являются списки. Такого рода
структуры в языках программирования весьма разнообразны. Простейшей
является линейный односвязный список, реализованный на базовом уровне
в таких языках программирования, как Питон, Лисп и Пролог.
Линейный список представляет собой набор идущих друг за другом
элементов, при записи разделяемых пробелом, запятой или иным знаком,
например:
(Чайник Кастрюля Самовар)
[a,b,c,d,e]

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

NIL — в языке Лисп;



[] — одно из обозначений в языке Пролог.

Основными операциями над списками служат:


взятие первого элемента — так называемой головы списка;



взятие остатка списка, также являющегося списком, или его хвоста;



добавление элемента в список;



удаление заданного элемента из списка;



проверка на вхождение элемента в список;



приписывание списка к списку;



подсчет количества элементов списка.

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

62

Во многих языках программирования списки не являются встроенной
структурой (хотя могут быть частью библиотеки, например, для С++
существует мощная библиотека STL), и их поддержка требует
конструирования на основе записей и ссылок (указателей). Это упражнение
весьма популярно при изучении Паскаля или Си. Такую реализацию
списка иллюстрирует рис. 9.
Д

Рис. 9

Элементы подобного списка иногда называют вершинами. Каждая
вершина здесь представляет собой элемент однотипных данных, хотя это
могут быть и данные составного типа, и указатель на следующий элемент
списка. Последний элемент списка содержит пустую ссылку.
В языках программирования, поддерживающих списки на базовом уровне,
часто допускается наличие в списке в качестве элементов данных
различающихся типов. Элементом списка может быть и список — в этом
случае говорят о вложенных списках.
Другие виды списков
Нетрудно заметить, что в линейном односвязном списке возможно лишь
движение от головы к хвосту. Иногда удобно иметь возможность
обратного продвижения по списку. Для этого достаточно налачия в каждой
вершине двух указателей — на предшествующий и последующий
элементы. Графически реализацию двусвязного списка можно представить
следующим образом (рис. 10).

63

Рис. 10

При реализации двусвязного списка у первого элемента делается пустая
ссылка на предшествующий.
Использование нескольких ссылок в каждой вершине позволяет строить и
более сложные списочные структуры, например деревья.
Дерево — частный случай многосвязного списка. Оно имеет
иерархическую организацию. Вершина дерева, не являющаяся ничьим
потомком и называемая корнем дерева (рис. 11), имеет ссылки на
вершины, называемые потомками, причем они не могут ссылаться на эту
вершину. В нижней части иерархии — вершины-листья, не имеющие
потомков (ссылки NIL).

Рис. 11

Чаще всего в практике программирования используются бинарные деревья
(у каждой вершины не более двух потомков).
Обработка деревьев обычно производится путем обхода вершин дерева в
том или ином порядке. Известны алгоритмы обхода деревьев снизу вверх,
сверху вниз и слева направо. Популярными операциями над деревьями
служат также поиск поддерева в дереве, удаление поддерева и добавление
вершин.

64

Иногда на основе списков строятся такие структуры данных, как стеки и
очереди.
Весьма важным при ручной реализации динамических структур данных
является следующее обстоятельство. При добавлении элемента в
динамическую структуру данных необходимо выделить необходимую
память, а при удалении — освободить ее. При этом в процессе работы с
динамическими типами данных в языках программирования память
выделяется из специального пула, называемого кучей. Если в языке
программирования отсутствует механизм автоматического управления
памятью при удалении — так называемая сборка мусора, ответственность
за очистку памяти возлагается на программиста, который должен
проделать это явным образом.
Сборщик мусора периодически освобождает память, удаляя объекты,
которые уже не будут востребованы приложением. Изначально он имеется
в таких языках, как Лисп и Java. Однако при выполнении программ на этих
языках наличие автоматической сборки мусора может приводить к
непредсказуемым задержкам в заранее не известные моменты времени. В
связи с этим на Си, например, управление памятью осуществляется
вручную с использованием библиотечных функций. Ниже приводится
возможный вариант программирования динамического массива на языке
Си:
#include
#define N 10
int main()
{
double* ptd; // объявляем указатель на массив
/* запрос выделения памяти из «кучи» */
ptd = (double*)malloc(N * sizeof(double));
if(ptd != NULL) /* если памяти нет, malloc возвращает NULL*/
{
for(int i = 0;i = glasn и soglasn ");scanf("%d",&a);
if (a%2) s+=a; /* экивалентно if (a%2!=0) s=s+a;*/
} while (a!=0); /* можно просто while(a); но это менее понятно*/
printf("сумма нечетных среди введенных =%d\n",s);
return 0;
}

Обратите внимание на некоторые особенности программы. В ней

107

соблюдены правила хорошего тона: после запуска до пользователя
доводится краткая информация о ее предназначении и делается
приглашение к вводу чисел. При этом для каждого очередного числа
выдается >. Вывод приглашения с помощью printf() и ввод с помощью
scanf() сгруппированы в одной строке, что вполне логично.
Используется цикл do (ДО) для ввода чисел и подсчета суммы нечетных.
Для определения четности/нечетности введенного числа используется
встроенная в язык операция % взятия остатка от деления. Если остаток от
деления на 2 ненулевой — число нечетное, в противном случае — четное.
Поскольку в языке программирования Си нет выделенного логического
типа и любое ненулевое число воспринимается как логическая ИСТИНА,
можно записать if (a%2) вместо if (a%2!=0). Этим, как и
сокращенной записью s+=a вместо s=s+a, соблюден дух Си. Однако это
несколько ухудшает прозрачность программы, и при проверке
ограничителя цикла подобный трюк не применяется.
Напишем теперь второй вариант программы. В нем сначала будем
запрашивать пользователя о количестве подлежащих обработке чисел.
Кроме того, вместо условного оператора if применим условное
выражение ?:
/* Сумма нечетных вторым способом */
#include
#define MAXN 1000 /* максимальная длина последовательности чисел */
int main()
{
int a,i,n,s=0; /*s — сумма, обнуляем*/
printf("Программа нахождения суммы нечетных членов числового
ряда\n");
printf("Введите количество чисел (");scanf("%d",&a);
s+=((a%2)?a:0); /* прибавляем или само число a, или ноль */
}
printf("сумма нечетных среди введенных =%d\n",s);
return 0;
}

В этом варианте следует обратить внимание на ввод ограничения сверху на
длину обрабатываемой числовой последовательности с помощью
директивы #define. Затем у пользователя запрашивается действительное

108

количество чисел, подлежащих обработке, n. Для ввода и обработки
используется единый цикл for, в котором переменная цикла i меняется от
0 до n – 1 путем записи for (i=0;ia=5;
uk->b=5;
uk->c=0xB;
printf("Битовое поле = %d\n",uk->a);
printbin((int*) uk);
return 0;
}

Как уже отмечалось, язык Си — язык системного программирования.
Неудивительна поэтому легкость интеграции Си с ассемблером. Например,
во многих версиях Си-систем вполне допустимы прямые ассемблерные
вставки в программу по следующему принципу (значение команд
ассемблера приводится в соответствующем разделе данной книги):
/* ассемблерные вставки в программу на Си */
#include
#pragma inline
int main ()
{
int a=10,b=20,c;
print ("a= %d, b=%d\n",a,b);

119

asm mov ax,10; /* строка на ассемблере — занесение 10 в регистр
AX */
asm mul a; /* строка на ассемблере — команда умножения AX на a
*/
c=_AX; /* прямой доступ к регистру AX процессора, с = 100 */
print ("c= %d \n",c);
/* целый фрагмент на ассемблере */
asm { mov ax,a
mov bx,b
xchg ax,bx
mov a,ax
mov b,bx
}
print ("a= %d, b=%d\n",a,b);
return 0;
}

Как видно из примера (варианта реализации Си-системы), в программе на
Си возможно прямое обращение к регистрам процессора, при этом их
имена предваряются символом подчеркивания _ (для процессоров
архитектуры Intel x86 это _AX, _BX, _DX и пр.). Для вставки одной строки
на языке ассемблер достаточно написать в ее начале ключевое слово
asm — и все дальнейшее до знака перевода строки будет восприниматься
как строка ассемблера. Несколько строк можно вставить с помощью
конструкции asm {}. Чтобы подобные вставки стали допустимыми,
используется директива препроцессора #pragma inline. Изнутри
ассемблерных вставок переменные, объявленные в программе на Си,
остаются доступными просто по их именам (контроль типов —
применимости ассемблерных команд к данным — ложится на
программиста).
Контрольные вопросы и упражнения
1. Что означает запись (*z)++? Как изменится значение переменной z?
Значение по адресу z?
2. В чем разница между записями a[5] и *(a+5) при обращении к
элементу массива?
3. Каким образом вы применили бы в программах указатели на функции?
Приведите пример.
4. В какой ситуации нужны функции с переменным числом параметов?
5. В каких ситуациях уместно использование битовых полей? Придумайте
пример.

120

6. Возможен ли доступ из ассемблерной вставки к переменной Си?
7. Возможен ли доступ в программе на Си к регистру процессора?

Достоинства и недостатки языка Си
Язык программирования Си был создан довольно давно — в 1971 году.
После появления он очень быстро завоевал популярность и потеснил такие
языки, как Фортран, Алгол и PL/I. Впоследствии язык Си сыграл
значительную роль в развитии языков программирования — стал
непосредственным прародителем или оказал влияние на такие языки, как
Objective C, C++, Java, C#, PHP, D и др.
Согласно рейтингу языков программирования TIOBE, на октябрь 2013
года чистый Си по популярности находится на первом (!) месте среди
языков программирования, опередив Java (второе место), С++ (четвертое)
и С# (шестое). Более того, шесть первых мест рейтинга заняты языками,
родственными Си!
В чем причина такого успеха?
Несомненными достоинствами языка программирования Си являются:






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

В то же время следует еще раз отметить ряд особенностей языка
программирования Си, которые, на взгляд автора (несмотря на то что
обычно достоинства являются продолжениями недостатков и наоборот),
вполне можно считать его недостатками и которые ограничивают сферу
его успешного применения.
Конструкции Си изначально рассчитывались на профессионалов —
системных программистов, и поэтому текст программы как минимум не
вполне ясен начинающему программисту, а кроме этого он предоставляет
весьма широкие возможности — можно сказать: язык «остер, как
бритва» — можно порезаться! На Си допустим, к примеру, следующий
фрагмент программы (сочинен студентами МАИ):
int X;
X = 1;
X+=X++ + ++X; /* Догадайся, чему будет равен X? */

Си (и, увы, во многом произошедшие от него языки, хотя в них пытались

121

эту проблему решать — например, в Java запрещено в явном виде
использование указателей и отсутствует адресная арифметика) изобилует
потенциально небезопасными конструкциями. Так, в нем можно
применить присваивание вместо проверки на равенство внутри оператора
if, например:
if (current->uid=0) retval=1;

и это не вызовет ошибки. Кстати, для борьбы именно с этой уязвимостью
был предложен метод записи условий в программах на Си, названный
нотацией Йоды. Этот персонаж саги «Звездные войны» необычным
образом строил предложения, меняя привычный порядок слов. При записи
if в программе на Си в виде условия Йоды сначала пишется константа, с
которой производится сравнение, и лишь после знака — переменная:
if (0==current->uid) retval=1;

Естественно, присвоить числовой константе значение нельзя, и это вызовет
ошибку. Некоторые программисты считают хорошим тоном использовать
в программах на Си нотацию Йоды. Однако это не спасает ситуацию в
целом. Не вызывает сомнений, что Си – изобилующий потенциальными
опасностями и не вполне прозрачный для восприятия человеком язык. В
приложении А содержится позаимствованный из книги Павловской [12]
пример совершенно нечитаемой и тем не менее корректной для языка Си
программы. Поэтому Си нужно с осторожностью использовать для
начального
обучения
программированию.
Весьма
популярной
альтернативой для этого у нас в стране является Паскаль.
Из-за слабого контроля действий программиста (таких особенностей, как
ручное управление динамической памятью — отсутствия сборки мусора,
не существующей автоматической инициализации переменных, адресная
арифметика, отсутствия контроля выхода индекса за пределы массива, и
пр.) при программировании на Си потенциально совершается больше
ошибок, чем при программировании на Модуле-2, Обероне или Аде. Но
несмотря на это он, как кажется автору, неоправданно популярен при
создании критических приложений, например, в аэрокосмической
промышленности или автоматизированных системах управления
технологическими процессами.
Своеобразный промежуточный уровень языка Си, как считают многие
исследователи, не позволяет эффективно применять его при написании
приложений, требующих высокого уровня абстракции, например систем
искусственного интеллекта. Для этих областей гораздо лучше подойдут
Пролог или Лисп.

122

Язык ассемблера (автокод)
Как мы уже знаем, ассемблеры возникли в качестве первых отличных от
машинных кодов средств программирования и относятся к второму
поколению языков программирования. Какой же смысл сегодня, в XXI
веке, изучать эту древность? Или язык ассемблера — современное
средство?
Разберем
этот
вопрос
подробнее.
Среди
языков
программирования ассемблер ближе всего к архитектуре ЭВМ,
следовательно, он требует от программиста досконального знания деталей
реализации данной ЭВМ, особенностей архитектуры. Это позволяет писать
эффективные программы — короткие, быстрые, не требующие большого
объема памяти. Где они востребованы и востребованы ли? Ответ на этот
вопрос — востребованы, и эта ситуация будет наблюдаться, по всей
видимости, еще много лет.
Как бы ни показалось удивительным некоторым читателям, но существуют
применения ЭВМ, где доступные ресурсы до сих пор весьма ограниченны.
Это, например, встроенные микропроцессоры и микроконтроллеры. А
ведь именно они представляют собой наиболее многочисленный класс
современных ЭВМ, если подсчитать все используемые суперкомпьютеры,
мэйнфреймы, мини-ЭВМ (рабочие станции), персональные компьютеры
и т. д. Микроконтроллеры повсюду — в телевизорах, телефонах,
микроволновых печах, автомобилях, лифтах… Другой пример —
системные программы (ядро операционной системы, драйверы). Можно
привести в качестве примера также большие программные комплексы,
работающие в системах массового обслуживания, в которых имеется узкое
«бутылочное горлышко» — фрагмент программы, наиболее часто
выполняющийся и критический с точки зрения производительности
системы в целом. Такой фрагмент целесообразно писать на ассемблере,
даже если остальная программная система использует Java или C#.
Весьма важный аспект — информационная безопасность. Вирусы и
вредоносные программы, программы-шпионы используют бреши в
уязвимости компьютерных систем со знанием тончайших деталей и
особенностей архитектуры. Для того чтобы противостоять им, нужно
обладать не меньшими познаниями и искусством программирования на
уровне машины. Неудивительно, что умение программировать на
ассемблере — своеобразный знак качества программиста, а разработчики
подобных программ окружены ореолом таинственности как носители
тайного знания. Но это не каждому по плечу!
Рассматривать ассемблер мы будем на примере программирования
микропроцессоров Intel семейства x86. Данная архитектура не является ни
наиболее простой для изучения, ни наиболее удобной и оптимальной с
точки
зрения
разработки
программ.
Настоящие
ценители

123

программирования на ассемблере помнят изящество архитектуры
ассемблера ЭВМ разработки компании DEC семейства PDP-11 [13].
Причина выбора данного языка заключается в невероятном количестве
выпущенных по всему миру компьютеров, основанных на архитектуре
x86 — впрочем, далеко не единственной выпущенной компанией Intel, в
послужном списке которой такие замечательные архитектуры, как,
например, iAPX 432 и Itanium. Из чего следует, что, во-первых, не должно
быть проблем с его нахождением и проверкой примеров, а во-вторых,
читатель, не исключено, сможет извлечь из материала некоторую
практическую пользу для себя. Ведь, как показывает многолетний опыт
преподавания, учащиеся не любят изучать новые языки и склонны в
практической работе на протяжении долгих лет использовать именно тот
язык программирования, который изучили на первом курсе... Ниже
представлены этапы исторического развития процессоров Intel.
1971 г. — первый в мире микропроцессор 4004, создан Intel
(внутри 16 разрядов, снаружи 8 разрядов) 1978
|
80186

8088

|
80286 (IBM PC AT) 1982
|
80386 (32-разрядный, защищенный режим) 1985
|
80486 1989
|
Pentium — PentiumPro (увеличенный размер кэш-памяти) 1993
|
Pentium MMX (multi medium extension) 1997
|
Pentium II 1997
|
Pentium III 1999
|
Pentium IV 2000
|

124

Core 2 Duo (многоядерный) 2006
|
Pentium G 2011
Другим важным обстоятельством является то, что огромный массив
существующих программ был разработан именно для x86, так что, весьма
вероятно, читателю придется разбираться именно с подобными
программами.
ЗАМЕЧАНИЕ
Данная глава ни в коем случае не является учебником по программированию
на языке ассемблера — весьма нетривиальной технической дисциплине,
имеющей массу нюансов. Она дает лишь весьма поверхностное общее
впечатление, позволяющее в некоторой степени понять особенности
программирования на ассемблере и способное стать отправной точкой для его
последующего изучения по специализированной литературе, например [13].

Для дальнейшего изложения нам потребуютсякраткие дополнительные
сведения об архитектуре ЭВМ — в частности, о представлении команд.
Для представления команды в памяти ЭВМ необходимо закодировать
двоичным кодом само действие и операнды — то, над чем производится
действие.
Поле команды состоит из двух частей — операционной и адресной. В
операционной части записывается код операции (КОП). Этот код
определяет действие, которое команда должна выполнить над данными
(обычно арифметическое или логическое). Адресная часть команды
содержит адреса ячеек памяти — операндов, обрабатываемых в операции.
Количество приводимых в команде адресов может быть различным.
Основными вариантами архитектур ЭВМ являются: трехадресная;
двухадресная; одноадресная.
КОП А1 А2 А3

КОП А1 А2

КОП А
Рис. 17

125

Большинство
операций,
реализуемых
арифметико-логическими
устройствами современных процессоров, — двухместные (бинарные), это
означает, что в результате обработки двух операндов получается один
результат. Рассмотрим пример вычисления выражения z=x+y.
В трехадресной архитектуре — самой полной — часть двоичного кода
команды отводится под представление операции. Например, 000110 —
сложение (в архитектуре PDP-11). Кроме этого, в ней присутствуют три
адреса: адрес первого операнда x — А1, адрес второго y — A2, и адрес, в
который нужно поместить результат, z — A3. Трехадресная архитектура
является наиболее гибкой, но и наиболее затратной с точки зрения объема
памяти, необходимого для представления каждой команды. Если адресное
пространство соответствует микропроцессорам 8086, под каждый из
адресов потребуется 20 бит. Соответственно, каждая команда должна быть
длиннее 60 бит, что не очень хорошо с точки зрения упаковки больших
программ.
Большинство современных ЭВМ, в том числе микропроцессоры семейств
x86, — двухадресные. В них в команде присутствуют два адреса, один из
которых используется как для взятия операнда, так и для помещения по
этому же адресу полученного результата. Примером может служить
x=x+y. Данный подход позволяет без существенной потери гибкости
сэкономить заметное количество памяти.
На одноадресной архитектуре были построены первые микропроцессоры.
В ней присутствует аккумулятор — специальный выделенный регистр в
процессоре, в который по умолчанию попадают результаты всех операций.
Из него же по умолчанию берется один из операндов. Соответственно, в
команде достаточно указать адрес всего одного операнда.
Самый экстремальный случай — безадресная архитектура. В ней команда
содержит лишь КОП. Операнды по умолчанию берутся из заранее
известного места — чаще всего из стека (два числа на вершине стека) (см.
раздел о структурах данных).
ЗАМЕЧАНИЕ
Не все команды используют адресные поля полностью. Есть действия, по своей
природе имеющие один адрес (например, смена знака числа). Есть команды и
вовсе не требующие указания адресов операндов (останов, пустая операция,
системный сброс и т. д.). В ЭВМ трехадресной и двухадресной архитектур
некоторые команды будут одноадресными и безадресными.

При обращении к ячейке памяти в программе на ассемблере можно указать
конкретный адрес в виде числа (в большинстве случаев
шестнадцатеричного или восьмеричного) — так называемый абсолютный
адрес (рис. 18).

126

Рис. 18

Существуют и другие способы адресации (обращения к ячейке). При
косвенной адресации в команде указывается регистр или ячейка памяти,
где располагается адрес операнда, а не сам операнд (рис. 19).

Рис. 19
ЗАМЕЧАНИЕ
Именно эта низкоуровневая особенность архитектуры ЭВМ повлияла на
концепцию указателей в языках Си-семейства.

В некоторых архитектурах реализованы еще более сложные способы
адресации. При автоинкрементной и автодекрементной адресации после
обработки данных при косвенной адресации автоматически происходит
увеличение или уменьшение адреса, что позволяет, например, эффективно
обрабатывать массивы (переходить к следующей ячейке). Эта
низкоуровневая особенность повлияла на такую конструкцию языков
программирования Си-семейства, как -- и ++.
Индексная, или базовая, адресация подразумевает, что, как в случае
косвенной адресации, в команде указываются ячейка, в которой находится
некоторый адрес в памяти, называемый базой, и смещение — величина,
которую надо предварительно прибавить к базе, чтобы получить адрес,
где, собственно, и находятся данные (рис. 20). Этот способ адресации
также применяется для обработки массивов.

Рис. 20

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

127

ЗАМЕЧАНИЕ
В некоторых архитектурах могут реализовываться и другие более экзотические
способы адресации операндов.

Обычно процессор помимо УУ, АЛУ и СК имеет встроенные так
называемые регистры. Они представляют собой сверхоперативную
память — команды могут обрабатывать данные без необходимости
обращения к ОЗУ ЭВМ, что значительно ускоряет вычисления. Регистры
могут указываться в командах вместо адресов данных в памяти.
В архитектуре x86 имеется несколько регистров, которые можно
использовать произвольным образом (почти), или регистров общего
назначения. Они имеют обозначения AX, BX, CX, DX, SI и DI. Несмотря на
универсальность, в программах регистры зачастую используются в
определенных целях и поэтому имеют дополнительные имена: AX —
аккумулятор, BX — база, CX — счетчик, DX — данные, SI — индекс
источника, DI — индекс результата.
Определив подходы к представлению команд в памяти ЭВМ, поговорим
немного о представлении данных. Компьютер имеет базовый параметр,
называемый разрядностью, определяющий размер машинного слова —
порции данных, обрабатываемой процессором при выполнении одной
команды. Сегодня разрядность у массовых компьютеров — 16, 32, 64
бит — два, четыре или восемь байт соответственно. Тем не менее обычно
минимально адресуемой единицей памяти является байт, и у 16-разрядной
ЭВМ, например, адреса соседних ячеек (слов) различаются на 2. При
представлении дробных чисел в современных ЭВМ обычно производится
нормализация и хранятся мантисса и порядок числа.
Важным является представление знака для чисел. Не вдаваясь в
подробности, отметим, что обычно допустима обработка как беззнаковых
чисел, так и чисел со знаком. При этом, если число рассматривается как
число со знаком, обычно крайний старший разряд слова принимается
носителем знака по следующей схеме: ноль — число положительное,
единица — отрицательное.
Символы и строки хранятся в памяти ЭВМ с использованием той или иной
системы кодирования. Наиболее распространены вариации кода ASCII и
Unicod. В кодировке ASCII (American Standard Code for Information
Interchange — увы, кодировка американская, и с русскими буквами мы
имеем массу проблем...) для кодирования одного символа используется 1
байт (фактически, изначально 7 бит, именно это позволило при создании
основанных на ней русскоязычных кодировок добавить кириллицу, но для
простоты можно считать, что 8 бит).
Программа на ассемблере может включать несколько секций (некоторые

128

не являются обязательными), или разделов (например, в ассемблерах
MASM и Flat Assembler):


заголовок;



описание интерфейса и подключаемых библиотек;



описание данных (констант и переменных);



собственно команды.

Правила записи заголовка и интерфейса программы могут различаться в
разных версиях программы-переводчика (также называемой ассемблером).
Автор рекомендует для программ на ассемблере x86 использовать
свободно распространяемый Flat Assembler, снабженный довольно
солидным набором библиотек, включающих, в частности, неплохую
поддержку компьютерной графики.
Основная часть программы на языке ассемблера состоит из выражений.
Все выражения могут быть записаны в следующем условном виде:
[Метка:] [Оператор] [Операнды] [; Комментарий]

Выражения могут быть директивами ассемблера и мнемоническими
обозначениями команд. Различие между ними следующее. Мнемоника
команды ассемблером превращается в машинный код, кототрый затем
записывается в память программы и в ходе ее исполнения обрабатывается
процессором. Директивы называются также псевдокомандами — это некие
предписания ассемблеру, предназначенные для программы-переводчика, а
не процессора. Набор команд специфичен для каждого процессора
(архитектуры). Директивы определяются реализацией программы
ассемблирования.
Сначала рассмотрим запись программы на языке ассемблера с помощью
команд:
A1:
mov
ax,2 ; занесение в регистр AX процессора числа 2
mov
bx,2 ; занесение в регистр BX процессора числа 2
add bx,ax; сложение содержимого BX и AX, результат → в BX

Надеемся, приведенный фрагмент не вызвал у читателя затруднений . В
данном примере данные заносились и обрабатывались в регистрах общего
назначения процессора. Если данные хранятся в памяти, ячейке обычно
дается мнемоническое имя с помощью соответствующих директив
ассемблера. Рассмотрим следующий пример (ассемблер MASM):
; в разделе описания данных
S1 dw 2 ; занесение в ячейку числа 2 и ее обозначение как S1
S2 dw 3 ; занесение в ячейку числа 3 и ее обозначение как S2
S3 dw ? ; резервирование ячейки памяти с именем S3
P db ? ; резервирование одного байта

129

MAS
STR

dw 1,2,-4,11,25; начиная с адреса MAS занесены пять чисел
db 'Привет'; начиная с адреса STR идут байты строки символов

; в разделе описания команд они обычно отделены друг от друга
sub
S2,S1; вычитание содержимого ячейки S1 из S2

ЗАМЕЧАНИЕ
В процессорах x86 при записи двухадресных команд адрес, куда помещается
результат операции, указывается до запятой. В других ассемблерах может быть
иначе.

Команды можно разделить:







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

Рассмотрим основные команды пересылки данных. Наиболее часто
используемая — mov. Эта двухадресная команда создает копию данных,
находящихся по указанному адресу, в другом месте. Примеры:
mov
mov
mov

ax,bx; копирование содержимого регистра BX в AX
cx,99; занесение 99 (непосредственная адресация) в CX
S1,S2; копирование значения ячейки S2 в ячейку S1

При программировании на ассемблере весьма активно используется
системный стек (см. описание стека как структуры данных в
соответствующем разделе). Для занесения информации на вершину стека
используется команда push, для снятия — pop:
push 99; занесение числа 99 в стек
push dx; сохранение в стеке содержимого регистра DX
pop
dx; снятие с вершины стека значения в регистр DX

В системе команд процессоров x86 есть еще одна весьма полезная пара
команд — pusha и popa. Они не имеют аргументов и предназначены для
занесения текущих значений всех регистров процессора в стек и
восстановления оттуда соответственно. Используются, например, при
вызове подпрограмм. Можно провести параллель между использованием
регистров процессора в этой ситуации и локальных переменных — в
языках высокого уровня.

130

ЗАМЕЧАНИЕ
В настоящей книге не рассматриваются все команды ассемблера x86 — и тем
более все возможные команды языков ассемблера различных ЭВМ.

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

ax,bx; обмен содержимым AX ↔ BX

Перейдем к командам преобразования данных. Это в первую очередь
арифметические операции, а также логические операции и команды
сдвигов. Сложение и вычитание весьма просты:
add
sub

ax,2; прибавление числа 2 к регистру AX
N,-1; вычитание минус единицы из ячейки с именем N

Существуют две специальные команды для уменьшения (декремента) и
увеличения на единицу (инкремента):
inc
dec

cx; cx=cx+1
N; уменьшение на единицу содержимого ячейки с именем N

Данные команды занимают меньше места в памяти и выполняются
быстрее, нежели sub и add с аргументом 1. В языке программирования
Си очевидна параллель — -- и ++.
Несколько более интересны команды умножения и деления. Во-первых,
система команд x86 предусматривает по две команды для умножения и
деления чисел — со знаком и беззнаковых. Умножение беззнаковых чисел
производится командой mul, чисел со знаком — imul. Во-вторых,
команда одноадресная — по умолчанию один из аргументов берется из
регистра AX и туда же заносится результат. Если результат не умещается в
AX полностью, старшие биты произведения помещаются в DX. Рассмотрим
пример:
mov
mov
mul

bx,5; первый сомножитель 5 заносим в BX
ax,25 ; второй сомножитель 25 → в AX
bx ; умножаем 5 * 25, результат → в AX

Команда деления беззнаковых чисел — div, чисел со знаком — idiv.
Поскольку аргументы воспринимаются как целые числа, а для них
полноценное математическое деление невозможно, операция производится
как целочисленное деление с занесением неполного частного в младшие
биты регистра AX, которые обозначаются AH, а остатка от деления — в его
старшие биты (AL). При делении чисел размером 1 байт частное заносится
в AL, а остаток — в DL.

131

ЗАМЕЧАНИЕ
Это обстоятельство может быть использовано при написании варианта
программы
подсчета
суммы
нечетных
элементов
числовой
последовательности.

Логические операции производятся побитово (аналоги в Си — !, |, &):
and
ax,64; логическое И с маской 64 (1000000) над AX
or dx,ax; логическое ИЛИ
xor
cx,cx; XOR исключающее ИЛИ — кстати, дает обнуление

Имеется набор команд сдвига. Первый аргумент при этом рассматривается
как набор битов, которые будут сдвигаться влево или вправо. Второй же
аргумент — целое без знака, показывающее, насколько надо сдвинуть
первый операнд.
Команда shl — логический сдвиг влево, ее действие иллюстрирует
рис. 21.
0
Рис. 21

Обратите вниманиена то, что крайний левый бит не теряется, а попадает в
специальный разряд — флаг — процессора, называемый CF. В младший
разряд заносится ноль. shr — логический сдвиг вправо, работает
аналогично.
ЗАМЕЧАНИЕ
Логический сдвиг влево и вправо позволяет выполнить быстрое умножение и
деление беззнакового целого числа на делители, представляющие собой
степени числа 2, не требующее накладных расходов команды div.

Для подобного умножения и деления чисел со знаком можно применять
специально предусмотренные в системе команд ассемблера x86
арифметические сдвиги: sal — арифметический сдвиг влево, sar —
арифметический сдвиг вправо (рис. 22).

Рис. 22

Особенность циклических сдвигов заключается в том, что разряды
двигаются по кольцу. Причем существует две разновидности сдвигов в
зависимости от использования флага процессора CF: rol — циклический
сдвиг влево, ror — циклический сдвиг вправо (рис. 23).

132

Рис. 23

В команде rol, как показано на рисунке, бывший самым левым бит
заносится в качестве правого (младшего) и одновременно копируется в CF.
Команды сдвига через перенос rcl — циклический сдвиг влево и rcr —
циклический сдвиг вправо работают следующим образом (рис. 24).

Рис. 24

Поскольку речь зашла о флагах процессора, стоит рассмотреть их
подробнее. Обычно они используются при выполнении команд условного
перехода. В процессорах x86 используются следующие основные флаги:








ZF — флаг нуля, устанавливается в единицу, если результат равен 0;
SF — флаг положительного/отрицательного значения, устанавливается,
если результат меньше 0;
CF — бит переноса из старшего разряда результатов;
OF — флаг переполнения, устанавливается,
поместился в разрядную сетку ЭВМ;

если

результат

не

PF — флаг четности, устанавливается, если в 8 младших байтах
результата содержится четное количество двоичных единиц.

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

ax,bx; сравнение АХ и ВХ

В зависимости от флагов можно выполнить условный переход к метке. В
языке ассемблера x86 существует богатый набор команд переходов, часть
из которых приведены далее, причем допустимы две формы
мнемонической записи (указаны через дробь), что, вообще говоря, — не
лучший подход с точки зрения соблюдения стиля программирования:


JE/JZ — переход по нулю (JE — переход по равенству после cmp);



JNE/JNZ — если не ноль (не равны аргументы предыдущей cmp);



JG/JNLE — переход, если больше для знаковых;



JGE/JNL — переход, если больше или равно для знаковых;



JAE/JNBE — переход, если больше или равно для беззнаковых;

133



JC/JNAE — переход, если бит СF установлен в единицу.

Переходы необходимы для изменения линейного порядка выполнения
действий в программе. Для этого место в программе, куда передается
управление (с которого продолжается выполнение программы), должно
быть помечено. Рассмотрим пример нахождения максимума среди чисел
без знака:
; максимум среди чисел X и Y → в ячейку Z
mov
ax,X; берем в AX значение числа из ячейки с именем X
cmp
ax,Y; сравнение — формирование флагов
jae
M; переход к метке М если >=
mov
ax,Y;
M: mov
z,ax

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

M1; продолжить с метки M1

Если требуется, например, в целях информационной безопасности
максимально затруднить понимание логики программы, например, при ее
дизассемблировании
злоумышленниками,
можно
насытить
ее
беспорядочными переходами с помощью jmp.
При исполнении команды вызова подпрограммы call происходит
следующее. В системный стек заносится текущее значение регистра —
счетчика команд процессора (IP — Instruction Pointer) и управление
передается по указанному в команде адресу (метке). По окончании
подпрограммы в ней должна встретиться команда ret, при выполнении
которой производится обратное действие — извлекается значение с
вершины стека и управление передается в вызвавшую программу:
; вызов подпрограммы pecat
call pecat
; сюда возвращается управление после исполнения подпрограммы
; …
; где-то в другом месте исходного текста
; подпрограмма печати — комментарий необходим
pecat:; … действия
; действия
ret ; возврат из подпрограммы

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

134

выполняемые ею действия.
Система команд процессоров x86 довольно богата — в ней имеются
специальные команды для организации циклов. Рассмотрим пример с
использованием команды loop. Пусть некий фрагмент программы нужно
повторить N раз. Реализовать это можно, например, следующим образом:
mov
cx,N; регистр CX — счетчик, аналог переменной цикла
L: ;начало тела цикла
;… действия цикла
;…
;…
dec
cmp
jne

cx; CX=CX-1
cx,0; CX=0?
L; CX еще не ноль — возврат к метке L

Как видите, в конце цикла используется стандартная тройка команд. Ее
можно заменить одной — loop! Переписать программу в этом случае
можно следующим образом:
mov
cx,N; регистр CX — счетчик, аналог переменной цикла
L: ;начало тела цикла
;… действия цикла
;…
;…
loop L; цикл, использует регистр CX по умолчанию

Видно, что современные ассемблеры и архитектуры ЭВМ предоставляют
довольно гибкие возможности — главное, умело ими пользоваться.
Контрольные вопросы
1. К какому поколению языков программирования относится ассемблер?
2. В чем разница между ассемблером и автокодом? Откуда произошло
название «автокод»?
3. Как вы оцениваете перспективы ассемблера в XXI веке?
4. Каковы области применения ассемблера в современных сложных
программных проектах?
5. Как работает команда xchg? Удобно ли использовать ее на ассемблере
и как она могла бы повлиять на языки программирования высокого
уровня?
6. В чем заключается разница между арифметическим и логическим
сдвигами?
7. Что такое машинное слово?

135

8. В чем заключается механизм работы индексной адресации?
9. Какие разновидности машинных команд существуют?
10.Как работают команды условного перехода? Зачем они нужны?
11.Для чего применяется команда loop?

Сумма нечетных на ассемблере
Приведенной ранее информации достаточно для того, чтобы приступить к
написанию программы суммирования нечетных элементов числовой
последовательности, проходящей красной нитью через настоящую книгу,
на языке ассемблера x86. Будем пользоваться бесплатно распространяемой
версией Flat Assembler. Рассмотрим возможный вариант решения:
; программа подсчета суммы нечетных в массиве chisla
include 'win32ax.inc'
.data
chisla dw 1,2,3,4,5,0,0,0,0,0
N
dw 10
.code
start:

; начальная метка программы, в конце должнj быть .end start
mov esi,chisla
mov cx,[N] ; количество элементов в таблице
mov dx,0 ; в dx будем накапливать сумму нечетных, сначала
обнуляем
l1:
mov ax,[esi]; очередное число заносим в АX
test ax,1 ; проверяем на нечетность – младший бит на 1
jz l2 ; если младший бит двоичного числа равен нулю –
четное!
add dx,ax ; прибавляем очередной нечетный элемент
l2:
add esi,2
loop l1 ; цикл по счетчику cx, пока не дойдет до нуля
; вызываем outint для вывода целого значения — результата
mov ax,dx
call outint
invoke ExitProcess,0

Данная программа предполагает, что у нас есть возможность вывода на
экран результата — мы формируем его в регистре процессора AX. Первая
строка — комментарий, который, как и положено, описывает суть нашей
программы. Строка с include нужна, чтобы мы смогли использовать в
программе системный вызов invoke ExitProcess,0 для корректного

136

завершения. Директива .data FlatAssembler указывает на начало сегмента
описания данных в программе, директива .code — начало исполняемого
блока команд.
В секции описания данных у
находится директива chisla dw
1,2,3,4,5,0,0,0,0,0, с помощью которой мы заносим в память
набор обрабатываемых чисел. В следующей строке — описание ячейки N,
содержащей размер массива, в нашем случае 10.
Правила FlatAssembler подразумевают, что начало исполняемой
программы снабжается меткой start (последней строчкой программы
должна в этом случае быть директива .end start). Итак, вначале в
регистр ESI заносится адрес начала обрабатываемого массива в памяти.
Регистр ESI — так называемая расширенная (32-разрядная) версия
регистра процессора SI, ее использование в данном случае обусловлено
использованием современного компьютера. В следующей строке заносим в
регистр CX, используемый как счетчик, количество чисел. Квадратные
скобки необходимы, чтобы указать на необходимость взять в качестве
аргумента число по адресу, а не сам адрес ячейки, — косвенную
адресацию. Затем мы обнуляем регистр DX — в нем будем накапливать
сумму нечетных чисел.
Со следующей строки начинается тело цикла, поэтому она имеет метку l1.
В цикле мы первым делом извлекаем из памяти по адресу, на который
указывает ESI, очередное число (косвенную адресацию дают квадратные
скобки) и заносим его в регистр AX. Проверка нечетности числа
осуществляется путем вполне уместного при программировании на
ассемблере использования низкоуровневых возможностей — команды
битового тестирования по маске test ax,1. Вспомним, что данные
хранятся в памяти ЭВМ в двоичном виде в позиционном коде. Младший
разряд числа отвечает при этом за степень 20 и равен нулю в случае, если
число делится без остатка на 2, и единице — в противном случае.
Соответственно, для проверки на нечетность нет необходимости
выполнять операцию деления на 2. Достаточно проверить содержимое
младшего бита (маска 1). Следующая команда условного перехода jz
обеспечивает переход к метке l2 в случае, если результат нулевой (число
четное), с помощью чего производится обход команд программы,
производящих суммирование.
Следующая операция, которая выполняется либо после суммирования
естественным путем, либо после перехода по команде jz l2, — переход к
следующему числу в памяти. Для этого мы увеличиваем на 2 значение
регистра ESI. Увеличение на 2 связано с тем, что мы храним
обрабатываемые числа в машинных словах, а минимальная единица

137

адресации процессора x86 — 1 байт. В случае если счетчик не дошел до
нуля, с помощью специальной команды цикла loop
выполняется
переход к повтору цикла с метки l1.
После выполнения программы сумма нечетных чисел будет накоплена в
регистре DX. Нам было бы интересно получить это значение на экране. К
сожалению, в ассемблере нет удобных средств, подобных writeln в
Паскале или cout > и >> d;

Здесь cin — наименование стандартного потока ввода, обычно связанного
с клавиатурой, cout — название стандартного потока вывода,
назначаемого обычно на экран дисплея; endl — обозначение символа
перевода строки. Для применения потокового ввода-вывода необходимо
подключить стандартную библиотеку с заголовочным файлом
iostream.h.
Еще одно весьма удобное изменение — разрешение объявлять переменные
в произвольном месте программы, а не только в начале тела функции или
вне функций для глобальных переменных. Популярной конструкцией при
программировании на С++ становится использование глубоко локальных
переменных, время жизни которых ограничивается, например,
исполнением конкретного оператора цикла, как в следующем примере:
for (int i=0;i