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

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

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

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

ЛитератураПравить

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