<p>I'm trying to make a simple compiler, and am getting stuck with IR code generation for lists in my language. I asked around and learned about algebraic data types and how they work, but I can't seem to find any resources that explain how they are actually implemented.</p>
<p><strong>How can I represent a simple ADT in a compiler where it's possible to do user defined types?</strong> For now, I'm not trying to support generics. The compiler is implemented in Haskell.</p>

<types><algebraic-data-types>
How are algebraic data types implemented?
CC BY-SA 4.0
2024-04-18T20:26:41.307Z
That is a very big question; can you narrow it down a little? Are you asking how to implement a type checker, or how to represent types in a compiler, or what?  What kind of algebraic types do you intend to implement? Are you going to do generic types as well?  Give us more details!
Eric Lippert
CC BY-SA 4.0
2024-04-18T23:27:14.243Z
thank you for your feedback. did as you told and narrowed down the question. I hope this makes the question more clear. @EricLippert
NotAlfred
CC BY-SA 4.0
2024-04-19T00:56:02.460Z
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.
Community Compiler
CC BY-SA 4.0
2024-04-19T01:24:00.823Z
That's better -- can you say a little about what language you're implementing your compiler in? The way *that* language represents ADTs for its developers will inform how to represent ADTs in your compiler.
Eric Lippert
CC BY-SA 4.0
2024-04-19T02:20:59.453Z
Thank you for your patience. I'm doing it in Haskell. I already have a simple type system. I'm more curious about user defined types. @EricLippert
NotAlfred
<h1>Tagged unions</h1>
<p>ADTs are, at their core, restricted tagged unions. For example:</p>
<pre class="lang-ocaml prettyprint-override"><code>(* ocaml *)
type foobar =
    | One of int
    | Two of float
    | Three of int list
</code></pre>
<p>is a &quot;subset&quot; of what you can represent with</p>
<pre class="lang-c prettyprint-override"><code>// c-ish
enum foobar_tag {
    One,
    Two,
    Three
};
struct foobar {
    enum foobar_tag tag;
    union {
       int One;
       float Two;
       vec&lt;int&gt; Three; 
    };
};
</code></pre>
<p>The latter obviously lacking the type safety of the former - you can access any field at will, even if the tag isn't correct. However, if you typecheck the former, you can safely compile it to the latter - you know that all accesses are correct, and therefore there's no unsafety in the latter.</p>

