The Principal Type-Scheme of an Object in Combinatory Logic

Categorical logic and type theory

Categorical logic and type theory by Bart Jacobs, 1999, Elsevier Science edition, in English - 1st ed.

A theory of type polymorphism in programming

The aim of this work is largely a practical one. A widely employed style of programming, particularly in structure-processing languages which impose n…

Syntax and Semantics of Linear Dependent Types

A type theory is presented that combines (intuitionistic) linear types with type dependency, thus properly generalising both intuitionistic dependent type theory and full linear logic. A syntax...

Principal type-schemes for functional programs | Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

As part of the Digital Library's transition to Open Access, new features for researchers are available in the Premium Edition. Click here to learn more.

Categories of Containers

We introduce the notion of containers as a mathematical formalisation of the idea that many important datatypes consist of templates where data is stored. We show that containers have good closure properties under a variety of constructions including the formation of initial algebras and final coalgebras. We also show that containers include strictly positive types and shapely types but that there are containers which do not correspond to either of these. Further, we derive a representation result classifying the nature of polymorphic functions between containers. We finish this paper with an application to the theory of shapely types and refer to a forthcoming paper which applies this theory to differentiable types.

Introduction to Higher-Order Categorical Logic (Cambridge Studies in Advanced Mathematics)

Introduction to higher order catagorical logic by J. Lambek, March 25, 1988, Cambridge University Press edition, Paperback in English

Theorems for free! | Proceedings of the fourth international conference on Functional programming languages and computer architecture

The polymorphic blame calculus integrates static typing, including universal types, with dynamic typing. The primary challenge with this integration is preserving parametricity: even dynamically-typed code should satisfy it once it has been cast to a ...

Syntax and semantics of dependent types

In this chapter we fix a particular syntax for a dependently typed calculus and define an abstract notion of model as well as a general interpretation function mapping syntactical objects to entities in a model. This interpretation function is shown to be sound with respect to the syntax.

generalized algebraic theory in nLab

A generalized algebraic theory (GAT, Cartmell 1978/86) is a dependent type theory in the syntactic sense: There are judgments declaring types and terms of types, where, critically, a type AA declared in context Γ\Gamma is allowed to depend on terms of Γ\Gamma. The only other judgments allowed are of equality (judgemental equality) of pairs of types or terms.

Internal type theory

We introduce categories with families as a new notion of model for a basic framework of dependent types. This notion is close to ordinary syntax and yet has a clean categorical description. We also present categories with families as a generalized algebraic theory. Then we define categories with families formally in Martin-Löf's intensional intuitionistic type theory. Finally, we discuss the coherence problem for these internal categories with families.

A formulation of the simple theory of types

The purpose of the present paper is to give a formulation of the simple theory of types which incorporates certain features of the calculus of λ-conversion. A complete incorporation of the calculus of λ-conversion into the theory of types is impossible if we require that λx and juxtaposition shall retain their respective meanings as an abstraction operator and as denoting the application of function to argument. But the present partial incorporation has certain advantages from the point of view of type theory and is offered as being of interest on this basis (whatever may be thought of the finally satisfactory character of the theory of types as a foundation for logic and mathematics).For features of the formulation which are not immediately connected with the incorporation of λ-conversion, we are heavily indebted to Whitehead and Russell, Hilbert and Ackermann, Hilbert and Bernays, and to forerunners of these, as the reader familiar with the works in question will recognize.The class of type symbols is described by the rules that ı and o are each type symbols and that if α and β are type symbols then (αβ) is a type symbol: it is the least class of symbols which contains the symbols ı and o and is closed under the operation of forming the symbol (αβ) from the symbols α and β.

Categories of Optics

Bidirectional data accessors such as lenses, prisms and traversals are all instances of the same general 'optic' construction. We give a careful account of this construction and show that it extends to a functor from the category of symmetric monoidal categories to itself. We also show that this construction enjoys a universal property: it freely adds counit morphisms to a symmetric monoidal category. Missing in the folklore is a general definition of 'lawfulness' that applies directly to any optic category. We provide such a definition and show that it is equivalent to the folklore profunctor optic laws.

A modal analysis of staged computation | Journal of the ACM

We show that a type system based on the intuitionistic modal logic S4 provides an expressive framework for specifying and analyzing computation stages in the context of typed λ-calculi and functional languages. We directly demonstrate the sense in which ...

Profunctor Optics, a Categorical Update

Optics are bidirectional data accessors that capture data transformation patterns such as accessing subfields or iterating over containers. Profunctor optics are a particular choice of representation supporting modularity, meaning that we can construct accessors for complex structures by combining simpler ones. Profunctor optics have previously been studied only in an unenriched and non-mixed setting, in which both directions of access are modelled in the same category. However, functional programming languages are arguably better described by enriched categories; and we have found that some structures in the literature are actually mixed optics, with access directions modelled in different categories. Our work generalizes a classic result by Pastro and Street on Tambara theory and uses it to describe mixed V-enriched profunctor optics and to endow them with V-category structure. We provide some original families of optics and derivations, including an elementary one for traversals. Finally, we discuss a Haskell implementation.

What you needa know about Yoneda: profunctor optics and the Yoneda lemma (functional pearl) | Proceedings of the ACM on Programming Languages

Profunctor optics are a neat and composable representation of bidirectional data accessors, including lenses, and their dual, prisms. The profunctor representation exploits higher-order functions and higher-kinded type constructor classes, but the ...

Implementing a Hindley-Milner Type System (Part 1) | Blog

First part of a tutorial on implementing a Hindley-Milner type system for a simple, purely functional programming language in Haskell. We go over syntax representation, how the Hindley-Milner type system is defined, polymorphism vs. monomorphism, generalization, and instantiation.