В переписке Барендрегт показал несколько страниц из "J. Klop's Ustica notes", где говорится о существовании многошаговых рекурсивных нормализующих стратегий для "Micro Lambda Calculus" - именно так называется на самом деле редукция из заметки "The Delayed Beta Reduction".
Одна из многошаговых стратегий для "Micro Lambda Calculus" определена в статье "Axioms for the Theory of Lambda-Conversion" (Gyorgy Revesz) - предложенная там стратегия является многошаговой потому, что для выбора редекса используется не только само вычисляемое выражение, но и информация о предыдущих шагах вычисления.
К сожалению, по словам Барендрегта, вопрос о том, существует ли одношаговая стратегия для "Micro Lambda Calculus", остается открытым. Возможно, стоит заняться этой темой и попытаться доказать возможность (например, конструктивно) или невозможность существования такой стратегии.
Также хотелось бы построить абстрактную машину, скомбинировав подход "Micro Lambda Calculus" с такими идеями, как однородная память-куча ("The Heap Lambda Machine"), нерекурсивный обход дерева лямбда-выражения ("Функциональное программирование" Филда и Харрисона), а также "Lazy Evaluation" и "Garbage Collection".
Одна из многошаговых стратегий для "Micro Lambda Calculus" определена в статье "Axioms for the Theory of Lambda-Conversion" (Gyorgy Revesz) - предложенная там стратегия является многошаговой потому, что для выбора редекса используется не только само вычисляемое выражение, но и информация о предыдущих шагах вычисления.
К сожалению, по словам Барендрегта, вопрос о том, существует ли одношаговая стратегия для "Micro Lambda Calculus", остается открытым. Возможно, стоит заняться этой темой и попытаться доказать возможность (например, конструктивно) или невозможность существования такой стратегии.
Также хотелось бы построить абстрактную машину, скомбинировав подход "Micro Lambda Calculus" с такими идеями, как однородная память-куча ("The Heap Lambda Machine"), нерекурсивный обход дерева лямбда-выражения ("Функциональное программирование" Филда и Харрисона), а также "Lazy Evaluation" и "Garbage Collection".
