Язык программирования FPTL и средства работы с ним
Краткое описание языка FPTL

Автор: Mikhail Vorontsov
МЭИ

Опубликовано: 20.12.2006
Версия текста: 1.2

Общее

Функциональный язык программирования FPTL (Functional Programming Typified Language) был разработан профессорами МЭИ Кутеповым В.П. и Фальком В.Н. В данный момент ведется разработка нескольких проектов по данному языку: транслятора с FPTL на Java, среды выполнения для кластеров и многоядерных систем, среды разработки программ. Основное назначение данного языка (по мнению его авторов) – это выполнение высокопроизводительных вычислений. В данный момент язык не представляет каких-либо средств работы с пользовательским интерфейсом (создание оконнных приложений на нем невозможно), однако возможно подключение GUI через механизм подключаемых библиотек.

О языке

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

В языке FPTL программа – это функция, определенная над некоторыми типами данных. Тип функции записывается как T_вх => T_вых, T_вх – тип входных данных, T_вых – тип выходных данных. В языке есть набор базисных функций (приведен в главе «Встроенные функции»). Базисом для данных являются встроенные типы данных и конструкторы (описываются в главе «Типы данных»).

Встроенные функции

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

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

Операции композиции

Язык построен на основе всего трех операций композиции функций:

• Операции «точка»: F1.F2, означающей последовательное применение сначала функции F1 к исходным данным, а потом функции F2 к результату функции F1. В обычных языках программирования аналогичная конструкция выглядит так: F2(F1(d))
• Операции «звездочка»: F1*F2, означающей независимое друг от друга вычисление значений функций F1 и F2 к аргументу данной операции. Эта операция является явным источником параллелизма в программах – каждую функцию Fi можно вычислять параллельно. Заметим, что в качестве функций Fi могут быть любые другие функции. Например, этими функциями снова могут быть операторы звездочка, что дает нам возможность использования N-арного вида оператора звездочка: F1*…*Fn.
• Условного оператора: P -> F1, F2 . В случае, если P=false или омеге (специальному некорректному значению – будет описано далее), то результатом данной операции является F2(d), иначе F1(d). Данная операция является неявным источником параллелизма – мы можем спекулятивно выполнять вычисление значений функций F1 и F2 вместе с вычислением условия P. После вычисления значения условия, один из потоков F1, F2 становится ненужным и его необходимо прекратить.

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

Типы данных

В языке объявлены 4 встроенных типа данных: bool, int, real, string.

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

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

Data d
{
	d = int;
}

Пример создания типа данных-кортежа (или структуры – как кому привычнее):

Data d
{
	d = string * int * int;
}

В типе данных могут быть кортежи только одной длины.

Все типы данных в программе описываются в виде системы типовых уравнений. Каждое уравнение имеет вид:

Имя типовой переменной = описание типовой переменной;

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

Data Person
{
Person = name*age;
name = string;
age = int;
}

Для создания данных, отличных от встроенных типов (int, string и т.д.) в языке применяются конструкторы. Конструктор – это функция, создающее данное нового типа. Описание всех конструкторов имеет вид:

Данные, из которых строим наше данное => тип нашего данного : имя конструктора;

По соглашению, имена всех конструкторов начинаются с “c_”.

Длина данного, построенного на основе конструктора, равна одному.

Пример создания типа с конструкторами:

Data Nat
{
Constructors
	{
		=>Nat : c_null;
		Nat=>Nat : c_succ;
	}
	Nat = c_null ++ (Nat).c_succ;
}

Тип Nat имеет два конструктора: c_null и c_succ. Любое значение типа Nat может выглядеть как либо одиночный конструктор c_null, либо конструктор c_succ, примененный к данному типа Nat (последняя строка описания типа данных Nat). Примеры: c_null, ((c_null).c_succ).c_succ.

Создаваемые типы данных могут быть параметризованы типовыми переменными. Фактически, это аналог шаблонов из Си или generics из Java 5. Имена типовых параметров должны начинаться с апострофа. Их нужно указать в квадратных скобках после имени типа данных в его заголовке.

Пример создания параметризованного типа данных (аналог шаблонов):

