Categorical abstract machine


Categorical abstract machine

Categorical abstract machine (CAM) — is the model of computation of a program ["Cousineau G., Curien P.-L., Mauny M." The categorical abstract machine. — LNCS, 201, Functional programming languages computer architecture.-- 1985, pp.~50-64.] , which preserves the abilities of applicative, functional or compositional style.It is based on techniques of the applicative computing.

One of the implementation approaches to functional languages is given by the machinery based on 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 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.

The notion of categorical abstract machine, or CAM arose in the mid-1980s 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.

de Bruijn’s notation

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 phase 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-conversion on the same rights as the calculi of combinatory logic.

See also


*Combinatory logic
*Typed lambda calculus
*Cartesian closed category
* Applicative computing systems
*Anonymous recursion
*Evaluation strategy
*Explicit substitution
*SKI combinator calculus
*Unlambda
* Currying
* Caml

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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Abstract machine — An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. Abstraction of computing processes is used in both the computer science and computer engineering… …   Wikipedia

  • Ghost in the machine — This article is about a philosophical critique. For other uses, see Ghost in the machine (disambiguation). The ghost in the machine is the British philosopher Gilbert Ryle s description of René Descartes mind body dualism. The phrase was… …   Wikipedia

  • Caml — Infobox programming language name = Caml paradigm = multi paradigm: functional, imperative; object oriented in OCaml year = 1985 typing = strong, static designer = Gérard Huet, Guy Cousineau, Ascánder Suárez, Pierre Weis, Michel Mauny (Heavy… …   Wikipedia

  • Objective Caml — Infobox programming language name = Objective Caml paradigm = multi paradigm: imperative, functional, object oriented developer = INRIA latest release version = 3.10.2 latest release date = Release date and age|2008|02|29 operating system = Cross …   Wikipedia

  • OCaml — Paradigm(s) multi paradigm: imperative, functional, object oriented Appeared in 1996 Developer INRIA Stable release 3.12.1 (July 4, 2011; 4 months ago ( …   Wikipedia

  • OCaml — Objective Caml Apparu en 1987 (CAML), 1996 (OCaml) Développeur INRIA Dernière version stable …   Wikipédia en Français

  • Objective Caml — Apparu en 1987 (CAML), 1996 (OCaml) Développeur INRIA Dernière version stable 3.11.1 (le 12  …   Wikipédia en Français

  • Ocaml — Objective Caml Apparu en 1987 (CAML), 1996 (OCaml) Développeur INRIA Dernière version stable 3.11.1 (le 12  …   Wikipédia en Français

  • O’Caml — Objective Caml Apparu en 1987 (CAML), 1996 (OCaml) Développeur INRIA Dernière version stable 3.11.1 (le 12  …   Wikipédia en Français

  • Cam (disambiguation) — A cam is a mechanical linkage which translates motion.Cam or CAM may also refer to:Abbreviations* Crassulacean acid metabolism, a water conserving metabolic process of most succulent plants * Camelopardalis, standard astronomical abbreviation * A …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.