Пратт Т. Языки программирования. Разработка и реализация

Подождите немного. Документ загружается.

Глава 1. Проблемы

разработки языка

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

данных, можно назвать языком программирования; в настоящей книге, однако, речь

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

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

мы обсудим в следующих двух главах. Остальные главы посвящены подробному

описанию разработки и реализации различных компонентов языка. Нашей зада

чей является рассмотрение основных языковых концепций, общих для всех без

исключения языков программирования, и иллюстрирование их примерами из ши

рокого спектра наиболее распространенных языков.

В этой книге мы будем изучать применение этих языковых концепций на при

мере двенадцати основных языков программирования: Ada, C, C++, FORTRAN,

Java, LISP, ML, Pascal, Perl, Postscript, Prolog и Smalltalk. Кроме того, вкратце мы

рассмотрим и некоторые другие языки, оказавшие влияние на интересующую нас

область человеческой деятельности. Среди них APL, BASIC, COBOL, Forth, PL/1

и SNOBOL4. Однако, прежде чем приступать к изучению языков программирова

ния с общих позиций, следует разобраться, какую пользу это может принести про

граммисту.

1.1. Зачем изучать языки

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

К настоящему моменту разработаны и реализованы сотни языков программирова

ния. Еще в 1969 г. Саммет (Sammet) [95] привел список из 120 достаточно широко

используемых в то время языков, и с тех пор их число значительно возросло. Од

нако большинство программистов пользуются всего несколькими языками, мно

гие же вообще ограничиваются всего одним или двумя. Обычно программисты

работают с вычислительными системами, на которых используется какойлибо

один определенный язык: Java, C или Ada. Какую же пользу может получить про

граммист от изучения множества различных языков, которыми едва ли станет

пользоваться?

На самом деле это имеет смысл, если вы не ограничитесь только поверхност

ным рассмотрением возможностей языка, а постараетесь постичь его концепции

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

главных мотивов:

1. Вы сможете разрабатывать более эффективные алгоритмы. Многие языки

предоставляют возможности, которые при правильном использовании при

носят программисту пользу, а при неправильном могут привести к большим

затратам компьютерного времени или к логическим ошибкам в программе,

на исправление которых потребуется немало сил и времени. Даже програм

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

может не понимать всех его возможностей. Типичным примером является

рекурсия — полезное средство программирования, которое при правильном

использовании позволяет осуществлять непосредственную реализацию эле

гантных и эффективных алгоритмов. Однако неправильное ее использова

ние может привести к катастрофическому увеличению времени выполне

ния программы. Программист, ничего не знающий о проблемах разработки

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

ной конструкции, в то время как элементарное знание ее основных принци

пов и методов реализации позволит программисту оценить относительную

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

ли ее применение в конкретной ситуации. В литературе постоянно появля

ются описания новых методов программирования. Для наилучшего исполь

зования концепций объектноориентированного, логического или парал

лельного программирования необходимо понимание конкретных языков,

в которых эти концепции реализованы. Новые технологии, такие как Ин

тернет (Internet) и Всемирная паутина (World Wide Web), в корне измени

ли природу программирования. Создание методов программирования, опти

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

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

2. Вы сможете более эффективно использовать тот язык программирования,

которым обычно пользуетесь. Поняв, как в используемом вами языке реали

зованы те или иные возможности, вы сможете писать значительно более

эффективные программы. Например, понимание того, как создаются масси

вы, строки, списки или записи и как они обрабатываются в данном языке,

знание подробностей реализации рекурсии или понимание того, как строят

ся классы объектов, позволит вам создавать с помощью этих компонентов

более эффективные программы.

3. Вы пополните набор полезных программных конструкций. Роль языка в мыш

лении двояка, так как язык одновременно и помогает мышлению, и ограни

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

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

мыслить о чемто, что не имеет непосредственного словесного выражения.

Знание только одного языка программирования налагает подобное ограни

чение. При поиске способов представления данных и методов их обработки,

подходящих для решения некоторой задачи, человек думает только о струк

турах, которые непосредственно реализованы в знакомом ему языке. Изу

чая конструкции, имеющиеся в разных языках, программист расширяет свой

словарь. Понимание способов реализации конструкций в разных языках

