Type theory | Lambda calculus | Proof theory

Pure type system

In the branches of mathematical logic known as proof theory and type theory, a pure type system (PTS), previously known as a generalized type system (GTS), is a form of typed lambda calculus that allows an arbitrary number of sorts and dependencies between any of these. The framework can be seen as a generalisation of Barendregt's lambda cube, in the sense that all corners of the cube can be represented as instances of a PTS with just two sorts. In fact, Barendregt (1991) framed his cube in this setting. Pure type systems may obscure the distinction between types and terms and collapse the type hierarchy, as is the case with the calculus of constructions, but this is not generally the case, e.g. the simply typed lambda calculus allows only terms to depend on terms. Pure type systems were independently introduced by Stefano Berardi (1988) and Jan Terlouw (1989). Barendregt discussed them at length in his subsequent papers. In his PhD thesis, Berardi defined a cube of constructive logics akin to the lambda cube (these specifications are non-dependent). A modification of this cube was later called the L-cube by Geuvers, who in his PhD thesis extended the Curry–Howard correspondence to this setting. Based on these ideas, Barthe and others defined classical pure type systems (CPTS) by adding a double negation operator. Similarly, in 1998, Tijn Borghuis introduced modal pure type systems (MPTS). Roorda has discussed the application of pure type systems to functional programming; and Roorda and Jeuring have proposed a programming language based on pure type systems. The systems from the lambda cube are all known to be strongly normalizing. Pure type systems in general need not be, for example System U from Girard's paradox is not. (Roughly speaking, Girard found pure systems in which one can express the sentence "the types form a type".) Furthermore, all known examples of pure type systems that are not strongly normalizing are not even (weakly) normalizing: they contain expressions that do not have normal forms, just like the untyped lambda calculus. It is a major open problem in the field whether this is always the case, i.e. whether a (weakly) normalizing PTS always has the strong normalization property. This is known as the Barendregt–Geuvers–Klop conjecture (named after Henk Barendregt, , and Jan Willem Klop). (Wikipedia).

Video thumbnail

The big mathematics divide: between "exact" and "approximate" | Sociology and Pure Maths | NJW

Modern pure mathematics suffers from a major schism that largely goes unacknowledged: that many aspects of the subject are parading as "exact theories" when in fact they are really only "approximate theories". In this sense they can be viewed either as belonging more properly to applied ma

From playlist Sociology and Pure Mathematics

Video thumbnail

What Are Reactive Systems?

Reactive Systems use a high-performance software architecture. They are resilient under stress, and their reactive design allows them to scale elastically to meet demand. The reactive design approach allows the creation of more complex, more flexible systems and forms the basis for some of

From playlist Software Engineering

Video thumbnail

On the Setoid Model of Type Theory - Erik Palmgren

Erik Palmgren University of Stockholm October 18, 2012 For more videos, visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Reconsidering `functions' in modern mathematics | Arithmetic and Geometry Math Foundations 43

The general notion of `function' does not work in mathematics, just as the general notions of `number' or `sequence' don't work. This video explains the distinction between `closed' and `open' systems, and suggests that mathematical definitions should respect the open aspect of mathemat

From playlist Math Foundations

Video thumbnail

Discrete-Time Dynamical Systems

This video shows how discrete-time dynamical systems may be induced from continuous-time systems. https://www.eigensteve.com/

From playlist Data-Driven Dynamical Systems

Video thumbnail

The Scientific Method and the question of "Infinite Sets" | Sociology and Pure Maths| N J Wildberger

Let's get some kind of serious discussion going about the differences in methodology and philosophy between the sciences and mathematics, and how these differences manifest themselves in the attitude towards the logical foundations of mathematics. In particular we look at a bulwark notio

From playlist Sociology and Pure Mathematics

Video thumbnail

Type Systems I - Vladimir Voevodsky

Vladimir Voevodsky Institute for Advanced Study November 28, 2012 For more videos, visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Natural Models of Type Theory - Steve Awodey

