asdlGen Reference Manual : Input Syntax : Type Definitions : Sum Types
Previous: Product Types
Next: Field Labels

3.3.3. Sum Types

Sum types are the most useful types in ASDL. They provide concise notation used to describe a type that is the tagged union of a finite set of other types. Sum types consists of a series of constructors separated by a vertical bar. Each constructor consist of a constructor identifier followed by an optional sequence of fields similar to a product type.

Constructor names must be unique within the module in which they are declared. Constructors can be viewed as functions who take some number of arguments of arbitrary type and create a value belonging to the sum type in which they are declared. For example

module M {
  sexpr = Int(int)
	| String(string)
	| Symbol(identifier)
	| Cons(sexpr, sexpr)
	| Nil
}
declares that values of type sexpr can either be constructed from an int using the Int constructor or a string from a String constructor, an identifier using the Symbol constructor, or from two other sexpr using the Cons constructor, or from no arguments using the Nil constructor. Notice that the Cons constructor recursively refers to the sexpr type. ASDL allows sum types to be mutually recursive. Recursion however is limited to sum types defined within the same module.

3.3.3.1. The Rosetta Stone for Sum Types

In languages that have algebraic data types sum types are equivalent to the datatype and data declarations in ML and Haskell. In Algol like languages they are equivalent to tagged unions in C or variant records in Pascal. In class based object oriented languages sum types are equivalent to an abstract base class that represents the type of a family of subclasses one for each constructor of the type. The previous example written in ML would be

structure M =
 struct
  datatype sexpr = 
           Int of (int)
         | String of (string)
         | Symbol of (identifier)
         | Cons of (sexpr * sexpr)
         | Nil
 end
in C would be
typedef struct M_sexpr_s * M_sexpr_ty;
struct M_sexpr_s { 
 enum { M_Int_kind, M_String_kind, 
        M_Symbol_kind, M_Cons_kind, M_Nil_kind }  kind;
         union {
	  struct M_Int_s    { int_ty  int1;             } M_Int;
          struct M_String_s { string_ty string1;        } M_String;	 
          struct M_Atom_s   { identifier_ty identifier1;} M_Atom;
          struct M_Cons_s   { M_sexpr_ty; sexpr1 M_sexpr_ty sexpr2 }; M_Cons;
         } v;
}
and in Java would be
package ast.M;
public abstract class sexpr {
	 int kind;
	 static final Int_kind        = 0;
	 static final String_kind     = 1;
	 static final Symbol_kind     = 2;
	 static final Cons_kind       = 3;
	 static final Nil_kind        = 4;
	 abstract int kind();
}
public class Int extends sexpr { 
    int v; 
    Int(int v) { this.v = v;  } 
    int kind () { return Int_kind; }
}
public class String extends sexpr { String(string v) { ... } ... }
public class Symbol extends sexpr { Symbol(identifier v) { ... } ... }
public class Cons   extends sexpr { Cons(sexpr x, sexpr y) { ... } }
public class Nil    extends sexpr { Nil() { ... } }

3.3.3.2. Sum Types as Enumerations

Sum types which consist completely of constructors that take no arguments are often treated specially and translated into static constants of a enumerated value in languages that support them.

module Op {
  op = PLUS | MINUS | TIMES | DIVIDE 
}

Is translated into the enumeration and constants in C as

enum Op_op_ty {Op_PLUS_kind, Op_MINUS_kind, Op_TIME_kind, Op_DIVIDE_kind};
extern Op_op_ty Op_PLUS   = Op_PLUS_kind;
extern Op_op_ty Op_MINUS  = Op_MINUS_kind;
extern Op_op_ty Op_TIMES  = Op_TIMES_kind;
extern Op_op_ty Op_DIVIDE = Op_DIVIDE_kind;


asdlGen Reference Manual : Input Syntax : Type Definitions : Sum Types
Previous: Product Types
Next: Field Labels