STRING PROCESSING LIBRARY FOR PIFAGOR, A FUNCTIONAL DATAFLOW CONCURRENT PROGRAMMING LANGUAGE

БИБЛИОТЕКА ОБРАБОТКИ СТРОК ДЛЯ ЯЗЫКА ФУНКЦИОНАЛЬНО-ПОТОКОВОГО ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ ПИФАГОР

Научная статья

Удалова Ю.В.*

Сибирский Федеральный Университет, Красноярск, Россия

* Корреспондирующий автор (judalova[at]sfu-kras.ru)

Аннотация

Язык функционально-потокового параллельного программирования Пифагор является оригинальным языком программирования, ориентированным на поддержку концепции неограниченного параллелизма, потенциально позволяющим создавать максимально параллельные архитектурно-независимые программы, не связанные с ресурсными и архитектурными ограничениями.

В настоящее время разрабатываются библиотеки функций языка, предлагаются и совершенствуются инструментальные средства [5], [11]. Статья посвящена реализации библиотеки обработки строк, предоставляющей функциональные вызовы для часто встречающихся вычислительных операций обработки текста.

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

Ключевые слова: функциональное программирование, параллельное программирование, строки символов, библиотека функций.

STRING PROCESSING LIBRARY FOR PIFAGOR, A FUNCTIONAL DATAFLOW CONCURRENT PROGRAMMING LANGUAGE

Research article

Udalova Yu.V.*

Siberian Federal University, Krasnoyarsk, Russia

* Corresponding author (judalova[at]sfu-kras.ru)

Abstract

PIFAGOR is an original programming language that supports the concept of unlimited concurrency, potentially allowing for creating the most concurrent architecturally independent software that is not associated with the resource and architectural constraints.

The development of language function libraries as well as the improvement of the tools is taking place at the current moment. [5], [11]. The article explores the implementation of a string processing library that provides functional calls for frequently encountered text processing computing operations.

The first version of the string processing library has been developed, so attention is focused on creating a wide range of functional calls that allow for the automation of the solution of frequently encountered text processing subtasks. The algorithms of the library functions are adapted to achieve maximum concurrency within the framework of the functional dataflow concurrent computing model, which in the future will allow for the development of original and efficient algorithms to process large text data.

Keywords: functional programming, concurrent programming, character strings, function library.

Введение

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

Функции библиотеки обработки строк языка Пифагор

При создании библиотеки обработки строк для языка Пифагор в качестве примеров по функциональности послужили библиотека string.h языка С, содержащая базовые операции обработки строк, и методы класса QString кроссплатформенной среды разработки Qt, предоставляющие обширный инструментарий для локализации и изменения участков текста в строке.

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

Специальная функция для определения длины строки в библиотеке отсутствует, поскольку является базовой функцией языка Пифагор и записывается в коде как ‘|’. Индексация символов в строке начинается с единицы, выделение и удаление символа из строки по индексу являются базовыми операциями языка, но для замены символа в строке, включения символа в строку и других действий со строкой потребуется разработать свой код или вызвать функцию из представленной библиотеки.

 

Таблица 1 – Примеры функций библиотеки обработки строк

Имя функции	Назначение или результат работы	Пример входных данных	Пример вычисленного результата
strcat	Объединение двух строк в одну	("Hello"," world")	("Hello world")
strlistcat	Объединение списка строк в одну строку	("1","2","3","45")	("12345")
transposition	Объединение двух строк в одну чередованием символов	("Hello","world")	("Hweolrllod")
inversion	Получение строки в обратной записи	("MPI")	("IPM")
indchr	Индекс первого вхождения символа в строке или 0	("UUTАT",'T')	3
indchrend	Индекс первого с конца вхождения символа в строке или 0	("UUTАT",'T')	5
indschr	Список индексов вхождений символа в строке	("UUTАT",'T')	(3, 5)
amountchr	Количество вхождений символа в строке	("ToT kTo",'T')	3
selectthischrs	Получение строки, состоящей из символов, стоящих на указанных индексах	("1234567", (2, 5, 7) )	("257")
selectmidchrs	Получение строки, состоящей из символов, расположенных между парой индексов	("RT4TS",2,4)	("T4T")
replacelistchrs	Строка, полученная заменой в строке1 каждого вхождения символа из строки2 на соответствующий ему по индексу символ из строки3	("QWERTY", "QWEYP", "12345")	("123RT4")
strcmp	Сравнение пары строк, результатом является булево значение	("QWE","QTE")	false
strcmpind	Сравнение пары строк, результатом является список индексов совпадающих символов	("QWE", "QTE")	(1, 3)
indsstr	Список индексов вхождений строки2 в строке1	("+7-809-123-123", "123")	(8, 12)
insertstrlist	Вставить в строку строки из списка с позиций, указанных в списке индексов	("1234567", ("M", "PI"), (3,6))	("12M345PI67")
replacestr	Заменить в строке все вхождения строки1 на строку2	("123434", "34", "M")	("12MM")
string.int	Запись целой части числа в строку	-543.12	("-543")
string.intlist	Запись целых частей чисел из списка в строку через пробел	(-96, -1.75, 3005, 17.08)	("-96 -1 3005 17")
string.getfloat	Выделение вещественного числа из строки	("max=815.21, min=6")	815.21
string.getfloatlist	Выделение вещественных чисел из строки	("max=815.21, min=6,9")	(815.21, 6.9)

 

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

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

