Комбинаторная логика (назначение, синтаксис выражений, основные комбинаторы, правила редукции для них).

Так как в l-исчислении функции не имеют имен, то для представ-ия рекурсии необходим метод, позволяющий функциям вызывать себя не по имени, а каким-то другим способом. Можно представить рекурс-ую функцию как функцию, имеющую саму себя в качестве аргумента. Для вызова такой функции используется Y-комбинатор, удовлетворяющий уравнению Y f=f(Y f), который известен также как комбинатор фиксир. точки. Одно из возможных определений Y-комбинатора имеет вид Y-lh. (lx. H(x x))(lx.h(x x)).

  При вычислении l-выражений основной проблемой, снижающей эффективность, является порождение копии тела функции, чтобы за-менить переменные соответствующими им выражениями. Комбинаторная логика позволяет избавиться от переменных и свести вычисление выражения к выполнению последовательности преобра-зований, определяемых комбинаторами.

  Выражения в комбинаторной логике имеют следующий синтаксис:

<выр>::==<конст>