Программируй или будь запрограммирован.
— Дуглас Рашков
Определения оформляются представленным ниже способом. Курсивом указываются англоязычные эквиваленты определяемых терминов.
Алгоритм algorithm — точное предписание, задающее последовательность действий.
Работа заполняет время, отпущенное на неё.
— Первый закон Паркинсона
Курс состоит из недель, которые разбиваются на пары. За две недели следует выполнить одну лабораторную и одну самостоятельную работу. Последняя одна-две недели в конце семестра остаются для сдачи долгов. Теоретическая часть не связана строго с практической.
Тем, кто изучал Pascal, рекомендуется прочитать раздел Pascal vs. C++. Подраздел Прочие особенности C++ рекомендуется прочитать всем, но уже после начального ознакомления с C++.
При первом прочтении можно просто пропускать непонятные места. Основное внимание следует сосредоточить на изучении примеров и выполнении самостоятельных работ. В конце семестра и года рекомендуется просмотреть содержимое курса повторно и изучить ранее пропущенные места. Обычно это значительно помогает в усвоении материала. Ну а чтобы научиться программировать, нужно выполнять два основных действия: читать программы и писать программы. Полезно экспериментировать — если вас интересует как поведёт себя программа при выполнении какого-либо действия, попробуйте проверить практикой!
В целом, следующий совет подходит и к научным и техническим изданиям: при первом прочтении не следует останавливаться на непонятных вещах до конца раздела (здесь “раздел” = одна html-страница). Если после первого прочтения не всё ясно, следует прочитать повторно уже более внимательно, перечитывая сложные фрагменты повторно (иногда это действительно помогает). “Повторенье — мать ученья” — не просто рифма, а самая что ни на есть сермяжная правда.
Если возникли проблемы с пониманием примеров из самостоятельных работ, то следует найти последнее место, где “было понятно”, можно воспользоваться списком примеров и читать его с самого начала, остановившись на примере, в котором есть что-то непонятное. Этот пример следует изучить подробно, задать вопросы преподавателю. В случае разрешения трудностей продолжать до тех пор, пока не станут понятными примеры из самостоятельных работ.
В ряде мест встречаются упражнения, не являющиеся вариантами самостоятельных работ. Такие упражнения не являются обязательными для выполнения и не проверяются. Однако попытаться их стоит хотя бы для того, чтобы определить, понимаете ли вы материал или нет.
В примерах используются слова и фразы на английском языке. В случае, если какие-то использованные слова вам не знакомы, рекомендуется сразу смотреть их значения в словаре.
Замечания и дополнительная информация оформляются, как показано ниже.
Как изучать тот или иной пример?
Вначале следует прочитать его построчно. Убедиться, что содержание каждой строки вам понятно с точки зрения синтаксиса языка (если с синтаксисом вы уже знакомы достаточно хорошо, то этот этап можно пропустить).
Затем следует понять структуру программы: из каких частей она состоит, какой смысл выделения этих частей, каким образом они используются. Повторить для каждой составной части. Данное действие называется анализ.
Если отдельные действия понятны, но в целом алгоритм работы функции не ясен, попробовать выполнить его “в уме” или на бумаге.
При выполнении заданий следует вначале определить, представляете ли вы себе алгоритм решения задачи, который должен выполнить компьютер? Если есть затруднения, попробуйте взять пример и выполнить его на бумаге вместо компьютера, не забывая, что ему доступны только элементарные действия, вроде сравнения пары чисел или записи значения в ячейку памяти. Например, нельзя “охватить последовательность чисел взглядом и понять, что она не содержит последовательностей из двух и более нулей подряд”.
Выполнение действий на бумаге очень помогает на первых порах увидеть повторяющиеся действия и циклы. В конце концов, идея алгоритма может прийти как бы сама собой, главное — приложить усилие, вникнуть в задачу. После того, как понимание алгоритма обретено, можно приступать к “переводу” его на язык программирования, при этом необязательно писать текст программы “сверху вниз” — сразу подряд целиком. Можно выносить отдельные части в функции, которые заполнить уже “потом”, когда готова основная часть. Или наоборот, сначала описать набор некоторых элементарных с точки зрения алгоритма действий в виде отдельных функций, а затем собрать из них итоговую программу. Можно применять оба эти подхода в произвольной пропорции.
Одним из принципиальных требований к процессу программирования является регулярность в принятии решений, будь то какие-либо модели поведения или просто выбор названия: должны приниматься схожие решения в схожих ситуациях.
Пусть есть две функции: чтение данных и запись данных (здесь неважно, что это за “данные”, откуда они берутся и куда отправляются). Тогда пары названий
— плохие. Хорошие пары будут выглядеть так
Если в одном месте “data”, то и в другом месте то же самое — “data”. Если одна операция “write”, то противоположная операция — “read” (а не “load”, например). Не следует смешивать разные стили оформления названий в одной программе: либо “readInfo” и “writeInfo”, либо “read_info и write_info”.
Если используются математические объекты, следует по возможности придерживаться общепринятых обозначений и названий (их аналогов в “простом тексте”). Если это глобальные объекты, то сокращения следует заменять расшифровками.
Например, t — плохое название. Расшифровка temperature или time уже значительно лучше, но может быть недостаточной: обычно ещё желательно указать “чего температура” или “к какому событию относится момент времени”, скажем, boiler_max_temperature или last_frame_time.
Конечно, часто бывает просто лень изобретать или набирать длинные названия. Тем более для учебных примеров. Но если говорить о “реальном коде”, то, во-первых, его читают намного чаще, чем правят, и развёрнутые названия намного понятнее (особенно для других людей), во-вторых, при его создании собственно набирание текста занимает лишь малую долю общего времени.
Впрочем, короткие названия (в том числе однобуквенные) тоже имеют право на жизнь. Если их жизнь простирается лишь на небольшой фрагмент кода. При этом существуют широко применяемые обозначения, например: i, j, k — счётчики в циклах, n, m, sz (от size), len (от length) — размеры массивов, x, y, z, w (от width), h (от height), d (от distance) — геометрические координаты и размеры, t (от temporary) — временная переменная, p или ptr (от pointer) — указатель, p или pos (от position) — позиция в массиве или строке и т.д.
Естественно, всегда можно задать вопрос преподавателю. При этом желательно постараться предварительно как можно более сузить предмет вопроса, выяснить, что именно не понятно или вызывает сомнения.
Если вы чувствуете себя достаточно уверенно, то попробуйте найти в представленных примерах недочёты.
Слова программирование и программировать — производные слова программа, заимствованного в русский язык через французское programme (оттуда же английские programme и далее program), происходящее от латинского programma, заимствованного в свою очередь из древнегреческого πρόγραμμα “объявление, предписание, указ” — отглагольное существительное, складывающее приставку πρό- (“пред-”) и глагол γράφω (“пишу”).
Слово программа в значении “план деятельности” стало применяться (в том числе в русском языке) задолго до появления компьютеров и в близком значении вошло в математику.
Термин “язык программирования” может быть несколько обманчив в том плане, что слово “язык” здесь, скорее, следует понимать как “набор инструментов” или “строительных кубиков”, а не как сигнальную систему, предназначенную для передачи мыслей. Многие ограничения вносятся в языки намеренно с той целью, чтобы “направить” поток мысли программиста, помочь ему сконцентрироваться на определённом пути решения задачи.
Программы можно разделить на два основных класса:
Параллельных программ в данном курсе мы касаться не будем. Что же до последовательных программ (или просто “программ”), то для них предполагается наличие единственного исполнителя, способного за один шаг выполнить некоторое элементарное действие из конечного набора. Поэтому весь процесс выполнения программы можно записать в виде списка элементарных действий, выполненных строго по порядку. Основное отличие последовательной программы от параллельной — детерминизм: повторное исполнение последовательной программы при выполнении одних и тех же видимых программе условий на каждом шаге даёт один и тот же результирующий список шагов и конечный результат.
Есть исключение из данного правила: последовательная программа может использовать генератор истинно случайных чисел, что может приводить к потере детерминизма, так как последовательность чисел, выдаваемая таким генератором не предсказуема.
Согласно статье The camel has two humps для начинающих программистов существуют два первичных понятийных барьера, которые необходимо преодолеть (см. также Determining The Barriers Faced By Novice Programmer). Исходя из собственного опыта и особенностей использования языков C и C++, автор добавил ещё третий барьер:
Далее предполагается, что “компьютер” является разновидностью регистровой машины, что справедливо для современных конвенциональных цифровых компьютеров, архитектура которых наследует черты гарвардской и принстонской (“фоннеймановской”) архитектур. Но это не означает, что теоретически любой компьютер должен быть регистровой машиной.
Для одного — константа, а для другого — переменная.
Память компьютера можно представлять себе в виде таблицы из двух колонок — адреса и значения.
| Адрес | Значение |
|---|---|
| 0 | 100 |
| 1 | 50 |
| 2 | 201 |
| 3 | 45 |
Адрес — это просто выписанный и неизменный номер строчки (т.е. порядковый номер соответствующего значения). А вот значение — некоторое число, которое в процессе работы можно менять (но какое-то число там быть должно, ячейке запрещается быть пустой). Получается, что компьютеру доступны два элементарных действия:
Возможное множество значений, которые можно хранить в ячейке памяти в физических компьютерах, является конечным и обычно отождествляется с натуральным рядом от 0 до максимального значения (нам удобно считать 0 натуральным числом). Например, если наши ячейки имеют размер 1 байт, то они могут хранить значения от 0 до 255 включительно.
Но людям неудобно пользоваться числовыми адресами, тем более их пришлось бы распределять вручную, чтобы не было конфликтов между разными значениями, которые нужно хранить в памяти одновременно. Поэтому языки программирования позволяют давать ячейкам (или группам ячеек ввиду ограниченности одной ячейки) имена, которые затем автоматически подменяются на адреса, которые опять же автоматически выделяются так, чтобы не было конфликтов.
Эти именованные ячейки называются переменными variables, так как хранимые в них значения можно менять в процессе выполнения программы (посредством операции store). Операция изменения значения переменной на заданное (где вместо адреса используется символическое имя) называется присваивание assignment. Можно представлять себе это так — таблица с адресами ячеек подменяется таблицей с именами ячеек, в которой нет неименованных ячеек (нас не интересует состояние всей памяти, а лишь только переменных, которые мы в ней разместили).
| Имя | Значение |
|---|---|
| width | 100 |
| height | 50 |
| length | 201 |
| mass | 45 |
Предположим, в этот робот встроили некоторый прибор массой 15 кг (для этого использовали внутренний отсек, поэтому габариты не поменялись). Чтобы отразить сей факт в нашей памяти, нам надо добавить 15 к текущей массе. Для этого надо загрузить из памяти значение переменной mass, добавить к нему 15 и записать обратно в ячейку, отвечающую имени mass — выполнить присваивание mass = mass + 15. Несмотря на использование символа “=” (синтаксис языка C), это не запись логического утверждения или алгебраического уравнения, а приказ на изменение значения переменной.
| Имя | Значение |
|---|---|
| width | 100 |
| height | 50 |
| length | 201 |
| mass | 60 |
Пусть мы назначили ячейки памяти под номерами 0–3 для хранения значений переменных width, height, length и mass. При включении компьютера память может быть заполнена случайными величинами. Она не содержит осмысленных значений. Поэтому, чтобы получить осмысленное, например представленное на таблице состояние, необходимо перед использованием переменных их инициализировать.
Инициализация — присваивание переменной начального значения.
Инициализация может выглядеть как набор обычных присваиваний.
width = 100;
height = 50;
length = 201;
mass = 45;В приведённом выше примере инициализации переменных нам не важен порядок выполнения этих присваиваний, так как они никак не зависят друг от друга и используют только заранее заданные константы и разные ячейки памяти. Поэтому, в частности, их можно было бы выполнять даже одновременно (параллельно).
Однако, часто очень важно соблюдать строгий порядок выполнения действий. Например, программа, позволяющая роботу пройти из оранжевого кружка к синему в лабиринте, изображённом ниже, могла бы выглядеть примерно так:
Эту последовательность нужно выполнять в строгом порядке, иначе пройти по маршруту не получится. Подобная прямая последовательность действий является типичной для последовательных программ.
Предположим, что робот может перемещаться на дистанции, указанные с точностью до 10 см. Тогда один байт может хранить дистанцию до 25.5 м. Далее, предположим, что робот может поворачиваться с точностью до 1°, тогда разворот налево или направо возможен до 255°, хотя разумным будет ограничиться 180°. Наконец, пронумеруем действия, доступные роботу.
Теперь каждую команду в программе можно записать (“закодировать”) с помощью одного-двух байт: условного номера команды и аргумента x — конкретного значения. Команда с кодом 0 аргумента не имеет и записывается одним байтом. Запишем программу, представленную выше, в таком виде в память, начиная с нулевого адреса:
| Адрес | Значение |
|---|---|
| 0 | 1 |
| 1 | 40 |
| 2 | 3 |
| 3 | 90 |
| 4 | 1 |
| 5 | 90 |
| 6 | 2 |
| 7 | 90 |
| 8 | 1 |
| 9 | 110 |
| 10 | 2 |
| 11 | 90 |
| 12 | 1 |
| 13 | 90 |
| 14 | 3 |
| 15 | 90 |
| 16 | 1 |
| 17 | 40 |
| 18 | 0 |
Этот способ записи фактически представляет собой “машинный код” — язык, понятный “машине” (компьютеру) непосредственно. Но он не очень-то удобен для человека. Поэтому, как только появились полноценные компьютеры, появились и буквенные обозначения команд (“мнемонические”, т.е. удобные для запоминания) и способы записи программ, хотя и взаимно-однозначно сопоставимые с машинным кодом, но всё же значительно более удобные для людей — “ассемблерные языки”.
| Код | Мнемоника | Смысл |
|---|---|---|
| 0 | halt | останов |
| 1 | move | вперёд |
| 2 | left | налево |
| 3 | right | направо |
| Адрес | Код | Мнемоника |
|---|---|---|
| 0 | 1, 40 | move 40 |
| 2 | 3, 90 | right 90 |
| 4 | 1, 90 | move 90 |
| 6 | 2, 90 | left 90 |
| 8 | 1, 110 | move 110 |
| 10 | 2, 90 | left 90 |
| 12 | 1, 90 | move 90 |
| 14 | 3, 90 | right 90 |
| 16 | 1, 40 | move 40 |
| 18 | 0 | halt |
Наш робот способен исполнять наперёд заданные жёстко зафиксированные последовательности команд. В этом плане он не сильно отличается от музыкальной шкатулки XVII века или жаккардова ткацкого станка, позволявшего задавать узор с помощью перфокарт, начала XIX века.
Предположим, что требуется так запрограммировать робота, чтобы он мог по некоторому указанию выбирать один из трёх маршрутов. Этим указанием может быть значение в заданной ячейке памяти, которую мы будем обозначать переменной target (она должна содержать значения 1, 2 или 3). Пока не будем беспокоиться о том, каким образом данная переменная инициализирована.
Итак, перепишем текстовую программу из предыдущего пункта, дополнив её условными переходами.
Чтобы закодировать её в машинном коде, надо придумать код для команды “если переменная x равна y, то перейти к исполнению команд с адреса z”. Это сложная команда — сразу три операнда. Назначим ей незанятый пока код 4 и мнемонику beq (“branch if equal”) и в трёх последующих байтах разместим значения x (адрес ячейки памяти, где хранится значение интересующей нас переменной), y (числовая константа) и z (адрес ячейки памяти, в которой находится код команды, на которую надо перейти в случае истинности условия).
Переменную target разместим в ячейке с адресом 255.
| Адрес | Код | Мнемоника |
|---|---|---|
| 0 | 1, 40 | move 40 |
| 2 | 3, 90 | right 90 |
| 4 | 1, 45 | move 45 |
| 6 | 4, 255, 3, 29 | beq target, 3, 29 |
| 10 | 1, 45 | move 45 |
| 12 | 2, 90 | left 90 |
| 14 | 1, 110 | move 110 |
| 16 | 4, 255, 2, 34 | beq target, 2, 34 |
| 20 | 2, 90 | left 90 |
| 22 | 1, 90 | move 90 |
| 24 | 3, 90 | right 90 |
| 26 | 1, 40 | move 40 |
| 28 | 0 | halt |
| 29 | 2, 90 | left 90 |
| 31 | 1, 70 | move 70 |
| 33 | 0 | halt |
| 34 | 3, 90 | right 90 |
| 36 | 1, 40 | move 40 |
| 38 | 2, 90 | left 90 |
| 40 | 1, 50 | move 50 |
| 42 | 0 | halt |
Так как структура организации альтернативных веток через переходы неудобна для людей и легко приводит к ошибкам, языки программирования, как правило, предоставляют более естественную для человека схему “если условие то последовательность действий иначе альтернативная последовательность действий”, которая уже затем переводится в линейную последовательность с переходами вроде представленной выше, удобную для машины.
Данная схема элементарным образом обобщается на выбор из произвольного количества альтернатив простым вложением (“каскад если”):
Выполняется последовательность действий с минимальным номером i таким, что условие i истинно. Если же ни одно из условий 1, 2, …, N не истинно, то выполняется альтернативная последовательность действий. Большинство языков позволяют её не указывать, что эквивалентно пустой последовательности (т.е. не содержащей ни одного действия).
Перепишем программу в таком высокоуровневом стиле. Номера действий опустим, так как мы всё равно не хотим их использовать для переходов.
Слово итерация происходит от латинского iteratio — “повторение” от itero — “повторяю”, наречия iterum — “опять, снова, вторично, повторно”.
Слово цикл заимствовано в русский через западноевропейские языки из позднелатинского cyclus, которое в свою очередь заимствовано из древнегреческого κύκλος — “круг, кольцо, колесо”, на общеиндоевропейском уровне родственного русскому слову колесо и английскому слову wheel. То же самое можно сказать про английское cycle (через французский), однако термин “цикл” в программировании на английский переводится как loop, т.е. буквально “петля”.
Цикл — последовательность действий, которая в процессе выполнения программы потенциально может быть выполнена неоднократно.
Итерация — одно повторение цикла. Таким образом, во время выполнения программы цикл разворачивается в последовательность итераций, действия в которых повторяются с точностью до значений переменных и выбранных веток вложенных альтернатив.
Нередко слово итерация используется как синоним слова цикл (т.е. буквально “повторение” как процесс).
Для иллюстрации простого цикла представим, что мы хотим запрограммировать робота на бесконечное (пока не сядет аккумулятор, например, или его не выключат извне) курсирование между пунктами 1 и 2. Для простоты предположим, что на момент запуска программы робот пришёл в пункт 1, т.е. ориентирован в сторону тупика, и его требуется предварительно развернуть.
Признаком цикла является переход (условный или безусловный) “назад”, например, здесь — с п.13 на п.1. В данном случае цикл — вся программа целиком. Причём это вечный цикл, он продолжается сколь угодно долго, в программе нет условий для его прекращения (переходов изнутри цикла за его пределы).
Если вечный цикл возник случайно по ошибке программиста, то результатом может быть “зависание” программы.
Для выявления циклов достаточно попробовать выполнить желаемые действия (хотя бы в уме представить порядок их выполнения для получения желаемого результата) и обратить внимание на повторение групп одних и тех же действий. Если их можно описать словами “повторять последовательность действий”, “повторить n раз последовательность действий”, “для элементов некоторого множества выполнить последовательность действий” — в частности, “перебирая целые числа i от n до m, выполнить последовательность действий с параметром i”, наконец, “повторять последовательность действий, каждый раз проверяя некоторое условие прекращения”, то обнаружен цикл, который следует оформить подходящей конструкцией используемого языка программирования.
Слово рекурсия происходит от латинского отглагольного существительного recursio “возврат” от recurro “возвращаюсь” от re- (приставка со значением обращения или повторения действия) и curro “бегу, двигаюсь”.
Рекурсивное определение — определение, ссылающееся на себя само.
Рекурсивная функция — функция, при вычислении которой может использоваться значение этой же функции, но от других параметров.
Рассмотрим простой пример. Пусть есть стопка журналов, отсортированных по номеру. Требуется найти журнал с заданным номером. Например, №16.
Простым решением будет перебирать журналы по порядку, но это может быть весьма времязатратно, если стопка велика. Вместо перебора подряд, воспользуемся тем фактом, что журналы отсортированы. Возьмём, и снимем сразу половину стопки.
Верхний журнал имеет номер больше 16. Значит, искомый журнал может быть в нижней половине. Снова снимем половину стопки.
Опять верхний журнал имеет номер больше 16. (Да, это 17, поэтому человеку разумнее просто посмотреть сразу под ним.) Снимем половину стопки.
Оставшиеся один-два журнала можно проверить простым перебором. К сожалению, 16-го номера среди них не оказалось. Но таким же образом мы могли искать №17, тогда бы мы его обнаружили на предыдущем шаге, при сравнении номера журнала, находящегося наверху очередной половины с искомым.
Приведённый пример — пример типично рекурсивного алгоритма, называемого двоичный поиск. Двоичный поиск применим к отсортированным последовательностям и позволяет найти элемент (или убедиться в его отсутствии) не более чем за 2⌈log2 n⌉ сравнений (n — размер исходной последовательности).
Двоичный поиск между элементами a и b (последовательность упорядочена по возрастанию):
Для того чтобы рекурсивная функция была вычислима на практике, необходимо выполнение двух условий:
Итак, можно разбить множество P в объединение непересекающихся множеств P0, P1, P2, … таким образом, что при рекурсивных вызовах происходит “движение” в сторону уменьшения номеров.
Рекурсивный метод доказательства называется математической индукцией. Он предполагает движение в обратном направлении. Предположим, что необходимо доказать некое утверждение C как истинное для любого параметра p из множества P. Для этого достаточно доказать три связанных утверждения:
П.1 называется базой индукции, а комбинация пп.2 и 3 — шагом индукции.
Таким образом рекурсивное определение алгоритма может быть “переведено” в доказательство его корректности. В качестве примера можно взять всё тот же двоичный поиск.
Теорема (корректность алгоритма двоичного поиска). Пусть на множестве X задан линейный порядок. Пусть дана последовательность { xi } ⊆ X, i = 1, 2, …, N, дан искомый элемент x ∈ X и выполнены следующие условия
Тогда двоичный поиск найдёт на { xi } элемент x.
Формулировка алгоритма двоичного поиска, используемая в доказательстве.
Доказательство
База индукции. Пусть j – 1 ≤ a ≤ b ≤ j, либо j ≤ a ≤ b ≤ j + 1, тогда на шаге 1 имеем проверку элементов a и b (не более двух) и обнаружение xj (по условию 1).
Шаг индукции. Пусть m = ⌊(a + b)/2⌋ ≠ a. В случае j = m алгоритм находит элемент на шаге 2.3. Далее полагаем, что xm не эквивалентен xj (иначе просто положим j = m).
Предположим, что если a ≤ j < m или если m < j ≤ b, то алгоритм находит искомый элемент.
Если j < m, то xj < xm (из неэквивалентности и условия 2), следовательно, на шаге 2.2 переходим к поиску на диапазоне a–m и по предположению индукции находим элемент.
Если m < j, то xm < xm, следовательно, на шаге 2.1 переходим к поиску на диапазоне (m+1)–b и по предположению индукции находим элемент.
Из линейной упорядоченности множества X следует, что других вариантов нет.
Итак, положим a = 1, b = N, по условию теоремы a ≤ j ≤ b, следовательно, по индукции двоичный поиск найдёт элемент j. □
Рекурсию часто удобно применять для компактного описания алгоритмов. Чтобы понять, есть ли рекурсивный алгоритм решения некоторой задачи, следует вообразить, что такой алгоритм уже есть и попробовать выразить решение задачи через комбинацию решений подзадач из того же класса.
С теоретической точки зрения итерация и рекурсия эквивалентны — одно можно выразить через другое и наоборот. С практической точки зрения рекурсивные описания часто намного компактнее итеративных, но их реальное вычисление может обходиться дороже.
Любая проблема в компьютерных науках может быть решена добавлением ещё одного уровня косвенности.
Кроме проблемы слишком большого количества уровней косвенности.
Ранее мы уже использовали адреса ячеек памяти (которые отождествлялись с именами переменных) и команд (для организации переходов). Достаточно естественной представляется возможность интерпретировать значение ячейки памяти как адрес другой ячейки памяти. В конце концов, адрес — просто целое число.
Переменная, значением которой является адрес, называется указателем pointer.
Разыменованием указателя pointer dereferencing называют обращение к значению по адресу, хранимому указателем.
Указатель добавляет уровень косвенности и позволяет через одну переменную (себя) получить доступ к любой другой (если изменять записанный в него адрес).
Предположим, наш робот несёт на себе прибор, измеряющий текущий уровень радиации. Мы отправили его измерять радиацию в точках 1 и 2 — каждый раз, приходя в пункт 1 и пункт 2, робот должен записывать в свою память следующее измерение.
Последние сто замеров будут хранится в ячейках с адресами 100–199. Очередной замер будет сохраняться в переменную rads. Переменная pos будет играть роль указателя на текущую ячейку для записи следующего замера.
Упражнение. Попробуйте расширить систему машинных команд таким образом, чтобы приведённую только что программу можно было закодировать аналогично тому, как это делалось ранее. Закодируйте её.
В отличие от языка C большинство языков программирования не позволяют оперировать адресами непосредственно. Однако C изначально предназначен для выполнения в том числе и подобных низкоуровневых действий, так что “указатели” поддерживаются непосредственно в качестве типа данных.
Программа, приведённая выше, на языке C могла бы выглядеть следующим образом (при условии размещения данного кода в надлежащем контексте). Ключевое слово char вводит переменную, значение которой описывается одним байтом. Конструкция char* вводит переменную-указатель на байт. За размещение этих переменных в памяти отвечает компилятор.
char rads;
char *pos = (char*)100; // приведение типа: число -> указатель (адрес)
for (;;) // вечный цикл
{
rads = radiation();
*pos = rads; // * выполняет разыменование указателя
pos = pos + 1;
left(180);
move(40);
left(90);
move(130);
left(90);
move(50);
rads = radiation();
*pos = rads;
pos = pos + 1;
if (pos == (char*)200)
pos = (char*)100;
right(180);
move(50);
right(90);
move(130);
right(90);
move(40);
}Вообще, с точки зрения синтаксиса C, подражающая машинному коду конструкция
rads = radiation();
*pos = rads;
pos = pos + 1;избыточна и может быть заменена на одну строчку (типичный оборот для программ на C), переменную rads можно убрать:
*pos++ = radiation(); // ++ увеличивает pos на 1 после разыменованияВпрочем, в данном примере использование указателя относится к распространённому классу операций — действий с массивами. В C указатель может служить адресом начала непрерывной последовательности ячеек (массива), к которой можно обращаться по целочисленному индексу, что выглядит естественней и понятней для человека. Поэтому программу можно переписать следующим образом.
char i = 0; // i -- индекс в массиве
char *base = (char*)100; // адрес массива -- "база"
// base + i -- это то, что раньше было pos
for (;;) // вечный цикл
{
// обратимся к элементу i массива по адресу base
base[i++] = radiation(); // base[i] -- то же, что *(base + i)
left(180);
move(40);
left(90);
move(130);
left(90);
move(50);
base[i++] = radiation();
if (i == 100)
i = 0;
right(180);
move(50);
right(90);
move(130);
right(90);
move(40);
}Упражнение (сложное). Попробуйте придумать осмысленный пример, где нужен указатель, хранящий адрес другого указателя, т.е. “указатель на указатель”.
В 1964 году MIT, General Electric и Bell Labs начали разработку операционной системы (ОС) MULTICS (“Multiplexed Information and Computing Service”). Данная ОС предполагала множество новаций: два основных понятия файл (именованная единица данных) и процесс (выполняемая программа с выделенными ей ресурсами системы), динамически загружаемые библиотеки, использование в качестве основного языка программирования языка высокого уровня — нового тогда PL/I, амбициозного проекта действительно универсального языка программирования на базе языка Algol. В разработке MULTICS принимали участие Кен Томпсон и Деннис Ритчи, впоследствии (1968–1973) на основе переработки опыта MULTICS создавшие ОС Unix и язык программирования C.
Язык низкого уровня low-level language — язык, программа на котором, представленная на подходящем носителе данных в соответствующем формате, может быть выполнена некоторым физическим компьютером (процессором) непосредственно. Языки низкого уровня привязаны к конкретным семействам процессоров.
В целом, “низкоуровневыми” называют те программы или фрагменты программ, которые требуют переписывания при переносе программы на другую “платформу” (т. е. комбинацию ОС и архитектуры процессора).
Языки низкого уровня могут использоваться для создания программ для виртуальных машин virtual machine, VM вместо физических процессоров. Можно считать, что виртуальная машина — это программа, которая имитирует некий процессор. Виртуальная машина может сама задавать стандарт языка низкого уровня, например, Java VM исполняет “байт-код” Java, изначально предназначенный как для виртуальных машин, так и для аппаратных “Java-процессоров”.
Если же имитируется реальный процессор, не совместимый с физическим процессором, на котором выполняется виртуальная машина, то такую машину часто называют эмулятором (например, эмулятор игровой системы Sony PlayStation, позволяющий запускать игры для неё на ПК на основе процессора семейства x86 под управлением ОС Windows), а процесс исполнения программ для имитируемого процессора — эмуляцией.
Существует множество различных технологий и вариаций виртуальных машин, описывать которые здесь не представляется разумным. В итоге затруднительно дать действительно строгое определение, позволяющее разделить языки на уровни. Впрочем, такая ситуация — обычное дело, когда приходится классифицировать с реальные, а не абстрактные (умозрительные) объекты. Развитие и взаимопроникновение технологий смешивает разные понятия и размывает их смысл.
Язык высокого уровня high-level language, HLL — язык, не привязанный к конкретной машине-исполнителю. Программа на языке высокого уровня не может быть выполнена компьютером непосредственно и требует перевода в язык низкого уровня.
Язык высокого уровня не привязан к какому-либо семейству процессоров и допускает перенос программы с платформы на платформу с минимальными изменениями или вообще без изменений (кроссплатформенность).
Теоретически возможно создать процессор, способный исполнять программу на произвольном языке высокого уровня непосредственно, но с практической точки зрения это очень неразумное мероприятие, так как такой процессор будет не только очень сложным, но и, скорее всего, очень медленным по сравнению с “обычными” процессорами.
Исторически существовали компьютерные системы, созданные под конкретный язык высокого уровня (Algol, Lisp, Lingo, Java) и оптимизированные для выполнения программ на объектно-ориентированных языках со сборкой мусора (проект Intel iAPX 432). Однако ни одна из этих архитектур не исполняла код на HLL непосредственно, предоставляя вместо этого специальный язык низкого уровня, “подогнанный” под конкретный HLL. Кроме того, ни одна из архитектур данного направления не получила широкого распространения. Впрочем, процессоры семейства ARM могут содержать средства для ускорения исполнения байт-кода Java, вплоть до прямого его выполнения физическим процессором (байт-кода Java, а не самого Java).
В настоящее время можно встретить новые архитектуры процессоров (точнее, микроконтроллеров), “оптимизированные для языка C”. Это означает, что архитектура команд данного процессора (понимаемый им язык низкого уровня) разрабатывалась с учётом особенностей языка C и с целью как упрощения компилятора C, так и увеличения эффективности получаемых программ. В целом, эти архитектуры имеют достаточно традиционные черты (что также связано с историей и минимализмом языка C).
Операционная система (ОС) — комплекс ПО, служащий связующим звеном между прикладным ПО, решающим конкретные прикладные задачи и аппаратным обеспечением (напрямую или посредством отдельных программ — драйверов устройств). ОС могут включать ПО, предназначенное для обслуживания компьютера и решения задач хранения и передачи информации — утилиты utilities.
Операционные системы, драйверы устройств, утилиты, трансляторы, компоновщики, отладчики, а также определённые классы промежуточного ПО (например, драйверы баз данных и сетевых протоколов) называют системным ПО.
Промежуточное ПО middleware — программы, предназначенные для использования другими программами, вплоть до включения в их состав (библиотеки).
Язык системного программирования application programming language — язык, предназначенный для написания системного ПО.
Язык прикладного программирования system programming language — язык, предназначенный для написания прикладного ПО. Применение этого термина предполагает, что данный язык программирования жертвует какими-то средствами “низкого уровня”, как-то ограничивает программиста, либо не позволяет достичь максимального быстродействия программы, но зато упрощает решение прикладных задач, предоставляет программисту более богатый или более защищённый от ошибок арсенал встроенных средств.
Универсальный язык программирования universal programming language — язык, предназначенный как для системного программирования, так и для прикладного программирования, не содержащий в себе намеренно заложенных особенностей, ограничивающих сферу применения.
Предметно-ориентированный язык domain-specific language, DSL — язык, оперирующий терминами некоторой специальной ограниченной предметной области, предназначенный для решения узкого класса задач (т. е. изначально не универсальный).
Предметно-ориентированный язык может вовсе не быть языком программирования в традиционном смысле, т. е. не быть способным задать произвольные вычисления. В то же время, некоторые DSL вышли за рамки собственно DSL и могут считаться универсальными языками программирования, например JavaScript (язык сценариев Web-страниц) и Wolfram (язык пакета Mathematica).
Примеры DSL: SQL (системы управления базами данных), bash (командная строка), TeX (описание текстовых документов), PostScript (описание печатных документов), Verilog (описание и моделирование электронных схем), Modelica (моделирование систем с непрерывной динамикой или смешанного характера), MATLAB (математические пакеты).
Упрощая, можно сказать, что C был создан для того, чтобы не переписывать Unix на ассемблере для каждой новой машины (первые версии этой ОС были созданы на ассемблере для миникомпьютеров PDP-7 и PDP-11). Язык C изначально создавался как компилируемый в обычный машинный код язык, в то время как прямой предок C — язык B, созданный Томпсоном на основе BCPL, транслировался в “шитый код”.
В итоге, язык C стал самым известным и влиятельным языком системного программирования, широко распространившись вместе с вариантами ОС Unix. Из-за его приближенности к машине, нередко о C говорят как о языке низкого уровня, “переносимом ассемблере” portable assembly. Кроме того, C нередко используется вместо машинного кода как целевой язык компиляторов языков более высокого уровня (так было с C++, Eiffel, Modula-3 и многими другими).
В 1979 г. во время подготовки докторской диссертации Бьерн Страуструп использовал интерпретируемый язык Simula для моделирования работы распределённой ОС. Язык Simula изначально был создан для задач имитационного моделирования и представлял собой вариант Algol с дополнительными конструкциями, которые дали начало объектно-ориентированному программированию. К сожалению, реализация Simula плохо масштабировалась, приводя к неприемлемым потерям времени при исполнении программы. Попытка переписать код на языке C привела к появлению языка C with Classes, дополненного некоторыми конструкциями из Simula, код на котором транслировался в C. Как потом Страуструп написал в своей книге “Язык программирования C++”: “Язык C++ был разработан, в первую очередь, для того, чтобы моим друзьям и мне не приходилось программировать на ассемблере, C и различных современных языках высокого уровня”.
Альтернативным C++ вариантом подмешивания черт объектно-ориентированного программирования (позаимствованных из Smalltalk) в язык C стал язык Objective-C (1983), в последние годы обретший второе дыхание с ростом популярности платформ компании Apple, на которых он традиционно используется.
Естественно, после этого мир не замер на месте. Появившийся в 1995 язык Java разрабатывался отчасти с целью замещения C++ как языка прикладного программирования. Появились новые ниши для интерпретируемых языков. Классический “язык сценариев” Perl (1987) популярен в качестве средства для написания обслуживающих скриптов в тех случаях, когда интерпретатор командной строки не подходит. Языки для описания логики веб-сайтов: на стороне сервера — PHP (1995), на стороне клиента (браузера) — JavaScript (1995) (все эти языки имеют C-подобный синтаксис, хотя Perl его значительно расширяет).
Язык сверхвысокого уровня very high-level language, VHLL — язык, требующий для исполнения своих программ специальную виртуальную машину.
Язык C# (2000) многими считается своего рода улучшенным Java от Microsoft. Язык Go от Google (2009) создавался как “улучшенный C” (намеренно лишён ряда “сложных элементов”).
Ближе всего к нише C++ (как инфраструктурного языка широкого профиля, компилируемого в машинный код) находятся языки D (2001), Rust (2012) и Swift (2014).
Семейство языков программирования, наследующих элементы синтаксиса языка C, называют Curly Brace-языки (от англ. curly brace — “фигурная скобка”).
Руководящие принципы, выдвинутые комитетом стандартизации языка C при ISO (цит. по книге “Язык программирования C” С.Праты — см. список лит.):
Характеристика C++ от автора языка (цит. по книге “Язык программирования C++” Б.Страуструпа — см. список лит., подробнее там же):
Наконец, ещё два принципа развития языка C++:
Языки C и C++ относятся к небольшой группе языков программирования, стандартизуемых ISO. Относительно регулярно выходят новые версии стандартов. Изданные стандарты кратко обозначают комбинацией названия языка и двух последних цифр года принятия стандарта. Группа по стандартизации ISO C++ WG21 публикует рассматриваемые черновики изменений, дополнений и новых стандартов (также см. isocpp.org). Окончательные стандарты ISO не являются общедоступными документами, но таковыми являются все черновые версии и описания предложений, правок и дополнений.
Уровень поддержки того или иного стандарта зависит от версий используемого компилятора и прилагающейся к нему Стандартной библиотеки (которую, как правило, можно заменить на другую).
Существенную роль в развитии стандарта C++ играет набор библиотек Boost, некоторые части которого вошли в стандарт C++11, а некоторые, возможно, будут приняты в состав стандартной библиотеки в следующих редакциях.
Язык C
Язык C++
Полная поддержка C++17 декларируется компиляторами g++ (из набора GCC), начиная с версии 7.1 (полная поддержка Стандартной библиотеки C++17 с версии 8), Clang, начиная с версии 5 (ряд средств Стандартной библиотеки не реализованы), Microsoft Visual C++ 2017 (v.15.7). Подробную таблицу поддержки компиляторами элементов разных стандартов C++ можно найти здесь.
C++17, как новейший действующий стандарт C++ на данный момент, является “целевым” для настоящего курса. Однако о сколько-нибудь близком к 100% покрытии говорить не приходится — его объём слишком велик для двухсеместрового курса. Кроме того, с практической точки зрения важнее формирование “ядра” знаний, умений и навыков, а не изучение множества деталей конкретной технологии, которые с годами меняются и обновляются.
Минимальная программа на C++, которую можно собрать и запустить, но которая, естественно, ничего не делает, выглядит следующим образом (это содержимое .cpp-файла, заодно показан синтаксис комментариев):
// Это однострочный комментарий.
/* Это многострочный комментарий.
Наша программа ничего не делает.
*/
int main()
{
}Теперь приведём минимальную программу в духе helloworld, которая выводит текстовое сообщение:
// Подключить стандартные потоки текстового ввода-вывода.
#include <iostream>
int main()
{
std::cout << "Hello, user!";
}Те, кто уже знаком с синтаксисом C++, могут обратить внимание на то, что main — это функция, возвращающая целое число (об этом говорит ключевое слово int перед именем функции). Однако в приведённом примере ничто не указывает на наличие некоего возвращаемого результата, что может вызвать обоснованные сомнения в корректности предложенного кода. Впрочем, main — особая функция. С неё начинается выполнение программы, и выход из этой функции означает завершение программы. Значение, которое она возвращает, передаётся операционной системе и интерпретируется как код ошибки (подробнее здесь). И main — единственная функция в C++, которой разрешено не возвращать значение явно. Однако правилом хорошего тона считается возвращать “код ошибки”, даже если он никак программой не используется.
// Подключить стандартные потоки текстового ввода-вывода.
#include <iostream>
int main()
{
std::cout << "Hello, user!";
return 0; // Возвратим ОС "код результата работы".
}Код 0 традиционно используется как “код отсутствия ошибок”, в то время как ненулевые значения считаются кодами некоторых ошибок (общего стандарта на них не существует). Для сигнализации отсутствия ошибки также определённая в заголовочном файле cstdlib стандартная константа EXIT_SUCCESS (для наличия ошибки без уточнения её типа — EXIT_FAILURE), поэтому приведённый выше код можно переписать несколько яснее следующим образом (хотя многие программисты могут посчитать это своего рода “пижонством”)
#include <iostream>
#include <cstdlib>
int main()
{
std::cout << "Hello, user!";
return EXIT_SUCCESS; // Возвратим ОС "код успеха".
}Более сложные примеры программ приводятся в теоретической части курса и в примерах решений заданий самостоятельных работ. Также см. листинги здесь.
Не следует забывать, что C и C++ — разные языки, стандартизуемые разными группами ISO. Благодаря значительной “обратной” совместимости C++ по отношению к предыдущим вариантам C, большую часть C можно использовать без изменений, поэтому нередко говорят “си” или используют обозначение C/C++, подразумевая использование элементов C++ в произвольной пропорции с общим подмножеством C и C++.
Стандартные заголовочные файлы, с помощью которых производится подключение библиотек в C++ разбиты на три группы:
В программах на C++ вместо стандартных заголовочных файлов C рекомендуется использовать их C++-обёртки. Иногда они содержат расширенный функционал, например, перегружают имена функций для разных типов параметров, что удобно в использовании, но недоступно в C, который не поддерживает перегрузку функций. Например, в C++ можно использовать функцию std::abs для вычисления модуля числа произвольного подходящего встроенного типа (и результат будет того же типа, что и аргумент), в то время как в C следует выбирать вариант abs в зависимости от типа аргумента: abs для int, labs для long, llabs для long long, fabs для double, fabsf для float или fabsl для long double.
Кувшинов Д.Р. © 2015