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

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

Используя идентификаторы для ячеек памяти и мнемонические обозначения для команд, программисты смогли значительно повысить читабельность написанных ими последовательностей машинных команд. Вначале программисты использовали такие обозначения при разработке программ на бумаге, а затем переводили их на машинный язык. Однако вскоре стало понятно, что такой перевод может выполнить и сама машина. В результате были разработаны программы, названные ассемблерами и предназначенные для перевода записанных в мнемоническом виде программ на машинный язык. Название "ассемблер" [assembler - сборщик] эти программы получили потому, что их назначение заключалось в сборке машинных команд из кодов команд и операндов, полученных в результате перевода мнемонических обозначений и идентификаторов. Мнемонические системы записи программ стали, в свою очередь, рассматриваться как особые языки программирования, именуемые языками ассемблера.

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

В результате появились языки программирования третьего поколения, которые отличались от предыдущих поколений тем, что их языковые конструкции имели более высокий уровень и были машинно-независимыми. Наиболее известными примерами ранних языков третьего поколения являются FORTRAN [FORmula TRANslator - переводчик формул], который был предназначен для научных и инженерных расчетов, и COBOL [COmmon Business-Oriented Language - язык общего назначения деловой ориентации], разработанный специалистами военно-морского флота США для решения экономических задач.

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

После того как необходимый набор примитивов высокого уровня будет определен, пишется программа, называемая транслятором [translator - переводчик]. Она предназначена для перевода программ, записанных с использованием примитивов языка высокого уровня, на машинный язык. Подобный транслятор похож на программу-ассемблер второго поколения, за исключением того, что ему часто приходится объединять [компилировать] несколько машинных инструкций в короткие последовательности команд, предназначенные для имитации выполнения отдельных примитивов высокого уровня. Именно поэтому подобные программы-переводчики часто называют компиляторами. Разработку первого компилятора приписывают Грейс Хоппер [Grace Hopper], которая играла ведущую роль в продвижении концепции языков программирования высокого уровня. Действительно, идея писать программы в форме, близкой к естественному языку, была настолько революционной, что многие руководители поначалу отвергали ее. Популярной альтернативой трансляторам являются интерпретаторы, предложенные как еще один способ выполнения программ, написанных на языках программирования третьего поколения. Эти программы подобны трансляторам, однако они выполняют команды программы непосредственно после их перевода, а не записывают, подобно трансляторам, переведенный код в виде выполняемого модуля, предназначенного для последующего использования. Это означает, что вместо создания копии программы на машинном языке, которую необходимо будет выполнить позже, интерпретатор немедленно выполняет все переведенные им инструкции.

Верификация программ

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

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

С целью иллюстрации сказанного проведем верификацию итерационного алгоритма вычисления факториала числа N:

function Factorial (N) {
     R:=1;
     while (N>1) do {
          R:=R*N;
          N:=N-1;
     }
     return R;
}

В данном случае предусловие будет следующим:

Исходное значение N - натуральное число.

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

Каждый раз при выполнении проверки условия окончания цикла переменная R либо равна 1, либо произведению всех целых чисел, которые больше текущего значения переменой N и не превышают ее исходного значения.

Условие окончания цикла формулируется следующим образом:

Значение N равно 1.

Таким образом, как только цикл завершится, мы будем знать, что все условия должны быть выполнены, а это означает, что переменная R будет равна факториалу числа N.

Парадигмы программирования

Развитие языков программирования происходило по разным направлениям, связанным с альтернативными подходами к процессу программирования, называемыми парадигмами программирования. В данном разделе рассматриваются императивная, декларативная, функциональная и объектно-ориентированная парадигмы.

Императивная, или процедурная парадигма, представляет традиционный подход к процессу программирования. Действительно, именно в соответствии с этой парадигмой построен цикл обработки команды центрального процессора: "извлечь-декодировать-выполнить". Как следует из названия, императивная парадигма определяет процесс программирования как запись последовательности команд, которая при выполнении выполнит обработку данных, необходимую для получения желаемого результата. Таким образом, для решения задачи императивная парадигма предлагает попытаться найти алгоритм ее решения.

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

