Категориальная абстрактная машина

Категориа́льная абстра́ктная маши́на (КАМ) — это модель вычисления программы^[1], в которой сохраняются особенности аппликативного, функционального либо композиционного стиля. Она опирается на технику аппликативного вычисления.

Один из подходов к реализации функциональных языков дается машиной, основанной на суперкомбинаторах, или SK-машиной Дэвида Тёрнера. Представление о категориальной абстрактной машине даёт альтернативный подход^{[уточнить]}. Строение КАМ включает синтаксическую, семантическую и вычислительную конституэнты^{[уточнить]}. Синтаксис основан на формализме де Брёйна, использование которого позволяет преодолеть трудность, вызываемые применением связанных переменных. Семантика по своим выразительным возможностям аналогична SK-машине. Вычисления выполняются по аналогии тем вычислениям, которые использованы в SECD-машине Лэндина. Занимая такие позиции^{[уточнить]}, категориальная абстрактная предоставляет непротиворечивые основания для синтаксиса, семантики и теории вычислений. Такая интеграция возникает не без влияния функционального стиля программирования.

Концепция категориальной абстрактной машины возникла в середине 1980-х годов и играет роль варианта теории вычислений для программистов^{[уточнить]}. С теоретической точки зрения, категориальная абстрактная машина представлена декартово замкнутой категорией и погружена в комбинаторную логику. Машинные инструкции являются объектами-комбинаторами, образуя в совокупности специальный вариант комбинаторной логики — категориальную комбинаторную логику. Категориальная абстрактная машина является ясным и математически корректным представлением языков функционального программирования. Используя равенства выражений, машинный код удаётся оптимизировать^{[источник не указан 4034 дня]}. Особенно отчётливо проявляют различные механизмы вычислений — рекурсия, ленивые вычисления, — а также механизмы передачи параметров — вызов по имени, вызов по значению и т. п. С теоретической точки зрения категориальная абстрактная машина сохраняет все преимущества объектно-ориентированного подхода к программированию^{[источник не указан 4034 дня]}.

Формализм де БрёйнаПравить

Формализм де Брёйна — техника переобозначения связанных переменных (формальных параметров), которая позволяет избежать коллизий связывания при замещении формальных параметров на фактические. Он применяется при компилировании программного кода на КАМ. Этот прием переобозначения также носит название кодирования по де Брейну и он позволяет, фактически, аппаратом λ-исчисления пользоваться на тех же самых правах, что и аппаратом комбинаторной логики.

См. такжеПравить

ПримечанияПравить

↑ Cousineau G., Curien P.-L., Mauny M. The categorical abstract machine. — LNCS, 201, Functional programming languages computer architecture.-- 1985, pp.~50-64.

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

Вольфенгаген В. Э. Категориальная абстрактная машина. Конспект лекций: введение в вычисления. — 2-е изд. — М: АО «Центр ЮрИнфоР», 2002. — 96 с ISBN 5-89158-102-7.

[1] Cousineau G., Curien P.-L., Mauny M. The categorical abstract machine. — LNCS, 201, Functional programming languages computer architecture.-- 1985, pp.~50-64.

[1]