Programming Computable Functions Explained

In computer science, Programming Computable Functions (PCF) is a typed functional language introduced by Gordon Plotkin in 1977, based on previous unpublished material by Dana Scott. It can be considered to be an extended version of the typed lambda calculus or a simplified version of modern typed functional languages such as ML or Haskell.

A fully abstract model for PCF was first given by Robin Milner. However, since Milner's model was essentially based on the syntax of PCF it was considered less than satisfactory. The first two fully abstract models not employing syntax were formulated during the 1990s. These models are based on game semantics and Kripke logical relations. 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

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:

\Gamma\vdasht:bf{nat
,

\Gamma\vdashs0:\sigma, \Gamma\vdashs1:\sigma} { \Gamma\vdashbf{if}(t,s0,s1):\sigma}

(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,

[[bf{nat}]]:=N\bot

(the natural numbers with a bottom element adjoined, with the flat ordering)

[[\sigma\to\tau]]

is interpreted as the domain of Scott-continuous functions from

[[\sigma]]

to

[[\tau]]

, with the pointwise ordering.

x1:\sigma1,...,xn:\sigman

is interpreted as the product

[[\sigma1]] x ... x [[\sigman]]

\Gamma\vdashx:\sigma

are interpreted as continuous functions

[[\Gamma]]\to[[\sigma]]

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.

References

. John C. Mitchell . Foundations for Programming Languages . 1996 . 9780262133210 . The Language PCF . https://theory.stanford.edu/~jcm/books/fpl-chap2.ps .

External links