Общее О языке

Встроенные функции Операции композиции Типы данных Описание программы

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

Интерпретатор и компилятор языка 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. Отмечу, что для строковых функций первый символ в строке имеет индекс, равный нулю.

	Функция	Описание
	plus	x + y
	minus	x – y
	mult	x * y
	div	x / y
	rem	остаток от целочисленного деления
	round	целая часть x
	abs	модуль x
	eq	x = y
	ne	x != y
	lt	x < y
	gt	x > y
	le	x <= y
	ge	x >= y
	cat	конкатенация строк
	len	длина строки
	ins	вставка подстроки после указанного символа в
		исходную строку
	extr	извлечение подстроки указанной длины,
		начинающейся с указанной позиции
	find	поиск подстроки
	and	x & y
	or	x | y
	not	!x
	I(m,n)	выбор m-го элемента из кортежа длиной n
	<C>	функция-константа: для любого x <C>(x) = C, где C
		– некоторая константа любого типа
	id	тождественная функция: для любого x id(x) = x

Допустимые типы

данных

См. след. таблицу

int*int => int real => int

Int=>int; real=>real;

См. след. таблицу

string*string => string string => int

string*int*string => string

int*int*string => string

string*string => int

См. след. таблицу

bool => bool ‘t1*’t2*…*’tm*…*’tn =>‘tm

‘t => ‘tC, где ‘tC – тип

константы C

‘t => ‘t

Функции	Допустимые типы данных
Plus, minus, mult,	int*int => int; real*real => real; real*int => real; int*real => real
div

Eq, ne, lt, gt, le,	int*int => bool; int*real => bool; real*int => bool; real*real =>
ge	bool; string*string => bool; bool*bool => bool
And, or	bool*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]

{