www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - The Non-Virtual Interface idiom in D

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
In this article:

http://www.gotw.ca/publications/mill18.htm

Herb Sutter makes a powerful argument that overridable functions 
(customization points) should actually not be the same as the publically 
available interface. This view rhymes with the Template Method pattern 
as well.

This leads to the interesting setup in which an interface should ideally 
define some signatures of to-be-defined functions, but disallow client 
code from calling them. For the clients, the same interface should 
expose some higher-level final functions.

Ignoring for the moment access protection semantics in D (which are 
broken anyway), let's say this would work:

interface Cloneable(T) if (is(T == class))
{
     private T doClone(); // must implement but can't call
     T clone()            // this is what everybody can call
     {
         auto result = doClone();
         assert(typeof(result) == typeof(this));
         assert(this.equals(result));
         return result;
     }
}

So clients must implement doClone, but nobody can ever call it except 
Cloneable's module. This ensures that no cloning ever gets away with 
returning the wrong object.

Pretty powerful, eh? Now, sometimes you do want to allow a derived class 
to call the base class implementation. In that case, the interface 
function must be protected:

interface ComparableForEquality(T)
{
     protected bool doEquals(T);
     final bool equals(T rhs)
     {
         auto result = doEquals(rhs);
         assert(rhs.equals(cast(T) this) == result);
         return result;
     }
}

The difference is that now a derived class could call super.doEquals.

This feature would require changing some protection rules, I think for 
the better. What do you think?


Andrei
Sep 25 2009
next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Sat, 26 Sep 2009 00:49:27 +0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions  
 (customization points) should actually not be the same as the publically  
 available interface. This view rhymes with the Template Method pattern  
 as well.

 This leads to the interesting setup in which an interface should ideally  
 define some signatures of to-be-defined functions, but disallow client  
 code from calling them. For the clients, the same interface should  
 expose some higher-level final functions.

 Ignoring for the moment access protection semantics in D (which are  
 broken anyway), let's say this would work:

 interface Cloneable(T) if (is(T == class))
 {
      private T doClone(); // must implement but can't call
      T clone()            // this is what everybody can call
      {
          auto result = doClone();
          assert(typeof(result) == typeof(this));
          assert(this.equals(result));
          return result;
      }
 }

 So clients must implement doClone, but nobody can ever call it except  
 Cloneable's module. This ensures that no cloning ever gets away with  
 returning the wrong object.

 Pretty powerful, eh? Now, sometimes you do want to allow a derived class  
 to call the base class implementation. In that case, the interface  
 function must be protected:

 interface ComparableForEquality(T)
 {
      protected bool doEquals(T);
      final bool equals(T rhs)
      {
          auto result = doEquals(rhs);
          assert(rhs.equals(cast(T) this) == result);
          return result;
      }
 }

 The difference is that now a derived class could call super.doEquals.

 This feature would require changing some protection rules, I think for  
 the better. What do you think?


 Andrei


Sounds pretty good. I use NVI a lot in C++, but mostly for assertion  
tests. Here is an example:

template<class T>
class InvariantChecker { /*...*/ }; calls T::checkInvariant() in ctor and  
dtor (i.e. before entering function and upon exit)

class SoundInstance
{
public:
     bool pause() {
         InvariantChecker checker(this);
         bool result = _pause();
         assert(result == isPaused());
         return result;
     }

     bool play() {
         InvariantChecker checker(this);
         bool result = _play();
         assert(result == isPlaying());
         return result;
     }

     // etc

protected:
     virtual bool _pause() = 0;
     virtual bool _play() = 0;
     virtual void checkInvariant() = 0;
};
Sep 25 2009
prev sibling next sibling parent Justin Johansson <procode adam-dott-com.au> writes:
Andrei Alexandrescu Wrote:


 In this article:
 
 http://www.gotw.ca/publications/mill18.htm
 
 Herb Sutter makes a powerful argument that overridable functions 
 (customization points) should actually not be the same as the publically 
 available interface. This view rhymes with the Template Method pattern 
 as well.
 
 This leads to the interesting setup in which an interface should ideally 
 define some signatures of to-be-defined functions, but disallow client 
 code from calling them. For the clients, the same interface should 
 expose some higher-level final functions.
 
 Ignoring for the moment access protection semantics in D (which are 
 broken anyway), let's say this would work:
 
 interface Cloneable(T) if (is(T == class))
 {
      private T doClone(); // must implement but can't call
      T clone()            // this is what everybody can call
      {
          auto result = doClone();
          assert(typeof(result) == typeof(this));
          assert(this.equals(result));
          return result;
      }
 }
 
 So clients must implement doClone, but nobody can ever call it except 
 Cloneable's module. This ensures that no cloning ever gets away with 
 returning the wrong object.
 
 Pretty powerful, eh? Now, sometimes you do want to allow a derived class 
 to call the base class implementation. In that case, the interface 
 function must be protected:
 
 interface ComparableForEquality(T)
 {
      protected bool doEquals(T);
      final bool equals(T rhs)
      {
          auto result = doEquals(rhs);
          assert(rhs.equals(cast(T) this) == result);
          return result;
      }
 }
 
 The difference is that now a derived class could call super.doEquals.
 
 This feature would require changing some protection rules, I think for 
 the better. What do you think?



I read Sutter's 2001 article just now and thought that he eloquently put into
easy to understand language the same design principle I've used in C++ since
circa 1990.  I didn't recall the name of that particular design pattern but in
my own terminology I've always referred to the publicly callable methods as the
"driver" methods; meaning those methods that may only be called to drive the
low-level contracted and customizable interface.

The beauty of this design pattern as articulated is of course, that before and
after code can be used in the public driver methods to call down to and receive
results from the interface for assertion, argument and return value type
conversion, filtering purposes etc.  Naturally to enforce what I call the
driver principle you need to make the publicly callable "driver" methods final
as indicated (I think?) in the article but certainly as in the
ComparableForEquality.equals() method of your example.

