Categorical abstract machine
Encyclopedia
The categorical abstract machine (CAM) is a model of computation
for programs that preserves the abilities of applicative, functional, or compositional style. It is based on the techniques of applicative computing
.
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 all the advantages of object approach towards programming or computing.
, 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 the 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.
Model of computation
In computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs...
for programs that preserves the abilities of applicative, functional, or compositional style. It is based on the techniques of applicative computing
Applicative computing systems
Applicative computing systems, or ACS are the systems of object calculi founded on combinatory logic and lambda calculus.The only essential notion which is under consideration in these systems is the representation of object. In combinatory logic the only metaoperator is application in a sense of...
.
Overview
The notion of the categorical abstract machine arose in the mid-1980s and. It took its place in computer science as a kind of theory of computationTheory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
for programmers, represented by Cartesian closed category
Cartesian closed category
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
and embedded into the combinatory logic
Combinatory logic
Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...
. 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
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
or lazy evaluation
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
can be emulated as well as parameter passing, such as call by name, call by value, and so on. In theory, CAM preserves all the advantages of object approach towards programming or computing.
Implementation
One of the implementation approaches to functional languages is given by the machinery based on supercombinatorsSupercombinator
A supercombinator is a mathematical expression which is fully bound and self-contained. It may either be a constant or a combinator where all the subexpressions are 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 the de Bruijn’s
Nicolaas Govert de Bruijn
Nicolaas Govert de Bruijn is a Dutch mathematician, affiliated as professor emeritus with the Eindhoven University of Technology. He received his Ph.D. in 1943 from Vrije Universiteit Amsterdam....
notation, which overcomes the difficulties of using bound variables. The evaluations are similar to those of P. Landin’s
Peter J. Landin
Peter John Landin was a British computer scientist. He was one of the first to realize that the lambda calculus could be used to model a programming language, an insight that is essential to development of both functional programming and denotational semantics.- Academic :Landin was born in...
SECD machine
SECD machine
The SECD machine is a highly influential virtual machine and abstract machine intended as a target for functional programming language compilers. The letters stand for Stack, Environment, Code, Dump, the internal registers of the machine...
. With this coverage, CAM gives a sound ground for syntax, semantics, and theory of computation
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
. This comprehension arises as being influenced by the functional style of programming.
Further reading
- Wolfengagen, V.E. 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.