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