Программирование

ВВОДНАЯ ЛЕКЦИЯ

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

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

В пятидесятые годы двадцатого века с появлением компьютеров на электронных лампах началось бурное развитие языков программирования. Компьютеры, стоившие в то время значительно дороже, чем разработка любой программы, требовали высокоэффективного кода. Такой код разрабатывался вручную на языке Ассемблер. В середине 50-х годов под руководством Джона Бэкуса для фирмы IBM был разработан алгоритмический язык программирования FORTRAN. Несмотря на то, что уже существовали разработки языков, выполняющие преобразование арифметических выражений в машинный код, создание языка FORTRAN (FORmula TRANslator), предоставляющего возможность записи алгоритма вычислений с использованием условных операторов и операторов ввода/вывода, стало точкой отсчета эры алгоритмических языков программирования.

К языку FORTRAN предъявлялись требования cоздания высокоэффективного кода. Поэтому многие конструкции языка первоначально разрабатывались с учетом архитектуры IBM 407. Успех разработки этого языка привел к тому, что производители других вычислительных систем стали создавать свои версии трансляторов. С целью некоторой возможной на тот момент унификации языка язык FORTRAN IV, разработанный в 1966 году, стал первым стандартом, именуемым FORTRAN 66.

Как альтернатива языку FORTRAN, первоначально ориентированному на архитектуру IBM, под руководством Питера Наура в конце 50-х годов был разработан язык ALGOL (ALGOrithmic Language). Основной целью, преследуемой разработчиками этого языка, была независимость от конкретной архитектуры вычислительной системы. Кроме того, создатели языка ALGOL стремились разработать язык, удобный для описания алгоритмов и применяющий систему обозначений, близкую к той, что принята в математике.

Языки FORTRAN и ALGOL были первыми языками, ориентированными на программирование вычислений.

Язык PL/I, первые версии которого появились в начале 60-х годов, был первоначально ориентирован на IBM 360 и расширял возможности языка FORTRAN некоторыми средствами языка COBOL, разработанного в эти же годы. Несмотря на определенную популярность языка PL/I у программистов, работавших на компьютерах IBM и машинах серии ЕС, в настоящее время он представляет чисто теоретический интерес.

В конце 60-х годов под руководством Найарда и Дала был разработан язык Simula-67, использующий концепцию пользовательских типов данных. Фактически это первый язык, применяющий понятие классов.

В середине 70-х годов Вирт предложил язык Pascal, который сразу стал широко использоваться. В это же время по инициативе Министерства обороны США началась работа по созданию языка высокого уровня, получившего название Ada – в честь Ады Лавлейс, программистки и дочери лорда Байрона. Создание языка началось с определения требований и выработки спецификаций. Над проектом работали четыре независимые группы, но все они использовали как основу язык Pascal. В начале 80-х годов был разработан первый промышленный компилятор языка Ada.

Универсальный язык программирования С был разработан в середине 70-х годов Денисом Ритчи и Кеном Томпсоном. Этот язык стал популярным языком системного программирования и в свое время использовался для написания ядра операционной системы UNIX. Стандарт языка С начал разрабатываться рабочей группой института стандартов ANSI в 1982 году. Международный стандарт языка С принят в 1990 году. Язык С лег в основу разработки языков программирования C++ и Java.

Наряду с алгоритмическими языками параллельно развивались и языки, предназначаемые для обработки деловой информации, а также языки искусственного интеллекта. К первым относится язык COBOL (COmmon Business Oriented Language), а ко вторым – языки LISP (LISt Processing) и Prolog. Язык LISP, разработанный в 60-х годах под руководством Дж. Маккарти, был первым функциональным языком обработки списков, который нашел широкое применение в теории игр.

С появлением персональных компьютеров языки стали составными частями интегрированных сред разработки. Появились языки, применяемые в различных офисных программах, например VBA (Visual Basic for Application).

В 90-х годах с распространением сети Интернет расширяется возможность распределенной обработки данных, что отражается и на развитии языков программирования. Появляются языки, ориентированные на создание серверных приложений, такие как Java, Perl и PHP, языки описания документов – HTML и XML. Традиционные языки программирования С++ и Pascal также претерпевают изменения: под языком программирования начинает пониматься не только функциональность самого языка, а также библиотеки классов, предоставляемые средой программирования. Акцент со спецификации самих языков программирования переносится на стандартизацию механизмов взаимодействия распределенных приложений. Появляются новые технологии – COM и CORBA, специфицирующие взаимодействие распределенных объектов.

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

