Choosing whether to use Discriminated Unions or Record Types for a small AST in F#

Let's say I am implementing a very simple toy language parser. I am deciding whether to use DUs or record types (maybe a mix of both?). The structure of the language would be:

a Namespace consists of a name and a list of classes
a Class consists of a 开发者_如何转开发name and a list of methods
Method consists of a name, return type and a list of Arguments
Argument consists of a type and a name

Example of a program in this simple language:

namespace ns {
  class cls1 {
    void m1() {}
  }

  class cls2 {
    void m2(int i, string j) {}
  }
}

How would you model this and why?

---

You almost surely want to use DUs to implement alternations, where any part of the code structure could be one of multiple possibilities. A mix would probably be ideal, although you could use tuples in place of records - which may make it simpler to use, but perhaps more difficult to read and maintain, because you don't have named items in the tuples.

I would model it as something like this

type CompilationUnit = | Namespace list

and Namespace = { Name : String
                  Body : NamespaceBody }

and NamespaceBody = | Classes of Class list

and Class = { Name : String
              Body : ClassBody }

and ClassBody = | Members of Member list

and Member = | Method of Method

and Method = { Name : String
               Parameters : Parameter list option
               ReturnType : TypeName option
               Body : MethodBody }

and Parameter = { Name : String
                  Type : TypeName }

and MethodBody = ...

and TypeName = ...

The need for DUs might not be apparent using your example language, but will become clear as soon as you have any point in code which could be one or more items. Say, eg, if you add fields to your class - you'll just need to add a new Field discrimination to Member.

If you're using a grammar to parse your language (LL/LALR or similar), you'll probably need a matching DU for each alternation rule you have in the grammar.

---

a Namespace consists of a name and a list of classes a Class consists of a name and a list of methods Method consists of a name, return type and a list of Arguments Argument consists of a type and a name Example of a program in this simple language:

You also need a type definition for your type system and that is actually the only place where a union type is valuable:

type Type = Void | Int | String

So a type in your language is either an int or a string or void but cannot be nothing (e.g. null) and cannot be more than one of those options.

The type of a namespace could be entirely anonymous, like this:

string * (string * (Type * string * (Type * string) list) list) list

You could define your example namespace like this:

"ns", ["cls1", [Void, "m1", []]
       "cls2", [Void, "m2", [Int, "i"; String, "j"]]]

In practice, you probably want the ability to put namespaces in other namespaces and to put classes in classes so you might evolve the code into something like this:

type Type =
  | Void
  | Int
  | String
  | Class of Map<string, Type> * Map<string, Type * (Type * string) list>

type Namespace =
  | Namespace of string * Namespace list * Map<string, Type>

Namespace("ns", [],
          Map
            [ "cls1", Class(Map[], Map["m1", (Void, [])])
              "cls2", Class(Map[], Map["m2", (Void, [Int, "i"; String, "j"])])])

Anonymous types are fine as long as they won't be a source of confusion. As a rule of thumb, if you have two or three fields and they are of different types (like a "method" here) then a tuple is fine. If there are more fields or multiple fields with the same type then it is time to switch to a record type.

So in this case you might want to introduce a record type for methods:

type Method =
  { ReturnType: Type
    Arguments: (Type * string) list }

and Type =
  | Void
  | Int
  | String
  | Class of Map<string, Type> * Map<string, Method>

type Namespace =
  | Namespace of string * Namespace list * Map<string, Type>

Namespace("ns", [],
          Map
            [ "cls1", Class(Map[], Map["m1", { ReturnType = Void; Arguments = [] }])
              "cls2", Class(Map[], Map["m2", { ReturnType = Void; Arguments = [Int, "i"; String, "j"] }])])

and maybe a helper function to construct those records:

let Method retTy name args =
  name, { ReturnType = retTy; Arguments = args }

Namespace("ns", [],
          Map
            [ "cls1", Class(Map[], Map[Method Void "m1" []])
              "cls2", Class(Map[], Map[Method Void "m2" [Int, "i"; String, "j"]])])