In #848, mwanji mentioned Objects Are Not Hash Tables -- an interesting discussion which led me to a Lambda the Ultimate thread about Guy Steele's article which references William Cook's paper On Understanding Data Abstraction, Revisited ...

Anyway, Cook uses Integer Set as his example, talking about using closures to implement a form of Object-Oriented (as opposed to Class-oriented) programming. That is, objects shouldn't see into each other's internals.

Here's my shot at a Fantom version of some of Cook's examples. This works fine as a non-const class, but uncommenting the /*const*/ modifiers gives toImmutable errors.

This isn't "real code", just a learning experiment. I wanted to see whether Fantom could neatly implement that FP style from Cook's paper. I got this far, and am now a bit over my head: not sure if there's something in Fantom's Immutable Functions rules that explains this.

mixin ISet {
  abstract Bool isEmpty()
  abstract Bool contains(Int i)
  abstract ISet insert(Int i)
  abstract ISet union(ISet s)
}

/*const*/ class ISetImpl : ISet
{
  override Bool isEmpty()       { (isEmptyFunc)() }
  override Bool contains(Int i) { (containsFunc)(i) }
  override ISet insert(Int i)   { (insertFunc)(i) }
  override ISet union(ISet s)   { (unionFunc)(s) }

  private /*const*/ |     ->Bool| isEmptyFunc
  private /*const*/ |Int  ->Bool| containsFunc
  private /*const*/ |Int  ->ISet| insertFunc
  private /*const*/ |ISet ->ISet| unionFunc

  ** the empty set
  new Empty()
  {
    isEmptyFunc  = |      ->Bool| { true }
    containsFunc = |Int  i->Bool| { false }
    insertFunc   = |Int  i->ISet| { Insert(this, i) }  // ERROR NotImmutableError
    unionFunc    = |ISet s->ISet| { s }
  }
  ** the union of s1 and n
  new Insert(ISet s1, Int n)
  {
    //if (s1.contains(n))
    //  return s1
    //else
    isEmptyFunc  = |      ->Bool| { false }
    containsFunc = |Int  i->Bool| { i == n || s1.contains(i) }  // ERROR: toImmutable
    insertFunc   = |Int  i->ISet| { Insert(s1, i) }
    unionFunc    = |ISet s->ISet| { Union(s1, s) }
  }
  ** the union of s1 and s2
  new Union(ISet s1, ISet s2)
  {
    isEmptyFunc  = |      ->Bool| { false }
    containsFunc = |Int  i->Bool| { s1.contains(i) || s2.contains(i) }
    insertFunc   = |Int  i->ISet| { Insert(this, i) }
    unionFunc    = |ISet s->ISet| { Union(this, s) }
  }
  ** the set of even integers
  new Even()
  {
    isEmptyFunc  = |      ->Bool| { false }
    containsFunc = |Int  i->Bool| { i % 2 == 0 }
    insertFunc   = |Int  i->ISet| { Insert(this, i) }
    unionFunc    = |ISet s->ISet| { Union(this, s) }
  }
  ** the set of all integers
  new Full()
  {
    isEmptyFunc  = |      ->Bool| { false }
    containsFunc = |Int  i->Bool| { true }
    insertFunc   = |Int  i->ISet| { this }
    unionFunc    = |ISet s->ISet| { this }
  }
  ** the set of integers from 'n' to 'm'
  new Interval(Int n, Int m)
  {
    isEmptyFunc  = |      ->Bool| { n > m }
    containsFunc = |Int  i->Bool| { n <= i && i <= m }
    insertFunc   = |Int  i->ISet| { Insert(this, i) }
    unionFunc    = |ISet s->ISet| { Union(this, s) }
  }

  static Void main()
  {
    a := Insert(Empty, 1)
    b := Insert(a, 3)
    echo(b.contains(3))

    echo(! Empty.insert(3).union(Empty.insert(1)).insert(5).contains(4))
    echo(Interval(5, 9).contains(6))
    echo(Empty.union(Interval(1,3)).contains(2))
    echo(Full.contains(3))
    echo(Full.insert(2).contains(3))
  }
}

If you make ISet a const mixin then everything appears to work:

const mixin ISet {
   abstract Bool isEmpty()

Try that and see how it works for you.

BTW: very interesting exercise :-)

Ah. You're right; it does. const mixin never occurred to me, but it makes sense: not that the mixin itself has const data, but that using the mixin implies immutability, which is the intent here.

Here's a gem from the "On Understanding Data Abstraction" essay:

Object-oriented programming is designed to be as flexible as
possible.  It is almost as if it were designed to be as
difficult to verify as possible.

Anyways, very cool experiment here.

I had a few ideas to the interfaces more idiomatic with Fantom:

• Use Range for the Interval constructor.

  set := Interval(5..9)
  echo( set.contains(6) ) // true

• Implement the or method as an alias for union:

  set := Interval(5..9) | Interval(12..20)
  echo( set.contains(10) ) // false

• Implement the plus method as an alias for add:

  set := Empty() + 2 + 3 + 4 // { 2, 3, 4 }

Interval.isEmptyFunc should read n < m not n > m

Thanks Kevin! Very interesting technique

Isn't the implementation of Union#isEmptyFunc wrong? It can happen that both s1 and s2 are the empty set.

EDIT: I see it is the same in Cook's paper. Weird, I must be missing something...

That got me too; but Empty#unionFunc just returns the other set, so Empty.union(Empty) devolves to Empty which answers true to isEmpty. The Union constructor method is only called by those unionFunc's that need it.

There is a bug in the Insert constructor, though; apparently

insertFunc   = |Int  i->ISet| { Insert(s1, i) }
unionFunc    = |ISet s->ISet| { Union(s1, s) }

should be:

insertFunc   = |Int  i->ISet| { Insert(this, i) }
 unionFunc    = |ISet s->ISet| { Union(this, s) }

With that change, and with these added to the ISet mixin:

ISet or(ISet s2) { union(s2) }
ISet plus(Int i) { insert(i) }

this qualidafial example

//Implement the plus method as an alias for add:
set = Empty + 2 + 3 + 4 // { 2, 3, 4 }
echo(set.contains(2) && set.contains(3) && set.contains(4))

works. :-)

Its a pretty cool exercise - I wonder what this code would look like in Java :-)