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

ОбщееО языкеВстроенные функцииОперации композицииТипы данныхОписание программыПроцесс выполнения функциональной программыВызов программыПолный пример программыИнтерпретатор и компилятор языка FPTLКластерный интерпретаторКак достигается автоматический поиск переносимых ФП?Как мы находим мемоизуемые ФП?Как мы поддерживаем любое кол-во машин в кластере и процессоров на машине?Массивы в языке FPTLКомпилятор программ языка FPTLХарактеристики компилятораТесты компилятораПриложение – тексты тестовых программВычиcление интеграла с заданной точностью – JavaВычиcление интеграла с заданной точностью – FPTLТест рекурсии - JavaТест рекурсии – FPTLВычисление значения N-ого числа Фибоначчи на типе данных Nat – JavaВычисление значения N-ого числа Фибоначчи на типе данных Nat – FPTLРазделение строки на лексемы – JavaРазделение строки на лексемы – FPTLОбщееФункциональный язык программирования FPTL (Functional Programming Typified Language)был разработан профессорами МЭИ Кутеповым В.П.

и Фальком В.Н. В данный моментведется разработка нескольких проектов по данному языку: транслятора с FPTL на Java,среды выполнения для кластеров и многоядерных систем, среды разработки программ.Основное назначение данного языка (по мнению его авторов) – это выполнениевысокопроизводительных вычислений. В данный момент язык не представляет каких-либосредств работы с пользовательским интерфейсом (создание оконнных приложений на немневозможно), однако возможно подключение GUI через механизм подключаемых библиотек.О языкеСейчас будет приведено неполное описание языка.

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

Отмечу, что для строковыхфункций первый символ в строке имеет индекс, равный нулю.ФункцияДопустимые типыданныхОписаниеСм. след. таблицуplusx+yminusx–ymultx*ydivx/yremостаток от целочисленного деленияint*int => introundцелая часть xreal => intabsмодуль xInt=>int; real=>real;eqx=yСм. след. таблицуnex != yltx<ygtx>ylex <= ygex >= ycatконкатенация строкstring*string => stringlenдлина строкиstring => intinsвставка подстроки после указанного символа висходную строкуstring*int*string => stringextrизвлечение подстроки указанной длины,начинающейся с указанной позицииint*int*string => stringfindпоиск подстрокиstring*string => intandx&yСм.

след. таблицуorx|ynot!xbool => boolI(m,n)выбор m-го элемента из кортежа длиной n‘t1*’t2*…*’tm*…*’tn =>‘tm<C>функция-константа: для любого x <C>(x) = C, где C– некоторая константа любого типа‘t => ‘tC, где ‘tC – типконстанты Cidтождественная функция: для любого x id(x) = x‘t => ‘tФункцииДопустимые типы данныхPlus, minus, mult,int*int => int; real*real => real; real*int => real; int*real => realdivEq, ne, lt, gt, le,geint*int => bool; int*real => bool; real*int => bool; real*real =>bool; string*string => bool; bool*bool => boolAnd, orbool*bool => boolНа данный момент в язык введены функции для обработки массивов, но пока их поддержкавведена не всюду, они будут носить только экспериментальный характер.Операции композицииЯзык построен на основе всего трех операций композиции функций:Операции «точка»: 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)илиApplicationArray[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.