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

Перевод названия: Verification of Programs with Mutual Recursion in the Pifagor Language

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

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

Идентификатор DOI: 10.18255/1818-1015-2018-4-358-381

Ключевые слова: data driven functional parallel programming, Pifagor programming language, correctness of recursions, elimination of mutual recursion, universal recursive function, функционально-потоковое параллельное программирование, язык программирования Пифагор, корректность рекурсий, удаление взаимной рекурсии, универсальная рекурсивная функция

Аннотация: В работе рассматривается верификация программ со взаимной рекурсией для языка функционально-потокового параллельного программирования Пифагор. В языке используется модель представления программы в виде графа потока данных (информационного графа), в котором нет дополнительных управляющих связей, а присутствуют только информационные зависимости. Это позволяет упростить процесс верификации, так как не требует анализа возникающих в традиционных архитектурах дополнительных ресурсных конфликтов. Доказательство корректности программы опирается на удаление взаимных рекурсий посредством преобразования программы. Универсальным способом удаления взаимной рекурсии произвольного количества функций является построение универсальной рекурсивной функции, которая выполняет работу всех исходных функций и принимает, кроме аргумента выполняемой функции, натуральное число, являющееся номером выполняемой функции. В ряде случаев, когда присутствует косвенная рекурсия, можно использовать более простой способ преобразования - объединение кода функций, при котором происходит объединение тел вызывающих друг друга функций. Для преобразования произвольной рекурсии в прямую предлагается построение графа всех связанных функций и последующая трансформация данного графа путём удаления функций, не связанных с рассматриваемой, объединения косвенно рекурсивных функций и построения универсальной рекурсивной функции. Доказывается, что изменение функции на языке Пифагор при объединении кода и построении универсальной рекурсивной функции не влияет на корректность исходной программы. Приводится пример доказательства частичной корректности программы на языке Пифагор, осуществляющей синтаксический разбор простого арифметического выражения. После построения графа всех связанных функций рассматриваются два способа доказательства: с использованием объединения кода функций и с построением универсальной рекурсивной функции. In the article, we consider verification of programs with mutual recursion in the data driven functional parallel language Pifagor. In this language the program could be represented as a data flow graph, that has no control connections, and has only data relations. Under these conditions it is possible to simplify the process of formal verification, since there is no need to analyse resource conflicts, which are present in the systems with ordinary architectures. The proof of programs correctness is based on the elimination of mutual recursions by program transformation. The universal method of mutual recursion of an arbitrary number of functions elimination consists in constructing the universal recursive function that simulates all the functions in the mutual recursion. A natural number is assigned to each function in mutual recursion. The universal recursive function takes as its argument the number of a function to be simulated and the arguments of this function. In some cases of the indirect recursion it is possible to use a simpler method of program transformation, namely, the merging of the functions code into a single function. To remove mutual recursion of an arbitrary number of functions, it is suggested to construct a graph of all connected functions and transform this graph by removing functions that are not connected with the target function, then by merging functions with indirect recursion and finally by constructing the universal recursive function. It is proved that in the Pifagor language such transformations of functions as code merging and universal recursive function construction do not change the correctness of the initial program. An example of partial correctness proof is given for the program that parses a simple arithmetic expression. We construct the graph of all connected functions and demonstrate two methods of proofs: by means of code merging and by means of the universal recursive function.

Журнал: Моделирование и анализ информационных систем

Выпуск журнала: Т. 25, № 4

Номера страниц: 358-381

ISSN журнала: 18181015

Место издания: Ярославль

Издатель: федеральное государственное бюджетное образовательное учреждение высшего образования "Ярославский государственный университет им. П.Г. Демидова"

• Ушакова Мария Сергеевна (Сибирский федеральный университет, Институт космических и информационных технологий)
• Легалов Александр Иванович (Сибирский федеральный университет, Институт космических и информационных технологий)

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