•A program logic for fresh name generation.•A logic to reason about the nu-calculus (an extension of the lambda-calculus).•Introduces a “derived from” concept with which to restrict universal ...quantification.•Extends modal quantification with the ability to name the state.•Proves soundness of the program logic rules and axioms.
We present a program logic for Pitts and Stark's ν-calculus, an extension of the call-by-value simply-typed λ-calculus with a mechanism for the generation of fresh names. Names can be compared for equality and inequality, producing programs with subtle observable properties. Hidden names produced by interactions between generation and abstraction are captured logically with a second-order quantifier over type contexts. We illustrate usage of the logic through reasoning about well-known difficult cases from the literature.
This handbook with exercises reveals in formalisms, hitherto mainly used for hardware and software design and verification, unexpected mathematical beauty. The lambda calculus forms a prototype ...universal programming language, which in its untyped version is related to Lisp, and was treated in the first author's classic The Lambda Calculus (1984). The formalism has since been extended with types and used in functional programming (Haskell, Clean) and proof assistants (Coq, Isabelle, HOL), used in designing and verifying IT products and mathematical proofs. In this book, the authors focus on three classes of typing for lambda terms: simple types, recursive types and intersection types. It is in these three formalisms of terms and types that the unexpected mathematical beauty is revealed. The treatment is authoritative and comprehensive, complemented by an exhaustive bibliography, and numerous exercises are provided to deepen the readers' understanding and increase their confidence using types.
In a recent paper, a realizability technique has been used to give a
semantics of a quantum lambda calculus. Such a technique gives rise to an
infinite number of valid typing rules, without giving ...preference to any subset
of those. In this paper, we introduce a valid subset of typing rules, defining
an expressive enough quantum calculus. Then, we propose a categorical semantics
for it. Such a semantics consists of an adjunction between the category of
distributive-action spaces of value distributions (that is, linear combinations
of values in the lambda calculus), and the category of sets of value
distributions.
Effectful program distancing Dal Lago, Ugo; Gavazzo, Francesco
Proceedings of ACM on programming languages,
01/2022, Volume:
6, Issue:
POPL
Journal Article
Peer reviewed
Open access
Semantics is traditionally concerned with program equivalence, in which all pairs of programs which are
not
equivalent are treated the same, and simply dubbed as incomparable. In recent years, ...various forms of program
metrics
have been introduced such that the distance between non-equivalent programs is measured as an element of an appropriate quantale. By letting the underlying quantale
vary
as the type of the compared programs become more complex, the recently introduced framework of differential logical relations allows for a new contextual form of reasoning. In this paper, we show that all this can be generalised to
effectful
higher-order programs, in which not only the
values
, but also the
effects
computations produce can be appropriately distanced in a principled way. We show that the resulting framework is flexible, allowing various forms of effects to be handled, and that it provides compact and informative judgments about program differences.
We develop metatheory of the Lambda calculus in Constructive Type Theory, using a first-order presentation with one sort of names for both free and bound variables and without identifying terms up to ...α-conversion. Concerning β-reduction, we prove the Church–Rosser theorem and the Subject Reduction theorem for the system of assignment of simple types. It is thereby shown that this concrete approach allows for gentle full formalisation, thanks to the use of an appropriate notion of substitution due to A. Stoughton. The whole development has been machine-checked using the system Agda.
Light chain amyloidosis is one of the most common forms of systemic amyloidosis. The disease is caused by the misfolding and aggregation of immunoglobulin light chains to insoluble fibrils. These ...fibrils can deposit in different tissues and organs such as heart and kidney and cause organ impairments that define the clinical presentation. In this study, we present an overview of IGLV-IGLJ and IGLC germline utilization in 85 patients classified in three clinically important subgroups with dominant cardiac, renal as well as cardiac and renal involvement. We found that IGLV3 was the most frequently detected IGLV-family in patients with dominant cardiac involvement, whereas in renal patients IGLV1 were most frequently identified. For patients with dominant heart and kidney involvement IGLV6 was the most frequently detected IGLV-family. In more detailed analysis IGLV3-21 was observed as the most dominant IGLV-subfamily for patients with dominant heart involvement and IGLV1-44 as the most frequent IGLV-subfamily in the group of patients with dominant kidney involvement. For patients with dominant heart and kidney involvement IGLV6-57 was the most frequently detected IGLV-subfamily. Additionally, we were able to show an exclusive linkage between IGLJ1 and IGLC1 as well as between IGLJ2 and IGLC2 in the fully assembled IGL mRNA.
We propose a way to unify two approaches of non-cloning in quantum lambda-calculi: logical and algebraic linearities. The first approach is to forbid duplicating variables, while the second is to ...consider all lambda-terms as algebraic-linear functions. We illustrate this idea by defining a quantum extension of first-order simply-typed lambda-calculus, where the type is linear on superposition, while allows cloning base vectors. In addition, we provide an interpretation of the calculus where superposed types are interpreted as vector spaces and non-superposed types as their basis.
PDF
