ЯЗЫКИ ПРОГРАММИРОВАНИЯ
Они дают возможность описывать вычисления многими
способами. Язык превращает ЭВМ в «виртуальную машину»,
особенности которой определяются программным обеспечением
Лоуренс Г. Теслер
Язык программирования — это нечто большее, чем просто система обозначений для команд, которые воспринимают ЭВМ. Язык в совокупности с про­граммным обеспечением, которое «понимает» его, может полностью преобразить ЭВМ, превратить ее в машину совершенно другого типа. Аппаратные компоненты типичной ЭВМ — это регистры ячейки памяти, сумматоры и т. д. Когда программист пишет на языке машинных команд, ему приходится рабо­тать непосредственно с этими аппаратными сред­ствами. Новый язык порождает новую модель ЭВМ. У программиста появляется возможность опериро­вать переменными вместо ячеек памяти, файлами данных вместо каналов ввода/вывода и алгебраиче­скими формулами вместо регистров и сумматоров, хотя аппаратура при этом не меняется. Некоторые языки даже порождают машины с «расщеплением личности»: ЭВМ становится как бы коллективом «организацией», каждая из которых выполняет свои собственные вычисления и обменивается с другими сообщениями.
Языков программирования и их диалектов насчи­тывается по крайней мере несколько сотен, а скорее всего — несколько тысяч, и хотя естественных языков человеческого общения, возможно, даже больше, языки программирования в некоторых отношениях более разнообразны. У каждого язы­ка — свои грамматика и синтаксис, своя манера выражения понятий. В принципе большинство вычислительных задач можно решить, пользуясь любым языком, хотя программы при этом выглядели бы совершенно по-разному; кроме того, для какой-то конкретной задачи написать программу на одном языке бывает проще, чем на другом. Здесь мы опишем некоторые широко распространенные языки программирования и попытаемся дать представление
как об их общих свойствах, так и об особенностях, отличающих их друг от друга.
На рисунке на с. 79 показано несколько этапов составления короткой программы на языке Лого. Этот язык был предложен в конце 1960-х годов Сеймуром Пейпертом и его коллегами из Массачу-сетского технологического института (МТИ). Одна из интересных особенностей Лого состоит в возмож­ности управлять «черепахой» — небольшим роботом, который может двигаться вперед и назад, повора­чиваться на месте и поднимать и опускать перо, рисующее след черепахи. Обычно черепаха — это не реальное устройство, а программная модель, поведение которой имитируется на экране дисплея.
Первоначальная версия программы состоит только из команд, отдаваемых черепахе. Сначала опускается перо, затем две команды forward 50 и right 144 по­вторяются пять раз, после чего перо поднимается. Исполняя эти команды, черепаха рисует пятико­нечную звезду. Команда forward 50 предписывает черепахе нарисовать прямую линию длиной в 50 еди­ниц. Команда right 144 задает поворот на 144° по часовой стрелке — изменение направления движения в каждой вершине пятиконечной звезды.
Если бы запись команд, которые должны после­довательно выполняться, была единственным мето­дом для общения с ЭВМ, то создание сложных про-грамм едва ли было бы возможным. В действитель-ности Лого и другие языки программирования имеют средства для упрощения и обобщения команд. В дан­ном случае сразу бросается в глаза фрагмент про­граммы, нуждающейся в усовершенствовании, — это пятикратное повторение инструкций forward и right. Программист по возможности старается не писать одно и то же несколько раз, и не просто потому, что набивать такую программу утомительно. Если программу можно сжать, она будет занимать меньше машинной памяти. Кроме того, повторение одних и тех же строк повышает вероятность описки,
© 1984 by Scientific American, Inc.
© перевод на русский язык, «Мир», 1984.
Языки программирования 77
частности, при модификации программы. В данном случае от повторения можно избавиться, заменив пять команд движения черепахи инструкцией repeat 5 [forward 50 right 144].
Теперь предположим, что программист хочет на­рисовать девятиконечную звезду со сторонами дли­ной в 80 единиц. Это можно сделать, например, по­средством такой инструкции: repeat 9 [forward 80 right 160], но очевидно, что здесь повторяется та же программная конструкция, что и выше, с небольши­ми отличиями в параметрах. Правильнее будет оп­ределить более общую процедуру, в которой число концов и длина сторон задаются как переменные величины. В Лого определение процедуры вводится словом to. Так, фраза to звезда указывает, что далее следуют инструкции, которые надо запомнить как процедуру изображения звезды. После этого звезда становится новой командой языка, — командой, ко­торую можно использовать в программе точно так же, как и встроенные команды forward и right.
Переменные в процедуре звезда являются пара­метрами. Они «передаются» в процедуру в момент ее вызова. В Лого имени параметра предшествует двоеточие. Так, если определить процедуру при по­мощи фразы to звезда : размер : числоконцов, то в результате выполнения строки звезда 80 9 перемен­ной размер будет присвоено значение 80, а перемен­ной числоконцов 9 и, таким образом, будет построена девятиконечная звезда со стороной в 80 единиц.
В процедуру звезда можно внести еще одно усо­вершенствование. В Лого любая описанная процедура может вызываться любой другой процедурой. Это ценное качество языка, но оно повышает вероятность того, что процедуре будут переданы неприемлемые параметры. В лабиринте программы иногда трудно предвидеть, что черепахе будет отдана команда на­рисовать звезду с одним или двумя концами. Про­блему можно решить, добавив в программе условие if числоконцов>2. Оно играет роль «часового», ко­торый разрешает черепахе рисовать только в том случае, если заданное ей число концов больше двух.
Из приведенного выше примера можно видеть, что Лого обладает по крайней мере поверхностным сходством с таким естественным языком, как ан­глийский. Лого имеет словарь, содержащий слова, числа и другие символы (все вместе называемые знаками), которые можно связывать друг с другом с тем, чтобы образовывать более крупные конструк­ции, подобные предложениям естественного языка. Некоторые знаки являются «ключевыми словами» с фиксированным значением, другие определяются программистом. Одни знаки используются как глаго­лы, другие как существительные, определения или знаки препинания. Правила, определяющие, каким образом можно сочетать различные знаки, состав­ляют грамматику языка.
В целом предложения языка программирования делятся на описания и инструкции. Описания опре­деляют, что собой представляет тот или иной объект, что он обозначает или какую он имеет структуру. В программе на Лого строка to звезда : размер : числоконцов является описанием, которое опреде­ляет звезда как имя процедуры, а размер и число-концов как переменные, служащие параметрами про­цедуры звезда. Инструкция обычно описывает часть алгоритма, она указывает, какое действие следует выполнить. В большинстве случаев инструкция имеет форму императива; она начинается с глагола, за ко­торым идут дополнение или обстоятельство. В ин­струкции repeat само слово repeat (повторить) яв­ляется глаголом, последующее число служит наре­чием, а текст в скобках — дополнением к глаголу.
На словаре и синтаксисе процедуры звезда ска­зывается специфика Лого, однако подобные меха­низмы управления ходом выполнения процедур мож­но обнаружить в подавляющем большинстве языков программирования. При отсутствии каких-либо яв­ных инструкций передачи управления программа выполняется последовательно. Если вообразить, что ЭВМ читает программу, то это чтение происходит строка за строкой сверху вниз, и при отсутствии специальных указаний каждая инструкция выпол­няется ровно один раз.
Одним из элементов программы, изменяющих ход выполнения, является инструкция repeat. Она служит примером циклической или итеративной конструкции. Когда машина встречает фразу repeat n и следующую за ней группу инструкций в скобках, она читает и выполняет то, что содержится в скобках п раз. Дру­гим способом управления ходом выполнения про­граммы является условная конструкция, которая в Лого (как и во многих других языках) воплощается в инструкции if. Инструкции, использование которых определяется действием if, выполняются только в том случае, если удовлетворено некоторое условие.
У конструкций итеративного и условного выпол­нения много вариаций. Так, инструкция repeat по­лезна только тогда, когда еще до выполнения цикла известно, сколько раз его требуется повторить. Дру­гие конструкции позволяют управлять завершением цикла на основании данных, формируемых в ходе его выполнения. Для этого в цикл включается не­которое условное выражение. В ряде языков ин­струкция, начинающаяся с ключевого слова while, повторяется до тех пор, пока условие, содержа­щееся в данной инструкции, остается истинным. Другим способом изменения хода выполнения про­граммы служит «безусловный переход» или инструк­ция goto, которая попросту передает управление в выполняемой программе в другую точку. В последние годы среди программистов-теоретиков инструкция goto пользуется дурной славой. Это объясняется тем,
78 Современный компьютер
что программы с большим количеством переходов трудно разобрать (человеку, но не ЭВМ).
Концепция определения процедуры является жиз­ненно важным элементом программирования. Это главный механизм абстракции, процесса перехода от частных примеров (пятиконечная звезда со сто­роной в 50 единиц) к обобщенным понятиям (звезда с некоторым числом концов и с некоторой длиной сторон). Процедура определяется один раз и хра­нится в памяти только в одном месте, но вызываться
она может из многих мест программы, тем самым обеспечивается многократное ее использование. Каждый раз при вызове процедуры точка выполне­ния перемещается в ту область памяти, где хранится данная процедура. Когда процедура завершается, происходит возврат к выполнению инструкции, не­посредственно следующей за инструкцией вызова процедуры. Процедура специального вида, называе­мая функцией, возвращает в вызывающую программу некоторое значение. Например, функция тангенс.
tmpAC-1.gif
СНИМОК ПРОГРАММЫ в ходе ее выполнения демонстри­руется системой разработки программ Пекан. Большая часть исходного текста, или исходной программы, пока­зана в большом окне экрана дисплея вверху справа. Это программа на языке Паскаль для суммирования нечетных чисел в массиве целых чисел. Команды, управ­ляющие выполнением программы, даны в окне вверху слева. Выполнение приостановлено на инструкции, в ко­торой собственно и происходит суммирование.
Эта инструкция заключена в рамку в окне для исходного текста. Ниже исходного текста показана часть блок-схемы и сле­ва от нее — бинарное дерево, изображающее логиче­скую структуру инструкции присваивания. Вложенные рамки внизу слева указывают на области действия симво­лов (имен переменных, типов и т. п.). Окно стека дает картину структур данных. Система Пекан разработана С. Рейссом из университета Брауна, он же является авто­ром этой иллюстрации.
Языки программирования 79
СОСТАВЛЕНИЕ ПРОГРАММЫ НА ЛОГО прослеживается на ее пяти версиях. Программа да­ет команды «черепахе» — меха­ническому рисующему устрой­ству. В первой версии програм­мы все команды для изображе­ния пятиконечной звезды даны в явном виде. Инструкция re­peat во второй версии сжимает программу и снижает вероят­ность ошибки. Третья версия имеет ту же структуру, но рису­ет девятиконечную звезду боль­ших размеров. В четвертой версии определяется процеду­ра, для которой длина сторон и число концов являются пере­менными величинами. В послед­ней версии программы условие if разрешает выполнение проце­дуры лишь тогда, когда задан­ное число концов больше двух. Инструкции repeat и if служат примерами управляющих струк­тур, играющих важную роль фактически во всех языках программирования.
tmpAC-2.gif
При вызове ей в качестве параметра дается угол, а в качестве значения она возвращает тангенс этого угла.
Из сотен или тысяч языков программирования только десяток или около того имеет широкое рас­пространение. На рисунках на с. 81—85 показана одна и та же задача, запрограммированная на шести языках: Бейсик, Паскаль, Кобол, Форт, АПЛ и Лисп. Выбор этих языков отчасти обусловлен их широким распространением. Программистов, свободно владею­щих ими, довольно много. Пример этих языков хо­рошо демонстрирует, насколько разнообразны спо­собы, при помощи которых может быть выражена одна и та же идея. В каждом примере я пытался писать в стиле, естественном или удобном для про­граммиста, привыкшего к данному языку.
Задача состоит в том, чтобы просуммировать не­четные числа из некоторого набора целых чисел. Сама по себе она не представляет особого интереса. Она выбрана потому, что ее решение легко запрограм­мировать на всех этих языках, и потому, что она демонстрирует важные механизмы определения пе-
ременных и процедур управления итеративным и условным выполнением.
Язык программирования Бейсик был разработан в 1965 г. Дж. Кемени и Т. Курцем из Дартмутского колледжа. Изначально язык предназначался для вводного курса по информатике. В дальнейшем в академических кругах этим языком стали пользо­ваться меньше, но зато он стал популярным в дру­гих сферах, особенно в программировании для мик­рокомпьютеров. В Бейсике каждая строка иденти­фицируется номером, и управление ходом программы в значительной степени основано на указании но­меров строк. Центральное место в программе в рассматриваемом примере занимает цикл, в который входят все инструкции между FOR и NEXT. В цикле их выполнение неоднократно повторяется. Собствен­но вычисление происходит в инструкции присваива­ния, которая начинается с ключевого слова LET и дает новое значение переменной.
Язык Паскаль был создан примерно в 1970 г. Н. Виртом из швейцарского Федерального института технологии в Цюрихе. Это еще один язык, предна-
80 Современный компьютер
tmpAC-3.gif
В ПРИМЕРЕ ВЫЧИСЛЕНИЙ, иллюстрирующем свойства нескольких языков программирования, подсчитывается сумма нечетных элементов в массиве из п целых чисел. Алгоритм, показанный на блок-схеме слева, непосредст­венно реализован в программах на Паскале, Бейсике и Коболе, приведенных на следующей странице. Централь­ное место алгоритма — цикл, выполняемый n раз. На каждом проходе цикла анализируется некоторый элемент
значавшийся для обучения, который затем был при­способлен для множества других целей. Паскаль в отличие от Бейсика требует, чтобы программист объявлял каждую переменную и указывал ее тип. В данном случае переменные представляют целые и массивы целых чисел. На процедуры и функции здесь ссылаются при помощи имени, а не номера строки, благодаря чему программу удобнее читать.
Паскаль особенно важен как прародитель более поздних языков. Так, например, Вирт недавно пред­ложил язык, названный Модула-2, который основан на многих концепциях, введенных в Паскале, но, кроме того, особое внимание уделяется построению программы как набора независимых модулей. Ада — язык, разработанный по заданию министерст­ва обороны США, — также в значительной мере базируется на Паскале, хотя он существенно сложнее.
Язык Кобол был создан в 1960 г. объединенным комитетом производителей и пользователей ЭВМ. Название языка — акроним от слов Common Busi-
массива: если это нечетное число, оно прибавляется к текущему итогу. Справа можно проследить за последо­вательным рядом значений, присваиваемых переменным в ходе вычислений для массива из четырех чисел. Символ «:=» дает переменной, стоящей слева, значение, вычис­ленное справа. Число в скобках, как, например, в надписи числа [1] — это индекс, указывающий номер элемента массива числа.
ness-oriented Language (язык, ориентированный на обработку коммерческой информации). И действи­тельно, Кобол давно стал основным языком для обработки больших массивов данных в правитель­ственных учреждениях, банках, страховых фирмах и т. п. Программа на Коболе состоит из четырех разделов или частей: раздела идентификации, разде­ла среды (оборудования), раздела данных и раздела процедур. На рисунках, приведенных на с. 81—82, показаны только раздел данных, в котором описы­ваются переменные, и раздел процедур, в котором формулируются алгоритмы. В противоположность многим языкам программирования, основанным на системе записи (или нотации), принятой в математи­ке и формальной логике, в Коболе за образец был взят синтаксис английского предложения. Поэтому программы на Коболе очень легко читать, но часто они оказываются слишком многословными.
Язык Форт (Forth) был изобретен примерно в 1970 г. Ч. Муром, который в то время работал
Языки программирования 81
в Национальной радиоастрономической обсерватории. Язык был задуман для управления процессами, в частности для управления телескопами, но и этот язык распространился на другие области. Его при­способили для многих мини- и микрокомпьютерных приложений. Отчасти это объясняется тем, что про­граммы на языке Форт занимают мало места в па­мяти. В противоположность Коболу читать програм­мы на Форте трудно, и они крайне немногословны: несколько ключевых слов являются просто знаками препинания.
В языке Форт одним из основных средств, предо­ставляемых машиной, служит «стек» — область памяти, организованная наподобие стопки подносов
в столовой. Таким образом, если что-то укладывается в такую стопку-стек первым, то забирают его оттуда последним. В приведенном примере программы на Форте предполагается, что массив чисел и его размер в момент вызова функции находятся на верху стека. Все вычисления выполняются на стеке, а значения (результаты) функций возвращаются на верх стека. Никакие переменные в программе не описываются.
     В языке АПЛ синтаксис еще более сжатый, чем у Форта. Название языка — сокращение от слов A Programming Language (APL) (язык программи­рования). В 1961 г., когда впервые была опубликова­на книга по АПЛ (К. Айверсон, IBM), язык пред­ставлял собой только способ записи для описания
