scientific article; zbMATH DE number 4051567
[For the entire collection see Zbl 0632.00018.] In the past few years there has been a lot of interest in the semantics of second order lambda calculus. After the first model constructions (Closure Model; Finitary Retraction Model), \textit{K. Bruce}, \textit{A. Meyer} and \textit{J. Mitchell} [``The semantics of second order lambda- calculus, Inf. Comput. (to appear)] have given a general notion of model, together with a proof of soundness and, under the assumption that every type is not empty, completeness. Shortly afterwards, other models were discovered: the Finitary Projection Model, which is based on early ideas by Scott, the PER (or ``modest) Model; the Qualitative Domains Model. Although these models differ in important ways, they all agree in being extensional models: the (\(\eta)\) rule (that is: \(\lambda x:\alpha.Mx=M\) and \(\Lambda t.Mt=M\), for x and t not free in M) is sound in all of them. By this, in each type, every function has only one representative. In the first order type-free calculus, on the other hand, no one ever doubted that (\(\eta)\) was a very strong requirement, and much effort was devoted to build non-extensional models, that is structures in which only a weak extensionality property (expressed by the (\(\xi)\) rule) holds. Models like \(P\omega\), \(D_ A\), \(T^{\omega}\), are all non-extensional \(\lambda\)-models. As for the (first order) simply typed \(\lambda\)- calculus, a categorical characterization of non-extensional models is given by \textit{S. Hayashi} [Theor. Comput. Sci. 41, 95-104 (1985; Zbl 0592.03010)] (semi (or weak) cartesian closed categories); the author [``Categorical models for types and type-free non-extensional lambda- calculus, Preprint, Pisa (1986)] has shown how to obtain a wCCC from the Ideal Model by \textit{D. MacQueen}, \textit{G. Plotkin}, and \textit{R. Sethi} [Inf. Control 71, 95-130 (1986; Zbl 0636.68016)] thus obtaining a ``concrete non-extensional model of the simply typed calculus. The main aim of this paper, thus, is to determine a non-extensional, second order lambda model, by ``generalizing, in a sense, the Ideal Model.
- The semantics of second-order lambda calculus
- Semantics of the second order lambda calculus
- scientific article; zbMATH DE number 3882403
- An elementary fragment of second-order lambda calculus
- scientific article; zbMATH DE number 3889500
- Models of the lambda calculus
- Ordered models of the lambda calculus
- Models of the lambda calculus: an introduction
- On the semantics of second order lambda calculus: From bruce-meyer-mitchell models to hyperdoctrine models and vice-versa
- The Intensional Lambda Calculus
- Recursion over realizability structures
- Categorical models of polymorphism
- On nonstandard models in higher order logic
- Pre-adjunctions in order enriched categories
- Semantics of the second order lambda calculus
- The theory of semi-functors
- Comparing models of the non-extensional typed lambda-calculus
- On the semantics of second order lambda calculus: From bruce-meyer-mitchell models to hyperdoctrine models and vice-versa
- The semantics of second-order lambda calculus
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787977)