From what I can see of your proposal, this makes for better DBC
(design-by-contract) software engineering, and, especially given that there are
only benefits and no downsides, the concept is a no brainer.

So I vote, yay, go for it, Andrei!

-- Justin Johansson
Sep 25 2009
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:

 This feature would require changing some protection rules, I think for 
 the better. What do you think?


1. what are those changes?

2. did you mean to add executable code to an interface?
Sep 25 2009
next sibling parent reply language_fan <foo bar.com.invalid> writes:
Fri, 25 Sep 2009 20:07:40 -0700, Walter Bright thusly wrote:


 Andrei Alexandrescu wrote:

 This feature would require changing some protection rules, I think for
 the better. What do you think?


 
 1. what are those changes?
 
 2. did you mean to add executable code to an interface?


This starts to sound like traits (http://www.codecommit.com/blog/scala/
scala-for-java-refugees-part-5). On this road D is becoming a great 
tribute to Scala.
Sep 26 2009
parent reply Walter Bright <newshound1 digitalmars.com> writes:
language_fan wrote:

 This starts to sound like traits (http://www.codecommit.com/blog/scala/
 scala-for-java-refugees-part-5). On this road D is becoming a great 
 tribute to Scala.


D has borrowed ideas from many different languages. The trick is to take 
the good stuff and avoid their mistakes <g>.
Sep 26 2009
parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Sat, 26 Sep 2009 22:30:58 +0400, Walter Bright  
<newshound1 digitalmars.com> wrote:


 language_fan wrote:

 This starts to sound like traits (http://www.codecommit.com/blog/scala/
 scala-for-java-refugees-part-5). On this road D is becoming a great  
 tribute to Scala.


 D has borrowed ideas from many different languages. The trick is to take  
 the good stuff and avoid their mistakes <g>.


How about this one:
http://sadekdrobi.com/2008/12/22/null-references-the-billion-dollar-mistake/

:)
Sep 26 2009
next sibling parent Jason House <jason.james.house gmail.com> writes:
Denis Koroskin Wrote:


 On Sat, 26 Sep 2009 22:30:58 +0400, Walter Bright  
 <newshound1 digitalmars.com> wrote:
 

 language_fan wrote:

 This starts to sound like traits (http://www.codecommit.com/blog/scala/
 scala-for-java-refugees-part-5). On this road D is becoming a great  
 tribute to Scala.


 D has borrowed ideas from many different languages. The trick is to take  
 the good stuff and avoid their mistakes <g>.


 
 How about this one:
 http://sadekdrobi.com/2008/12/22/null-references-the-billion-dollar-mistake/
 
 :)


I'd love to see D have non-nullable references by default.
Sep 26 2009
prev sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Denis Koroskin wrote:

 How about this one:
 http://sadekdrobi.com/2008/12/22/null-references-the-billion-dollar-mistake/ 


Started new thread for this.
Sep 26 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Walter Bright wrote:

 Andrei Alexandrescu wrote:

 This feature would require changing some protection rules, I think for 
 the better. What do you think?


 
 1. what are those changes?


I thought some more about it and here are the changes in protection rules:

1. Public final methods CANNOT be hijacked in derived classes by any 
means. That means, if I see:

class Root {
     final void fun(double) {
         ...
     }
}

I can be darn sure that if I call obj.fun(5) against any class 
inheriting Root, the call will go straight to Root.fun.

One nice thing about that is that we already have very solid 
anti-hijacking rules in place, so we have a great precedence for 
consistency.

2. Private non-final (overridable) methods must be overridable in 
derived classes, even those defined in distinct modules.

3. A class overriding a method is NOT allowed to decrease encapsulation 
by relaxing the protection level of an overridden method. In particular, 
if a method is private and overridable, the function can override it but 
is unable to call super.method.

I think the above rules are enough to implement a mean NVI.


 2. did you mean to add executable code to an interface?


Yes. We need to allow final methods in interfaces. I remember I posted a 
bug to that effect. These are not problematic to implement because have 
the same binary regime as regular functions:

interface A {
     void transmogrify();
     final void transmogrifyTwice() {
         transmogrify();
         transmogrify();
     }
}

I am very excited about this development, particularly because we can 
get tricky things like opEquals right.


Andrei
Sep 27 2009
prev sibling next sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
Andrei Alexandrescu wrote:

 interface Cloneable(T) if (is(T == class))
 {
     private T doClone(); // must implement but can't call
     T clone()            // this is what everybody can call
     {
         auto result = doClone();
         assert(typeof(result) == typeof(this));
         assert(this.equals(result));
         return result;
     }
 }


This sounds like a case for contract inheritance rather than two layers
of functions.


 interface ComparableForEquality(T)
 {
     protected bool doEquals(T);
     final bool equals(T rhs)
     {
         auto result = doEquals(rhs);
         assert(rhs.equals(cast(T) this) == result);
         return result;
     }
 }


This, on the other hand, does require two layers of functions if you
want to remove the infinite recursion by replacing the 'equals' in the
assertion with 'doEquals'.


-- 
Rainer Deyke - rainerd eldwood.com
Sep 25 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Rainer Deyke wrote:

 Andrei Alexandrescu wrote:

 interface Cloneable(T) if (is(T == class))
 {
     private T doClone(); // must implement but can't call
     T clone()            // this is what everybody can call
     {
         auto result = doClone();
         assert(typeof(result) == typeof(this));
         assert(this.equals(result));
         return result;
     }
 }


 
 This sounds like a case for contract inheritance rather than two layers
 of functions.


Contract inheritance has its place but NVI is more general than that.


 interface ComparableForEquality(T)
 {
     protected bool doEquals(T);
     final bool equals(T rhs)
     {
         auto result = doEquals(rhs);
         assert(rhs.equals(cast(T) this) == result);
         return result;
     }
 }


 
 This, on the other hand, does require two layers of functions if you
 want to remove the infinite recursion by replacing the 'equals' in the
 assertion with 'doEquals'.


