www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [contest] Is a Cow an animal ++

reply bearophile <bearophileHUGS lycos.com> writes:
This is a harder variant of an old and very simple OOP problem:
http://merd.sourceforge.net/pixel/language-study/various/is-a-cow-an-animal/

The problem presents a hierarchy of types, some rules, and 11 tests, each one
of them represents a bug because it contains a violation of the rules. You have
to write the program in a way that the type system refuses as many of those 11
tests as possible at compile-time. There are many acceptable ways to write the
program, for example you may use functional programming, so you are able to
return different types, that enforce different rules, so it's not a contest,
it's more like a demonstration.

A basic Python implementation catches none of the 11 tests at compile time :-)
A basic D implementation that I have written catches five of the 11 bugs at
compile time:
http://ideone.com/87q67
I will try to write a more statically typed D version.

The site shows four C++ versions, the fourth is able to catch 8 of the 11 bugs
at compile-time. A type system that supports typestates is probably able to
catch all 11 bugs (because for example the Cow type has two states, alive and
eaten, and you can't perform some operations on a eaten cow, like eating it
again), but probably it's very hard to do this with D.

The fourth C++ version contains a line that I am am not even sure how to
translate to D (maybe there is a workaround with template constraints):
(void) static_cast<My_kind *>((Kind *) 0);

Bye,
bearophile
Sep 27 2010
next sibling parent Justin Johansson <no spam.com> writes:
On 27/09/2010 10:26 PM, bearophile wrote:
 This is a harder variant of an old and very simple OOP problem:
 http://merd.sourceforge.net/pixel/language-study/various/is-a-cow-an-animal/

 The problem presents a hierarchy of types, some rules, and 11 tests, each one
of them represents a bug because it contains a violation of the rules. You have
to write the program in a way that the type system refuses as many of those 11
tests as possible at compile-time. There are many acceptable ways to write the
program, for example you may use functional programming, so you are able to
return different types, that enforce different rules, so it's not a contest,
it's more like a demonstration.

 A basic Python implementation catches none of the 11 tests at compile time :-)
A basic D implementation that I have written catches five of the 11 bugs at
compile time:
 http://ideone.com/87q67
 I will try to write a more statically typed D version.

 The site shows four C++ versions, the fourth is able to catch 8 of the 11 bugs
at compile-time. A type system that supports typestates is probably able to
catch all 11 bugs (because for example the Cow type has two states, alive and
eaten, and you can't perform some operations on a eaten cow, like eating it
again), but probably it's very hard to do this with D.

 The fourth C++ version contains a line that I am am not even sure how to
translate to D (maybe there is a workaround with template constraints):
 (void) static_cast<My_kind *>((Kind *) 0);

 Bye,
 bearophile

Accolades to you bearophile for using a subject annotation i.e. [contest] for this post. It would be nice if people used, say, [license] or whatever as appropriate as an annotation to discriminate their posts on the long running "Andrei's Google Talk"thread which is more of a Gordian Knot rather than a thread per se. Anyway, my 2 cents about this type of problem is that much of OOP is about trying too hard to model taxonomies in single inheritance fashion, and this has obvious failing in the real world. Still I have not read your links and perhaps I'm shooting from the foot so I will go off now and digest the problem that you submit as a [contest]. :-) Regards JJ
Sep 27 2010
prev sibling next sibling parent Justin Johansson <no spam.com> writes:
On 27/09/2010 10:26 PM, bearophile wrote:

I did some research and came up with this.

Does a cow eat bread?

http://www.joke-of-the-day.com/jokes/duck-walks-bar
Sep 27 2010
prev sibling next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:


 The fourth C++ version contains a line that I am am not even sure how to  
 translate to D (maybe there is a workaround with template constraints):
 (void) static_cast<My_kind *>((Kind *) 0);

This is a static assert of sorts. Basically, the function will only compile if Kind is a subtype of My_kind. In D, you would use is( Kind : My_kind ), where Kind and My_Kind are interfaces Here's mine ( 8/11 at compile-time, the remaining at runtime ): http://ideone.com/6WlFJ I don't think it's possible to make it better than that in D without, as you say, for instance type states. -- Simen
Sep 27 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Philippe Sigaud:
 Encoding the cow's state in its type is no good either, as you cannot change
 a cow's type. I think OCaml does it with algebraic data types. These are
 doable in D, but only testable at runtime...

More answers later. In the meantime this contains something about the "typestate": http://d.puremagic.com/issues/show_bug.cgi?id=4571 Bye, bearophile
Sep 27 2010
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Simen kjaeraas:

 This is a static assert of sorts. Basically, the function will only
 compile if Kind is a subtype of My_kind. In D, you would use
 is( Kind : My_kind ), where Kind and My_Kind are interfaces

OK.
 Here's mine ( 8/11 at compile-time, the remaining at runtime ):
 http://ideone.com/6WlFJ

Thank you. It's a nice implementation, and it doesn't use template magic at all, it's fully OOP :-) Your implementation shows that there are many different ways to solve this puzzle. I presume a bit shorter code is possible using templates (as in the 4th C++ version). I have modified your code a little, I have added the missing 'override', I have added the required sequence ("there should be a way to handle a list of animals and the energy of each animal"), but there is no need for the name field because there is the classinfo.name, and I have shortened/simplified your (nice) test code a lot: http://ideone.com/TQzyD What's the purpose of using class names like "wCarrot" instead of "Carrot"? I'd like to send (with full attribution) the D versions to the site/page owner (Pixel), maybe she/he's interested.
 I don't think it's possible to make it better than that in D without,
 as you say, for instance type states.