Data List['x]
{
	Constructors
	{
		=>List : c_nil;
		'x*List['x] => List['x] : c_cons;
	}
	List = c_nil ++ ('x * List).c_cons;
}

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

Описание программы

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

Scheme factorial
{
    factorial = P -> F1, F2;
    P = (id*<0>).eq;
    F1 = <1>;
    F2 = (id * DEC.@).mult;
    DEC = (id*<1>).minus;
}

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

Имя функциональной переменной = описание функциональной переменной;

В описании функциональной переменной мы можем использовать три введенные ранее операции композиции, функциональные переменные, определенные в нашей схеме, а также все встроенные функции языка. В программе явно не указываются аргументы функциональных переменных. По сути, они передаются неявно. Например, аргументы функциональной переменной factorial будут переданы в функциональные переменные P, F1, F2 при их вызовах из factorial. Получить значение аргументов можно либо при помощи функции id, результатом которой являются все ее входные аргументы ( id(a)=a), либо при помощи функции I(m, n) – выбор m-ного аргумента из n входных аргументов. В программе может быть использован символ “@” – он является синонимом функциональной переменной с именем, совпадающим с именем схемы.

Процесс выполнения функциональной программы

Опишем то, как меняется аргумент функциональных переменных в процессе выполнения функциональной программы.

В factorial мы передаем одно целое число типа int. Оно же передается в P, F1, F2.

В P мы берем аргумент функциональной переменной (id возвращает целое число) и приписываем к нему справа еще одно целое число – константу ноль. Этот кортеж из двух чисел становится аргументом функции eq (проверка на равенство). Результат функции eq (булевское значение) становится результатом функциональной переменной P.

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

В F2 мы берем входной параметр (целое число) и к нему справа приписываем результат вызова функций DEC.@ (эквивалентно DEC.factorial). Результатом фукциональной переменой DEC будет целое число (см. ниже). Оно передается на вход функциональной переменной factorial. На выходе из нее мы получим также целое число (см. выше). Соответственно, результатом вызова пары DEC.@ будет одно целое число. Мы приписываем его справа к арументу функции F2 (id) и передаем полученную пару целых чисел на вход функции mult (умножение). Ее результат (целое число) будет являться результатом функциональной переменной F2.

В DEC мы берем аргумент функциональной переменной (целое число), приписываем к нему справа целочисленную константу (1) и передаем полученную пару чисел на вход функции minus (вычитание). Полученное целое число будет результатом функциональной переменной.

Вызов программы

Вызов программы, описанной в схеме, производится из секции Application программы:

Application
%factorial(6)

или

Application
Array[int] : a = 
(15 * (910 * (200 * (0 * (8 * (75 * (3 * (12 * (7 * (6 * (1 * (4 * (15 *
   (40 * c_empty).c_add
).c_add).c_add).c_add).c_add).c_add).c_add).c_add).c_add).c_add).c_add).c_add).c_add).c_add;
%BubbleSort(a)

Во втором примере показан пример объявления переменных в секции Application. Это необязательная практика. Описание переменной в секции Application имеет вид:

Тип переменной : имя переменной = значение переменной;

Полный пример программы

Functional Program factorial

Scheme factorial
{
    factorial = P -> F1, F2;
    P = (id*<0>).eq;
    F1 = <1>;
    F2 = (id * DEC.@) . mult;
    DEC = (id*<1>).minus;
}

Application
%factorial(6)

Интерпретатор и компилятор языка FPTL

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

Мы параллельно ведем два проекта:

• Кластерный интерпретатор программ FPTL
• Компилятор языка FPTL

Кластерный интерпретатор

Кластерный интерпретатор позволяет выполнять программы FPTL на любом кластере машин, на которых установлен JRE 1.5 и пакеты среды выполнения языка FPTL. Связь между машинами осуществляется посредством сокетов. Мы не используем какие-либо стандартные библиотеки для параллельных вычислений (OpenMP, MPI, и т.д.) из-за различных ограничений, накладываемых ими. Интерпретатор пользуется особенностями языка FPTL для поиска параллельно вычисляемых функциональных переменных (далее – ФП). Явной возможности указать параллельно вычисляемые ФП в языке нет.

Интерпретатор имеет следующие отличительные черты:

• Поддержка сетей любого размера (по кол-ву машин)
• Поддержка любой пропускной способности сети
• Поддержка любого кол-ва процессоров/ядер на машине (далее в статье считаем их многопроцессорными)
• Автоматический поиск ФП с достаточной вычислительной сложностью (переносимых между машинами)
• Функционал по поиску и использованию в процессе вычислений мемоизуемых ФП (ФП таких, что если f(a) уже было ранее вычислено, то при следующей попытке вычисления f(a) будет сразу использован сохраненный с предыдущего вызова результат)
• Работа на куче, а не на стеке, что упрощает выполнение рекурсивных алгоритмов
• Использование информации о загруженности как отдельной машины, так и кластера в процессе вычислений для оптимизации переноса вычисляемых ФП
• Возможность динамического добавления новых машин в кластер в процессе вычисления (они сразу же смогут быть использованы системой)
• В интерпретаторе реализована система динамического управления выполнением функций в зависимости от загруженности машин кластера (отдельные внутримашинное и кластерное управление)

В наших планах добавление в интерпретатор следующих функций:

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

Как достигается автоматический поиск переносимых ФП?

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

Вторым необходимым условием для переносимости ФП является ее достаточная сложность в результате анализа структурной сложности программы. Алгоритм оценки структурной сложности здесь приводится не будет (он еще находится в доработке), но гарантируется, что структурная сложность будет возрастать в таком порядке (F(G) – ФП F зависит от ФП G):

1. F()
2. F(G), где G()
3. F(F)
4. F(G), где G(G)

И так далее. Фактически сложность ФП вычисляется по формуле «сложность самой сложной из ФП, от которой зависит данная» + 1, если данная ФП не рекурсивная или +2, если данная ФП рекурсивная (рекурсия любого типа – как саморекурсивная – F(F), так и взаимно рекурсивная – F(G), G(F) или F1(F2), F2(F3), F3(F1) – для любого кол-ва ФП в цепочке зависимостей).

ФП считается переносимой, если ее сложность не меньше какой-то части от сложности самой сложной ФП в программе (ФП входа в программу). На данный момент эта часть равна 80% от максимальной сложности.

Как мы находим мемоизуемые ФП?

По определению, мемоизуемая функция – это такая функция, которая за время работы программы хотя бы дважды вызывалась с одним и тем же значением ее аргумента. В функциональных программах необходимость поддержки мемоизации заметно возрастает, т.к. множественные рекурсивные вызовы функции часто приводят ко многим вызовам функции с одним и тем же ее аргументом. Одним из известных примеров функций, которые очень выгодно мемоизовать, является вычисление чисел Фибоначчи по формуле fib(n) = fib(n-1) + fib(n-2), при которой у нас будет fib(1) вызовов fib(n), fib(2) вызовов fib(n-1) и т.д. Другим менее известным, но еще более показательным примером является вычисление функции Аккермана, при котором мемоизация дает возможность программам на медленных скриптовых языках обходить реализации «в лоб», написанные на Си (заметим, что если язык дает мемоизацию задаром, то мы можем считать ее как оптимизацию сгенерированного кода, и, следовательно как преимущество над другими компиляторами).

Для поиска мемоизуемых ФП интерпретатор имеет режим работы, в котором, одновременно с вычислением значения программы, ведется накопление истории вызовов всех ФП в программе. По окончании работы программы строится таблица, в которой для каждой ФП сохраняется общее кол-во ее вычислений и кол-во различных аргументов, с которыми вызывалась данная ФП. Чем больше отношение первого числа ко второму, тем выше оценка, получаемая ФП. Также на окончательное решение мемоизовать ФП или нет влияет оценка ее структурной сложности. Чем выше эта оценка, тем больше шансов у ФП быть мемоизуемой. В данный момент интерпретатор записывает предлагаемые для мемоизации названия ФП в файл настроек funcs.xml.

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

Как мы поддерживаем любое кол-во машин в кластере и процессоров на машине?

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

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

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

Массивы в языке FPTL

На данный момент у нас есть реализация встроенной в язык поддержки работы с массивами на одномашинном одноядерном интерпретаторе. Мы планируем перенести эту возможность и в сетевой интерпретатор.

Компилятор программ языка FPTL

Основной целью проекта по созданию компилятора с языка FPTL является поиск оптимизаций для интерпретатора языка. Компилятор переводит программы с языка FPTL на исходный код на языке Java. Затем он вызывает компилятор, поставляемый в комплекте JDK для окончательной обработки программы.

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

• Оптимизирующий компилятор на язык Java (строит по данным языка FPTL классы Java, делает наиболее очевидные оптимизации кода)
• Преобразователь функций, имеющих хвостовую рекурсию (tail recursive functions) из рекурсивного вида в итеративный
• Преобразователь программ FPTL, подставляющий inline все простые ФП в программе (с очень низкой вычислительной сложностью)
• Поиск переносимых и мемоизуемых ФП программы за счет анализа структурной сложности программы
• Механизм компиляции, переноса на удаленные машины и загрузки и выполнения там откомпилированных классов
• Механизм автоматического вывода типов программы
• «Клей» между компилированными и интерпретируемыми программами (генерация кода, трансформирующего данные в виде, используемом интерпретатором, в вид, используемый в данной компилированной программе) (частично реализован)
• Добавление возможности генерации многопоточного кода в компилятор (не реализовано)
• Добавление функционала по работе с массивами в компилятор (не реализовано)
• Поддержка мемо-функций в компилируемом коде (не реализовано)
• Генерация программ на языке FPTL на основе математических формул. Планируется, что форматом формул будет являться формат набора TeX.

Разработка компилятора имеет перед собой по крайней мере две цели:

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

Характеристики компилятора

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

private int ACK(int arg0, int arg1)
{
if ((arg0 == 0))
{
return arg1 + 1;
}
else
{
if ((arg1 == 0))
{
return ACK(arg0 - 1, 1);
}
else
{
return ACK(arg0 - 1, ACK(arg0, arg1 - 1));
}
}
} 

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

• Замена хвостовой рекурсии на итерацию (на данный момент заменяется только внешний, реально хвостовой вызов функции). Это дает ускорение за счет меньшей нагрузки на стек, а также возможность работы с данными большей размерности за счет не ухода в стек при рекурсивном вычислении функций.
• Вычисление константных выражений (реализовано для большинства встроенных функций). Все константные выражения в программе вычисляются на этапе компиляции. К константным относятся и арифметические тождества типа “a / a = 1, если a != 0”
• В части случаев происходит замена выражений String + String (сложение строк) на использование класса StringBuilder. Это очень сильно оптимизирует алгоритмы, составляющие результат в строке (обычно рекурсивно).
• Механизм вывода типов дает возможность генерации полностью типизированного кода для всех данных, используемых в программе (для каждой параметризации параметризуемых данных создается свой отдельный класс). Полное использование явно выведенных типов дает возможность использования максимально быстрого кода во время выполнения (например, арифметики без контроля типов аргументов).
• Все данные – классы, появляющиеся в программе в виде констант, анализируются, и, при необходимости, выносятся в static-часть класса для экономии на их постоянной инициализации во время выполнения программы. Иногда, например, при проверке условия выхода из рекурсии, такие данные без этой оптимизации могут создавать очень большое кол-во раз. В таких случаях эта оптимизация выгодна.
• Делаются следующие простые преобразования частных случаев условного оператора: “if(condition)var=true else var=false => var=condition”; “if(condition)var=false else var=true => var=!condition”; “if (condition) branch else branch => branch”. В последнем случае требуется полное совпадение обоих ветвей условного оператора.
• Если функция condition условного оператора является одной из двух булевских констант, то генерируется лишь соответствующая ветвь условного оператора.
• Функции из исходной программы, реально не используемые в коде, не компилируются. Это дает некоторую экономию на размере получаемых классов, и, соответственно, на потребление памяти средой выполнения Java.
• Для функций, вызываемых только из одной точки в программе, и имеющих часть параметров в этом вызове – константы базовых типов, эти параметры вносятся в функцию и удаляются соответствующие аргументы данной функции (реализуется только в тех функциях, где соответствующий аргумент отсутствует в левой части операторов присваивания). Это может дать возможность отработать оптимизации – обработке константных аргументов встроенных функций.
• Для функций, чей результат используется в нескольких точках программы, генереируется отдельный вызов для вычисления данных функций. После этого используется только их результат. Прямая подстановка делается только для констант и уже объявленных переменных. Примером таких функций может быть функция F в коде F.(G*H), где результат F будет использоваться на входе у G и H.

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

Тесты компилятора

Приведу несколько примеров времени выполнения программ в интерпретируемом и компилируемом режимах. Все программы из этих примеров есть в конце данной статьи (файлы java являются сгенерированными промежуточными файлами компилятора. Из них я удалил только отладочные комментарии.). При желании вы можете реализовать их на своем любимом компиляторе и сравнить результаты. Все тесты выполнялись на процессоре Intel Pentium Mobile ULV 1.1 GHz, с оперативной памятью 1280 Mb (ноутбук Dell Latitude X1).

Вычисление интеграла с заданной точностью

Худший случай для компилятора. Это пример времени выполнения программы, не переводимой в итеративную форму. В процессе генерируются переменные var9 и var18, которые пока не оптимизируются текущей версией транслятора.

Интеграл вычисляется по формуле

INT = | Trp(a, (a+b)/2) + Trp((a+b)/2,b) – Trp(a,b) | < E -> Trp(a,b),
	INT(a, (a+b)/2, E/2) + INT((a+b)/2, b, E/2)

где Trp – функция вычисления площади фигуры по методу трапеций на интервале от a до b.

Интеграл берется от функции x² на промежутке от 0 до 10 с точностью 1e-8.

Все вычисления ведутся на одном и том же компьютере.

Компилированный код: 0.12 секунд

Интерпретатор: 3.1 секунд

Тест рекурсии из комплекта тестов с сайта http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all

Компилированный код: 3.844 сек

Интерпретируемый код в данном тесте мемоизует функции ACK, FIBD, TAK. Без поддержки мемоизации время выполнения слишком велико. А вот с мемоизацией интерпретатор сразу обгоняет компилированный код: 1.828 сек!!!

Вычисление значения N-ого числа Фибоначчи на типе данных Nat

Вычисление числа 26-го числа Фибоначчи на типе чисел Nat, для которого определены функции nul (аналог нуля) и succ (следующее число). Так, например, число 2 в этом типе чисел выглядит как nul.succ.succ. Программа сначала переводит свой аргумент из обычных чисел в тип Nat, затем вычисляет указанное число Фибоначчи, используя арифметику над типом Nat, а затем переводит полученный результат из типа Nat обратно в обычные числа.

Компилируемый код: 0.25 сек

Интерпретируемый код: 3.969 сек (мемоизовалась функция F)

Разделение строки на лексемы

Не так давно популярный на rsdn тест по повторяемому в цикле один миллион раз разделению строки "123 345 asdf 23453 asdfas" на лексемы пробелами, и суммированию кол-ва получившихся лексем.

Компилируемый код: 2.968 сек

Интерпретируемый код:7.08 сек (для 100 000 итераций. Для миллиона итераций интерпретатор уходит в своп и дождаться результата не представляется возможным).

Приложение – тексты тестовых программ

Вычиcление интеграла с заданной точностью – Java

package fptl.decompiler.Generated;

import ComputingBlock.InternalForm.Data.*;
import java.util.*;
public class Test implements Runnable
{
public void run()
{
System.out.println("Compiled:" + integ(0.0, 1.0, 9.99999993922529E-9));
}

private double integ(double arg0, double arg1, double arg2)
{
double var9 = (arg0 + arg1) / (double)2;
double var18 = (arg0 + arg1) / (double)2;
if (Math.abs((((((var9 - arg0) * ((var9 * var9) + (arg0 * arg0))) / (double)2) + (((arg1 - var18) * ((arg1 * arg1) + (var18 * var18))) / (double)2)) - (((arg1 - arg0) * ((arg1 * arg1) + (arg0 * arg0))) / (double)2))) < arg2)
{
return ((arg1 - arg0) * ((arg1 * arg1) + (arg0 * arg0))) / (double)2;
}
else
{
return integ(arg0, (arg0 + arg1) / (double)2, arg2 / (double)2) + integ((arg0 + arg1) / (double)2, arg1, arg2 / (double)2);
}
}

}

Вычиcление интеграла с заданной точностью – FPTL

Functional Program integ
Scheme integ
{
@= ((((I(1,3)*MID).TRP * (MID*I(2,3)).TRP).plus * (I(1,3)*I(2,3)).TRP).minus.abs * I(3,3)).lt ->
	(I(1,3)*I(2,3)).TRP,
	(((I(1,3)*MID*(I(3,3)*<2>).div).@ * (MID*I(2,3)*(I(3,3)*<2>).div).@).plus);

MID = ((I(1,3)*I(2,3)).plus*<2>).div;
TRP = (((I(2,2)*I(1,2)).minus*(I(2,2).F*I(1,2).F).plus).mult*<2>).div;
F = (id*id).mult;
}
Application
%integ(0.0, 10.0, 0.00000001)

Тест рекурсии - Java

package fptl.decompiler.Generated;

import ComputingBlock.InternalForm.Data.*;
import java.util.*;
public class Test implements Runnable
{
public void run()
{
System.out.println("Compiled:" + gentoo());
}

private ParamClass0 gentoo()
{
return new ParamClass0(ACK(3, 11), FIBD(38.0), TAK(30, 20, 10), FIB(3), TAKD(3.0, 2.0, 1.0));
}

private int ACK(int arg0, int arg1)
{
while (!(arg0 == 0))
{
if (arg1 == 0)
{
int argTemp0 = arg0 - 1;
int argTemp1 = 1;
arg0 = argTemp0;
arg1 = argTemp1;
}
else
{
int argTemp0 = arg0 - 1;
int argTemp1 = ACK(arg0, arg1 - 1);
arg0 = argTemp0;
arg1 = argTemp1;
}
}
return arg1 + 1;
}

private double FIBD(double arg0)
{
return FIBD_TAILREC(arg0, 1.0);
}
private double FIBD_TAILREC(double arg0, double arg1)
{
while (true)
{
if (arg0 < 2.0) break;
double argTemp0 = arg0 - 2.0;
double argTemp1 = arg1 + FIBD(arg0 - 1.0);
arg0 = argTemp0;
arg1 = argTemp1;
}
return arg1;
}

private int TAK(int arg0, int arg1, int arg2)
{
while (!(arg1 >= arg0))
{
int argTemp0 = TAK(arg0 - 1, arg1, arg2);
int argTemp1 = TAK(arg1 - 1, arg2, arg0);
int argTemp2 = TAK(arg2 - 1, arg0, arg1);
arg0 = argTemp0;
arg1 = argTemp1;
arg2 = argTemp2;
}
return arg2;
}

private int FIB(int arg0)
{
return FIB_TAILREC(arg0, 1);
}
private int FIB_TAILREC(int arg0, int arg1)
{
while (true)
{
if (arg0 < 2) break;
int argTemp0 = arg0 - 2;
int argTemp1 = arg1 + FIB(arg0 - 1);
arg0 = argTemp0;
arg1 = argTemp1;
}
return arg1;
}

private double TAKD(double arg0, double arg1, double arg2)
{
while (!(arg1 >= arg0))
{
double argTemp0 = TAKD(arg0 - 1.0, arg1, arg2);
double argTemp1 = TAKD(arg1 - 1.0, arg2, arg0);
double argTemp2 = TAKD(arg2 - 1.0, arg0, arg1);
arg0 = argTemp0;
arg1 = argTemp1;
arg2 = argTemp2;
}
return arg2;
}

}

class ParamClass0
{
	public int field0;
	public double field1;
	public int field2;
	public int field3;
	public double field4;

	public ParamClass0(int lparam0, double lparam1, int lparam2, int lparam3, double lparam4)
	{
		field0 = lparam0;
		field1 = lparam1;
		field2 = lparam2;
		field3 = lparam3;
		field4 = lparam4;
	}

	public String toString()
	{
		return "(" + field0 + " * " + field1 + " * " + field2 + " * " + field3 + " * " + field4 + ")";
	}
}

Тест рекурсии – FPTL

Functional Program gentoo

Scheme gentoo
{
@= ((<3>*<11>).ACK *
   <38.0>.FIBD *
   (<30>*<20>*<10>).TAK *
   <3>.FIB *
   (<3.0>*<2.0>*<1.0>).TAKD);

ACK = (I(1,2)*<0>).eq -> (I(2,2)*<1>).plus,
	(
		(I(2,2)*<0>).eq -> (I(1,2).DEC*<1>).ACK,
		(
			(I(1,2).DEC * (I(1,2)*I(2,2).DEC).ACK).ACK
		)
	);

DEC = (id*<1>).minus;
DECD = (id*<1.0>).minus;

FIB = (id*<2>).lt -> <1>,
	(
		((id*<2>).minus.FIB * id.DEC.FIB).plus
	);
FIBD = (id*<2.0>).lt -> <1.0>,
	(
		((id*<2.0>).minus.FIBD * id.DECD.FIBD).plus
	);

TAK = (I(2,3)*I(1,3)).ge -> I(3,3),
	(
		((I(1,3).DEC*I(2,3)*I(3,3)).TAK *
		(I(2,3).DEC*I(3,3)*I(1,3)).TAK *
		(I(3,3).DEC*I(1,3)*I(2,3)).TAK).TAK
	);

TAKD = (I(2,3)*I(1,3)).ge -> I(3,3),
	(
		((I(1,3).DECD*I(2,3)*I(3,3)).TAKD *
		(I(2,3).DECD*I(3,3)*I(1,3)).TAKD *
		(I(3,3).DECD*I(1,3)*I(2,3)).TAKD).TAKD
	);
}

Application
%gentoo(1)

Вычисление значения N-ого числа Фибоначчи на типе данных Nat – Java

package fptl.decompiler.Generated;

import ComputingBlock.InternalForm.Data.*;
import java.util.*;
public class Test implements Runnable
{
public void run()
{
System.out.println("Compiled:" + fib());
}

private int fib()
{
return COUNT(F(CNV(23)));
}

private Nat CNV(int arg0)
{
return CNV_TAILREC(arg0, consBd2);
}
private Nat CNV_TAILREC(int arg0, Nat arg1)
{
while (true)
{
if (arg0 == 0) break;
int argTemp0 = arg0 - 1;
Nat argTemp1 = Nat.c_succ(arg1);
arg0 = argTemp0;
arg1 = argTemp1;
}
return arg1;
}

private Nat F(Nat arg0)
{
return F_TAILREC(arg0, consBd5);
}
private Nat F_TAILREC(Nat arg0, Nat arg1)
{
while (true)
{
boolean var18;
if (arg0 == null || consBd4 == null)
var18 = false;
else
var18 = LE(arg0, consBd4);
if (var18) break;
Nat argTemp0 = MINUS(arg0, consBd5);
Nat argTemp1 = PLUS(arg1, F(MINUS(arg0, consBd4)));
arg0 = argTemp0;
arg1 = argTemp1;
}
return arg1;
}

private int COUNT(Nat arg0)
{
return COUNT_TAILREC(arg0, 0);
}
private int COUNT_TAILREC(Nat arg0, int arg1)
{
while (true)
{
if (arg0.hasConstructor(0)) break;
Nat argTemp0 = arg0.m_fc_succ0;
int argTemp1 = arg1 + 1;
arg0 = argTemp0;
arg1 = argTemp1;
}
return arg1;
}

private boolean LE(Nat arg0, Nat arg1)
{
return LT(arg0, arg1) | EQ(arg0, arg1);
}

private Nat MINUS(Nat arg0, Nat arg1)
{
while (!(arg1.hasConstructor(0)))
{
Nat argTemp0 = arg0.m_fc_succ0;
Nat argTemp1 = arg1.m_fc_succ0;
arg0 = argTemp0;
arg1 = argTemp1;
}
return arg0;
}

private Nat PLUS(Nat arg0, Nat arg1)
{
while (!(arg1.hasConstructor(0)))
{
Nat argTemp0 = Nat.c_succ(arg0);
Nat argTemp1 = arg1.m_fc_succ0;
arg0 = argTemp0;
arg1 = argTemp1;
}
return arg0;
}

private boolean LT(Nat arg0, Nat arg1)
{
if (arg0.hasConstructor(0) && arg1.hasConstructor(1) )
{
return true;
}
else
{
boolean var40;
if (arg0.m_fc_succ0 == null || arg1.m_fc_succ0 == null)
var40 = false;
else
var40 = LT(arg0.m_fc_succ0, arg1.m_fc_succ0);
return var40;
}
}

private boolean EQ(Nat arg0, Nat arg1)
{
if (arg0.hasConstructor(0) && arg1.hasConstructor(0) )
{
return true;
}
else
{
boolean var43;
if (arg0.m_fc_succ0 == null || arg1.m_fc_succ0 == null)
var43 = false;
else
var43 = EQ(arg0.m_fc_succ0, arg1.m_fc_succ0);
return var43;
}
}

private static final Nat consBd2;
private static final Nat consBd4;
private static final Nat consBd5;
static
{
consBd2 = Nat.c_null();
consBd4 = Nat.c_succ(Nat.c_succ(Nat.c_null()));
consBd5 = Nat.c_succ(Nat.c_null());
}

}

class Nat
{
	private int m_consName;
	public Nat m_fc_succ0;
	private Nat()
	{
	}
	public static Nat c_null()
	{
		Nat var = new Nat();
		var.m_consName = 0;
		return var;
	}
	public static Nat c_succ(final Nat fc_succ0)
	{
		Nat var = new Nat();
		var.m_fc_succ0 = fc_succ0;
		var.m_consName = 1;
		return var;
	}
	public boolean hasConstructor(int consName)
	{
		return m_consName == consName;
	}
	public String toString()
	{
		Map<Nat, String> m_res = new HashMap<Nat, String>();
		Stack<Nat> m_stack = new Stack<Nat>();
		m_stack.push(this);
		while (!m_stack.empty())
		{
			Nat cur = m_stack.peek();
			if (cur.m_consName == 0)
			{
				m_stack.pop();
				m_res.put(cur, "(" + ").c_null");
			}
			if (cur.m_consName == 1)
			{
				String res = m_res.get(cur.m_fc_succ0);
				if (res == null)
					m_stack.push(cur.m_fc_succ0);
				else
				{
					m_stack.pop();
					m_res.put(cur, "(" + res + ").c_succ");
				}
			}
			if (m_stack.empty())
				return m_res.get(cur);
		}
		return "";
	}
}

Вычисление значения N-ого числа Фибоначчи на типе данных Nat – FPTL

Functional Program fib

Data Nat
{
	Constructors
	{
		=>Nat : c_null;
		Nat=>Nat : c_succ;
	}
	Nat = c_null ++ (Nat).c_succ;
}

Scheme fib
{
    @ = CNV.F.COUNT;

    F = 
        (id*<((c_null).c_succ).c_succ>).LE -> 
            <(c_null).c_succ>, 
            (
                (
                    (id*<(c_null).c_succ>).MINUS.F * 
                    (id*<((c_null).c_succ).c_succ>).MINUS.F
                ).PLUS
            );

    ///////////////////////////////////////////////////////////////////////////

    PLUS = 
        I(2,2).~c_null -> 
            I(1,2), 
            (
                (I(1,2).c_succ * I(2,2).~c_succ).PLUS
            );

    MINUS =
        I(2,2).~c_null -> 
            I(1,2), 
            (
                (I(1,2).~c_succ * I(2,2).~c_succ).MINUS
            );

    LT = 
        (I(1,2).~c_null * I(2,2).~c_succ) -> <true>,
        (
            ((I(1,2).~c_succ * I(2,2).~c_succ).LT) -> <true>, <false>
        );

    GT = 
        (I(1,2).~c_succ * I(2,2).~c_null) -> <true>,
        (
            ((I(1,2).~c_succ * I(2,2).~c_succ).GT) -> <true>, <false>
        );
    EQ = 
        (I(1,2).~c_null * I(2,2).~c_null) -> <true>,
        (
            ((I(1,2).~c_succ * I(2,2).~c_succ).EQ) -> <true>, <false>
        );

    GE = (GT * EQ) . or;
    LE = (LT * EQ) . or;
	

    CNV = (id*<0>).eq -> <c_null>, (((id*<1>).minus.CNV).c_succ);
    COUNT = ~c_null -> <0>, (~c_succ.(COUNT * <1>).plus);
}

Application
%fib(26)

Разделение строки на лексемы – Java

package fptl.decompiler.Generated;

import ComputingBlock.InternalForm.Data.*;
import java.util.*;
public class Test implements Runnable
{
public void run()
{
System.out.println("Compiled:" + split());
}

private int split()
{
return F("123 345 asdf 23453 asdfas", " ", 1000000, 0);
}

private int F(String arg0, String arg1, int arg2, int arg3)
{
while (!(arg2 == 0))
{
int argTemp2 = arg2 - 1;
int argTemp3 = S0(arg0, arg1) + arg3;
arg2 = argTemp2;
arg3 = argTemp3;
}
return arg3;
}

private int S0(String arg0, String arg1)
{
return S1(arg0, arg1, 0);
}

private int S1(String arg0, String arg1, int arg2)
{
while (true)
{
String var8;
if (arg0.indexOf(arg1) == -1)
{
var8 = "";
}
else
{
int var14 = arg0.length() - arg0.indexOf(arg1);
int var17 = arg0.indexOf(arg1);
var8 = arg0.substring((var17 + 1), (var17 + 1) + (var14 - 1));
}
if (var8.compareTo("") == 0) break;
String var22;
if (arg0.indexOf(arg1) == -1)
{
var22 = "";
}
else
{
int var28 = arg0.length() - arg0.indexOf(arg1);
int var31 = arg0.indexOf(arg1);
var22 = arg0.substring((var31 + 1), (var31 + 1) + (var28 - 1));
}
String argTemp0 = var22;
int argTemp2 = arg2 + 1;
arg0 = argTemp0;
arg2 = argTemp2;
}
return arg2 + 1;
}

}

Разделение строки на лексемы – FPTL

Functional Program split

Scheme split
{
//string*string*int => int
    @ = (id*<0>).F;
//string*string*int*int => int
    F = (I(3,4)*<0>).eq -> I(4,4), ((I(1,4)*I(2,4)*I(3,4).DEC*((I(1,4)*I(2,4)).S0*I(4,4)).plus).F);	

//string*string => int
    S0 = (id*<0>).S1;
//string*string*int => int
    S1 = ((I(1,3)*I(2,3)).SP*<"">).eq -> I(3,3).INC, (((I(1,3)*I(2,3)).SP*I(2,3)* I(3,3).INC ).S1);
//string*string => string
    SP = (find*<-1>).eq -> <"">, (( (I(1,2).len*find).minus.DEC * find.INC * I(1,2) ).extr);	

    INC = (id*<1>).plus;
    DEC = (id*<1>).minus;
}

Application
%split("123 345 asdf 23453 asdfas", " ", 1000000)