Content deleted Content added
Citation bot (talk | contribs) m Updating page numbers after recent improvement to Template:Cite book. Formatted: pages. |
Add section: Syntax |
||
Line 2:
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.
==Syntax==
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 combinator|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:
: <math>
\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
}
</math>
: ('''nat'''s will be interpreted as booleans here with a convention like zero denoting truth, and any other number denoting falsity)
==External links==
| |||