Три богатыря на рубеже столетий. Основы программирования. Алгоритмы, структуры данных и программирование

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

Почти одновременно с появлением первых ЭВМ системные программисты стремились переложить на плечи ЭВМ наиболее рутинную работу, сопровождавшуюся многочисленными ошибками и описками. Первые элементы автоматизации процесса написания программ были связаны с заменой числовых кодов машинных операций их мнемоническими символьными обозначениями. Например, команда сложения содержимого двух ячеек памяти вместо сугубо числового кода 01 0100 0101 0102 превращалась в более осмысленное действие типа ADD 0100,0101,0102. Почти сразу же стало ясно, что использование естественной числовой нумерации ячеек памяти становится неразумной преградой между обозначениями переменных решаемой задачи и их эквивалентами в виде числовых адресов. Почему бы не возложить на специальную программу чисто механическую работу по замене символьных обозначений исходных и промежуточных данных задачи на их машинные адреса? И тогда очередной пункт алгоритма, выражавшийся простой формулой z = х + у, превращался в достаточно наглядную и близкую по смыслу команду ADD X,Y,Z. На первом этапе развитие этих идей сдерживало отсутствие устройств ввода/вывода, которые могли бы обрабатывать алфавитно-цифровую информацию. Как только аппаратные средства позволили преодолеть это препятствие, неотъемлемой частью программного обеспечения ЭВМ стали системы, получившие название Автокодов или Ассемблеров.

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

К числу первых алгоритмических языков, получивших достаточно широкое распространение, относятся Фортран (FORTRAN — от FORmula TRANslation, "трансляция формул") и Алгол (ALGOL — от ALGOrthmic Language, "алгоритмический язык"). Первый из них родился в недрах фирмы IBM в 1954 г. и активно поддерживался этим наиболее могущественным концерном по производству средств вычислительной техники. В нашей стране он стал широко известен в связи с переходом на выпуск ЭВМ Единой Системы (ЕС ЭВМ), программно совместимых с ранее появившимися моделями IBM/360, IBM/370. История развития Фортрана насчитывает довольно много версий и диалектов, среди которых наиболее известны Fortran-II, Fortran-IV, Fortran-77 и Fortran-90.

Алгол-60 появился как противовес Фортрану в результате объединенных усилий европейских ученых, представлявших, по большей части, академическую и вузовскую науку. Первые сведения о нем были опубликованы в 1958 г., но как стандарт языка он был утвержден в 1960 г. Алгол получил довольно широкое признание в нашей стране. Для него отечественными учеными были разработаны несколько систем программирования — ТА-1М (Вычислительный центр фирмы С. П. Королева), ТА-2М (Институт прикладной математики АН СССР), Альфа (Вычислительный центр СО АН СССР). Однако следующий стандарт языка Алгол-68 практически остался академическим проектом и большого распространения не получил, т. к. в срочном порядке был вытеснен Фортраном.

Несмотря на совершенно разную структуру и наличие несоизмеримых по финансовой мощи спонсоров, оба языка оказали существенное влияние на последующее развитие систем программирования. Так, например, язык Бейсик многое заимствовал из Фортрана, тогда как Паскаль продолжил линию алголоподобных языков. Несколько особняком стоит язык Си, впитавший в себя элементы как низкоуровневого программирования (наследие от языков типа Ассемблер), так и типы данных и синтаксические конструкции алгоритмических языков высокого уровня. Он не только объединил эти две кажущиеся противоположными компоненты, но и внес значительный вклад в развитие объектно-ориентированного программирования.

Далеко немногие алгоритмические языки выдержали испытание временем. Однако языки Бейсик, Си и Паскаль, включенные в нашу книгу, сродни трем былинным богатырям. Их возраст либо приближается к заветному сказочному рубежу в 33 года, либо уже превысил его, что мы и постарались отметить в названии первой главы. На сегодняшний день они являются наиболее популярными как у начинающих, так и у профессиональных программистов.