Oops, yah, sorry about that. Replace rhs.equals with rhs.doEquals. 
Access to doEquals was actually the point of the example.


Andrei
Sep 25 2009
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2009-09-25 16:49:27 -0400, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:


 In this article:
 
 http://www.gotw.ca/publications/mill18.htm
 
 Herb Sutter makes a powerful argument that overridable functions 
 (customization points) should actually not be the same as the 
 publically available interface. This view rhymes with the Template 
 Method pattern as well.
 
 This leads to the interesting setup in which an interface should 
 ideally define some signatures of to-be-defined functions, but disallow 
 client code from calling them. For the clients, the same interface 
 should expose some higher-level final functions.
 
 Ignoring for the moment access protection semantics in D (which are 
 broken anyway), let's say this would work:
 
 interface Cloneable(T) if (is(T == class))
 {
      private T doClone(); // must implement but can't call
      T clone()            // this is what everybody can call
      {
          auto result = doClone();
          assert(typeof(result) == typeof(this));
          assert(this.equals(result));
          return result;
      }
 }
 
 So clients must implement doClone, but nobody can ever call it except 
 Cloneable's module. This ensures that no cloning ever gets away with 
 returning the wrong object.
 
 Pretty powerful, eh? Now, sometimes you do want to allow a derived 
 class to call the base class implementation. In that case, the 
 interface function must be protected:
 
 interface ComparableForEquality(T)
 {
      protected bool doEquals(T);
      final bool equals(T rhs)
      {
          auto result = doEquals(rhs);
          assert(rhs.doEquals(cast(T) this) == result);
          return result;
      }
 }


[Note: I corrected the above example by replacing rhs.equals with 
rhs.doEquals.]


 The difference is that now a derived class could call super.doEquals.
 
 This feature would require changing some protection rules, I think for 
 the better. What do you think?


I think you're writing a lot of boilerplate code for something that the 
compiler should be able to do by itself. I mean, it's a lot cleaner 
with contracts, and there is no reason the compiler couldn't generate 
itself that "contract-verifying" non-virtual function.

Not only could it generate that contract-verifying function by itself, 
but having a separate contract-verifying function you could decide 
whether to evaluate contracts or not when compiling the calling 
function instead of the function you call, which is better in my 
opinion.

About that last example, where you must bypass contracts when 
evaluating your own contract: with the ability to select at the call 
site whether or not you want to evaluates contracts, you could make it 
so that within a contract functions are automatically called without 
contract evaluation. This way you would not have to think too much 
about infinite recursion caused by contracts.


-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Sep 26 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Michel Fortin wrote:

 On 2009-09-25 16:49:27 -0400, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> said:
 

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions 
 (customization points) should actually not be the same as the 
 publically available interface. This view rhymes with the Template 
 Method pattern as well.

 This leads to the interesting setup in which an interface should 
 ideally define some signatures of to-be-defined functions, but 
 disallow client code from calling them. For the clients, the same 
 interface should expose some higher-level final functions.

 Ignoring for the moment access protection semantics in D (which are 
 broken anyway), let's say this would work:

 interface Cloneable(T) if (is(T == class))
 {
      private T doClone(); // must implement but can't call
      T clone()            // this is what everybody can call
      {
          auto result = doClone();
          assert(typeof(result) == typeof(this));
          assert(this.equals(result));
          return result;
      }
 }

 So clients must implement doClone, but nobody can ever call it except 
 Cloneable's module. This ensures that no cloning ever gets away with 
 returning the wrong object.

 Pretty powerful, eh? Now, sometimes you do want to allow a derived 
 class to call the base class implementation. In that case, the 
 interface function must be protected:

 interface ComparableForEquality(T)
 {
      protected bool doEquals(T);
      final bool equals(T rhs)
      {
          auto result = doEquals(rhs);
          assert(rhs.doEquals(cast(T) this) == result);
          return result;
      }
 }


 
 [Note: I corrected the above example by replacing rhs.equals with 
 rhs.doEquals.]
 

 The difference is that now a derived class could call super.doEquals.

 This feature would require changing some protection rules, I think for 
 the better. What do you think?


 
 I think you're writing a lot of boilerplate code for something that the 
 compiler should be able to do by itself. I mean, it's a lot cleaner with 
 contracts, and there is no reason the compiler couldn't generate itself 
 that "contract-verifying" non-virtual function.


I think it would be a mistake to latch on my quick examples. It's not 
only about before and after checks, it's more about low-level 
customization points versus higher-level interfaces.

Andrei
Sep 26 2009
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2009-09-26 10:06:24 -0400, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:


 Michel Fortin wrote:

 I think you're writing a lot of boilerplate code for something that the 
 compiler should be able to do by itself. I mean, it's a lot cleaner 
 with contracts, and there is no reason the compiler couldn't generate 
 itself that "contract-verifying" non-virtual function.


 
 I think it would be a mistake to latch on my quick examples. It's not 
 only about before and after checks, it's more about low-level 
 customization points versus higher-level interfaces.


Then your examples should have shown this instead.

I fully support having a way to specify a default implementation for a 
function in an interface. It might get handy for a few things (like 
implementing the delegate pattern you see everywhere in Cocoa). But 
it's a bad replacement for contracts.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Sep 27 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Michel Fortin wrote:

 On 2009-09-26 10:06:24 -0400, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> said:
 

 Michel Fortin wrote:

 I think you're writing a lot of boilerplate code for something that 
 the compiler should be able to do by itself. I mean, it's a lot 
 cleaner with contracts, and there is no reason the compiler couldn't 
 generate itself that "contract-verifying" non-virtual function.


 I think it would be a mistake to latch on my quick examples. It's not 
 only about before and after checks, it's more about low-level 
 customization points versus higher-level interfaces.


 
 Then your examples should have shown this instead.


