Typical Types of Typing and the Types They Typify, Part 2

Note: This is the conclusion of a two-part entry in my ongoing “Road to Wheeler” series.

In my last post I covered some of the popular type schemes used in programming today. I continued a little past where most discussions of type go when I pulled in pattern matching.

Deconstructing Types

Imagine that you are using a language with no data types and you want to implement some of the typing behavior that I showed in my last post. One way you might do it is with a record used to associate type information with a value.

A C-style int might look something like this:

x = (int, 5)

That’s pretty simple. We’re storing our value along with it’s type. Using that same scheme we can also represent a typical object instance:

vendor = (Vendor, FirstName, LastName)

“Vendor” here is the classname, but it could also be an interface name. Or the record could contain a list of interfaces supported. Or, a list of methods implemented.

The pattern matching example from last time is already in record format. We’ll just change the Erlang braces to parentheses for continuity with the other examples:

(customer, FirstName, LastName)

Let’s list all of these records together to compare them:

(int, 5)
(Vendor, FirstName, LastName)
(customer, FirstName, LastName)

See the similarity? The types are from different methodologies, but they boil down to equivalent concepts.

Our Own Imaginary Type Implementation

I could easily define a function in my imaginary typeless language to properly handle any of these records:

def display(record):

	type = record[0] # Key off first item in the record.

	if type == int:
		print_int(record)

	elif type == Vendor:
		print_vendor(record)

	elif type == customer:
		print_customer(record)

Is pattern matching a typing scheme? Do typing schemes devolve to pattern matching?

One thing I left out of my pattern matching example from last time: Patterns can match concrete values, such as specific numbers. In this example I’m expecting to find out just how overdue a customer’s account is:

bill_with_msg({customer, 0}) -> send_bill("Here's your new bill.");
bill_with_msg({customer, DaysOverdue}) -> send_bill("Your bill is ~p days overdue.", DaysOverdue).

The first pattern matches on the atom “customer” and the specific value of 0 for the number of days overdue.

If we rewrote this in our typeless language with records it might look something like this:

def bill_with_msg(record):

	type = record[0]
	days_overdue = record[1]

	if days_overdue == 0:
		send_bill("Here's your new bill")
	else:
		send_bill("You're bill is $days_overdue days overdue.")

Guards Point The Way

Have you seen guards? They’re pretty handy. Here’s an example of guards in Erlang:

bill_with_msg({customer, 0}) -> send_bill("New bill.");
bill_with_msg({customer, DaysOverdue}) when DaysOverdue <= 30 -> send_bill("Your bill is overdue.");
bill_with_msg({customer, DaysOverdue}) when DaysOverdue > 30 -> send_bill("YOUR BILL IS SERIOUSLY OVERDUE. PLEASE PAY NOW.").

Those “when” clauses are guards. And they’re pretty nice. In a fairly concise and clear way we’ve expressed our desire to do several things with relatively little code. In the process we’ve managed to unlock a new dimension to typing. If you accept that typing is essentially pattern matching you can see that the guards are actually adding extra dimension to our types by letting us do very specific pattern matching.

The trouble with guards is that they are bound to a function. What if you want to capture a certain type of customer (one who has spent more than $10k this year) so you can target them directly? You might find yourself with functions like this:

bill_customer(customer, spent) when spent > 10000 -> preferred_billing().

find_shipping_options(customer, spent) when spent > 10000 -> preferred_shipping().

lookup_special_offers(customer, spent) when spent > 10000 -> offer_preferred_promos().

That’s a lot of repetition; a code smell. If you’re an OO type of person you might break that kind of customer out into it’s own class, generated by a factory. Or perhaps you might decorate your customer objects with particular account classes. And of course there might be many other strategies.

This might also be a good place for a macro if you’re a Lisper.

Another way might be to declare a type with the guard built-in. Here’s one way this might work with some made-up syntax:

typedef Customer = Customer when spent < 10000
typedef GoldCustomer = Customer when spent >= 10000 and spend < 10000
typedef PlatinumCustomer = Customer when spent >= 100000

Here we’re creating some concise types on top of an existing type. Instead of subtyping or aggregating classes, we’re taking a class or data structure (Customer) and describing some situations where we’d like it to be treated specially. Now we can have polymorphic behavior on anything – types, values, or ranges of values.

This scheme will stretch a little farther:

typedef Spam = String when contains "viagra"

def proc_mail(Spam msg):
	mark_and_toss()

def proc_mail(String msg):
	deliver(msg)

Of course you can only do this with lazy type evaluation, so there’s some runtime cost. I’m ok with that. Laziness has its virtues.

What I’ve presented so far is interesting but still rather flat. We can go farther. What if we can look at the shape of things too? After all, an interface represents a sort of shape. What if you just want to support objects that have a “Text” property? What if you only want to deal with Customers who have blue items in their RecentPurchases collection? Or more abstractly, what if we only want to deal with objects that expose a hashtable containing other hashtables?

Sound weird? It shouldn’t. It happens all the time, it just depends on the environment you work and code in. See also: jQuery, LINQ, RSpec, Hamcrest, etc., etc..

This Way To The Egress

I haven’t seen a type system that does exactly what I describe. Maybe you have. If so I hope you’ll tell me about it. Haskell’s type system is pretty nice (and I’m still learning), but seems to stop short of the dynamic behavior I’m looking for. Wheeler, the language I’m working on, aims (at least in part) for something very much like this.