Algebraic Data Types

Why have them?

Algebraic data types let us solve a couple issues.

They let us avoid the need for nil pointers

They let us return errors from functions, as opposed to:

• C, which uses a lot of in-band signalling - sending error codes in the return value - which is no good.
• Go, which supports multi-value return. This is a special language construct that solves that specific problem.

Rationale

Consider reading from a file.

In C

C has the read function that reads from file descriptors.

// If successful, the number of bytes actually read is returned.
// Upon reading end-of-file, zero is returned.
// Otherwise, a -1 is returned and the global variable errno is set to indicate the error.
ssize_t read(int fildes, void *buf, size_t nbyte);

Assuming fd is a valid file descriptor

char buf[1024];
n := read(fd, buf, 1024);
if (n = -1) {
	int err = errno;
	// handle error
	return
}
doStuffWith(buf, n);

In Go

Go has the Reader interface. Signature of a Reader is:

type Reader interface {
    Read(p []byte) (n int, err error)
}

Assuming r is an open Reader

buf := make([]byte, 1024)
n, err := r.Read(buf)
if err != nil {
	// handle error
	return
}
doStuffWith(buf[:n])

In Boson

In Boson we want something like Go’s interfaces. However we want to be able to return a single algebraic Result type that can be a success value or an error.

type Reader interface {
    Read(p []byte) Result[int]
}

Assuming r is an open Reader

var buf byte[1024] <!-- TODO: address array syntax -->
m := r.Read(buf)
match m {
case Error(e):
	// handle error
case Ok(n):
	doStuffWith(buf, n)
}

Syntax

Declaration

The declaration syntax will be as follows:

type Option[T] {
	Some(T)
	None
}

This declares the Option[T] type, with two type constructors, Some and None. Option[T] has a type parameter T, and that is used to parameterize the constructor Some.

The syntax should allow for multiple type parameters:

type Pair[L, R] {
	Pair(L, R)
}

Usage

Using a type once it’s been declared should be straight forward. The type constructors in the declaration are callable, and construct a value of the type.

var o Option[int] = Some(10)
var p Pair[int, bool] = Pair(10, true)

Incomplete and Concrete types

Incomplete types

Option[T] is an example of an incomplete type. It is incomplete because T does not name a concrete type, and is used as a parameter. The only valid place to use an incomplete type is in a type definition. Everywhere else, we need a concrete type.

Concrete types

Option[int] is an example of a concrete type. It is concrete because int names another concrete type. We can use Option[int] anywhere we would use any other concrete type. Incomplete types give us prototypes for creating concrete types. We can use any concrete type in place of the type parameter in an Incomplete type. That includes primitive types, arrays, structs, and even other ADTs:

type widget struct {
	foo string
	bar string
}

type Option[T] {
	Some(T)
	None
}

func main() {
	// All of the following are valid:
	var optInt Option[int] = Some(10)
	var optWidget Option[Widget] = Some(widget{"foo", "bar"})
	var optOptWidget Option[Option[Widget]] = Some(Some(widget{"foo", "bar"}))
	var emytyOptOptWidget Option[Option[Widget]] = Some(None)
}