Scribd
Upload
294 views

Programming Computable Functions

PCF is a typed functional programming language introduced in 1977 as an extension of the Logic of Computable Functions. It serves as a model of computation for effective functions. PCF has a simple type system and semantics but was not initially given a fully abstract model. Later work in game semantics and logical relations produced the first fully abstract models not relying on syntactic methods. The language's denotational semantics interprets types as domains and terms as continuous functions between domains in a category of domains. However, this model is not fully abstract for full PCF.

Uploaded by

Hgfghf Ghfghgf
Copyright
© Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online on Scribd
294 views

Programming Computable Functions

PCF is a typed functional programming language introduced in 1977 as an extension of the Logic of Computable Functions. It serves as a model of computation for effective functions. PCF has a simple type system and semantics but was not initially given a fully abstract model. Later work in game semantics and logical relations produced the first fully abstract models not relying on syntactic methods. The language's denotational semantics interprets types as domains and terms as continuous functions between domains in a category of domains. However, this model is not fully abstract for full PCF.

Uploaded by

Hgfghf Ghfghgf
Copyright
© Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Programming Computable Functions

Programming Computable Functions


In computer science, Programming Computable Functions,[1] or PCF, is a typed functional language introduced by Gordon Plotkin in 1977. It is based on the Logic of Computable Functions (LCF) by Dana Scott. 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. A fully abstract model for PCF was first given by Milner (1977). However, since Milner's model was essentially based on the syntax of PCF it was considered less than satisfactory (Ong, 1995). The first two fully abstract models not employing syntax were formulated during the 1990s. These models are based on game semantics (Hyland and Ong, 2000; Abramsky, Jagadeesan, and Malacaria, 2000) and Kripke logical relations (O'Hearn and Riecke, 1995). 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.

Syntax
The types of PCF are inductively defined as nat is a type For types and , there is a type A context is a list of pairs x : , where x is a variable name and is a type, such that no variable name is duplicated. One then defines typing judgments of terms-in-context in the usual way for the following syntactical constructs: Variables (if x : is part of a context , then x : ) Application (of a term of type to a term of type ) -abstraction The Y fixed point combinator (making terms of type out of terms of type ) The successor (succ) and predecessor (pred) operations on nat and the constant 0 The conditional if with the typing rule:

(nats will be interpreted as booleans here with a convention like zero denoting truth, and any other number denoting falsity)

Semantics
Denotational semantics
A relatively straightforward semantics for the language is the Scott model. In this model, Types are interpreted as certain domains. (the natural numbers with a bottom element adjoined, with the flat ordering) is interpreted as the domain of Scott-continuous functions from to is interpreted as the product are interpreted as continuous functions

A context Terms in context

Variable terms are interpreted as projections Lambda abstraction and application are interpreted by making use of the cartesian closed structure of the category of domains and continuous functions Y is interpreted by taking the least fixed point of the argument

Programming Computable Functions This model is not fully abstract for PCF; but it is fully abstract for the language obtained by adding a parallel or operator to PCF (p.293 in the Hyland and Ong 2000 reference below).

Notes
[1] "PCF is a programming language for computable functions, based on LCF, Scotts logic of computable functions" (Plotkin 1977). Programming Computable Functions is used by (Mitchell 1996). It is also referred to as Programming with Computable Functions or Programming language for Computable Functions.

References
Abramsky, S., Jagadeesan, R., and Malacaria, P. (2000). "Full Abstraction for PCF". Information and Computation 163 (2): 409470. doi:10.1006/inco.2000.2930. Hyland, J. M. E. and Ong, C.-H. L. (2000). "On Full Abstraction for PCF". Information and Computation 163 (2): 285408. doi:10.1006/inco.2000.2917. O'Hearn, P. W. and Riecke, J. G (1995). "Kripke Logical Relations and PCF". Information and Computation 120 (1): 107116. doi:10.1006/inco.1995.1103. Loader, R. (2001). "Finitary PCF is not decidable". Theoretical Computer Science 266 (1-2): 341364. doi:10.1016/S0304-3975(00)00194-8. Ong, C.-H. L. (1995). "Correspondence between Operational and Denotational Semantics: The Full Abstraction Problem for PCF" (http://users.comlab.ox.ac.uk/luke.ong/publications/index.html). In Abramsky, S., Gabbay, D., and Maibau, T. S. E.. Handbook of Logic in Computer Science. Oxford University Press. pp.269356. Plotkin, Gordon D. (1977). "LCF considered as a programming language" (http://homepages.inf.ed.ac.uk/ gdp/publications/LCF.pdf). Theoretical Computer Science 5: 223255. doi:10.1016/0304-3975(77)90044-5. Mitchell, John C. (1996). "The Language PCF". Foundations for Programming Languages.

External links
Introduction to RealPCF (http://www.cs.bham.ac.uk/~mhe/papers/RNC3.pdf) Lexer and Parser for PCF written in SML (http://www.cs.pomona.edu/classes/cs131/Parsers/parsePCF.sml)

Article Sources and Contributors

Article Sources and Contributors


Programming Computable Functions Source: http://en.wikipedia.org/w/index.php?oldid=494141826 Contributors: Arjayay, AugPi, CRGreathouse, Functor salad, Imz, Khazar, Koffieyahoo, Ruud Koot, Smimram, That Guy, From That Show!, Tizio, Wipe, 7 anonymous edits

License
Creative Commons Attribution-Share Alike 3.0 Unported //creativecommons.org/licenses/by-sa/3.0/

You might also like