2

I am trying to determine how to manage types and conversions between types within a compiler that I am writing. The compiler is being written in C#.

There are a number of different kinds of types.

  1. Classes (read only / not mutable)
  2. Mutable Types (Which contain another type. Think the opposite of C++ const.)
  3. Generic Types (With constraints referring to types)
  4. etc

The problem I am trying to solve is, given two types, how can I determine whether one can be converted to the other. (eg. Allow a mutable type to be assigned to the read only version of the type)

My first thought was to use a virtual method and a visitor. However, since types can depend on others (e.g. A mutable type is a wrapper referring to another type.), this can cause the number of cases that need to be handled to balloon. I am looking for a design that keeps this to a minimum.

Improve this question
6
  • 3
    Type systems can be very complex, before anything else you need to define the rules of your type system-> Do you allow covariance or contravariance on your parameterized types? Do you have subtypal, prototypal, contract-only, and/or inferrable(duck-type) polymorphism? Do you have contracts? How do you define the type of a function? You need to detail all of these things before implementation so that you can manually walk all the implications yourself or plug them into a proof solver to verify correctness/consistency. Incorrectness in your type system will make writing the compiler impossible. Commented Jan 24, 2015 at 17:18
  • rather, not impossible, but very difficult and confusing. Easier implementing a compiler if you already know the rules of your type system and have ensured they're self-consistent. Commented Jan 24, 2015 at 17:24
  • I think I have a pretty good understanding of the rules of the type system I'm using. My primary concern is figuring out how to represent it in code. With generic parameters it becomes arbitrarily recursive. Commented Jan 24, 2015 at 17:33
  • not arbitrarily recursive, have a look at Algorithm W here for how parameterized types can be verified. Algorithm W falls over a bit with OO subtypal systems but it should still give you some good insights on how to proof correctness with parametric polymorphism Commented Jan 24, 2015 at 18:00
  • It sounds like your problem is focussed on cycle finding, there's algorithms for doing just that. Modeling cycles in a graph isn't that hard, you just need to find them before your type checker goes into an infinite loop. Perhaps you should edit your question to specify that you want advice on identifying and modelling a cyclical graph Commented Jan 25, 2015 at 17:41

1 Answer 1

Reset to default
3

The problem I am trying to solve is, given two types, how can I determine whether one can be converted to the other.

In your language design, you have a well defined set of rules for your type system. A is a subtype of B if and only if these conditions hold. C can be assigned to a variable of type D if and only if these other conditions hold. And you do the paperwork to prove that your type system is consistent (you can't get into a state where the rules are broken).

Then, for implementation it's fairly straightforward. You define some classes to define your various type forms - often derived from some common type baseclass so the concrete types can be used wherever your language expects a type. Then you write these rules into nice static (possibly recursive) binary predicates that tell you if for these two types, do the conditions hold.

Yes, that often means a bunch of if T is GenericType ugliness. You can get around that a little by using dynamic and doing dynamic dispatch on the predicates. I'm not sure that's particularly cleaner.

The good thing about the static predicates is that they are absurdly easy to unit test, and should be a near 1:1 translation of your type system on paper. They're hard to screw up, and they provide clear documentation to future programmers (likely you) about what the rules are.

Improve this answer
1
  • The suggestion of using dynamic gave me the idea of trying to write this particular part in F# so I can use pattern matching. Commented Jan 26, 2015 at 22:59

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.