Функциональная парадигма рассматривает процесс разработки программ как конструирование ее из неких "черных ящиков", каждый из которых получает некоторые исходные данные [на входе] и вырабатывает соответствующий результат [на выходе]. Математики называют такие "ящики" функциями, поэтому этот подход называется функциональной парадигмой. Языковые конструкции функциональных языков программирования состоят из элементарных функций, на основе которых программист должен создавать более сложные функции, необходимые для решения поставленной задачи. Таким образом, согласно функциональной парадигме, программист решает задачу, рассматривая исходные данные, требуемые результаты и преобразование, которое необходимо выполнить, чтобы получить результаты из исходных данных. Решение требуемой задачи, вероятнее всего, можно получить, разбивая исходное преобразование на более простые преобразования, порождающие промежуточные результаты, служащие, в свою очередь, исходными данными для других простых преобразований. Короче говоря, в соответствии с функциональной парадигмой процесс программирования заключается в конструировании требуемых функций в виде вложенных друг в друга совокупностей более простых функций. Например, функцию вычисления среднеарифметического нескольких чисел можно построить из трех более простых функций. Первая из них - Sum - получает на вход список чисел и вычисляет их сумму; вторая - Count - получает список чисел и подсчитывает их количество; третья - Divide - получает на вход два числа и вычисляет их частное. На языке LISP [популярном функциональном языке программирования] эта конструкция может быть записана в виде следующего выражения:

(Divide (Sum Numbers) (Count Numbers))

Использование в этом выражении вложенных структур отражает, что исходные данные для функции Divide являются результатами выполнения функций Sum и Count.

Объектно-ориентированная парадигма, которая предполагает применение методов объектно-ориентированного программирования [ООП], - это еще один подход к процессу разработки программного обеспечения. В рамках этого подхода элемент данных рассматривается как активный "объект", а не как пассивный элемент, как это принято в традиционной императивной парадигме. Поясним это на примере списка имен. В традиционной императивной парадигме этот список рассматривается просто как совокупность некоторых данных. Любая программа, получающая на вход этот список, должна содержать алгоритм выполнения над ним требуемых действий. Таким образом, список является пассивным объектом, поскольку он обрабатывается управляющей программой, а не обрабатывает себя сам. Однако при объектно- ориентированном подходе список рассматривается как объект, содержащий некоторую совокупность данных вместе с набором процедур для их обработки. Этот набор может включать процедуры для вставки в список нового элемента, удаления элемента из списка или сортировки списка. Поэтому программа, получающая доступ к списку для его обработки, не обязана содержать алгоритм для выполнения указанных действий. При необходимости она просто выполняет процедуры, предоставляемые самим объектом.

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

Существование множества объектов, имеющих сходные, но все же отличающиеся характеристики, приводит к явлению, напоминающему перегрузку. Понятие перегрузки означает использование одного и того же символа, например знака +, для представления разных операций в зависимости от типа указанных операндов. Предположим, что объектно-ориентированный графический пакет состоит из разнообразных объектов, каждый из которых описывает некоторую фигуру [окружность, прямоугольник, треугольник и т.п.]. Каждое изображение состоит из совокупности таких объектов. Для каждого объекта известны его размер, положение и цвет, а также то, как он реагирует на сообщения, требующие от него определенных действий, например перемещение в новое положение или отображение самого себя на экране. Для того чтобы нарисовать изображение в целом, мы просто посылаем сообщение "нарисуй себя" каждому из объектов, образующих это изображение. Однако программы, рисующие отдельные объекты, изменяются в зависимости от их формы - процесс рисования квадрата отличается от процесса рисования окружности. Данный механизм специфической интерпретации одного и того же сообщения называется полиморфизмом, а соответствующее сообщение - полиморфным.

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