Typestate (a single word, it seems) is probably an useful thing, it's not the expression of an esoteric need. But to implement it I think you need flow analysis done by the compiler at compile-time. Among all the possible applications of flow analysis I think this can be one of the most useful :-) Runtime tests are useful to avoid bugs, but it's nice to have a static type that's able to catch bugs at compile time.
I guess it actually is doable at CT, by coding the whole puzzle within the
confines of CTFE or TMP. I'm not going to, though.<

Better to not go there, because you are back to the Python version, but done at compile time :-) Bye, bearophile
Sep 27 2010
prev sibling next sibling parent BCS <none anon.com> writes:
Hello Simen,

 bearophile <bearophileHUGS lycos.com> wrote:
 
 The fourth C++ version contains a line that I am am not even sure how
 to  translate to D (maybe there is a workaround with template
 constraints): (void) static_cast<My_kind *>((Kind *) 0);
 

compile if Kind is a subtype of My_kind. In D, you would use is( Kind : My_kind ), where Kind and My_Kind are interfaces Here's mine ( 8/11 at compile-time, the remaining at runtime ): http://ideone.com/6WlFJ I don't think it's possible to make it better than that in D without, as you say, for instance type states.

The given test as is might be all catchable but add loops and references into the picture and I think it turns into the halting problem. -- ... <IXOYE><
Sep 29 2010
prev sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
BCS <none anon.com> wrote:

 The given test as is might be all catchable but add loops and references  
 into the picture and I think it turns into the halting problem.

Would you mind explaining in further detail? I am not really sure what you mean. -- Simen
Sep 29 2010
next sibling parent BCS <none anon.com> writes:
Hello Simen,

 BCS <none anon.com> wrote:
 
 The given test as is might be all catchable but add loops and
 references  into the picture and I think it turns into the halting
 problem.
 

you mean.

Cow c; while(someFn()) { c = new Cow(); c.slaughter(); } c.slaughter(); // invalid Iff the loop ends Cow c, d, r; for(int i = 0; someFn(); i++) { c = new Cow(); d = new Cow(); r = (i%2) ? c : d; c.slaughter(); } r.slaughter(); // invalid Iff the loop ends on an odd i. void Fn(Cow c, Cow d) { c.slaughter(); d.slaughter(); // invalid Iff called with (c is d). } Checking that the sequence of member function calls on an object is valid is limited by how good your static analysts is. The type system *can't* help you as the exact same code may or may not be valid depending on arbitrary external aspects. -- ... <IXOYE><
Sep 29 2010
prev sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
BCS <none anon.com> wrote:

 Checking that the sequence of member function calls on an object is  
 valid is limited by how good your static analysts is. The type system  
 *can't* help you as the exact same code may or may not be valid  
 depending on arbitrary external aspects.

You are of course correct. Some such analysis could still be performed, and the examples you give would simply leave the typestate in an indeterminate state. -- Simen
Sep 29 2010
parent reply BCS <none anon.com> writes:
Hello Simen,

 BCS <none anon.com> wrote:
 
 Checking that the sequence of member function calls on an object is
 valid is limited by how good your static analysts is. The type system
 *can't* help you as the exact same code may or may not be valid
 depending on arbitrary external aspects.
 

performed, and the examples you give would simply leave the typestate in an indeterminate state.

Having code that's "leagal unless proven guilty" doesn't sound like a good idea to me. -- ... <IXOYE><
Sep 29 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Simen:
 You are of course correct. Some such analysis could still be
 performed, and the examples you give would simply leave the typestate
 in an indeterminate state.


BCS:
 Having code that's "leagal unless proven guilty" doesn't sound like a good
 idea to me.

There are situations where it may be impossible to perform the static analysis needed by the typestate implementation (external C code that modifies some struct state or some multiprocessing situation), and in some other situations this static analysis may be theoretically possible but it becomes too much slow for a certain pathological case (so you may want to add a timeout to such static analysis), so probably in a real-world language you need some fallback mechanism, that allows you to force the compilation of the code. A typestate is a part of a type system, and generally in most type systems there are situations where it doesn't work, or it is not flexible enough. A cast() is a way to punch a hole in it and do what you need. Typestates (and generally type systems) are ways to help you avoid some classes of bugs, but they are not meant to be perfect, you need to think of them as nets able to catch only a certain percentage of the possible bugs of your code :-) You need several different strategies to catch most bugs, a single strategy is never enough. And probably if you want to add perfect implementations of DesignByContract or Typestate to a language, you have to design it from the start around such features, and this probably means your end product language will not be as flexible as D. If you add those features to an existing C-like language, you probably must accept some trade-off, as you see in the D DbC implementation. Bye, bearophile
Sep 30 2010
parent reply BCS <none anon.com> writes:
Hello bearophile,

 Simen:
 
 You are of course correct. Some such analysis could still be
 performed, and the examples you give would simply leave the
 typestate in an indeterminate state.
 


 Having code that's "leagal unless proven guilty" doesn't sound like a
 good idea to me.
 

analysis needed by the typestate implementation (external C code that modifies some struct state or some multiprocessing situation), and in some other situations this static analysis may be theoretically possible but it becomes too much slow for a certain pathological case

My take on this is that the type system should promise to check something and then always check it or say nothing at all. It should never say maybe. The worst it can do is check something most of the time but then not check it in the really hard cases (where I most need it). -- ... <IXOYE><
Sep 30 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
BCS:

 My take on this is that the type system should promise to check something 
 and then always check it or say nothing at all. It should never say maybe. 
 The worst it can do is check something most of the time but then not check 
 it in the really hard cases (where I most need it).

