<p>I am implementing a <em>toy language</em>, for learning. As of now, it has a Rust-like syntax and I would like to implement monomorphization of Generic types.</p>
<p>After parsing, I have an <em>Abstract Syntax Tree</em>. Now, I am replacing the <strong>type variables</strong> of generic <code>struct</code> and <code>enums</code> (tagged unions) and functions, depending on how they are used. I feel this is straight-forward to implement, as long as the types are visible in the function signatures.</p>
<p>So now to a few cases where I am not sure about how to implement. Consider that I have a type <code>Result</code> (common in some functional languages) that is a tagged union type with <strong>two type variables</strong>.</p>
<p>E.g.:</p>
<pre><code>enum Result s e = Ok(s) | Err(e)
</code></pre>
<p>where <code>s</code> and <code>e</code> are two independent type variables.</p>
<p>Consider these two example functions:</p>
<pre><code>fn demo_fn_one() -&gt; i32 {
    let res = Ok(45);
    match res {
        Ok(n) =&gt; n,
        Err(_) =&gt; 64, // not in use, could be Type&lt;None&gt;
    }
}
</code></pre>
<p>and</p>
<pre><code>fn demo_fn_two() -&gt; i32 {
    let res = Ok(45);
    match res {
        Ok(n) =&gt; n,
        Err(e) =&gt; e, // is used here, is Type&lt;i32&gt;
    }
}
</code></pre>
<h2>Type Checking</h2>
<p>I assume that this pass will return another <em>Intermediate Abstract Syntax Tree</em>, but without any Generic types, they are replaced with concrete types. I am targeting WebAssembly and the identifier <code>res</code> is stored as a <a href="https://webassembly.github.io/spec/core/syntax/modules.html#syntax-func" rel="nofollow noreferrer">local</a> and I <strong>need to know what types and size</strong> it occupies. (No optimizations in use)</p>
<p>What I find most difficult is regarding the <em>type variable</em> <code>e</code>.</p>
<p>I see <code>Ok(s)</code> as a generic function, with return type <code>Result&lt;s,e&gt;</code> so the identifier <code>res</code> will occupy that size, but I need to find out the concrete type for the type variables.</p>
<p>I assume that the &quot;type checking&quot;-pass walks the AST tree, recursively, starts with <code>Ok(45)</code> and return the concrete types of the expressions and keep the type of identifiers in a symbol table. But this means that when I return from the <code>Ok(45)</code> AST-node, I fully don't know the return type, it is like <code>Result&lt;i32,??&gt;</code> since the type of <code>e</code> is not discovered yet.</p>
<p>Any suggestions on how to implement the &quot;type checking&quot; pass, especially regarding these examples?</p>

<implementation><type-checker><generics>
How to implement type checking of generics?
CC BY-SA 4.0
2024-05-14T21:38:48.690Z
Is monomorphisation the issue here, or is it about the type checking/inference in a (logically) prior step? It seems like the same issue arises without monomorphisation in that you just don't know the types of some expressions. How does your type system and type checker operate?
Michael Homer
CC BY-SA 4.0
2024-05-14T21:42:55.077Z
yes, this problem is because the Type has type variables `Result<s,e>`, if the `Result` type was concrete/without any type variables, then it wouldn't be a problem. But yes, my thought was to do type checking in the same pass, but I mostly focus on this problem that I stumbled upon.
Jonas
CC BY-SA 4.0
2024-05-14T21:45:39.200Z
Ok, so there hasn't been any checking at all so far? I think that is probably the real question to address then - we have *some* related questions under [tag:type-checker] that might be useful, but if none of them get at what you're looking for then it'll be a good one to ask.
Michael Homer
CC BY-SA 4.0
2024-05-14T22:57:41.077Z
Yes, this question is about type checking and maybe type inference, not about monomorphization. Monomorphization is a way to implement the execution of generic code. It comes after finding what the types are, and verifying that the types are correct.
Eldritch Conundrum
CC BY-SA 4.0
2024-05-18T10:40:26.577Z
In its current form, the question cannot be answered as it lacks details on type checking and the underlying type lattice for, both, the input and the target IRs. In its current form, it would allow for trivial answer like "box everything" or "box variable types and resort to RTTI"
feldentm
CC BY-SA 4.0
2024-05-18T10:42:07.837Z
It is also not clear, why a parameter type needs to be inferred at all if it is just about monomorphization where it would be dropped anyway in most languages.
feldentm
CC BY-SA 4.0
2024-05-24T10:06:08.953Z
What's wrong with the explanation in  [Types and Programming Languages](https://www.cis.upenn.edu/~bcpierce/tapl/)? Or indeed the original paper [L. Damas, R. Milner, Principal type-schemes for functional programs](https://people.eecs.berkeley.edu/~necula/Papers/DamasMilnerAlgoW.pdf) which is crystal clear and very simple? (I had to implement that algorithm as coursework in a 3rd year undergraduate course.) The paper  is only 6 pages and crystal clear.
Martin Berger
# How to implement type checking of generics?
Posted by: username_0 on 2024-05-14
I am implementing a toy language, for learning. As of now, it has a Rust-like syntax and I would like to implement monomorphization of Generic types.
After parsing, I have an Abstract Syntax Tree. Now, I am replacing the type variables of generic struct and enums (tagged unions) and functions, depending on how they are used. I feel this is straight-forward to implement, as long as the types are visible in the function signatures.
So now to a few cases where I am not sure about how to implement. Consider that I have a type Result (common in some functional languages) that is a tagged union type with two type variables.
E.g.:
enum Result s e = Ok(s) | Err(e)

