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

Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия - Мати Пентусом.

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

Формальные языки

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

Чтобы лучше разобраться в том, как именно изучаются формальные языки, необходимо сначала понять, в чем заключаются особенности математических методов изучения. Согласно Колмогорову и др. (Александров А.Д., Колмогоров А.Н., Лаврентьев М.А. Математика. Ее содержание, методы и значение. Том 1. М.: Издательство Академии Наук СССР, 1956.), математический метод, к чему бы он ни применялся, всегда следует двум основным принципам:

1. Обобщение (абстрагирование). Объекты изучения в математике - это специальные сущности, которые существуют только в математике и предназначены для изучения математиками. Математические объекты образуются путем обобщения реальных объектов. Изучая какой-нибудь объект, математик замечает только некоторые его свойства, а от остальных отвлекается. Так, абстрактный математический объект «число» может в реальности обозначать количество гусей в пруду или количество молекул в капле воды; главное, чтобы о гусях и о молекулах воды можно было
   говорить как о совокупностях. Из такой «идеализации» реальных объектов следует одно важное свойство: математика часто оперирует бесконечными совокупностями, тогда как в реальности таких совокупностей не существует.
2. Строгость рассуждений. В науке принято для выяснения истинности того или иного рассуждения сверять их результаты с тем, что существует в действительности, т.е. проводить эксперименты. В математике этот критерий проверки рассуждения на истинность не работает. Поэтому выводы не проверяются экспериментальным путем, но принято доказывать их справедливость строгими, подчиняющимися определенным правилам, рассуждениями. Эти рассуждения называются доказательствами и доказательства служат единственным способом обоснования верности того или иного утверждения.

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

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

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

Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита - начальные строчные буквы латинского алфавита. Например, выражение V = {a,b} обозначает алфавит из двух символов a и b.

Цепочка представляет собой конечную последовательность символов. Например, abc - цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1...an - цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.

Наконец, формальный язык L над алфавитом V - это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.

Итак, формальные языки - это просто множества цепочек, составленных из символов некоторого конечного алфавита. Но возникает вопрос: как можно задать формальный язык? Если язык конечен, то можно просто выписать все его цепочки одну за другой (конечно, можно задуматься, имеет ли смысл выписывать цепочки языка, имеющего хотя бы десять тысяч элементов и, вообще, есть ли смысл в таком выписывании?). Что делать, если язык бесконечен, как его задавать? В этот момент на сцену выходят грамматики.

