1,720,975 research outputs found
Mechanizing type environments in weak HOAS
Full text linkWe provide a paradigmatic case study, about the formalization of System F<:'s type language in the proof assistant Coq. Our approach relies on weak HOAS, for the sake of producing a readable and concise representation of the object language. Actually, we present and discuss two encoding strategies for typing environments which yield a remarkable influence on the whole formalization. Then, on the one hand we develop System F<:'s metatheory, on the other hand we address the equivalence of the two approaches internally to Coq
A certified, corecursive implementation of exact real numbers
No full textAbstractWe implement exact real numbers in the logical framework Coq using streams, i.e., infinite sequences, of digits, and characterize constructive real numbers through a minimal axiomatization. We prove that our construction inhabits the axiomatization, working formally with coinductive types and corecursive proofs. Thus we obtain reliable, corecursive algorithms for computing on real numbers
Plug and Play the Theory of Contexts in Higher-Order abstract Syntax
No full textWe illustrate the pragmatic aspects of the Theory of Contexts, recently proposed as a general approach for reasoning on languages with binders in Higher-Order Abstract Syntax, through two working examples: λ-calculus and Abadi and Cardelli’s impς-calculus
Internal Adequacy of Bookkeeping in Coq
No full textWe focus on a common problem encountered in encoding and formally reasoning about a wide range of formal systems, namely, the representation of a typing environment. In particular, we apply the bookkeeping technique to a well-known case study (i.e., System F<:'s type language), proving in Coq an internal correspondence with a more standard representation of the typing environment as a list of pairs. In order to keep the signature readable and concise, we make use of higher-order abstract syntax (HOAS), which allows us to deal smoothly with the representation of the universal binder of System F<: type language
A protoype-based approach to object evolution
Full text linkWe investigate, in the context of functional prototype-based languages, a calculus of objects which might extend themselves upon receiving a message, a capability referred to by Cardelli as a self-inflicted operation. We present a sound type system for this calculus which guarantees that evaluating a well-typed expression will never yield a message-not-found runtime error. The resulting calculus is an attempt towards the definition of a language combining the safety advantage of static type checking with the flexibility found in dynamically typed languages
- …