Самый почтенный среди них — Бейсик, днем рождения которого считается 1 мая 1964 г. В этот день в Дартмутском колледже (США) проявил первые признаки жизни интерпретатор, созданный студенческим коллективом во главе с профессорами Джоном Кемени (J. G. Kemeny) и Томасом Куртцем (Т. Е. Kurtz). Своим названием BASIC обязан сокращению фразы Beginner's All-purpose Symbolic Instruction Code, которая дословно переводится как "многоцелевой код (язык) символических инструкций для начинающих".

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

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

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

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

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

Аналогичная программа на Паскале содержит, минимум, три строки, а ее длина превышает 20 символов:

Примерно вдвое большего по числу символов требует ее аналог на Си:

Становлению и распространению Бейсика в нашей стране способствовали первые в мире пошаговые компиляторы с этого языка, созданные в 1969 г. для отечественных ЭВМ типа М-20 в Горьковском университете под руководством одного из авторов этой книги.

Второе поколение Бейсик-систем ведет свой отсчет от появления первых ПК на базе 8-разрядных микропроцессоров Intel-8080 и Z-80, для которых в середине 70-х годов был разработан компактный интерпретатор BASIC-80. Именно с него началась карьера самого молодого американского миллиардера Билла Гейтса, основавшего корпорацию Microsoft.

Появление 16-разрядных IBM-совместимых ПК ознаменовалось конкурентной борьбой между компаниями Borland International и Microsoft Corp. Первая из них выпустила на рынок удобную интегрированную среду с компилятором Turbo BASIC, которая быстро привлекла на свою сторону многочисленных любителей Бейсика. Однако более мощная компания, постоянный президент которой не упускает случая прибавить к своей профессии приставку "программист Бейсика", не могла смириться с таким положением. На смену тихоходному интерпретатору GW-BASIC пришла целая серия скоростных систем Quick BASIC, в составе которых наряду с интегрированной средой поставлялись автономные компиляторы и достаточно мощные библиотеки программ. Соревнование Бейсик-систем третьего поколения закончилось поражением фирмы Borland, прекратившей сопровождение своей разработки и передавшей права на Turbo BASIC одному из авторов, вышедшему из состава компании. Одна из последующих его разработок известна под названием Power Basic (Мощный Бейсик).

А фирма Microsoft совершенствовала свое любимое детище и выпустила в конце 80-х годов мощные системы для профессиональных разработок (Professional Development System) BASIC PDS-6 и PDS-7.

Авторы языка Кемени и Куртц спустя 25 лет попытались разработать новую версию под названием True Basic (Истинный Бейсик), однако из-за отсутствия серьезной поддержки со стороны крупных производителей программного обеспечения эта попытка, кроме издания книги и выпуска пробной версии системы, продолжения не получила.

Наконец, четвертое поколение Бейсика мы связываем с появлением в 1991 г. системы визуального программирования Visual Basic и ее последующим совершенствованием сотрудниками Microsoft. На момент выпуска нашей книги в эксплуатации находится версия VB-6.0. До версии 3.0 включительно Visual Basic был построен по схеме интерпретатора, однако последние его версии позволяют получать готовые к исполнению модули. Кроме полноценной системы программирования, фирма Microsoft с 1993 г. выпускает версии YBA (Visual Basic for Application -- система для разработки программируемых процедур в пакете MS Office) и VBScript (ограниченная версия для разработки Web-приложений).

Алгоритмический язык Паскаль был придуман в 1968 г. профессором Института информатики при Швейцарской высшей технической школе Ник-лаусом Виртом. В 1970 г. под его руководством был разработан первый компилятор, а в следующем году появилась и первая публикация. Свое название язык получил в честь известного французского математика Блеза Паскаля, который в 19-летнем возрасте изобрел первую суммирующую машину.

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

Заметную роль в разработке стандарта языка Паскаль и совершенствовании его средств ввода/вывода сыграла рабочая группа Британского института стандартов во главе с А. Эддиманом. Британский стандарт был принят в 1982 г., а несколько позднее его утвердила международная организация ISO. Однако к этому времени Н. Вирт, недовольный предложениями рабочей группы, отказался от сотрудничества по совершенствованию Паскаля и переключился на новый проект Модула.

