From Wikipedia, the free encyclopedia
A typed functional language
In
computer science
,
Programming Computable Functions
(PCF) is a
typed
functional language
introduced by
Gordon Plotkin
in 1977,
[1]
based on previous unpublished material by
Dana Scott
.
[note 1]
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
.
[2]
However, since Milner's model was essentially based on the syntax of PCF it was considered less than satisfactory.
[3]
The first two fully abstract models not employing syntax were formulated during the 1990s. These models are based on
game semantics
[4]
[5]
and
Kripke logical relations
.
[6]
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.
[7]
Syntax
[
edit
]
The
types
of PCF are inductively defined as
- nat
is a type
- For types
σ
and
τ
, there is a 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:
- (
nat
s will be interpreted as booleans here with a convention like zero denoting truth, and any other number denoting falsity)
Semantics
[
edit
]
Denotational semantics
[
edit
]
A relatively straightforward semantics for the language is the
Scott model
. In this model,
- Types are interpreted as certain
domains
.
- (the natural numbers with a bottom element adjoined, with the flat ordering)
- is interpreted as the domain of
Scott-continuous
functions from
to
, with the pointwise ordering.
- A context
is interpreted as the product
- Terms in context
are interpreted as continuous functions
- 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.
[4]
: 293
Notes
[
edit
]
- ^
"PCF is a programming language for computable functions, based on LCF, Scott’s logic of computable functions."
[1]
Programming Computable Functions
is used by (
Mitchell 1996
). It is also referred to as
Programming with Computable Functions
or
Programming language for Computable Functions
.
References
[
edit
]
- ^
a
b
Plotkin, Gordon D.
(1977).
"LCF considered as a programming language"
(PDF)
.
Theoretical Computer Science
.
5
(3): 223?255.
doi
:
10.1016/0304-3975(77)90044-5
.
- ^
Milner, Robin
(1977).
"Fully abstract models of typed λ-calculi"
(PDF)
.
Theoretical Computer Science
.
4
: 1?22.
doi
:
10.1016/0304-3975(77)90053-6
.
hdl
:
20.500.11820/731c88c6-cdb1-4ea0-945e-f39d85de11f1
.
- ^
Ong, C.-H. L. (1995).
"Correspondence between Operational and Denotational Semantics: The Full Abstraction Problem for PCF"
. In Abramsky, S.; Gabbay, D.; Maibau, T. S. E. (eds.).
Handbook of Logic in Computer Science
. Oxford University Press. pp. 269?356. Archived from
the original
on 2006-01-07
. Retrieved
2006-01-19
.
- ^
a
b
Hyland, J. M. E. & Ong, C.-H. L. (2000).
"On Full Abstraction for PCF"
.
Information and Computation
.
163
(2): 285?408.
doi
:
10.1006/inco.2000.2917
.
- ^
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
.
{{
cite journal
}}
: CS1 maint: multiple names: authors list (
link
)
- ^
O'Hearn, P. W. & Riecke, J. G (1995).
"Kripke Logical Relations and PCF"
.
Information and Computation
.
120
(1): 107?116.
doi
:
10.1006/inco.1995.1103
.
- ^
Loader, R. (2001).
"Finitary PCF is not decidable"
.
Theoretical Computer Science
.
266
(1?2): 341?364.
doi
:
10.1016/S0304-3975(00)00194-8
.
External links
[
edit
]