Рисунок 1. Структура машины Тьюринга
Одной из главных отличительных черт любого системного или прикладного приложения является возможность работать в сети. Сейчас мы наблюдаем экспоненциальный рост самой большой информационной сети, когда-либо создававшейся человеком - Internet. И современное приложение должно не просто уметь работать с сетью, а по возможности представлять собой распределенную программную систему, части которой взаимодействуют между собой через Internet. В соответствии с этим приложение должно быть кросс-платформенным, т.е. иметь возможность выполняться на как можно большем количестве компьютерных архитектур. Таким образом, приходим к к тому, что приложение должно выполняться в рамках т.н. виртуальной машины, представляющей собой программно моделируемый компьютер, эмуляция которого возможна на большинстве современных аппаратных платформ без существенной потери производительности.
Путём теоретических и опытных исследований доказано, что наиболее оптимальной для технологии виртуальной машины является т.н. стековая архитектура. В настоящее время актуальной является задача трансляции языков, созданных для других архитектур (фон-неймановской, функциональной и др.) в функциональные аналоги для стековой архитектуры.
Целью работы является исследование возможности трансляции программы, написанной в терминах функциональной парадигмы, в аналогичную программу для стековой архитектуры. В соответствии с поставленной целью основными задачами являются:
Научная новизна работы заключается в том, что можно на практике подтвердить инвариантность различных моделей вычислимости, доказав, что любой программе, записанной в терминах одной парадигмы (в данном случае - функциональной) можно найти функциональный аналог в терминах другой парадигмы (стековой).
Практическая ценность состоит в реализации транслятора функционального языка, генерируемый код которого будет кросс-платформенным, т.е. отпадает многие проблемы, связанные с переносимостью приложений.
Реализация результатов работы данного исследования состоит в том, что полученный в результате транслятор можно использовать удалённо. В частности, планируется его использование в системе дистанционного обучения функциональным языкам, которая разрабатывается в ДонНТУ.
Под алгоритмом будем понимать точное предписание о порядке выполнения системы операций для решения всех задач данного типа. Вычислимость алгоритма - это реальная или потенциальная возможность представить алгоритм как программу для одной из моделей (систем) вычислимости.
К настоящему времени существует множество систем вычислимости. Среди наиболее известных можно назвать следующие: машины Тьюринга (1936), рекурсивные функции Чёрча (1936), нормальные алгоритмы Маркова (1951), комбинаторные процессы Поста (1936).
В своё время было доказано для каждой системы вычислимости, что она может быть использована для моделирования всех остальных, т.е. модели вычислимости инвариантны. На основе этого был сформулирован основной принцип теории алгоритмов - принцип Чёрча, который говорит, что любое вычисление, для которого существует эффективная процедура, может быть смоделировано на машине Тьюринга (машине Поста, конечном автомате Маркова, последовательности рекурсивных функций Чёрча). По самой своей природе это утверждение недоказуемо, поскольку не существует строго определения термина "эффективная процедура". Тем самым принцип Чёрча является аксиомой, не требующей доказательства, которая формализует понятие алгоритма ("эффективной процедуры") и в силу статуса аксиомы опровергающего контрпримера иметь не может.
Рассмотрим наиболее изученный класс систем вычислимости - машину Тьюринга, которая была предложена А.М. Тьюрингом в 1936 г.
Машина Тьюринга (в классическом виде) имеет только одну структуру данных - линейный массив Т переменной длины, называемый лентой. Каждый элемент ленты содержит одну литеру. Имеется также простая переменная Н, называемая головкой чтения, которая всегда содержит указатель на некоторый на некоторый элемент Т. Этот указатель может быть представлен целым индексом, и таким образом Н может рассматриваться как простая целая переменная. Эта структура изображена на рисунке 1:
Машина Тьюринга может выполнять только несколько простых операций:
Получить значение Т[Н], сравнить его с некоторой известной литерой и изменить последовательность выполнения дальнейших операций в зависимости от того, совпадают литеры или нет.
Присвоить Т[Н] новое значение - некоторую новую литеру.
Увеличивать или уменьшать значение Н на 1, показывая тем самым продвижение вперёд, к следующему элементу ленты, или возвра-щение его назад, к предыдущему элементу. Если эта операция при-ведёт к выходу Н за пределы ленты, то лента расширяется в соот-ветствующем направлении путём добавления нового элемента, содержащего специальную литеру #. Индексом этого элемента является текущее значение Н.
Остановиться.
Порядок работы машины Тьюринга:
На ленту записывается некоторая входная цепочка длиной N, где N - длина ленты.
Переменной Н присваивается начальное значение 1.
Производится чтение элемента ленты из ячейки с номером H.
В зависимости от содержания элемента выполняется одна из операций 1-4.
Если не операция 4, то переход к пункту 3.
С помощью машин Тьюринга можно смоделировать целый класс формальных языков, называемых императивными. Такие языки основаны на концепции обновляемой памяти, т.е. наборе ячеек (ленты), содержимое которых изменяется при выполнении команд. Базовой в них является операция присваивания. Таким образом, алгоритм, составленный на таком языке, изменяет своё окружение (контекст). На обновляемой памяти основана архитектура фон Неймана, применяемая в большинстве современных вычислительных машин, как наиболее просто реализуемая на существующей элементной базе.
Однако у этой модели есть недостатки, из-за которых возникают побочные эффекты. Их причиной является то, что не всегда результат работы алгоритма в данной модели однозначно определяется исходными данными, так как строгое соблюдение этого правила приводит к снижению производительности. Это приводит к быстрому росту сложности программы и, начиная с некоторого порога, невозможно правильно верифицировать программу и доказать её правильность.
Другая известная модель вычислимости - рекурсивные функции Чёрча (лямбда-исчисление), которая является теоретическим фундаментом другой большой группы формальных языков, объединённых названием "функциональные". Согласно этой модели, алгоритм решения задачи можно представить в виде последовательности вложенных друг в друга функций. При этом пользуются математическим определением функции, определяющим функцию как некое правило, отображающее область аргументов функции в область её значений, причём значения определяются по значениям аргументов единственным образом.
Программа на языке, использующем концепцию лямбда-исчисления, выглядит как композиция конечного набора функций, каждая из которых, в свою очередь, может быть композицией ещё более элементарных функций, и т.д. При этом каждая функция может прямо или косвенно осуществлять рекурсию, т.е. вызов самой себя. Данная модель лишена недостатков машин Тьюринга, описанных выше, в силу своей структуры, изначально требующей определения функций, значения которых зависят исключительно от аргументов функции и не зависят от контекста вызова и выполнения.
Рассмотрим также модель вычислимости, основанную на конечных автоматах. Близость к булевой алгебре и теории графов, наглядность графического представления и детерминированность поведения являются заметными достоинствами этой системы. Чтобы определить место конечных автоматов среди других моделей, рассмотрим сети Петри, занимающие промежуточное положение между машинами Тьюринга и конечными автоматами.
Сети Петри работают в терминах условий и событий, где первым сопоставлены позиции (особые узлы - емкости для хранения фишек связаны ориентированными дугами с переходами), а последним - переходы (особые узлы-действия, перемещающие фишки и связанные ориентированными дугами с позициями).
Конечные автоматы являются частным случаем сетей Петри и эквивалентны автоматным сетям Петри - сетям, в которых каждый переход может иметь точно одну входную и одну выходную позицию.
Сети Петри лучше всего подходят для описания любых асинхронных систем (асинхронное программирование), тогда как конечные автоматы - лишь для сугубо последовательных систем (автоматное программирование). Наглядность динамики и композиционные возможности сетей Петри выше, чем у конечных автоматов, но при этом компактность представления предпочтительнее у последних.
Что касается отношения к машине Тьюринга, то достаточно расширить сеть Петри сдерживающими дугами (позволяющими определять отсутствие фишек в данной позиции), как она тут же становится эквивалентной машине Тьюринга. Очевидно, что чем "мощнее" абстракция, чем больше она позволяет синтезировать возможностей, тем сложнее её анализировать. Иными словами, конечные автоматы анализировать гораздо проще, чем классические сети Петри и, тем более, машины Тьюринга. Они широко применяются в тех областях, где представимость алгоритма в виде множества состояний и переходов между состояниями достаточно очевидна. Рассмотренные модели вычислимости являются наиболее теоретически изученными и широко применяемыми.
Функциональное программирование
Функциональное программирование представляет из себя одну из альтернатив императивному подходу. В императивном программировании алгоритмы - это описания последовательно исполняемых операций. Здесь существует понятие "текущего шага исполнения" (то есть, времени), и "текущего состояния", которое меняется с течением этого времени.
В функциональном программировании понятие времени отсутствует. Программы являются выражениями, исполнение программ заключается в вычислении этих выражений. Практически все математики, сами того не замечая, занимаются функциональным программированием, описывая, например, чему равно абсолютное значение произвольного вещественного числа.
Императивное программирование основано на машине Тьюринга. Функциональное программирование основано на более естественном с математической точки зрения формализме - лямбда-исчислении Черча.
Как правило, рассматривают так называемое "расширенное лямбда-исчисление". Его грамматику можно описать следующим образом:
Выражение ::= Простое выражение | Составное выражениеКонстантами в расширенном лямбда-исчислении могут быть числа, кортежи, списки, имена предопределенных функций, и так далее.
Результатом вычисление применения предопределенной функции к аргументам будет значение предопределенной функции в этой "точке".
Результатом применения лямбда-абстракции к аргументу будет подстановка аргумента в выражение - "тело" лямбда-абстракции. Сами лямбда-абстракции так же являются выражениями, и, следовательно, могут быть аргументами.
Видно, что лямбда-абстракции имеют всего один аргумент. В то же время, функции в традиционном понимании не обязаны быть одноместными. Пред-ставления функций от нескольких аргументов можно достичь двумя способами:
1) Считать, что аргумент является кортежем. Например, apply = lambda (f, x) -> ( f x ) end можно понимать как apply = lambda y -> ( ( first y ) ( second y ) ) end. 2) Понять, что множество вычислимых функций X * Y -> Z очевидным образом взаимнооднозначно отображается в множество вычислимых функций X -> (Y -> Z) (так называемые карризованные функции). Так, apply = lambda f -> lambda x -> (f x) end end.Когда не надо будет ставить скобки вокруг применения функций к аргументам, можно объявить операцию применения функции (которая при записи опускается, так же, как в математике принято не писать явно символ умножения) левоассоциативной, то есть, понимать запись вида f x y как ((f x) y). Это - традиционное соглашение, поэтому никакие "стандарты" при этом не нарушаются.
Чистое лямбда-исчисление Черча позволяет обходится исключительно именами, лямбда-абстракциями от одного аргумента и применениями выражений к выражениям. Оказывается, в этих терминах можно описать и "предопределенные" константы (числа и т.п.), структуры данных (списки, кортежи...), логические значения и ветвление. Более того, в чистом лямбда-исчислении можно обойтись без квалифицированных выражений, и, следовательно, выразить рекурсию, не используя для этого употребления имени функции в теле функции. Некоторые экспериментальные модели функционального программирования позволяют обходится без каких-либо имен вообще.
Функциональное программирование обладает следующими двумя примечательными свойствами:
1) Аппликативность: программа есть выражение, составленное из применения функций к аргументам. 2) Настраиваемость: так как не только программа, но и любой программный объект (в идеале) является выражением, можно легко порождать новые программные объекты по образцу, как значения соответствующих выражений (применение порождающей функции к параметрам образца).Настраиваемость активно используется в таком направлении программирования, как generic programming. Основная задача, решаемая в рамках это направления - создание максимально универсальных библиотек, ориентированных на решение часто встречающихся подзадач (обработка агрегатных данных; потоковый ввод-вывод; взаимодействие между программами, написанными на разных языках и различающихся в деталях семантики; универсальные оконные библиотеки). Эти направления наиболее ярко представлены в STL - стандартной библиотеке шаблонов (контейнеров) языка С++, а так же в реализации платформы .NET фирмы Microsoft.
Для обеспечения видовой корректности программ в функциональные языки вводят специальные системы типов, ориентированные на поддержку настраиваемости. Как правило, трансляторы функциональных языков могут самостоятельно определять типы выражений, без каких-либо описаний типов вообще. Так, функция add = lambda x -> lambda y -> x+y end end будет иметь тип number -> number -> number, а уже рассмотренная выше функция apply - тип any(X).any(Y).(X->Y)->X->Y, где any обозначает "квантор всеобщности" для типов, а X и Y являются переменными.
Можно заметить, что так как порядок вычисления подвыражений не имеет значения (так как понятия состояния у функциональной программы нет), функциональное программирование может быть естественным образом реализовано на платформах, поддерживающих параллелизм. Потоковая модель функционального программирования является естественным представлением функциональных программ в терминах систем взаимодействующих процессов.
Функциональное программирование, как и другие модели "неимперативного" программирования, обычно применяется для решения задач, которые трудно сформулировать в терминах последовательных операций. Практически все задачи, связанные с искусственным интеллектом, попадают в эту категорию. Среди них следует отметить задачи распознавания образов, общение с пользователем на естественном языке, реализацию экспертных систем, автоматизированное доказательство теорем, символьные вычисления, построение трансляторов. Эти задачи далеки от традиционного прикладного программирования, поэтому им уделяется немного внимания в обычных учебных программах по программированию.
С созданием компьютеров, возникла потребность в общении с подобными устройствами, поскольку оказалось необходимым передавать им приказы, задания и описания работы, которую они должны выполнять. Для этой цели начали разрабатывать специальные языки, которые стали называть искусственными в отличие от естественных языков общения людей. Искусственные языки должны быть, с одной стороны, удобными и понятными для человека, а с другой - должны восприниматься устройствами. Совмещение этих требований в одном языке оказалось трудной задачей, поэтому появились средства для преобразования текстов с языка, понятного человеку, на язык устройства. Такие средства назвали трансляторами.
Транслятор может быть интерпретирующего или компилирующего типа. В первом случае его называют интерпретатором входного языка, а во втором - компилятором. Интерпретатор последовательно читает предложения входного языка, анализирует их и сразу же выполняет, а компилятор не выполняет предложения языка, а строит программу, которая может в дальнейшем быть запущена для получения результата. На вход компилятора подается текст, написанный на входном языке - языке, понятном человеку, а результатом работы компилятора является текст на языке, понятном устройству.
Работа компилятора состоит из нескольких стадий, которые могут выполняться последовательно, либо совмещаться по времени. Эти стадии могут быть представлены в виде схемы (см. рисунок 2):
Первая стадия работы компилятора называется лексическим анализом, а программа, её реализующая, - лексическим анализатором (ЛА). На вход лекси-ческого анализатора подаётся последовательность символов входного языка. ЛА выделяет в этой последовательности простейшие конструкции языка, кото-рые называют лексическими единицами. Примерами лексических единиц яв-ляются идентификаторы, числа, символы операций, служебные слова и т.д. ЛА преобразует исходный текст, заменяя лексические единицы их внутренним представлением - лексемами. Лексема может включать информацию о классе лексической единицы и её значении. Кроме того, для некоторых классов лексических единиц ЛА строит таблицы, например, таблицу идентификаторов, констант, которые используются на последующих стадиях компиляции.
Вторую стадию работы компилятора называют синтаксическим анализом, а соответствующую программу - синтаксическим анализатором (СА). На вход СА подается последовательность лексем, которая преобразуется в промежуточный код, представляющий собой последовательность символов действия или атомов. Каждый атом включает описание операции, которую нужно выполнить, с указанием используемых операндов. При этом последовательность расположения атомов, в отличие от лексем, соответствует порядку выполнения операций, необходимому для получения результата.
На третьей стадии работы компилятора осуществляется построение выходного текста. Программа, реализующая эту стадию, называется генератором выходного текста (Г). Генератор каждому символу действия, поступающему на его вход, ставит в соответствие одну или несколько команд выходного языка. В качестве выходного языка могут быть использованы команды устройства, команды ассемблера, либо операторы какоголибо другого языка.
Рассмотренная схема компилятора является упрощенной, поскольку реальные компиляторы, как правило, включают стадии оптимизации.
Для построения компилятора необходимо однозначное и точное задание входного и выходного языков. Такое задание предполагает определение правил построения допустимых конструкций (выражений) языка. Множество таких правил называют синтаксисом языка. Кроме того, задание должно включать описание назначения и смысла каждой конструкции языка. Такое описание называют семантикой языка.
Для построения точных и недвусмысленных описаний применяют метод абстракций, который предполагает выделение наиболее существенных свойств рассматриваемого объекта и опускание свойств, менее значимых для рассматриваемого случая. Например, при построении модели входных языков можно рассматривать входной текст как последовательность символов, построенную по определенным правилам, отвлекаясь от характера начертания символов и их расположения на листе. Математические модели, использующие представление текстов в виде цепочек символов, называют формальными языками и грамматиками.
Грамматика определяется терминальным словарем, множеством правил и начальным символом. С помощью правил грамматики можно строить выводы цепочек, состоящих из терминальных символов. Множество таких цепочек, выводимых из начального символа грамматики, образует формальный язык, задаваемый грамматикой.
В зависимости от ограничений, накладываемых на вид правил, формальные грамматики и порождаемые ими языки делятся на четыре типа (т.н. классификация по Хомскому): общего вида или естественные, контекстно-зависимые, контекстно-свободные, автоматные. На практике чаще всего ис-пользуются контекстно-свободные и автоматные языки и грамматики.
Графическим изображением вывода цепочки с помощью правил грамматики является дерево вывода или синтаксическое дерево. Каждой цепочке, выводимой в грамматике, может соответствовать одно или несколько деревьев вывода. Если цепочке соответствует не одно, а несколько деревьев вывода, то её называют неоднозначной, и грамматику, порождающую такую цепочку, также называют неоднозначной. Для таких грамматик процедура восстановления вывода для заданной цепочки значительно усложняется.
Для задания правил используются различные формы описания: символическая, форма Наура-Бэкуса, итерационная форма и синтаксические диаграммы.
В практических применениях вместо символического представления схем грамматик обычно используют форму Наура-Бэкуса, или синтаксические диаграммы.
При описании синтаксиса конкретных языков программирования приходится вводить большое число нетерминальных символов, и символическая форма записи теряет свою наглядность. В этом случае применяют форму Наура-Бэкуса (ФНБ), которая предполагает использование в качестве нетерминальных символов комбинаций слов естественного языка, заключенных в угловые скобки, а в качестве разделителя - специального знака, состоящего из двух двоеточий и равенства. Например, если правила L и E записаны в символической форме, и символ L соответствует синтаксическому понятию список, а символ E - "элемент списка", то их можно представить в форме Наура-Бэкуса так: <список>::= <элемент списка><список>, <список>::= <элемент списка>.
Чтобы сократить описание схемы грамматики, в ФБН разрешается объединять правила c одинаковой левой частью в одно правило, правая часть кото-рого должна включать правые части объединяемых правил, разделенные вертикальной чертой. Используя объединение правил, для рассматриваемого примера получаем: <список>::=<элемент списка><список>|<элемент списка>.
Задача построения формальных грамматик состоит в том, что для заданного в виде описания на естественном языке множества конечных цепочек, требуется построить формальную грамматику, порождающую это множество цепочек. Учитывая, что терминальный словарь грамматики должен включать все символы, используемые для построения цепочек, входящих в заданное множество, результатом решения задачи должны явиться нетерминальный словарь и схема грамматики.
Построение этих объектов представляется весьма сложным, поскольку оно должно выполняться неформально и требует мысленного охвата всевозможных вариантов построения цепочек заданного множества и синтеза правил их построения. Построение усложняется еще и тем, что оно, как и всякая другая задача синтеза, имеет много решений.
Основой создания правил грамматики является способ выделения структуры заданного множества цепочек. Этот способ предусматривает расчленение цепочек, входящих в заданное множество, на части таким образом, чтобы выявить повторяющиеся части цепочек и части, входящие во все цепочки в неизменном виде. Такое расчленение на части представляет собой выявление структуры цепочек заданного множества.
Для каждого выявленного элемента структуры вводятся обозначения. Множество таких обозначений составляет основу словаря нетерминальных символов некоторой грамматики. Следующим шагом построения является выявление последовательностей, в которых элементы структуры могут входить в заданные цепочки. Такие последовательности являются основой для построения правил грамматики.
Основные результаты работы
Результатом работы явялется доказательство тезиса Чёрча о инвариантности моделей вычислимости путём построени транслятора функционального языка Лисп для платформы Microsoft .NET. При этом апробированы известные алгоритмы теории трансляции в контексте нового окружения среды выполнения (в данном случае - платформа Common Language Runtime).