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

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

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

Содержание

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

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

Формально, лямбда-выражение 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.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Суперкомбинаторы" в других словарях:

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

  • Логика в компьютерных науках — Логика в информатике это направления исследований и отрасли знания, где логика применяется в информатике и искусственном интеллекте. Логика оказалась гораздо более эффективной в информатике, чем это было в математике[1]. Включаются следующие… …   Википедия

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

  • Модель вычислений — Иные значения см. разделе в Компьютерное моделирование. Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для… …   Википедия

  • Логика в информатике — Логика в информатике  это направления исследований и отраслей знания, где логика применяется в информатике и искусственном интеллекте. Логика очень эффективна в этих областях[1]. Содержание 1 Область применения …   Википедия

  • Модели вычислений — Иные значения см. разделе в Компьютерное моделирование. Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для… …   Википедия

  • Языки программирования — Язык программирования  формальная знаковая система, предназначенная для записи программ. Программа обычно представляет собой некоторый алгоритм в форме, понятной для исполнителя (например, компьютера). Язык программирования определяет набор… …   Википедия

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

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


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»