The Artima Developer Community
Sponsored Link

Weblogs Forum
Static Behavioral Subtyping and Heron Traits

17 replies on 2 pages. Most recent reply: Jan 13, 2006 1:30 AM by Howard Lovatt

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 17 replies on 2 pages [ 1 2 | » ]
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Static Behavioral Subtyping and Heron Traits (View in Weblogs)
Posted: Jan 2, 2006 4:12 PM
Reply to this message Reply
Summary
The latest HeronFront prototype now provides traits which support structural subtyping (duck typing), and behavioral subtyping. This extensions should prove very interesting to people who are interested in agile programming methodologies, and programming with contracts.
Advertisement
Heron traits are similar to Scala traits with some enhancements. Like Scala, in Heron a trait corresponds to a type, similar to Java interfaces. For example here is the a Stack trait in Heron:
  trait Stack[type Element] {
    requires {
      def push(Element x);
      def pop() : Element;
      def is_empty() : bool;
    }
  }
The C++ code generated for trait references act as polymorphic pointers to any objects which implement a trait's requirements.

Unlike Java and Scala, Heron traits support structural subtyping (a.k.a duck typing). This means that a trait reference type can be bound to any class which provides the required function signatures. For example consider the following C++ class which implicitly implement the Heron Stack trait:

  struct simple_stack {
    simple_stack() : cnt(0) { }
    static const int max = 42;
    void push(int n) {
      if (cnt > max) throw 0;
      data[cnt++] = n;
    }
    int pop() {
      return data[--cnt];
    }
    bool is_empty() {
      return count() == 0;
    }
    int count() {
      return cnt;
    }
    int get(uint n) {
      return data[n];
    }
    void set(uint n, int x) {
      data[n] = x;
    }
  private:
    int data[max + 1];
    int cnt;
  };
The simple_stack class can then be used with the generated trait reference object as follows:
  void fill_stack(Stack<int> stack, int cnt) {
    for (int i=0; i < cnt; ++i) {
      stack.push(i);
    }
  }

  int main(int argc, char* argv[])
  {
    simple_stack stack;
    fill_stack(stack, 13);
    return 0;
  }
Like Scala traits, and unlike Java interfaces, Heron traits allow the definition of new functions which call trait functions. For instance:
  trait Indexable[type Element] {
    requires {
      def get(uint n) : Element;
      def set(uint n, Element x);
      def count() : uint;
    }
    public {
      def is_empty() : bool {
        return count() = 0;
      }
    }
  }
Where Heron becomes even more interesting is that it introduces partially implemented required functions. These have a huge benefit of enforcing behavioral subtyping by verifying preconditions and postconditions of the various member functions. For example the Stack trait can be written as:
  trait Stack[type Element] {
    requires {
      def push(Element x) {
        _override;
        assert(!is_empty());
      }
      def pop() : Element {
        assert(!is_empty());
        _override;
      }
      def is_empty() : bool;
    }
  }
The _override keyword delegates the function call to the appropriate concrete implementation of the function. This is an example of programming with contracts, where the trait not only specifies the interface, but the contractual obligations of the implementation.

The idea of introducing semantic information into traits addresses one of the biggest concerns with interfaces and structural subtyping, which have been raised numerous times by countless professionals and researchers.

For example a recent blog post at Artima by Eamonn McManus, brings up the issue of lack of behavioral (or semantic) information in Java interfaces as a reason to be prudent with the usage of Java interfaces.


Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 2, 2006 7:08 PM
Reply to this message Reply
I am intrigued by your _override construct which is the same (?) as the Simula/Beta construct inner. This is a construct other language designers have not favoured, e.g. Bertrand Meyer in Object-Oriented Sodtware Construction (page 1122 2nd ed.) finds failt with it. Many people favour:
abstract class Stack< E > {
    public final push( E e ) {
        pushInnerBody( e );
        assert !isEmpty();
    }
    protected abstract pushInnerBody( E e );
    ...
}

Because:

1. It is not an extra construct

2. It is clear that push surrounds pushInnerBody with extra stuff

3. It is clear that you are calling push and not pushInnerBody alone

Why do you think construct inner is superior?

Daniel Berger

