The Programming language for Computable Functions, 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 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.
External links
Sources
- Abramsky, S., Jagadeesan, R., and Malacaria, P. (2000). "Full Abstraction for PCF". Information and Computation. 163 (2): 409–470. doi:10.1006/inco.2000.2930.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - Hyland, J. M. E. and Ong, C.-H. L. (2000). "On Full Abstraction for PCF". Information and Computation. 163 (2): 285–408. doi:10.1006/inco.2000.2917.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - O'Hearn, P. W. and Riecke, J. G (1995). "Kripke Logical Relations and PCF". Information and Computation. 120 (1): 107–116. doi:10.1006/inco.1995.1103.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - Loader, R. (2001). "Finitary PCF is not decidable". Theoretical Computer Science. 266 (1–2): 341–364. 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". In Abramsky, S., Gabbay, D., and Maibau, T. S. E. (ed.). Handbook of Logic in Computer Science. Oxford University Press. pp. 269–356.
{{cite book}}: CS1 maint: multiple names: editors list (link) - Plotkin, G. D. (1977). "LCF considered as a programming language". Theoretical Computer Science. 5: 223–255. doi:10.1016/0304-3975(77)90044-5.
 | This programming-language-related article is a stub. You can help Wikipedia by expanding it. |