I am not sure. Type systems are like automatic systems that perform a proof. Goedel told us that in some cases there's no way to decide if something is true. This happens for type systems too, and the more complex type systems are, the more situations there are where they reach blocking situations. All real programs contain many bugs, so you have think about finding bugs as a probabilistic effort, your purpose is to reduce some probabilities, because in real-world programs you can't hope to catch all bugs. There is not much difference if some of those bugs come from bugs in the type system, in the compiler, in the program, etc. In C# the type system gives you errors for uninitialized variables, this is a very useful feature that I'd like in D too, but there are situations where such static analysis fails, and the C# compiler gives you false positives. You want a reliable type state that gives zero false negatives, this may be possible, I don't know, but it has a cost, because it has to turn some undetermined cases into false positives. Maybe there is no way to design a typestate as you desire in D. Bye, bearophile
Sep 30 2010
next sibling parent BCS <none anon.com> writes:
Hello bearophile,

 BCS:
 
 My take on this is that the type system should promise to check
 something and then always check it or say nothing at all. It should
 never say maybe. The worst it can do is check something most of the
 time but then not check it in the really hard cases (where I most
 need it).
 

Type systems are like automatic systems that perform a proof. Goedel told us that in some cases there's no way to decide if something is true. This happens for type systems too, and the more complex type systems are, the more situations there are where they reach blocking situations. All real programs contain many bugs, so you have think about finding bugs as a probabilistic effort, your purpose is to reduce some probabilities, because in real-world programs you can't hope to catch all bugs. There is not much difference if some of those bugs come from bugs in the type system, in the compiler, in the program, etc. In C# the type system gives you errors for uninitialized variables, this is a very useful feature that I'd like in D too, but there are situations where such static analysis fails, and the C# compiler gives you false positives. You want a reliable type state that gives zero false negatives, this may be possible, I don't know, but it has a cost, because it has to turn some undetermined cases into false positives. Maybe there is no way to design a typestate as you desire in D.

I have no problem with tools that do what you are looking for. That said I have major problems with that being the type system. The type system should be defined in terms of "MUST", "MUST NOT", "REQUIRED", "SHALL" and "SHALL NOT" and should never use the term, "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" http://www.faqs.org/rfcs/rfc2119.html To do that with the type of static analyses you want would requiter specifying the algorithms to be used and that would be pointless as they would be out of date within months. -- ... <IXOYE><
Sep 30 2010
prev sibling next sibling parent Justin Johansson <no spam.com> writes:
On 1/10/2010 10:53 AM, bearophile wrote:
 BCS:

 My take on this is that the type system should promise to check something
 and then always check it or say nothing at all. It should never say maybe.
 The worst it can do is check something most of the time but then not check
 it in the really hard cases (where I most need it).

I am not sure. Type systems are like automatic systems that perform a proof. Goedel told us that in some cases there's no way to decide if something is true. This happens for type systems too, and the more complex type systems are, the more situations there are where they reach blocking situations. All real programs contain many bugs, so you have think about finding bugs as a probabilistic effort, your purpose is to reduce some probabilities, because in real-world programs you can't hope to catch all bugs. There is not much difference if some of those bugs come from bugs in the type system, in the compiler, in the program, etc. In C# the type system gives you errors for uninitialized variables, this is a very useful feature that I'd like in D too, but there are situations where such static analysis fails, and the C# compiler gives you false positives. You want a reliable type state that gives zero false negatives, this may be possible, I don't know, but it has a cost, because it has to turn some undetermined cases into false positives. Maybe there is no way to design a typestate as you desire in D.

Maybe OT, but my take on type systems is that these are human inventions whereas the "integers" were discovered. As with all human inventions there are faults.
Oct 01 2010
prev sibling parent reply retard <re tard.com.invalid> writes:
Fri, 01 Oct 2010 03:18:29 +0000, BCS wrote:

 Hello bearophile,
 
 BCS:
 
 My take on this is that the type system should promise to check
 something and then always check it or say nothing at all. It should
 never say maybe. The worst it can do is check something most of the
 time but then not check it in the really hard cases (where I most need
 it).
 

Type systems are like automatic systems that perform a proof. Goedel told us that in some cases there's no way to decide if something is true. This happens for type systems too, and the more complex type systems are, the more situations there are where they reach blocking situations. All real programs contain many bugs, so you have think about finding bugs as a probabilistic effort, your purpose is to reduce some probabilities, because in real-world programs you can't hope to catch all bugs. There is not much difference if some of those bugs come from bugs in the type system, in the compiler, in the program, etc. In C# the type system gives you errors for uninitialized variables, this is a very useful feature that I'd like in D too, but there are situations where such static analysis fails, and the C# compiler gives you false positives. You want a reliable type state that gives zero false negatives, this may be possible, I don't know, but it has a cost, because it has to turn some undetermined cases into false positives. Maybe there is no way to design a typestate as you desire in D.

I have no problem with tools that do what you are looking for. That said I have major problems with that being the type system. The type system should be defined in terms of "MUST", "MUST NOT", "REQUIRED", "SHALL" and "SHALL NOT" and should never use the term, "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" http://www.faqs.org/rfcs/rfc2119.html To do that with the type of static analyses you want would requiter specifying the algorithms to be used and that would be pointless as they would be out of date within months.

Are you talking about the specification of the type system here? Denotational semantics? Operational semantics? That rfc has nothing to do with type systems, now does it.
Oct 02 2010
parent BCS <none anon.com> writes:
Hello retard,

 Fri, 01 Oct 2010 03:18:29 +0000, BCS wrote:
 
 Hello bearophile,
 
 BCS:
 
 My take on this is that the type system should promise to check
 something and then always check it or say nothing at all. It should
 never say maybe. The worst it can do is check something most of the
 time but then not check it in the really hard cases (where I most
 need it).
 