Posts: 1373
Nickname: djberg96
Registered: Sep, 2004

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 2, 2006 9:54 PM
Reply to this message Reply
What happens in the event a class mixes in (if that's the appropriate terminology) two Traits with identical methods, both with partial, but different, implementations?

Or can you only mix in one trait?

- Dan

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 2, 2006 10:09 PM
Reply to this message Reply
> What happens in the event a class mixes in (if that's the
> appropriate terminology) two Traits with identical
> methods, both with partial, but different,
> implementations?
>
> Or can you only mix in one trait?

With standard Traits you have to exclude one or rename one - not sure with Heeron.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 2, 2006 11:43 PM
Reply to this message Reply
> I am intrigued by your _override construct
> which is the same (?) as the Simula/Beta construct
> inner.

I'll have to admit a lack of familiarity with Simula and Beta, so I should probably rename "_override" to "_inner".

> This is a construct other language
> designers have not favoured, e.g. Bertrand Meyer in
> Object-Oriented Sodtware Construction (page 1122 2nd ed.)

Unfortunately I don't have that book, perhaps you could summarize his rationale?

<snip/>

> Because:
>
> 1. It is not an extra construct
>
> 2. It is clear that push surrounds
> pushInnerBody with extra stuff
>
> 3. It is clear that you are calling push and
> not pushInnerBody alone
>
> Why do you think construct inner is superior?

As you probably realize you can still implement such a pattern using the Heron traits:


trait Stack[type E] {
public {
push( E e ) {
pushInnerBody( e );
assert(!isEmpty());
}
pop() : E {
assert(!isEmpty());
result = popInnerBody();
}
}
requires {
pushInnerBody( E e );
popInnerBody( ) : E;
isEmpty() : bool;
}
}


This is more code and complexity than neccessary. One example, where I prefer to only have a single set of function signatures is when I view a trait as a contract, containing a list of functions which need to be implemented along with their preconditions, and postconditions.


trait StackWithContract[type E] {
requires {
push( E e ) {
_override;
postcondition(!isEmpty());
}
pop() : E {
precondition(!isEmpty());
_override;
}
isEmpty() : bool;
}
}


To be honest though, I don't see really see any disadvantage of using _override.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 4:30 AM
Reply to this message Reply
> > This is a construct other language
> > designers have not favoured, e.g. Bertrand Meyer in
> > Object-Oriented Sodtware Construction (page 1122 2nd
> ed.)
>
> Unfortunately I don't have that book, perhaps you could
> summarize his rationale?

Meyer's main objection in the context of a Trait is that it is not easy to say what a method which is derived from another does, since without looking at its super method you don't know what if any aspects of the super method are used when you call the derived method.

> As you probably realize you can still implement such a
> pattern using the Heron traits:
>
>

> trait Stack[type E] {
> public {
> push( E e ) {
> pushInnerBody( e );
> assert(!isEmpty());
> }
> pop() : E {
> assert(!isEmpty());
> result = popInnerBody();
> }
> }
> requires {
> pushInnerBody( E e );
> popInnerBody( ) : E;
> isEmpty() : bool;
> }
> }
>


This isn't quite the same since push and pop should be final to prevent the contracts from being circumvented.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 12:46 PM
Reply to this message Reply
> Meyer's main objection in the context of a Trait is that
> it is not easy to say what a method which is derived from
> another does, since without looking at its super method
> you don't know what if any aspects of the super method are
> used when you call the derived method.

This is essentially the same as saying you can't know what any function does without knowing what the functions it calls does, true but not particularly relevant (IMHO).

> > As you probably realize you can still implement such a
> > pattern using the Heron traits:
> >
> >

> > trait Stack[type E] {
> > public {
> > push( E e ) {
> > pushInnerBody( e );
> > assert(!isEmpty());
> > }
> > pop() : E {
> > assert(!isEmpty());
> > result = popInnerBody();
> > }
> > }
> > requires {
> > pushInnerBody( E e );
> > popInnerBody( ) : E;
> > isEmpty() : bool;
> > }
> > }
> >

>
> This isn't quite the same since push and pop should be
> final to prevent the contracts from being circumvented.

In Heron the notion of final is obsolete, there are no virtual functions. Any need for polymorphism is achieved through trait reference types. Dispatching calls through a trait reference will never circumvent the contract. Direct calls to the concrete type will not know about the contract (there is an exception to this explained below).

HeronFront doesn't support Heron classes, but is compatible with C++ classes, so consider the following C++ class:


template<typename T>
struct stack {
void push(T x) {
m.push_back(x);
}
T pop() {
T ret = m.back();
m.pop_back();
return ret;
}
bool is_empty() {
return m.empty();
}
private:
std::vector<T> m;
};


Now here is how you could use the code:


stack<int> s; // C++ class
s.pop(); // contract checking off, I believe undefined behaviour occurs
Stack<int> ts = s; // HeronFront generated trait reference
ts.pop(); // contract checking on, violation reported


So yes, in this scenario the contract checking can be violated if the consumer of the stack data type is given access to the raw type, rather than just the trait. I believe the argument was already made that in some cases either of the two versions is more appropriate and it is important for the software developer be able to choose.

Now finally, there is the case of how to implement a class which protects itself using the contract. This isn't implemented yet, but it will be achieved through delegations.


template<typename T>
struct raw_stack_impl {
...
};

template<typename T>
struct stack {
delegates_Stack(T, m); // this is a macro
private:
raw_stack_impl<T> m;
};


The delegation macro will be generated by the next version of HeronFront.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 5:10 PM
Reply to this message Reply
> > Meyer's main objection in the context of a Trait is
> that
> > it is not easy to say what a method which is derived
> from
> > another does, since without looking at its super method
> > you don't know what if any aspects of the super method
> are
> > used when you call the derived method.
>
> This is essentially the same as saying you can't know what
> any function does without knowing what the functions it
> calls does, true but not particularly relevant (IMHO).

I think he is refering to this when you don't have access to the source of the super method, i.e. what does one in the following do (it is written in Java but imagine that Java had an inner construct):
class Derived extends Base {
    int one() { return 1; }
 
    public static final void main( String[] notUsed ) {
        final Derived d = new Derived();
        System.out.println( d.one() );
    }
}

The answer is that you can't tell what one does because you don't know if Base has a one method that uses inner. EG suppose that Base was:
class Base {
    int one() { inner; return 2; }
}

Then the above example would print 2! The problem is that when looking at Derive you have no clue that one in Base uses inner.

It is quite possible that I have misunderstood your _override construct, but this is how inner works :)

