Пратт Т. Языки программирования. Разработка и реализация
Подождите немного. Документ загружается.
74 Глава 2. Влияние машинной архитектуры
Ê Компилятор — это транслятор, для которого исходным является язык
высокого уровня. Объектный язык близок к машинному языку реально
го компьютера — это либо язык ассемблера, либо какойнибудь вариант
машинного языка. Например, программы на языке C компилируются, как
правило, в программы на языке ассемблера, которые затем транслируют
ся ассемблером в машинный язык.
Ê Загрузчик, или редактор связей, — это транслятор, у которого объектный
язык состоит из готовых к выполнению машинных команд, а исходный
язык почти идентичен объектному. Обычно он состоит из программ на
машинном языке в перемещаемой форме и таблиц данных, указывающих
те точки, в которых перемещаемый код должен быть модифицирован, что
бы стать действительно выполняемым. Например, некоторая подпрограмма
P
может быть откомпилирована таким образом, что она должна размещать
ся и использовать область памяти с адресами от 0 до 999, а подпрограмма
Q— область памяти с адресами от 0 до 1999. Помимо того, эти подпрограм
мы могут использовать библиотечные функции, для которых определены
адреса памяти от 0 до 4999. Задачей загрузчика является создание единой
выполняемой программы, в которой используются согласованные адреса,
как показано в следующей таблице. Выполняемая программа устроена как
единая программа с используемыми адресами от 0 до 7999.
Подпрограмма Адреса Адреса в выполняемой
после компиляции программе
P 0–999 0–999
Q 0–1999 1000–2999
Библиотека 0–4999 3000–7999
Ê Препроцессор, или макропроцессор, — это транслятор, исходный язык ко
торого является расширенной формой какоголибо языка высокого уров
ня (например, Java или C++), а объектный язык — стандартной версией
этого языка. Объектная программа, созданная препроцессором, готова
к трансляции и выполнению обычными процессорами исходного стандарт
ного языка. Большинство компиляторов C включает в себя препроцес
сор, который до начала фазы компиляции сначала преобразует исполь
зуемые в программе макросы в стандартные операторы языка C.
Трансляция программ с исходного языка высокого уровня на машинный
язык часто требует нескольких шагов. Например, нередко программа на
C++ сначала транслируется в программу на C, затем компилируется в
программу на языке ассемблера, которая далее транслируется в переме
щаемый машинный код и, наконец, редактором связей преобразуется в
выполняемый машинный код, который уже может быть загружен в
память загрузчиком и выполнен. Более того, сама фаза компиляции
может включать в себя несколько последовательных этапов, каждый из
которых соответствует определенной промежуточной форме программы,
прежде чем получится конечная объектная программа.
75
2. Программная имитация (программная интерпретация). Вместо того чтобы
транслировать программы на языке высокого уровня в эквивалентные про
граммы на машинном языке, можно смоделировать с помощью программ,
выполняемых на хосткомпьютере, другой компьютер, для которого машин
ным языком будет данный язык высокого уровня. Для этого нужно сконстру
ировать набор программ на машинном языке хосткомпьютера, которые мо
делируют алгоритмы и структуры данных, необходимые для выполнения
программ на языке высокого уровня. Другими словами, при помощи про
грамм, выполняемых на хосткомпьютере, создается (моделируется) компь
ютер с машинным языком высокого уровня; этот компьютер мог бы быть
создан и аппаратным способом. Подобный метод называется программной
имитацией (или программной интерпретацией) компьютера с машинным
языком высокого уровня на хосткомпьютере. Для моделируемой машины
входными данными являются программы на языке высокого уровня. Основ
ная моделирующая программа, используя алгоритм интерпретации, ана
логичный представленному на рис. 2.2, декодирует и выполняет каждый
оператор заданной программы в соответствующей последовательности и про
изводит определяемый интерпретируемой программой вывод результиру
ющих данных.
В таком случае мы говорим, что хосткомпьютер создает виртуальный ком
пьютер, моделирующий язык высокого уровня. Когда хосткомпьютер вы
полняет программу на языке высокого уровня, сложно сказать, выполня
ется ли программа непосредственно аппаратной частью компьютера или
сначала она преобразуется в программу на машинном языке низкого уров
ня, а затем уже выполняется.
Отметим разницу между трансляцией и программной интерпретацией. И для
транслятора, и для программного интерпретатора входными данными являются
программы на языке высокого уровня. Но в результате трансляции получается
просто программа на объектном языке, которая затем должна выполняться аппа
ратным интерпретатором для этого объектного языка, а программный интерпре
татор непосредственно выполняет введенную программу. Если проследить за об
работкой введенной программы транслятором и программным интерпретатором,
то окажется, что транслятор обрабатывает операторы, входящие в программу, в по
рядке их фактического ввода, а интерпретатор следует логике управления выпол
няемой программы. Обычно транслятор обрабатывает каждый оператор только
один раз, в то время как интерпретатор может обрабатывать некоторые операторы
многократно (если, например, они являются частью цикла) или полностью игно
рировать другие (если на них не будет передано управление).
Но чистая трансляция и чистая интерпретация — это две крайности; на практи
ке обычно эти технологии используются вместе, дополняя друг друга. Чистая транс
ляция используется достаточно редко. Это происходит, как правило, если исход
ный язык достаточно близок к машинному языку, как в случае с ассемблером. Так
же редки случаи использования чистой интерпретации — она применяется для
интерактивных языков и для языков управления операционными системами. Чаще
всего для реализации языка на компьютере используется комбинированный под
ход, как показано на рис. 2.3. Сначала программа транслируется из своей исход
2.1. Структура и принципы работы компьютера
76 Глава 2. Влияние машинной архитектуры
ной формы в форму, более удобную для выполнения. Обычно это делается с помо
щью нескольких независимых частей программы, называемых процедурами или
подпрограммами. На этапе загрузки эти независимые части объединяются с набо
ром программ поддержки выполнения (runtime support routines), реализующих
программномоделируемые операции, что приводит к созданию выполняемой фор
мы программы, операторы которой декодируются и выполняются посредством их
интерпретации.
Рис. 2.3. Структура типичной реализации языка программирования
При реализации языка программирования и трансляция, и интерпретация име
ют свои преимущества. Некоторые структуры в программах лучше транслировать
в более простые формы еще до выполнения, другие лучше оставить в первоначаль
ном виде и обрабатывать по мере надобности в процессе выполнения. Те операто
ры исходной программы, которые выполняются неоднократно (например, опера
торы в теле цикла или внутри подпрограммы, которая вызывается более одного
раза), эффективнее транслировать. Для выполнения таких операторов часто тре
буется сложный процесс декодирования, с помощью которого определяются тре
буемые операции и их операнды. Каждый раз при выполнении операторов этот
процесс или большая его часть выполняется заново. Так, если какойто оператор
должен быть выполнен 1000 раз, то и один и тот же процесс его декодирования
должен повториться 1000 раз. Если же этот оператор оттранслирован в более про
стой для декодирования код (например, в последовательность машинных команд),
то сложный процесс декодирования происходит только один раз при транслиро
вании, а потом в каждом из 1000 случаев повторного выполнения этого оператора
требуется декодировать уже более простой код.
Главным недостатком трансляции является потеря информации о программе.
Если данные исходной программы транслируются в последовательность адресов
на машинном языке и в программе имеется ошибка (например, один из этих объек
тов данных делится на 0), часто бывает трудно определить, какой из операторов
программы на исходном языке выполнялся и какие объекты данных использова
77
лись в нем. При интерпретации вся эта информация остается доступной для пользо
вателя. Кроме того, поскольку оператор на языке высокого уровня содержит го
раздо больше информации, чем команда машинного языка, при трансляции раз
мер программы значительно возрастает, то есть программа на машинном языке
занимает в памяти гораздо больше места, чем исходная программа.
Интерпретация имеет свои достоинства, почти прямо противоположные пере
численным для трансляции. Операторы остаются в своей исходной форме до тех
пор, пока они не понадобятся при выполнении, тем самым не расходуется память
для хранения нескольких копий длинных последовательностей машинных команд;
все необходимые команды достаточно сохранить один раз в моделирующей про
грамме (интерпретаторе). Однако за это приходится расплачиваться необходимо
стью многократно декодировать один и тот же оператор, если он, например, встре
чается в цикле или часто вызываемой подпрограмме.
Ключевой вопрос реализации языка программирования заключается в том, ка
кое представление имеет программа во время ее выполнения на реальном компью
тере. Иначе говоря, является этот язык машинным языком данного компьютера
или нет? В зависимости от ответа на этот вопрос языки (вернее, их реализации)
делятся на компилируемые и интерпретируемые.
1. Компилируемые языки. Языки C, C++, FORTRAN, Pascal и Ada принято счи
тать компилируемыми. Это означает, что программы, написанные на этих
языках, транслируются в машинный код данного компьютера перед нача
лом выполнения. Программная интерпретация при этом ограничивается
только интерпретацией набора программ поддержки выполнения, которые
моделируют элементарные операции исходного языка, не имеющие близко
го аналога в машинном языке. Транслятор компилируемого языка является
обычно довольно большой и сложной программой, и при трансляции основ
ное значение имеет создание максимально эффективных с точки зрения их
выполнения программ.
2. Интерпретируемые языки. Языки LISP, ML, Perl, Postscript, Prolog и Small
talk часто реализуются с использованием программного интерпретатора. При
такой реализации транслятор выдает не машинный код используемого ком
пьютера, а некую промежуточную форму программы. Эта форма легче для
выполнения, чем исходная программа, но все же она отличается от машин
ного кода. Процесс интерпретации для выполнения полученной программы
должен быть реализован программным образом, поскольку аппаратный ин
терпретатор в данном случае непосредственно применить невозможно. Ис
пользование программного интерпретатора обычно приводит к относитель
но медленному выполнению программы. Трансляторы интерпретируемых
языков обычно представляют собой довольно простые программы, основ
ная сложность реализуется в программном обеспечении процесса интерпре
тации.
Развитие Всемирной паутины WWW и появление языка Java внесли некото
рые изменения в описанную схему. Язык Java похож скорее на Pascal и C++, чем
на LISP, но в большинстве случаев он реализуется как интерпретируемый язык.
Компилятор Java вырабатывает промежуточный набор байткодов (bytecodes) для
2.1. Структура и принципы работы компьютера
78 Глава 2. Влияние машинной архитектуры
виртуальной машины Java. Основной причиной неэффективности webприложе
ний является потеря времени при передаче по сети затребованных пользователем
страниц, а не выполнение программ на хосткомпьютере. Передача байткодов на
локальный компьютер (даже если он медленнее, чем webсервер) выгоднее в отно
шении временных затрат, чем передача результатов выполнения программы на web
сервере. Однако webсервер не в состоянии предугадать машинную архитектуру
хосткомпьютера. Поэтому браузер создает виртуальную машину Java, которая и
выполняет стандартный набор байткодов Java.
2.2. Виртуальные компьютеры
и время связывания
В предыдущем разделе компьютер был определен как интегрированный набор ал
горитмов и структур данных, способный хранить и выполнять программы. Мы
рассмотрели, каким образом можно сконструировать требуемый компьютер.
1. Путем аппаратной реализации, когда структуры данных и алгоритмы не
посредственно представлены физическими устройствами.
2. Путем программноаппаратной реализации, когда структуры данных и ал
горитмы представлены микропрограммами, которые выполняются на соот
ветствующем микропрограммируемом аппаратном компьютере.
3. Как виртуальный компьютер, то есть путем моделирования структур дан
ных и алгоритмов программами, написанными на какомлибо другом языке
программирования.
4. Посредством комбинации перечисленных методов, когда некоторые части
требуемого компьютера реализованы аппаратным способом, другие — про
граммноаппаратным, третьи — при помощи программного моделирования,
то есть виртуальным способом.
При реализации языка программирования структуры данных и алгоритмы, за
действованные при выполнении программы, определяют некоторую вычислитель
ную машину (компьютер). Поскольку этот компьютер всегда (хотя бы частично)
моделируется программным образом (как в случае с программноаппаратной реа
лизацией компьютера), он называется виртуальным компьютером, определяемым
реализацией языка. Машинным языком этого виртуального компьютера будет яв
ляться выполняемая программа, выдаваемая транслятором этого языка. Если язык
компилируемый, эта программа может состоять из машинных команд реального
компьютера; она может быть представлена произвольной структурой данных, если
язык интерпретируемый. Структурами данных этого виртуального компьютера
являются структуры данных, которые используются во время выполнения про
граммы. Примитивные операции — это те операции, которые действительно вы
полняются аппаратным компьютером при выполнении программы. Аналогично
структуры управления последовательностью действий, данными и памятью — это
те же структуры, которые используются при выполнении программ, независимо
от того, поддерживаются ли они аппаратной частью, микропрограммами или смо
делированы программным образом.
79
2.2.1. Виртуальные компьютеры
и реализация языка
Если бы языки программирования определялись в терминах своих виртуальных
компьютеров, так что каждый язык ассоциировался бы с некоторым однозначно
определенным и понимаемым виртуальным компьютером, то описание семантики
языка в терминах виртуального компьютера было бы очевидным. Но в действи
тельности языки обычно определяются путем индивидуального задания семанти
ки для каждой своей синтаксической конструкции, поэтому определение вирту
ального базового компьютера осуществляется только неявным образом. Каждый
раз, когда язык программирования реализуется на новом компьютере, разработ
чик видит несколько (или совершенно) иной виртуальный компьютер в определе
нии того же самого языка. Таким образом, две различные реализации одного и того
же языка программирования могут использовать различные структуры данных
и различные наборы операций, особенно это относится к структурам данных и опе
рациям, которые скрыты в программном синтаксисе. Каждый разработчик имеет
достаточную широту в определении структур виртуального компьютера, которые
составляют основу для конкретной реализации языка.
Когда язык программирования реализуется на какомлибо конкретном компь
ютере, в первую очередь требуется определить виртуальный компьютер, который
представляет собой интерпретацию семантики языка. Затем этот виртуальный
компьютер конструируется на основе возможностей аппаратной части и программ
ных элементов, предоставляемых конкретным базовым компьютером. Например,
если в виртуальном компьютере присутствуют операция целочисленного сложе
ния и операция извлечения квадратного корня, то разработчик может выбрать сле
дующий вариант. Для реализации целочисленного сложения можно использовать
аналогичную операцию, непосредственно встроенную в аппаратную часть базово
го компьютера, а извлечение квадратного корня можно смоделировать программ
ным образом в виде подпрограммы, вычисляющей квадратные корни. Можно при
вести пример, иллюстрирующий различные возможности реализации структур
данных. Если в виртуальном компьютере имеется простая целочисленная пере
менная X, можно реализовать ее, непосредственно выделив область памяти, в ко
торой хранится значение этой переменной. Но можно сделать иначе — выделить
область памяти, в которой будет содержаться информация о типе данных, храня
щихся в переменной (в нашем случае целый тип), и указатель на другую область
памяти, в которой содержится фактическое значение переменной X. Организация
и структура реализации языка складываются из множества подобных решений,
которые принимает разработчик с учетом аппаратных и программных возможно
стей базового компьютера и стоимости их использования.
Разработчик также должен точно решить, что именно должно быть сделано
в процессе трансляции программы, а что — во время выполнения. Часто бывает
так, что использование какогото конкретного способа представления структуры
данных или операции виртуального компьютера во время выполнения программы
возможно, только если во время трансляции были проделаны определенные дей
ствия, необходимые для создания структуры во время выполнения программы.
Если разработчик решит сделать транслятор более простым, опустив эти действия,
2.2. Виртуальные компьютеры и время связывания
80 Глава 2. Влияние машинной архитектуры
тогда во время выполнения могут потребоваться различные представления струк
туры.
Таким образом, различия в реализациях одного и того же языка объясняются
следующими тремя факторами.
1. Разные разработчики могут иметь различные мнения о том, как должен быть
устроен виртуальный компьютер, неявно определяемый данным языком
программирования.
2. Различные базовые компьютеры, на которых реализуется язык, предостав
ляют различные возможности.
3. Каждый разработчик выбирает собственные решения для реализации эле
ментов виртуального компьютера, используя возможности, предоставляемые
базовым компьютером, и для конструирования транслятора таким образом,
чтобы он поддерживал выбранные решения для представления виртуального
компьютера.
2.2.2. Иерархия виртуальных компьютеров
Виртуальная машина, используемая программистом для создания приложений,
состоит фактически из иерархии виртуальных компьютеров. В основании этой
иерархии, разумеется, должен находиться реальный компьютер. Но обычно про
граммисты крайне редко имеют дело непосредственно с ним. Этот реальный ком
пьютер последовательно преобразуется слоями программного обеспечения (или
микропрограммами) в виртуальную машину, которая может значительно отличать
ся от реального компьютера. Вторым слоем (или третьим, если микропрограммы
формируют второй слой) является операционная система, представляющая собой
сложный набор программ.
Обычно операционная система моделирует некоторое количество новых эле
ментарных операций и структур данных, которые не обеспечены непосредственно
аппаратной частью компьютера (например, структуры внешних файлов или функ
ции определения времени). Помимо того, из виртуального компьютера, опреде
ляемого операционной системой, исключаются и становятся недоступными для
пользователя некоторые элементарные аппаратные операции (например, простей
шие операции вводавывода, выключения компьютера, мультипрограммирования
и организации мультипроцессорной работы). Обычно разработчик, который зани
мается реализацией языка высокого уровня, имеет дело именно с таким, определя
емым операционной системой виртуальным компьютером. В процессе этой реа
лизации разработчик создает новый слой программного обеспечения, которое
выполняется на этом виртуальном компьютере и моделирует операции виртуаль
ного компьютера для языка высокого уровня. Кроме того, он создает транслятор
для языка высокого уровня, переводящий программы пользователя на машинный
язык виртуального компьютера.
Фактически описанная иерархическая система не заканчивается на реализа
ции языка высокого уровня. Программы, создаваемые программистом, добавляют
следующие уровни к этой иерархии. На рис. 2.4 представлена иерархия виртуаль
ных компьютеров, как она выглядит с точки зрения пользователя WWW.
81
Рис. 2.4. Иерархия виртуальных компьютеров для web$приложения
Над виртуальным компьютером языка С, создаваемым компилятором этого
языка, программист с использованием языка С (или другого, ему эквивалентного)
строит программу, называемую webбраузером. Этот браузер создает виртуальный
webкомпьютер, который способен обрабатывать основные структуры данных
WWW, гиперссылки (URL) для перехода к другим webсайтам, основные элемен
ты языка HTML для отображения webстраниц, а также выполнять интерактивные
программы (апплеты) для пользователей браузера. Самый верхний уровень в этой
конкретной иерархии занимает компьютер webприложения, реализованный как
webстраница. Webразработчик использует свойства виртуального webкомпью
тера (HTML, апплеты и т. п.) для предоставления пользователям возможности
работать с этой webстраницей.
Центральная концепция, неявно присутствующая в приведенных рассуждени
ях, заключается в эквивалентности программы и данных. Мы привыкли восприни
мать одни типы объектов в программировании как программы, а другие — как дан
ные. Часто это интуитивное разделение оказывается полезным, но, как следует из
вышеприведенных рассуждений, оно скорее иллюзорное, а не объективно суще
ствующее. Например, тот объект, который в какомто контексте является програм
мой, в другом может представлять собой некую структуру данных. Например, за
дающий некоторую webстраницу код HTML является структурой данных для
виртуального webкомпьютера, который обрабатывает эти данные и определяет,
2.2. Виртуальные компьютеры и время связывания
82 Глава 2. Влияние машинной архитектуры
как следует располагать на странице информацию. С другой стороны, для web
разработчика, использующего HTML для обработки той информации, которую он
хочет поместить на страницу, этот код является программой.
Область применения принципа эквивалентности данных и программ можно
расширить. В языках типа С и FORTRAN выполняемые программы обычно хра
нятся отдельно от тех данных, которые используются в этих программах. В других
языках, таких как Prolog или LISP, такого разделения не существует. Программы
и данные хранятся вместе и различие между ними проявляется только в процессе
выполнения.
2.2.3. Связывание и время связывания
Если не ставить задачу быть предельно точными, можно сказать, что связывание
элемента программы с конкретной характеристикой или свойством — это просто
выбор определенного свойства из некоторого ряда допустимых свойств. Момент
времени, когда при составлении или выполнении программы происходит это свя
зывание, называется временем связывания данного свойства с данным элементом.
В языках программирования существует множество различных типов связывания,
так же как и множество вариантов для времени связывания. Кроме того, в понятия
связывания и времени связывания мы включаем свойства элементов программ,
которые устанавливаются либо определением языка, либо его реализацией.
Классификация времени связывания
Хотя не существует простого способа классифицировать различные типы связы
вания, все же можно выделить несколько классов времени связывания. В основе
этой классификации лежит наше предположение о том, что обработка программы
независимо от языка всегда включает в себя фазу трансляции, за которой следует
выполнение оттранслированной программы.
1. Во время выполнения программы. Связывание часто происходит во время
выполнения программы. Сюда входят связывание переменных с их значе
ниями, а также (во многих языках) связывание переменных с конкретными
областями памяти. Здесь можно выделить две важные подкатегории:
Ê При входе в подпрограмму или блок. В большинстве языков связывание
допустимо только при входе в подпрограмму или блок при выполнении
программы. Например, в языках С и С++ связывание формальных пара
метров с фактическими и связывание формальных параметров с опреде
ленными областями памяти происходит только во время входа в подпро
грамму.
Ê В произвольных точках программы во время ее выполнения. Некоторые
типы связывания могут происходить в произвольных точках программы
во время ее выполнения. Наиболее важным примером этого является
связывание переменных с их значениями путем присваивания. В та
ких языках, как LISP, ML и Smalltalk допустимо также связывание
имен с областями памяти в произвольный момент при выполнении про
граммы.
83
2. Во время трансляции (компиляции). Можно выделить три класса связыва
ний, происходящих во время трансляции.
Ê Связывание по выбору программиста. При написании программы програм
мист принимает множество решений по вопросам выбора типов и имен
переменных, структуры элементов программы и т. п. Эти решения опре
деляют связывания, происходящие при трансляции. Транслятор данно
го языка использует эти связывания для определения окончательной
формы объектной программы.
Ê Связывание по выбору транслятора. В некоторых случаях связывание оп
ределяется транслятором языка без непосредственного участия програм
миста. Например, относительное расположение объекта данных в области
памяти, отведенной под некоторую процедуру, обычно задается трансля
тором без какоголибо вмешательства со стороны программиста. Хране
ние массивов данных и создание (при необходимости) дескрипторов мас
сивов — это также прерогатива транслятора. Для различных реализаций
одного и того же языка это связывание может происходить поразному.
Ê Связывание по выбору загрузчика. Обычно программа состоит из несколь
ких подпрограмм, которые должны быть объединены в одну выполняемую
программу. Как правило, транслятор связывает переменные с адресами
относительно областей памяти, определенных для каждой подпрограммы.
Но эти области должны быть размещены в физической памяти с действи
тельными адресами компьютера, на котором программа будет выполнять
ся. Это происходит во время загрузки, также называемое временем редак
тирования связей.
3. Время реализации языка. Некоторые аспекты определений языка в рамках
некоторой его реализации могут быть одними и теми же для всех выпол
няемых программ, однако они могут различаться в других его реализациях.
Например, часто представление чисел и арифметических операций опреде
ляется тем, как эти операции реализованы с помощью аппаратной части ба
зового компьютера. Если программа написана на языке, использующем воз
можности, определения которых были заданы при его реализации, то эта
программа не обязательно будет работать в другой реализации этого же языка;
хуже того, программа может работать, но выдавать неверный результат.
4. Время определения языка. В основном структура языка формируется во вре
мя определения языка на основе спецификации альтернатив, доступных
программисту при написании программы. Например, возможные альтерна
тивные формы операторов, типы структур данных, программные структуры
и т. п. определяются, как правило, во время определения языка.
Чтобы проиллюстрировать многообразие связывания и времен связывания,
рассмотрим следующий простой оператор присваивания:
X = X + 10.
Предположим, что этот оператор появился в некоторой программе, написан
ной на гипотетическом языке L. Можно исследовать типы связывания и времена
связывания следующих элементов этого оператора.
2.2. Виртуальные компьютеры и время связывания