Herb's article has them!


 I fully support having a way to specify a default implementation for a 
 function in an interface. It might get handy for a few things (like 
 implementing the delegate pattern you see everywhere in Cocoa). But it's 
 a bad replacement for contracts.


Walter has implemented contract inheritance, and we hope to be able to 
have contracts on interfaces in too. The former is a nice expected 
feature; the latter could convince DbC skeptics to start using it.

Andrei
Sep 27 2009
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2009-09-27 09:53:12 -0400, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:


 Then your examples should have shown this instead.


 
 Herb's article has them!


From what I read, Herb's article is focussing on making classes ABI 
less fragile by removing virtual functions from public view and forcing 
users to call them behind a non-virtual functions. My take on this is 
that it's useful, but unintuitive.

There is one example where he separates a task into multiple virtual 
functions called apparently in sequence from non-virtual one. That's a 
fine concept, but putting this into something called "interface" seems 
dubious to me as it looks more like an implementation detail than an 
interface.

Still, having a way to write a default implementation for a function in 
an interface seems useful to me in some situations, but not in those 
illustrated the article you pointed to.



 I fully support having a way to specify a default implementation for a 
 function in an interface. It might get handy for a few things (like 
 implementing the delegate pattern you see everywhere in Cocoa). But 
 it's a bad replacement for contracts.


 
 Walter has implemented contract inheritance, and we hope to be able to 
 have contracts on interfaces in too. The former is a nice expected 
 feature; the latter could convince DbC skeptics to start using it.


That's really great! :-)


-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Sep 27 2009
prev sibling parent reply =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeberger free.fr> writes:
Michel Fortin wrote:

 I fully support having a way to specify a default implementation for a =



 function in an interface. It might get handy for a few things (like=20
 implementing the delegate pattern you see everywhere in Cocoa). But it'=


s=20

 a bad replacement for contracts.
=20


	Then what's the difference between an interface and an abstract=20
class? I thought that the whole point of interfaces was that you=20
couldn't have implementations of the methods so that you had no=20
problem choosing an implementation when inheriting from multiple=20
interfaces.

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Sep 27 2009
parent reply Jeremie Pelletier <jeremiep gmail.com> writes:
Jérôme M. Berger wrote:

 Michel Fortin wrote:

 I fully support having a way to specify a default implementation for a 
 function in an interface. It might get handy for a few things (like 
 implementing the delegate pattern you see everywhere in Cocoa). But 
 it's a bad replacement for contracts.


     Then what's the difference between an interface and an abstract 
 class? I thought that the whole point of interfaces was that you 
 couldn't have implementations of the methods so that you had no problem 
 choosing an implementation when inheriting from multiple interfaces.
 
         Jerome


The interface supports multiple inheritance since it doesn't add to the 
vtable of the class using it, and its code would be implemented on the 
classes implementing the interface, not overridden by subclasses.
Sep 27 2009
parent reply =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeberger free.fr> writes:
Jeremie Pelletier wrote:

 J=E9r=F4me M. Berger wrote:

 Michel Fortin wrote:

 I fully support having a way to specify a default implementation for =







 a function in an interface. It might get handy for a few things (like=






=20

 implementing the delegate pattern you see everywhere in Cocoa). But=20
 it's a bad replacement for contracts.


     Then what's the difference between an interface and an abstract=20
 class? I thought that the whole point of interfaces was that you=20
 couldn't have implementations of the methods so that you had no=20
 problem choosing an implementation when inheriting from multiple=20
 interfaces.

         Jerome


=20
 The interface supports multiple inheritance since it doesn't add to the=


=20

 vtable of the class using it,


	?? The interface adds as much (or as little) to the vtable as=20
another class would. The reason why interfaces support multiple=20
inheritance is that since the interface does not contain the code=20
for any of its methods, there is never any doubt which method should=20
be called even if several ancestors have methods with the same=20
signature. Once you add code to the interface you loose that advantage.


 and its code would be implemented on the=20
 classes implementing the interface, not overridden by subclasses.


	I don't see how that's different from standard class inheritance.=20
After all there is nothing that forces you to override methods in=20
subclasses if they already have an implementation in the parent=20
class either.

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Sep 30 2009
parent reply Jeremie Pelletier <jeremiep gmail.com> writes:
Jérôme M. Berger wrote:

 Jeremie Pelletier wrote:

 Jérôme M. Berger wrote:

 Michel Fortin wrote:

 I fully support having a way to specify a default implementation for 
 a function in an interface. It might get handy for a few things 
 (like implementing the delegate pattern you see everywhere in 
 Cocoa). But it's a bad replacement for contracts.


     Then what's the difference between an interface and an abstract 
 class? I thought that the whole point of interfaces was that you 
 couldn't have implementations of the methods so that you had no 
 problem choosing an implementation when inheriting from multiple 
 interfaces.

         Jerome


 The interface supports multiple inheritance since it doesn't add to 
 the vtable of the class using it,


 
     ?? The interface adds as much (or as little) to the vtable as 
 another class would. The reason why interfaces support multiple 
 inheritance is that since the interface does not contain the code for 
 any of its methods, there is never any doubt which method should be 
 called even if several ancestors have methods with the same signature. 
 Once you add code to the interface you loose that advantage.


Wrong, the implementation of the interface makes the vtable, the 
interface is only a skeleton for the methods. That interface code would 
only provide a default implementation for the class implementing it, 
which is really useful if you intend to have multiple implementations 
and get some generic code from the interface, unless of using template 
mixins.


 and its code would be implemented on the classes implementing the 
 interface, not overridden by subclasses.


 
     I don't see how that's different from standard class inheritance. 
 After all there is nothing that forces you to override methods in 
 subclasses if they already have an implementation in the parent class 
 either.
 
         Jerome