особенно важно, поскольку, чтобы использовать некую конструкцию в язы

ке, в котором она не представлена непосредственно, программист должен

1.1. Зачем изучать языки программирования?

18 Глава 1. Проблемы разработки языка

осуществить ее реализацию в терминах базовых элементов этого языка. На

пример, структура управления подпрограммами (subprogram control struc

ture), известная как сопрограмма, полезна во многих случаях, но только не

многие языки предоставляют ее непосредственную реализацию. Однако

программисты, пишущие на языках C или FORTRAN, если они знакомы

с концепцией сопрограммы и методами ее реализации, могут легко спроек

тировать программу, в которой используется сопрограмма, а затем реализо

вать ее на C или FORTRAN.

4. Вы сможете выбрать язык программирования, наиболее подходящий для

реализации конкретного проекта. Таким образом уменьшается объем необ

ходимых работ. Приложения, в которых выполняется большой объем чи

сленных расчетов, могут быть легко разработаны на таких языках, как C,

FORTRAN или Ada. Приложения, используемые для принятия решений,

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

на языках LISP, ML или Prolog. Для Интернетприложений больше подхо

дят Perl или Java. Знание основных особенностей языка, его достоинств и не

достатков дает программисту более широкие возможности выбора.

5. Вам будет легче изучать новые языки. Лингвист, глубоко понимающий струк

туры, лежащие в основе естественных языков, может выучить новый иност

ранный язык легче и быстрее, чем начинающий, который плохо представля

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

конструкций и способов реализации ряда языков программирования позво

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

6. Вам будет легче разрабатывать новые языки. Большинство программистов

даже и не помышляют о разработке нового языка программирования, хотя

создаваемые ими приложения в действительности являются некоторой фор

мой языков программирования. Разработчики пользовательского интерфей

са для большой программы, такой как, например, текстовый редактор, опе

рационная система или графический пакет, неизбежно сталкиваются со

многими из тех проблем, которые встречаются и при разработке языков про

граммирования общего назначения. Многие новые языки основаны на моде

лях реализации языков C или Pascal. Подобный аспект разработки программ

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

ных конструкций и способами реализации обычных языков программиро

вания.

Изучение языков программирования есть нечто большее, нежели просто бег

лое знакомство с их возможностями. В действительности сходство возможностей

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

реализованы совершенно разными способами, и, таким образом, эти две версии

могут очень сильно различаться по стоимости использования. Например, почти в

каждом языке операция сложения реализована как одна из основных операций, но

в различных языках, например в C, COBOL или Smalltalk, стоимость операции

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

В данной книге рассматривается множество языковых конструкций, которые

почти всегда сопровождаются одним или несколькими примерами их реализа

ции на стандартном компьютере. Однако мы не пытались полностью осветить

все возможные способы реализации. Те же самые языки или языковые конст

рукции при реализации на компьютере читателя могут радикально отличаться

по стоимости или по деталям структуры, если используются разные методы реа

лизации или если архитектура компьютера отличается от простой стандартной

архитектуры.

1.2. Краткая история

языков программирования

С тех пор как в 50е гг. появились первые языки программирования высокого уров

ня, методы их разработки и реализации постоянно развиваются. Те 12 языков, ко

торые описаны в данной книге, появились в разное время: первые версии

FORTRAN и LISP были разработаны в 50е гг., история языков Ada, C, Pascal, Prolog

и Smalltalk начинается в 70х гг., в 80е возникли такие языки, как С++, ML, Perl,

Postscript, а язык Java — самый молодой, он появился в 90х. В 60е и 70е гг. новые

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

ного обеспечения как их составная часть. Когда в 70е гг. Министерством обороны

США в рамках основного проекта разработки языка Ada был составлен отчет об

используемых в то время языках программирования, выяснилось, что в различ

ных оборонных проектах было использовано более 500 языков.

1.2.1. Разработка первых языков

В этом разделе мы в общих чертах опишем языки, разработанные в начале компью

терной эры, начиная с середины 50х по 70е гг. Более поздние разработки будут

подробно освещены по мере рассмотрения в книге новых языков.

Языки численных расчетов. Первый этап развития компьютерных техноло

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

до начала 40х. Во время Второй мировой войны основной задачей компьютеров,

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