> > >

> > > trait Stack[type E] {
> > > public {
> > > push( E e ) {
> > > pushInnerBody( e );
> > > assert(!isEmpty());
> > > }
> > > pop() : E {
> > > assert(!isEmpty());
> > > result = popInnerBody();
> > > }
> > > }
> > > requires {
> > > pushInnerBody( E e );
> > > popInnerBody( ) : E;
> > > isEmpty() : bool;
> > > }
> > > }
> > >

> >
> > This isn't quite the same since push and pop should be
> > final to prevent the contracts from being circumvented.

On the same tack of probably mis-understanding your language I am assuming that the following would be possible:


trait StackNoChecks[type E] extends Stack[E] {
public {
push( E e ) {
pushInnerBody( e );
// assert(!isEmpty()); -- no assert
}
pop() : E {
// assert(!isEmpty()); -- no assert
result = popInnerBody();
}
}
requires {
pushInnerBody( E e );
popInnerBody( ) : E;
isEmpty() : bool;
}
}

I probably got your syntax wrong (as well as misunderstanding you :) ), but I think you will get the point. Why doesn't StackNoChecks turn off the checks?

PS I find the type declarations odd, e.g.:

pushInnerBody( E e );
popInnerBody( ) : E;

Why not like Scala:

pushInnerBody( e : E );
popInnerBody( ) : E;

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 6:29 PM
Reply to this message Reply
> It is quite possible that I have misunderstood your
> _override construct, but this is how
> inner works :)

That is not how _override works. Comparing to Java examples is pretty meaningless, because functions aren't virtual.
Consider the following:


trait TFuBar {
requires {
FuBar() { _override; }
}
}

class CFuBar {
public {
FuBar() { writeln("fubar"); }
}
}

CFuBar cfb;
TFuBar tfb = cfb;
tfb.FuBar(); // prints "fubar"


Does that make sense? The _override is like a call to the concrete object that the trait reference is bound to.

Perhaps the page at http://www.heron-language.com/heronfront.html is more clear.

> On the same tack of probably mis-understanding your
> language I am assuming that the following would be
> possible:
>
>

> trait StackNoChecks[type E] extends Stack[E] {
> public {
> push( E e ) {
> pushInnerBody( e );
> // assert(!isEmpty()); -- no assert
> }
> pop() : E {
> // assert(!isEmpty()); -- no assert
> result = popInnerBody();
> }
> }
> requires {
> pushInnerBody( E e );
> popInnerBody( ) : E;
> isEmpty() : bool;
> }
> }
>

