Programming Computable Functions

Programming Computable Functions
Programming Computable Functions
Paradigm	functional
Designed by	Dana Scott,; Robin Milner,; Gordon Plotkin
First appeared	December 1977
Final release	Full Abstraction / 15 December 2000

In computer science, Programming Computable Functions (PCF), or Programming with Computable Functions, or Programming language for Computable Functions, is a programming language which is typed and based on functional programming, introduced by Gordon Plotkin in 1977,^[1] based on prior unpublished material by Dana Scott.^[a] It can be considered as an extended version of the typed lambda calculus, or a simplified version of modern typed functional languages such as ML or Haskell.

A fully abstract model for PCF was first given by Robin Milner.^[2] However, since Milner's model was essentially based on the syntax of PCF it was considered less than satisfactory.^[3] The first two fully abstract models not employing syntax were formulated during the 1990s. These models are based on game semantics^[4]^[5] and Kripke logical relations.^[6] For a time it was felt that neither of these models was completely satisfactory, since they were not effectively presentable. However, Ralph Loader demonstrated that no effectively presentable fully abstract model could exist, since the question of program equivalence in the finitary fragment of PCF is not decidable.^[7]

^ ^a ^b Cite error: The named reference Plotkin 1977 was invoked but never defined (see the help page).
^ Cite error: The named reference Milner 1977 was invoked but never defined (see the help page).
^ Cite error: The named reference Ong 1995 was invoked but never defined (see the help page).
^ Cite error: The named reference Hyland 2000 was invoked but never defined (see the help page).
^ Cite error: The named reference Abramsky 2000 was invoked but never defined (see the help page).
^ Cite error: The named reference O'Hearn 1995 was invoked but never defined (see the help page).
^ Cite error: The named reference Loader 2001 was invoked but never defined (see the help page).

Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).

[Plotkin_1977-1] Cite error: The named reference Plotkin 1977 was invoked but never defined (see the help page).

[Milner_1977-3] Cite error: The named reference Milner 1977 was invoked but never defined (see the help page).

[Ong_1995-4] Cite error: The named reference Ong 1995 was invoked but never defined (see the help page).

[Hyland_2000-5] Cite error: The named reference Hyland 2000 was invoked but never defined (see the help page).

[Abramsky_2000-6] Cite error: The named reference Abramsky 2000 was invoked but never defined (see the help page).

[O'Hearn_1995-7] Cite error: The named reference O'Hearn 1995 was invoked but never defined (see the help page).

[Loader_2001-8] Cite error: The named reference Loader 2001 was invoked but never defined (see the help page).

[1]

[a]

[2]

[3]

[4]

[5]

[6]

[7]