Definierbare Funktionen im ...-Kalkül mit Typen.
Denotational aspects of untyped normalization by evaluation
We show that the standard normalization-by-evaluation construction for the simply-typed -calculus has a natural counterpart for the untyped -calculus, with the central type-indexed logical relation replaced by a “recursively defined” invariant relation, in the style of Pitts. In fact, the construction can be seen as generalizing a computational-adequacy argument for an untyped, call-by-name language to normalization instead of evaluation.In the untyped setting, not all terms have normal forms,...
Denotational aspects of untyped normalization by evaluation
We show that the standard normalization-by-evaluation construction for the simply-typed λβη-calculus has a natural counterpart for the untyped λβ-calculus, with the central type-indexed logical relation replaced by a “recursively defined” invariant relation, in the style of Pitts. In fact, the construction can be seen as generalizing a computational-adequacy argument for an untyped, call-by-name language to normalization instead of evaluation.In the untyped setting, not all terms have normal...
Domain-free -calculus
Domain-Free λµ-Calculus
We introduce a domain-free λµ-calculus of call-by-value as a short-hand for the second order Church-style. Our motivation comes from the observation that in Curry-style polymorphic calculi, control operators such as callcc-operators cannot, in general, handle correctly the terms placed on the control operator's left, so that the Curry-style system can fail to prove the subject reduction property. Following the continuation semantics, we also discuss the notion of values in classical system,...
Easy lambda-terms are not always simple
A closed λ-term M is easy if, for any other closed term N, the lambda theory generated by M = N is consistent. Recently, it has been introduced a general technique to prove the easiness of λ-terms through the semantical notion of simple easiness. Simple easiness implies easiness and allows to prove consistency results via construction of suitable filter models of λ-calculus living in the category of complete partial orderings: given a simple easy term M and an arbitrary closed term N, it is possible...
Easy lambda-terms are not always simple
A closed λ-term M is easy if, for any other closed term N, the lambda theory generated by M = N is consistent. Recently, it has been introduced a general technique to prove the easiness of λ-terms through the semantical notion of simple easiness. Simple easiness implies easiness and allows to prove consistency results via construction of suitable filter models of λ-calculus living in the category of complete partial orderings: given ...
Ein algebraischer Beweis für das Church-Rosser-Theorem.
Functional representation of preiterative/combinatory formalism
Functorial polymorphism and semantic parametricity
Generalized E-algebras via λ-calculus I
An R-algebra A is called an E(R)-algebra if the canonical homomorphism from A to the endomorphism algebra of the R-module , taking any a ∈ A to the right multiplication by a, is an isomorphism of algebras. In this case is called an E(R)-module. There is a proper class of examples constructed in [4]. E(R)-algebras arise naturally in various topics of algebra. So it is not surprising that they were investigated thoroughly in the last decades; see [3, 5, 7, 8, 10, 13, 14, 15, 18, 19]. Despite...
Intersection Types for lambda^{gtz}-calculus
Lambda-calcul, évaluation paresseuse et mise en mémoire
Le lambda-calcul du second ordre
Les -types du système
Nous démontrons dans ce papier que les types du système habités uniquement par des -termes (les -types) sont à quantificateur positif. Nous présentons ensuite des conséquenses de ce résultat et quelques exemples.
Les I-types du système
We prove in this paper that the types of system inhabited uniquely by λI-terms (the I-types) have a positive quantifier. We give also consequences of this result and some examples.
Les types de données syntaxiques du système
Nous présentons dans ce papier une définition purement syntaxique des types entrées et des types sorties du système . Nous définissons les types de données syntaxiques comme étant des types entrées et sorties. Nous démontrons que les types à quantificateurs positifs sont des types de données syntaxiques et qu’un type entrée est un type sortie. Nous imposons des restrictions sur la règle d’élimination des quantificateurs pour démontrer qu’un type sortie est un type entrée.
Les types de données syntaxiques du système
We give in this paper a purely syntactical definition of input and output types of system . We define the syntactical data types as input and output types. We show that any type with positive quantifiers is a syntactical data type and that an input type is an output type. We give some restrictions on the ∀-elimination rule in order to prove that an output type is an input type.
Logic and functional programming by retractions
Mengentheoretische Modelle des ...K-Kalküls.