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

Суперкомбинатор — объект, инвариантный относительно среды вычислений, который формируется динамически, в ходе выполнения программы. Суперкомбинаторы устанавливают чисто объектную систему программирования, встроенную в комбинаторную логику. Тем самым непосредственно удовлетворяется потребность в денотационном вычислении инструкций языков программирования, когда объектами выражается функциональный смысл программы. Существенно, что вычисление начинается с некоторого заранее известного набора инструкций. В процессе вычисления значения программы динамически возникают заранее неизвестные, но необходимые по ходу дела инструкции, которые дополнительно фиксируются в системе программирования.

Определение суперкомбинатора

Суперкомбинатор — это математическое выражение, в котором все переменные связаны и которое не зависит от других выражений. Он может быть константой или комбинатором, в котором все подвыражения являются комбинаторами.

Формально, лямбда-выражение S считается суперкомбинатором арности n, если оно имеет вид λx1.λx2…λxn.E (где n ≥ 0, так что символы «λ» не являются обязательными), причем выражение E не является лямбда-абстракцией, а всякая абстракция в E — суперкомбинатор^[1].

Подходы к применению суперкомбинаторов

Имеется два подхода к применению суперкомбинаторов для реализации аппликативных языков программирования. При первом из них программа компилируется посредством фиксированного набора суперкомбинаторов (в неоптимизированном варианте — S, K, I) с заранее известными определениями. При втором подходе определения суперкомбинаторов генерируются самой программой в процессе компиляции.

См. также

• Комбинаторная логика
• Категориальная абстрактная машина
• Аппликативные вычислительные системы
• Аппликативный подход к программированию

Ссылки

1. ↑ Peyton Jones S.L. The implementation of functional programming languages. — N.Y.: Prentice Hall International, 1987. — 445~p. [1]

Литература

• Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — М.: МИФИ, 1994. — 204 с; 2-е изд., М.: АО «Центр ЮрИнфоР», 2003. — 336 с ISBN 5-89158-101-9.