Категориальная абстрактная машина
Материал из Википедии — свободной энциклопедии
 |
Для улучшения статьи желательно?:
|
Категориальная абстрактная машина (КАМ) — это модель вычисления программы[1], в которой сохраняются особенности аппликативного, функционального либо композиционного стиля. Она опирается на технику аппликативного вычисления.
Один из подходов к реализации функциональных языков дается машиной, основанной на суперкомбинаторах, или SK-машиной Д.Тернера. Представление о КАМ дает альтернативный подход. Строение КАМ включает синтаксическую, семантическую и вычислительную конституэнты. Синтаксис основан на формализме Дебрейна, использование которого позволяет преодолеть трудность, вызываемые применением связанных переменных. Семантика по своим выразительным возможностям аналогична SK-машине. Вычисления выполняются по аналогии тем вычислениям, которые использованы в SECD-машине П.Лендина. Занимая такие позиции, КАМ предоставляет непротиворечивые основания для синтаксиса, семантики и теории вычислений. Такая интеграция возникает не без влияния функционального стиля программирования.
Концепция категориальной абстрактной машины, или КАМ, возникла в середине 1980-х гг. и в computer science играет роль варианта теории вычислений для программистов. С теоретической точки зрения КАМ представлена декартово замкнутой категорией (д.з.к.) и погружена в комбинаторную логику. Машинные инструкции являются объектами-комбинаторами, образуя в совокупности специальный вариант комбинаторной логики — категориальную комбинаторную логику. КАМ является ясным и математически корректным представлением языков функционального программирования. Используя равенства выражений, машинный код удается оптимизировать. В КАМ особенно ясно проявляют себя различные механизмы вычислений — рекурсия, ленивые вычисления, — а также механизмы передачи параметров — вызов по имени, вызов по значению и т. п. С теоретической точки зрения КАМ сохраняет все преимущества объектно-ориентированного подхода к программированию.
Содержание |
[править] Формализм Дебрейна
Формализм Дебрейна — это техника переобозначения связанных переменных (формальных параметров), которая позволяет избежать коллизий связывания при замещении формальных параметров на фактические. Он применяется при комплирировании программного кода на КАМ. Этот прием переобозначения также носит название кодирования по де Брейну и он позволяет, фактически, аппаратом λ-исчисления пользоваться на тех же самых правах, что и аппаратом комбинаторной логики.
[править] См. также
[править] Ссылки
- ↑ 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.