Type systems are like automatic systems that perform a proof. Goedel told us that in some cases there's no way to decide if something is true. This happens for type systems too, and the more complex type systems are, the more situations there are where they reach blocking situations. All real programs contain many bugs, so you have think about finding bugs as a probabilistic effort, your purpose is to reduce some probabilities, because in real-world programs you can't hope to catch all bugs. There is not much difference if some of those bugs come from bugs in the type system, in the compiler, in the program, etc. In C# the type system gives you errors for uninitialized variables, this is a very useful feature that I'd like in D too, but there are situations where such static analysis fails, and the C# compiler gives you false positives. You want a reliable type state that gives zero false negatives, this may be possible, I don't know, but it has a cost, because it has to turn some undetermined cases into false positives. Maybe there is no way to design a typestate as you desire in D.

said I have major problems with that being the type system. The type system should be defined in terms of "MUST", "MUST NOT", "REQUIRED", "SHALL" and "SHALL NOT" and should never use the term, "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" http://www.faqs.org/rfcs/rfc2119.html To do that with the type of static analyses you want would requiter specifying the algorithms to be used and that would be pointless as they would be out of date withihe n months.

Denotational semantics? Operational semantics?

Any and all of the above plus any less formal description of what the type system must accept and reject.
 That rfc has nothing to do with type systems, now does it.
 

Nope it doesn't, but it has everything to do with how those terms I used are used in standards documents. -- ... <IXOYE><
Oct 03 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--00151750e90099bcf4049144bd2c
Content-Type: text/plain; charset=UTF-8

On Mon, Sep 27, 2010 at 19:20, Simen kjaeraas <simen.kjaras gmail.com>wrote:

 Here's mine ( 8/11 at compile-time, the remaining at runtime ):
 http://ideone.com/6WlFJ
 I don't think it's possible to make it better than that in D without,
 as you say, for instance type states.

Yeah, I concur. OK for doing the first 8 tests at CT. But at CT you have only enums, so you cannot reassign 'variables'.I cannot find a way to change a cow state from alive to dead. Encoding the cow's state in its type is no good either, as you cannot change a cow's type. I think OCaml does it with algebraic data types. These are doable in D, but only testable at runtime... If pointers were available at compile-time, it'd doable. Didn't Don say we should get classes and pointers at CT at some time? Philippe --00151750e90099bcf4049144bd2c Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Mon, Sep 27, 2010 at 19:20, Simen kjaeraas <s= pan dir=3D"ltr">&lt;<a href=3D"mailto:simen.kjaras gmail.com">simen.kjaras = gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); p= adding-left: 1ex;"> <br> Here&#39;s mine ( 8/11 at compile-time, the remaining at runtime ):<br> <a href=3D"http://ideone.com/6WlFJ" target=3D"_blank">http://ideone.com/6Wl= FJ</a><br> I don&#39;t think it&#39;s possible to make it better than that in D withou= t,<br> as you say, for instance type states.<br></blockquote><div><br>Yeah, I conc= ur.=C2=A0 OK for doing the first 8 tests at CT. But at CT you have only enu= ms, so you cannot reassign &#39;variables&#39;.I cannot find a way to chang= e a cow state from alive to dead. <br> Encoding the cow&#39;s state in its type is no good either, as you cannot c= hange a cow&#39;s type. I think OCaml does it with algebraic data types. Th= ese are doable in D, but only testable at runtime...<br><br>If pointers wer= e available at compile-time, it&#39;d doable. Didn&#39;t Don say we should = get classes and pointers at CT at some time?<br> <br><br>Philippe<br><br></div></div> --00151750e90099bcf4049144bd2c--
Sep 27 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Philippe Sigaud <philippe.sigaud gmail.com> wrote:

 On Mon, Sep 27, 2010 at 19:20, Simen kjaeraas  
 <simen.kjaras gmail.com>wrote:

 Here's mine ( 8/11 at compile-time, the remaining at runtime ):
 http://ideone.com/6WlFJ
 I don't think it's possible to make it better than that in D without,
 as you say, for instance type states.

Yeah, I concur. OK for doing the first 8 tests at CT. But at CT you have only enums, so you cannot reassign 'variables'.I cannot find a way to change a cow state from alive to dead. Encoding the cow's state in its type is no good either, as you cannot change a cow's type. I think OCaml does it with algebraic data types. These are doable in D, but only testable at runtime... If pointers were available at compile-time, it'd doable. Didn't Don say we should get classes and pointers at CT at some time?

I guess it actually is doable at CT, by coding the whole puzzle within the confines of CTFE or TMP. I'm not going to, though. -- Simen
Sep 27 2010
prev sibling next sibling parent Mike Linford <mike.linford.reg gmail.com> writes:
A random question about your naming scheme: What does the 'w' stand for 
in front of all your class names?

-- 
Mike Linford
Sep 27 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:

 Simen kjaeraas:

 Here's mine ( 8/11 at compile-time, the remaining at runtime ):
 http://ideone.com/6WlFJ

Thank you. It's a nice implementation, and it doesn't use template magic at all, it's fully OOP :-) Your implementation shows that there are many different ways to solve this puzzle. I presume a bit shorter code is possible using templates (as in the 4th C++ version). I have modified your code a little, I have added the missing 'override', I have added the required sequence ("there should be a way to handle a list of animals and the energy of each animal"), but there is no need for the name field because there is the classinfo.name, and I have shortened/simplified your (nice) test code a lot: http://ideone.com/TQzyD