Формальные грамматики

Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L = {a^nb^n} (здесь n - натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д. Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.

Назначение грамматики - задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.

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

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

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

• Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» - в противном случае.
• Порождающие грамматики. Этот вид устройств используется для порождения цепочек языков по требованию. Образно говоря, при нажатии кнопки будет сгенерирована некоторая цепочка языка.
• Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

Интересным представляет вопрос о преобразовании видов грамматики друг в друга. Можно ли, имея порождающую грамматику, построить, скажем, перечисляющую? Ответ - да, можно. Для этого достаточно генерировать цепочки, упорядочив их, скажем по длине и порядку символов. Но превратить перечисляющую грамматику в распознающую в общем случае нельзя. Можно использовать следующий метод. Получив на вход цепочку, запустить процесс перечисления цепочек и ждать, напечатает ли перечисляющая грамматика эту цепочку или нет. Если такая цепочка напечатана, то заканчиваем процесс перечисления и печатаем «Да». Если цепочка принадлежит языку, то она обязательно будет напечатана и, таким образом, распознана. Но, если цепочка не принадлежит языку, то процесс распознавания будет продолжаться бесконечно. Программа распознающей грамматики зациклится. В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих. Это следует иметь ввиду, когда сравнивают порождающие грамматики Хомского и распознающие машины Тьюринга.

Окрестностные грамматики

В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» - цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.

В качестве примера рассмотрим язык A = {a+a, a+a+a, a+a+a+a,...} . Этот язык представляет собой простейшую модель языка арифметических выражений, где роль чисел играет символ «a», а роль операций - символ "+". Составим для этого языка окрестностную грамматику. Зададим окрестности для символа «a». Символ «a» может встречаться в цепочках языка A в трех синтаксических контекстах: вначале, между двумя символами "+" и в конце. Для обозначения начала и конца цепочки введем псевдосимвол "#". Тогда окрестности символа «a» будут следующими: #a+, +a+, +a# . Обычно для выделения центра окрестности этот символ в цепочке подчеркивается (ведь в цепочке могут быть и другие такие символы, которые не являются центром!), здесь этого делать не будем за неимением простой технической возможности. Символ "+" встречается только между двух символов «a», поэтому для него задается одна окрестность, цепочка a+a .

Рассмотрим цепочку a+a+a и проверим, принадлежит ли она языку. Первый символ «a» цепочки входит в нее вместе с окрестностью #a+ . Второй символ "+" входит в цепочку вместе с окрестностью a+a . Подобное вхождение можно проверить и для остальных символов цепочки, т.е. данная цепочка принадлежит языку, как и следовало ожидать. Но, например, цепочка a+aa языку A не принадлежит, поскольку последний и предпоследний символы «a» не имеют окрестностей, с которыми они входят в эту цепочку.

Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.

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

Можно сказать, что шрейдеровские языки задают одно простое синтаксическое отношение - «быть рядом» или отношение непосредственного предшествования. Отношение дальнего предшествования (которое, очевидно, присутствует в языке B) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.

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

· алфавит допустимых символов и служебных (ключевых) слов;

· синтаксические правила построения из алфавита допустимых конструкций языка;

· семантику, объясняющую смысл и назначение конструкций языка.

Языки программирования служат для представления решения задач в такой форме, чтобы они могли быть выполнены на ЭВМ.

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

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

Транслятор - это программа, которая считывает текст программы, написанной на одном языке, и транслирует (переводит) его в эквивалентный текст на другом языке (обычно на машинном языке). Трансляторы бывают двух основных видов: компиляторы и интерпретаторы .

Компилятор преобразует текст исходной программы в набор инструкций для данного типа процессора (машинный код) и далее записывает его в исполняемый файл (exe-файл), который может быть запущен на выполнение как отдельная программа. Другими словами, компилятор переводит программу с языка высокого уровня на низкоуровневый язык.

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

Разделение на компилируемые и интерпретируемые языки является несколько условным. Так, для любого традиционно компилируемого языка, как, например, Pascal, можно написать интерпретатор, а для любого интерпретируемого языка можно создать компилятор, - например, язык Бейсик, изначально интерпретируемый, может компилироваться без каких бы то ни было ограничений.

Некоторые языки, например Java и C#, находятся между компилируемыми и интерпретируемыми. А именно, программа компилируется не в машинный язык, а в машинно-независимый код низкого уровня, байт-код. Далее байт-код выполняется виртуальной машиной. Для выполнения байт-кода обычно используется интерпретация. Подобный подход в некотором смысле позволяет использовать плюсы как интерпретаторов, так и компиляторов.

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

Классификацию языков программирования можно вести по нескольким критериям: машинно-ориентированные (ассемблеры) и машинно-независимые, специализированные и универсальные.

К специализированным языкам можно отнести язык АРТ (A utomatically P rogrammed T ools ) - первый специализированный язык программирования для станков с числовым управлением. Язык был разработан группой американских специалистов в 1956–1959 гг. под руководством математика Дугласа Т. Росса. Язык СOBOL (Co mmon B usiness–O riented L anguage ), созданный в США под руководством Грейс Мюррей Хоппер в 1959 г., ориентирован на обработку экономической информации. Математик Грейс Мюррей Хоппер возглавила проект по разработке СOBOL в чине капитана второго ранга, впоследствии она стана контр-адмиралом. Г.М. Хоппер называют “мамой и бабушкой” СOBOLа.

(Grace Murray Hopper)

К специализированным языкам можно отнести и современные языки web-программирования Perl и PHP. Языки Рапира, Е-язык (Россия), SMR (Великобритания), LOGO (США) можно отнести к языкам, предназначенным для обучения программированию.

Самыми распространенными универсальными языками программирования сегодня являются C++, Delphi, Java, Pascal, Visual Basic, Python.

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

Классификация языков программирования

Языки программирования можно разделить на два класса: процедурные и непроцедурные. Процедурные (императивные ) языки - это языки операторного типа. Описание алгоритма на этом языке имеет вид последовательности операторов. Характерным для процедурного языка является наличие оператора присваивания (Basic, Pascal, С). Программа, написанная на императивном языке, очень похожа на приказы, выражаемые повелительным наклонением в естественных языках, то есть это последовательность команд, которые должен выполнить компьютер. Программируя в императивном стиле, программист должен объяснить компьютеру, как нужно решать задачу.

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

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

Логические языки

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

Первым языком логического программирования был язык Planner, он был разработан Карлом Хьюитом в Лаборатории искусственного интеллекта Массачусетсского технологического института в 1969 г. В этом языке была заложена возможность автоматического вывода (получения) результата из данных и заданных правил путем перебора вариантов (совокупность которых называлась планом). Но самым известным языком логического программирования является ПРОЛОГ (Prolog), который был создан во Франции в Марсельском университете в 1971 г. Аленом Кольмеро (Colmerauer).

Ален Кольмеро
(Alain Colmerauer)

Программа на языке ПРОЛОГ содержит две составные части: факты и правила. Факты представляют собой данные, с которыми оперирует программа, а совокупность фактов составляет базу данных ПРОЛОГа, которая, по сути, является реляционной базой данных. Основная операция, выполняемая над данными, - это операция сопоставления, называемая также операцией унификации или согласования. Правила состоят из заголовка и подцелей. Выполнение программы, написанной на ПРОЛОГе, начинается с запроса и состоит в доказательстве истинности некоторого логического утверждения в рамках заданной совокупности фактов и правил. Алгоритм этого доказательства (алгоритм логического вывода) и определяет принципы исполнения программы, написанной на ПРОЛОГе.

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

мама("Даша","Маша").

мама("Наташа","Даша").

Кроме этого, имеется правило, вводящее отношение бабушка:

бабушка(X,Y):-

Теперь мы можем делать запросы на предмет того, кто бабушка того или иного человека, или кто является внучкой (внуком) определенной женщины:

бабушка("Наташа",X).

Ответ на этот запрос система ПРОЛОГ выдаст так:

Возможности применения языка ПРОЛОГ весьма обширны. Среди наиболее известных - применение в символической математике, планировании, автоматизированном проектировании, построении компиляторов, базах данных, обработке текстов на естественных языках. Но, наверное, самое характерное применение ПРОЛОГа - это экспертные системы.

На сегодняшний день существует целый класс логических языков; так, от языка Planner также произошли логические языки программирования QA-4, Popler, Conniver и QLISP. Языки программирования Mercury, Visual Prolog, Oz и Fril произошли уже от языка Prolog.

Функциональные языки

Первым языком функционального типа является язык ЛИСП, созданный в Массачусетсском технологическом институте в 1956–1959 гг. Джоном Маккарти, который в 1956 г. на Дармутской конференции (США) впервые предложил термин “искусственный интеллект”.

Джон Маккарти (John McCarthy)

И хотя до сих пор не утихают споры вокруг этого термина и развившегося научного направления в его рамках, исследователи единодушны в использовании функциональных и логических языков для данной области. Значительное число работ по искусственному интеллекту реализовано на ЛИСПе.

После своего появления ЛИСПу присваивали много эпитетов, отражающих его черты: язык функций, символьный язык, язык обработки списков, рекурсивный язык. С позиций сегодняшней классификации ЛИСП определяется как язык программирования функционального типа, в основу которого положен метод -исчисления (метод -исчисления разработан в 30-е годы прошлого столетия А.Черчем в качестве строгой математической модели для вычислимых функций, см. “Теория алгоритмов” ).

Программа, написанная на функциональном языке, состоит из неупорядоченного набора уравнений, определяющих функции и значения, которые задаются как функции от других значений. Программы и данные ЛИСПа существуют в форме символьных выражений, которые хранятся в виде списковых структур. ЛИСП имеет дело с двумя видами объектов: атомами и списками . Атомы - это символы, используемые для идентификации объектов, которые могут быть числовыми и символьными (понятия, материалы, люди и т.д.). Список - это последовательность из нуля или более элементов, заключенных в круглые скобки, каждый из которых является либо атомом, либо списком. Над списками выполняются три примитивные операции: извлечение первого элемента списка; получение оставшейся части списка после удаления первого элемента; объединение первого элемента списка L и оставшейся части списка Q.

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

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

Кроме ЛИСПа, к функциональным языкам относят РЕФАЛ (разработан в середине 60-х годов В.Ф. Турчиным в МГУ им. М.В. Ломоносова), Haskell, Clean, ML, OCaml, F#.

Приведем пример описания известного алгоритма быстрой сортировки списка на языке Haskell:

qsort (x:xs) = qsort elts_lt_x ++ [x]

Qsort elts_greq_x where

elts_lt_x =

elts_greq_x =

Здесь записано, что пустой список уже отсортирован. А сортировка непустого списка состоит в том, чтобы разбить список на три: список элементов, меньших головы исходного списка, голова исходного списка ([x]) и список элементов хвоста исходного списка, больше или равных x.

Объектно-ориентированные языки

Объектно-ориентированные языки - это языки, в которых понятия процедуры и данных, используемых в обычных системах программирования, заменены понятием “объект” (см. статью “Объектно-ориентированное программирование ”). Языком объектно-ориентированного программирования в чистом виде считается SmallTalk, возможности объектно-ориентированного программирования заложены также в Java, C++, Delphi.

Дальнейшее развитие современного программирования связано с так называемым “параллельным программированием”. Для реализации этой технологии разрабатываются специализированные объектно-ориентированные языки. К языкам такого типа относят, например, MC# (mcsharp ) - высокоуровневый объектно-ориентированный язык программирования для платформы.NET, поддерживающий создание программ, работающих в распределенной среде с асинхронными вызовами.

Структура языка программирования

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

Любой язык программирования состоит из предложений (операторов). Предложения (как и слова) определены над неким алфавитом С. Синтаксис языка описывает множество предложений над алфавитом С, которые внешне представляют правильно сформированные программы.

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

Знание формального языка (алфавита + синтаксиса) хотя и достаточно для установления синтаксической корректности программы, однако недостаточно для понимания ее назначения и способа действий. Значение и способ действия программы на языке программирования уточняются путем задания семантики.

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

Для определения формальных языков, в том числе для языков программирования, используют БНФ (формы Бэкуса - Наура) и синтаксические диаграммы. Это два взаимозаменяемых способа описания.

При описании языка программирования через БНФ используются следующие обозначения:

1) <..>- определяемое слово;

