Type-oriented programming/Printable version


Type-oriented programming

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Type-oriented_programming

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.


Types and properties

Types can be viewed of bundles of properties and functions operating on them. Such functions are conventionally called methods. Here’s an example of a simple type:

type Person {
  property name String
  property age Int
}

This type declaration states that the Person type has two properties. An instance of this type can be created using a new statement:

var p = new Person {
  name = "Jane",
  age = 18
}

The properties of a type’s instance can be accessed via the dot operator, for example:

return p.name

NB: The pseudocode can be tried out using the Funcy app, which can be downloaded for free from Apple’s App Store (iOS/macOS), Google Play (Android) or Amazon Appstore. The code to be executed must be placed in a main {} block. The example above can be tried out by running the following code:

type Person {
  property name String
  property age Int
}

main {
  var p = new Person {
    name = "Jane",
    age = 18
  }
  return p.name
}



Restricted properties

While subtyping is often ampliative, that is, a subtype contains all the properties of its supertype(s), it’s often useful to remove an inherited property from a subtype. For example, a complex has a real part and an imaginary part. Every real number is also a complex number but its imaginary part is always equal to zero so we don’t want this property to take up space in the instances. However we can’t remove the imaginary part altogether because it might be used by code working with complex numbers. What one can do is assign the property a fixed value:

type Complex {
  property real Float
  property imag Float

  func _add(x Complex) Complex {
    return new Complex {
      real=self.real+x.real,
      imag=self.imag+x.imag
    }
  }

  func _mul(x Complex) Complex {
    return new Complex {
      real=self.real*x.real-self.imag*x.imag,
      imag=self.real*x.imag+self.imag*x.real
    }
  }

  func description() String {
    return self.real.description() + "+" + self.imag.description() + "i"
  }
}

type Real : Complex {
  restrict imag Float = 0.0
}

main {
  var x = new Complex { real=2.0, imag=3.0 }
  var y = new Real { real=2.0 }
  return (x*y).description()
}

Note that the Real type now has only one stored property but the methods in the Complex type can still be used with the subtype.

NB: The pseudocode can be tried out using the Funcy app, which can be downloaded for free from Apple’s App Store (iOS/macOS), Google Play (Android) or Amazon Appstore. The code to be executed must be placed in a main {} block.



Self at the type level

Just like the self variable refers contextually to the instance in whose method it’s used, the Self type variable contextually refers to the type. Let’s have a look at a simple example:

type A {
  sfunc create() Self {
    return new Self
  }
}

type B : A {}

main {
  var obj = $B.create()
  return obj
}

The create method’s return type is Self so in the example above it refers to the B type because we called the type method using $B.create().

Using Self gives the type system considerable power since it squares well with type operators, as illustrated by the following example:

type Maybe[T] {
  property val T

  func description() String {
    return self.val.isNil() ? "none" : self.val.description()
  }

  func map[U](f Func[T,U]) Self[U] {
    return new Self[U] {
      val = self.val.isNil() ? nil : f(self.val)
    }
  }
}

main {
  var x = new Maybe[Int] { val=3 }
  var y = x.map[Float](\(x Int) Float . x.asFloat())
  return y.description() + " " + y.typeName()
}

Note that the map method has a type argument and how new Self[U] is used. In this case Self is a contextual type operator.

NB: The pseudocode can be tried out using the Funcy app, which can be downloaded for free from Apple’s App Store (iOS/macOS), Google Play (Android) or Amazon Appstore. The code to be executed must be placed in a main {} block.



Type variance

Consider the following type hierarchy:

type A {}

type B : A {}

type F[T] {}

Without type arguments, F is a type operator while F[A] and F[B] are proper types. In general, neither is a subtype of the other. However it may sometimes make sense for them to be in a subtype relation depending on the hierarchy of their argument(s). If we declare F as follows

type F[cov T] {}

then F[B] will be a subtype of F[A] because B is a subtype of A. Conversely, if we declare F as

type F[con T] {}

then F[A] will be a subtype of F[B]. In the former case, we say that F is covariant in its type argument whereas in the latter case its contravariant (since the hierarchy is reversed).

A real-world example of type variance are function types. When we expect a function whose return type is A (that is, of type Func[A]), we can always use a function of type Func[B] in its stead. On the other hand, when we expect a function whose argument is of type B (that is, of type Func[B,X], we can always use a function of type Func[A,X] in its stead. In sum, function types are covariant in their return type and contravariant in their arguments’ types.

NB: The pseudocode can be tried out using the Funcy app, which can be downloaded for free from Apple’s App Store (iOS/macOS), Google Play (Android) or Amazon Appstore. The code to be executed must be placed in a main {} block.



Bounded type arguments

Consider the following code:

type Equatable {
  func equals(x Any) Bool
}

type Complex : Equatable {
  property real Float
  property imag Float

  func equals(x Any) Bool {
    if x is Complex then {
      var x = x as Complex
      return self.real == x.real & self.imag == x.imag
    }
    return false
  }
}

type Pair[T] {
  property first T
  property second T
}

main {
  var x = new Complex { real=2.0, imag=3.0 }
  var y = new Complex { real=2.0, imag=3.0 }
  return x.equals(y)
}

We now want to implement the equals method also for Pair:

func equals(p Pair[T]) Bool {
  return self.first.equals(p.first) & self.second.equals(p.second)
}

Note, however, that this code won’t compile since the compiler can’t be sure that T represents an equatable type. We need to change the declaration of Pair to

type Pair[T:Equatable] { ... }

Now it’s ensured that T is equatable and we can check pairs for equality:

main {
  var x = new Complex { real=2.0, imag=3.0 }
  var y = new Complex { real=2.0, imag=4.0 }
  var p1 = new Pair[Complex] { first=x, second=y }
  var p2 = new Pair[Complex] { first=x, second=y }
  return p1.equals(p2)
}

Here, the T type argument is called bounded since there’s a type constraint placed on it.

NB: The pseudocode can be tried out using the Funcy app, which can be downloaded for free from Apple’s App Store (iOS/macOS), Google Play (Android) or Amazon Appstore. The code to be executed must be placed in a main {} block.



Functors

A functor is a type operator equipped with a map method declared as follows:

type Functor[T] {
  func map[U](f Func[T,U]) Self[U]
}

The map method must satisfy some formal requirements that we ignore here for now. The important point is that map takes a function of type Func[T,U] (where U is a type argument of the method) and returns an instance of type Self[U], that is, the same functor possibly with a different type argument. You’ve already met the Maybe functor:

type Maybe[T] : Functor[T] {
  property val T

  func map[U](f Func[T,U]) Self[U] {
    return new Self[U] {
      val = self.val.isNil() ? nil : f(self.val)
    }
  }

  func description() String {
    return self.val.isNil() ? "none" : self.val.description()
  }
}

In the next section, we’ll use Maybe to explain what a monad is and how a generic Monad type can be implemented.

NB: The pseudocode can be tried out using the Funcy app, which can be downloaded for free from Apple’s App Store (iOS/macOS), Google Play (Android) or Amazon Appstore. The code to be executed must be placed in a main {} block.