Steve Awodey Carnegie Mellon University; Member, School of Mathematics March 28, 2013 For more videos, visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

PureScript: Tomorrow’s JavaScript Today

It's almost impossible to imagine the web without JavaScript. And as professional web developers, it's almost heresy to do so. But despite 20 years of maturity and a truly frantic pace of innovation, JavaScript isn't just the sea we swim in, it's also the shark trying to bite us. JavaScrip

From playlist JavaScript

Video thumbnail

Stanford Seminar - Concatenative Programming: From Ivory to Metal

EE380: Computer Systems Colloquium Seminar Concatenative Programming: From Ivory to Metal Speaker: Jon Purdy, Microsoft Concatenative programming is a relatively new programming paradigm built on a simple yet powerful tool: function composition. In this talk I will give an overview of con

From playlist Stanford EE380-Colloquium on Computer Systems - Seminar Series

Video thumbnail

PROG2006: Programming: Terminology 2/2

PROG2006: Advanced Programming Introduction Programming Terminology continued.

From playlist PROG2006 - Programming

Video thumbnail

EmberConf 2021 - Keep It Local by Chris Krycho

Keep It Local by Chris Krycho What do Steve McConnell’s variable scoping guidelines in Code Complete 2, pure functional programming, the data ownership system in Rust, classical object-oriented programming, the actor model in Erlang, and autotracking in Glimmer all have in common? Every o

From playlist EmberConf 2021

Video thumbnail

SHM - 16/01/15 - Constructivismes en mathématiques - Thierry Coquand

Thierry Coquand (Université de Gothenburg), « Théorie des types et mathématiques constructives »

From playlist Les constructivismes mathématiques - Séminaire d'Histoire des Mathématiques

Video thumbnail

Brave New World: Tales of PureScript and Haskell in Production

The rumours are true. Writing code in purely functional languages tends to produce code that is much easier to read, modify and reason about. This talk examines how an experienced Scala team transitioned into writing production code using PureScript in AWS lambda, and services using Haskel

From playlist Software Development

Video thumbnail

Lec 34 | MIT 3.091 Introduction to Solid State Chemistry

Two-component Phase Diagrams: Limited Solid Solubility Lever Rule View the complete course at: http://ocw.mit.edu/3-091F04 License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/terms More courses at http://ocw.mit.edu

From playlist MIT 3.091 Introduction to Solid State Chemistry, Fall 2004

Video thumbnail

18. Weber on Traditional Authority

Foundations of Modern Social Thought (SOCY 151) We return to Weber's idea of domination, Herrschaft. Herrschaft has been translated into English as "authority" and as "domination." The translation into domination highlights the elements of power and legitimacy that are co-mingled in t

From playlist Foundations of Modern Social Theory with Iván Szelényi

Video thumbnail

PROG2006: Haskell - Functor

PROG2006 Advanced Programming Haskell - state, introduction Identity element Associative, Commutative operations Functor

From playlist PROG2006 - Programming

Video thumbnail

ArrrrCamp 2014- Functional Programming for Rubyists

By, Arne Brasseur Slides @ http://arnebrasseur.net/talks/arrrrcamp2014/#/ Ruby isn't exactly know for being a functional programming language, but neither is it known for not being a functional programming language. With lambdas, blocks, and Matz himself citing LISP as a major influenc

From playlist ArrrrCamp 2014

Video thumbnail

Introduction to Differential Equations

Please Subscribe here, thank you!!! https://goo.gl/JQ8Nys Introduction to Differential Equations - The types of differential equations, ordinary versus partial. - How to find the order of a differential equation.

From playlist Differential Equations

Related pages

Normal form (abstract rewriting) | Type theory | Structure (mathematical logic) | Curry–Howard correspondence | Mathematical logic | System U | Lambda-mu calculus | Calculus of constructions | Double negation | Lambda cube | Simply typed lambda calculus | Typed lambda calculus | Proof theory