баллистических траекторий путем решения дифференциальных уравнений дви

жения.

В начале 50х начали появляться первые языки, использовавшие символьные

системы обозначений. Грейс Хупер (Grace Hooper) возглавил в компании Univac

группу, которая разрабатывала язык A0, а Джон Бэкус (John Backus) создал язык

Speedcoding для IBM 701. Оба эти языка предназначались для преобразования

простых арифметических выражений в исполняемый машинный код.

Настоящий прорыв произошел в 1957 г., когда Бэкус руководил группой по

созданию языка FORTRAN, или транслятора формул (FORmula TRANslator). На

ранней стадии разработки FORTRAN был ориентирован на численные вычисления,

но конечной целью был вполне законченный язык программирования, включаю

щий в себя управляющие структуры, условные операторы и операторы вводавы

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

с языком ассемблера, в котором машинные команды кодировались вручную, ос

1.2. Краткая история языков программирования

20 Глава 1. Проблемы разработки языка

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

операторы разрабатывались с учетом специфики ЭВМ IBM 704. Концепции язы

ка FORTRAN типа механизма трехветвевого перехода

вытекала напрямую из ап

паратной архитектуры IBM 407, а операторы типа READ INPUT TAPE сегодня выгля

дят весьма причудливо. Все это выглядело не очень изящно, но в то время еще не

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

лял писать программы, которые выполнялись достаточно быстро на ЭВМ упомя

нутого типа.

FORTRAN оказался весьма удачным языком и оставался доминирующим вплоть

до 70х гг. Следующая версия FORTRAN вышла в 1958 г. и стала называться

FORTRAN II, а спустя несколько лет появился FORTRAN IV. Поскольку каждый

производитель ЭВМ

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

языка, то, понятное дело, царил хаос. В 1966 г. FORTRAN IV стал стандартом под

названием FORTRAN 66 и с тех пор дважды подвергался пересмотру, в результате

чего возникли стандарты FORTRAN 77 и FORTRAN 90. Наличие большого коли

чества программ, написанных на ранних версиях языка, явилось причиной того,

что создаваемые трансляторы должны были удовлетворять требованиям обратной

совместимости, что препятствовало внедрению в язык новых идей и концепций

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

Поскольку FORTRAN оказался столь успешным языком, в Европе возникли

опасения, что IBM будет доминировать в компьютерной отрасли. Немецкое об

щество прикладной математики (German society of applied mathematics — GAMM)

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

for Computing Machinery (ACM) организовала похожий комитет в США. Несмот

ря на то что у европейцев было некоторое беспокойство по поводу господства

американцев, оба этих комитета слились в один. Под руководством Питера На

ура (Peter Naur) этот комитет разработал IAL (International Algorithmic Lan

guage). Предлагавшееся название ALGOL (ALGOrithmic Language) было внача

ле отвергнуто. Но поскольку оно стало общеупотребительным, официальное имя

IAL пришлось впоследствии изменить на ALGOL 58. Новая версия появилась

в 1960 г., и ALGOL 60 (с небольшими изменениями, сделанными в 1962 г.) с 60х

и до начала 70х гг. прошлого века был стандартом академического языка про

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

Если FORTRAN разрабатывался для эффективного использования на IBM 704,

перед разработчиками языка ALGOL стояли совершенно другие цели, а именно:

1. Сделать систему обозначений в ALGOL как можно ближе к стандартной

математической.

2. ALGOL должен быть приспособлен для описания алгоритмов.

3. Программы на ALGOL должны были компилироваться в машинный язык.

4. ALGOL не должен быть привязан к конкретной машинной архитектуре.

Имеется в виду арифметический IF. — Примеч. науч. ред.

В те далекие времена в нашей стране было принято компьютеры называть электронными вычисли

тельными машинами (ЭВМ). Термин «компьютер» стал дефакто стандартом с распространением

персональных компьютеров. — Примеч. науч. ред.

Все эти цели оказались в 1958 г. недостижимы. Чтобы обеспечить независи

мость от архитектуры, в этот язык не были включены возможности вводавывода;

для таких операций следовало создавать специальные процедуры. Хотя это и обес

печивало независимость языка от архитектуры компьютера, но в то же время при

