Я пишу интерпретатор для лямбда-исчисления в C #.До сих пор я искал следующие пути для интерпретации:
- Компиляция терминов в MSIL, так что ленивая оценка все еще сохраняется.
- Оценка на дереве терминов (переписывание терминов).
На данный момент стратегия компиляции MSIL значительно выше на порядок быстрее в большинстве случаев, которые я смог протестировать.Тем не менее, я смотрю на оптимизацию термина переписывания путем определения шаблонов, часто используемых при построении терминов LC.До сих пор я придумал, в частности, один метод, который обеспечивает относительно небольшое ускорение: идентификация экспонированных приложений.Например, f (f (f (f x))) упрощается до f^4 x.Затем используется правило для приложений равных экспонент заявителя, а именно f^m (f^n x) = f^(m + n) x.Это правило работает очень хорошо, в частности, для возведения в степень церковных чисел.
Эта оптимизация заставляет меня задуматься: существуют ли другие основанные на шаблонах подходы к оптимизации в LC?