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 else x::(ins (leq, xs, y)) end end

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 `orderedSet`

s:

val r = empty ((x, y) => x <= y) for i in 1 to 10 do r = insert r (random i) end 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`

- 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`

. - Instead of
`insert (r, x)`

we just want to write`r + x`

. - Instead of
`toList r`

it should be OK to write`r.list`

. - We want to be able to write
`for x in r do ... end`

- We want to be able to write
with empty leq do yield a yield b yield c end

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)) end /* 5. */ def collector_close_ = this def collector_add_ x = this + x def empty = orderedSet (leq, []) end

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