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

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

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

Формализм де Брёйна

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

См. также

• Аппликативные вычислительные системы
• Комбинаторная логика
• Лямбда-исчисление с типами
• Каррирование

Примечания

Литература

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