Паскаль довольно долго оставался средством для изучения программирования в университетах, т. к. ни одна серьезная компьютерная фирма его не поддерживала. Перелом в отношении к этому языку наметился в 1984 г., когда молодой француз Филипп Кан привез в США необычайно скоростной компилятор Turbo Pascal для IBM-совместимых ПК и начал торговать им по смехотворно низкой цене 49 долларов 95 центов (для сравнения напомним, что первые версии Бейсик-интепретатора распространялись по цене порядка 500 долларов). Удачная реклама и бросовая цена позволили Кану продать за первый месяц более 3000 копий системы и заложить основы фирмы Borland International. Последующие восемь лет Turbo Pascal оставался наиболее опекаемым продуктом фирмы, которая сумела выпустить девять различных версий. Самая последняя из них (7.0, 1992 г.) включает две системы — Turbo Pascal, функционирующую под управлением MS-DOS, и расширенную версию Borland Pascal, работающую в среде Windows. Несмотря на то, что в январе 1995 г. Ф. Кан покинул пост президента и ушел из компании, фирма Borland на базе языка Object Pascal выпустила одну из наиболее популярных сред визуального программирования — Delphi и продолжает поддерживать ее версии в современных операционных системах. На сегодня наибольшей популярностью пользуется версия Delphi 5.O.

Язык Си был придуман в 1972 г. сотрудником Bell Laboratories (отделение известной телефонной компании AT&T) Деннисом Ритчи, одним из первых пользователей операционной системы Unix. Задумывался он не как универсальный алгоритмический язык, а, скорее, как инструмент для развития операционной системы и создания новых обслуживающих программ (утилит). Такой подход характерен для большинства системных программистов, разрабатывающих сложные проекты и придумывающих для облегчения своего труда различные сервисные процедуры, макрокоманды и т. п. По завершении разработки, как правило, эти инструментальные наборы предаются забвению или, в лучшем случае, остаются в личных архивах авторов. Язык Си эта участь миновала. Вполне возможно, что его становлению способствовало последующее всемирное признание операционной системы Unix.

Как алгоритмический язык сравнительно низкого уровня, т. е. достаточно близкий к Ассемблеру, Си имел предшественников в лице аналогичных инструментальных средств — языков CPL, BCPL (Basic Combined Programming Language — базовый комбинированный язык программирования) и В. Два первых разрабатывались в конце 70-х годов в Кембриджском университете в качестве машинно-независимых языков для создания трансляторов. Последний был придуман Кеном Томпсоном — сотрудником Bell Laboratories и автором операционной системы Unix. В отличие от своих предшественников Д. Ритчи наряду с машинно-ориентированными типами данных (байт, слово) ввел в состав Си объекты и операторы, присущие универсальным языкам (числовые и символьные переменные, структурные блоки), сохранив при этом элементы, характерные для макроассемблера MACRO-11 (логические операции над битами, сдвиги, работа с адресами и регистрами).

Первым программным продуктом, написанным почти полностью на Си, был компилятор с языка Си в код машинных команд компьютера PDP-11/20 (прототип мини-ЭВМ СМ-4). В 1973 г. Д. Ритчи и К. Томпсон переписали на Си большую часть операционной системы Unix. Из 13 000 машинных команд для PDP-7, на которой появилась первая версия Unix, только 800 пришлось вручную перевести в ассемблер PDP-11. В процессе перевода Unix из однопользовательской операционной системы, ориентированной на работу в конкретной ЭВМ, превратилась в мобильную операционную систему коллективного пользования. Успех этой операции в значительной мере предопределил популярность новой операционной системы и ее базового инструмента — языка Си. В 1976 г. Д. Ритчи и К. Томпсон перенесли Unix с ЭВМ фирмы DEC на компьютеры другой архитектуры (Interdata 8/32), практически ничего не изменив в ядре операционной системы, написанном на Си. Точно таким же образом система Unix распространялась на десятки машин различных типов.

В 1978 г. появилась первая книга, посвященная описанию Си и технике Программирования на этом языке, которая с большим запозданием была переведена на русский язык (Б. Керниган, Д. Ритчи, Л. Фьюэр. "Язык программирования Си. Задачи на языке Си". — М.: Финансы и статистика, 1985). От фамилий двух первых авторов произошло сокращенное обозначение первого, никем не утверждавшегося, но принятого всеми программистами стандарта языка Си — K&R.

