asdlGen
Reference Manual
: Input Syntax
: Type Definitions
: 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.
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() { ... } }
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