С течением времени одни языки развивались, приобретали новые черты и остались востребованы, другие утратили свою актуальность и сегодня представляют в лучшем случае чисто теоретический интерес. В значительной степени это связано с такими факторами, как:

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

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

• оperator1; operator2; operator3;

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

  function1(function2(
     function3(beginning_date)));
                

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

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

  if condition1 then operator1;	
  if condition2 then operator2;	
  if condition3 then operator3;
                  

• Объектно-ориентированные языки, основанные на построении объектов как набора данных и операций над ними. Объектно-ориентированные языки объединяют и расширяют возможности, присущие процедурным и аппликативным языкам. К объектно-ориентированным языкам относятся C++, Object Pascal, Java.

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

Концепция языка программирования неотрывно связана с его реализацией. Для того чтобы компиляция одной и той же программы различными компиляторами всегда давала одинаковый результат, разрабатываются стандарты языков программирования. Существует ряд организаций, целенаправленно занимающихся вопросами стандартизации. Это Американский национальный институт стандартов ANSI (American National Standards Institute), Институт инженеров по электротехнике и электронике IEEE (Institute of Electrical and Electronic Engineers), Организация международных стандартов ISO (International Organization for Standardization).

Как правило, при создании языка выпускается частный стандарт, определяемый разработчиками языка. Если язык получает широкое распространение, то со временем появляются различные версии компиляторов, которые не точно следуют частному стандарту. В большинстве случаев идет расширение зафиксированных первоначально возможностей языка. Для приведения наиболее популярных реализаций языка в соответствие друг с другом разрабатывается согласительный стандарт. Очень важным фактором стандартизации языка программирования является своевременность появления стандарта – до широкого распространения языка и создания множества несовместимых реализаций. В процессе развития языка могут появляться новые стандарты, отражающие современные нововведения. Так, язык FORTRAN первоначально был стандартизирован в 1966 году. В результате был издан стандарт FORTRAN 66. Далее этот стандарт несколько раз пересматривался (в 1977 году был выпущен FORTRAN 77, затем появился и FORTRAN 90).

Язык Java, ставший в последнее время весьма распространенным, постепенно был значительно расширен и модифицирован: новая спецификация получила название Java 2.

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

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

Компилятор языка программирования выступает как составная часть среды проектирования. Сама программа наряду с конструкциями, предусмотренными стандартом, как правило, использует библиотечные функции и классы, предоставляемые средой проектирования. Так, интегрированная среда разработки VisualStudio.NET содержит библиотеку классов MFC (Microsoft Foundation Classes), значительно упрощающую процесс разработки приложений, использующих оконный интерфейс.

Интегрированная среда проектирования VisualStudio.NET позволяет создавать и компилировать приложения на языках C++, C#, Visual Basic и VisualJ. Для разработки приложений на языке С++ предназначается также среда CBuilder.

Для проектирования приложений на языке Object Pascal используется интегрированная среда проектирования Delphi.

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

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

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

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

Унарный оператор действует только на один операнд, а бинарный оператор – на два операнда.

Синтаксис выражения можно представить в виде дерева: вершиной дерева является последняя выполняемая операция, узлы описывают промежуточные операции, а листья указывают данные (переменные или константы).

Для представления выражения в линейной форме применяются следующие формы записи:

В префиксной записи, называемой также польской префиксной записью, сначала записывается символ операции, а затем по порядку слева направо записываются операнды. Так, выражение (z+2)*(x+y) в префиксной записи будет иметь следующий вид: * + z 2 + x y. Польская префиксная запись не содержит скобок и позволяет однозначно определять порядок вычисления выражения.

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

Например:

* (+ (z 2) +(x y))
          

В постфиксной записи, называемой также обратной польской записью или суффиксной записью, символ операции записывается после операндов. Выражение (z+2)*(x+y) в постфиксной записи будет иметь следующий вид: z 2 + x y + *.

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

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

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

Вычисление выражений, имеющих операции с одинаковым приоритетом, производится в соответствии с правилом сочетательности, которое определяет порядок выполнения таких операций. В языке С сочетательность операций применяется как слева направо, так и справа налево (как и при вычислении возведения в степень). Порядок вычисления справа налево означает, что выражение x** 2**4 трактуется как x**(2**4).