Yes but you can only extend a single base class, while you may implement 
multiple interfaces, how would you implement generic methods for these 
interfaces under that model? The only way is through template mixins and 
that's not the most convenient method.

Basically interface code would be just like templates that gets mixed in 
the implementing class. You could easily write generic contracts for 
interfaces that way, instead of repeating the same contracts in every 
implementation. It's just another tool to help generic programming.
Sep 30 2009
parent =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeberger free.fr> writes:
Jeremie Pelletier wrote:

 Jérôme M. Berger wrote:

 Jeremie Pelletier wrote:

 Jérôme M. Berger wrote:

 Michel Fortin wrote:

 I fully support having a way to specify a default implementation 
 for a function in an interface. It might get handy for a few things 
 (like implementing the delegate pattern you see everywhere in 
 Cocoa). But it's a bad replacement for contracts.


     Then what's the difference between an interface and an abstract 
 class? I thought that the whole point of interfaces was that you 
 couldn't have implementations of the methods so that you had no 
 problem choosing an implementation when inheriting from multiple 
 interfaces.

         Jerome


 The interface supports multiple inheritance since it doesn't add to 
 the vtable of the class using it,


     ?? The interface adds as much (or as little) to the vtable as 
 another class would. The reason why interfaces support multiple 
 inheritance is that since the interface does not contain the code for 
 any of its methods, there is never any doubt which method should be 
 called even if several ancestors have methods with the same signature. 
 Once you add code to the interface you loose that advantage.


 
 Wrong, the implementation of the interface makes the vtable, the 
 interface is only a skeleton for the methods. That interface code would 
 only provide a default implementation for the class implementing it, 
 which is really useful if you intend to have multiple implementations 
 and get some generic code from the interface, unless of using template 
 mixins.
 


	And how does it work if you implement several interfaces, with 
functions of the same name and different "interface code". This is 
precisely the reason why we don't have multiple inheritance of 
classes...


 and its code would be implemented on the classes implementing the 
 interface, not overridden by subclasses.


     I don't see how that's different from standard class inheritance. 
 After all there is nothing that forces you to override methods in 
 subclasses if they already have an implementation in the parent class 
 either.

         Jerome


 
 Yes but you can only extend a single base class, while you may implement 
 multiple interfaces, how would you implement generic methods for these 
 interfaces under that model? The only way is through template mixins and 
 that's not the most convenient method.
 
 Basically interface code would be just like templates that gets mixed in 
 the implementing class. You could easily write generic contracts for 
 interfaces that way, instead of repeating the same contracts in every 
 implementation. It's just another tool to help generic programming.


	I'll ask it again: how is that different from multiple class 
inheritance? I know we don't have it in D (and for good reasons) but 
once we add what you're describing, we might as well call the 
interfaces "classes" and be done with it.

		Jerome

PS: Contracts are a different issue. I'd be all in favour of adding 
contracts to the interfaces now that we have contract inheritance 
for classes.
-- 
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Oct 01 2009
prev sibling next sibling parent reply Jeremie Pelletier <jeremiep gmail.com> writes:
Andrei Alexandrescu wrote:

 In this article:
 
 http://www.gotw.ca/publications/mill18.htm
 
 Herb Sutter makes a powerful argument that overridable functions 
 (customization points) should actually not be the same as the publically 
 available interface. This view rhymes with the Template Method pattern 
 as well.
 
 This leads to the interesting setup in which an interface should ideally 
 define some signatures of to-be-defined functions, but disallow client 
 code from calling them. For the clients, the same interface should 
 expose some higher-level final functions.
 
 Ignoring for the moment access protection semantics in D (which are 
 broken anyway), let's say this would work:
 
 interface Cloneable(T) if (is(T == class))
 {
     private T doClone(); // must implement but can't call
     T clone()            // this is what everybody can call
     {
         auto result = doClone();
         assert(typeof(result) == typeof(this));
         assert(this.equals(result));
         return result;
     }
 }
 
 So clients must implement doClone, but nobody can ever call it except 
 Cloneable's module. This ensures that no cloning ever gets away with 
 returning the wrong object.
 
 Pretty powerful, eh? Now, sometimes you do want to allow a derived class 
 to call the base class implementation. In that case, the interface 
 function must be protected:
 
 interface ComparableForEquality(T)
 {
     protected bool doEquals(T);
     final bool equals(T rhs)
     {
         auto result = doEquals(rhs);
         assert(rhs.equals(cast(T) this) == result);
         return result;
     }
 }
 
 The difference is that now a derived class could call super.doEquals.
 
 This feature would require changing some protection rules, I think for 
 the better. What do you think?
 
 
 Andrei


What about:

interface ComparableForEquality(T) {
	bool equals(T rhs)
	out(result) {
		assert(rhs.equals(cast(T)this) == result);
	}
}

Getting instead a contract that gets added to implementations, or at 
least only the base implementation, and letting the actual method 
unimplemented.

However having code for interfaces as well as protection would be neat. 
They could prevent a lot of template mixins within every implementation 
to get a common feature.
Sep 26 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Jeremie Pelletier wrote:

 Andrei Alexandrescu wrote:

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions 
 (customization points) should actually not be the same as the 
 publically available interface. This view rhymes with the Template 
 Method pattern as well.

 This leads to the interesting setup in which an interface should 
 ideally define some signatures of to-be-defined functions, but 
 disallow client code from calling them. For the clients, the same 
 interface should expose some higher-level final functions.

 Ignoring for the moment access protection semantics in D (which are 
 broken anyway), let's say this would work:

 interface Cloneable(T) if (is(T == class))
 {
     private T doClone(); // must implement but can't call
     T clone()            // this is what everybody can call
     {
         auto result = doClone();
         assert(typeof(result) == typeof(this));
         assert(this.equals(result));
         return result;
     }
 }

 So clients must implement doClone, but nobody can ever call it except 
 Cloneable's module. This ensures that no cloning ever gets away with 
 returning the wrong object.

 Pretty powerful, eh? Now, sometimes you do want to allow a derived 
 class to call the base class implementation. In that case, the 
 interface function must be protected:

 interface ComparableForEquality(T)
 {
     protected bool doEquals(T);
     final bool equals(T rhs)
     {
         auto result = doEquals(rhs);
         assert(rhs.equals(cast(T) this) == result);
         return result;
     }
 }

 The difference is that now a derived class could call super.doEquals.

 This feature would require changing some protection rules, I think for 
 the better. What do you think?


 Andrei


 
 What about:
 
 interface ComparableForEquality(T) {
     bool equals(T rhs)
     out(result) {
         assert(rhs.equals(cast(T)this) == result);
     }
 }


