Programming Computable Functions
Typed functional language
title: "Programming Computable Functions" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["programming-languages-created-in-1977", "academic-programming-languages", "educational-programming-languages", "functional-languages", "programming-language-theory", "articles-with-example-code"] description: "Typed functional language" topic_path: "technology/programming-languages" source: "https://en.wikipedia.org/wiki/Programming_Computable_Functions" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Typed functional language ::
::data[format=table title="Infobox programming language"]
| Field | Value |
|---|---|
| name | Programming Computable Functions |
| screenshot | |
| paradigm | functional |
| designers | Dana Scott, |
| Robin Milner, | |
| Gordon Plotkin | |
| released | |
| latest release version | Full Abstraction |
| latest release date | |
| discontinued | Yes |
| file format | |
| website | |
| :: |
| name = Programming Computable Functions | screenshot = | screenshot caption = | sampleCode = | paradigm = functional | family = | designers = Dana Scott, Robin Milner, Gordon Plotkin | released = | latest release version = Full Abstraction | latest release date = | typing = | memory management = | scope = | programming language = | discontinued = Yes | platform = | operating system = | license = | file ext = | file format = | website = | implementations = | dialects = | influenced by = | influenced = In computer science, Programming Computable Functions (PCF), or Programming with Computable Functions, or Programming language for Computable Functions, is a programming language which is typed and based on functional programming, introduced by Gordon Plotkin in 1977, based on prior unpublished material by Dana Scott. It can be considered as 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 data types of PCF are inductively defined as
- nat is a type
- For types σ and τ, there is a function type σ → τ
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:
- Variables (if x : σ is part of a context Γ, then Γ ⊢ x : σ)
- Application (of a term of type σ → τ to a term of type σ)
- λ-abstraction
- The Y fixed point combinator (making terms of type σ out of terms of type σ → σ)
- The successor (succ) and predecessor (pred) operations on nat and the constant 0
- The conditional if with the typing rule: : \frac{ \Gamma ; \vdash ; t ; : \textbf{nat} , \quad \quad \Gamma ; \vdash ; s_0 ; : \sigma , \quad \quad \Gamma ; \vdash ; s_1 ; : \sigma } { \Gamma ; \vdash ; \textbf{if}(t,s_0,s_1) ; : \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,
- Types are interpreted as certain domains.
- [![ \textbf{nat} ]!] := \mathbb{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.
- A context x_1 : \sigma_1, ; \dots, ; x_n : \sigma_n is interpreted as the product [![\sigma_1]!] \times ; \dots ; \times [![\sigma_n]!]
- Terms in context \Gamma ; \vdash ; x ; : ; \sigma are interpreted as continuous functions [![\Gamma]!] ; \to ; [![\sigma]!]
- Variable terms are interpreted as projections
- Lambda abstraction and application are interpreted by making use of the cartesian closed structure of the category of domains and continuous functions
- Y is interpreted by taking the least fixed point of the argument
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.
Notes
References
- {{cite journal |last1=Scott |first1=Dana S. |author1-link=Dana Scott |year=1969 |title=A type-theoretic alternative to CUCH, ISWIM, OWHY |journal=Unpublished Manuscript |url=https://www.cs.cmu.edu/~kw/scans/scott93tcs.pdf
- {{cite book |last1=Mitchell |first1=John C. |author1-link=John C. Mitchell |year=1996 |title=Foundations for Programming Languages |isbn=9780262133210 |chapter=The Language PCF |publisher=MIT Press |chapter-url=https://theory.stanford.edu/~jcm/books/fpl-chap2.ps
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::