Categorical abstract machine: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 14:41, 10 May 2022

The categorical abstract machine (CAM) is a model of computation for programs^[1] that preserves the abilities of applicative, functional, or compositional style. It is based on the techniques of applicative computing.

Overview

The notion of the categorical abstract machine arose in the mid-1980s. It took its place in computer science as a kind of theory of computation for programmers, represented by Cartesian closed category and embedded into the combinatory logic. CAM is a transparent and sound mathematical representation for the languages of functional programming. The machine code can be optimized using the equational form of a theory of computation. Using CAM, the various mechanisms of computation such as recursion or lazy evaluation can be emulated as well as parameter passing, such as call by name, call by value, and so on. In theory, CAM preserves^[how?] all the advantages of object approach towards programming or computing.

The main current implementation is OCaml, which added class inheritance and dynamic method dispatch to Caml the Categorical Abstract Machine Language. Both are variants of MetaLanguage ML, and all three languages implement type inference.

Implementation

One of the implementation approaches to functional languages is given by the machinery based on supercombinators, or an SK-machine, by D. Turner. The notion of CAM gives an alternative approach. The structure of CAM consists of syntactic, semantic, and computational constituents. Syntax is based on de Bruijn’s notation, which overcomes the difficulties of using bound variables. The evaluations are similar to those of P. Landin’s SECD machine. With this coverage, CAM gives a sound ground for syntax, semantics, and theory of computation. This comprehension arises as being influenced by the functional style of programming.

References

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

@@ Line 1: / Line 1: @@
+{{Refimprove|date=December 2012}}
-'''Categorical abstract machine (CAM)''' — is the [[model of computation]] of a program<ref>''Cousineau G., Curien P.-L., Mauny M.'' The categorical abstract machine. — LNCS, 201, Functional programming languages computer architecture.-- 1985, pp.~50-64.</ref>, which preserves the abilities of applicative, functional or compositional style.
-It is based on techniques of the [[applicative computing systems|applicative computing]].
+The '''categorical abstract machine''' ('''CAM''') is a [[model of computation]] for programs<ref>''Cousineau G., Curien P.-L., Mauny M.'' The categorical abstract machine. — LNCS, 201, Functional programming languages computer architecture.-- 1985, pp.~50-64.</ref> that preserves the abilities of applicative, functional, or compositional style. It is based on the techniques of [[applicative computing systems|applicative computing]].
-One of the implementation approaches to functional languages is given by the machinery based on [[supercombinator|  supercombinators]], or SK-machine by D. Turner. The notion of CAM gives the alternative approach. The structure of CAM consists of syntactic, semantic and computational constituents. Syntax is based on the [[Nicolaas Govert de Bruijn | de Bruijn’s]] notation which overcomes the difficulties of using the bound variables. Semantics is as representative as SK-machine. The evaluations are similar to those of P. Landin’s SECD-machine. With this coverage CAM gives a sound ground for syntax, semantics and [[theory of computation]]. This comprehension arises as being influenced by the functional style of programming.
+== Overview ==
-The notion of categorical abstract machine, or CAM was arisen in mid-1980th and in computer science takes a place of a kind of ''[[theory of computation]] for programmers''.
-In a theory CAM is represented by [[Cartesian closed category]] (c.c.c.) and embedded into the [[combinatory logic]]. The machine instructions are the combinators-as-objects giving rise to a special kind of [[combinatory logic]] -- the [[categorical combinatory logic]]. CAM is a transparent and sound mathematical representation for the languages of functional programming. The machine code can be optimized using the equational form of a theory of computation. Using CAM the various mechanisms of computation such as [[recursion]], [[lazy evaluation]] can be emulated as well as parameter passing: [[call by name]], [[call by value]] etc. In a theory CAM preserves all the advantages of object approach towards programming or computing.
+The notion of the categorical abstract machine arose in the mid-1980s. It took its place in computer science as a kind of [[theory of computation]] for programmers, represented by [[Cartesian closed category]] and embedded into the [[combinatory logic]]. CAM is a transparent and sound mathematical representation for the languages of functional programming. The machine code can be optimized using the equational form of a theory of computation. Using CAM, the various mechanisms of computation such as [[recursion]] or [[lazy evaluation]] can be emulated as well as parameter passing, such as [[call by name]], [[call by value]], and so on. In theory, CAM preserves{{how|date=December 2015}} all the advantages of object approach towards programming or computing.
+The main current implementation is OCaml, which added class inheritance and dynamic method dispatch to [[Caml]] the Categorical Abstract Machine Language.  Both are variants of MetaLanguage [[ML (programming language)|ML]], and all three languages implement [[type inference]].
-== de Bruijn’s notation ==
+== Implementation ==
-'''De Bruijn’s notation''' is the method of replacement for bound variables (formal parameters) which overcomes the bounding collision when substituting the formal parameters by the actual ones. This method is used in a code compiling faze for CAM. This kind of replacing the bound variables can be mentioned as “de Bruijn’s encoding” and is vital in using the calculi of [[lambda calculus | lambda-conversion]] on the same rights as the calculi of [[combinatory logic]].
+One of the implementation approaches to functional languages is given by the machinery based on [[Supercombinator|  supercombinators]], or an SK-machine, by D. Turner. The notion of CAM gives an alternative approach. The structure of CAM consists of syntactic, semantic, and computational constituents. Syntax is based on [[Nicolaas Govert de Bruijn | de Bruijn’s]] [[ De Bruijn notation | notation]], which overcomes the difficulties of using bound variables. The evaluations are similar to those of [[Peter J. Landin | P. Landin’s]] [[SECD machine]]. With this coverage, CAM gives a sound ground for syntax, semantics, and [[theory of computation]]. This comprehension arises as being influenced by the functional style of programming.
 == See also ==
+{{colbegin|colwidth=25em}}
+*[[Combinatory logic]]
+*[[Typed lambda calculus]]
+*[[Cartesian closed category]]
 * [[Applicative computing systems]]
-* [[Combinatory logic]]
+*[[Anonymous recursion]]
-* [[Typed lambda calculus]]
+*[[Evaluation strategy]]
+*[[Explicit substitution]]
+*[[SKI combinator calculus]]
+*[[Unlambda]]
 * [[Currying]]
+* [[Caml]]
+{{colend}}
 == References ==
+{{reflist}}
-<references/>
 == Further reading ==
-* Wolfengagen, V.E. ''[http://vew.0catch.com/books/Wolfengagen_CLP-2003-En.djvu Combinatory logic in programming.] Computations with objects through examples and exercises''. -- 2-nd ed. -- M.: "Center JurInfoR" Ltd., 2003. -- x+337 с. ISBN 5-89158-101-9.
+* Wolfengagen, V.E. ''[https://web.archive.org/web/20070128222953/http://www.wolfengagen.mephi.ru/papers/Wolfengagen_CLP-2003(En).pdf Combinatory Logic in Programming]: Computations with Objects through Examples and Exercises''. 2nd ed. M.: "Center JurInfoR" Ltd., 2003. x+337 с. {{ISBN|5-89158-101-9}}.
-[[Category:Theoretical computer science]]
+[[Category:Implementation of functional programming languages]]
-[[Category:Theory of computation]]
+[[Category:Models of computation]]
-[[Category:Computational models]]
-[[Category:Formal methods]]
 [[Category:Applicative computing systems]]
-[[ru:Категориальная абстрактная машина]]