Трансляторы

Процесс перевода программы с одного языка на другой называется трансляцией. Программа в своем оригинальном виде называется исходной программой; а оттранслированная ее версия называется объектным кодом. Процесс трансляции состоит из трех этапов - лексического анализа, синтаксического разбора и генерации кода, которые выполняются элементами транслятора, называемыми лексическим анализатором, синтаксическим анализатором и генератором кода.

Лексический анализ - это процесс выделения отдельных символьных строк из текста исходной программы. Например, символы '153' должны интерпретироваться транслятором не как совокупность цифр, состоящая из единицы, пятерки и тройки, а как единое числовое значение, равное ста пятидесяти трем. Аналогично этому, слова в программе представляют собой самостоятельные и неразделимые единицы текста, хотя и состоят из отдельных символов. Большинство людей выполняют лексический анализ без каких-либо видимых усилий. И действительно, когда нас просят прочитать текст вслух, мы произносим целые слова, а не те отдельные буквы, из которых они состоят. Таким образом, лексический анализатор символ за символом считывает текст исходной программы, определяя, какие группы символов образуют самостоятельные единицы текста. Затем эти единицы классифицируются, чтобы выяснить, что они собой представляют - числа, слова, арифметические операторы и т.д. Как только единица текста классифицирована, лексический анализатор генерирует ее битовый образ, называемый лексемой [token], и передает его синтаксическому анализатору. При выполнении этого процесса лексический анализатор игнорирует все комментарии, содержащиеся в тексте исходной программы.

Из сказанного выше можно прийти к заключению, что синтаксический анализатор [parser] анализирует программу в терминах лексических единиц [лексем], а не отдельных символов. Задачей синтаксического анализатора является объединение этих единиц в операторы. Действительно, синтаксический анализ - это процесс идентификации грамматической структуры программы и распознавания роли каждого ее компонента.

Последним этапом трансляции является генерация кодов - процесс создания команд машинного языка, имитирующих выполнение операторов, опознанных синтаксическим анализатором. Этот процесс включает множество различных аспектов, один из которых - повышение эффективности генерируемого кода. Например, рассмотрим задачу трансляции последовательности из двух следующих операторов:

x := у +z;
w := x +z;

Эти операторы могут быть оттранслированы по отдельности. Однако это не позволит достичь высокой эффективности результата. Генератор кода должен суметь распознать, что, когда первый оператор будет выполнен, переменные х и z уже будут находиться в регистрах общего назначения центрального процессора и, следовательно, нет необходимости снова загружать их из памяти перед выполнением второго оператора. Реализация подобных нюансов в построении программы называется оптимизацией кода и является важной задачей генератора кода.

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

Связывание и загрузка

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

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

Наконец, чтобы выполнить оттранслированную программу, ее загрузочный модуль должен быть размещен в основной памяти машины с помощью специальной программы, называемой загрузчиком [loader]. Загрузчик обычно является частью программы-планировщика операционной системы. Важность этого этапа особенно велика в многозадачных системах. В подобных системах любая программа вынуждена использовать память совместно с другими параллельно выполняемыми процессами, причем набор параллельно выполняемых процессов изменяется при каждом выполнении программы. Поэтому точное расположение выделяемого для некоторой программы участка памяти остается неизвестным, вплоть до ее вызова на выполнение. Таким образом, задачей загрузчика является считывание программы в указанную операционной системой область памяти и выполнение в ней всех необходимых настроек, которые невозможно осуществить, пока не будет известно точное расположение данной программы в памяти. Команды перехода в программе должны выполнять переход на правильные адреса внутри программы. Желание минимизировать объем выполняемой загрузчиком окончательной настройки привело к разработке таких способов программирования, в которых запрещается использовать явные ссылки на адреса памяти в программе. Это позволяет создавать программные модули (называемые переместимыми модулями), которые правильно работают без каких-либо изменений в их тексте, независимо от того, в какую область памяти они загружены.

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

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