> I probably got your syntax wrong (as well as
> misunderstanding you :) ), but I think you will get the
> point. Why doesn't StackNoChecks turn off the
> checks?

I am confused StackNoChecks doesn't turn off anything, it simply doesn't make any checks. However, you would have a compilation error because you are reintroducing the requires functions which are inherited from Stack[E]. The correct way to do it is:


trait StackWithChecks[type E] {
public {
push( E e ) {
pushInnerBody( e );
assert(!isEmpty());
}
pop() : E {
assert(!isEmpty());
result = popInnerBody();
}
}
requires {
pushInnerBody ( E e );
popInnerBody () : E;
isEmpty();
}
}

trait StackNoChecks[type E] {
inherits {
Stack[E];
}
public {
push( E e ) {
pushInnerBody( e );
// assert(!isEmpty()); -- no assert
}
pop() : E {
// assert(!isEmpty()); -- no assert
result = popInnerBody();
}
}
}


In this case the public functions from push and pop hide the public push and pop in StackNoChecks[T].

> PS I find the type declarations odd, e.g.:
>

> pushInnerBody( E e );
> popInnerBody( ) : E;
>

> Why not like Scala:
>

> pushInnerBody( e : E );
> popInnerBody( ) : E;
>


Yeah, I guess you are right, might as well go the whole nine yards. I didn't give it a whole lot of thought, the syntax just kind of happened that way. I happen to prefer types after functions, but before parameters. I am weird I guess. Though I am torn between appealing to Pascal/Scala programmers and C++/Java programmers.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 8:00 PM
Reply to this message Reply
Sounds like I missunderstood your construct I was expecting that:

trait Base {
public {
one() : int { _override; return 2; }
}
}

class Derived { // Derrived by structural equivalence
public {
one() : int { return 1; }
}
}

Derived d;
Base b = d;
writelin( b.one() ); // prints 2?

> I am confused StackNoChecks doesn't turn off anything, it
> simply doesn't make any checks. However, you would have a
> compilation error because you are reintroducing the
> requires functions which are inherited from Stack[E]. The
> correct way to do it is:
>

trait StackWithChecks[type E] {
public {
push( E e ) {
pushInnerBody( e );
assert(!isEmpty());
}
pop() : E {
assert(!isEmpty());
result = popInnerBody();
}
}
requires {
pushInnerBody ( E e );
popInnerBody () : E;
isEmpty();
}
}

trait StackNoChecks[type E] {
inherits {
Stack[E];
}
public {
push( E e ) {
pushInnerBody( e );
// assert(!isEmpty()); -- no assert
}
pop() : E {
// assert(!isEmpty()); -- no assert
result = popInnerBody();
}
}
}

> In this case the public functions from push and pop hide
> the public push and pop in StackNoChecks[T].

I guess in the above code you meant inherits from StackWithChecks not Stack. And in the above paragraph you are saying that push and pop in StackNoCheck hide push and pop in StackWithChecks. This is the situation that the final declarations in the Java version prevent, i.e. it prevents you from writing a StackNoCheck that inherits from StackWithChecks and that this is desirable because StackWithChecks has the checks for good reason!

As you have hinted in your replies, you can't do final because you are allowing structural type matching. So this is probably a pro and con of a design decision. If you allow structural matching then some control is lost. But if you want structural matching then that is the way it is.

> > PS I find the type declarations odd, e.g.:
> >

> > pushInnerBody( E e );
> > popInnerBody( ) : E;
> >

> > Why not like Scala:
> >

> > pushInnerBody( e : E );
> > popInnerBody( ) : E;
> >

>
> Yeah, I guess you are right, might as well go the whole
> nine yards. I didn't give it a whole lot of thought, the
> syntax just kind of happened that way. I happen to prefer
> types after functions, but before parameters. I am weird I
> guess. Though I am torn between appealing to Pascal/Scala
> programmers and C++/Java programmers.

I don't mind almost any syntax, I soon learn it, but I did think the mix of the two styles was odd. If it helps with your decision, there are many more Algol/Fortran/C/C++/Java programmers than Pascal/Scala/Delphi/Modula programmers :)

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 8:27 PM
Reply to this message Reply
> I guess in the above code you meant inherits from
> StackWithChecks not Stack.

Yes thank you.