where s and e are two independent type variables.
Consider these two example functions:
fn demo_fn_one() -> i32 {
    let res = Ok(45);
    match res {
        Ok(n) => n,
        Err(_) => 64, // not in use, could be Type
    }
}

and
fn demo_fn_two() -> i32 {
    let res = Ok(45);
    match res {
        Ok(n) => n,
        Err(e) => e, // is used here, is Type
    }
}

Type Checking
I assume that this pass will return another Intermediate Abstract Syntax Tree, but without any Generic types, they are replaced with concrete types. I am targeting WebAssembly and the identifier res is stored as a local and I need to know what types and size it occupies. (No optimizations in use)
What I find most difficult is regarding the type variable e.
I see Ok(s) as a generic function, with return type Result so the identifier res will occupy that size, but I need to find out the concrete type for the type variables.
I assume that the "type checking"-pass walks the AST tree, recursively, starts with Ok(45) and return the concrete types of the expressions and keep the type of identifiers in a symbol table. But this means that when I return from the Ok(45) AST-node, I fully don't know the return type, it is like Result since the type of e is not discovered yet.
Any suggestions on how to implement the "type checking" pass, especially regarding these examples?
**Tags:** implementation type-checker generics
> **Comments:**
> **username_1**: Is monomorphisation the issue here, or is it about the type checking/inference in a (logically) prior step? It seems like the same issue arises without monomorphisation in that you just don't know the types of some expressions. How does your type system and type checker operate?  
> **username_0**: yes, this problem is because the Type has type variables `Result<s,e>`, if the `Result` type was concrete/without any type variables, then it wouldn't be a problem. But yes, my thought was to do type checking in the same pass, but I mostly focus on this problem that I stumbled upon.  
> **username_1**: Ok, so there hasn't been any checking at all so far? I think that is probably the real question to address then - we have *some* related questions under [tag:type-checker] that might be useful, but if none of them get at what you're looking for then it'll be a good one to ask.  
> **username_2**: Yes, this question is about type checking and maybe type inference, not about monomorphization. Monomorphization is a way to implement the execution of generic code. It comes after finding what the types are, and verifying that the types are correct.  
> **username_3**: In its current form, the question cannot be answered as it lacks details on type checking and the underlying type lattice for, both, the input and the target IRs. In its current form, it would allow for trivial answer like "box everything" or "box variable types and resort to RTTI"  
> **username_3**: It is also not clear, why a parameter type needs to be inferred at all if it is just about monomorphization where it would be dropped anyway in most languages.  
> **username_4**: What's wrong with the explanation in  [Types and Programming Languages](https://www.cis.upenn.edu/~bcpierce/tapl/)? Or indeed the original paper [L. Damas, R. Milner, Principal type-schemes for functional programs](https://people.eecs.berkeley.edu/~necula/Papers/DamasMilnerAlgoW.pdf) which is crystal clear and very simple? (I had to implement that algorithm as coursework in a 3rd year undergraduate course.) The paper  is only 6 pages and crystal clear.  
---
## 0 answers