2) R - правило из синтаксиса для формирования слова;

3) ::= - БНФ-правило.

Каждое R состоит из терминальных слов или лексем языка и, возможно, следующих символов:

· [..] - данный элемент присутствует в БНФ;

· {..} - данное вхождение может быть использовано в БНФ;

· {..}* - данное вхождение может быть использовано в БНФ конечное число раз.

Пример 1. Приведем пример БНФ-правила, определяющего целое число.

Читается это правило так: “Целое число - это символ 0 или последовательность символов, которая может начинаться символом “–”, а далее следует отличная от нуля цифра, вслед за которой может следовать любая конечная последовательность цифр”.

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

Пример 2 . Описание целого числа с помощью синтаксической диаграммы.

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

Следует рассказать, почему возникают новые языки и совершенствуются старые: в первую очередь это происходит при поиске средства для быстрого написания сложных программ, которые к тому же не содержали ошибок. Известен пример, когда создание языка АДА (назван так в честь первой женщины-программиста Ады Лавлейс, дочери Байрона) было инициировано в 1974 году в Министерстве обороны США. Американские военные осознали, что они теряют много времени, усилий и денег на разработку и сопровождение встроенных компьютерных систем (например, систем наведения ракет), а трудноуловимые ошибки языков программирования приводят к настоящим катастрофам.

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

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

В настоящее время существуют два наиболее распространенных подхода к преподаванию программирования:

1) преподавание на основе специально разработанного языка учебного языка, ориентированного на обучение основным навыкам программирования;

2) изучение одного или нескольких языков программирования, широко используемых на практике при решении научных и хозяйственных задач (такие языки можно назвать стандартными).

Первый подход часто используется при преподавании основ программирования в младших классах средней школы с использованием специальных языков, например, Рапиры, Е-языка, LOGO. Эти языки учитывают возможности школьников младших классов. Такой подход хорош при углубленном изучении информатики в 5–6-х классах.

Относительно второго подхода можно сказать, что большинство современных реализаций стандартных языков загружено большим количеством технических деталей и сложны в изучении. Тем не менее наиболее приемлемым для общеобразовательной школы, где курс информатики преподается в 8–11-х классах, является обучение теоретическим основам программирования на базе стандартного языка. При этом не обязательно вдаваться в глубины языка. Учащиеся, которых он заинтересует, могут сделать это и сами. Наибольшее внимание следует уделить переходу от алгоритмических структур к их программной реализации на языке программирования.

Здесь стоит отметить, что Pascal первоначально создавался как учебный язык, но со временем получил широкое распространение в качестве стандартного языка и развитие в виде объектно-ориентированного языка с визуальной технологией программирования Delphi. За основу курса в 8–9-х классах можно взять Pascal или Basic, а в качестве расширенного (факультативного) курса в 10–11-х классах ознакомить учащихся с их объектно-ориентированными расширениями (Delphi и Visual Basic). У каждого языка есть свои сторонники и противники, и конечный выбор остается за учителем.

Существует два основных подхода к изучению языка программирования: формальный и “программирование по образцу”. Первый основан на формальном (строгом) описании конструкций языка программирования (синтаксиса языка и его семантики ) тем или иным способом (с помощью синтаксических диаграмм, мета-языка или формального словесного описания, в частности, семантики) и использовании при решении задач только изученных, а следовательно понятных, элементов языка. При втором подходе школьникам сначала выдаются готовые программы, рассказывается, что именно они делают, и предлагается написать похожую программу или изменить имеющуюся, не объясняя до конца ряд “технических” или несущественных, с точки зрения учителя, для решения задачи деталей. При этом говорится, что точный смысл соответствующих конструкций вы узнаете позднее, а пока поступайте аналогичным образом. Второй подход дает возможность так называемого “быстрого старта”, но создает опасность получить полуграмотных пользователей среды программирования, т.е. людей, которые используют в своей практике достаточно сложные конструкции, но не могут четко объяснить, почему в том или ином случае нужно применять именно их, и как они работают. В результате рано или поздно такие “программисты” сталкиваются с ошибками, исправить которые они просто не в состоянии - им не хватает знаний.

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

Естественные языки программирования (ЕЯП) определяют следующий шаг развития языков программирования, отличаясь отязыков запросов тем, что пользователь любого уровня освобождается от необходимости освоения каких-либо специальных словарей, грамматики и синтаксиса –предложения ЕЯП весьма похожи на предложения обычной человеческой речи. ЕЯП еще дальше отдаляют пользователя от ВС и ее СПО, существенно повышая интеллектуальный уровень интерфейсапервого с вычислительными ресурсами. В настоящее время на ПК успешно используются ЕЯП с ограниченными возможностями, такие, какClout, Q&A, Savvy Retriever, HAL и др. Основные разработки ЕЯП связываются с задачами ИИ и интеллектуализацией интерфейса в СУБЗ. В этом направлении непосредственную прикладную значимость (особенно в связи с массовым применением ПК) получили различного рода ЕЯП-интерфейсы с ЭВМ. Из ЕЯП такого типа можно отметитьрегламентированные языки (меню, анкетные, инструкций и др.), играющие большую роль в интеллектуализации интерфейса с ЭВМ при использовании различного рода ППО; большую роль они играют в различных системахинтервьюирования ,обучающих, экспертных и др., однако их использование жестко регламентировано определенными рамками, а в случае переноса систем срегламентированными ЕЯП на другие типы ЭВМ зачастую требуются существенные их переделки. Поэтому для более гибкого и естественного общения пользователя с ЭВМ более адекватен именноестественный язык.

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