> And in the above
> paragraph you are saying that push and pop in StackNoCheck
> hide push and pop in StackWithChecks. This is the
> situation that the final declarations in the Java version
> prevent, i.e. it prevents you from writing a StackNoCheck
> that inherits from StackWithChecks and that this is
> desirable because StackWithChecks has the checks for good
> reason!

If that is the behaviour you want then you should instead have written:


trait StackWithChecks[type E] {
requires {
push( E e ) {
_override;
assert(!isEmpty());
}
pop() : E {
assert(!isEmpty());
_override;
}
isEmpty() : bool;
}
}


This way any new trait inheriting from this one has to maintain the checks.

> As you have hinted in your replies, you can't do final
> because you are allowing structural type matching. So this
> is probably a pro and con of a design decision. If you
> allow structural matching then some control is lost.

I don't consider the lack of final a loss at all. Final is really only meaningful in traditional OOP models where inheritance is an approximation of subtyping. In Heron subtyping is only through the structural / behavioural technique of using traits. The idea that a class should control how it is inherited (e.g. through final or protected methods) then becomes irrelevant. At least that is my opinion on the matter.

> I don't mind almost any syntax, I soon learn it, but I did
> think the mix of the two styles was odd. If it helps with
> your decision, there are many more
> Algol/Fortran/C/C++/Java programmers than
> Pascal/Scala/Delphi/Modula programmers :)

Good point.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 9:15 PM
Reply to this message Reply
Thanks for spending the time explaining your construct, unfortunately I still have some questions? Below is an example and the questions I have are in the comments.

trait Base {
public {
one() : int { _override; return 11; }
}
requires {
two() : int { _override; return 22; }
}
}

class Derived { // Derrived by structural equivalence
public {
one() : int { return 1; }
two() : int { return 2; }
}
}

Derived d;
writelin( b.one() ); // prints 1?
writelin( b.two() ); // prints 2?
Base b = d; // Is this a syntax error?
writelin( b.one() ); // prints 1?
writelin( b.two() ); // prints 22?

PS I can't run HerronFront since I don't have C++.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 9:20 PM
Reply to this message Reply
Oops posting error, testing code should be:

Derived d;
writeln( d.one() ); // prints 1?
writeln( d.two() ); // prints 2?
Base b = d; // Is this a syntax error?
writeln( b.one() ); // prints 1?
writeln( b.two() ); // prints 22?

The first two writes use d not as originally posted b - sorry.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 4, 2006 10:27 PM
Reply to this message Reply
> Oops posting error, testing code should be:
>

> Derived d;
> writeln( d.one() ); // prints 1?
> writeln( d.two() ); // prints 2?
> Base b = d; // Is this a syntax error?
> writeln( b.one() ); // prints 1?
> writeln( b.two() ); // prints 22?
>

> The first two writes use d not as originally posted b -
> sorry.

This is correct on all fronts except for:


writeln( b.one() ); // prints 11 not 1.


When accessing a trait, you can't access the underlying object. The public methods of a trait, are specific to the trait type itself. I almost called them "extensions" to reflect this, and I may revert to that nomenclature to avoid future confusions.

I appreciate you trying to learn how Heron works, it is helping me to learn how to explain my ideas better.

W.r.t HeronFront, I plan on eventually bundling it with gcc, so that anyone can use it.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Static Behavioral Subtyping and Heron Traits Posted: Jan 5, 2006 12:26 AM
Reply to this message Reply
Unfortunately now I don't get the difference between public and requires. Are the following assumptions correct?

trait Base {
public {
one() : int { _override; return 11; }
}
requires {
two() : int { _override; return 22; }
}
}

trait Derived {
inherits {
Base
}
public {
one() : int { _override; return 111; }
}
requires {
two() : int { _override; return 222; }
}
}

class DerivedClass { // Derived by structural equivalence
public {
one() : int { return 1; }
two() : int { return 2; }
}
}

// As before but with corrected output for b.one()
DerivedClass dc;
writelin( dc.one() ); // prints 1
writelin( dc.two() ); // prints 2
Base b = dc; // OK
writelin( b.one() ); // prints 11
writelin( b.two() ); // prints 22
// New with questions
Derived d = dc; // OK?
writelin( d.one() ); // prints 111?
writelin( d.two() ); // prints 222?

Flat View: This topic has 17 replies on 2 pages [ 1  2 | » ]
Topic: Use cases for Generics Previous Topic   Next Topic Topic: Are Web Services an Investment or an infinite Cost?


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us