Сибирский федеральный университет

Перевод названия: Features of tail recursion transformation in a functional dataflow language for parallel programming

Тип публикации: статья из журнала

Год издания: 2013

Ключевые слова: tail recursion, Code optimization, functional programming, Dataflow programming, information graph, destructive assignment, delayed list, хвостовая рекурсия, оптимизация программы, функциональное программирование, программирование потоков данных, информационный граф, разрушающее присваивание, задержанный список

Аннотация: В работе рассматриваются вопросы выявления хвостовой рекурсии и ее преобразования в цикл для языка функционально-потокового параллельного программирования Пифагор. Данный язык ориентирован на реализацию не только последовательных, но и параллельных рекурсивных вызовов. Вместе с тем, применение в нем хвостовой рекурсии также допустимо и позволяет реализовывать конвейерный параллелизм при использовании асинхронных списков. Среди возможных вариантов исследуется случай, когда рекурсивный вызов является последней операцией внутри задержанного списка, раскрываемой перед возвратом из функции. При этом предполагается что аргумент, поступающий на вход функции, является списком данных или скаляром. Данная ситуация является одной из простейших, но при этом широко применяется в различных программах. Реализация метода ее преобразования в итерацию позволяет в дальнейшем перейти к оптимизации программ, в которых хвостовая рекурсия сочетается с другими операциями, используемыми при функционально-потоковом параллельном программировании. Приведенный пример демонстрирует особенности замены хвостовой рекурсии специальной операцией повторения, позволяющей перенаправить выходной поток данных на вход, используемый для поступления аргумента функции. Для рассматриваемого случая предложен алгоритм преобразования хвостовой рекурсии в итерацию. Описаны действия, выполняемые оператором повторения функции при передаче данных на вход аргумента. Выполняемые алгоритмом преобразования осуществляются на реверсивном информационном графе, формируемом в процессе трансляции исходных текстов анализируемой функции The paper deals with detection of a tail recursion and its transformation into the cycle for the PIFAGOR functional dataflow parallel programming language. The language is focused on the implementation of not only consistent calls but parallel recursive ones as well. At the same time, the use of the tail recursion is also acceptable and allows implementing pipelined parallelism while using asynchronous lists. Among the choices, the case where a recursive call is the last operation within the delayed list disclosed before returning from the function is studied. It is assumed that an argument entering the function is a data list or a scalar. This situation is one of the simplest and it is being widely used in various programs. The implementation of the method of its transformation into iteration allows further programs optimization where the tail recursion is combined with other operations used in a functional dataflow parallel programming. The examined example shows the features of replacing the tail recursion by a special repetition operation, which allows redirecting the output dataflow used for entering the function argument toward the input. For the case under consideration, the algorithm of the tail recursion transformation into iteration has been proposed. The actions made by the function loop statement in transferring the data to the argument input have been described. The performed transformations are carried out on a reversing information graph being formed in the process of translation of the analyzed function incoming texts

Журнал: Системы. Методы. Технологии

Выпуск журнала: № 3

Номера страниц: 106-111

ISSN журнала: 20775415

Место издания: Братск

Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Братский государственный университет"

• Васильев В.С. (Сибирский федеральный университет)
• Легалов А.И. (Сибирский федеральный университет)
• Постников А.И. (Сибирский федеральный университет)

• РИНЦ (eLIBRARY.RU)
• Список ВАК