В целом ряде случаев естественный язык выразителен менееграфического, тщательно отработанныйформальный язык предметной области бывает выразительнееестественного языка (также имеющегонемало недостатков). Более того, многие предметные области (математика, физика, химия, биология и др.) имеют свойязыковый сленг, в ряде случаев существенно отличающийся от обычного естественного языка. Поэтому, развитыйязыковый интерфейс может являтьсясимбиозом естественного иформальных языков либо представлять собойиерархию языков:естественный язык -формальный {структурированный) язык ЭВМ. В любом случае, данная проблема пока еще весьма далека от своего полного решения.

Лекция № 34 прикладное программное обеспечение

План лекции.

1. Прикладное программное обеспечение ЭВМ.

2. Классы пакетов прикладных программ.

3. Основные прикладные средства.

4. Качественные характеристики программного обеспечения.

34.1. Прикладное программное обеспечение эвм

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

(1) принцип организации ППП;

(2) требования к профессиональной подготовке пользователя;

(3) основные современные группы ППП.

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

Создание ППП - достаточно длительный и трудоемкий процесс, требующий использования специальных инструментальных средств. Однако в общем случае такие системы оказываются весьма сложными, а создаваемые ими пакеты достаточно далекими от требуемой эффективности. Поэтому одним из способов устранения указанных недостатков является создание специализированных инструментальных систем, ориентированных насемейства проблемно-ориентированных ППП соднородными входными языками иодинаковыми принципами функционирования. Из отечественных средств данного типа можно отметитьмета системы САТУРН иPACKAGE . Так, вPACKAGE подобно другим аналогичным системам выделяются две вышеуказанных фазы:описание искомого ППП на специальном ЯФП (подсистемаКонструктор) игенерация ППП с его входным языком (подсистемаПрепроцессор); при этом обеспечивается технологичность программирования на основных этапахгенерации пакета: (1) описание класса решаемых пакетом задач и методов их решения; (2) создание входного языка ППП; (3) программирование и отладка необходимых программных модулей.

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

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

В отличие от рассмотренной организации ППП, обеспечивающей их гибкость и адаптируемость к предметной области и выдвигающей ряд требований к профессиональному уровню пользователя, для массового пользователя используется, как правило, жесткая организация, не позволяющая ему модифицировать пакет. Такая организация имеет два основных исполнения: (1) высокийлогический уровеньвходного языка пакета (ВЯП), ориентированного на пользователя и предметную область, ивнутреннего языка пакета, позволяющего создавать в его среде модули, обеспечивающие функции расширения пакета, а также создание документов для конкретных приложений пакета; (2) интерфейс с пакетом обеспечивается только на уровне проблемно-ориентированного ВЯП. Вобоих случаях практика создания ВЯП для пакета использует два основных подхода: (1) создание языка на основе уже существующего ЯВУ (который, как правило, является иязыком реализации пакета) и (2) разработкаоригинального входного языка. Припервом подходе существенно упрощается реализациявходного языка, тогда как для непрофессионального пользователя возникают дополнительные сложности по освоению пакета.Второй подход требует в ряде случаев значительно больших затрат на разработкувходного языка, однако позволяет сделать его легким в освоении и использовании (язык меню, элементы естественного профессионального языка, язык запросов, язык диалоговой графики и др.).

При этом спектр пользовательской ориентированности ВЯП лежит в весьма широком диапазоне - от начинающего пользователя до профессионала в некоторой предметной области. Например,игровые пакеты имеют высокопонятийныйграфический интерфейс и не требуют особого освоения; пакетытекстовых редакторов также имеют развитый языксистемы меню, достаточно высокого понятийного уровня (например пакетMs Word); проблемно-ориентированные пакеты (например,MathCAD, Reduce. Mathematica обеспеченывходным языком, ориентированным на знакомого с математическим языком пользователя. Наконец,внутренний язык пакета ориентирован, главным образом, на программирование функций, непосредственно не поддерживаемых пакетом, либо программированиедокументов для конкретных его приложений. Часто в качествевнутреннего языка используется языкреализации пакета или его модификации (например пакетыReduce. Mathematica и др.); однако в ряде случаеввнутренний язык имеет ориентацию напредметную область пакета имеетвходной язык на основе простой и дружелюбной системы меню ивнутренний С-подобный SALT-язык, позволяющий легко и быстро создавать и выполнять в среде пакета SLT-документы (программы, модули для конкретных приложений пакета)].Сложность внутренних языков ППП различна, требует определенного программистского навыка для их освоения; однако они позволяют создавать развитые библиотеки документов, выполнение которых в среде пакета позволяетсущественно расширять его функции и область приложений.

Наконец, жесткая организация в сочетании с предметно-ориентированным ВЯП ориентирована на относительно небольшие по объему пакеты либо пакеты специальной направленности, но массового применения. В качестве ВЯП, как правило, выступают языки типа меню, диалоговой графики, запросные и др., ориентированные на непрофессионального пользователя. Примером такойорганизации могут служить простые пакеты текстовых редакторов, специальные пакеты и т.д. Вместе с тем более развитые из них располагают макросредствами, позволяющими оформлять на уровнемакросов наиболее часто используемыепоследовательности операций с пакетом (напримерChiWriter , Ms Word , Word Perfect vs . др.).

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

Большинство современных ППП перед началом использования требуют проведения операции инсталляции, состоящей в настройке пакета на конкретные условияэксплуатации (конфигурация аппаратных средств, режим решения задач и др.). Как правило, инсталляция проводится один раз и выполняется либовнутренними средствами пакета(Ms Word, Quattro и др.), либо посредствомспециальных утилит(Sprint, Mathematica и др.). Для простых пакетовинициализация, как правило, производится каждый раз автоматически при их загрузке средствами операционной системы(Framework , AutoSketch и др.).

Документация, поставляемая с пакетом, должна включать рекомендации по его инсталляции на конкретные условия применения. Рассмотревтри основных принципа организации ППП, кратко обсудимфункциональное наполнение пакетов, которое нафайловом уровне в общем случае можно представить, как: (1)модули обеспечения основных функций пакета; (2) конфигурационные файлы; (3) утилиты общего назначения и расширяющие функции пакета; (4) специализированная БД; (5) библиотека документов для выполнения их в среде пакета; (6) файлы, содержащие справочную, лицензионную информацию по пакету, а также документацию. Как правило, во всех современных ППП прослеживается отмеченнаяструктуризация ихфайловой системы.