Пример 1. Определить является ли строка палиндромом.

Программный код на языке Пифагор.

func << funcdef Param // Param – аргумент функции, строка

{ (Param, Param:inversion):strcmp >> return ; }

Используются две функции библиотеки: inversion - обратная запись исходной строки Param и strcmp – сравнение пары строк, здесь аргументами strcmp являются исходная строка Param и её обратная запись Param:inversion.

Пример 2. Определить являются ли первое и последнее слово строки палиндромами. Считать, что слова в строке разделяются пробелами, и строка не содержит пробелы перед первым словом и после последнего слова.

Программный код на языке Пифагор. func << funcdef Param // Param – аргумент функции, строка {(Param,' '):indchr >> ind1 ; //ind1 - индекс первого пробела (Param,' '):indchrend >> ind2 ; //ind2 - индекс последнего пробела //выделение первого слова в идентификатор firstWord (Param,(ind1,1):-):selectfirstchrs >> firstWord ; //выделение последнего слова в идентификатор lastWord (Param,(ind2,1):+, Param:|):selectmidchrs >> lastWord ; //cond1 – условие равенства первого слова его обратной записи (firstWord,firstWord:inversion):strcmp >> cond1 ; //cond2 – условие равенства последнего слова его обратной записи (lastWord,lastWord:inversion):strcmp >> cond2 ; //Ниже операция * это логическое И над cond1 и cond2 (cond1, cond2):* >> return ; }

Примеры входных данных и результатов вычисления функции: "123 + 789" -> false, "323 + 789" -> false, "323 + 989" -> true.

Адаптация алгоритмов функций библиотеки для достижения максимального параллелизма в рамках модели функционально-потоковых параллельных вычислений

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

Рис. 1 – Обобщенный информационно-управляющий граф последовательной рекурсии обработки строки

 

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

Рис. 2 – схема функций обработки строк с параллельными списками или параллельной рекурсией (a) и пример вычислений функции indschr (б)

 

Например, функция indschr, вычисляющая список индексов вхождений символа в строке, записанная в указанном стиле (см. рисунок 2), базируется на базовых командах языка и обработке параллельного списка, обладает указанным ниже программным кодом, в котором dup, #, ? это дупликация, транспонирование и определение индексов истинных булевых величин в списке.

indschr << funcdef Param // Param = (строка, символ)

