Основы программирования

Основы программирования

2-е издание, исправленное

Мейер Б.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Основы программирования/ Б. Мейер - М.: Национальный Открытый Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2011-2016
(c) Мейер Б., 2011-2016

3

Введение

У слушателей Интернет университета появилась уникальная возможность не только
пройти курсы лекций по замечательной книге “Почувствуй класс. Учимся
программировать хорошо с объектами и контрактами”, но и увидеть, услышать автора
книги – профессора Бертрана Мейера. Отвечая на вопросы профессора Владимира
Биллига – переводчика книги, Бертран Мейер объясняет, почему этот курс может быть
интересен студентам, приступающим к изучению информатики, чем книга может быть
интересна преподавателям, читающим подобный курс, чем книга и курсы по ней могут
быть интересны профессионалам ИТ. Он рассказывает о том, как учат информатике в
ЕТН – одном из старейших учебных заведений Европы, об особенностях этого курса. В
беседе затрагиваются и другие вопросы, в частности Бертран говорит о своей любви к
русскому языку и о том, как он, будучи школьником, учил русский язык. Эта лекция
является хорошим введением в курс, полученным “из первых уст”.

Доступные ресурсы

“Почувствуй класс” основан (на момент публикации оригинала книги) на шестилетнем
опыте преподавания курса “Введение в программирование” в ETH (Цюрих), который
читается всем студентам, поступающим на отделение информатики (computer science).
Параллельно с созданием курса и книги разработан большой объем учебных
материалов. Приветствуется использование этих материалов при обучении студентов.
На сайте, посвященном курсу и книге: ссылка: http://touch.ethz.ch можно найти ссылки
на:

полный набор слайдов к курсу (PowerPoint + PDF) в его последней версии;
доступные для загрузки видеозаписи лекций;
дополнительные материалы;
упражнения;
слайды для практических занятий (учебные пособия);
страницу Wiki для преподавателей, использующих эту книгу в качестве учебника;
доступную для загрузки программную систему “Traffic” (Windows, Linux…);
опубликованные статьи и отчеты о нашей учебной деятельности, которая связана с
курсом и другими работами, ведущимися на факультете, включая разработку
основ курса TrucStudio;
информацию о курсах в других университетах, применяющих эту книгу как
учебник;
список опечаток;
уголок преподавателей (требуется регистрация) — активных членов сообщества,
обменивающихся опытом работы.

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

Большинство материалов, в частности, слайды и видеозаписи, сделаны на английском.
Доступна также версия упражнений и слайдов на немецком языке. Мы надеемся на

4

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

Добро пожаловать в наше сообщество!

Посвящение

Эта книга посвящена двум пионерам информатики в знак благодарности за их
неоценимое влияние и блестящее понимание сути вещей:

Энтони Хоару (C.A.R. Hoare) — по случаю его 75-летия и Никласу Вирту (N. Wirth) —
с особой благодарностью за его вклад в становление информатики в ETH.

Предисловие редактора перевода

Так учат в ETH

Швейцарское федеральное высшее техническое училище — ETH (Eidgenossische
Technische Hochschule) входит в пятерку лучших университетов Европы. Для
программистов ETH славен тем, что именно здесь Никлас Вирт создал знаменитую
серию языков программирования — Algol-W, Pascal, Modula, Oberon. Язык Pascal
воплотил идеи структурного программирования и структурных типов данных, став
де-факто языком, на котором в большинстве университетов учили программированию
в течение десятилетий.

Последние 8 лет кафедру Вирта Software Engineering возглавляет профессор Бертран
Мейер (по правилам Швейцарии профессор Вирт после 65 лет не занимает
административных постов, оставаясь почетным профессором и научным
консультантом университета). Меняются персоналии, но традиция остается, и эта
кафедра ETH по-прежнему остается центром, генерирующим новые идеи, как в
программировании, так и в обучении программированию.

Перед нами фундаментальный труд профессора Бертрана Мейера, создававшийся в
течение 6 лет преподавания в ETH. Книга, рассказывающая о том, чему и как учат
программистов в ETH, интересна, полезна, необходима всем, кто учит и учится
программированию. Это первый и очевидный круг читателей книги.

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

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

5

Известная книга Кнута называется “Искусство программирования”, книга Гриса —
“Наука программирования”, книга Соммервилла — “Инженерия программного
обеспечения”. Википедия утверждает, что программирование содержит все эти части
— науку, искусство и инженерию.

Книга Бертрана Мейера “Почувствуй класс” дает нам прекрасный пример сочетания
этих разных сторон программирования. Здесь есть хорошая математика, например,
приводятся разные варианты доказательства фундаментальной теоремы “о
неразрешимости проблемы остановки”. Глава 15, посвященная разработке алгоритма и
программы топологической сортировки, — это образец искусства программирования.
Рефрен всей книги — инженерия программ. Автор стремится с первых шагов учить
профессиональному стилю программирования, ориентированному на создание
программных продуктов высокого качества, создаваемого из повторно используемых
компонентов, имеющих долгую жизнь.