That lacks the compile-time tests, though. The point of writing it the way I did was to allow runtime tests if the problems were not caught at compiletime.
 What's the purpose of using class names like "wCarrot" instead of  
 "Carrot"?

Merely that I wanted to call them all objects, and that name was taken. So I added a random letter, and wanted to keep a consistent naming convention. -- Simen
Sep 28 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Mike Linford <mike.linford.reg gmail.com> wrote:

 A random question about your naming scheme: What does the 'w' stand for
 in front of all your class names?

'What'. :P Honestly, I just saw everything being an 'object' and, that name being taken, added a random letter to its front. -- Simen
Sep 28 2010
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Mon, 27 Sep 2010 22:06:18 -0400, bearophile wrote:

 Simen kjaeraas:
 Here's mine ( 8/11 at compile-time, the remaining at runtime ):
 http://ideone.com/6WlFJ

Thank you. It's a nice implementation, and it doesn't use template magic at all, it's fully OOP :-) Your implementation shows that there are many different ways to solve this puzzle. I presume a bit shorter code is possible using templates (as in the 4th C++ version). I have modified your code a little, I have added the missing 'override', I have added the required sequence ("there should be a way to handle a list of animals and the energy of each animal"), but there is no need for the name field because there is the classinfo.name, and I have shortened/simplified your (nice) test code a lot: http://ideone.com/TQzyD

One of the requirements is: "animals can eat some food, their energy is raised by the food's energy amount" However, the eat method seems not to be part of the animal class in your code. Admittedly this is hair-splitting.
Sep 28 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--00c09f923dda13aa3b0491575a63
Content-Type: text/plain; charset=UTF-8

I forgot to post my version yesterday:

http://ideone.com/rvwiN

I chose to use static typing and templates. Compiling it with IDEone gives
the first 8 tests in the 'compilation info' box.


Philippe

--00c09f923dda13aa3b0491575a63
Content-Type: text/html; charset=UTF-8

I forgot to post my version yesterday:<br><br><a
href="http://ideone.com/rvwiN">http://ideone.com/rvwiN</a><br><br>I chose to
use static typing and templates. Compiling it with IDEone gives the first 8
tests in the &#39;compilation info&#39; box.<br>
<br><br>Philippe<br>

--00c09f923dda13aa3b0491575a63--
Sep 28 2010
prev sibling next sibling parent Mike Linford <mike.linford.reg gmail.com> writes:
On Tue, 28 Sep 2010 14:56:33 +0200, Simen kjaeraas wrote:

 Mike Linford <mike.linford.reg gmail.com> wrote:
 
 A random question about your naming scheme: What does the 'w' stand for
 in front of all your class names?

'What'. :P Honestly, I just saw everything being an 'object' and, that name being taken, added a random letter to its front.

Ah. How about 'Thing' next time? ;-) -- Mike Linford
Sep 28 2010
prev sibling next sibling parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
IMHO, the test misses the point of compile-time metaprogramming: The 
concept of "state" belongs to run-time. The D compile-time language is 
purely functional and does not know a state or even an "order of execution".

The conditions "cannot die or be eaten twice" are, at their core, issues 
of state. Any "solutions" that claim to catch one of the last three 
errors must either go beyond the purely functional nature of the 
compile-time language or rely on additional constraints (e.g. no reuse 
of previous elements)

Of course, one could devise a language with non-functional compile time 
features, but within D, this would fundamentally break the existing 
concept of meta-programming.




On 09/27/2010 02:26 PM, bearophile wrote:
 This is a harder variant of an old and very simple OOP problem:
 http://merd.sourceforge.net/pixel/language-study/various/is-a-cow-an-animal/

 The problem presents a hierarchy of types, some rules, and 11 tests, each one
of them represents a bug because it contains a violation of the rules. You have
to write the program in a way that the type system refuses as many of those 11
tests as possible at compile-time. There are many acceptable ways to write the
program, for example you may use functional programming, so you are able to
return different types, that enforce different rules, so it's not a contest,
it's more like a demonstration.

 A basic Python implementation catches none of the 11 tests at compile time :-)
A basic D implementation that I have written catches five of the 11 bugs at
compile time:
 http://ideone.com/87q67
 I will try to write a more statically typed D version.

 The site shows four C++ versions, the fourth is able to catch 8 of the 11 bugs
at compile-time. A type system that supports typestates is probably able to
catch all 11 bugs (because for example the Cow type has two states, alive and
eaten, and you can't perform some operations on a eaten cow, like eating it
again), but probably it's very hard to do this with D.

 The fourth C++ version contains a line that I am am not even sure how to
translate to D (maybe there is a workaround with template constraints):
 (void) static_cast<My_kind *>((Kind *) 0);

 Bye,
 bearophile

Sep 29 2010
next sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Wed, 29 Sep 2010 11:21:11 +0400, Norbert Nemec  
<Norbert nemec-online.de> wrote:

 IMHO, the test misses the point of compile-time metaprogramming: The  
 concept of "state" belongs to run-time. The D compile-time language is  
 purely functional and does not know a state or even an "order of  
 execution".

 The conditions "cannot die or be eaten twice" are, at their core, issues  
 of state. Any "solutions" that claim to catch one of the last three  
 errors must either go beyond the purely functional nature of the  
 compile-time language or rely on additional constraints (e.g. no reuse  
 of previous elements)

 Of course, one could devise a language with non-functional compile time  
 features, but within D, this would fundamentally break the existing  
 concept of meta-programming.

