Questions tagged [type-inference]
The type-inference tag has no usage guidance.
78
questions
0
votes
1answer
26 views
Inference and Unification algorithm provided to a Unification graph of two expressions
I am trying to unify two expressions given a unification algorithm $unify$ applied to the unification graph of the two expressions. However, I struggle a lot in understanding how exactly the steps of ...
2
votes
1answer
67 views
Type-checking function calls with functional subtyping
I'm relatively new to the topic. Suppose that you want to type-check an expression of the form f(a), i.e. a function call. Assuming that all the declarations are ...
0
votes
0answers
61 views
Consistency of a set of bidirectional typing rules
Main
Is there any way to algorithmically check the consistency of a set of bidirectional typing rules, e.g. the absence of cycles and the uniqueness of the derivation tree? This problem is naturally ...
24
votes
1answer
2k views
What are the strongest known type systems for which inference is decidable?
It's well known that Hindley–Milner type inference (the simply-typed $\lambda$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without ...
2
votes
0answers
35 views
Substitution of monomorphic type variables in generalized Hindley–Milner
I am trying to understand the constraints-based Hindley–Milner type inference algorithm described in the Generalizing Hindley-Milner paper. The function $\text{S}\small{\text{OLVE}}$ is defined as ...
0
votes
0answers
49 views
Is there some place I can find an implementation of the Cartesian Product Algorithm for Type Inference?
Where can I find an implementation of the cartesian product algorithm for type inference? (Preferably in Python/C++, but any language would really do)
I've searched the internet many times but there ...
1
vote
1answer
32 views
Type inference with overloading
I am working on a type system supporting overloading. I have a rough idea of how type inference is usually implemented in such a scenario, but I am wondering how - after type inference is completed - ...
5
votes
2answers
577 views
Does the underlying computational calculus in type theories affect decidability?
I'm looking for a high-level explanation although if that isn't possible or difficult, I'd prefer references to books/papers.
I understand that modern type theory is inspired by Curry-Howard ...
2
votes
1answer
32 views
Type inference with imports
I understand how a type inference algorithm infers types within a single file by building on top of already inferred types and identified constraints (e.g. in the Hindley-Milner type system).
I am ...
2
votes
1answer
52 views
Hindley-Milner system with let expansion
I'm reading these slides that present Hindley-Milner type inference. In the system HM, we have the following let rule:
$\dfrac{\Gamma \vdash t:S \;\; \Gamma,x:S \vdash t':T }{\Gamma \vdash \text{let} ...
2
votes
0answers
76 views
How could 'Complete and Easy Bidirectional Type Checking' handle invariant parameters on type constructors
The paper Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism provides examples for checking if one function type is a subtype of another, which I think demonstrates checking ...
2
votes
2answers
46 views
Are type variables really only used in mathematical conversation about types?
Are type variables really only used in mathematical conversation about types? i.e. are type variables (meta-variables that only contain the type classification label) only exist in proofs for types ...
1
vote
1answer
113 views
What is the difference between $ \alpha \to \alpha $ vs $ \forall \alpha. \alpha \to \alpha$?
I was studying polymorphic types and I was finding the distinction with monomorphic types difficult to pin down (context CS 421). From the course I linked the have the following (vague attempt) at a ...
5
votes
1answer
88 views
What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?
I was learning about polymorphic types but I couldn't understand the notation, can someone explain it means (context cs421 UIUC):
$$ \forall \alpha_1, \dots , \alpha_n . \tau $$
its supposed to be a ...
6
votes
1answer
547 views
Encoding row types
I'm working on a type system with extensible records, similar to ones explained in "A Polymorphic Type System for Extensible Records and Variants - Benedict R. Gaster and Mark P. Jones" and "...
0
votes
0answers
39 views
Inferring the type of (f .) in Haskell
If we have the following in Haskell:
f x y = x + y
:type f
f :: Num a => a -> a -> a
then GHC would report ...
2
votes
0answers
41 views
Real world example of contraction and weakening
Can you provide me a real world example of contraction and weakening in the type system of a popular language like Java, Kotlin, etc.? I heard that Rust has got explicit contraction but I don´t ...
3
votes
0answers
142 views
Type inference for System F-omega
There have been some nice papers about simple type inference for System F: "HMF: Simple Type Inference for First-Class Polymorphism", "Practical type inference for arbitrary-rank types", and "Complete ...
2
votes
0answers
152 views
Proving that the failure of algorithm W implies that the program is not typable
How one does prove that if algorithm W failed for a given program $e$ and context $\Gamma$, then there is no substitution $S$ and type $\tau$ such that $S\Gamma \vdash e : \tau$ ?
The original paper ...
3
votes
0answers
31 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
71 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 ...
3
votes
2answers
112 views
How does a compiler infer a value's type?
From A Swift Tour — The Swift Programming Language (Swift 5):
var myVariable = 42
myVariable = 50
let myConstant = 42
A constant or variable must have the same ...
1
vote
1answer
48 views
Add type checking/inference to my programming language
I am currently creating my own compiled programming language, and I have come to a point where I would like to start working on the type system and introduce some type checking. Ideally I would like ...
4
votes
2answers
177 views
Check if a lambda constructor is well-typed
In basic type inference for 𝜆-calculus with parametric polymorphism à la Hindley–Milner,
when can we say that we cannot give a type to a lambda constructor?
For example
$$(λx.λy.y(x\ ...
Gilles 'SO- stop being evil'
38.9k7 gold badges103 silver badges167 bronze badges
3
votes
1answer
94 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 ...
1
vote
1answer
66 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 ...
2
votes
0answers
34 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 ...
2
votes
0answers
26 views
How does the free program identifiers (fpi) extend over constraints and type schemes in $HM(X)$?
Chapter 10 of Advanced Topics in Types and Programming Languages; gives a very comprehensive description of type inference by constraints solving.
They introduce the free program indentifiers of an ...
4
votes
1answer
214 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 ...
4
votes
1answer
310 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:
...
5
votes
3answers
1k views
Why isn't the Swift programming language type inference more aggressive?
Couldn't the type inference in Apple's new programming language Swift had been done more aggressive? For instance why can't the return type of a function be deduced?
...
5
votes
1answer
159 views
Hindley-Milner type inference for language with implicit type casting
I've only implemented the HM algorithm on a small academic language with a few primitive types and functions. In that case, the unification algorithm would return a type error if two different ...
1
vote
2answers
111 views
Symbolic Evaluation for Type Inference in a Dynamic Language
Say I have the following contrived example code:
...
4
votes
2answers
259 views
In Hindley-Milner system, how can I prove that let id=\x.x in id id is well-typed?
I am trying to infer the type and prove that this is well-typed:
let $f =\lambda x.x$ in $f f$
Obviously the $f$ is the identity function, so it's the same as
let $id =\lambda x.x$ in $id$ $id$
I ...
Gilles 'SO- stop being evil'
38.9k7 gold badges103 silver badges167 bronze badges
10
votes
0answers
449 views
Advantages of algorithm W over algorithm J for type inference in Hindley-Milner type system
According to A modern eye on ML type inference
Furthermore, for some
unknown reason,
W
appears to have become more popular than
J, even though the latter is viewed—with reason!—by Milner as ...
2
votes
1answer
151 views
Assertion of Type Inference Rules/Type Checking
I have a problem in a book I am trying to accomplish.
I understand the overall type of the expression is boolean and how it derives. (y * x) will be rule 4 (counting from top right). (y * x) + x when ...
4
votes
0answers
308 views
Hindley-Milner: How do I separate constraint generation and unification phases in Algorithm W when inferring types of patterns?
I am self-teaching myself Hindley-Milner type inference by writing my own implementation, separating tree traversal and constraint solving. The tutorials that I've been following only allow patterns ...
44
votes
1answer
6k views
What makes type inference for dependent types undecidable?
I have seen it mentioned that dependent type systems are not inferable, but are checkable. I was wondering if there is a simple explanation of why that is so, and whether or not there is there a limit ...
2
votes
1answer
45 views
Typing by value
I wondered if there was a generalized name for typing a variable by assigning a specific value to it. For instance
a = 4
This would make the variable ...
1
vote
0answers
1k views
How does C# do type inference?
Sometimes the C# compiler can do some type inference when you have to specify the generic parameters of some methods, like:
...
2
votes
2answers
31 views
Inferring used fields in return type
A common issue in app development is avoiding over-fetching of data, such as in this naive (pseudocode) example:
...
3
votes
2answers
624 views
System f-sub, how to do type checking?
I was reading that system f-sub (polymorphic lambda calculus with sub-typing) and I was quite confused with its one checking rule called "T-TAPP".
This rule as following (ctx denotes the typing ...
4
votes
1answer
122 views
What's the advantage of “value restriction” over its alternatives?
What is the motivation to pick "value restriction" over other candidates?
Examples of alternatives:
Enclosing pureness into the function type, for example:
...
4
votes
1answer
297 views
Type Inference and Generalization
I've been trying to understand type inference for Hindley-Milner-based languages, and I'm struggling to understand how generalization works. Let's say I have the following program in Haskell:
...
3
votes
1answer
149 views
Partial type inference for dependent types
I'm looking for resources on (partial) type inference for dependent types.
For example there could be a type inference scheme that fails if the term doesn't have a principal type, or a scheme that ...
8
votes
0answers
272 views
Type-classes for type inference
I'm creating a semantic analyzer with type inference. For the basics I've got a type variable and a type construct with name and a list of types.
I want to support overloading and I know that Haskell ...
8
votes
2answers
1k views
Relation between type-checking decidability, typability decidability and strong normalization
Yo! This is probably a stupid question, however I've never seen it written down explicitly if, for instance, decidability of type-checking is equivalent to the strong normalization property. Therefore ...
3
votes
2answers
292 views
Which type compilers report if they cannot infer a precise type?
In the presence of subtyping, a type checker can usually infer only some inequality constraints on the type rather than the exact type. Of course, internally it will store the full constraints. But ...
5
votes
1answer
106 views
Local type argument synthesis when type variable does not appear in arguments
I am implementing the techniques described in the classic Local Type Inference paper. Specifically, I am implementing the type argument synthesis algorithm from section 3.
My algorithm seems to ...
5
votes
1answer
194 views
Polymorphism restriction on lambda-bound variables in HM
I'm trying to implement the Hindley-Milner type system, following Milner 1978, "A Theory of Type Polymorphism in Programming" (link). In the Hindley-Milner system, a polymorphic let-bound expression ...
