On transformations of untyped functional programs and their procedural semantics

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