Questions tagged [type-theory]
formal systems to specify properties of objects
2
votes
0answers
18 views
Is the expression (λx.xx)(λy.y) typeable in the following system?
We are given a simple functional language:
$ e ::= x | n | e_{1}e_{2}|\lambda(x:\tau).e$
with types:
$\tau ::= \text{int} | \tau_{1} \rightarrow \tau_{2}| \tau_{1} \land \tau_{2} $
Is the ...
1
vote
0answers
29 views
Substituting a term for a variable in a context
At this link you can read Nicola Gambino's slides on one way to approach the formal syntax of Martin-Löf dependent type theory. (They are concise and very readable.)
On slide 10, he gives a standard ...
2
votes
3answers
58 views
How is functional property guaranteed in type theory when function type is defined?
I understand that functions are not defined in type theory the same way they are defined in set theory, hence functional property is not directly defined when defining function type in type theory. ...
1
vote
0answers
35 views
Is it possible to write a fully-decidable type system for the J language?
I'm experimenting with the J array language, a dynamically-typed array language with mutable assignment, subtyping, and function overloading (just like traditional APL).
It is unclear to me whether ...
1
vote
0answers
32 views
Design considerations of datatypes in early programming languages like C
Although type theory originated (e.g. already discussed by Russell in 1910s) much earlier than programming languages, I have this feeling that languages such as C considered type-checking from a very ...
0
votes
0answers
29 views
Confusion regarding algebraic specification of the queue
I was given the following question in the test where I had to write the algebraic specification and its axioms based on below-defined operations:
...
0
votes
1answer
33 views
Find typing derivation of STLC term with reference types
The problem is to find the typing derivation of a term of the call-by-value STLC extended with reference types. The evaluation and typing rules for this language is given in Types and Programming ...
12
votes
5answers
1k views
Is there any use case for the bottom type as a function parameter type?
If a function has return type of ⊥ (bottom type), that means it never returns. It can for example exit or throw, both fairly ordinary situations.
Presumably if a function had a parameter of type ⊥ it ...
6
votes
1answer
46 views
Reversing an application of `sym` to `ua` and `isoToEquiv` in cubical type theory
I am proving a kind of structure invariance principle for magmas in Cubical Type Theory with the Agda/Cubical library. This is done by constructing a path between two simple magmas and then ...
6
votes
1answer
83 views
Can all regular tree types be expressed as $\mu$ types?
In "Types and Programming Languages", Pierce gives a translation from recursive types ($\mu$ types) to types expressed as regular trees: possibly infinite trees, but with finitely many distinct ...
2
votes
1answer
30 views
Relationship between dependent sum type and dependent product type?
Since dependent sum type ($\sum_{n\in \mathbb{N}} P(n) $) is interpreted as ($\exists n\in \mathbb{N}:P(n) $) and dependent product type ($\prod_{n\in \mathbb{N}} P(n)$) is interpreted as ($\forall n\...
3
votes
1answer
63 views
What is the relation between syntax and type theory?
Type theory and syntax are similar, in that they are inductive rules that determine whether a particular string of symbols is "correctly specified" in some sense.
There is a difference between ...
6
votes
1answer
82 views
How do we know $\neg \neg LEM$ isn't provable in MLTT?
I've been trying (fruitlessly) to prove something which I now know is not provable. Take the following definitions:
$$LEM \equiv \prod_{A : Type} \neg A \vee A$$
$$DNE \equiv \prod_{A : Type} \neg \...
1
vote
1answer
37 views
Isoecursive Types When to Fold and Unfold
I'm trying to implement recursive types into my programming language. I've implemented extensible rows and was hoping to add some recursive typing in order to get something like ...
0
votes
0answers
98 views
Definition of M-type in type theory
According to nLab, M-types are the dual of W-types. What are the introduction and elimination rules for M-types?
Edit: For example, the formation/introduction/elimination rules for W-types are:
$$\...
3
votes
1answer
60 views
How to statically type polymorphic lambdas using hindley milner style type inference
I am playing with a simple implicitly typed functional language and have implemented type checking using a Hindley Milner style system. In order to guide code generation, I want to tag each term with ...
0
votes
1answer
73 views
Is it possible to interpret some Martin-Löf types as abelian monoids in such a way that any abelian monoid can be represented as a type?
For instance, I can interpret the unit type as the trivial monoid with one element. Non-dependent pairs $A \times B$ can be interpreted as the direct sum $A ⊕ B$ when $A$ and $B$ can both be ...
3
votes
1answer
50 views
Meaning of the “why not” modality from linear type theory?
In linear type theory there is a modality written ! where !T can be read as "infinite copies of ...
5
votes
3answers
77 views
How exactly do we define parametric polymorphism?
My naive distinction between parametric polymorphism and ad-hoc polymorphism, is that:
In parametric polymorphism, the type is given as a variable: (pseudocode)
Function f: <.Type T> T $\to$...
2
votes
0answers
34 views
How can one flip a stream using corecursion
Following is the definition of codata stream:
codata Stream where
hd : Stream −> A
tl : Stream −> Stream
For simplicity I assume I have just a ...
2
votes
0answers
65 views
An Alternative History of Haskell: being lazy without class?
[The q is a play on the title of this 2007 survey of Haskell.]
tl;dr I have a couple of connected questions about Haskell's overloading mechanisms. I'll ask first then explain why. I'm looking at the ...
5
votes
2answers
75 views
Identity types and universes
Let us consider Martin-Löf type theory with a cumulative hierarchy of universes
$$
\mathcal{U}_0\colon\mathcal{U}_1\colon\ldots
$$
If $A, B\colon \mathcal{U}_i$, we can form an identity type $A=_{\...
0
votes
0answers
25 views
If you can have cyclic base types, or if they need to be infinite types
I am confused how to properly think about classes of classes. Basically, you can have a dog "filo" which is an instance of the dog "class". But the dog class is itself not an instanceof of "animal", ...
2
votes
1answer
130 views
Dependent type system with different computation model
There exist various Turing-equivalent models of computation, such as lambda calculus, Turing machines, or register machines.
It seems that dependent type systems (like Coq, Agda, Idris, homotopy type ...
5
votes
1answer
594 views
Where are C++ templates inside of the lambda cube?
C++ templates have type variables and can express lambdas, so they must have System F embedded. But is that exactly where they are located in the lambda cube? Can C++ templates produce new types or ...
3
votes
1answer
48 views
What are different ways to provide a semantics to a language?
Suppose you have 1. a grammar for terms of a language; 2. type-assignment rules, 3. a set of reduction rules. You want to prove that your language is adequate for mathematical reasoning. If I ...
2
votes
0answers
31 views
Question about let syntax in type systems
I'm on the Wikipedia page for Hindley-Milner type systems, on the section about "let polymorphism": https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system#Let-polymorphism
I'm a bit ...
3
votes
1answer
40 views
T&PL: Language grammar with terms
I'm autodidacting Pierce's Types and Programming Languages. On page 27 he states a definition for "terms, concretely" in constructing a language of terms, thus:
For each natural number $i$, define a ...
1
vote
1answer
50 views
What is the difference between a Top type and a Unit type
Wikipedia defines a Top type: (edited for readability)
The Top type [...] is the universal supertype, as all other types in any given type system are subtypes of Top
However, the article goes on ...
1
vote
0answers
25 views
The underlying type theory of HOL/Isabelle
Is there a good source on the type theory of HOL/Isabelle/other HOL-based LCF-style theorem provers?
0
votes
0answers
29 views
Computational type theorists: how do you compare terms for equality here?
I am attempting to implement Simple Type Theory in the language D. How do you compare subterms to a term $R$ for the sake of computing the covering abstractors of $R$ in $M$?
By reference (class ...
3
votes
1answer
276 views
Drawbacks of adding type equality to 1ML
In the 1ML – Core and Modules United (F-ing First-Class Modules) paper, the author gives the following example for why module types do not form a lattice under subtyping:
...
4
votes
1answer
166 views
Typing rule for binding groups
In "Typing Haskell in Haskell", by Mark P. Jones, is provided a sort of haskell-like specification for typing Haskell. As stated in this paper, binding groups is a area "neglected in most theoretical ...
0
votes
0answers
47 views
Mathematical resource material accompanying TAPL
I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types.
Prior to this chapter I found the book challenging but ...
3
votes
1answer
65 views
Is there a generally accepted name for creating types that select a subset of other types?
Tl;Dr;
Given:
type A = { int: foo, int: bar }
type B = select foo from A
What is the name of the typing relationship between A and B?
What is the name of the ...
1
vote
0answers
25 views
Summary of types of equivalence and equality in type theory, with notations and examples
Coming from non-computer science background, I am trying to understand the different types of equivalence and equality usually used in type theory. Ideally, I am looking for clear definitions and ...
4
votes
1answer
87 views
Roadmap to formal verification
I would like to learn about different approaches to formal verification of software programs that goes beyond what Wikipedia has to offer. Ideally one would not only get an overview but also ...
6
votes
2answers
172 views
LET REC recursive expression static typing rule
I'm taking a programming languages course and had a question regarding the typing rules for a recursive let rec expression in a static typing system.
To be more ...
2
votes
3answers
283 views
Soundness and completeness w.r.t. programming languages
I'm studying programming languages (more specifically type systems) and came across a concept I couldn't quite wrap my head around: soundness and completeness.
I'm taking a class, and according to my ...
0
votes
0answers
35 views
Composition of compostion as a functor
"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type ...
1
vote
1answer
45 views
PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?
In Practical Foundations for Programming
Languages, on page 138 (page 156 of the pdf), it says:
Requiring solutions to all type equations may seem suspicious, because
we know by Cantor’s Theorem ...
1
vote
0answers
34 views
Propositional extentionality in the lean theorem prover?
Propositional extentionality in the lean theorem prover is stated as the following axiom:
axiom proptext {a b : Prop} : (a $\iff$ b) \to a = b
My confusion about this is as follows: Previously I’...
1
vote
0answers
45 views
Type theory based automated theorem prover?
I know that there exist type theory based proof-checker, and I know that there are logic/sequent-calculus based automated theorem provers.
But I haven’t heard of a type-theory based automated theorem ...
1
vote
1answer
58 views
Curry-howard isomorphism in object oriented programming languages
I want to get a better intuition for the curry howard isomorphism, and my intuition is mainly based on object oriented programming languages like JavaScript.
So as an example, I am going to formalize ...
1
vote
2answers
75 views
What is the type signature of a Turing Machine?
Maybe my question is a bad question, but if it is, I want to know eactly how it is a bad question.
Suppose we have some Turing machien $M$ that takes as input a natural number $n$ in the form of a ...
0
votes
1answer
66 views
Bounded Quantification: Full F<: intuition
I'm currently looking into Chapter 26 of Types and Programming Languages and am a bit confused by the "intuition" for Full F<: (p. 395):
A type T = ∀X<:T1.T2 describes a collection of ...
2
votes
1answer
74 views
Does co-inductive and co-recursive types also have their recursors?
I'm new to type theory, and recently read introductory materials where dependent type are discussed. One of my friend asked me, "Those dependent types are having recursors & 'inductors'(dependent ...
3
votes
1answer
43 views
Multiplicative Pure Type Systems
All the references about Pure Type Systems I know consider only systems that allow to recover natural deduction systems with additive rules. Is there any variant that allows it to recover natural ...
3
votes
2answers
88 views
Are Bad churches inhabited?
In type theory, some inductively defined data types allow you to prove absurdity. For example
...
1
vote
2answers
49 views
How can MLTT etc encode computability?
I am recently thinking about proving the undecidability of some problem. This problem has been formalized in Coq and by staring at it, people including me think "for sure" this is undecidable. "For ...
