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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Суперкомбинатор — замкнутое математическое выражение, которое не содержит внутри себя свободных переменных. Это может быть либо константа, либо комбинатор, в котором все подвыражения являются суперкомбинаторами. С точки зрения математики λ-терм \(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.