Programming Computable Functions: Difference between revisions

Revision as of 17:09, 18 January 2006

Revision as of 08:28, 19 January 2006

Line 1:

'''PCF''' or [[Programming language for Computable Functions]] is a typed [[Functional programming|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 programming language|ML]].

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 [[Kripe logical relations]] (O'Hearn and Riecke, 1995).

A [[fully abstract]] model for PCF was first given using [[game semantics]].

==External link==

Line 10:

*{{ Journal reference

| Author = Abramsky, S., Jagadeesan, R., and Malacaria, P.

| Last = Plotkin | First = G. D.

| Title = Full Abstraction for PCF

| Journal = Information and Computation

| Date= 2000

| Pages = 409-470

| Volume = 163

| Number = 2

| ID = {{doi|10.1006/inco.2000.2930}}

}}

*{{ Journal reference

| Author = Hyland, J. M. E. and Ong, C.-H. L.

| Title = On Full Abstraction for PCF

| Journal = Information and Computation

| Date= 2000

| Pages = 285-408

| Volume = 163

| Number = 2

| ID = {{doi|10.1006/inco.2000.2917}}

}}

*{{ Journal reference

| Author = O'Hearn, P. W. and Riecke, J. G

| Title = Kripke Logical Relations and PCF

| Journal = Information and Computation

| Date = 1995

| Pages = 107-116

| Volume = 120

| Number = 1

| ID = {{doi|10.1006/inco.1995.1103}}

}}

*{{Book reference

| Author = Ong, C.-H. L.

| Year = 1995

| Title = Handbook of Logic in Computer Science

| Chapter = Correspondence between Operational and Denotational Semantics: The Full Abstraction Problem for PCF

| Editor = Abramsky, S., Gabbay, D., and Maibau, T. S. E.

| Pages = 269-356

| Publisher = Oxford University Press

| URL = http://users.comlab.ox.ac.uk/luke.ong/publications/index.html

}}

*{{ Journal reference

| LastAuthor = Plotkin | First =, G. D.

| Title = LCF considered as a programming language

| Journal = Theoretical Computer Science

Line 16 ⟶ 56:

| Pages = 223-255

| Volume = 5

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

}}