Эволюция и классификация языков программирования. Структуры данных

1 Лекция 2 Рассматриваемые вопросы: 1. Эволюция и классификация языков программирования. 2. Специализированные языки. 3. Основные понятия языков программирования. 4. Структуры и типы данных языка программирования Список используемой для подготовки литературы: 1) Могилев, А.В. Информатика: учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – М.: Издательский центр «Академия», 2009. – 848 с. 2) Информатика: экспресс-подготовка к интернет-тестированию: учеб. пособие / В.М. Титов, О.Н. Рубальская, О.В. Маленкова и др.; под ред. О.Н. Рубальской. – М.: Финансы и статистика; ИНФРА-М, 2010. – 240 с. 3) Соколов, В.В. Эволюция языков программирования. http://www.ait.org.ua/p/pub_evolution.html 4) http://www.immsp.kiev.ua/publications/monographs/files/04_Paragraf_11.pdf [1] Глава 1 Подраздел 6. Структуры данных 1.6.1. Данные и их обработка Суть всех алгоритмов (и компьютерных программ) состоит в том, что они описывают преобразование некоторых начальных данных в конечные. Какие-то данные алгоритм (программа) может использовать как промежуточные. Естественно, что представление и организация данных имеют при разработке алгоритма первостепенное значение. Вопрос о том, как должны быть организованы данные, необходимо решать до того, как начинается разработка алгоритма (программы). Ведь прежде чем выполнить какие-либо операции, надо иметь объекты, к которым они будут применяться, и четко представлять себе структуру объектов, которые будут получены. Развитие вычислительной техники и программирования сопровождалось эволюцией представлений о роли данных и их организации. Одним из свойств компьютеров является способность хранить огромные объемы информации и обеспечивать легкий доступ к ней. Информация, подлежащая обработке, в некотором смысле представляет абстракцию фрагмента реального мира. Мы говорим о данных как об абстрактном представлении реальности, поскольку некоторые свойства и характеристики реальных объектов при этом игнорируются (как несущественные для данной и задачи). Например, каждый сотрудник в списке сотрудников некоторого учреждения представлен множеством данных. Это множество может включать идентифицирующие данные (например, фамилию), данные, относящиеся к тому, что сотрудник делает, или к тому, что делают для него. Однако маловероятно, что будут включены такие сведения, как цвет глаз или волос, рост и масса тела. Решая конкретную задачу, необходимо выбрать множество данных, представляющих реальную ситуацию. Затем надлежит выбрать способ представления этой информации. Представление данных определяется исходя из средств и возможностей, допускаемых компьютером и его программным обеспечением. Однако важную роль играют и свойства самих данных, операции, которые должны выполняться над ними. С развитием вычислительной техники и программирования средства и возможности представления данных также развивались и теперь позволяют использовать как простейшие неструктурированные данные, так и данные более сложных типов, полученные с помощью комбинации простейших данных. Такие данные называют структурированными, поскольку они обладают некоторой организацией. Современные средства программирования позволяют оперировать с множествами, массивами, записями, файлами (очередями). В более сложных случаях программист может задать динамические структуры данных, память для хранения которых выделяется прямо в процессе выполнения программы. К таким данным относят линейные списки (одно- и двунаправленные), стеки, деревья, графы. 2 Получило развитие так называемое объектно-ориентированное программирование, в котором в известной мере устранено противостояние данных и программ. Объект – это некое образование, состоящее не только из данных, но и из процедур их обработки. Остановимся подробнее на свойствах различных представлений данных, или, как еще говорят, типах данных. 1.6.2. Простые (неструктурированные) типы данных В математике принято классифицировать величины в соответствии с их характеристиками. Различают целые, вещественные, комплексные и логические величины, величины, представляющие собой отдельные значения, множества значений или множества множеств. Аналогично этому в информатике любая константа, переменная, выражение или функция относится к некоторому типу. Фактически тип характеризует множество значений, которые может принимать константа, переменная, выражение или функция. Широко используется правило, по которому тип явно указывается в описании константы, переменной или функции. К данным каждого типа применимы определенные операции и их поведение подчиняется некоторым аксиомам. Так, над целыми числами могут выполняться операции сложения (+), вычитания (-) и умножения (*). Существуют две различные операции, связанные с делением и не выводящие за границы множества целых чисел: определение целой части от деления одного числа на другое; определение остатка от деления одного числа на другое. Целые числа, используемые компьютером, имеют те же свойства (подчиняются тем же аксиомам), что и целые числа в арифметике. Все вычисления с ними выполняются абсолютно точно (не приближенно). Имеется только одно отличие в свойствах компьютерных целых чисел от тех, которыми оперирует абстрактная математика, а именно – ограниченность диапазона: для каждой компьютерной системы имеется самое большое допустимое в ней целое число М+∞ (и самое малое, отрицательное М-∞). Обычно выполняется соотношение М+∞ + 1 = М-∞ (М-∞ - 1 = М+∞), т.е. прибавив единицу к самому большому допустимому положительному числу, мы получим модуль самого малого допустимого отрицательного. Это свойство компьютерных чисел связано с особенностями их кодирования в ячейках памяти компьютера. Над действительными (или вещественными) числами могут быть выполнены операции сложения (+), вычитания (-), умножения (*) и деления (/), так же, как и над математическими действительными числами. Однако все операции над действительными числами выполняются с точностью, не превосходящей некоторого фиксированного значения, вследствие того, что представления чисел в памяти компьютера имеют ограниченную длину (зависящую от конкретного компьютера и используемой системы программирования). Так, например, в машинной арифметике может быть 1/3 = 0,33333333, тогда как математически точное десятичное представление дроби 1/3 – бесконечно длинное число. Главным свойством литерных (символьных) данных является их упорядоченность, т.е. свойство быть сравнимыми. Обычным признаком значения символьной или текстовой величины являются кавычки, и справедливо 'а' < 'b’, 'b' < 'с', 'с' < ‘d' и т.д. Каждый символ имеет определенный числовой код (например, код символа латинской буквы 'A' в большинстве кодировок 63), и упорядочение происходит в соответствии с этими числовыми кодами. Как правило, имеются функции, позволяющие получить по символу его код и символ по коду. Для строчных величин единственной выполнимой операцией является конкатенация («сложение») строк. Например, 'abcd' + 'efg' = 'abcdefg'. В конкретных системах обычно определены функции, определяющие длину строк, вхождение в них тех или иных подстрок, вырезающие из строк некоторые фрагменты. К логическим данным, способным принимать значения «истина» (и, «true») или «ложь» (л, «false»), применимы основные операции логики высказываний: конъюнкция (логическое И — «and»), дизъюнкция (логическое ИЛИ - «or»), отрицание (логическое НЕ «not»). Иногда можно использовать операции импликации («если»), эквиваленции («если и только если») и т.п. Эти логические операции определяются таблицей истинности 3 (табл. 1.12). Таблица 1.12 – Таблица истинности для логических операций А И И Л Л В И Л И Л И (A and В) И Л Л И ИЛИ (A or В) И И И Л НЕ (not A) Л Л И И Часто при решении задач оказываются полезными определенные разработчиком типы данных, представляющие собой перечисление некоторых констант или ограниченный с обеих сторон диапазон определенных ранее данных. Например, создается тип данных из двух символов 'а' и 'b' или из целых чисел в диапазоне от 1 до 100 и т.д. 1.6.3. Структурированные типы данных Описанные выше типы данных называют простыми. Основной признак, по которому можно определить величину простого типа, таков: одно имя – одно значение. Значительно большие возможности заключают в себе структурированные данные, определяемые разработчиком программы (в пределах возможностей используемого им языка программирования). К структурированию данных разработчика программы толкает как логика прикладной задачи, так и чисто утилитарное соображение: При наличии в задаче большого количества входных и выходных данных отдельное именование каждого из них может оказаться практически невозможным. Разумеется, действия разработчика алгоритма и программы ограничены возможностями того языка программирования, на который он ориентируется. В разных языках возможности структуризации переменных на уровне сложных структур не совпадают, но многие структуры давно стали традиционными и реализованы в большинстве практически используемых языков программирования. Структурированные типы данных классифицируют по следующим основным признакам: однородная – неоднородная, упорядоченная – неупорядоченная, прямой доступ последовательный доступ, статическая – динамическая. Эти признаки противостоят друг другу лишь внутри пары, а вне этого могут сочетаться. Если все элементы, образующие структуру, однотипны (например, целые числа или символы), то структура является однородной; если же в ней «перепутаны» элементы разной природы (например, числа чередуются с символами), то неоднородной. Структуру называют упорядоченной, если между ее элементами определен порядок следования. Примером упорядоченной математической структуры служит числовая последовательность, в которой у каждого элемента (кроме первого) есть предыдущий и последующий. Наличие индекса в записи элементов структуры уже указывает на ее упорядоченность (хотя индекс для этого не является обязательным признаком). По способу доступа упорядоченные структуры бывают прямого и последовательного доступа. При прямом доступе каждый элемент структуры доступен пользователю в любой момент независимо от других элементов. Глядя на линейную таблицу чисел, мы можем списать или заменить сразу, допустим, десятый элемент. Однако если эта таблица не на бумаге, а, скажем, каким-то образом записана на магнитофонную ленту, то сразу десятое число нам недоступно – надо сначала извлечь девять предшествующих. В последнем случае мы имеем дело с последовательным доступом. Если у структуры размер (длина, количество элементов) не может быть изменен «на ходу», а фиксирован заранее, то такую структуру называют статической. Программные средства информатики иногда позволяют не фиксировать размер структуры, а устанавливать его по ходу решения задачи и менять при необходимости, что бывает очень удобно. Такую структуру называют динамической. Например, при описании закономерностей движения очереди в магазине мы не знаем заранее, сколько человек в ней будет в тот или иной момент, и соответствующую структуру данных (например, список фамилий участников очереди) лучше представлять динамической. 4 Массивы Самым традиционным и широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) – однородная упорядоченная статическая структура прямого доступа. Массивом называют однородный набор величин одного и того же типа, называемых компонентами массива, объединенных одним общим именем (идентификатором) и идентифицируемых (адресуемых) вычисляемым индексом. Это определение подчеркивает, что все однотипные компоненты массива имеют одно и то же имя, но различаются по индексам, которые могут иметь характер целых чисел из некоторого диапазона, литер, перечисленных констант. Индексы позволяют адресовать компоненты массива, т.е. получать доступ в произвольный момент времени к любой из них как к одиночной переменной (рис. 1.26). Обычный прием работы с массивом – выборочное изменение отдельных его компонент. Вычисляемые индексы позволяют использовать единое обозначение элементов массива для описания массовых однотипных операций в циклических конструкциях программ. Важной особенностью массива является его статичность. Массив должен быть описан в программе (т.е. определены тип и число компонент) и его характеристики не могут быть изменены в ходе выполнения программы. Компонентами массива могут быть не только простейшие данные, но и структурные, в том числе массивы. В этом случае мы получаем массив массивов – многомерный массив. Для индексации элементарных компонент в этом случае могут потребоваться два, три и более индексов. В некоторых системах программирования существуют специальные виды массивов. Например, массив литер (символов) определяется как строка. Данные, хранящиеся в массивах, находятся в оперативной памяти компьютера. Это, с одной стороны, ускоряет доступ к ним в ходе решения задачи, а с другой – налагает ограничения на объем возможной информации, организованной в виде массивов. Не следует поэтому, без крайней необходимости, создавать новые массивы для перемещения данных из уже существующих массивов. Рассмотрим в качестве примера задачу сортировки набора некоторых данных, для которых имеют смысл отношения «больше» или «меньше». Представьте себе, что надо карточки в картотеке разместить в порядке возрастания записанных на них чисел. Используем для сортировки набора чисел (т.е. записи их в порядке возрастания) одномерный (линейный) массив. Дадим ему имя А, тогда а1, а2, а3, ..., aN – компоненты массива. Существует огромное число методов сортировки массивов. Рассмотрим один из самых простых (но не самых быстрых) – метод выбора. В начале процесса имеем заполненный числами массив (неотсортированный). Процесс сортировки строится по индукции. Допустим, мы уже отсортировали часть массива и имеем упорядоченную последовательность а1 < а2 < … < аi-1 и оставшуюся неотсортированной последовательность аi, аi+1, ..., aN. При каждом шаге, начиная с i = 1, из неотсортированной части последовательности извлекается наименьший элемент x = aj и меняется местами с i-м элементом. Затем этот процесс повторяется для i = 2, i = 3 и т.д., до тех пор, пока не останется один, самый большой элемент. Этот алгоритм потребует многократного нахождения наименьшего элемента массива. 5 Этот «вспомогательный» алгоритм поиска наименьшего среди а1, ..., aN может быть следующим: 1) фиксируется в качестве значения вспомогательной переменной m первый слева элемент массива: m = ai (в конце процесса m будет иметь значение наименьшего элемента); 2) выполняется сравнение m с элементом массива aj (начиная с номера j = i+1) и, если aj < m, то m заменяется на aj; 3) далее выполняется сравнение m с очередным элементом массива, т.е. j увеличивается на единицу и шаги 2, 3 выполняются снова, до тех пор, пока j не достигнет максимального значения индекса элемента массива. После выполнения этих предписаний переменная m будет соответствовать наименьшему элементу массива. Двумерный массив визуально представляется плоской таблицей (табл. 1.13). При наличии одного имени (идентификатора) для всех компонент каждая из них фиксируется значениями двух индексов, указывающих номер строки и номер столбца, на пересечении которых находится эта компонента. Таблица 1.13 – Графический образ двумерного массива j 1 2 3 4 … i … 1 а11 а12 а13 а14 2 а21 а22 а23 а24 … 3 а31 а32 а33 а34 … 4 … а41 … а42 … а43 … а44 … … … Рассмотрим пример обработки данных, хранящихся в двумерном массиве. Допустим, что на некоторой территории (например, страны) «квадратно-гнездовым» способом расставлены температурные датчики и их показания собраны в одном центре (что вполне близко к реальной деятельности метеослужбы). Тогда в таблицу – двумерный массив – попадут значения температуры tij в соответствующих точках. Требуется, просматривая таблицу построчно, найти те точки (т.е. индексы узлов), между которыми температура принимает некоторое заданное значение Т. Пусть в таблице n строк и m столбцов. Вспомогательным алгоритмом в данной задаче может быть алгоритм поиска нужных узлов в одной строке. Пусть эта строка имеет номер k. Алгоритмы записаны без комментариев для самостоятельного разбора. Вспомогательный алгоритм (k): 1) положить j = 1; 2) если tk,j < Т < tk,j+1, то см. п. 2; 3) увеличить j на 1; 4) если j < m, то вернуться к п. 2; 5) задача решена, ответ: (k,j), (k,j+1); 6) конец. Основной алгоритм: 1) положить k = 1; 2) выполнить вспомогательный алгоритм (k); 3) увеличить k на 1; 4) если k > n, то вернуться к п. 2; 5) конец. Записи, множества, файлы Обобщением массива является комбинированный тип данных – запись, являющаяся неоднородной упорядоченной статической структурой прямого доступа. Запись есть набор именованных компонент – полей (часто разного типа), объединенных одним общим именем и идентифицируемых (адресуемых) с помощью как имени записи, так и имен по- 6 лей (рис. 1.27). Запись В состоит из трех полей, имеющих последовательно типы «текст», «целое число», «вещественное число»: первое поле – название детали, второе – условный номер по каталогу, третье – длина. При работе с единственной записью (что бывает нечасто), имя поля можно использовать как обычную переменную, т е. можно изменять значение поля с помощью операции присваивания или любых других доступных операций над величинами данного типа. Если же данная запись – лишь часть набора данных, то имя поля состоит из двух частей и называется составным именем поля (на рис. 1.27 составные имена В.name, B.number, B.length). Для облегчения работы с полями в различных языках программирования существуют средства, облегчающие их адресацию. И записи, и массивы обладают одним общим свойством – произвольным доступом к компонентам. Записи более универсальны в том смысле, что для них не требуется идентичности типов их компонент. Массивы обеспечивают большую гибкость – индексы их компонент можно вычислять в отличие от имен полей записей. Существенно иные возможности дает структура данных, моделирующая свойства математического объекта – множества. Над множеством могут быть выполнены следующие операции: 1) объединение множеств (операция сложения ( + )); 2) пересечение множеств (операция умножения (*)); 3) теоретико-множественная разность (вычитание множеств (-)); 4) проверка принадлежности элемента множеству. Различия между множеством и массивом очень существенны: размер множества заранее не оговаривается (хотя и ограничен компьютерной реализацией, например 255), не существует иного способа доступа к элементам множества, кроме как проверкой принадлежности множеству. Более сложной, чем рассмотренные выше, из предусмотренных в современных системах программирования структур данных является очередь (файл). Понятие «файл» при всей своей привычности употребляется в информатике в нескольких не совсем совпадающих смыслах. Здесь мы остановимся лишь на представлении о файле как однородной упорядоченной динамической структуре последовательного доступа – очереди. Очередь есть линейно упорядоченный набор следующих друг за другом компонент, доступ к которым происходит по следующим правилам: 1) новые компоненты могут добавляться лишь в хвост очереди; 2) значения компонент могут читаться (извлекаться) лишь в порядке следования компонент от головы к хвосту очереди. Размер очереди заранее не оговаривается и теоретически может считаться бесконечным. Для запоминания (хранения) компонент очереди часто используют внешние запоминающие устройства большой емкости – магнитные диски и ленты. Отсюда другое название очереди – файл (в английском языке это слово имеет ряд значений, в том числе «картотека», «шеренга», «очередь»). Исторически слово «файл» стало впервые применяться в информатике для обозначения последовательного набора каких-либо данных или команд (программа), хранящихся на внешнем запоминающем устройстве. Несколько позже были осознаны абстрактные, не зависящие от магнитных дисков и лент, свойства очереди как структуры данных, полезные при решении многих задач обработки информации. Такой принцип извлечения и добавления компонент к очереди часто называется «первым вошел – первым вышел» (английская аббревиатура – «FIFO») (Рис. 1.28). 7 В языках программирования существуют и такие разновидности файлов, которые не подчиняются условию последовательности доступа к его компонентам (так называемые файлы прямого доступа). Они уже не являются очередями. Суперпозиция структур данных Из рассмотренных структур данных можно создавать различные суперпозиции (вопрос о допустимости той или иной суперпозиции в конкретном языке программирования следует искать в его описании). Рассмотрим в качестве примера такую часто используемую суперпозицию как файл записей – обычную, например, при создании баз данных. Итак, имеется файл по имени F, содержащий некоторое количество таких записей, как на рис. 1.27. Составим алгоритм подсчета количества болтов, у которых длина (length) заключена в пределах от 3 до 40: 1) положить k = 0 (в конце работы к – число искомых болтов); 2) прочесть первую запись из файла; 3) если В.name = 'болт' и 30 < B.lenght < 40, то увеличить k на 1; 4) если файл уже опустел, то идти к п. 7, иначе – к п. 5; 5) прочесть следующую запись из файла; 6) идти к п. 3; 7) конец работы; k – число искомых болтов. Стек Существует (и часто используется) и другая структура данных, в которой тот элемент, который первый в нее помещался, выходит последним и, наоборот, тот, который последним входит, выходит первым (английская аббревиатура «LIFO»). Такая структура получила название стек (или магазин – по сходству с магазином стрелкового оружия) (рис. 1.29). Стеки и принцип LIFO находят очень широкое применение в информатике. Рассмотрим в качестве примера использование стека при вычислении значения арифметического выражения. Вычисление значения выражения требует соблюдения старшинства операций. Операции по старшинству при вычислении значений математических выражений располагаются в следующем порядке: вычисление значений функций (включая возведение в степень), умножение и деление, сложение и вычитание. Изменить такой «естественный» порядок операций можно с помощью скобок. Например, вычисление известного из школьного курса математики выражения b2 – 4 * а * с включает предварительное установление порядка выполнения операций: 1 4 2 3 b2 – 4 * а * с Для этого выражение просматривают несколько раз. Выполнение каждой операции 8 дает некоторое число, которое приходится записывать отдельно от выражения, запоминая тот фрагмент выражения, для которого число является значением. Рассмотрим экономный алгоритм вычисления значения выражения, использующий два магазина для перестановки элементов выражения (с учетом старшинства операций) и для хранения промежуточных результатов. Магазины обозначим М1 и М2; в M1 будут попадать знаки операций, в M2 – числа, участвующие в записи выражения, значения переменных и все промежуточные числовые значения. Ограничимся выражениями, состоящими только из чисел и переменных без индекса, связанных знаками операций «*», «/», «+», «-». Знак «минус» будет знаком лишь двухместной операции вычитания, выражения типа «- а + 1» исключаются из рассмотрения. От этих ограничений можно было бы и отказаться, но это удлинило бы изложение. Пока предположим также, что в выражении нет скобок. Опишем алгоритм вычисления. Исходное выражение читается слева направо; если прочитано число, то оно заносится в М2, если переменная – в М2 заносится ее значение; если же прочитан знак операции, то необходимо различать несколько случаев: 1) М1 пуст; прочитанный знак помещается на вершину M1; 2) прочитанный знак помещается на вершину М1, если он обозначает операцию, которая старше и поэтому должна выполняться до операции, знак которой был расположен на вершине М1; 3) если операции равноправны или если та, знак которой только что прочитан в выражении, должна выполняться позднее, необходимо применить операцию, знак которой расположен на вершине М1 к двум верхним числам из М2 (число на вершине – второй операнд, число под ним – первый); знак операции, расположенный на вершине М1, удаляется, вместо двух верхних чисел в М2 помещается результат выполнения над ними операции. В некоторый момент в исходном выражении не остается символов. Если пуст и М1, то вычисление окончено, результат находится в М2; в противном случае знаки операции извлекаются по очереди из М1 и соответствующие операции применяются к числам из М2. Рассмотрим вычисление выражения b2 – 4 * a * с; значения переменных а, b, с обозначим соответственно А, В, С. Знак возведения в степень обозначим, как часто делается, стрелкой вверх. М2: М2: М2: М2: М2: М2: М2: М2: М2: В 2 В В↑2 4 В↑2 А 4 В↑2 4*А В↑2 С 4*А В↑2 4*А*С В↑2 В↑2 - 4 * А * С М1: М1: ↑ ↑ М1: М1: - М1: * - М1: - М1: * - М1: - М1: Про знак операции говорят, что он имеет более высокий приоритет в сравнении с другим знаком, если обозначаемая им операция старше. В других случаях говорят о равных приоритетах или более низком приоритете. Рассмотренные знаки операций распадаются на группы равных по приоритету: ↑ *, / +, Группы упорядочены по убыванию приоритета. 9 Теперь дадим правило работы со скобками. Левая скобка заносится в М1 сразу после прочтения. Прочтение правой скобки влечет выполнение всех операций, знаки которых находятся в М1 выше левой скобки; после выполнения этих операций обе скобки уничтожаются. Вот что будет происходить при вычислении выражения (а + b)*с: М2: М2: М2: М2: М2: М2: А В А А+В А+В С А+В (А + В) *С М1: М1: М1: М1: М1: ( + ( ( * М1: Иерархическая организация данных Во всех рассмотренных выше структурах отдельные элементы (компоненты, поля, составляющие) структуры были формально равноправны. Существует, однако, широкий круг задач, в которых одни данные естественным образом «подвязаны» к другим. В этом случае возникает соподчиненная (иерархическая) структура данных. Ограничимся конкретным примером. Представим себе генеалогическое дерево, корень которого – имя человека, на следующем уровне – имена его родителей, еще на следующем – имена родителей и т.д. Такая структура называется двоичным деревом (рис. 1.30). Как структурировать эти данные (имена)? Для помещения их в текстовый массив или запись трудно придумать логически оправданный порядок следования. Самое разумное создать динамическую структуру, подобную той, что изображена на рис. 1.30. Современные языки программирования позволяют это делать и обрабатывать такие структуры с высокой эффективностью. ГЛАВА 3 ЯЗЫКИ И МЕТОДЫ ПРОГРАММИРОВАНИЯ Прохожий спросил у фермера, сооружающего небольшую деревянную постройку, что тот строит. - Пока не знаю, - ответил фермер. Если мне удастся сдать это сооружение, тогда оно - очаровательный сельский домик, а если не удастся, то это будет курятник. Из журнала Reader's Digest ВВЕДЕНИЕ Данная глава посвящена важнейшему разделу информатики - программированию ЭВМ. В ней рассматриваются конкретные языки программирования, являющиеся наиболее употребимыми в настоящее время и отражающие различные тенденции в современном программировании. По каждому из языков приводятся необходимые сведения и примеры, чтобы сложилась общая картина, и стало возможным самостоятельное решение относительно несложных задач по программированию. При необходимости изучить тот или иной язык «полностью» (задача эта весьма неопределенная хотя бы из-за наличия у 10 каждого языка многих версий, особенностей трансляторов, интерфейсных оболочек и т.д.) необходимо обратиться к специальной литературе. Наибольшее внимание уделено языку Паскаль. Он заслуженно является наиболее популярным при традиционном – процедурном – подходе к программированию, пригоден для разработки прикладных программ для самых различных предметных областей. Именно на базе Паскаля создана одна из наиболее мощных сред объектноориентированного программирования, что является дополнительным стимулом к его более детальному изучению. § 1. ИСТОРИЯ РАЗВИТИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ Одной из самых революционных идей, приведших к созданию автоматических цифровых вычислительных машин, была высказанная в 20-х годах XIX века Ч. Бэббиджем мысль о предварительной записи порядка действий машины для последующей автоматической реализации вычислений - программе. И, хотя использованная Бэббиджем запись программы на перфокартах, придуманная для управления ткацкими станками французским изобретателем Жозефом Мари Жаккаром, технически не имеет ничего общего с современными приемами хранения программ в ЭВМ, принцип здесь по существу один. С этого момента начинается история программирования. Аду Лавлейс, одну из немногих современников Чарльза Бэббиджа, кто сумел по достоинству оценить аналитическую машину, называют первым в мире программистом. Она теоретически разработала некоторые приемы управления последовательностью вычислений, которые используются в программировании и по сей день, описала одну из важнейших конструкций практически любого современного языка программирования – цикл. Революционным моментом в истории языков программирования стало появление системы кодирования машинных команд с помощью специальных символов, предложенной Джоном Моучли, сотрудником Пенсильванского университета. Система кодирования, предложенная Моучли, увлекла одну из сотрудниц его компании – Грейс Мюррей Хоппер, которая посвятила всю свою жизнь компьютерам и программированию. Она вспоминает, что стала «третьим в мире программистом первого в мире большого цифрового компьютера». Г.Хоппер доказала, чего она стоит как программист. Впоследствии она писала: «Я имела то преимущество, что изучала как технику, так и математику и знала, как работает машина от начала и до конца». При работе на компьютере «Марк-I» Г.Хоппер и ее группе пришлось столкнуться со многими проблемами и все, что ими придумано, было впервые. В частности они придумали подпрограммы. Сейчас любой программист, не задумываясь, использует аппарат подпрограмм в любом языке программирования. И еще одно фундаментальное понятие техники программирования впервые ввели Г.Хоппер и ее группа - «отладка». Однажды жарким летним днем 1945 г. неожиданно произошла остановка компьютера «Марк-I». Обнаружилась неисправность одного реле, контакты которого были заблокированы мотыльком, залетевшим неизвестно каким образом в помещение вычислительного центра. Вспоминает Г.Хоппер: «Когда к нам зашел офицер, чтобы узнать, чем мы занимаемся, мы ответили, что очищаем компьютер от насекомых (debuging)». С тех пор термин «debuging» (отладка) используется в технических процессах тестирования неисправностей в компьютере, а также в системах программирования. На заре компьютерной эры машинный код был единственным средством общения человека с компьютером. Огромным достижением создателей языков программирования было то, что они сумели заставить сам компьютер работать переводчиком с этих языков на машинный код. В конце 40-х годов, до прихода Г.Хоппер в фирму Джона Моучли, последний создал систему под названием «Short Code», которая являлась примитивным языком программирования высокого уровня. В ней программист записывал решаемую задачу в виде математических формул, а затем, используя специальную таблицу, переводил символ за символом, преобразовывал эти формулы в двухлитерные коды. В дальнейшем специальная программа компьютера превращала эти коды в двоичный машинный код. Систе- 11 ма, разработанная Дж. Моучли, была по существу одним из первых примитивных интерпретаторов. Уже в 1951 г. Хоппер создала первый в мире компилятор и ею же был введен сам этот термин. Компилятор Хоппер осуществлял функцию объединения команд и в ходе трансляции производил организацию подпрограмм, выделение памяти компьютера, преобразование команд высокого уровня (в то время псевдокодов) в машинные команды. «Подпрограммы находятся в библиотеке (компьютера), когда вы подбираете материал из библиотеки – это называется компиляцией» - так она объясняла происхождение введенного ею термина. В 1954 г. группа под руководством Г.Хоппер разработала систему, включающую язык программирования и компилятор, которая в дальнейшем получила название MATHMATIC. После удачного завершения работ по созданию МАТН-MATIC Г.Хоппер и ее группа принялись за разработку нового языка и компилятора, который позволил бы пользователям программировать на языке, близком к обычному английскому. Необходимость появления подобной системы Хоппер объясняла следующим образом: «Существует много различных людей, которым нужно решать разные задачи. Некоторые из них связаны с обработкой символов, другие – с обработкой слов, и им нужны языки другого типа, а не наши попытки превратить их всех в математиков». В 1958 г. появился компилятор FLOW-MATIC. В отличие от ФОРТРАНа – языка для научных приложений – FLOW-MATIC был первым языком для задач обработки коммерческих данных. Работы в этом направлении привели к созданию языка КОБОЛ (COBOL – Common Business Oriented Language). Одним из основных консультантов при создании этого языка была Грейс Мюррей Хоппер. Середина 50-х годов характеризуется стремительным прогрессом в области программирования. Роль программирования в машинных командах стала уменьшать. Начали появляться языки программирования нового типа, выступающие в роли посредника между машинами и программистами. Первым и одним из наиболее распространенных был Фортран (FORTRAN, от FORmula TRANslator - переводчик формул), разработанный группой программистов фирмы IBM в 1954 г. (первая версия). В середине 60-х годов сотрудники математического факультета Дартмутского колледжа Томас Курц и Джон Кемени создали специализированный язык программирования, который состоял из простых слов английского языка. Новый язык назвали «универсальным символическим кодом для начинающих» (Beginners All-Purpose Symbolic Instruction Code, или, сокращенно, BASIC). Годом рождения нового языка можно считать 1964 г. Сегодня универсальный язык Бейсик (имеющий множество версий) приобрел большую популярность и получил широкое распространение среди пользователей ЭВМ различных категорий во всем мире. В значительной мере этому способствовало то, что Бейсик начали использовать как встроенный язык персональных компьютеров, широкое распространение которых началось в конце 70-х годов. В начале 60-х годов все существующие языки программирования высокого уровня можно было пересчитать по пальцам, однако впоследствии их число достигло трех тысяч. Разумеется, подавляющая часть языков не получила сколько-нибудь широкого распространения; в практической деятельности используется не более двух десятков. Разработчики ориентировали языки на разные классы задач, в той или иной мере привязывали их к конкретным архитектурам ЭВМ, реализовывали личные вкусы и идеи. В 60-е годы были предприняты попытки преодолеть эту «разноголосицу» путем создания универсального языка программирования. Первым детищем этого направления стал PL/1 (Programm Language One), 1967 г. Затем на эту роль претендовал АЛГОЛ-68 (1968 г.). Предполагалось, что подобные языки будут развиваться и усовершенствоваться и вытеснят все остальные. Однако ни одна из этих попыток на сегодняшний день не увенчалась успехом (хотя PL/1 в усеченных версиях использовали многие программисты). Всеохватность языка приводила к неоправданной, с точки зрения программиста, сложности конструкций, неэффективности компиляторов. Языки программирования служат разным целям, и их выбор определяется удобностью пользователя, пригодностью для данного компьютера и данной задачи. А задачи для компьютера бывают самые разнообразные: вычислительные, экономические, графические, экспертные и т.д. Такая разнотипность решаемых ком- 12 пьютером задач и определяет многообразие языков программирования. По всей видимости, в программировании наилучший результат достигается при индивидуальном подходе, исходящем из класса задачи, уровня и интересов программиста. Например, Бейсик широко употребляется при написании простых программ; Фортран является классическим языком программирования при решении на ЭВМ математических и инженерных задач; язык Кобол (COBOL, от Common Business Oriented Language – общий язык, ориентированный на деловые задачи; создан в 1960 г.) был задуман как основной язык для массовой обработки данных в сферах управления и бизнеса. Еще более специализированным является язык ЛОГО (от греческого logos - слово), созданный для обучения программированию школьников профессором математики и педагогики Сеймуром Пейпертом из Массачусетского технологического института. Обучаясь программированию на ЛОГО, дети задают простые команды, которые управляют игрушечной черепашкой, снабженной карандашиком. Отметим и еще один достаточно популярный специализированный язык – Пролог (Prolog – PROgramming in LOGic), разработанный как язык программирования для создания систем искусственного интеллекта. В конце 50-х годов плодом международного сотрудничества в области программирования явился Алгол (ALGOL, от ALGOrithmic Language – алгоритмический язык). Алгол предназначен для записи алгоритмов, которые строятся в виде последовательности процедур, применяемых для решения поставленных задач. Специалисты-практики восприняли этот язык далеко неоднозначно, но, тем не менее, его влияние на развитие других языков и теорию программирования оказалось весьма значительным. В нашей стране в те годы был создан под руководством Сергея Петровича Ершова транслятор Альфа, который представлял довольно удачную русифицированную версию Алгола. Впоследствии академик Ершов сыграл важнейшую роль в становлении в СССР школьной информатики. Развитие идеи Алгола о структуризации разработки алгоритмов нашло наивысшее отражение при создании в начале 70-х годов языка Паскаль швейцарским ученым Николаусом Виртом. Язык Паскаль первоначально разрабатывался как учебный, и, действительно, сейчас он является одним из основных языков обучения программированию в школах и вузах. Однако качества его в совокупности оказались столь высоки, что им охотно пользуются и профессиональные программисты. Не менее впечатляющей, в том числе и финансовой, удачи добился джазист Филип Кан, француз, разработавший систему Турбо-Паскаль. Суть его идеи состояла в объединении последовательных этапов обработки программы – компиляции, редактирования связей, отладки и диагностики ошибок – в едином интерфейсе. Версии Турбо-Паскаля заполонили практически все образовательные учреждения, программистские центры и частные фирмы. Период с конца 60-х и до начала 80-х годов характеризуется бурным ростом числа различных языков программирования, сопровождавшим, как это ни парадоксально, кризис программного обеспечения. Этот кризис особо остро переживало военное ведомство США. В январе 1975 г. Пентагон решил навести порядок в хаосе трансляторов и учредил комитет, которому было предписано разработать один универсальный язык. На конкурсной основе комитет проработал сотни проектов и, когда стало ясно, что ни один из существующих языков не может их удовлетворить, принял два проекта для окончательного рассмотрения. В мае 1979 г. был объявлен победитель – группа ученых во главе с Жаном Ихбиа. Победивший язык окрестили АДА, в честь Огасты Ады Лавлейс. Язык АДА – прямой наследник языка Паскаль. Этот язык предназначен для создания и длительного (многолетнего) сопровождения больших программных систем, допускает возможность параллельной обработки, управления процессами в реальном времени и многое другое, чего трудно или невозможно достичь средствами более простых языков. Большой отпечаток на современное программирование наложил язык Си (первая версия – 1972 г.), являющийся очень популярным в среде разработчиков систем программного обеспечения (включая операционные системы). Си сочетает в себе черты, как языка высокого уровня, так и машинно-ориентированного языка, допуская программиста ко всем машинным ресурсам, чего не обеспечивают такие языки как Бейсик и Паскаль. Следует отметить, что многие языки, первоначально разработанные для больших и 13 малых ЭВМ, в дальнейшем были приспособлены к персональным компьютерам. Хорошо вписались в «персоналки» не только Паскаль, Бейсик, Си, Лого, но и ЛИСП, ПРОЛОГ – языки искусственного интеллекта. В течение многих лет программное обеспечение строилось на основе операциональных и процедурных языков, таких как Фортран, Бейсик, Паскаль, Ада, Си. И сегодня современные версии этих и им подобных языков (Модула, Форт и др.) доминируют при разработке прикладных программных средств. Однако по мере эволюции языков программирования получили широкое распространение и другие, принципиально иные, подходы к созданию программ. Классическое операциональное и/или процедурное программирование требует от программиста детального описания того, как решать задачу, т.е. формулировки алгоритма и его специальной записи. При этом ожидаемые свойства результата обычно не указываются. Основные понятия языков этих групп – оператор и данные. При процедурном подходе операторы объединяются в группы – процедуры. Структурное программирование в целом не выходит за рамки этого направления, оно лишь дополнительно фиксирует некоторые полезные приемы технологии программирования. Принципиально иное направление в программировании связано с методологиями (иногда говорят «парадигмами») непроцедурного программирования. К ним можно отнести объектно-ориентированное и декларативное программирование. Объектноориентированный язык создает окружение в виде множества независимых объектов. Каждый объект ведет себя подобно отдельному компьютеру, их можно использовать для решения задач как «черные ящики», не вникая во внутренние механизмы их функционирования. Из языков объектного программирования, популярных среди профессионалов, следует назвать прежде всего С++, для более широкого круга программистов предпочтительны среды типа Delphi и Visual Basic. При использовании декларативного языка программист указывает исходные информационные структуры, взаимосвязи между ними и то, какими свойствами должен обладать результат. При этом процедуру его получения («алгоритм») программист не строит (по крайней мере, в идеале). В этих языках отсутствует понятие «оператор» («команда»). Декларативные языки можно подразделить на два семейства – логические (типичный представитель – Пролог) и функциональные (Лисп). По всей видимости, непроцедурные языки имеют большое будущее. Все сказанное выше можно отобразить схемой – крупноструктурной классификацией языков программирования. В ней указаны основные методологии программирования; в нижнем ряду, в скобках – типичные языки соответствующих групп. § 2. ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ 2.1. Понятие о языках программирования высокого уровня Языки программирования – это формальные языки специально созданные для общения человека с компьютером. Каждый язык программирования, равно как и «естествен- 14 ный» язык (русский, английский и т.д.), имеет алфавит, словарный запас, свои грамматику и синтаксис, а также семантику. Алфавит – фиксированный для данного языка набор основных символов, допускаемых для составления текста программы на этом языке. Синтаксис – система правил, определяющих допустимые конструкции языка программирования из букв алфавита. Семантика – система правил однозначного толкования отдельных языковых конструкций, позволяющих воспроизвести процесс обработки данных. При описании языка и его применении используют понятия языка. Понятие подразумевает некоторую синтаксическую конструкцию и определяемые ею свойства программных объектов или процесса обработки данных. Взаимодействие синтаксических и семантических правил определяют те или иные понятия языка, например, операторы, идентификаторы, переменные, функции и процедуры, модули и т.д. В отличие от естественных языков правила грамматик и семантики для языков программирования, как и для всех формальных языков, должны быть явно, однозначно и четко сформулированы. Языки программирования, имитирующие естественные языки, обладающие укрупненными командами, ориентированными на решение прикладных содержательных задач, называют языками «высокого уровня». В настоящее время насчитывается несколько сотен таких языков, а если считать и их диалекты, то это число возрастет до нескольких тысяч. Языки программирования высокого уровня существенно отличаются от машинноориентированных (низкого уровня) языков. Во-первых, машинная программа, в конечном счете, записывается с помощью лишь двух символов 0 и 1. Во-вторых, каждая ЭВМ имеет ограниченный набор машинных операций, ориентированных на структуру процессора. Как правило, этот набор состоит из сравнительно небольшого числа простейших операций, типа: переслать число в ячейку; считать число из ячейки; увеличить содержимое ячейки на +1 и т.п. Команда на машинном языке содержит очень ограниченный объем информации, поэтому она обычно определяет простейший обмен содержимого ячеек памяти, элементарные арифметические и логические операции. Команда содержит код и адреса ячеек, с содержимым которой выполняется закодированное действие. Языки программирования высокого уровня имеют следующие достоинства: • алфавит языка значительно шире машинного, что делает его гораздо более выразительным и существенно повышает наглядность и понятность текста; • набор операций, допустимых для использования, не зависит от набора машинныx операций, а выбирается из соображений удобства формулирования алгоритмов решения задач определенного класса; • конструкции команд (операторов) отражают содержательные виды обработки данных и задаются в удобном для человека виде; • используется аппарат переменных и действия с ними; • поддерживается широкий набор типов данных. Таким образом, языки программирования высокого уровня являются машиннонезависимыми и требуют использования соответствующих программ-переводчиков (трансляторов) для представления программы на языке машины, на которой она будет исполняться. 2.2. Метаязыки описания языков программирования Интерпретация конструкций языка программирования должна быть абсолютно однозначной, ибо фраза на языке программирования превращается в машинный код автоматически, с помощью программы-транслятора, и любой намек на неоднозначность либо делает эту фразу непереводимой, либо приводит к ошибке. В этом отношении языки программирования значительно отличаются от естественных языков, допускающих неоднозначно интерпретируемые фразы, рассчитанные на здравый смысл и жизненный опыт человека – слушателя и исполнителя, способного додумать содержание фразы. «Додумывание» не входит в способности компьютеров, поэтому необходимы приемы описания 15 конструкций языков программирования типа: «Оператором присваивания называется...», причем продолжение подобной фразы на естественном языке чаще всего оказывается либо слишком громоздким, либо неоднозначным, либо и тем, и другим одновременно. Для строгого и точного описания синтаксиса языка программирования, как правило, используют специальные метаязыки (языки для описания других языков). Наиболее распространенными метаязыками являются металингвистические формулы Бэкуса - Наура (язык БНФ) и синтаксические диаграммы Вирта. Язык БНФ (называемый также языком нормальных форм) представляет компактную форму в виде некоторых формул, похожих на математические. Для каждого понятия языка существует единственная метаформула (нормальная форма). Она состоит из левой и правой частей. В левой части указывается определяемое понятие, а в правой - задается множество допустимых конструкций языка, которые объединяются в это понятие. В формуле используют специальные метасимволы в виде угловых скобок, в которых заключено определяемое понятие (в левой части формулы) или ранее определенное понятие (в ее правой части), а разделение левой и правой частей указывается метасимволом «::=», смысл которого эквивалентен словам "по определению есть». Например, метаформулы <переменная>::=А|В <выражение>::=<переменная>|<переменная>+ <переменная>|<переменная>-<переменная> означают, что в том (сугубо модельном) языке, на который эта метаформула распространяется, под термином <переменная> понимается любая из букв А или В, а под термином <выражение> - любая из следующих десяти записей: А; В; А+А; А+В; В+А; В+В; АА; А-В; В-А; В-В. Знак | следует читать «или». Правая часть метаформулы может содержать правило построения допустимых последовательностей. Допускаются рекурсивные определения терминов и понятий, т.е. когда в правой части формулы участвует понятие, определяемое левой частью. Например, пусть необходимо ввести понятие <двоичный код>, под которым понимается любая непустая последовательность цифр 0 и 1. Тогда простое и компактное рекурсивное определение с помощью метаформул выглядит так: <двоичная цифра>::= 0 | 1 <двоичный код>::=<двоичная цифра>|<двоичный код> <двоичная цифра> Рекурсия здесь не мешает конструктивному построению понятия <двоичный код>, так как по принятым правилам при первом обращении к рекурсивно определяемому понятию следует ограничиться нерекурсивной частью формулы, т.е. под двоичным кодом понимать двоичную цифру - 0 или 1. Но при втором обращении к метаформуле, определяющей двоичный код, мы имеем варианты (конечно, неполные) понятия <двоичный код>, и можем применить рекурсию, которая даст нам следующие варианты этого понятия: 0 1 00 01 10 11, т.е. все возможные одно- и двухцифровые двоичные коды. Очевидно, что при следующих применениях рекурсии мы получим любой возможный двоичный код. Для задания синтаксических конструкций произвольной длины часто используют фигурные скобки как метасимволы. Фигурные скобки означают, что конструкция может повторяться нуль или более раз. В частности, термин <двоичный код> можно определить по другому, а именно: <двоичный код>::=<двоичная цифра><двоичная цифра> И еще, для полноты множества синтаксических конструкций, необходимо определить конструкцию <пусто>: <пусто>::= . В большинстве учебных пособий по программированию, технических описании языков, метаформулы рассматриваемого языка представлены полностью. Синтаксическая диаграмма является графическим представлением значения метапеременной метаязыка. Диаграмма состоит из основных символов или понятий языка. Каждая диаграмма имеет входящую и выходящую стрелки, означающие начало и конец синтаксической конструкции и отражающие процесс ее чтения и анализа. Из каждого элемента выходит одна или несколько стрелок, указывающих на те элементы, которые могут следовать непосредственно за данным элементом. Для сравнения с метаформулами приведем несколько примеров. 16 Синтаксическая диаграмма Читатель может поупражняться в составлении синтаксических диаграмм для известных ему языков программирования. Металингвистические формулы в некотором виде заложены в трансляторы; с их помощью ведется проверка конструкций, используемых программистом, на формальное соответствие какой-нибудь из конструкций, синтаксически допустимых в этом языке (синтаксический контроль). 2.3. Грамматика языков программирования Описанию грамматики языка предшествует описание его алфавита. Алфавит любого языка состоит из фиксированного набора символов, однозначно трактуемых. Алфавит языков программирования, как правило, связан с литерами клавиатуры печатной машинки. Клавиатуры персональных компьютеров близки к ним по наличию литер. Алфавиты большинства языков программирования близки друг другу и основываются на буквах латинского алфавита, арабских цифрах и общепринятых спецсимволах, таких как знаки препинания, математических операций, сравнений и обозначений. Большинство популярных языков программирования в своем алфавите содержат следующие элементы: <буква> : : = AaBbCcDdEeFf и т.д. <цифра> :: = 0123456789 <знак арифметической операции >:: = */ + <разделитель> :: = .,;:()[]{}': = <служебное слово> : : = begin end if then else for next и т.д. <спецсимвол> :: = <знак арифметической операции> | <разделитель> | <служебное слово> <основной символ>::=<буква> | <цифра> | <спецсимвол> <комментарий>::=<любая последовательность символов> Несмотря на значительные различия между языками программирования, ряд фундаментальных понятий в большинстве из них схожи. Приведем часть этих понятий. Оператор - одно из ведущих понятий всех языков программирования (теоретически за исключением чисто декларативных; но в действительности и они используют родственное понятие). Каждый оператор представляет собой законченную фразу языка и определяет однозначно трактуемый этап обработки данных. В соответствии с теорией алгоритмов выделяют основные (базисные) операторы языка: присвоения, условный и безусловный переход, пустой оператор. К производным, не основным, относят составной оператор, оператор выбора, оператор цикла и оператор присоединения. Все операторы языка в тексте программы отделяются друг от друга явными или неявными разделителями, например: S1; S2;...; SN Операторы выполняются в порядке их следования в тексте программы. Лишь с помощью операторов перехода этот естественный порядок может быть нарушен. Большая часть операторов ведет обработку величин. Величины могут быть постоянными и переменными. Значения постоянных величин не изменяются в ходе выполнения программы. Величина характеризуется типом, именем и значением. Наиболее распространенные типы величин – числовые (целые и вещественные), символьные, логические. Тип величины определяется ее значением. 17 Другая важная классификация величин – простые и структурированные. Простая величина в каждый момент может иметь не более одного значения. Ей соответствует одна ячейка памяти (поскольку термин «ячейка» несколько устарел, часто говорят «машинное слово») или ее эквивалент во внешней памяти компьютера. Структурированная величина, имея одно имя, может иметь разом несколько значений. Эти значения представляют собой элементы (компоненты) величины. Самый широкоизвестный пример – массив, у которого элементы различаются по индексам (номерам). Вопрос о структурировании величин - входных, выходных и промежуточных – для успеха решения прикладной задачи не менее важен, чем вопрос о правильном написании последовательности операторов. Важнейшие характеристики структурированной величины таковы: упорядоченность (да или нет), однородность (да или нет), способ доступа к элементам, фиксированность числа элементов (да или нет). Так, массив является упорядоченной однородной структурой с прямым доступом к элементам и фиксированным их количеством. Всем программным объектам в языках даются индивидуальные имена. Имя программного объекта называют идентификатором (от слова «идентифицировать»). Чаще всего идентификатором является любая конечная последовательность букв и цифр, начинающаяся с буквы: <идентификатор>::=<буква> | <идентификатор> | <буква>| <идентификатор><цифра> Как правило, в большинстве языков программирования в качестве идентификатора запрещается использовать служебные слова языка. Многим слово «идентификатор» не нравится, и в настоящее время чаще употребляют слово «имя», поскольку <имя>::=<идентификатор>. Программисты выбирают имена по своему усмотрению. Принципы выбор назначения имен программным объектам естественны. Следует избегать мало выразительных обозначений, не гоняться за краткими именами. Имена должны быть понятны, наглядны, отражать суть обозначаемого объекта. Например, Summa, Time, i, j, integral, init и т.п. Некоторым идентификаторам заранее предписан определенный смысл и их называют стандартными, например, Sin – это имя известной математической функции. Описания или объявления программных объектов связаны с правилами обработки данных. Данные бывают разные и необходимо для каждого из них определить его свойства. Например, если в качестве данных выступает массив, то необходимо задать его размерность, границы индексов, тип элементов массив. Описательная часть языка программирования является необходимой как для системных программистов - разработчиков трансляторов, которые должны, в частности, проводить синтаксическую и семантическую диагностику программ, - так и для «прикладного» программиста, которому объявления программных объектов часто облегчают процесс разработки и отладки программ. В некоторых языках стандартные описания простых числовых и символьных данных опускают (описания по умолчанию), или в них задаются правила описания по имени объекта. Например, в Фортране переменные, имена которых начинаются с букв I, J, K, L, M, N, могут принимать целые значения (при отсутствии явного описания типа, которое возможно), т.е. определены как числовые данные целого типа. В Бейсике-MSX данные строкового типа присваиваются переменным, имена которых заканчиваются специальным символом $: А$, Sl$. Особый интерес представляют в языках программирования описания нестандартных структур данных, таких как запись, файл, объект, список, дерево и т.п. Приведем список наиболее употребительных обозначений типов данных, используемых в описаниях: Целый - Integer Вещественный - Real Логический - Boolean Символьный - Char Строковый - String Массив -Array Множество - Set 18 Файл - File Запись - Record Объект - Object Переменные играют важнейшую роль в системах программирования. Понятие «переменная» в языках программирования отличается от общепринятого в математике. Переменная - это программный объект, способный принимать некоторое значение с помощью оператора присваивания. В ходе выполнения программы значения переменной могут неоднократно изменяться. Каждая переменная после ее описания отождествляется с некоторой ячейкой памяти, содержимое которой является ее значением. Синтаксис переменной, точнее, ее идентификатора, как правило, имеет вид: <имя переменной>::= →<буква>→ →<буква>→ →<цифра>→ →<спецсимвол→ Семантический смысл переменной заключается в хранении некоторого значения, соответствующего ее типу (например, переменная целого типа может принимать значение произвольного целого числа), а также в выполнении с ней операций пересылки в нее и извлечения из нее этого значения. Функция - программный объект, задающий вычислительную процедуру определения значения, зависимого от некоторых аргументов. Вводится в языки программирования для задания программистом необходимых ему функциональных зависимостей. В каждом языке высокого уровня имеется в наличии библиотека стандартных функций: арифметических, логических, символьных, файловых и т.п. Функции - стандартные и задаваемые программистом - используются в программе в выражениях. Выражения строятся из величин - постоянных и переменных, функций, скобок, знаков операций и т.д. Выражение имеет определенный тип, определяемый типом, принимаемых в итоге его вычисления значений. Возможны выражения арифметические, принимающие числовые значения, логические, символьные, строковые и т.д. Выражение 5 + 7 является, несомненно, арифметическим, выражение А + В может иметь самый разный смысл - в зависимости от того, что стоит за идентификаторами А и В. Процедура - это программный объект, представляющий некоторый самостоятельный этап обработки данных. По сути, процедуры явились преемниками подпрограмм, которые были введены для облегчения разработки программ еще на самых ранних стадиях формирования алгоритмических языков. Процедура имеет входные и выходные параметры, называемые формальными. При использовании процедуры формальные параметры заменяются на фактические. Модуль (Unit) - это специальная программная единица, предназначенная для создания библиотек и разделения больших программ на логически связанные блоки. По сути, модуль - это набор констант, типов данных, переменных, процедур и функций. В состав модуля входят разделы: заголовок,, интерфейс, реализация, инициализация. Заголовок необходим для ссылок на модуль. Интерфейс содержит объявления, включая процедуры и функции. Раздел «реализация» содержит тела процедур и функций, перечисленных в интерфейсной части. Раздел «инициализация» содержит операторы, необходимые для инициализации модуля. Каждый модуль компилируется отдельно, и каждый элемент модуля можно использовать в программе без дополнительного объявления. [2] 19 5. АЛГОРИТМИЗАЦИЯ ЯЗЫКИ И ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ 5.1. Языки программирования высокого уровня 5.1.1. Эволюция и классификация языков программирования Для первых вычислительных машин составление программ велось исключительно на машинных языках, которые представляли собой свод правил кодирования инструкций для ЭВМ с помощью чисел. Более высоким уровнем по сравнению с машинными языками являются машинноориентированные языки символического кодирования. Основной принцип создания языков символьного кодирования состоит в замене машинных кодов на их буквенные обозначения, а также в автоматизации процесса распределения памяти и диагностики ошибок. Такой машинно-ориентированный язык получил название языка Ассемблера. Недостатком машинно-ориентированных языков является невозможность использования программ, написанных для процессоров одного типа, на ЭВМ, которые построены на процессорах другого типа. Машинные и машинно-ориентированные языки относятся к языкам низкого уровня. Эти языки используются для системного программирования. На следующем уровне развития языков программирования находятся процедурноориентированные языки. В отличие от машинно-ориентированных языков синтаксис и семантика этих языков не зависят от состава имеющихся команд конкретной ЭВМ. привязку составленной программы к конкретному типу ЭВМ осуществляет транслятор (программа-переводчик). Процедурно-ориентированные языки относятся к языкам высокого уровня. Одним из первых процедурно-ориентированных языков стал Фортран (1958 г.) (FORmula TRANslation – преобразование формул). Фортран до сих пор применяется в сфере научных и инженерно-технических вычислений. Процедурно-ориентированные языки, предназначенные для реализации определенных алгоритмов, называются алгоритмическими. Первым алгоритмическим языком принято считать Алгол (1960 г.) (ALGOL – ALGOritmic Language – алгоритмический язык). алгоритмический язык Бэйсик (1965 г.) (BASIC – Beginners All-purpose Symbolic Instruction Code) был предназначен для пользователей непрофессионалов, т.е. тех людей, у которых основная профессия не связана с программированием. Следующим этапом развития программирования принято считать структурное программирование, которое обеспечило возможность коллективной работы программистов над созданием сложных программных комплексов. Примерами таких языков могут служить Паскаль (1971 г.) и С (1973 г.). Паскаль (Pascal) – это хорошо структурированный язык, который был разработан Н. Виртом специально для обучения студентов программированию. Язык С, созданный Д. Ричи при разработке операционной системы Unix, считается одним из самых популярных языков программирования. Объектный подход является следующей ступенью в развитии структурного программирования. Первым объектно-ориентированным языком программирования был язык Симула (1967 г.), который предназначался для решения задач моделирования. Почти все современные языки программирования являются объектноориентированными. Например, на базе языка Паскаль была создана объектноориентированная среда разработки Дельфи (1995 г.), на базе С – С++ (1980 г.), на базе Бэйсика – Visual Basic (1991 г.). 5.1.2. Специализированные языки Для решения экономических задач в 1961 г. был создан язык Кобол (COBOL - Common Business Oriented Language). Считается, что Кобол был первым языком, предназначенным для работы с базами данных. Все реляционные СУБД (системы управления базами данных) используют структурированный язык запросов (SQL – Structured Query Language). Первоначально SQL был разработан фирмой IBM для работы с базами данных на больших ЭВМ. Затем SQL был принят в качестве национального стандарта США, а с 1987 г. – в качестве международного стандарта работы с реляционными базами 20 данных. Языки Лисп (Lisp – LIST Processing) 1960 г. и Пролог 1978 были разработаны для решения задач, относящихся к искусственному интеллекту. Язык Пролог является непроцедурным языком логического программирования. Пролог относят к декларативным языкам высокого уровня. В декларативных языках даются описания исходных данных и правила вывода на их основе новых данных. Язык Лисп относится к непроцедурным языкам функционального программирования, в котором вычисления производятся на основе вызова множества связанных функций. В настоящее время интерес к Лиспу связан с тем, что на базе одного из диалектов языка (АвтоЛисп) разработана популярная графическая система Автокад. Развитие интернет-технологий послужило причиной создания целой серии языков. Язык гипертекстовой разметки HTML (HTML – HyperText Markup Language) был создан в 1989 году для разработки веб-страниц. Результирующий документ, составленный на языке HTML, кроме текста может содержать иллюстрации, аудио- и видео- материалы. Для придания веб-страницам интерактивности используется язык PERL (Practical Extraction and Report). С помощью этого языка веб-дизайнеры реализуют чаты, поисковые системы, доски объявлений и др. Эти же задачи можно решать с помощью скриптовых (сценарных) языков JavaScript и VBScript, которые называются клиентскими скриптовыми языками, потому что написанные на них программы при работе в Интернете пересылаются с сервера на машину клиента и интерпретируются браузером. В настоящее время JavaScript могут интерпретировать все браузеры, а VBScript – только Internet Explorer. Язык PHP (Plug and Play) – это пример серверного скриптового языка. Тексты на этом языке тоже встраиваются в веб-страницы, но интерпретация осуществляется на сервере до пересылки страницы на клиентскую машину. Язык Java предназначен для составления программ, которые работаю в сети. программы, написанные на языке Java, используются для создания динамической рекламы. Язык Java относится к объектно-ориентированным языкам. Синтаксис языка во многом похож на язык С++. 5.1.3. Основные понятия алгоритмических языков программирования Основу любого языка (естественного и искусственного) составляет алфавит – это совокупность символов, используемых в языке. Из алфавита формируется словарь (конструкции) алгоритмического языка, которым пользуются при составлении программы. Простейшими конструкциями алгоритмического языка являются константы, переменные, функции, выражения, операторы. Константы и переменные – слова пользователей, описывающие информацию. Слова пользователей для обозначения данных называют именами данных, или идентификаторами. Функции, выражения и операторы – служебные слова, означающие действия, выполняемые над информацией. Служебные слова языка программирования называются ключевыми. Имена данных не должны совпадать с ключевыми словами. Константы – данные, неизменяемые в процессе выполнения программы. К константам можно отнести явно заданные в программе числа и текст. Переменные – данные, значения которых меняются в ходе выполнения программы. Выражения – конструкции языка, предназначенные для проведения в программе арифметических действий с переменными и константами. Выражения могут включать функции. Функции отличаются от процедур тем, что они возвращают значение и поэтому могут входить в выражения. В любой среде программирования есть богатый набор встроенных функций. Операторы – конструкции языка, указывающие на действия, которые должен выполнить компьютер. Данные, входящие в состав операторов, называются операндами. 21 5.1.4. Типы данных Во время выполнения программы данные хранятся в оперативной памяти компьютера. В каждом языке программирования есть разделы описания данных. Специальные операторы резервируют место для хранения данных. Для этого необходимо задать тип данных. Каждый тип данных характеризуется размером (количеством байт), требуемым для хранения значений данных, и диапазоном допустимых значений. Примеры основных типов данных Visual Basic приведены в табл. 6.1. Таблица 6.1 – Примеры основных типов данных Visual Basic Тип данных Размер, байт Диапазон допустимых значений Byte (байт) 1 Целые положительные числа от 0 до 255 Integer (целое) 2 Целые числа от -32 768 до 32 767 Long (длинное це4 Целые числа от -2 147 483 648 до 2 147 483 лое) 648 Char (символьный) 1 Символы – 256 Boolean 1 True (1) и False (0) (логический) Особым типом данных является указатель (ссылка), который служит для хранения адреса области памяти. 5.1.5. Структуры данных Данные могут объединяться в структуры. Данные, объединенные в структуры, называют составными данными. Массив – это упорядоченный набор однотипных данных. Массив обозначается именем, а элемент массива – порядковым номером. Массив характеризуется параметрами: размерностью и индексом. В общем случае массивы могут быть многомерными. Индекс служит для обращения к элементу данных. Пример. А[5] (индекс=5) – пятый элемент одномерного массива А. B[2,5] (первый индекс=2, второй индекс=5) – пятый элемент во второй строке массива В. Запись – объединяет разнотипные данные, описывающие один объект или процесс. Отдельные данные записи называются полями. Если в процессе обработки данных размер структуры изменяется, то она называется динамической структурой. Стек – это динамическая структура данных, при которой включение и исключение данных из структуры возможно только на одном конце стека, называемом вершиной. Такой принцип работы стека имеет название «последним пришел – первым вышел» (Last In Fist Out, LIFO). Очередь – это динамическая структура данных, при которой исключение элементов из структуры производится из начала очереди, а включение данных в конце очереди. такой принцип работы очереди имеет название «первым пришел – первым вышел» (First In First Out, FIFO). Доступ к элементам очереди осуществляется по указателям начала и конца очереди. В зависимости от способа межэлементной связи различают линейные и нелинейные структуры. К линейным (или последовательным) структурам данных относятся: массив, запись, стек и очередь, к нелинейным структурам данных: список. Для связи элементов списка используются указатели, в которых хранятся адреса следующих элементов списка. Списки относятся к динамическим структурам, в которых можно произвольным образом менять структуру, в частности, исключать и добавлять элементы, а также объединять списки. Графическим представлением списка является ориентированный граф, в его вершинах содержаться данные, а дуги графа являются указателями (рис. 6.1). 22 Рис. 6.1 [3] Введение. Развитие вычислительной техники сопровождается созданием новых и совершенствованием существующих средств общения программистов с ЭВМ - языков программирования (ЯП). Под ЯП понимают правила представления данных и записи алгоритмов их обработки, которые автоматически выполняются ЭВМ. В более абстрактном виде ЯП является средством создания программных моделей объектов и явлений внешнего мира. К настоящему времени созданы десятки различных ЯП от самых примитивных до близких к естественному языку человека. Чтобы разобраться во всем многообразии ЯП, нужно знать их классификацию, а также историю создания, эволюцию и тенденции развития. Настоящая статья и посвящена рассмотрению этих вопросов. Движущие силы эволюции ЯП Чтобы понимать тенденции развития ЯП, нужно знать движущие силы их эволюции. Для выяснения этого вопроса будем рассматривать ЯП с различных точек зрения. Во-первых, ЯП является инструментом программиста для создания программ. Для создания хороших программ нужны хорошие ЯП. Поэтому одной из движущих сил эволюции ЯП является стремление разработчиков к созданию более совершенных программ. Во-вторых, процесс разработки программы можно сравнивать с промышленным производством, в котором определяющими факторами являются производительность труда коллектива программистов, себестоимость и качество программной продукции. Создаются различные технологии разработки программ (структурное, модульное, объектноориентированное программирование и другие), которые должны поддерживаться ЯП. Поэтому второй движущей силой эволюции ЯП является стремление к повышению эффективности процесса производства программной продукции. В-третьих, программы можно рассматривать как аналог радиоэлектронных устройств обработки информации, в которых вместо радиодеталей и микросхем используют конструкции ЯП (элементная база программы). Как и электронные устройства, программы могут быть простейшими (уровня детекторного приемника) и очень сложными (уровня автоматической космической станции), при этом уровень инструмента должен соответствовать сложности изделия. Кроме того, человеку удобнее описывать моделируемый объект в терминах предметной области, а не языком цифр. Поэтому третьей движущей силой, ведущей к созданию новых, специализированных, ориентированных на проблемную область и более мощных ЯП, является увеличение разнообразия и повышение сложности задач, решаемых с помощью ЭВМ. В-четвертых, совершенствование самих ЭВМ приводит к необходимости создания языков, максимально реализующих новые возможности ЭВМ. В-пятых, программы являются интеллектуальным продуктом, который нужно накапливать и приумножать. Но программы, как и технические изделия, обладают свойством морального старения, одной из причин которого является их зависимость от типа ЭВМ и операционной среды. С моральным старением программ борются путем их модернизации и выпуска новых версий, однако при высокой динамике смены типов ЭВМ и операционных сред разработчики будут только тем и заниматься, что модернизировать старые программы. Поэтому, ЯП должен обеспечивать продолжительный жизненный цикл программы, и стремление к этому является пятой движущей силой развития ЯП. 23 История развития ЯП Известно, что первым программистом была женщина - леди Ада Лавлейс, дочь лорда Байрона. Она разрабатывала программы для одного из первых механических компьютеров, созданного в начале XIX века английским ученым Чарльзом Беббиджом. Однако настоящее программирование в современном понимании началось с момента создания первой электронной вычислительной машины. Но теме не менее, имя этой замечательной женщины - Ada - присвоено одному из самых мощных современных ЯП, который является базовым для министерства обороны США. Первые ЭВМ, созданные человеком, имели небольшой набор команд и встроенных типов данных, но позволяли выполнять программы на машинном языке. Машинный язык (МЯ) - единственный язык, понятный ЭВМ. Он реализуется аппаратно: каждую команду выполняет некоторое электронное устройство. Программа на МЯ представляет собой последовательность команд и данных, заданных в цифровом виде. Например, команда вида 1А12 в 16-ричном виде или 0001101000010010 в двоичном виде означает операцию сложения (1А) содержимого регистров 1 и 2. Данные на МЯ представлены числами и символами. Операции являются элементарными и из них строится вся программа. Ввод программы в цифровом виде производился непосредственно в память с пульта ЭВМ либо с примитивных устройств ввода. Естественно, что процесс программирования был очень трудоемким, разобраться в программе даже автору было довольно сложно, а эффект от применения ЭВМ был довольно низким. Этот этап в развитии ЯП показал, что программирование является сложной проблемой, трудно поддающейся автоматизации, но именно программное обеспечение определяет в конечном счете эффективность применения ЭВМ. Поэтому на всех последующих этапах усилия направлялись на совершенствование интерфейса между программистом и ЭВМ языка программирования. Стремление программистов оперировать не цифрами, а символами, привело к созданию мнемонического языка программирования, который называют ассемблером, мнемокодом, автокодом. Этот язык имеет определенный синтаксис записи программ, в котором, в частности, цифровой код операции заменен мнемоническим кодом. Например, команда сложения записывается в виде AR 1,2 и означает сложение (Addition) типа регистррегистр (Register) для регистров 1 и 2. Теперь программа имеет более удобочитаемую форму, но ее не понимает ЭВМ. Поэтому понадобилось создать специальную программу транслятор, который преобразует программу с языка ассемблера на МЯ. Эта проблема потребовала, в свою очередь, глубоких научных исследований и разработки различных теорий, например теорию формальных языков, которые легли в основу создания трансляторов. Практически любой класс ЭВМ имеет свой язык ассемблера. На сегодняшний день язык ассемблера используется для создания системных программ, использующих специфические аппаратные возможности данного класса ЭВМ. Следующий этап характеризуется созданием языков высокого уровня (ЯВУ). Эти языки являются универсальными (на них можно создавать любые прикладные программы) и алгоритмически полными, имеют более широкий спектр типов данных и операций, поддерживают технологии программирования. На этих языках создается неисчислимое множество различных прикладных программ. Принципиальными отличиями ЯВУ от языков низкого уровня являются: • использование переменных; • возможность записи сложных выражений; • расширяемость типов данных за счет конструирования новых типов из базовых; • расширяемость набора операций за счет подключения библиотек подпрограмм; • слабая зависимость от типа ЭВМ. С усложнением ЯП усложняются и трансляторы для них. Теперь в набор инструментов программиста, кроме транслятора, входит текстовый редактор для ввода текста программ, отладчик для устранения ошибок, библиотекарь для создания библиотек программных модулей и множество других служебных программ. Все вместе это называется системой программирования. Наиболее яркими представителями ЯВУ являются FORTRAN, PL/1, Pascal, C, Basic, Ada. 24 Может возникнуть вопрос: почему создано столько различных языков одного класса? Почему нельзя создать один язык на все случаи жизни? Ответ на этот вопрос может быть таким же, как и на вопрос о различных языках народов мира: так уж получилось. Каждый из разработчиков ЯВУ стремился создать самый лучший и самый универсальный язык, который позволял бы быстро получать самые эффективные, надежные и безошибочные программы. Однако в процессе этого поиска выяснилось, что дело не в самом языке, а в технологии его использования. Поэтому дальнейшее развитие языков стало определяться новыми технологиями программирования. Одновременно с развитием универсальных ЯВУ стали развиваться проблемноориентированные ЯП, которые решали экономические задачи (COBOL), задачи реального времени (Modula-2, Ada), символьной обработки ( Snobol), моделирования (GPSS, Simula, SmallTalk), численно-аналитические задачи (Analitic) и другие. Эти специализированные языки позволяли более адекватно описывать объекты и явления реального мира, приближая язык программирования к языку специалиста в проблемной области. Другим направлением развития ЯП является создание языков сверхвысокого уровня (ЯСВУ). На языке высокого уровня программист задает процедуру (алгоритм) получения результата по известным исходным данным, поэтому они называются процедурными ЯП. На ЯСВУ программист задает отношения между объектами в программе, например систему линейных уравнений, и определяет, что нужно найти, но не задает как получить результат. Такие языки еще называют непроцедурными, т.к. сама процедура поиска решения встроена в язык (в его интерпретатор). Такие языки используются, например, для решения задач искусственного интеллекта (Lisp, Prolog) и позволяют моделировать мыслительную деятельность человека в процессе поиска решений. К непроцедурным языкам относят и языки запросов систем управления базами данных (QBE, SQL). Классификация ЯП Исходя из вышесказанного, ЯП можно классифицировать по следующим признакам. 1. По степени ориентации на специфические возможности ЭВМ ЯП делятся на: • машинно-зависимые; • машинно-независимые. К машинно-зависимым ЯП относятся машинные языки, ассемблеры и автокоды, которые используются в системном программировании. Программа на машинно-зависимом ЯП может выполняться только на ЭВМ данного типа. Программа на машиннонезависимом ЯП после трансляции на машинный язык становится машинно-зависимой. Этот признак ЯП определяет мобильность получаемых программ (возможность переноса на ЭВМ другого типа). 2. По степени детализации алгоритма получения результата ЯП делятся на: • языки низкого уровня; • языки высокого уровня; • языки сверхвысокого уровня. 3. По степени ориентации на решение определенного класса задач: • проблемно-ориентированные; • универсальные. 4. По возможности дополнения новыми типами данных и операциями: • расширяемые; • нерасширяемые. 5. По возможности управления реальными объектами и процессами: • языки систем реального времени; • языки систем условного времени. 6. По способу получения результата: • процедурные; • непроцедурные. 7. По типу решаемых задач: 25 • языки системного программирования; • языки прикладного программирования. 8. Непроцедурные языки по типу встроенной процедуры поиска решений делятся на: • реляционные; • функциональные; • логические. Рассмотренная схема классификации позволяет каждому ЯП присвоить один из признаков каждого класса. Тенденции развития ЯП Рассмотренная схема классификации ЯП позволяет сделать вывод о том, что ЯП обладают определенной специализацией. Поэтому рассмотрим тенденции развития классов ЯП. Языки системного программирования, на которых создаются операционные системы, трансляторы и другие системные программы, развиваются в направлении повышения их уровня и независимости от ЭВМ. На сегодняшний день почти 90% системного программного обеспечения создается не на языке ассемблера, а на языке C. Например, операционная система Unix практически полностью написана на C. Язык C позволяет получать программы, сравнимые по своей эффективности с программами, написанными на языке ассемблера. Правда, объем программ получается больше, но зато эффективность их создания гораздо выше. Машинная независимость достигается использованием стандарта языка, поддерживаемого всеми разработчиками трансляторов, и использованием так называемых кросссистем для эквивалентного преобразования программ с одного языка низкого уровня на другой. Другим направлением является повышение уровня самого машинного языка. Например, известны Lisp-машины, в которых машинным языком является язык Lisp (реализован аппаратно). Другим примером являются ЭВМ 5-го поколения с машинным языком искусственного интеллекта Prolog. ЯВУ развиваются в направлении поддержки технологий программирования, обеспечения низкоуровневых операций (уровня ассемблера), обеспечения новых информационных технологий (НИТ) и независимости от среды реализации. Следует сказать, что по своим возможностям ЯВУ постепенно сближаются и программисту на C все труднее становится спорить о преимуществах языка C с программистом, работающим на языке Basic. Тотальный бум переживает технология объектно-ориентированного программирования (ООП): практически все современные ЯВУ поддерживают ООП. Да и все современные программные системы построены на принципах ООП, и сегодня каждый программирующий студент знает, что такое инкапсуляция, наследование и полиморфизм. Для обозначения факта поддержки ООП языки получают приставку Object (например, ObjectPascal) или другие (например, C++). Windows, сети ЭВМ, серверы, базы данных и Internet, как основа НИТ, оказывают сильнейшее влияние на современные ЯП. Разработчики ЯП просто обязаны включать в языки средства поддержки НИТ, чтобы привлечь программистов на свою сторону. Для поддержки Windows создаются системы визуального программирования с приставкой Visual, например Visual C++, Visual Basic и др. Для работы с БД, сетями и Internet в ЯП включаются специальные внутренние или внешние средства. Стремление к созданию программ, независимых от типа ЭВМ и операционной системы, привело к созданию языка Java. Основная задача Java - обеспечить выполнение программ, распространяемых через Web-страницы Internet, на любой рабочей станции. Кроме того, Java поддерживает все средства НИТ и в ближайшее время, очевидно, станет самым популярным ЯП. Популярность языков искусственного интеллекта за последние 10 лет, к сожалению, заметно упала. На мой взгляд это связано прежде всего с психологическими проблемами, которые испытывают программисты при использовании этих языков. Например, в мощнейшем языке Lisp программа имеет очень сложную для понимания списочную структуру 26 и небольшой по объему проект очень быстро выходит из под контроля. В языке Prolog программист должен точно знать логику работы встроенной машины логического вывода, а работа программы зависит от структуры и содержимого базы знаний (БЗ). Если с проектированием программы и структуры БЗ программист справляется, то для заполнения БЗ он должен быть экспертом в предметной области либо тесно контактировать с экспертом и извлекать из него знания, а то и другое является сложной задачей. Поэтому необходимы дополнительные обеспечивающие средства для возврата популярности этих языков. Заключение Изучение вопросов эволюции ЯП призвано облегчить программисту выбор языка для решения определенных задач. Однако следует осознавать, что не все мы полиглоты и не нужно изучать все существующие ЯП - достаточно изучать по одному языку каждого класса по мере необходимости, так как в процессе эволюции все языки одного класса сближаются. И помните главное: лучший язык тот, который знаешь в совершенстве. Рисунки к лекции 27 28