В 1990 году Джон Лэмпинг опубликовал статья, предлагающая оптимальную реализацию нетипизированного лямбда-исчисления. Поскольку этой газете уже 25 лет, интересно, насколько мы продвинулись с тех пор. Таким образом, мой вопрос: каково простое описание оптимального алгоритма оценки лямбда-исчисления Джона (или, в случае, если мы сделали улучшения с тех пор, улучшенного алгоритма), предпочтительно кратко объясненного на псевдокоде Haskellish?
Обновление: поскольку я узнал больше с тех пор, как спросил, я считаю, что правильным ответом может быть просто псевдокод для нераздутого алгоритма, который 1. отображает чистые нетипизированные лямбда-члены в сети взаимодействия; 2. уменьшает эти сети и 3. отображает обратно из сетей в лямбда-члены, так что весь процесс оптимальным образом нормализует начальный лямбда-член.