Ряд известных пакетов (Expert Choice , Mathematica , MathCAD , Ms Excel и др.) поставляются также на уровне иллюстративных и/или обучающих версий, которые функционально ограничены относительно основного пакета, но позволяют проводить иллюстрацию пакета в действии, а также обучать основам работы в его среде, что в целом ряде случаев позволяет сделать более осознанный выбор данного средства для последующего коммерческого использования.

Основные понятия

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

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

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

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

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

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

Системой операций называется совокупность всех машинных операций, предусмотренных в ЭВМ.

Команда представляет собой элементарное предписание, предусматривающее выполнение некоторой группы операций.

Основными операциями ЭВМ являются арифметические, логические, переносы, переходы, когда машина осуществляет переход от выполнения одной команды к выполнению другой, выборка команд из оперативной памяти и останов машины («стоп»). Основными операциями над буквенной информацией являются: определение длины слова; перенос слова с одного места оперативной памяти в другое; выделение определенной части заданного слова; включение между словами пробелов; деление строки слов на более мелкие строки; сравнение двух слов. Обычно перечисленные операции называют редактированием.

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

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

При решении на ЭВМ некоторой задачи (класса задач) работа распадается на следующие этапы:

математическую формулировку задачи;

разработку методики ее решения;

разработку алгоритма ее решения и запись ее на некотором языке программирования;

программирование;

отладку программы на машине;

подготовку исходных данных, решение задачи на ЭВМ.

Описанный комплекс работ называют проблемным программированием.

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

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

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

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

Применяя ЭВМ для решения задачи, необходимо учитывать следующие ее особенности:

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

Программирование. Программирование заключается в записи разработанного алгоритма на языке программирования (например, на так называемом языке АССЕМБЛЕРА или на АЛГОЛе, ФОРТРАНе, КОБОЛе, ПЛ/I), выполняемой вручную, и последующей трансляции на машинный алгоритмический язык.

Трансляцией называется процесс равносильного преобразования алгоритма, заданного на языке программирования, в алгоритм на машинном языке. Этот процесс выполняется с помощью специальной программы, называемой транслятором.

Отладка программы на машине. Отладка программы на машине преследует цель устранить в программе неправильности и включает: контроль программы; поиск и определение содержания (диагностику) ошибок; исправление обнаруженных ошибок.

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

Как правило, для ввода информации в вычислительную машину используются либо 80-колонные ПК, либо бумажная ПЛ. На больших машинах имеется и то и другое. Перфокарта содержит 12 строк, и, следовательно, в каждой колонке возможно 12 пробивок; в поперечном направлении перфоленты допускаются 5, 6, 7 и 8 позиции пробивки. Таким образом, теоретически возможно использование алфавита от 2 5 =32 до 2 12 =4096 символов, но на практике в колонке перфокарты редко встречается более 3 пробивок, так что, как правило, используемый алфавит содержит от 40 до 80 символов. Среди оборудования вычислительной машины имеется самостоятельное устройство воспроизведения на бумаге информации, содержащейся на перфокартах и перфоленте в виде, удобном для чтения ее человеком. В результате мы получаем то, что обычно называется листингом, или распечаткой.

После ввода в ЭВМ программ и исходных данных решение задачи производится автоматически.

Математическое обеспечение ЭВМ

Математическое обеспечение (МО) ЭВМ можно определить как некоторое собрание программ, каждая из которых может быть практически применена пользователем одна или в совокупности с некоторыми другими программами для решения задач, либо для выполнения некоторых работ, связанных с программированием, либо для создания определенного режима работы ЭВМ.

В систему МО вычислительных машин могут входить следующие группы программ:

операционная система программ;

система средств программирования;

приложения к программам;

система программ поддержания математического обеспечения;

система испытательных программ, предназначенных для контроля исправности ЭВМ.

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

диспетчер - программа, обеспечивающая определенный режим работы ЭВМ;

супервизор, или монитор,- программа, обеспечивающая работу, задаваемую машине человеком-оператором в рамках установленного для нее режима;

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

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

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

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

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

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

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

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

Система средств программирования содержит ряд трансляторов-программ для перевода алгоритмов, заданных на различных входных языках программирования, на машинный язык. Обычно система средств программирования содержит трансляторы с алгоритмических языков трех уровней.

Процесс перевода алгоритма и процесс его выполнения машиной могут сочетаться одним из двух способов.

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

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

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

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

Системы средств программирования новейших ЭВМ часто основываются на так называемом принципе модульности. Модулями называют «куски» алгоритмов, заданных на языке исполнительной системы или на входном языке программирования, для которых выполнены следующие условия:

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

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

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

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

В библиотеку собирают обычно специально составленные и специально оформленные программы.

Перечисленные средства программирования целесообразно применять для решения различных задач (проблем). При этом считается, что программы отдельных задач (проблем) могут быть и не очень «хорошие», зато суммарным расход средств на программирование и решение задачи на ЭВМ бывает обычно меньше, чем при составлении более «хороших» программ.

Математическое обеспечение АСУ

Математическое обеспечение (МО) АСУ - это система методов, приемов и средств, позволяющих эффективно разрабатывать программы решения на ЭВМ конкретных задач АСУ, управлять работой ЭВМ в процессе решения этих задач, контролировать правильность работы ЭВМ.

Основными положениями, которыми необходимо руководствоваться при создании МО АСУ, являются следующие:

• совместимость и базирование разрабатываемого МО АСУ на имеющемся МО ЭВМ;
• ориентированность выбираемых средств МО на задачи АСУ;
• достаточное разнообразие средств автоматизации программирования;
• возможность эффективного внесения изменений в рабочие программы;
• возможность однозначного и исчерпывающего описания алгоритмов;
• возможность оптимизации работы программ частного применения;
• модульность построения программ.

МО АСУ служит для представления пользователю широкого спектра услуг по технологии программирования. Его можно разделить на две части: составление управляющих программ и составление обрабатывающих программ.

Управляющие программы осуществляют первоначальную загрузку оперативной памяти машин и управление работой АСУП, включая обработку прерываний, распределение работы каналов, загрузку программ из библиотеки в оперативную память. Управляющие программы обеспечивают многопрограммную работу, осуществляют связь с оператором.

Обрабатывающие программы включают в себя систему автоматизации программирования и обслуживающие программы.

Функции системы автоматизации программирования следующие: запись программ на входных языках программирования; трансляции программ на внутренний язык ЭВМ; объединение (сборка) нужных конфигураций (сегментов) из стандартных подпрограмм; отладка программ на уровне входных языков; корректировка программ на уровне входных языков.

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

Основными компонентами МО АСУ являются системная диспетчерская программа и библиотека стандартных подпрограмм и типовых программ, предназначенных для обработки производственно-экономической информации.

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

