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

В различных методах преобразования программ возникают объекты, подобные программам, но способные содержать несколько определений одной и той же функции — мы будем называть такие объекты полипрограммами. Например, в системе Бëрстолла–Дарлингтона такими объектами являются просто множества рекурсивных уравнений, а в насыщении равенствами Тейта и др. аналогичная структура называется E-PEG. Важным свойством полипрограмм, используемым в этих преобразованиях, является их способность представлять множества обычных программ. В данной работе мы вводим понятие полипрограммы на нестрогом функциональном языке первого порядка, определяем денотационную семантику для полипрограмм, и описываем некоторые возможные преобразования полипрограмм. Мы также касаемся темы выделения обычных программ из полипрограммы.