CC BY-SA 4.0
2024-04-19T01:54:11.190Z
2024-04-19T01:54:11.190Z
blueberry
<p>When I used to interview people a common technique for technical questions was to write a very simple specification and see if the candidate could translate that into very simple code. Like if I said &quot;a binary tree is either empty, or two binary trees called left and right, how could you very clearly implement that specification?&quot; then the candidate might start by writing something like:</p>
<pre><code>abstract class BinaryTree {}
sealed class Empty : BinaryTree {}
sealed class NonEmpty : BinaryTree 
{
  BinaryTree left;
  BinaryTree right;
}
</code></pre>
<p>and then flesh it out into working code.</p>
<p>You can do the same. Start by writing a <em>very clear</em> specification for what a type is. Maybe in your language it is:</p>
<ul>
<li>An atomic type is a kind of type. int and string are atomic types.</li>
<li>A record type is a list of zero or more fields; a field has a name and a type.</li>
<li>A union type is a list of two or more types.</li>
</ul>
<p>And so on.  Once you have your <em>very clear</em> definition, translate that into the simplest possible type declarations:</p>
<pre><code>abstract class MyType {}
abstract class AtomicType : MyType {}
// CONSIDER: Make these singletons?
sealed class IntType : AtomicType {} 
sealed class StringType : AtomicType {}
sealed class Field 
{
  MyType type;
  string name;
}
sealed class RecordType : MyType { ...
</code></pre>
<p>and so on; you see how this goes I'm sure.</p>
<p>The key thing though that I really want to emphasize here is <em>write a specification</em>.  It's only a handful of sentences, but they will strongly inform you about how to structure the code, regardless of the language you're implementing your compiler in.</p>
<hr />
<p>UPDATE: I missed your note that you're doing this in Haskell; that language is excellent for concisely translating clear specifications into code that reflects the structure inherent in the spec, so I think you should find it pretty straightforward once you have written a clear spec. Do feel free to ask follow-up questions if you get stuck!</p>

CC BY-SA 4.0
2024-04-19T03:16:59.497Z
2024-04-20T17:52:47.083Z
2024-04-20T17:52:47.083Z
Eric Lippert
CC BY-SA 4.0
2024-04-19T03:32:32.510Z
thank you. so if got it correctly for each type definition I have to come up with its own definition? no weird mathematics going on? also multiple people been warning me about turing completeness. is that really a big issue?
NotAlfred
CC BY-SA 4.0
2024-04-19T08:09:17.297Z
@n0nsense: No weird math yet. As for completeness, once your type system is complex enough then sure, you can make the compiler solve arbitrarily hard problems to check for type safety. But in practice, developers do not write code that is hard to type check.
Eric Lippert
CC BY-SA 4.0
2024-04-19T08:11:22.663Z
You can certainly encode arbitrary problems in the Haskell type system. Any type system that has generic types with contravariance (Java, C#, and so on) is known to be Turing complete. People do not build types whose conversion rules simulate steps in a Turing machine.
Eric Lippert
CC BY-SA 4.0
2024-04-19T13:26:47.410Z
I find it mentally irritating to see a sealed class with no public surface area.  I realize you are answering a langdev question rather than a SO question.  However, using fully legal syntax and applying multiple keywords means my brain refuses to treat it as pseudo-code that just so happens to be legal c#.
Brian
CC BY-SA 4.0
2024-04-19T16:14:40.490Z
@Brian: It was just a sketch to show how to start. Obviously there would have to be a public surface area. A candidate who wrote only that would not get a hire recommendation; a candidate who started with that and fleshed it out is probably going to do fine.
Eric Lippert
CC BY-SA 4.0
2024-04-19T23:11:01.670Z
"developers do not write code that is hard to type check." Until they start to do generics. I notice that most of the SO questions about Python type checking involve generics.
Barmar
CC BY-SA 4.0
2024-04-20T08:27:15.483Z
@Barmar: I mean hard in the sense of NP HARD or harder. (Though to be fair when we were designing C# 3 I discovered a way to make overload resolution NP HARD that was actually quite likely in practice and we changed the design of LINQ to make it less likely.)
Eric Lippert
# How are algebraic data types implemented?
Posted by: username_0 on 2024-04-18
I'm trying to make a simple compiler, and am getting stuck with IR code generation for lists in my language. I asked around and learned about algebraic data types and how they work, but I can't seem to find any resources that explain how they are actually implemented.

**How can I represent a simple ADT in a compiler where it's possible to do user defined types?** For now, I'm not trying to support generics. The compiler is implemented in Haskell.
**Tags:** types algebraic-data-types
> **Comments:**
> **username_1**: That is a very big question; can you narrow it down a little? Are you asking how to implement a type checker, or how to represent types in a compiler, or what?  What kind of algebraic types do you intend to implement? Are you going to do generic types as well?  Give us more details!  
> **username_0**: thank you for your feedback. did as you told and narrowed down the question. I hope this makes the question more clear. @EricLippert  
> **username_2**: Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.  
> **username_1**: That's better -- can you say a little about what language you're implementing your compiler in? The way *that* language represents ADTs for its developers will inform how to represent ADTs in your compiler.  
> **username_0**: Thank you for your patience. I'm doing it in Haskell. I already have a simple type system. I'm more curious about user defined types. @EricLippert  
---
## 2 answers
### Answer by username_1 on 2024-04-19. Score: 6 | Accepted answer
When I used to interview people a common technique for technical questions was to write a very simple specification and see if the candidate could translate that into very simple code. Like if I said "a binary tree is either empty, or two binary trees called left and right, how could you very clearly implement that specification?" then the candidate might start by writing something like:
abstract class BinaryTree {}
sealed class Empty : BinaryTree {}
sealed class NonEmpty : BinaryTree 
{
  BinaryTree left;
  BinaryTree right;
}

and then flesh it out into working code.
You can do the same. Start by writing a very clear specification for what a type is. Maybe in your language it is:

An atomic type is a kind of type. int and string are atomic types.
A record type is a list of zero or more fields; a field has a name and a type.
A union type is a list of two or more types.

And so on.  Once you have your very clear definition, translate that into the simplest possible type declarations:
abstract class MyType {}
abstract class AtomicType : MyType {}
// CONSIDER: Make these singletons?
sealed class IntType : AtomicType {} 
sealed class StringType : AtomicType {}
sealed class Field 
{
  MyType type;
  string name;
}
sealed class RecordType : MyType { ...

and so on; you see how this goes I'm sure.
The key thing though that I really want to emphasize here is write a specification.  It's only a handful of sentences, but they will strongly inform you about how to structure the code, regardless of the language you're implementing your compiler in.

UPDATE: I missed your note that you're doing this in Haskell; that language is excellent for concisely translating clear specifications into code that reflects the structure inherent in the spec, so I think you should find it pretty straightforward once you have written a clear spec. Do feel free to ask follow-up questions if you get stuck!
> **Comments:**
> **username_0** (2024-04-19): thank you. so if got it correctly for each type definition I have to come up with its own definition? no weird mathematics going on? also multiple people been warning me about turing completeness. is that really a big issue?  
> **username_1** (2024-04-19): @n0nsense: No weird math yet. As for completeness, once your type system is complex enough then sure, you can make the compiler solve arbitrarily hard problems to check for type safety. But in practice, developers do not write code that is hard to type check.  
> **username_1** (2024-04-19): You can certainly encode arbitrary problems in the Haskell type system. Any type system that has generic types with contravariance (Java, C#, and so on) is known to be Turing complete. People do not build types whose conversion rules simulate steps in a Turing machine.  
> **username_4** (2024-04-19): I find it mentally irritating to see a sealed class with no public surface area.  I realize you are answering a langdev question rather than a SO question.  However, using fully legal syntax and applying multiple keywords means my brain refuses to treat it as pseudo-code that just so happens to be legal c#.  
> **username_1** (2024-04-19): @Brian: It was just a sketch to show how to start. Obviously there would have to be a public surface area. A candidate who wrote only that would not get a hire recommendation; a candidate who started with that and fleshed it out is probably going to do fine.  
> **username_5** (2024-04-19): "developers do not write code that is hard to type check." Until they start to do generics. I notice that most of the SO questions about Python type checking involve generics.  
> **username_1** (2024-04-20): @Barmar: I mean hard in the sense of NP HARD or harder. (Though to be fair when we were designing C# 3 I discovered a way to make overload resolution NP HARD that was actually quite likely in practice and we changed the design of LINQ to make it less likely.)  
---
### Answer by username_3 on 2024-04-19. Score: 8
Tagged unions
ADTs are, at their core, restricted tagged unions. For example:
(* ocaml *)
type foobar =
    | One of int
    | Two of float
    | Three of int list

is a "subset" of what you can represent with
// c-ish
enum foobar_tag {
    One,
    Two,
    Three
};
struct foobar {
    enum foobar_tag tag;
    union {
       int One;
       float Two;
       vec Three; 
    };
};

The latter obviously lacking the type safety of the former - you can access any field at will, even if the tag isn't correct. However, if you typecheck the former, you can safely compile it to the latter - you know that all accesses are correct, and therefore there's no unsafety in the latter.
---