Дальнейшая работа по совершенствованию языка Си и принятию в 1987 г. первого настоящего стандарта ANSI С была выполнена на общественных началах рабочей группой при Американском национальном институте стандартов. Возглавлял эту работу Лэрри Рослер — сотрудник Bell Labs. Наиболее серьезный вклад в развитие языка Си за последние годы внес еще один представитель той же лаборатории Бьерн Страуструп, который ввел в обращение новые объекты — классы, объединяющие данные, и обрабатывающие их функции. С 1983 г. за расширенной версией языка Си с классами закрепилось название C++.

Первые версии Си подвергались серьезной критике за отсутствие достаточной строгости, приводившей к многочисленным ошибкам из-за работы с неинициализированными переменными, отсутствия контроля за выходом индексов у элементов массивов из установленных пределов, несоответствия типов формальных и фактических параметров функций и т. п. Перед системными программистами Bell Labs эти проблемы остро не стояли, т. к. они пользовались специальной программой Lint, которая проводила тщательный анализ программ, написанных на Си, перед их трансляцией и выполнением.

Для рядовых пользователей ситуация изменилась с появлением интегрированных сред, из которых наибольшую популярность приобрели Турбо-системы фирмы Borland. Первая версия Turbo С, работавшая в среде MS-DOS, была выпущена в 1987 г. Совсем недавно фирма Borland выпустила на рынок версию 5.0, предназначенную для работы под управлением Windows. На базе этого компилятора компания Borland (новое название — Inprise Corp.) разработала серию систем визуального программирования — Borland C++ Builder.

Известны и другие реализации языка Си на IBM-совместимых ПК -Microsoft С, Lattice С, Zortech С, Symantec С. В нашей стране продукция фирмы Borland получила наибольшее распространение, хотя за последнее время намечается тенденция к более широкому использованию среды Visual C++, разработанной фирмой Microsoft. В основном, это диктуется требованиями зарубежных фирм, размещающих свои заказы у отечественных производителей программных продуктов.

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

Бейсик — один из наиболее распространенных в мире алгоритмических языков, используемых, как правило, непрофессиональными программистами. По данным из пяти миллионов программирующих пользователей ЭВМ Бейсиком пользуется не менее двух миллионов человек. Большая часть учащихся средних школ начинает освоение информатики с изучения Бейсика, т. к. он доступен на самой допотопной вычислительной технике, которой, к сожалению, еще до сих пор укомплектовано большинство школ России. Несмотря на то, что Бейсик является старожилом по сравнению с Си и Паскалем, в последние годы он переживает вторую молодость в связи с появлением модных систем визуального программирования и массовым использованием Microsoft Office.

Паскаль —алгоритмический язык, созданный специально для изучения программирования и широко используемый в высших учебных заведениях. Вслед за Бейсиком он тоже вступил на тропу визуального программирования, и система Delphi считается одним из лучших инструментальных средств для создания приложений, функционирующих под управлением Windows 95/98/NT.

Си —язык профессионалов, на котором сегодня написано большинство программных систем. Большая часть высших учебных заведений, особенно технического профиля, использует Си в качестве основного языка преподавания программирования. Такие среды визуального программирования, как Borland C++ Builder и Microsoft Visual C++ являются несомненными лидерами в разработках современного программного обеспечения.

В связи с тем, что книга ориентирована на начальное знакомство с перечисленными алгоритмическими языками, в качестве сред программирования нами выбраны самые непритязательные по требованиям к оборудованию системы — QBasic, Turbo С 2.0 или Borland C++ 3.1 и Turbo Pascal 7.0. Все они могут функционировать на самых примитивных IBM-совместимых ПК с оперативной памятью от 1 Мб, занимая на винчестере от 1 до 25 Мб. Кроме того, система QBasic является составной частью операционной системы MS-DOS и представлена там всего двумя небольшими файлами — интерпретатором qbasic.eхe и файлом помощи qbasic.hlp.

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

Практика программирования на 3GL

Три богатыря на рубеже столетий