I want to cajole Walter into implementing contracts on interfaces as well.


 Getting instead a contract that gets added to implementations, or at 
 least only the base implementation, and letting the actual method 
 unimplemented.
 
 However having code for interfaces as well as protection would be neat. 
 They could prevent a lot of template mixins within every implementation 
 to get a common feature.


Note that NVI is about more than pre- and post-conditions. I'm actually 
amazed that so many people latched so firmly onto the examples I gave 
(as opposed to e.g. the examples in Herb's article).


Andrei
Sep 26 2009
parent Jeremie Pelletier <jeremiep gmail.com> writes:
Andrei Alexandrescu wrote:

 Jeremie Pelletier wrote:

 Andrei Alexandrescu wrote:

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions 
 (customization points) should actually not be the same as the 
 publically available interface. This view rhymes with the Template 
 Method pattern as well.

 This leads to the interesting setup in which an interface should 
 ideally define some signatures of to-be-defined functions, but 
 disallow client code from calling them. For the clients, the same 
 interface should expose some higher-level final functions.

 Ignoring for the moment access protection semantics in D (which are 
 broken anyway), let's say this would work:

 interface Cloneable(T) if (is(T == class))
 {
     private T doClone(); // must implement but can't call
     T clone()            // this is what everybody can call
     {
         auto result = doClone();
         assert(typeof(result) == typeof(this));
         assert(this.equals(result));
         return result;
     }
 }

 So clients must implement doClone, but nobody can ever call it except 
 Cloneable's module. This ensures that no cloning ever gets away with 
 returning the wrong object.

 Pretty powerful, eh? Now, sometimes you do want to allow a derived 
 class to call the base class implementation. In that case, the 
 interface function must be protected:

 interface ComparableForEquality(T)
 {
     protected bool doEquals(T);
     final bool equals(T rhs)
     {
         auto result = doEquals(rhs);
         assert(rhs.equals(cast(T) this) == result);
         return result;
     }
 }

 The difference is that now a derived class could call super.doEquals.

 This feature would require changing some protection rules, I think 
 for the better. What do you think?


 Andrei


 What about:

 interface ComparableForEquality(T) {
     bool equals(T rhs)
     out(result) {
         assert(rhs.equals(cast(T)this) == result);
     }
 }


 
 I want to cajole Walter into implementing contracts on interfaces as well.
 

 Getting instead a contract that gets added to implementations, or at 
 least only the base implementation, and letting the actual method 
 unimplemented.

 However having code for interfaces as well as protection would be 
 neat. They could prevent a lot of template mixins within every 
 implementation to get a common feature.


 
 Note that NVI is about more than pre- and post-conditions. I'm actually 
 amazed that so many people latched so firmly onto the examples I gave 
 (as opposed to e.g. the examples in Herb's article).
 
 
 Andrei


I agree, pre- and post-conditions are usually things that change very 
little across implementations and would therefore be best suited in NVI 
than repeated across all implementations.

However I think interfaces could allow for an optionnal body as well, 
and even templated methods, here's an problem I had with my I/O interfaces:

interface IInputStream : IStream {
	size_t read(ubyte[] buf); // Read data up to buf.length, returns actual 
read bytes.

	void read(S : S*)(S* s) { // specialized read for primitives and structs
		if(read((cast(ubyte*)s)[0 .. S.sizeof]) != S.sizeof)
			throw new ReadException();
	}
}

This is something you just can't do right now, yet would be extremely 
useful to provide method variants that call into a method of the 
implementation.

The way I worked around it right now was to add a bunch of specialized 
prototypes for every primitive size (readByte, readShort, readInt, 
readLong, readStruct) and declare a mixin template to implement them in 
every IInputStream implementation.

Jeremie
Sep 26 2009
prev sibling next sibling parent reply Yigal Chripun <yigal100 gmail.com> writes:
On 25/09/2009 23:49, Andrei Alexandrescu wrote:

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions
 (customization points) should actually not be the same as the publically
 available interface. This view rhymes with the Template Method pattern
 as well.

 This leads to the interesting setup in which an interface should ideally
 define some signatures of to-be-defined functions, but disallow client
 code from calling them. For the clients, the same interface should
 expose some higher-level final functions.

 Ignoring for the moment access protection semantics in D (which are
 broken anyway), let's say this would work:

 interface Cloneable(T) if (is(T == class))
 {
 private T doClone(); // must implement but can't call
 T clone() // this is what everybody can call
 {
 auto result = doClone();
 assert(typeof(result) == typeof(this));
 assert(this.equals(result));
 return result;
 }
 }

 So clients must implement doClone, but nobody can ever call it except
 Cloneable's module. This ensures that no cloning ever gets away with
 returning the wrong object.

 Pretty powerful, eh? Now, sometimes you do want to allow a derived class
 to call the base class implementation. In that case, the interface
 function must be protected:

 interface ComparableForEquality(T)
 {
 protected bool doEquals(T);
 final bool equals(T rhs)
 {
 auto result = doEquals(rhs);
 assert(rhs.equals(cast(T) this) == result);
 return result;
 }
 }

 The difference is that now a derived class could call super.doEquals.

 This feature would require changing some protection rules, I think for
 the better. What do you think?


 Andrei


to clarify your suggestion above I have a few questions:
are the functions with definitions always final?

interface A {
    final func () {...}
}
interface B {
    final func () {...}
}

class C : A, B {...}
auto obj = new C;
C.func(); // what happens here?
Sep 26 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Yigal Chripun wrote:

 On 25/09/2009 23:49, Andrei Alexandrescu wrote:

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions
 (customization points) should actually not be the same as the publically
 available interface. This view rhymes with the Template Method pattern
 as well.

 This leads to the interesting setup in which an interface should ideally
 define some signatures of to-be-defined functions, but disallow client
 code from calling them. For the clients, the same interface should
 expose some higher-level final functions.

 Ignoring for the moment access protection semantics in D (which are
 broken anyway), let's say this would work:

 interface Cloneable(T) if (is(T == class))
 {
 private T doClone(); // must implement but can't call
 T clone() // this is what everybody can call
 {
 auto result = doClone();
 assert(typeof(result) == typeof(this));
 assert(this.equals(result));
 return result;
 }
 }

 So clients must implement doClone, but nobody can ever call it except
 Cloneable's module. This ensures that no cloning ever gets away with
 returning the wrong object.

 Pretty powerful, eh? Now, sometimes you do want to allow a derived class
 to call the base class implementation. In that case, the interface
 function must be protected:

 interface ComparableForEquality(T)
 {
 protected bool doEquals(T);
 final bool equals(T rhs)
 {
 auto result = doEquals(rhs);
 assert(rhs.equals(cast(T) this) == result);
 return result;
 }
 }

 The difference is that now a derived class could call super.doEquals.

 This feature would require changing some protection rules, I think for
 the better. What do you think?


 Andrei


 
 to clarify your suggestion above I have a few questions:
 are the functions with definitions always final?
 
 interface A {
    final func () {...}
 }
 interface B {
    final func () {...}
 }
 
 class C : A, B {...}
 auto obj = new C;
 C.func(); // what happens here?


I think that would be a compile-time ambiguity error.

Andrei
Sep 26 2009
prev sibling next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
I think this is great, especially fine to see final methods in interfaces. 
Looks a bit like aspect oriented programming.

Just wanted to add that it's not always *only* a benefit. Like with template 
method, flow of control may be a bit more complicated for the people who do 
the overriding. But that depends on how you use it though.
Sep 27 2009
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 25 Sep 2009 16:49:27 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 This leads to the interesting setup in which an interface should ideally  
 define some signatures of to-be-defined functions, but disallow client  
 code from calling them. For the clients, the same interface should  
 expose some higher-level final functions.


There are also some other benefits to allowing defining interface  
implementation, such as defining one function in terms of another (public)  
function.  For example, take a look at:

http://www.dsource.org/projects/dcollections/docs/current/dcollections.model.Collection.html

Look at the definition for both remove functions, the one which takes no  
bool can easily be defined in terms of the one that takes a bool reference  
(in fact, this is what I do in all the implementations).

The only issue is that you run into multiple inheritance issues (as  
brought up by Yigal)...

vote++

-Steve
Sep 27 2009
prev sibling parent reply Don <nospam nospam.com> writes:
Andrei Alexandrescu wrote:

 In this article:
 
 http://www.gotw.ca/publications/mill18.htm
 
 Herb Sutter makes a powerful argument that overridable functions 
 (customization points) should actually not be the same as the publically 
 available interface. This view rhymes with the Template Method pattern 
 as well.


Ever since I read that earlier this year, I've wondered about this (from 
the spec):

"All non-static non-private non-template member functions are virtual. 
This may sound inefficient, but since the D compiler knows all of the 
class hierarchy when generating code, all functions that are not 
overridden can be optimized to be non-virtual. In fact, since C++ 
programmers tend to "when in doubt, make it virtual", the D way of "make 
it virtual unless we can prove it can be made non-virtual" results, on 
average, in many more direct function calls."

Based on what Herb says, D is actively encouraging bad design...
Sep 29 2009
parent reply Bill Baxter <wbaxter gmail.com> writes:
On Tue, Sep 29, 2009 at 4:04 AM, Don <nospam nospam.com> wrote:

 Andrei Alexandrescu wrote:

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions
 (customization points) should actually not be the same as the publically
 available interface. This view rhymes with the Template Method pattern as
 well.


 Ever since I read that earlier this year, I've wondered about this (from the
 spec):

 "All non-static non-private non-template member functions are virtual. This
 may sound inefficient, but since the D compiler knows all of the class
 hierarchy when generating code, all functions that are not overridden can be
 optimized to be non-virtual. In fact, since C++ programmers tend to "when in
 doubt, make it virtual", the D way of "make it virtual unless we can prove
 it can be made non-virtual" results, on average, in many more direct
 function calls."

 Based on what Herb says, D is actively encouraging bad design...