tmpAC-4.gif
ПРОГРАММА НА ПАСКАЛЕ суммирует нечетные числа из массива и является функцией SumOdds с двумя пара­метрами: целым n и массивом terms. Собственно функ­ция состоит из инструкций в цветной полосе, остальная часть программы объявляет массив для работы SumOdds.
В Паскале каждая переменная должна быть объявлена в описании, задающем ее тип. Некоторые типы, как integer (целый), встроены, другие, как TermIndex, определяются программистом. Цикл задается инструкцией for...to...do..., а условная конструкция — if...then...
tmpAC-5.gif
ПРОГРАММА НА БЕЙСИКЕ суммирует нечетные числа в массиве. Подпрограмма выделена цветной полосой и не имеет названия. Обращаться к ней надо по номеру стро­ки, это делает инструкция GOSUB 1100. Подпрограмма на Бейсике не имеет также и параметров, значения присваи­ваются «глобальным» переменным, к которым имеется
доступ из подпрограммы. Переменную Бейсика, если она не имеет индекса, объявлять не надо. В данном примере DIM (от „dimension" — размерность) определяет, что в массиве Т может быть до 100 элементов. Инструкция FOR...NEXT... задает цикл, IF...THEN... — условную конст­рукцию.
82 Современный компьютер
tmpAC-6.gif
ПРОГРАММА НА КОБОЛЕ суммирует нечетные числа, используя процедуру СУМ-НЕЧЕТ, которая вызывает про­цедуру АНАЛИЗ-ОДНОГО-ЧИСЛА. У процедуры Кобола нет параметров, поэтому перед вызовом СУМ-НЕЧЕТ инструкцией PERFORM переменной N и первым N эле­ментам массива ЧИСЛА присваиваются значения. Ключе-
задач прикладной математики. На ЭВМ язык был реализован позже. Отличительной чертой АПЛ яв­ляется то, что в нем одинаково просто работать как с одиночными величинами, так и с массивами чисел. Так, команду, которая складывает два числа, без всяких изменений можно применить для сложе­ния массивов с тысячей элементов. В примере про­граммы на АПЛ сложение нечетных чисел, храня­щихся в массиве, задается одной инструкцией. Не­нулевое значение числа по модулю 2 идентифицирует нечетные числа-элементы массива, которые таким образом выделяются из массива и суммируются.
Язык Лисп в некоторых отношениях самый простой из тех, что здесь рассмотрены. В нем есть только один вид инструкций, а именно вызов функ­ции. Главным источником силы языка служит то, что значением функции может быть другая функция. Язык Лисп был разработан в конце 50-х годов Дж. Маккарти, в то время работавшим в МТИ. С тех пор Лисп является самым популярным всюду, где ведутся работы по искусственному интеллекту. На­звание языка происходит от слов «list processing» — обработка списков — и программы, и данные в нем представлены в виде списков.
Программу для нашего примера можно было бы написать на Лиспе как итеративный цикл, однако программист, привыкший к стилю Лиспа, скорее всего выбрал бы технику рекурсии, когда процедура вызывает саму себя, затем вызванная процедура вызывает еще раз саму себя и т. д. Для выхода из такого процесса необходимо иметь соответствующие средства, иначе рекурсия превратится в бесконечную цепочку обращений процедуры самой к себе. Обыч-
вые слова PERFORM...VARYING... определяют цикл, IF... открывает условное предложение. Числа 01 и 02 обозна­чают уровни иерархии в структуре данных. PICTURE опи­сывает, в какой форме должны выдаваться на печать числа.
ным средством такого рода служат условные ин­струкции. Когда условие выполняется, происходит возврат к ближайшему более высокому уровню.
В программе набор чисел имеет форму связанного списка. Если список пуст, функция возвращает в качестве результата нуль. В противном случае, если первый элемент списка нечетный, он прибавляется к сумме, и функция вызывает саму себя с аргумен­том (параметром), состоящим из списка, который остается после того, как первый элемент удаляется*. В конце концов все элементы будут выбраны из списка, после чего завершатся все отложенные вы­числения.
Вообще ЭВМ не рассчитана на то, чтобы «пони­мать» Лого, Бейсик или другие языки программи­рования, которые оперируют на подобном уровне абстракции. Аппаратура ЭВМ распознает только двоичные числа, преобразованные в электрические сигналы. Программа в той форме, в которой она может быть выполнена (эта форма называется ма­шинным кодом или машинным языком), представ­лена последовательностью таких чисел. Одни из них являются командами для центрального про­цессора, другие являются данными, а третьи служат адресами в памяти ЭВМ.
Написать программу непосредственно на машин­ном языке можно, но это весьма утомительное за­нятие, и вероятность завершить даже небольшой проект без ошибок мала. (Для ЭВМ не составляет
* Суммирование выполнится только после того, как соот­ветствующая функция-аргумент выдаст результат. Так воз­никает цепочка отложенных вычислений. — Прим. перев.
Языки программирования 83
ПРОГРАММА НА ФОРТЕ для суммирования нечетных чисел в массиве не описывает ни пере­менных, ни каких-либо других структур данных. Она работает только со значениями в стеке. Когда вызывается СУМ-НЕЧЕТ, предполагается, что элементы массива находятся в стеке, а число элементов — на его вер­ху. Строка, следующая за опи­санием процедуры, приведена для того, чтобы выполнить про­грамму для массива из четырех элементов. Приведена полная трассировка выполнения про­граммы, показывающая содер­жимое стека после выполнения каждого слова. Числовое «сло­во» типа 0 или 2 помещает число в стек; SWAP меняет местами два верхних элемента; DUP помещает в стек копию верхнего элемента; DROP вы­брасывает верхний элемент. Опе­раторы типа «-)-» и MOD заме­няют два верхних элемента стека на свой результат. Конст­рукция цикла DO удаляет из стека два элемента (скажем, i и j) и выполняет слова до LOOP i — j раз. Условная кон­струкция /F выполняет слова между IF и ELSE, если на верху стека (TOS) не нуль, в против­ном случае она выполняет слова между ELSE и THEN.
tmpAC-7.gif
труда отличить 01101001 от 01011001 и запомнить, что означает каждый из этих кодов, а человеческие глаз и разум плохо приспособлены для решения таких задач.) В конце 40-х и в начале 50-х годов для облегчения тяжелого труда по написанию про­грамм в машинных кодах была изобретена система обозначений, названная языком ассемблера. Вместо
выписывания двоичных цифр для каждой машинной команды программист писал короткое слово или аббревиатуру типа ADD, SUB или MOVE. Анало­гичным образом адреса ячеек памяти, в которых хранились переменные, заменялись на имена, кото­рые этим переменным присваивались. Числовые значения выражались в десятеричной системе. Для
84 Современный компьютер
слов, обозначающих машинные команды, выбирали легко запоминающиеся слова, так называемые мнемоники.
Первое время перевод с языка ассемблера на ма­шинный язык делали вручную. Технология здесь проста: одна таблица фиксирует соответствие между мнемониками и их двоичными кодами (эта таблица задается раз и навсегда), другую подобную таблицу можно строить по ходу перевода для имен пере­менных, появляющихся в программе. Ясно, что этот процесс легко автоматизировать, и скоро были на­писаны программы, названные ассемблерами, кото­рые выполняли такой перевод.
Языком ассемблера пользуются и сейчас потому, что он дает возможность непосредственного доступа ко всем средствам ЭВМ. Программа, тщательно на­писанная на языке ассемблера, быстра и эффек­тивна, и если требуется достичь компромисса между размером программы и скоростью ее выполнения, то, пользуясь языком ассемблера, программист мо­жет сам принимать соответствующие решения. Со­временные ассемблеры — это изощренные трансли­рующие программы. Однако по-прежнему соблюда­ется соответствие, грубо говоря, один к одному меж­ду строками языка ассемблера и командами машины, из-за чего программы получаются, как правило, весьма длинными и возможностей для ошибок здесь тьма. Структуры управления, доступные в большин­стве языков ассемблера, примитивны. Что особенно важно, язык ассемблера остается ближе к. машин­ному языку, чем к языку программиста. Алгоритмы приходится выражать в терминах того, что должна делать машина, а не в терминах, естественных для решаемой задачи. (Вариант программы суммиро­вания нечетных чисел на языке ассемблера показан на верхнем рисунке на с. 86.)
Работая над решением задачи, вряд ли кто-нибудь станет мысленно оперировать регистрами и адресами памяти — задача сама подскажет подходящие обо­значения. Если это задача по физике, программы можно было бы начать строить, отправляясь от урав­нения, например, F = та; в коммерческих задачах можно было бы выбрать формулу прибыль = до­ход — вложения. Действия, описываемые формулой, затем транслируются в точные команды для маши­ны. Уже давно стало ясно, что такая трансляция также может быть автоматизирована. На этих сооб­ражениях основаны языки типа Фортран, Бейсик и Паскаль. В течение ряда лет языки такого рода называли языками высокого уровня. Сейчас кажется более уместным отнести их просто к языкам про­граммирования, потому что машинные коды и языки ассемблера, по существу, нельзя считать языками в полном смысле этого слова.
С начала 60-х годов большая часть программного обеспечения пишется на языках программирования.
У них много преимуществ над средствами пред­ставления более низкого уровня. Поскольку одна инструкция может развернуться в несколько машин­ных команд, программы становятся короче, что снижает трудозатраты по их написанию и делает их яснее. Пользуясь понятиями, присущими решае­мой задаче, а не понятиями, которые определяются реализацией программы на машине, мы уменьшаем вероятность появления ошибок. Более того, это со­здает предпосылки для появления «машинной неза­висимости», когда одна и та же программа может работать на машинах различных типов.
Важно различать язык программирования и реали­зацию языка. Сам язык — это система записи, набор правил, определяющих синтаксис правильной про­граммы. Реализация языка — это программа, которая преобразует запись высокого уровня в последова­тельность машинных команд.
Имеются два основных вида средств реализации языка: компиляторы и интерпретаторы. Компиляторы транслируют весь текст программы, написанной на, языке высокого уровня, в машинный код в ходе одного непрерывного процесса. При этом создается полная программа в машинных кодах, которую затем можно выполнять без участия компилятора. Обычно работа с компилируемым языком состоит из трех этапов: сначала текст программы создается при помощи редактора текстов или какой-либо другой программы текстовой обработки, затем текст ком­пилируется, и наконец, скомпилированная програм­ма выполняется. Термин компилятор был введен в 1951 г. Грейс М. Хоппер, работавшей тогда в Remington-Rand Univac, и назвавшей так свою пер­вую транслирующую программу. Одной из операций, которую выполняла ее программа в ходе трансляции, были выборка стандартных последовательностей машинных команд из таблиц, хранящихся на маг­нитной ленте, и компиляция из них готовой про­граммы.
Интерпретатор в каждый момент времени выпол­няет по одному предложению программы, по ходу дела превращая каждую конструкцию, записанную на языке высокого уровня, в машинные команды. Разница между компилятором и интерпретатором подобна разнице между переводчиком литературы и переводчиком устной речи. Переводчик литературы берет всю книгу и создает новый текст на другом языке. Переводчик устной речи переводит каждую фразу, как только она произнесена. В действитель­ности большинство интерпретирующих программ проводят некоторую предварительную обработку текста перед тем, как начать выполнение программы. Так, ключевые слова преобразуются в более короткие знаки и имена переменных заменяются их адресами. Но все же эти два вида реализации остаются от­личными друг от друга: для выполнения интерпре-
Языки программирования 85
тируемой программы интерпретатор должен нахо­диться в основной памяти, в то время как для про­граммы, которая уже скомпилирована, компилятор больше не нужен.
В принципе любой язык программирования может быть как интерпретируемым, так и компилируемым, но в большинстве случаев по традиции у каждого языка есть свой предпочтительный способ реализа­ции. Фортран, Кобол, Паскаль в основном компили­руют; Лого, Форт и АПЛ почти всегда интерпре­тируют; Бейсик и Лисп широко используются в обеих формах. Основным преимуществом компиляции яв­ляется скорость выполнения готовой программы, поскольку интерпретатор должен строить соответ-
ствующую последовательность команд в момент, когда инструкция выполняется. Интерпретируемый язык почти неизбежно медленнее компилируемого. В то же время интерпретируемый язык часто более удобен для программиста. Он хорошо подходит для диалогового стиля разработки программ. Отдельные части программы можно написать, проверить и вы­полнить, не выходя из интерпретатора, а когда най­дена ошибка, ее можно исправить немедленно, и при этом нет необходимости возвращаться к про­грамме редактирования текста и затем компили­ровать программу снова.
Внутренние механизмы компилятора или интер­претатора — тема слишком обширная, чтобы ее
tmpAC-8.gif
ПРОГРАММА НА АПЛ вычисляет сумму нечетных элемен­тов в массиве при помощи функции, действие которой определяется одной строчкой. Функция имеет один пара­метр ЧИСЛА — массив, который «знает», сколько в нем элементов, так что нет необходимости указывать N в про­грамме. Инструкция в АПЛ выполняется справа налево, за исключением тех случаев, когда скобки изменяют поря­док вычислений. В этом примере выражение (2 | ЧИСЛА) вычисляется первым, оно дает остаток от деления каждо­го элемента ЧИСЛА на 2 и создает массив такого же
размера, как ЧИСЛА, для остатков. Символ «/» может указывать на две различные операции, обе они встреча­ются в примере. В выражении (2 | ЧИСЛА)/ЧИСЛА «/» яв­ляется оператором «уплотнения», который создает новый массив, где каждый элемент массива ЧИСЛА появляется только тогда, когда соответствующий элемент массива остатков ненулевой. В случае «+/» символ «/» служит оператором «редукции», который приводит массив к од­ному числу путем вставления знака «+» в каждую пару элементов.
tmpAC-9.gif
ПРОГРАММА НА ЛИСПЕ вычисляет сумму нечетных эле­ментов при помощи функции, которая вызывает себя рекурсивно. Функция Лиспа является списком, его первый элемент (называемый CAR) — имя функции, а остаток списка (CDR) задает параметры. DEFUN — это функция, определяющая функцию, a LAMBDA предшествует име­нам параметров. Здесь единственный параметр — список чисел. COND — условная функция, выполняющая CAR списков, являющихся параметрами COND. Если резуль­тат — Т (т. е. истина), то выполняется CDR от этого списка,
в противном случае COND переходит к следующему списку. В данном случае — три возможности. Если ЧИС­ЛА — пустой список, то NULL истинно и СУМ-НЕЧЕТ воз­вращает нуль. Если CAR от ЧИСЛА нечетен, он прибавля­ется к текущему итогу, а СУМ-НЕЧЕТ вызывается для об­работки CDR от ЧИСЛА. Если ни одно из условий не истинно, то доходим до предложения Т (которое всегда истинно). Оно просто вызывает СУМ-НЕЧЕТ с (CDR ЧИС­ЛА) в качестве параметра. При каждом вызове вычисле­ния откладываются.
tmpAC-10.gif
МАШИННЫЙ КОД И КОМАНДЫ АССЕМБЛЕРА опреде­ляют шаги вычисления нечетных элементов через аппа­ратные средства ЭВМ. У каждой машины свой код. Здесь используется код для микропроцессора Motorola 68000. Алгоритм подобен процедуре Паскаля SumOdds, хотя программа компактнее, чем машинная программа, кото­рую сгенерировал бы компилятор Паскаля. Параметры
передаются процедуре, и результат возвращается через стек. Адрес, куда нужно вернуться по завершении про­цедуры, также находится в стеке. Вариант программы на ассемблере, где команды представлены в виде мнемони­ческих аббревиатур, можно перевести прямо в двоичные коды команд, выполняемых микропроцессором.
tmpAC-11.gif
РАБОТА КОМПИЛЯТОРА или транслятора для языка про­граммирования проходит по крайней мере в три этапа. Они показаны здесь для простого случая арифметическо­го выражения в Паскале. В процессе лексического анали­за знаки, или символы, из которых состоит программа, идентифицируются и классифицируются. Синтаксический разбор определяет семантические отношения между знаками. В арифметическом выражении основная задача синтаксического разбора — определить, с каким опера­тором связан каждый операнд. Здесь это делается путем сравнения приоритетов операторов (в предположении,
что умножение предшествует делению, которое пред­шествует сложению и т. д.); в скобки заключаются опера­ции более высокого приоритета. Выражение преобразу­ется в «постфиксную» запись сменой мест оператора и второго операнда в каждом подвыражении. Скобки затем удаляются, в результате выражение можно вычислять слева направо. Генератор кода превращает разобранное выражение в машинные команды, применяя простой алгоритм, отводящий под каждую переменную аппарат­ный регистр.
Языки программирования 87
здесь рассматривать, но структуру типичного компи­лятора в общих чертах описать можно. Процесс компиляции состоит по крайней мере из трех фаз. Первая фаза — лексический анализ, в процессе которого компилятор идентифицирует различные символы в тексте программы и классифицирует их на ключевые слова, числовые значения, имена переменных и т. д. Следующая фаза — синтакси­ческий анализ, в процессе которого компилятор определяет синтаксические соотношения ключевых слов и строит каркас структуры программы. Каждое слово if, например, связывается с последующим then. В третьей фазе генерируется машинный код, соответствующий структуре разобранной программы. В некоторых компиляторах имеется еще четвертая фаза оптимизации, в которой сгенерированная программа еще раз просматривается и корректиру­ется, чтобы повысить ее эффективность.
За последние 30 лет специалисты много размыш­ляли о том, как лучше конструировать компиляторы, и сейчас существует хорошо развитая методология для их создания. Первым шагом является определе­ние языка как такового в абсолютно точной форме. Сейчас общепринята практика определения грамма­тики в терминах «правил вывода», которые рекурсив­но можно применять для создания всех возможных инструкций языка. После этого создание компиля­тора является относительно простой работой для программиста, существуют даже компиляторы ком­пиляторов, которые могут автоматизировать часть работы.
Идея языка программирования появилась так же давно, как большие универсальные цифровые вы­числительные машины. В 1945 г. немецкий математик Конрад Цузе изобрел систему записи, которую он назвал Планкалкюль. Инструкции в языке имели двумерный формат: переменные и их индексы располагались вертикально, а операции над ними
располагались вдоль горизонтальной оси. Цузе писал программы на Планкалкюле на бумаге (одна из них моделировала ходы шахматных фигур), но язык он не реализовал. Тем не менее многие развитые им идеи нашли отражение в современных языках.
Несомненно наибольшее влияние на все после­дующие языки программирования оказал Фортран, разработанный Джоном Бэкусом и его коллегами в IBM в 1954—1957 гг. Название языка происходит от formula translation (трансляция формул), и пред­назначался язык для научных и численных расчетов. Для этих целей он используется до сих пор. В те времена язык был встречен довольно скептически. Вычислительная техника была тогда редким и дорогим средством, из-за этого много внимания уделялось эффективности программ. Предполагалось, что язык высокого уровня неизбежно снизит эффек­тивность, но Бэкус и его группа совершили по­истине чудо. Они создали компилятор, который генерировал программы, по качеству эквивалентные закодированным вручную.
Приблизительно в то же время Хоппер и ее сотрудники в Ramington-Rand Univac разработали язык программирования, названный Флоу-Матик, для обработки коммерческой информации. Он был проще Фортрана, но опыт, приобретенный за не­сколько лет работы с ним, привел к созданию Кобо­ла. Еще более важным языком, появившимся в конце 50-х годов, был Алгол (от algorithmic lan­guage — алгоритмический язык). Алгол-58, первая версия языка, был разработан международным комитетом, который воспользовался идеями, зало­женными как в прагматичном синтаксисе Фортрана, так и в более элегантной системе обозначений Планкалкюля. Результатом работы комитета явился легко читаемый и практичный язык. Он занял важное место в генеалогии последующих языков, включая Паскаль.
tmpAC-12.gif
НЕПРОЦЕДУРНЫЙ ЯЗЫК Пролог не имеет инструкций, а состоит полностью из описаний. Другими словами, Про­лог-программа не дает явных указаний для выполнения операции, она только устанавливает отношения и делает выводы, основанные на них. На рисунке показана про­грамма на диалекте Микро-Пролог. Первые пять описа­ний формулируют определенные отношения «родитель—
ребенок». После этого система может дать ответ на вопросы об установленных фактах, например, указать родителей Авеля и детей Евы. Затем вводятся два прави­ла логического вывода для определения отношения «пре­док» через отношение «родитель». Система может при­менять эти правила для отыскания предков или потомков.
88 Современный компьютер
Довольно много других языков уходят своими корнями в ту же эпоху. Комит (COMIT) был создан для анализа текстов, а АПТ (APT) — для управления станками. Джовиал (JOVIAL), произ­водная от Алгола, был первым широко используемым многоцелевым языком. Он был удобен как для научных, так и для коммерческих расчетов. В начале 60-х годов появился Лисп и разработана нотация АПЛ (но не реализация).
Стремительное размножение языков встревожило многих специалистов. Ведь, в конце концов, во всей математике используется только одна универсальная общепринятая система записи. Реализация языка — это длительная работа, кроме того, нужно время на усвоение его программистом. Поэтому многие специалисты срочно занялись разработкой нового языка, который, обладая достаточной полнотой и гибкостью, мог бы служить универсальным сред­ством программирования. Все эти попытки закончи­лись неудачей. Частичный успех языка ПЛ/1, раз­работанного по заказу IBM, показал, что всеохва­тывающий язык, по всей видимости, должен быть и трудным в изучении, и громоздким в реализации. Более того, так как методы вычислений становились все более разнообразными, специалисты стали приходить к выводу, что необходимость в новых языках для новых областей будет появляться всегда.
В известном смысле все исследования в области программирования с 1957 г. были мотивированы попытками избавиться от недостатков, присущих Фортрану. Вместе с тем и сам Фортран несколько раз подвергался ревизиям. Первоначальная версия накладывала определенные ограничения на про­граммиста (например, имя переменной не могло быть длиннее шести литер) и предоставляла лишь ограниченные возможности для определения струк­тур данных. Вероятно, наиболее серьезные недостат­ки были в управляющих структурах. Все точки ветвлений приходилось определять номерами строк и внимательнейшим образом следить, чтобы смысл программы полностью не затерялся в путанице инструкций GOTO. В более поздних версиях были введены управляющие структуры, способствующие применению более наглядного стиля программиро­вания.
Все языки, которые я до сих пор обсуждал, можно определить как процедурные или предписывающие. Программа, написанная на таком языке, говорит, как получить результат. Она говорит, что сначала надо сделать это, а потом делать то и т. д. Суще­ствуют также непроцедурные или описательные языки, и они приобретают все большее значение. Описательная программа констатирует, какой резуль­тат желателен, не указывая, как этого достичь. В программе скорее формулируются соотношения, а не последовательность вычислений, и, таким
образом, программист освобождается от обязанности разрабатывать шаги алгоритма и определять их порядок.
Наиболее известными непроцедурными языками являются автобланковые (spreadsheet) программы, такие, как Визикальк и Мультиплан, которые стали популярными в связи с широким распространением персональных ЭВМ. В Мультиплане вычисления задаются написанными формулами, так же как в Бейсике или Фортране. Однако порядок, в котором должны выполняться действия формул, определяется не программистом, а реализацией. Временные соотношения в некоторой степени заменяются пространственными. В обычном языке выход одной процедуры может служить входом в другую процеду­ру, аналогичным образом в автобланковых языках значение одной ячейки зависит от значения другой.
В языке Пролог — производной от Лиспа,— кото­рым в последнее время заинтересовались многие исследователи, работающие в области искусственного интеллекта, определение процедур играет еще мень­шую роль. В Прологе не пишут формул, вместо этого определяют соотношения между объектами и величинами. Язык состоит только из описаний и не имеет инструкций. Так, отношение (произве­дение высота ширина площадь) описывает равенство площадь = высота X ширина, но оно не указывает на то, что высота и ширина являются заданными величинами или что площадь следует вычислять. То же самое отношение может служить и для того, чтобы найти высоту, когда известны • ширина и площадь.
Другая тенденция в эволюции языков программи­рования — рост интереса к системам записи, назы­ваемым объектно-ориентированными языками. Как отмечалось выше, инструкции большинства языков программирования являются императивными: вы­числяющее средство не имеет имени, поскольку оно просто-напросто представляет собой абстрактный компьютер в целом. В объектно-ориентированном языке ЭВМ условно делится на объекты, к которым можно обращаться индивидуально. Более того, объекты могут связываться друг с другом при помощи посылки сообщений.
Понятие программных объектов было введено О. Д. Далом и К. Нигардом из Норвежского вычис­лительного центра в Осло в языке Симула-67, веду­щем свое происхождение от Алгола-60. Однако идея не привлекла широкого внимания вплоть до разработки языка Смоллток в 1970 г. А. Кейем и группой его коллег (одним из которых был автор) в Исследовательском центре в Пало-Альто фирмы Xerox. Смоллток состоит исключительно из объект­но-ориентированных конструкций, которые делают описание языка компактным и весьма универсаль­ным, но, с другой стороны, так как все в языке
Языки программирования 89
представлено объектами, некоторые важные меха­низмы структурирования данных невозможно реали­зовать эффективно.
Программный объект состоит из структур данных и алгоритмов. Каждый объект «знает», как выпол­нять операции со своими собственными данными, но для остальной программы объект может тракто­ваться как черный ящик, о внутренней работе которого ничего знать не нужно. Действительно, различные объекты могут пользоваться совершенно разными алгоритмами при выполнении заданий, определенных одним и тем же ключевым словом. Очевидно, что так же, как пингвины, лошади и сороконожки пользуются различными способами для осуществления действия, которое можно назвать ходьбой, так и объекты, чьи данные состоят из целых чисел, массивов или комплексных чисел, будут пользоваться различными методами для выпол­нения операции сложения.
Я и мои коллеги по фирме Apple Computer Inc. разработали язык, названный Класкаль, который дополнил базовые структуры Паскаля концепцией классов объектов. Класкаль, Смоллток, Симула и несколько других объектно-ориентированных языков позволяют объектам в классе наследовать свойства от суперклассов, к которым они принадлежат, так что каждый класс не приходится строить, начиная с нуля. Нужно лишь описать особенности, отличаю­щие данный класс. Так, к пингвинам, лошадям и сороконожкам применимо общее понятие ног. Отличаются они количеством ног и особенностями способа передвижения. Наследование является еще одним механизмом абстракции, позволяющим мно­гим подклассам использовать свойства класса.
Особенно полезным наследование оказалось в создании графического программного обеспечения — области, которая сейчас бурно развивается. На гра­фических образах можно построить целые языки программирования. Действительно, даже некоторые компьютерные игры, построенные в основном на графике, имеют определенные черты языка про­граммирования. Замечательным примером является игра «Робот Одиссей 1», недавно предложенная фирмой Learning Company. В «роботах», запрограм­мированных путем соединения электронных логи­ческих вентилей и других компонент на экране
дисплея, можно пользоваться понятиями условного выполнения и определения процедур. Дж. Лейниером и его коллегами по фирме VPL Research в Пало-Альто сейчас разрабатывается полный визуальный язык программирования, предварительно названный Mandate.
Другим направлением, в котором развиваются языки программирования, является использование параллельных вычислений в мультипроцессорных системах. Казалось бы, что 100 процессоров должны решать задачу в 100 раз быстрее, чем один. Но тако­го ускорения можно достичь только тогда, когда программное обеспечение способно разбить задачу на много частей, которые могут решаться одно­временно.
В некоторых языках предусмотрены явные спо­собы указания заданий, которые могли бы выпол­няться параллельно. Примером является язык Оккам, разработанный фирмой British semicon­ductor manufacturer Inmos. В других языках предпо­лагается, что компилятор будет анализировать и выявлять то, что поддается распараллеливанию. Одним из таких языков является Компел (от compute parallel — вычислять параллельно), над которым мы работали совместно с X. Енеа в 1969 г. Программа на Компеле полностью состоит из инструкций присваивания; их необязательно выпол­нять в том порядке, в котором они написаны, — компилятор сам должен решить, какие вычисления должны быть выполнены в первую очередь. Никакого компилятора для языка Компел написано не было, но языки с подобным механизмом (названные «языками, управляемыми данными», — "data — flow") сейчас уже реализованы.
Огромное разнообразие языков программирования делает невозможным их классификацию по некото­рой единой шкале. Не существует самого лучшего языка программирования, как не существует и самого лучшего естественного языка. «Я разговари­ваю по-испански с богом, по-итальянски с женщи­нами, по-французски с мужчинами и по-немецки с моей лошадью», — сказал Карл V (вероятно, по-французски). Выбор языка программирования, по-видимому, также должен определяться целями его предполагаемого применения.