водило к тому, что каждая реализация неизбежно была несовместима с любой

другой. Чтобы сохранить аналогию со строгой математикой, подпрограмма рас

сматривалась как макроподстановка, что породило концепцию передачи парамет

ров по имени; как будет показано в разделе 9.3, эффективно реализовать передачу

параметров по имени достаточно трудно.

Хотя ALGOL и имел некоторый успех в Европе, он так и не получил коммер

ческого успеха в Америке, тем не менее его влияние на другие языки было до

статочно велико. В качестве примера приведем разработанную Шварцем (Jules

Schwartz) из System Development Corporation (CDS) версию языка IAL — JOVIAL

(Jules’ Own Version of IAL). Этот язык использовался военновоздушными сила

ми США для решения прикладных задач.

Бэкус был редактором отчета, в котором определялся язык ALGOL [14]. Он

использовал синтаксическую систему обозначений, сопоставимую с концепцией

контекстносвободного языка, разработанной Хомским (Chomsky) [27]. Так про

изошло внедрение теории формальных грамматик в область языков программиро

вания (раздел 3.3). Поскольку Бэкус и Наур внесли огромный вклад в концепцию

разработки ALGOL, эта система обозначений носит их имя — нормальная форма

Бэкуса–Наура (НФБ) (Backus–Naur Form — BNF).

Можно привести еще один пример влияния ALGOL. Компания по продаже

компьютеров Burroughs, которая после слияния с компанией Sperry Univac обра

зовала компанию Unisys, обнаружила работы польского математика Лукашевича

(Lukasiewicz), который разработал методику, позволяющую записывать арифме

тические выражения без скобок, используя алгоритм вычислений с использова

нием стека. Эта методика оказала значительное влияние на теорию разработки

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

Burroughs разработала компьютер B5500 со стековой архитектурой и вскоре реа

лизовала компилятор языка ALGOL, значительно превышавший по скорости су

ществовавшие в то время компиляторы языка FORTRAN.

С этого момента ситуация изменяется. В 60е гг. была разработана концепция

пользовательских типов данных, которая не была реализована ни в языке

FORTRAN, ни в языке ALGOL. Язык Simula67, разработанный норвежцами

Найгардом (Nygaard) и Далом (Dahl), ввел концепцию классов в ALGOL. В 80е гг.

это натолкнуло Страуструпа (Stroustrup) на идею создать C++ как расширение C

с добавлением понятия классов (см. приложение, раздел П.3). В середине 60х Вирт

(Wirth) разработал расширение языка ALGOL — ALGOLW, пользовавшийся

меньшим успехом. Тем не менее в 70х гг. он же разработал Pascal, который стал

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

успех ALGOL 60, разработал язык ALGOL 68, который, однако, оказался слиш

ком сложным для понимания и эффективной реализации.

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

IBM в своей лаборатории Hursley, находящейся в Англии, разработала новый

язык — NPL (New Programming Language). В связи с некоторым недовольством

1.2. Краткая история языков программирования

22 Глава 1. Проблемы разработки языка

сотрудников Национальной физической лаборатории (English National Physical

Laboratory) язык был переименован в MPPL (MultyPurpose Programming Lan

guage). В дальнейшем это название было сокращено до PL/I. Язык PL/I объеди

нил в себе вычислительные возможности языка FORTRAN и возможности биз

неспрограммирования (обработки деловой информации), имевшиеся в языке

COBOL. В 70е гг. PL/I пользовался некоторой популярностью (так, среди язы

ков, описанных во втором издании этой книги, он обладал наибольшим количе

ством возможностей), в настоящее же время он практически забыт, поскольку вы

теснен такими языками, как C, C++ и Ada. Версия PL/C этого языка в 70е гг.

получила распространение как компилятор PL/I для студентов. BASIC был раз

работан, чтобы удовлетворить потребность в численных расчетах людей, не имею

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

и вышли далеко за рамки первоначальных целей.

Языки обработки деловой информации. Сфера обработки деловой информа

ции стала следующей после численных расчетов областью, которая привлекла вни

мание разработчиков языков. В 1955 г. группа сотрудников Univac под руковод

ством Грейса Хупера (Grace Hooper) разработала язык FLOWMATIC. Целью было

