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

В свете ожидаемого выходана рынок действительно многоядерных процессоров (с кол-вом ядер от 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 elsevar=true => var=!condition”; “if (condition) branch else branch => branch”. В последнемслучае требуется полное совпадение обоих ветвей условного оператора.Если функция condition условного оператора является одной из двух булевскихконстант, то генерируется лишь соответствующая ветвь условного оператора.Функции из исходной программы, реально не используемые в коде, некомпилируются.

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

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

Все программы из этих примеров есть в конце данной статьи(файлы java являются сгенерированными промежуточными файлами компилятора. Из них яудалил только отладочные комментарии.). При желании вы можете реализовать их на своемлюбимом компиляторе и сравнить результаты. Все тесты выполнялись на процессоре IntelPentium 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.Интеграл берется от функции x2 на промежутке от 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ление интеграла с заданной точностью – Javapackage 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ление интеграла с заданной точностью – FPTLFunctional Program integScheme 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)Тест рекурсии - Javapackage 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,{while (!(arg1 >= arg0)){int argTemp0 = TAK(arg0 int argTemp1 = TAK(arg1 int argTemp2 = TAK(arg2 arg0 = argTemp0;arg1 = argTemp1;arg2 = argTemp2;}return arg2;}int arg1, int arg2)1, arg1, arg2);1, arg2, arg0);1, arg0, arg1);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{publicpublicpublicpublicpublicint field0;double field1;int field2;int field3;double field4;public ParamClass0(int lparam0, double lparam1, int lparam2, intlparam3, double lparam4){field0 = lparam0;field1 = lparam1;field2 = lparam2;field3 = lparam3;field4 = lparam4;}public String toString(){return "(" + field0 + " * " + field1 + " * " + field2 + " * " +field3 + " * " + field4 + ")";}}Тест рекурсии – FPTLFunctional Program gentooScheme 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 – Javapackage 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;elsevar18 = 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;elsevar40 = 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;elsevar43 = EQ(arg0.m_fc_succ0, arg1.m_fc_succ0);return var43;}}privateprivateprivatestatic{consBd2consBd4consBd5}static final Nat consBd2;static final Nat consBd4;static final Nat consBd5;= Nat.c_null();= Nat.c_succ(Nat.c_succ(Nat.c_null()));= 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 – FPTLFunctional Program fibData 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) .