In D, there are templates (that are written in functional style, have no state etc) and there is also CTFE that allows mutable state (but no classes).
Sep 29 2010
parent Norbert Nemec <Norbert Nemec-online.de> writes:
On 09/29/2010 09:32 AM, Denis Koroskin wrote:
 On Wed, 29 Sep 2010 11:21:11 +0400, Norbert Nemec
 <Norbert nemec-online.de> wrote:

 IMHO, the test misses the point of compile-time metaprogramming: The
 concept of "state" belongs to run-time. The D compile-time language is
 purely functional and does not know a state or even an "order of
 execution".

 The conditions "cannot die or be eaten twice" are, at their core,
 issues of state. Any "solutions" that claim to catch one of the last
 three errors must either go beyond the purely functional nature of the
 compile-time language or rely on additional constraints (e.g. no reuse
 of previous elements)

 Of course, one could devise a language with non-functional compile
 time features, but within D, this would fundamentally break the
 existing concept of meta-programming.

In D, there are templates (that are written in functional style, have no state etc) and there is also CTFE that allows mutable state (but no classes).

CTFE is restricted to pure functions, which means that it is effectively syntactic sugar for something that could be done with pure functional programming. It may in fact be possible to solve the contest within a CTFE pure function. It would then not be a challenge for the type system of the language but it would demonstrate that D can run code at compile time. Type violations are caught at compile-time even if the assignment itself happens at run-time. This kind of protection is (out of principle) not possible for killing or eating something twice, even with CTFE.
Sep 29 2010
prev sibling next sibling parent reply retard <re tard.com.invalid> writes:
Wed, 29 Sep 2010 09:21:11 +0200, Norbert Nemec wrote:

 IMHO, the test misses the point of compile-time metaprogramming: The
 concept of "state" belongs to run-time. The D compile-time language is
 purely functional and does not know a state or even an "order of
 execution".
 
 The conditions "cannot die or be eaten twice" are, at their core, issues
 of state. Any "solutions" that claim to catch one of the last three
 errors must either go beyond the purely functional nature of the
 compile-time language or rely on additional constraints (e.g. no reuse
 of previous elements)
 
 Of course, one could devise a language with non-functional compile time
 features, but within D, this would fundamentally break the existing
 concept of meta-programming.

I only read the abstract of one typestate paper, but I think this is what they are all about - associating a (compile time) mutable state with the type. (No need to correct me, I've soon read more about the issue.) I experimented with this (a colleague of mine already solved all 11 cases at compile time with Scala) a bit and noticed that conditions like "has already been eaten" cannot be expressed without purely functional state passing via monads or explicitly (uniqueness types catch potential errors here). Why? The operation 'eat' has to change the state and states can only be verified on type level at compile time. Another way to solve this would be typestates.
Sep 29 2010
next sibling parent Justin Johansson <no spam.com> writes:
On 30/09/2010 1:57 AM, Danny Wilson wrote:
 Op Wed, 29 Sep 2010 15:33:29 +0200 schreef retard <re tard.com.invalid>:

 Wed, 29 Sep 2010 09:21:11 +0200, Norbert Nemec wrote:

 I experimented with this (a colleague of mine already solved all 11 cases
 at compile time with Scala)

Would your colleague share the Scala solution? :-)

That would be nice [to share the Scala solution].
Sep 29 2010
prev sibling parent reply miasma <_ freenode.net.via_irc> writes:
29.9.2010 18:57, Danny Wilson wrote:
 Op Wed, 29 Sep 2010 15:33:29 +0200 schreef retard <re tard.com.invalid>:

 Wed, 29 Sep 2010 09:21:11 +0200, Norbert Nemec wrote:

 I experimented with this (a colleague of mine already solved all 11 cases
 at compile time with Scala)

Would your colleague share the Scala solution? :-)

Minor note about the implementation -- the state passing style isn't idiomatic Scala and the HumanFood tag might be implementable more modularly with implicits. This is just a really quick rewrite of the existing parametric C++ code. --- abstract class EnergyEntity(var energy: Int) abstract class Food(energy: Int) extends EnergyEntity(energy) abstract class Meat(energy: Int) extends Food(energy) with HumanFood abstract class Vegetable[+VegType <: Food](energy: Int) extends Food(energy) with Edible[VegType] class EatenMeat(energy: Int) extends Meat(energy) abstract class EdibleMeat(energy: Int) extends Meat(energy) with Edible[Meat] { def result = new EatenMeat(energy) } trait HumanFood trait Edible[+Result <: Food] { protected def energy: Int protected def result: Result def eaten: (Int, Result) = (energy, result) } abstract class Animal(i_energy: Int) extends EnergyEntity(i_energy) class DeadAnimal(i_energy: Int) extends Animal(i_energy) abstract class AliveAnimal[When_slaughtered, Accepted_food <: Food]( val when_slaughtered: Int => When_slaughtered, i_energy: Int) extends Animal(i_energy) { def eat[R <: Food](food: Edible[R] with Accepted_food) = { val (food_energy, food_result) = food.eaten energy += food_energy (this, food_result) } def slaughter = (new DeadAnimal(energy), when_slaughtered(energy)) } class Carrot(energy: Int) extends Vegetable[Carrot](energy) with HumanFood { def result = this } class Grass(energy: Int) extends Vegetable[Grass](energy) { def result = this } class Beef(energy: Int) extends EdibleMeat(energy) class Dead_rabbit(energy: Int) extends EdibleMeat(energy) class Dead_human(energy: Int) extends EdibleMeat(energy) class Cow(energy: Int) extends AliveAnimal[Beef, Grass](new Beef(_), energy) class Rabbit(energy: Int) extends AliveAnimal[Dead_rabbit, Carrot](new Dead_rabbit(_), energy) class Human(energy: Int) extends AliveAnimal[Dead_human, Food with HumanFood](new Dead_human(_), energy) object test { def main(a: Array[String]) { val grass = new Grass(5) val carrot = new Carrot(10) val a_rabbit = new Rabbit(100) val a_cow = new Cow(1000) val a_human = new Human(300) val another_human = new Human(350) val animals = List(a_rabbit, a_cow, a_human, another_human) for (a <- animals) println(a + " " + a.energy) val (a_rabbit2, carrot2) = a_rabbit eat carrot val (a_cow2, grass2) = a_cow eat grass val (a_rabbit3, a_dead_rabbit) = a_rabbit2.slaughter val (a_cow3, a_beef) = a_cow2.slaughter val (a_human2, carrot3) = a_human eat carrot2 val (a_human3, carrot4) = a_human2 eat carrot3 val (a_human4, a_beef2) = a_human3 eat a_beef val (a_human5, a_dead_rabbit2) = a_human4 eat a_dead_rabbit val (another_human2, human_slaughter) = another_human.slaughter val (a_human6, human_slaughter2) = a_human5 eat human_slaughter if (a_human6.energy != 1785) throw new Error("Failed") println("ok") // (new Cow(10)).slaughter.eat(grass) // (new Cow(10)).slaughter.slaughter // carrot4 eat grass // carrot4.slaughter // (new Cow(10)) eat carrot // (new Cow(10)).eat((new Cow(10)).slaughter) // a_human6 eat (new Cow(10)) // a_human6 eat grass // a_human6 eat a_beef2 // a_cow3 eat grass // a_cow3.slaughter } }
Sep 29 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Philippe Sigaud:

 If doing state passing like this is authorized, I might be doable
 doing 11/11 with D, at the type level.