В следующей таблице приведены в убывающем порядке уровни приоритета операций языка С.

Операции AND, OR, NOT и XOR относятся к логическим операциям. Следующая таблица показывает результаты применения логических операций.

Единственной операцией, имеющей три операнда, является операция "условие" (называемая также условной операцией).

Условная операция имеет следующий формальный синтаксис:

(expr_log) ? expr1:expr2.
          

Если выражение expr_log принимает значение true, то условная операция возвращает значение expr1, а если false, то значение expr2.

Например:

// x примет значение 1, если y>z.
x=(y>z)? 1:0;
          

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

value<<count_of_position
value>>count_of_position.
          

Например, выражение 9<<2 вычисляется следующим образом: число 9 имеет в двоичном представлении значение 001001 (11₈) и при сдвиге его на два разряда влево получается значение 100100 (44₈).

Операции инкремента и декремента соответственно увеличивают или уменьшают значение операнда на 1. Различают постфиксный и префиксный инкремент и декремент. Например, выражение x++ возвращает значение переменной х, а затем увеличивает его на 1, а выражение ++x увеличивает значение x на 1 и возвращает его.

Операция присваивания в различных языках имеет разное обозначение. Так, в языках С, C++, Java операция присваивания обозначается символом =. Например, x=y+z;. Язык С позволяет в одном операторе указывать несколько операций присваивания. Например: x1=x2=y+z;. В языках Pascal и ALGOL операция присваивания указывается символами :=. Например: x:=y+z;. В языке LISP операция присваивания обозначается функцией SETQ (например, (SETQ x (PLUS y z))).

Структурное программирование

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

К основным достоинствам структурного программирования следует отнести:

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

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

Составные операторы

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

Для создания сложных управляющих композиций иногда последовательность операторов необходимо указывать как один оператор. Для этой цели служит составной оператор. Синтаксически составной оператор может быть указан ключевыми словами begin end (язык Pascal) или фигурными скобками {} (языки C++, Java, Perl).

Операторы выбора

К операторам выбора относятся:

Операторы выбора осуществляют ветвление. Оператор if в зависимости от значения выражения-условия позволяет выполнить только одну из двух указанных последовательностей операторов (в большинстве языков программирования такая последовательность операторов указывается как один составной оператор). Существуют формы оператора if, позволяющие задавать вместо второй выполняемой последовательности операторов условие (if-elseif-then- elseif-then).

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

Например:

switch (i):
{
case 0:
case 1: // последовательность операторов
         break;
case 2: // последовательность операторов
         break;
default:
}
          

Реализация оператора if достаточно проста: как правило, процессор поддерживает команды перехода и ветвления.

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

Операторы цикла

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

Языки программирования, как правило, имеют несколько форм оператора цикла.

В языке С++ предусмотрено три формы оператора цикла:

Цикл for выполняется заданное число раз, а проверка условия принадлежности счетчика цикла заданному диапазону производится до выполнения операторов, указанных в цикле.

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

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

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

Реализация операторов цикла с конечным числом повторений отличается от реализации циклов с бесконечным повторением или повторением, основанным на некоторых данных. При реализации цикла с конечным числом повторений выделяется специальная область памяти для хранения этого значения. Цикл for также может относиться как к циклам с конечным числом повторений ( for (i=1; i<50; i++){cout<<i<<endl;}), так и к циклам с бесконечным повторением (for (;;){j=i+j;}).

Операторы перехода

Для выхода из бесконечных циклов или подпрограмм используются операторы перехода. В языке C++ реализованы четыре оператора перехода:

Операторы исключений

Некоторые языки программирования позволяют реализовывать обработку ошибок, называемых исключениями, используя операторы исключений. Код, который может инициировать исключение, заключается в специальный оператор try-catch. При этом ключевое слово catch определяет действия, выполняемые в случае возникновения определенного исключения. Исключение может инициироваться программно или оператором throw (бросок исключения). Некоторые языки программирования позволяют передавать обработку исключения вызывающему методу (так, в языке Java в сигнатуре метода можно ключевым словом throws указать список исключений, при возникновении которых управление будет возвращено вызывающей программе).