Библиотека стандартных подпрограмм, имеющаяся в МО ЭВМ, является переходной ступенью к разработке системной библиотеки, ориентированной на процессы обработки информации в АСУ. Системная библиотека должна содержать:

программы ввода и преобразования в машинную форму документов и других письменных источников исходных данных;

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

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

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

Языком программирования называются знаковые системы, применяемые для описания процессов решения задач на ЭВМ. По своему характеру языки программирования делятся на три группы:

1. формальные алгоритмические языки;
2. формальные неалгоритмические языки программирования;
3. не вполне формализованные знаковые системы, применяемые при программировании.

Формальные языки программирования. К этой группе языков относятся: алгоритмические языки машин и операционных систем; машинно-ориентированные алгоритмические языки; проблемно-ориентированные алгоритмические языки; универсальные машинно-независимые алгоритмические языки.

Языками операционных систем называются алгоритмические языки, воспринимаемые комплексами, образованными из ЭВМ и разработанной для них программы-диспетчера (иногда называемой также супервизором).

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

Машинно-ориентированные алгоритмические языки содержат выразительные средства, позволяющие в записи алгоритма указать, с помощью каких технических средств должны выполняться те или иные его части и каким образом при этом должны быть использованы запоминающие устройства. К числу машинно-ориентированных языков программирования относятся автокоды и некоторые языки, приближающиеся по своим возможностям к универсальным алгоритмическим языкам, например AЛMO.

Проблемно-ориентированные алгоритмические языки это такие языки, которые специально разработаны для описания процессов решения задач некоторого узкого класса, например задач линейной алгебры, статистики, задач обработки данных и т. п. В частности, к проблемно-ориентированным языкам относится КОБОЛ.

Универсальные машинно-независимые алгоритмические языки пригодны для создания алгоритмов решения задач весьма широких классов. К числу этих языков относятся уже упомянутые АЛГОЛ, ФОРТРАН, ПЛ/1.

Из числа универсальных машинно-независимых алгоритмических языков исключение составляет ЯЛС. Назначение этого языка не сводится к тому, чтобы быть языком программирования. ЯЛС используется как первый этап описания алгоритмов при программировании на машинном языке или на языке АССЕМБЛЕРА (операторный метод программирования; записанный на ЯЛС алгоритм вручную переводится на язык машины или язык АССЕМБЛЕРА).

В таблице ниже приводятся сравнительные данные формальных языков программирования.

Не вполне формализованные знаковые системы. Эти языки обычно используются при программировании вручную или на предварительном, выполняемом вручную этапе автоматизированного программирования. Их примером является блок-схема программы. Блок-схема программы представляет собой укрупненное описание программы, при котором отдельные ее части изображаются в виде «блоков» (прямоугольников, ромбов, кружков и т. п.), внутри которых на естественном языке (например, на русском) излагается содержание этих частей. Связь между блоками (частями программы) изображается с помощью линий, обозначающих передачу управления. Линии могут быть снабжены надписями, указывающими условия, при которых происходит передача управления. Блок-схемы аналогичны алгоритмам, записанным на ЯЛС с помощью обобщенных операторов, но отличаются от них тем, что значение блоков изложено на естественном, неформальном языке, тогда как в ЯЛС обобщенные операторы снабжены расшифровкой на точном формальном языке.

В настоящее время известно более 2000 различных алгоритмических языков и более 700 областей их применения для решения соответствующих задач на ЭВМ.

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

язык нулевого или низшего уровня - машинный код;

язык первого уровня - мнемокод, или язык символического кодирования;

язык второго уровня - автокод (макрокод);

языки третьего уровня (высшего)-проблемно-ориентированные языки.

В качестве входных языков в зависимости от вида задач АСУП целесообразно применять проблемно-ориентированные языки различного типа

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

Класс алгоритмических языков программирования	Учет особенностей ЭВМ	Характеристика класса задач	Способ программирования	Условная оценка качества программ
Машинные языки
Машинно-ориентированные языки	Частичный	Определяется особенностями ЭВМ	Автоматизированный	Удовлетворительная
Проблемно-ориентированные языки	Незначительный		Автоматизированный	Удовлетворительная
Универсальные машиннонезависимые языки	Отсутствует или весьма незначительный	Весьма обширный	Автоматизированный	Невысокая

(например, для анализа - АЛГОЛ, ФОРТРАН и др., для экономических задач- АЛГЭК и др., для информационных задач -КОБОЛ, СИНТОЛ и др.).

Рассмотрим некоторые из алгоритмических языков программирования.

АЛГОЛ-60. Название языка происходит от английских слов Algorithmic Language. Он был разработан группой ученых различных стран в 1960 г. и получил повсеместное распространение. Причины успеха заключаются в его близости к обычному математическому языку, в удобстве описания широкого класса задач, универсальности и полной независимости от конкретной ЭВМ, строгой формализации языка от алфавита до самых сложных конструкций.

АЛГОЛ-60 не только универсальный язык программирования, но и международный язык описания алгоритмов.

Основой записи алгоритмов на языке АЛГОЛ-60 является последовательность операторов, разделенных символом «;». К этой последовательности операторов, являющихся единичными действиями в языке, присоединяется последовательность описаний, дающих транслятору информацию о необходимых свойствах, используемых в операторах. Описания, например, дают информацию о классах чисел, используемых в качестве значений переменных, о размерности массивов чисел и т. д. Такое объединение описаний и операторов в этом языке называется блоком.

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

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

В СССР АЛГОЛ-60 получил распространение в виде некоторых его вариантов.

ФОРТРАН. Слово ФОРТРАН образовано из двух английских слов (Formula Translator). Одной из важнейших особенностей языка ФОРТРАН является то, что он относительно свободен от специфики конкретной вычислительной машины. ФОРТРАН является машиннонезависимым языком программирования.

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

Повсеместное внедрение ФОРТРАНа в практику программирования происходит благодаря его качествам, из которых следует отметить, во-первых, его простоту по сравнению с другими алгоритмическими языками (например, АЛГОЛом); во-вторых, благодаря отсутствию слишком сложных конструкций оттранслированные программы получаются более эффективными по сравнению с программами, составленными на других языках; в то же время ФОРТРАН пригоден для программирования большинства вычислительных алгоритмов;

в-третьих, в ФОРТРАНе имеются очень мощные средства для связи человека с машиной: выдаваемая ЭВМ информация представляется в виде, привычном для ученых и инженеров. И наконец, в-четвертых, ФОРТРАН хорошо приспособлен для эффективного использования внешних устройств ЭВМ.