I don't think that's even true what the spec says.  How can the
compiler know "all of the class hierarchy" if you compile modules
separately?  If you compile the base class module first, it has no way
of knowing whether or not some class in another module is going to
come along later and want to override a method.  Could be possible in
a smart linker, I suppose, but the spec clearly says "compiler".
Walter just got through telling us how the linker is a very simple
program, so I doubt OPTLINK at least is capable of such feats.

--bb
Sep 29 2009
next sibling parent Jeremie Pelletier <jeremiep gmail.com> writes:
Bill Baxter wrote:

 On Tue, Sep 29, 2009 at 4:04 AM, Don <nospam nospam.com> wrote:

 Andrei Alexandrescu wrote:

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions
 (customization points) should actually not be the same as the publically
 available interface. This view rhymes with the Template Method pattern as
 well.


 Ever since I read that earlier this year, I've wondered about this (from the
 spec):

 "All non-static non-private non-template member functions are virtual. This
 may sound inefficient, but since the D compiler knows all of the class
 hierarchy when generating code, all functions that are not overridden can be
 optimized to be non-virtual. In fact, since C++ programmers tend to "when in
 doubt, make it virtual", the D way of "make it virtual unless we can prove
 it can be made non-virtual" results, on average, in many more direct
 function calls."

 Based on what Herb says, D is actively encouraging bad design...


 
 I don't think that's even true what the spec says.  How can the
 compiler know "all of the class hierarchy" if you compile modules
 separately?  If you compile the base class module first, it has no way
 of knowing whether or not some class in another module is going to
 come along later and want to override a method.  Could be possible in
 a smart linker, I suppose, but the spec clearly says "compiler".
 Walter just got through telling us how the linker is a very simple
 program, so I doubt OPTLINK at least is capable of such feats.
 
 --bb