создание приложений для обработки деловой информации с использованием

некоторого англоподобного текста. В 1959 г. Министерство обороны США профи

нансировало совещание по разработке языка CBL (Common Business Language),

который должен был стать бизнесориентированным языком, максимально ис

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

грамм. В связи с несогласованной деятельностью различных компаний для быст

рой разработки этого языка был сформирован специальный комитет Short Range

Committee. Хотя члены этого комитета думали, что они будут разрабатывать не

кий промежуточный вариант языка, оказалось, что разработанная ими специфи

кация, опубликованная в 1960 г., определила новый язык — COBOL (COmmon

Business Oriented Language). COBOL пересматривался в 1961 и 1962 гг. и был стан

дартизован в 1968 г. В 1974 и 1984 гг. он снова подвергся пересмотру. (Дополни

тельные комментарии можно найти в обзоре языка 8.3.)

Языки искусственного интеллекта. Интерес к языкам искусственного интел

лекта возник в 50е гг., когда компанией Rand Corporation был разработан язык

IPL (Information Processing Language). Версия IPLV стала довольно широко из

вестна, но ее использование ограничивалось тем, что IPLV не был языком высо

кого уровня. Огромным шагом вперед стала разработка Джоном МакКарти (John

McCarthy), сотрудником Массачусетсского технологического института (MIT),

языка LISP (LISt Processing) для компьютеров IBM 704. Версия LISP 1.5 стала

стандартом для его реализации на многие годы. Развитие LISP продолжается

до настоящего времени (см. приложение, раздел П.6).

LISP разрабатывался как функциональный язык обработки списков. Естествен

ной областью приложения LISP явилась разработка стратегии ведения игры, по

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

возможных направлений движения (как связанный список) и, продвигаясь по этому

дереву, искать оптимальную стратегию. Другой естественной областью примене

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

символов может заменяться на другую. В этой области первой разработкой был

язык COMIT, созданный Ингве (Yngve), сотрудником MIT. Каждый оператор

программы, написанной на этом языке, был очень похож на контекстнонезависи

мое правило (contextfree production, см. раздел 3.3.1) и представлял собой набор

замен, которые можно было осуществить, если в исходных данных обнаружива

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

разработчиков из AT&T Bell Telephone Laboratories решила создать свой собствен

ный язык — так появился SNOBOL (см. обзор языка в разделе 8.4).

Если LISP создавался как язык обработки списков для универсальных прило

жений, Prolog (см. приложение, раздел П.11) стал специализированным языком с

основанными на понятиях математической логики структурами управления и стра

тегией реализации.

Системные языки. В целях повышения эффективности выполняемых программ

использование языка ассемблера в системной области продолжалось достаточно

долго даже после того, как для приложений в других областях стали использовать

ся языки высокого уровня. Многие языки системного программирования, такие

как CPL и BCPL, так и не нашли широкого применения. Все изменилось с появле

нием языка C (см. приложение, раздел П.2). С развитием в 70е гг. конкурентоспо

собной среды UNIX, написанной в основном на языке C, была доказана эффектив

ность использования языков высокого уровня и в системной области.

1.2.2. Эволюция архитектуры

программного обеспечения

Разработка языков программирования происходит не в вакууме. Так, на констру

ирование языков огромное влияние оказывает то оборудование, на котором долж

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

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

Внешняя среда, поддерживающая выполнение программ, называется операцион

ной средой. Среда, в которой программа разрабатывается, кодируется, тестируется

и отлаживается, или среда разработки (host environment), и операционная среда,

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

друга. В настоящее время в компьютерной индустрии наступила третья эра разра

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

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

Эра универсальных ЭВМ

С момента появления первых компьютеров в 40е и вплоть до 70х гг. в области

вычислений доминировали большие универсальные ЭВМ. Дорогостоящий ком

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

специалистов.

Пакетные среды. Самая ранняя и простая операционная среда полностью со

стояла из внешних файлов с данными. Программа брала несколько входных фай

лов с данными, обрабатывала их и создавала несколько выходных файлов с дан

ными (например, программа начисления заработной платы обрабатывала два

входных файла, содержащих основные записи платежных ведомостей и время, от

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

1.2. Краткая история языков программирования