Алгоритм решения задачи, записанный с помощью ФОРТРАНа, состоит из последовательности операторов. Эти операторы могут принадлежать к нескольким различным типам. Вместе взятые операторы, определяющие алгоритм решения задачи, составляют исходную программу. После того как исходная программа написана и отперфорирована на перфокартах, она преобразуется с помощью транслятора ФОРТРАНа в рабочую программу.

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

При составлении программ на ФОРТРАНе рекомендуется придерживаться следующего порядка следования операторов: 1) оператор-заголовок основной программы (подпрограммы); 2) оператор описания файлов; 3) неявный оператор задания типа; 4) явный оператор задания типа, оператор задания размеров, оператор задания общих областей; 5) оператор задания эквивалентности; 6) оператор-функция, оператор-процедура; 7) оператор задания формата, выполняемые операторы (безусловные, условные, ввода, вывода); 8) оператор конца.

КОБОЛ. Название языка происходит от английских слов Common Business Orientated Language. КОБОЛ - проблемно-ориентированный алгоритмический язык, предназначенный для описания процессов решения задач и обработки данных. В настоящее время КОБОЛ является единственным широко распространенным языком высокого уровня для программирования экономических задач. Его широкая популярность объясняется тем, что КОБОЛ достаточно близок к естественному языку, на котором обычно формулируются и решаются экономические задачи.

Отличительные особенности языка КОБОЛ состоят в следующем:

язык в известном смысле является подмножеством английского языка; написанный на КОБОЛе текст можно понимать без предварительной подготовки;

на языке хорошо описываются данные со структурой, типичной для деловых бумаг; эти данные могут относиться к личным делам, товарам, финансам (допускаются и комбинированные данные);

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

Программа на языке КОБОЛ состоит из четырех частей, называемых разделами. Эти разделы имеют следующие названия: раздел идентификации, раздел оборудования, раздел данных и раздел процедур. В разделе процедур содержится собственно программа, но она не имеет смысла (или в лучшем случае не полностью определена), если неизвестна структура подлежащих обработке данных, определяемая в третьем разделе. Раздел оборудования делится в свою очередь на секцию конфигураций и секцию ввода-вывода, а раздел данных - на секцию массивов, секцию рабочей памяти и секцию констант. В начале раздела (секции) находится название раздела (секции), за которым следует точка; название с точкой занимает отдельную строку. Содержимое раздела или секции состоит из предложений, сгруппированных в именованные параграфы.

В КОБОЛе значительно облегчено внесение в программу мелких изменений, необходимых при обработке коммерческой информации.

В КОБОЛе основной единицей ввода-вывода является файл данных. Каждый файл состоит из записей. Один и тот же файл часто используется в различных программах в зависимости от характера решаемых задач. Описание файлов является очень строгим и не допускает изменений.

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

СОЛ. Цифровое моделирование как эффективный метод исследования завоевывает все большую популярность среди специалистов, занимающихся анализом и проектированием сложных систем.

Очень часто специалист по системам испытывает трудности в составлении программы, моделирующей работу исследуемой им системы. Причиной этого может быть чрезвычайная сложность систем, которые практически невозможно описать математически. Задачами такого типа изобилует, в частности, практика создания контрольно-измерительных и управляющих систем. Для облегчения составления программ в настоящее время применяются языки автоматического программирования (специализированные моделирующие языки), которые позволяют при наименьших затратах времени на подготовку и реализацию задач на ЭВМ строить и исследовать программы, моделирующие работу исследуемой системы.

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

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

Рассмотрим некоторые специализированные алгоритмические языки моделирования.

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

Алгоритмический язык SIMSCRIPT принято считать наиболее мощным моделирующим языком в настоящее время. Благодаря ряду своих уникальных черт он применим для самого широкого класса задач. Однако этот язык сравнительно сложен, диагностические средства для отладки программ ограничены. Кроме того, потенциальный потребитель этого языка должен знать ФОРТРАН, иметь опыт программирования.

Внимание специалистов, связанных с решением проблем моделирования, привлекают специализированные языки, разработанные для этих целей на базе АЛГОЛа. Среди таких языков автоматического программирования наиболее совершенными являютсяSIMULA и SOL (СОЛ).

Примером одного из наиболее удачных специализированных алгоритмических языков, предназначенных для моделирования дискретно изменяющихся систем, является язык СОЛ - Simulation Orientated Language.

Язык СОЛ построен на базе универсального языка программирования АЛГОЛ, имеет такую же структуру и использует основные его элементы. Для описания широкого класса процессов с дискретными событиями СОЛ представляет универсальную систему понятий, и потому он во многих отношениях очень похож на проблемно-ориентированные языки автоматического программирования, такие, как АЛГОЛ или ФОРТРАН. Однако языку СОЛ присущи основные черты, отличающие его от этих языков: СОЛ обеспечивает механизм моделирования асинхронных параллельных процессов, удобные обозначения для случайных элементов внутри арифметических выражении, автоматические средства сбора статистических данных о компонентах моделируемой системы. С другой стороны, многие черты проблемно-ориентированных универсальных языков не используются в СОЛе не потому, что они несовместимы с ним, а скорее потому, что они вносят большие усложнения в его схему, не расширяя его возможности. Принципы, положенные в основу построения языка и написания моделирующих программ на нем, позволяют строить модели сложных систем в удобной для чтения форме.

ПЛ/ I . Название языка происходит от английских слов Programming Language/One.

Язык ПЛ/I появился после создания целого ряда весьма совершенных языков, и, конечно, эти языки-предшественники оказали существенное влияние на его структуру. Так, в нем сохранены от АЛГОЛа блочная структура программы, возможность динамического распределения памяти, имеется аппарат вызова процедур, способ задания форматов, используемый в ФОРТРАНе, и т. д. Но много и новых черт. Язык удобен для моделирования, решения логических задач, исследования логических схем, решения задач в реальном масштабе времени, разработки систем математического обеспечения. Возможно использование разного типа данных (двоичных, десятичных, символьных, комплексных чисел, матриц и т. д.), однако весьма сложно организовывать эти данные в массивы, таблицы, тексты, анкеты, картотеки и т. и. Имеется большой набор стандартных функций и процедур. В языке ПЛ/I разработана удачная система операции, управляющих всеми процессами ввода, вывода и обмена информацией между основными и запоминающими устройствами. Все эти особенности производят впечатление сильной перегруженности языка. Следует иметь в виду и недостатки: описание языка неудовлетворительно, оно не формализовано.

ПЛ/I - многоцелевой язык программирования, предназначенный не только для экономического и научно-технического программирования, но также для программирования работ в реальном масштабе времени и для создания систем программирования.

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