From what I have seen this puzzle gives few rules, but then the implementation is quite free. It's not a true competition, with strict rules. I think the spirit of the game is to catch many violations at compile time, while keeping the program "useful". Bye, bearophile
Sep 29 2010
prev sibling next sibling parent "Danny Wilson" <danny decube.net> writes:
Op Wed, 29 Sep 2010 15:33:29 +0200 schreef retard <re tard.com.invalid>:

 Wed, 29 Sep 2010 09:21:11 +0200, Norbert Nemec wrote:

 I experimented with this (a colleague of mine already solved all 11 cases
 at compile time with Scala)

Would your colleague share the Scala solution? :-)
Sep 29 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Wed, Sep 29, 2010 at 21:59, miasma <_ freenode.net.via_irc> wrote:

Thanks for the code. It's always interesting to see some Scala!

 =C2=A0 =C2=A0val (a_rabbit2, carrot2) =3D a_rabbit eat carrot
 =C2=A0 =C2=A0val (a_cow2, grass2) =3D a_cow eat grass

Ah, but you do not change the state of carrot or grass, or do you?
 =C2=A0 =C2=A0val (a_human4, a_beef2) =3D a_human3 eat a_beef
 // =C2=A0 =C2=A0a_human6 eat a_beef2

Same remark: a_beef doesn't change state. I understood the challenge as cat= ching a_human3 eat a_beef a_human6 eat a_beef At compile-time. a_beef was eaten once, you cannot eat it again. If doing state passing like this is authorized, I might be doable doing 11/11 with D, at the type level. Philippe
Sep 29 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Wed, Sep 29, 2010 at 23:10, bearophile <bearophileHUGS lycos.com> wrote:
 Philippe Sigaud:

 If doing state passing like this is authorized, it might be doable
 doing 11/11 with D, at the type level.

From what I have seen this puzzle gives few rules, but then the implementation is quite free. It's not a true competition, with strict rules. I think the spirit of the game is to catch many violations at compile time, while keeping the program "useful".

I was wondering how you can 'return' two types from a template and then use them independantly... For example Eat!(Who, What) could be a template that returns two types (let access them through .Who and .What) which are the new states. But then, you can do that with CTFE too: auto whoWhat = who.eat(what); // eat returns a Tuple!(Who, Eaten!What) who2 = whoWhat[0]; eatenWhat = whoWhat[1]; (Damn, how I miss tuple extraction in D) eatenWhat has type Eaten!What, which is different from What and is not a food anymore. So the compiler will catch: who2.eat(eatenWhat); at compile time. The same idea can be used for slaughtering something twice, and such. But to me, that's cheating (I'm not pretending miasma's code is cheating. I am not fluent enough in Scala) Philippe
Sep 29 2010
prev sibling parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Idea: rather than trying to change state, one could attempt a different 
approach:

When "food" is "eaten", this action could define a new compile time 
object "eater(food)" as some value. When eating something twice, this 
would attempt to define the same object as two different values, causing 
a compiler error.

Of course, this still means that the process of eating must happen at 
compile time. Obviously the following can never be caught at compile time:

if(runtime_userinput) {
	rabbit1.eat(carrot);
}
if(another_runtime_userinput) {
	rabbit2.eat(carrot);
}

Which confirms my original position: the final three tests in the 
contest are flawed by concept. If the actions of eating and slaughtering 
are supposed to happen at run-time, no compiler in the world can 
reliably detect them happening twice. Of course, if the whole action 
happens at compile-time, it is a simple matter of finding a nice syntax 
to express a regular program as compile-time code (e.g. within a CTFE 
routine)





On 09/27/2010 02:26 PM, bearophile wrote:
 This is a harder variant of an old and very simple OOP problem:
 http://merd.sourceforge.net/pixel/language-study/various/is-a-cow-an-animal/

 The problem presents a hierarchy of types, some rules, and 11 tests, each one
