Programming Computable Functions: Difference between revisions

Revision as of 21:49, 22 June 2007

Revision as of 17:48, 17 November 2007

Line 3:

A [[fully abstract]] model for PCF was first given by [[Robin Milner|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 linklinks==

* [http://www.cs.bham.ac.uk/~mhe/papers/RNC3.pdf Introduction to RealPCF]

* [http://www.cs.pomona.edu/classes/cs131/Parsers/parsePCF.sml Lexer and Parser for PCF written in SML]

Line 69 ⟶ 68:

| id = {{doi|10.1016/0304-3975(77)90044-5}}

}}

{{compu-lang-stub}}

[[Category:Programming languages]]

{{compu-lang-stub}}