И при обучении, и в реальной работе крайне важно и крайне сложно соблюсти баланс
между этими гранями программирования. Принципиальное решение этой проблемы
дает использование контрактов при проектировании и разработке программной
системы. “Проектирование по контракту” — это главный вклад профессора Бертрана
Мейера в современное программирование.

Бертран Мейер — автор языка Eiffel и научный руководитель созданной им фирмы
Eiffel Software, успешно работающей многие годы, реализовавшей многие крупные
проекты в различных областях — здравоохранении, банковском секторе, обороне.
Бертран Мейер не без основания полагает, что объектно-ориентированный язык Eiffel
является лучшим языком как для целей обучения, так и для разработки серьезных
промышленных проектов. Понятно, что язык Eiffel и среда разработки Eiffel Studio
стали тем рабочим окружением, на базе которого строится обучение в ETH.

Несколько важных принципов положено в основу обучения:

Начинать учить нужно сразу объектно-ориентированному программированию.
С первых шагов студенты должны работать в мощной программной среде с
множеством классов, создавая из готовых компонентов эффективные приложения
с графическим интерфейсом (студентам ETH предоставляется специальная
система Traffic, а также все библиотеки, используемые в Eiffel Studio).Такой
подход называется “обращенным учебным планом”.
Для работы в такой среде достаточно знания интерфейсов, построенных на
контрактах. У студентов с самого начала вырабатывается понимание важности
спецификации разрабатываемого ПО. Код всего программного обеспечения,
предоставляемого студентам, открыт, что позволяет перейти на нужном этапе от
понимания интерфейса к пониманию реализации. Такой подход называется “извне
— внутрь”.

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

6

Не хочу выступать в роли апологета Eiffel и призывать всех завтра же учить так, как
учат в ETH сегодня (полагаю, что найдутся те, кто, прочитав эту книгу, решится на
такой шаг).

Но вот что совершенно бесспорно. Опыт обучения программированию в ETH нельзя не
учитывать. В первую очередь это касается контрактов. Они должны появляться с
первых программ, написанных студентами, они должны быть неотъемлемой частью
профессионально разрабатываемого ПО. Хороший курс обучения программированию,
так же, как и курс, реализованный в ETH, должен включать все грани
программирования — науку, искусство и инженерию.

Я уже говорил, что признанных учебников по программированию, используемых в
разных университетах, до сих пор нет. Книга “Почувствуй класс. Учимся
программировать хорошо с объектами и контрактами” — один из претендентов на эту
роль.

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

В заключение несколько слов о профессоре Бертране Мейере. Вот что говорится о нем
в Википедии: “Бертран Мейер является одним из ведущих ученых в области
инженерии программного обеспечения. Он автор девяти книг. Им опубликовано более
250 научных работ, охватывающих широкий спектр направлений, все из которых
трудно перечислить. Вот лишь некоторые из них: методы построения надежных,
повторно используемых компонентов и программных продуктов, параллельное,
распределенное и интернет-программирование, технологии баз данных, формальные
методы и доказательство корректности программ”.

Он хорошо известен российским программистам. Почетный доктор СПбГУ ИТМО. Из
9 его книг это — третья книга, переведенная на русский язык. Первая книга, “Методы
программирования”, появилась еще в 1982 году под редакцией Андрея Петровича
Ершова. Перевод второй его книги, “Объектно-ориентированное конструирование
программных систем”, называемой без преувеличения библией “объектноориентированного программирования“, вышел в 2005 году с большим запозданием по
отношению к первому изданию оригинала книги. Оригинал данной книги, “Touch of
Class. Learning to Program Well with Objects and Contracts” вышел в 2009 году, так что
запаздывание с переводом не столь велико.

Бертран Мейер знает русский язык, в молодые годы проходил стажировку у А. П.
Ершова в Академгородке, где была написана одна из первых его статей. Довольно
часто приезжает в Россию, выступает на конференциях. Последняя организованная им
международная конференция по программной инженерии — SEAFOOD 2010 —
проходила в июне 2010 года в Санкт-Петербургском государственном университете.

Нельзя не отметить стиль, в котором написана эта книга. Как и все книги Бертрана

7

Мейера, она интересна своим широким культурным контекстом. Символично то, что
на обложке оригинала книги “Touch of Class” помещена картина Рафаэля “Академия
Платона”, в центре которой Платон, беседующий с учениками.

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

 
Во всем мне хочется дойти 
    До самой сути.
В работе, в поисках пути,
    В сердечной смуте. 
    
До сущности протекших дней,
    До их причины,
