Некоторый непустой подалфавит алгоритмического языка используется для кодирования исходной (перерабатываемой) информации. Известно, что даже двухбуквенный алфавит достаточен для кодирования любой информации. Однако указанный алфавит обычно расширяется для возможности более удобного и экономного кодирования. Правила преобразования информации в различных алгоритмах весьма разнообразны и качественно различны. Однако все конкретные алгоритмы могут быть составлены из весьма небольшого числа элементарных предписаний. Наборы предписаний, из которых могут быть построены любые мыслимые алгоритмы, называются алгоритмически полными. Алгоритмический язык называется универсальным, если в нем может быть описан алгоритмически полный набор предписаний (а тем самым любой алгоритм). Задание универсального алгоритмического языка равносильно заданию алгоритмической системы, то есть общего способа записи алгоритмов.
Специфика алгоритмического языка выражается, главным образом, в его семантике и заключается в том, что предложения языка должны быть алгоритмами, то есть последовательностями предписаний, при помощи которых осуществляется переработка информации (реализуется алфавитное отображение). В каждом алгоритмическом языке должны быть средства для задания операторов, осуществляющих переработку информации, и операторов перехода (распознавателей), определяющих порядок выполнения этих операторов. Операторы, в свою очередь, могут обозначать последовательности других более элементарных операций. Например, оператор умножения многозначных чисел обозначает последовательность некоторых действий над однозначными числами.
Языки, с помощью которых строятся классические системы (нормальные алгоритмы Маркова, рекурсивные функции, машины Тьюринга, машины Поста и др.), несмотря на их универсальность, оказались практически неприемлемыми для описания алгоритмов решения задач при их реализации на ЭВМ. Данное обстоятельство является результатом того, что все эти системы ориентированы на рассмотрение фундаментальных теоретических вопросов теории алгоритмов и уже запись одного сколь-нибудь сложного алгоритма в любой из этих систем представляет собой самостоятельную трудную задачу. В связи с этим решение практических задач с помощью ЭВМ вызвало появление большого числа работ, посвященных созданию так называемых языков программирования, для которых алгоритмические языки служат теоретической основой.
Языки программирования
Языки программирования (я. п.) - формальные языки связи человека с цифровой вычислительной машиной, предназначение для описания данных (информации) и алгоритмов (программ) их обработки на вычислительной машине. Язык программирования задается своим синтаксисом и семантикой - множеством правил, определяющих, какой вид фраз можно использовать для задания программ и каково их функциональное значение.
Каждый язык программирования посредством своего синтаксиса и семантики определяет некоторый присущий ему процессор (преобразователь), реальный или мыслимый, которым этот язык, в свою очередь, определяется однозначно. Таким образом, программа на данном языке программирования определяет порядок и вид действий, которые должен выполнить соответствующий данному языку процессор при ее реализации. На практике такой процессор состоит из “языкового процессора” и ЭВМ.
Программу для вычислительной машины, позволяющую ей "понимать" директивы и предложения входного языка, используемого программистами, мы будем называть "языковым процессором". Вообще говоря, существует два типа таких программ для обработки языков: интерпретаторы и трансляторы.
Интерпретатор - это программа, которая допускает в качестве входа исходную программу, записанную на языке программирования называемом исходным языком, и производит пооператорное (покомандное) ее выполнение и соответствующие вычисления, предписываемые этой программой.
Транслятор - это программа, которая допускает в качестве входа программу на исходном языке, а в качестве выхода выдает другую версию этой программы, написанную на другом языке, который называется объектным языком. Объектный язык обычно является машинным языком некоторой вычислительной машины, причем в этом случае программу можно сразу же выполнять.
Существует довольно условное деление трансляторов на ассемблеры и компиляторы, которые транслируют соответственно языки низкого и высокого уровней. В основе всех процессов обработки языков лежит теория автоматов и формальных языков.
Основные требования, предъявляемые к языкам программирования - обеспечение обозримости, определенного удобства в их использовании, и эффективной реализации их процессоров.
Возникновение и развитие языков программирования неразрывно связано с развитием ЭВМ и с расширением сферы их применения. Языками программирования являются, например, внутренние машинные языки (то есть языки непосредственной интерпретации ЭВМ, задаваемые системами команд этих ЭВМ), которые явились первыми языками программирования.
Существующие в настоящее время языки программирования подразделяют на четыре больших класса: машинно-ориентированные, процедурно-ориентированные, проблемно-ориентированные и объектно-ориентированные. К машинно-ориентированным языкам программирования относятся языки, в которых с одной стороны явно выражена связь с конкретной ЭВМ (структура команд, памяти, внешних устройств и т. д.), а с другой - в язык введены элементы, упрощающие и автоматизирующие процесс программирования (символьное обозначение команд и ячеек памяти, широкое использование привычных для человека обозначений и т. д.). Машинно-ориентированные языки программирования позволяют писать программы, не уступающие по эффективности программам, написанным непосредственно в кодах машины, но в значительной степени облегчают работу по их созданию и отладке. В зависимости от степени связи человека с ЭВМ, машинно-ориентированные я. п. делятся на машинные я. п., автокоды (или ассемблерные языки) и машинно-независимые я. п. (для нескольких машин).
Процедурно-ориентированные языки представляют собой следующий более высокий уровень я. п., предназначаемый для различных сфер применения ЭВМ и учитывающих специфику этих применений.
Во всяком языке программирования можно выделить две самостоятельные части. Первая из них предназначается для описания объектов перерабатываемой информации (исходных, промежуточных и окончательных результатов), а вторая - набор средств для описания процессов переработки этих данных. В зависимости от ориентации языка указанные части могут быть более или менее развиты. Так, в языках ориентированных на решение научно-технических задач вычислительного характера, первая часть языка, как правило, незначительна и состоит из описания типов числовых данных (целые, вещественные, булевы), иногда дополняемого описанием некоторых других величин (векторных, строчных и др.), а вторая - довольно сильно развита.
Другие языки, например, ориентированные на обработку экономических данных, характеризуются более развитым аппаратом, предназначенным для описания перерабатываемой информации, которая, как правило, представляет собой совокупность объектов сложной структуры. Под сложностью структуры данных подразумевается их представление в виде "дерева", количество ярусов которого может практически достичь нескольких десятков и каждый из ярусов может иметь большое количество вершин.
Из наиболее ранних зарубежных я. п., ориентированных на класс вычислительных и научных задач, наибольшее распространение получил язык ФОРТРАН. Значение ФОРТРАНА определяется его широким распространением, реализацией на всех более или менее распространенных ЭВМ, а также наличием огромных библиотек, насчитывающих сотни и тысячи программ, описанных на этом языке. Использование процедурно-ориентированных языков явилось мощным толчком к разработке и созданию систем автоматического программирования как транслирующего, так и интерпретирующего типов.
Среди языков, выражающих основные понятия проблемы обработки экономической информации, наиболее видное место занимает КОБОЛ. Обширный аппарат этого языка направлен на эффективное использование характерных особенностей современных ЭВМ.
КОБОЛ допускает эффективное описание алгоритмов, оперирующих с данными сложной иерархической структуры. Основным понятием в КОБОЛЕ является понятие записи как единицы информации, состоящей в общем случае из структуры данных, включающей числовые (номер, цена, количество и т.д.), нечисловые данные (фамилия, название объекта, шифр и т.п.) и массивы (файлы) записей - упорядоченного их ряда. Записью может быть строка ведомости, наряд на отгрузку и др. Над этими данными могут выполняться сравнительно простые операции, такие как поиск (адресный и ассоциативный по совокупности определенных признаков), пересылка, сортировка, редактирование и др.
Расширение сфер использования ЭВМ привело к необходимости решать задачи, компактное описание которых выходит за рамки одного процедурно-ориентированного языка. Попытки использовать процедурно-ориентированные языки для решения задач, выходящих за пределы их ориентации, привели к практически непреодолимым трудностям. Так возникли проблемно-ориентированные я.п., то есть я.п. предназначенные для описания специальных проблем и решения определенного класса задач. Программа работы на таком языке содержит, помимо описания условия задачи, указания решить задачу данного класса. Примерами таких языков являются язык ЛИСП, предназначенный для описания процессов обработки информации, представленной в виде списков, и язык ПРОЛОГ, предназначенный для разработки программ и систем искусственного интеллекта. Языком такого рода является также язык STRESS, предназначенный для описания задач конструирования. Программа на языке STRESS содержит описание общих характеристик системы (размерности, число вершин и др.) и данные, а также указание: решить задачу и представить определенные данные в виде некоторой таблицы. Развитие таких языков имеет весьма важное практическое значение в силу чрезвычайной простоты их использования.