of them represents a bug because it contains a violation of the rules. You have
to write the program in a way that the type system refuses as many of those 11
tests as possible at compile-time. There are many acceptable ways to write the
program, for example you may use functional programming, so you are able to
return different types, that enforce different rules, so it's not a contest,
it's more like a demonstration.

 A basic Python implementation catches none of the 11 tests at compile time :-)
A basic D implementation that I have written catches five of the 11 bugs at
compile time:
 http://ideone.com/87q67
 I will try to write a more statically typed D version.

 The site shows four C++ versions, the fourth is able to catch 8 of the 11 bugs
at compile-time. A type system that supports typestates is probably able to
catch all 11 bugs (because for example the Cow type has two states, alive and
eaten, and you can't perform some operations on a eaten cow, like eating it
again), but probably it's very hard to do this with D.

 The fourth C++ version contains a line that I am am not even sure how to
translate to D (maybe there is a workaround with template constraints):
 (void) static_cast<My_kind *>((Kind *) 0);

 Bye,
 bearophile

Sep 30 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Norbert Nemec:

 Which confirms my original position: the final three tests in the 
 contest are flawed by concept.

Those tree tests may be impossible to do, but they are not flawed (and they are not impossible to do, see below).
 If the actions of eating and slaughtering 
 are supposed to happen at run-time, no compiler in the world can 
 reliably detect them happening twice.

The Rust language (that doesn't exist yet, by Mozilla) will probably be able to do that. It implements the idea of "typestate". This is the old original paper about typestates, Typestate: A Programming Language Concept for Enhancing Software Reliability", by Robert E. Strom and Shaula Yemini, 1986: http://www.cs.cmu.edu/~aldrich/papers/classic/tse12-typestate.pdf In a language like D a type has no state, a int value is always an int. In a language that supports typestate you may think of a File type as a finite state machine, in each state of this FSM you are able to access only a subset of the File methods, when the state of the File type is open, you can't access the 'open' method, and so on. The transitions between those states don't happen at runtime, they happen in the code space. The compiler must analyse the code, perform some flow analysis and change the state of the File type in different parts of the program. Before the File.open() the File type is in the start state, then in the section of the code after the call to open the type of that File instance is in the opened state, and so on. So the FSM of a Cow state is just two states, alive and dead/eaten, and the compiler that supports typestates disallows the eat() method in the section of the code where the state of that Cow instance is Eaten. I'd probably like to have typestates in D3 too. Bye, bearophile
Sep 30 2010
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
In fact, I am beginning to see how a language could conceivably support 
the concept of killing a cow at runtime while ensuring at compile-time 
that it is not killed twice:

A language that allows deleting symbols from the current namespace could 
be extended to allow linking the action of killing the cow run-time 
object with deleting the compile-time symbol referring to the cow. 
Furthermore, it would have to be ensured that there is only ever a 
single reference to the cow and it would have to be prohibited that the 
cow is killed within run-time conditional blocks.

In D, definitions within a source file do not have a well-defined order. 
This solves the issue of forward references because a symbol is 
essentially defined before it appears in the source. This fact, of 
course, makes the deletion of symbols pointless because in the view of 
the D compiler, there is not "before" or "after" within a source file.

Order is only defined within routines, where local variables cannot be 
references before they are defined. The cow would therefore have to be a 
local variable in a routine. The state of the cow would also have to be 
tied to the routine where a time-order is defined.

More generally: the whole concept of type-states that have been 
discussed only makes sense within a routine. The global name-space does 
not evolve in any ordered way, and without time evolution, the concept 
of changing state does not make sense.



On 30/09/10 14:04, bearophile wrote:
 Norbert Nemec:

 Which confirms my original position: the final three tests in the
 contest are flawed by concept.

Those tree tests may be impossible to do, but they are not flawed (and they are not impossible to do, see below).
 If the actions of eating and slaughtering
 are supposed to happen at run-time, no compiler in the world can
 reliably detect them happening twice.

The Rust language (that doesn't exist yet, by Mozilla) will probably be able to do that. It implements the idea of "typestate". This is the old original paper about typestates, Typestate: A Programming Language Concept for Enhancing Software Reliability", by Robert E. Strom and Shaula Yemini, 1986: http://www.cs.cmu.edu/~aldrich/papers/classic/tse12-typestate.pdf In a language like D a type has no state, a int value is always an int. In a language that supports typestate you may think of a File type as a finite state machine, in each state of this FSM you are able to access only a subset of the File methods, when the state of the File type is open, you can't access the 'open' method, and so on. The transitions between those states don't happen at runtime, they happen in the code space. The compiler must analyse the code, perform some flow analysis and change the state of the File type in different parts of the program. Before the File.open() the File type is in the start state, then in the section of the code after the call to open the type of that File instance is in the opened state, and so on. So the FSM of a Cow state is just two states, alive and dead/eaten, and the compiler that supports typestates disallows the eat() method in the section of the code where the state of that Cow instance is Eaten. I'd probably like to have typestates in D3 too. Bye, bearophile

Sep 30 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Norbert Nemec:

In fact, I am beginning to see how a language could conceivably support the
concept of killing a cow at runtime while ensuring at compile-time that it is
not killed twice:<

Good :-)
 More generally: the whole concept of type-states that have been
 discussed only makes sense within a routine. The global name-space does
 not evolve in any ordered way, and without time evolution, the concept
 of changing state does not make sense.

I agree, in D global names don't have a true order, so a typestate can't be used (at best you may somehow manually set the initial global state of a type), you may use it inside functions. In a language like C/Pascal where global definitions too define an order, the typestate may have sense for global variables too. Bye, bearophile
Sep 30 2010