До оснований, до корней,
    До сердцевины. 

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

Надеюсь, что читатели новой книги Бертрана Мейера получат наслаждение от
понимания того, как программировать хорошо с объектами и контрактами.

Владимир Биллиг

Предисловие автора к русскому изданию

Книга “Почувствуй класс” представляет новый подход в обучении началам
программирования — подход, доказавший на практике свою успешность и
применяемый в ETH Цюрих вот уже восьмой год.

Книга написана в первую очередь для тех студентов, кто выбрал информатику
(computer science) своей специальностью, и использовалась не только в ETH, но и в
других университетах. Лекторы, желающие применить книгу при обучении, могут
найти много полезных ресурсов (слайды презентаций, упражнения, видеозаписи
лекций, список опечаток, форум для преподавателей и прочее), регулярно
обновляемых на сайте ссылка: http://touch.ethz.ch.

Публикация английского издания показала, что многие другие читатели, включая
инженеров и менеджеров, работающих в индустрии, находят полезным “Почувствуй
класс”, открывая для себя источники новых идей современного программирования.

8

Еще одна категория читателей — специалисты в дисциплинах, отличных от
информатики, стремящиеся понять основы концепции программирования, не
ограничиваясь техническими деталями.

Сегодня нельзя учить программированию так, как учили нас и многие поколения
программистов (в деталях это обсуждается в основном предисловии к книге). Причина
не только в том, что изменилось программирование, которое стало столь вездесущим, и
не только в том, что программы стали столь сложными, но и в том, что изменились
студенты. Сегодня на начальный курс редко приходят студенты, вовсе не знакомые с
программированием. Из них примерно 85% уже имеют программистский опыт, и
примерно 15% уже создавали довольно большие программы. Что же они ожидают от
университетского курса, и что мы должны дать им? Как сказано в заглавии книги,
нужно учить их программировать хорошо. Этим они будут отличаться от миллионов
людей, знакомых с программированием, но не являющихся профессионалами высокого
уровня. Цель этой книги — направить читателей по пути, ведущему к становлению
профессионалов.

“Почувствуй класс” покрывает широкий спектр тем, часть из которых — довольно
продвинутые и обычно не включаются в начальный курс. Наш подход к обучению
“извне — внутрь”, подробно описанный в большом предисловии, основан на свободно
распространяемой библиотеке классов Traffic, специально построенной для этих целей.
Он позволяет читателям учиться на примерах и одновременно является источником
вдохновения для собственных разработок. Полагаю, что это лучший способ стать
первоклассным программистом. Я настоятельно рекомендую преподавателям,
использующим книгу при обучении, давать студентам упражнения, применяя Traffic и
другое ПО с открытым кодом, поддерживающее этот курс.

“Почувствуй класс” имеет четкую ориентацию на практику работы, но равновесно
содержит серьезный теоретический материал, включающий логические утверждения,
сложность алгоритмов, лямбда-исчисление. Центральной темой, объединяющей
процесс обучения, является тема “Проектирования по Контракту”. Это единственный
путь, насколько я знаю, создавать высококачественное ПО, функционирующее
корректно, устойчиво и безопасно. Не следует откладывать изучение этих методов на
будущее в углубленных курсах по программированию. Они могут применяться всеми
программистами для любых приложений, и умение ими пользоваться — еще один
пример того, что отличает профессионала от любителя.

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

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

9

Мне особенно приятно, что перевод этой книги сделан профессором Владимиром
Биллигом. Его предыдущий перевод моей книги “Объектно-ориентированное
конструирование программных систем” (Русская Редакция, 2000) заслужил много
комплиментов за стиль и высокое качество. Владимир Биллиг многократно помогал
мне, когда я готовил доклады на русском языке и выступал с ними в России. Те же
навыки и талант он продемонстрировал и при переводе “Почувствуй класс”
(обнаружив в процессе перевода ряд опечаток в английской версии, которые
скорректированы в русском издании). Благодаря его интенсивной работе русская
версия появляется практически вслед за английским изданием. Я благодарен
профессору Биллигу за сотрудничество, продолжающееся уже многие годы.

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

Бертран Мейер,

Цюрих, декабрь 2010

Предисловия

note
  description: "[
    В этой книге два предисловия: одно для преподавателей, другое – для
    студентов, что отражено ниже в непривычной, но корректно используемой
    нашей собственной нотации, применяемой при записи программ. 
         ]"
class PREFACING inherit
  KIND_OF_READER
create
  choose
feature — Инициализация
  choose
      — Выбрать предисловие, предназначенное для вас.
    do
      if is_student then
        student_preface.read
      elseif is_instructor then
        instructor_preface.read
      else
        pick_one_or_both
      end
        check
          — Вы узнаете о динамическом связывании.
        note
          why: "Вы сумеете выразить все элегантнее!"
        end
    end

10