{ (Param:1,(Param:2,Param:1:|):dup):#:[]:=:(.):? >> return ; }

Реализация функции indschr с помощью последовательной рекурсии (см. рисунок 1) не только увеличивает объем программного кода, но и ограничивает потенциальные возможности распараллеливания. Подобная реализация функции indschr на языке Пифагор будет выглядеть следующим образом.

indschr << funcdef Param

{ Param:1 >> str; Param:2 >> c; str:| >> len ;

({(1,(.))}, {(Param:3, Param:4)}):[(Param:|,2):(=,>):?]:. >> ind ;

( { ( { (ind:2:[], ind:1) }, { ind:2 }

 ):[(str:1,c):(=,!=):?]:.

 },

 { ( { (str:-1,c,(ind:1,1):+, (ind:2:[], ind:1)):string.indschr },

 { (str:-1,c,(ind:1,1):+, ind:2):string.indschr }

 ):[(str:1,c):(=,!=):?]:.

 }

):[(len,1):(=,>):?]:.>> return ; }

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

Заключение

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

Библиотеки для языка Пифагор [8] проектируются как статические библиотеки, предоставляющие файлы с исходным кодом. Все функциональные вызовы включаются в открытый репозиторий языка, таким образом, функции можно не только вызывать на исполнение, но и использовать их программный код или его части в программах пользователя.

Финансирование Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант № 17-07-00288 «Архитектурно-независимая разработка параллельных программ на основе функционально-потоковой парадигмы», 2017-2019 гг.	Funding This work was supported by the Russian Foundation for basic research, grant № 17-07-00288 "Architecture-independent development of parallel programs based on the functional-streaming paradigm", 2017-2019.
Конфликт интересов Не указан.	Conflict of Interest None declared.

Список литературы / References

1. Legalov A.I. A toolkit for the development of data-driven functional parallel programmes / A.I. Legalov et al. // Communications in Computer and Information Science. – 2018. – V. 910. – P. 16-30. DOI: 10.1007/978-3-319-99673-8_2
2. Легалов А.И. Инструментальная поддержка создания и трансформации функционально-потоковых параллельных программ / А. И. Легалов и др. // Труды Института системного программирования РАН. – 2017. – Т. 29 – № 5. – С. 165-184. DOI: 10.15514/ISPRAS-2017-29(5)-10
3. Легалов А. И. Особенности разработки и преобразования функционально-потоковых параллельных программ / А. И. Легалов, М. С. Ушакова // Суперкомпьютерные дни в России: тр. междунар. конф. М. – 2018. – С. 999–1000.
4. Функционально-потоковое параллельное программирование. Среда разработки, статьи, примеры программ. [Электронный ресурс] URL: http://www.softcraft.ru/fppp/ (дата обращения: 26.11.2020).
5. Легалов А.И. Добавление статической типизации в язык функционально-потокового параллельного программирования / А.И. Легалов, И.А. Легалов, И.В. Матковский // Электронные библиотеки. – 2020. – Т. 23. – № 4. – С. 788-807. DOI: 10.26907/1562-5419-2020-23-4-788-807
6. Легалов А.И. Динамически изменяющийся параллелизм с асинхронно-последовательными потоками данных / А.И. Легалов, И.В. Матковский, М.С. Ушакова, Д.С. Романова // Моделирование и анализ информационных систем. – 2020. – Т. 27. – № 2. – С. 164-179. DOI: 10.18255/1818-1015-2020-2-164-179
7. Легалов А.И. Особенности семантики статически типизированного языка функционально-потокового параллельного программирования / А.И. Легалов, И.А. Легалов, И.В. Матковский // Научный сервис в сети Интернет. – 2019. – № 21. – С. 489-500. DOI:10.20948/abrau-2019-08
8. Удалова Ю.В. Библиотека математических функций для языка функционально-потокового параллельного программирования Пифагор / Ю. В. Удалова // Вестник Бурятского государственного университета. Математика, информатика. – 2019. – № 4. – С. 57–64. DOI: 10.18101/2304-5728-2019-4-57-64
9. Ушакова М. С. Верификация программ со взаимной рекурсией на языке Пифагор / М. С. Ушакова, А. И. Легалов // Моделирование и анализ информационных систем. – 2018. – Т. 25. – № 4 (76). – С. 358–381. DOI: 10.18255/1818-1015-2018-4-358-381
10. Васильев В. С. Оптимизация инварианта цикла в языке Пифагор / В.С. Васильев, А.И. Легалов // Моделирование и анализ информационных систем. – 2018. – Т. 25 – № 4 (76) – С. 347–357. DOI: 10.18255/1818-1015-2018-4-347-357
11. Удалова Ю. В. Верификация функционально-потоковых параллельных программ методом индуктивных утверждений / Ю. В. Удалова, А.И. Легалов // Доклады Академии наук высшей школы Российской Федерации. – 2014. – № 2–3 (23–24). – С. 125–132.

Список литературы на английском языке / References in English

1. Legalov A.I. A toolkit for the development of data-driven functional parallel programmes / A.I. Legalov et al. // Communications in Computer and Information Science. – 2018. – V. 910. – P. 16-30. DOI: 10.1007/978-3-319-99673-8_2
2. Legalov A.I. Instrumental'naja podderzhka sozdanija i transformacii funkcional'no-potokovyh parallel'nyh program [Tool support for the creation and transformation of data-driven functional parallel programs] / A.I. Legalov and others // Trudy Instituta sistemnogo programmirovanija RAN [Proceedings Of the Institute of system programming of the Russian Academy of Sciences] – 2017. – V. 29 – № 5. – P. 165-184. DOI: 10.15514/ISPRAS-2017-29(5)-10 [in Russian]
3. Legalov A.I. Osobennosti razrabotki i preobrazovanija funkcional'no-potokovyh parallel'nyh program [Features of the development and transformation of data-driven functional parallel programs] / A.I. Legalov, M. S. Ushakova // Superkomp'juternye dni v Rossii: trudy mezhdunarodnoj konferencii [Supercomputer days in Russia: proceedings of the international conference] – 2018. – P. 999–1000. [in Russian]
4. Funkcional'no-potokovoe parallel'noe programmirovanie. Sreda razrabotki, stat'i, primery programm. [Data-driven functional parallel programming. Development environment, articles and sample programs.] [Electronic resource] URL: http://www.softcraft.ru/fppp/ (accessed: 26.11.2020). [in Russian]
5. Legalov A.I. Dobavlenie staticheskoj tipizacii v jazyk funkcional'no-potokovogo parallel'nogo programmirovanija [Adding static typing in the language of data-driven functional parallel programming] / A.I. Legalov, I.A. Legalov, I.V. Matkovskij // Jelektronnye biblioteki [Electronic library] – 2020. – V. 23. – № 4. – P. 788-807. DOI: 10.26907/1562-5419-2020-23-4-788-807 [in Russian]
6. Legalov A.I. Dinamicheski izmenjajushhijsja parallelizm s asinhronno-posledovatel'nymi potokami dannyh [Dynamically changing parallelism with asynchronous-sequential data flows] / A.I. Legalov, I.V. Matkovskij, M. S. Ushakova, D.S. Romanova // Modelirovanie i analiz informacionnyh system [Modeling and analysis of information systems] – 2020. – V. 27. – № 2. – P. 164-179. DOI: 10.18255/1818-1015-2020-2-164-179 [in Russian]
7. Legalov A.I. Osobennosti semantiki staticheski tipizirovannogo jazyka funkcional'no-potokovogo parallel'nogo programmirovanija [Features of the semantics of a statically typed functional-stream parallel programming language] / A.I. Legalov, I.A. Legalov, I.V. Matkovskij // Nauchnyj servis v seti Internet [Scientific service on the Internet] – 2019. – № 21. – P. 489-500. DOI:10.20948/abrau-2019-08 [in Russian]
8. Udalova Ju.V. Biblioteka matematicheskih funkcij dlja jazyka funkcional'no-potokovogo parallel'nogo programmirovanija Pifagor [Library of mathematical functions for the language of data-driven functional parallel programs Pythagor] / Ju.V. Udalova // Vestnik Burjatskogo gosudarstvennogo universiteta. Matematika, informatika [Bulletin of the Buryat state University. Mathematics, computer science] – 2019. – № 4. – P. 57–64. DOI: 10.18101/2304-5728-2019-4-57-64 [in Russian]
9. Ushakova M. S. Verifikacija programm so vzaimnoj rekursiej na jazyke Pifagor [Verification of programs with mutual recursion in the Pythagor language] / M. S. Ushakova, A.I. Legalov // Modelirovanie i analiz informacionnyh system [Modeling and analysis of information systems] – 2018. – V. 25. – № 4 (76). – P. 358–381. DOI: 10.18255/1818-1015-2018-4-358-381[in Russian]
10. Vasil'ev V. S. Optimizacija invarianta cikla v jazyke Pifagor [Optimization of the loop invariant in the Pythagor language] / V. S. Vasil'ev, A.I. Legalov // Modelirovanie i analiz informacionnyh system [Modeling and analysis of information systems] – 2018. – V. 25 – № 4 (76) – P. 347–357. DOI: 10.18255/1818-1015-2018-4-347-357 [in Russian]
11. Udalova Ju.V. Verifikacija funkcional'no-potokovyh parallel'nyh programm metodom induktivnyh utverzhdenij [Verification of data-driven functional parallel programs by the method of inductive statements] / Ju.V. Udalova, A.I. Legalov // Doklady Akademii nauk vysshej shkoly Rossijskoj Federacii [Reports of the Academy of Sciences of the higher school of the Russian Federation] – 2014. – № 2–3 (23–24). – P. 125–132. [in Russian]