Programming Computable Functions

PCF or Programming language for Computable Functions is a typed functional language introduced by Gordon Plotkin in 1977. It is based on the Logic of Computable Function (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 Kripe logical relations (O'Hearn and Riecke, 1995).

External link

• Introduction to RealPCF

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.
• 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.
• 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.
• http://users.comlab.ox.ac.uk/luke.ong/publications/index.html. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Chapter= ignored (|chapter= suggested) (help); Unknown parameter |Editor= ignored (|editor= suggested) (help); Unknown parameter |Pages= ignored (|pages= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help)
• Plotkin, G. D. (1977). "LCF considered as a programming language". Theoretical Computer Science. 5: 223–255. doi:10.1016/0304-3975(77)90044-5.