8
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ 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! $\endgroup$ Commented Apr 18 at 20:26
  • $\begingroup$ thank you for your feedback. did as you told and narrowed down the question. I hope this makes the question more clear. @EricLippert $\endgroup$
    – NotAlfred
    Commented Apr 18 at 23:27
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$ Commented Apr 19 at 0:56
  • $\begingroup$ 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. $\endgroup$ Commented Apr 19 at 1:24
  • $\begingroup$ 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 $\endgroup$
    – NotAlfred
    Commented Apr 19 at 2:20

2 Answers 2

6
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – NotAlfred
    Commented Apr 19 at 3:32
  • $\begingroup$ @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. $\endgroup$ Commented Apr 19 at 8:09
  • $\begingroup$ 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. $\endgroup$ Commented Apr 19 at 8:11
  • $\begingroup$ 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#. $\endgroup$
    – Brian
    Commented Apr 19 at 13:26
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Apr 19 at 16:14
8
$\begingroup$

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<int> 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .