On Types, Part VI: Abstract Datatypes

So far we have only had examples for type definitions where outer values and inner values were the same. For abstract datatypes, this is usually not the case: the inner value determines the internal representation of the datatype, and the outer value determines how the datatype looks like to its clients.

To examine abstract datatypes in Babel-17, let us define a new type orderedSet which represents sets that are ordered by a given order:

module com.obua.util.orderedSet

private (orderedSet), ins

typedef orderedSet (leq, list) = nil

def empty leq = (leq, [])
def insert (orderedSet (leq, list), y) = (orderedSet (leq, ins (leq, list, y))
def toList (orderedSet (leq, list)) = list

def ins (leq, [], y) = [y]
def ins (leq, x::xs, y) =
    if leq (y, x) then
        if leq (x, y) then x::xs else y::x::xs end
        x::(ins (leq, xs, y))

To use this module somewhere else in our code, we first import it via

import com.obua.util.orderedSet

Now we can play around with orderedSets:

val r = empty ((x, y) => x <= y)
for i in 1 to 10 do
  r = insert r (random i)
toList r

Note that the only way for us to create values of type orderedSet is by calling empty and insert, because of the declaration private (orderedSet). Note also that there is no other way to see the elements of an orderedSet except via the toList function.

There may be other types around which also have an empty function to create empty versions of them. If we want to use these types together, it will be inconvenient to import the com.obua.util.orderedSet module. It is then more convenient to import com.obua.util and to write orderedSet.empty and orderedSet.insert. The only thing that is somewhat ugly is that now we have to refer to the type via orderedSet.orderedSet. But we can remedy this by introducing the following rule into Babel-17: if the name of a type is the same as the name of the module it is defined in, then the name of the module can be used as a synonym for the name of the type. In our case this means that the type com.obua.util.orderedSet.orderedSet is also accessible as com.obua.util.orderedSet.

We would like to add the following features to orderedSet

  1. ordered sets should be comparable in a way that makes sense; right now, the expression
    insert (empty leq, 1) == insert (empty leq, 2) evaluates to true because both values have outer value nil.

  2. Instead of insert (r, x) we just want to write r + x.
  3. Instead of toList r it should be OK to write r.list.
  4. We want to be able to write for x in r do ... end
  5. We want to be able to write
    with empty leq do 
      yield a 
      yield b 
      yield c 

We can achieve this (and much more, see section 25.8 in the Babel-17 reference) by replacing the outer value nil with an object that implements the desired functionality. Therefore we replace the line typedef orderedSet (leq, list) = nil by the following:

typedef orderedSet (leq, mylist) = object

/* 1. */
def rank_ = mylist

/* 2. */
def plus_ x = insert (this, x)

/* 3. */
def list x = mylist

/* 4. */
def iterate_ = 
    match mylist 
        case [] => () 
        case (x::xs) => (x, orderedSet (leq, xs))

/* 5. */
def collector_close_ = this
def collector_add_ x = this + x
def empty = orderedSet (leq, [])


Note that we reintroduced the keyword this into the Babel-17 language, and also note that the above code only works if this does not refer to the original object definition, but to the object definition that has been retyped as an orderedSet. Applying the same reasoning to object inheritance, we can resolve our earlier beef with this that led to the temporary removal of this from Babel-17.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: