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

Категориальная абстрактная машина
Wiki letter w.svg
 Для улучшения этой статьи желательно?:
  • Исправить статью согласно стилистическим правилам Википедии.

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

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

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

Содержание

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

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

См. также

Примечания

  1. ↑ 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.

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


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

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

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

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

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

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

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

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

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

  • Типизированное лямбда-исчисление — Типизированное λ исчисление это типовый формализм, использующий символ абстракции «λ» для записи выражений, обозначающих безымянные функции. Типовые λ исчисления являются фундаментальными примитивными языками программирования, которые… …   Википедия

  • Вольфенгаген, Вячеслав Эрнстович — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей …   Википедия


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

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