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 reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
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
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 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 reply 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
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 parent reply 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
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
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
Sep 28 2010
prev sibling next sibling parent reply 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
parent reply "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
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 parent reply 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);
 


 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.



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
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
parent reply 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.
 


 Would you mind explaining in further detail? I am not really sure what
 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
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.
 


 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.

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




 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


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

uninitialized variables, this is a very useful feature that I'd like in D too,

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 reply 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).
 


 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

 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

 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
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).
 


 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

 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

 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).
 


 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,

 variables, this is a very useful feature that I'd like in D too, but

 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 withihe n months.
 


 Are you talking about the specification of the type system here?
 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 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

uninitialized variables, this is a very useful feature that I'd like in D too,

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 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 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
parent reply "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
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 reply 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
parent reply 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
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