Суперкомбинатор

Суперкомбинатор — замкнутое математическое выражение, которое не содержит внутри себя свободных переменных. Это может быть либо константа, либо комбинатор, в котором все подвыражения являются суперкомбинаторами. С точки зрения математики λ-терм $S$ является суперкомбинатором арности $n$, если в нём нет свободных переменных и он имеет вид $\lambda x_1.\lambda x_2 \ldots \lambda x_n.E$ (при $n \ge 0$, поэтому сами по себе связывающие символы «λ» не нужны), где выражение $E$ не является λ-абстракцией и все λ-абстракции внутри $E$ являются суперкомбинаторами.

Другими словами суперкомбинатор $\$ S$ может быть определён следующим образом: $$\$ S \equiv \lambda x_1.\lambda x_2 \ldots \lambda x_n.E,$$ где $E$ не является λ-абстракцией и:

1. Выражение $S$ не содержит связанных переменных.
2. Все имеющиеся λ-абстракции в $E$ являются суперкомбинаторами.
3. $n \ge 0$.

Литература

• S. L. Peyton Jones, The Implementation of Functional Programming Languages. Prentice Hall, 1987.