В языке ПЛ/I каждому описателю переменной, каждой уточняющей конструкции-дополнению и каждой спецификации придана «интерпретация (принцип) умолчания». Это означает, что всюду, где язык предоставляет несколько возможностей, а программист не указал никакой, компилятор применяет «интерпретацию умолчания», т. е. подразумевается некоторая из возможностей, предусмотренная в языке на этот случай. В качестве таких подразумеваемых для каждой конструкции возможностей в языке выбраны те, которые, вероятнее всего, потребуются программисту.

Программы на языке ПЛ/I пишутся в свободной форме; программист может сам разработать нужные ему формы записи программ. При этом обеспечен доступ ко всем средствам системы ЭВМ.

Операторы программы, записанной на языке ПЛ/I, объединяются в «блоки». Блоки выполняют важные функции: они определяют область действия переменных и других имен, так что одно и то же имя в разных блоках может использоваться для различных целей; они позволяют отводить ячейки памяти под переменные только на время выполнения данного блока и освобождать их для использования в других целях по прекращении работы блока.

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

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

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

На основании этой информации транслятор РПГ формирует рабочую программу, и затем созданная программа обрабатывает входные файлы и печатает требуемый отчет.

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

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

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

После написания программы на соответствующих бланках текст программы перфорируется на картах.

Для получения рабочей программы сначала нужно выполнить трансляцию исходной программы. Для этого к картам исходной программы добавляются некоторые управляющие карты, такие, как управляющая карта транслятора РГ1Г и карты управляющих операторов - УПРАВЛЕНИЯ ЗАДАНИЯМИ, необходимые для работы транслятора РПГ. После трансляции полученный модуль может быть отредактирован с помощью РЕДАКТОРА. В результате редактирования получается готовая для выполнения программа (загрузочный модуль), которая называется рабочей программой. Компиляция и редактирование необходимы для получения желаемого отчета.

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

АЛГАМС. Алгоритмический язык АЛГАМС ориентирован на машины средней мощности; основой его стало подмножество языка АЛГОЛ-60.

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

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

При вводе текста последовательным элементам массива начиная с указанного объекта ввода присваиваются целые значения, соответствующие последовательным символам вводимой строки в смысле процедуры=ТЕХТ. Процедура = ТЕХТ определяется следующим образом: <оператор текст> ::=ТЕХТ (<строка>, <переменная с индексами>).

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

БЭЙСИ К. Название языка происходит от английских слов Beginners all Purpose Symbolic Instructioncode. Он получил широкую популярность благодаря своей простоте, легкости в изучении и большим возможностям для решения самых различных задач. Во многих мини-ЭВМ этот язык принят в качестве основного разговорного языка. Язык БЭЙСИК представляет собой язык программирования. Он удобен для решения научно-технических задач небольшого объема как по количеству выполняемых операций, так и по количеству исходных и результирующих данных. Важнейшей особенностью языка является то, что он приспособлен для шаговой реализации. Это означает, что после каждого изменения исходного текста программы на языке БЭЙСИК можно перетранслировать не всю-программу, а только те ее операторы, которые были изменены. Возможность шаговой реализации языка БЭЙСИК позволяет сократить затраты машинного времени на перетрансляцию. Это в свою очередь позволяет ускорить цикл отладки настолько, что становится целесообразной отладка БЭЙСИК-программ в режиме диалога.

Помимо возможности накапливать большие программы, состоящие из перенумерованных операторов языка БЭЙСИК, предусмотрены так называемые прямые команды, т. е. такие, которые исполняются тотчас же после ввода их с пульта программиста (с телетайпа). В режиме прямых команд могут использоваться не только административные директивы типа RUN-запуск исполнения, LIST - распечатка текста, SAVE - сохранить текст программы в библиотеке, BYE - конец сеанса работы; любой оператор языка БЭЙСИК, введенный без порядкового номера, исполняется в режиме прямой команды. Это позволяет, в частности, распечатывать и изменять значения переменных в любой момент выполнения программы.

Служебное слово Выполняемое действие

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

INPUT Ввести числа с пульта программиста и заслать их в указанные переменные

LET Присвоить переменной значение выражения

GO ТО Перейти к выполнению оператора с заданным номером

IF Если заданное условие выполнено, то необходимо выполнить действие, указанное в данном операторе, иначе - перейти к выполнению следующего оператора

DATA Данные; этот оператор не выполняется. Он описывает блок отладочных данных (чисел). Совокупность блоков отладочных данных образует массив отладочных данных

END Конец программы

Таким образом, шаговая схема компиляции в сочетании с режимом прямых команд позволяет эффективно отлаживать БЭЙСИК-программы в режиме диалога.

Программа на языке БЭЙСИК состоит из операторов, каждый из которых начинается со служебного слова. Служебное слово определяет тип оператора и характер действий, осуществляемых при его выполнении.

При решении многих задач необходимо представление данных в виде таблиц. Используя возможности некоторых операторов языка БЭЙСИК, можно формировать таблицы различных форматов.

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

На данный момент на земле проживает около 2000 народов. Их отличительным признаком, прежде всего, является язык.

Наряду с разговорными (естественными) человечество создало множество искусственных языков. Каждый из них предназначен для решения конкретных задач.

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

Определения

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

Основа большинства как искусственных, так и естественных языков — алфавит.

Он представляет собой набор символов, используемых для составления слов и фраз.

Язык характеризуется:

• набором используемых знаков;
• правилами составления из них «слов», «фраз» и «текстов»;
• набором правил (синтаксических, прагматических и семантических) использования составленных конструкций.

Характеристики естественных языков

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

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

• неоднозначность большинства слов;
• существование синонимов и омонимов;
• наличие нескольких названий у одного и того же предмета;
• существование исключений из практически всех правил.

Все эти характеристики являются главными отличиями естественных знаковых систем от формальных языков. Примеры неоднозначностей слов и высказываний известны всем. Так слово «эфир» в зависимости от контекста может означать, как вещество, так и радио- или телевещание.

При этом основными функциями разговорных языков являются:

• общение;
• познавательная деятельность;
• выражение эмоций;
• воздействие на собеседника (корреспондента, если речь идет о переписке).

Характеристики искусственных языков

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

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

Формальные языки и грамматики

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

Схема построения формальных знаковых система следующая:

• выбирается алфавит (совокупность исходных символов);
• задаются правила построения выражений (синтаксис) языка.

Сфера применения

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

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

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

Язык формальной логики

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

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

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

Особенности языков программирования

Как уже было сказано, их с некоторыми оговорками можно отнести к классу формальных.

С последними их объединяют многие синтаксические правила, а с естественными некоторые ключевые слова и конструкции.

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

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

Грамматики

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

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

Классификация языков программирования

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

Теперь вы сможете ответить на вопрос: “Какие формальные языки вам известны?”. Ученые продолжают совершенствовать их, с целью сделать возможными решение различных практических и теоретических задач, которые на данный момент считаются неразрешимыми.