The linker basically only resolve symbols, assign addresses and 
generates the executable. It's a pretty straightforward process. Besides 
once the object code gets to the linker, all calls have already been 
compiled in, even if the linker could optimize non-virtual methods the 
calls would still use the vtbl.

I agree that the design can have some flaws by compiling modules 
separately, I would much rather have a virtual AND override keyword 
myself and let the compiler optimize the calls to non-virtuals to skip 
the vtbl lookup.

I don't mind tagging methods with all sorts of keywords like final, 
override, virtual, const, nothrow, pure, etc. I like it that way, gives 
much more meaning to the method by simply looking at its prototype 
(which is often all you're given).
Sep 29 2009
prev sibling parent reply Don <nospam nospam.com> writes:
Bill Baxter wrote:

 On Tue, Sep 29, 2009 at 4:04 AM, Don <nospam nospam.com> wrote:

 Andrei Alexandrescu wrote:

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions
 (customization points) should actually not be the same as the publically
 available interface. This view rhymes with the Template Method pattern as
 well.


 Ever since I read that earlier this year, I've wondered about this (from the
 spec):

 "All non-static non-private non-template member functions are virtual. This
 may sound inefficient, but since the D compiler knows all of the class
 hierarchy when generating code, all functions that are not overridden can be
 optimized to be non-virtual. 






  the D way of "make it virtual unless we can prove

 it can be made non-virtual" results, on average, in many more direct
 function calls."

 Based on what Herb says, D is actively encouraging bad design...


 
 I don't think that's even true what the spec says.  How can the
 compiler know "all of the class hierarchy" if you compile modules
 separately? 


Yes, I don't see how it could.

And also, is this statement true?

 since C++ programmers tend to "when in doubt, make it virtual"




Do they? (Might be true, but I don't remember ever hearing it anywhere 
else).

I suspect that this paragraph in the spec is a relic from the very early 
days of D. Might be worth going through the spec looking for glib 
statements and hand-waving arguments.





  If you compile the base class module first, it has no way

 of knowing whether or not some class in another module is going to
 come along later and want to override a method.  Could be possible in
 a smart linker, I suppose, but the spec clearly says "compiler".
 Walter just got through telling us how the linker is a very simple
 program, so I doubt OPTLINK at least is capable of such feats.
 
 --bb
Sep 29 2009
parent reply Bill Baxter <wbaxter gmail.com> writes:
On Tue, Sep 29, 2009 at 8:46 AM, Don <nospam nospam.com> wrote:

 Bill Baxter wrote:

 On Tue, Sep 29, 2009 at 4:04 AM, Don <nospam nospam.com> wrote:

 Andrei Alexandrescu wrote:

 In this article:

 http://www.gotw.ca/publications/mill18.htm

 Herb Sutter makes a powerful argument that overridable functions
 (customization points) should actually not be the same as the publical=








ly

 available interface. This view rhymes with the Template Method pattern
 as
 well.


 Ever since I read that earlier this year, I've wondered about this (fro=






m

 the
 spec):

 "All non-static non-private non-template member functions are virtual.
 This
 may sound inefficient, but since the D compiler knows all of the class
 hierarchy when generating code, all functions that are not overridden c=






an

 be
 optimized to be non-virtual.






 =A0the D way of "make it virtual unless we can prove

 it can be made non-virtual" results, on average, in many more direct
 function calls."

 Based on what Herb says, D is actively encouraging bad design...


 I don't think that's even true what the spec says. =A0How can the
 compiler know "all of the class hierarchy" if you compile modules
 separately?


 Yes, I don't see how it could.

 And also, is this statement true?

 since C++ programmers tend to "when in doubt, make it virtual"




 Do they? (Might be true, but I don't remember ever hearing it anywhere
 else).


They might in practice, but the current preaching I hear is to
generally to make the slimmest and least virtual interface you can get
away with.  Of course nobody would need to preach about such
methodology if there weren't some contrary trend commonly seen out in
the wild.

--bb
Sep 29 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Bill Baxter wrote:

 On Tue, Sep 29, 2009 at 8:46 AM, Don <nospam nospam.com> wrote:

 Bill Baxter wrote:





 And also, is this statement true?

 since C++ programmers tend to "when in doubt, make it virtual"




 Do they? (Might be true, but I don't remember ever hearing it anywhere
 else).


 
 They might in practice, but the current preaching I hear is to
 generally to make the slimmest and least virtual interface you can get
 away with.  Of course nobody would need to preach about such
 methodology if there weren't some contrary trend commonly seen out in
 the wild.


Well there are two considerations that are in tension. One is that an 
abstract interface should be sufficient for getting work done, and that 
pushes its size up. If interfaces are too slim, people tend to "extend" 
them on the implementation side and then cast down to implementation 
whenever they need to get anything done. That pushes the size of 
interfaces upwards.

The other consideration is that interfaces should be narrow such that 
they are not difficult to understand and implement.

So thinking of making an interface as small as possible or as 
comprehensive as possible may miss part of the tradeoffs involved.

NVI offers the ability to distinguish between the interface that must be 
implemented, and the interface that gets used.


Andrei
Sep 29 2009