Eliminating special cases - a case study

Eliminating special cases - a case study

Post by phlip_cp » Sat, 06 Dec 2003 08:37:41


omp.object:

The XP mailing lists gets some great non-XP posts sometimes:

----8<------------------------------

Several months ago I attended my friend Payson Hall's excellent
problem-solving class. One of his problem-solving hueristics is to
try to simplify the problem before solving it. And sometimes
simplifying requires you to introduce a bit of complexity.

To illustrate the hueristic, he told us about how he once wrote a
program to play the solitaire card game Klondike (aka Canfield). As
he wrote the program, he noticed that a great deal of code was devoted
to special cases. For example, when you're playing to the tableau
(the seven piles of cards that you deal out in the starting position),
the usual rule is that you can play a card onto any opposite-colored
card of the next-higher rank -- that is, you can play a red 8 on a
black 9, or a black jack to a red queen. There is a special case
having to do with spaces (empty piles): You can play a king to a
space. So cards ace through queen have one rule, and kings have
another.

Another special case: playing to the foundation (the four initially
empty piles to which you ultimately play the cards). The general rule
in the foundation is that you can play a card to a same-suit card of
the next-lower rank -- you can play the three of clubs onto the two of
clubs. The special case: Aces are played to an empty foundation
pile. Cards 2 through king have one rule, and aces have another.

I loved Payson's way of simplifying the code: Introduce a slightly
more complex starting position.

The foundation piles don't start out empty, instead each has a face-up
card of a new rank: the Naught -- the naught of clubs, the naught of
hearts, and so on. The rank of a naught is zero. You can play an ace
onto a naught of the same color.

Visually, the naught cards are completely transparent. Though they're
there on the screen, you can't see them. A pile with only a naught
looks exactly like an empty pile. And because Payson's program
automatically moves cards to the foundation when possible, the user
never has to see which invisible card to play to. When the ace of
clubs appears, the program automatically plays it onto the naught of
clubs.

The tableau piles also have something new: Before dealing the cards
to the tableau, place onto each pile a face-down card of a new rank
and suit: the Emperor of Emeralds. Emperors outrank kings by one.
Now, when you move the next to last card from a pile, you flip over
the remaining card, the Emperor. The rule for playing to the tableau
becomes: you can move a card onto any different-suit card of the
next-higher rank. Not the opposite suit -- there are now three suits
-- but different suit. Most cards still behave the same way. Black 8
on red nine. But you can now move a king onto any Emperor of a
different suit -- that is, onto any Emperor of Emeralds.

As with the naughts, the Emperors of Emeralds are transparent. A pile
with only an Emperor looks empty. But you can't move an Emperor --
not because there are no empty spaces, but because there are no
higher-rank cards. Same rule as for the other cards.

The special cases for playing kings to the tableau and aces to the
foundation are now gone. Those moves work just like all other moves.
Greatly simplified code, for the cost of a slightly more complex
starting position.

Dale

--
Dale Emery -- Consultant -- Resistance
 
 
 

Eliminating special cases - a case study

Post by Dave Benja » Sat, 06 Dec 2003 08:45:55


That's funny... I was just about to comment that it reminded me of the Null
Object pattern when I read your comment at the bottom. I am a fan of this
technique as well.

--
.:[ dave benjamin (ramenboy) -:- www.ramenfest.com -:- www.3dex.com ]:.
: d r i n k i n g l i f e o u t o f t h e c o n t a i n e r :

 
 
 

Eliminating special cases - a case study

Post by Phli » Sat, 06 Dec 2003 14:21:23


Null

Note to the Real-Worlders:

In the Real World, decks of cards don't contain Naught ranks or Emerald
suits.

In the Real World, there are no Null Objects. (At least, philosophically,
they are either useless or not-Null.)

This is the situation I had in mind during this week's debate, but I didn't
push the issue because I couldn't think of a good example. This is it, in a
nutshell.
 
 
 

Eliminating special cases - a case study

Post by H. S. Lahm » Sun, 07 Dec 2003 08:05:52

Responding to Phlip...


True, which is why this solution is not a good OO solution. The problem
space has not been abstracted properly. Similarly, the original
solution did not provide good abstraction abstraction of the problem
space either, so one has just substituted one kludge for another. The
differences lie in the way the abstraction problem is manifested
(complicated assignment code vs. complicated set up code).

The problem arises when one models the tableau in terms of a "deck of
cards" having suits and ranks. Try separating the tableau structure
from the deck of cards and model the Tableau in terms of slots rather
than Cards. Now Slot.value can have the data domain of {0, card value)
and Slot.color can have the data domain of {Red, Black, Background}
while Card.value has the data domain of {card value} and Card.color has
the data domain of {Red, Black}.

Now the rules for validating playing a Card to a Slot (i.e.,
instantiating the relationship) are exactly the same for all situations
of current Slot occupancy, just like the Naught/Emerald approach. In
addition, by properly separating the concerns of the Tableau structure
from the concerns of a deck of playing cards, one can introduce a Deck
and deal the Tableau without worrying about the special rules for having
a phony transparent card on the bottom of each Slot stack. [The
complications of a hoaky setup have been replaced with a simple check
for no more cards assigned in Slot.removeCard(), which is made exactly
the same way whenever a card is moved from one Slot to another.]

Note also that the basic classes of Tableau, Slot, Deck, and Card and
their relationships can be reused for other solitaire games like Spider
that have notions like in-suit sequences and where color is an
insufficient designator of suit. [Try moving a sequence of cards in
suit in Spider when the bottom card is phony. Enter stage left: a
special case.] The Tableau, Slot, Deck, and Card base is easily
extensible to games like Spider because the basic invariants of
solitaire have already been captured through proper problem space
abstraction (mainly the separation of concerns of layout vs. cards
associated with the layout).


*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
XXXX@XXXXX.COM
Pathfinder Solutions -- Put MDA to Work
http://www.yqcomputer.com/
(888)-OOA-PATH
 
 
 

Eliminating special cases - a case study

Post by Univers » Sun, 07 Dec 2003 09:33:39

Phlip


You'd think people wouldn't be eager to not be a "real worlder".

Emerald
philosophically,

A thing's or processes null object is an object that is not in the thing
or process.

I don't understand why this is hard to comprehend if one studied Set
theory in grade school.

Every set is comprised of its elements AND the null element. A set with
only a null element is the "Empty" set.


Or even an OO solution period.


And this is *precisely* what is wrong with many of the xp'ers so-called
"unsuitable OO designs/solutions". They come up with what they think to
be the best OO design, and trash it thinking that disposes of the OO
approach to the problem.

But why are these people so confident they have come up with an OO
design, or the best OO design?

Why are these people so confident they understand the domain and use
cases in an OO, or best OO manner?

And especially since these are people who readily admit that typically
their upfront designs do not work out?

Elliott
--
The thing is that doing holistic investigation and creating
holistic plans at all times takes us as far ahead in terms of
understanding, as rapidly as possible while implementing in a way that
supports everything that we know will be incorporated.
 
 
 

Eliminating special cases - a case study

Post by Ron Jeffri » Sun, 07 Dec 2003 13:58:15


As far as I know, none of the commonly used axiomatizations of set theory refer
to a "null element". They do often refer to the null or empty /set/, i.e. the
set such that for all x, x is not an element of the null set.

The notion of a null /element/ does appear in algebra -- a null element, under
some operation "op" is an element 0 such that for all x, x op 0 = x

In addition, the null element is zero. In multiplication, the null element is
one.

The basic concepts of set theory are "set", and "membership", not members and
null element. For more information, see, for example,
http://www.yqcomputer.com/
was initially defined. Axiomatic set theory, described at
http://www.yqcomputer.com/ , takes a more complex
approach to set theory. This approach has few practical implications, as it
addresses, primarily, issues that arise when we consider operations on infinite
sets.

--
Ronald E Jeffries
http://www.yqcomputer.com/
http://www.yqcomputer.com/
I'm giving the best advice I have. You get to decide whether it's true for you.
 
 
 

Eliminating special cases - a case study

Post by Phli » Sun, 07 Dec 2003 22:16:11


philosophically,

When judging two designs you cannot claim one's better because it more
closely models the real world in objects.

I suspect your design is better, anyway.


However, this design also does not more closely model the real world.


While modeling the cards as values instead of objects would of course have
occurred to me, I don't know if this solution isn't just isomorphic to the
other one, with similar behavior applied to different structure.

But one should credit a design for how well it works and - to a much lesser
extent - how well its programmers understand it. Not whether it avoids hokey
objects not found in the real world, or whether the design supports
potential re-use into features not yet requested.

I understand perfectly well you are more capable of holding an object model
in your head than most. So could _your_ design become even simpler, for
Solitaire alone, if you added to your values the Naught rank and Emerald
suit?
 
 
 

Eliminating special cases - a case study

Post by S Perryma » Sun, 07 Dec 2003 22:38:06


philosophically,





A classic '15 minute' analysis of this particular variant of the "patience"
game
gave me a formal specification that suggested a "naught" or "emperor" of
anything is a wasteful irrelevance. Said analysis immediately suggested an
OO
design that was nothing more than a card entity, a stack entity, and the
means of
associating a mathematical constraint relationship with any stack (the
latter part
being so powerful in its abstraction that it immediately gave a reusable
domain
framework usable far beyond the game itself) .


Regards,
Steven Perryman
 
 
 

Eliminating special cases - a case study

Post by H. S. Lahm » Mon, 08 Dec 2003 05:16:04

esponding to Phlip...


For OO development one can and should. OO is based upon abstracting the
problem space and OOA is /exclusively/ based on doing that...



It models the real world of the solitaire problem space. Where does the
notion of 'tableau' come from, if not that real world? I could have
used Layout, but that would not have been so well tied to the specific
problem space.

Remember, real world == problem space in OO development. The computing
space is also real world from an OO viewpoint when abstracting something
like a GUI paradigm into Window/Control. Similarly, mathematics is real
world if one is abstracting computational methods. And hardware is a
real world if one is abstracting for device drivers.


But I wasn't modeling cards as values; I modeled them as Cards, which is
pretty straight forward. The real abstraction lay in abstracting --
separately -- the structure of the layout. A Card is something with a
value and color that gets assigned to a Slot, which also happens to have
a value and color.

It isn't isomorphic because the data domains of 'value' and 'color' are
different for Card and Slot in my version so they are asymmetric.


My counter is that the closer one maps the software to the problem
space, the more understandable it will be. (More precisely, the more
communicable it will be.) That's because the lingua franca among
developers has to be their domain expertise. As developers come and go
over the software life cycle the one invariant is a common perception of
the problem space. So any deviation that represents a particular
developer's unique vision or interpretation introduces long-term risk,
no matter how elegant and sound it may seem at the time.


If you want to do simple, elegant, and intuitive, then do functional
programming. If you want to do robustness in face of volatile
requirements over time, then do OO programming. Simplicity is not a
virtue in itself and when one counts the LOC in an OO application versus
the LOC in an FP application, it becomes painfully obvious that OO is
not the simplest way to implement software solutions.

I have no problem with XP's simplest-possible-thing mantra /provided/ it
is qualified with being sound OOA/D practice. Properly abstracting the
problem space with separation of concerns, etc. is part of good OOA/D
practice and, IMO, takes precedence over simplicity.

For example, I routinely introduce classes and is-a relationships for
the sole purpose of eliminating conditional relationships. That's
because navigating conditional relationships requires additional
/executable/ code in every navigation context and I am quite happy to
pay the price of dozens of extra /declarative/ lines for defining a
class to eliminate those executable lines. Why? Because it makes the
program more robust (relationship management is always done in one
place) and reliable (defects are directly proportional to executable
LOC). [No, I don't eliminate /all/ conditionals. B-)]

Note that XP doesn't really believe simplicity is a virtue in itself
either. When one refactors to get a nice DAG, one routinely adds
classes, relationships, and code to support them. So one doesn't end up
with the simplest possible implementation. All XP is doing is using
disciplined refactoring to add complexity that makes the code more
maintainable. I submit that good OOA/D abstractio
 
 
 

Eliminating special cases - a case study

Post by Phli » Mon, 08 Dec 2003 05:39:04


Ooooh! I'l find a way to technically disagree with you, yet!


There! I don't do CRCs! I barely know what they are.
 
 
 

Eliminating special cases - a case study

Post by phlip_cp » Mon, 08 Dec 2003 06:46:40


One wonders if you would have agreed with that post, not knowing its
source.

No matter. Let's play with the metrics. Suppose we give a single 'if'
statement a higher cost than a Null Object. (Not execution cost -
programmer's cogitive cost.)

If we declare by fiat that 'if' statements cost more, whose design now
has the lowest cost?


I tend not to say that kind of thing about my abstractions. I still
need to be able to get my head thru doors.

--
Phlip
 
 
 

Eliminating special cases - a case study

Post by Michael N. » Mon, 08 Dec 2003 16:35:16

Lahman - you're a smart guy - but you would seem smarter if you could reduce
the verbosity of your posts by about 60%.



l8r, Mike N. Christoff
 
 
 

Eliminating special cases - a case study

Post by Hast » Mon, 08 Dec 2003 17:29:15

In article <0LAAb.18524$ XXXX@XXXXX.COM >,
XXXX@XXXXX.COM says...

Hehe, indeed I found his posts in this thread very good.

But I would say 20%, at most; it's so hard to be both
concise and complete... We cannot ask him to spend THAT
time for us :-)


Cheers, Mike
 
 
 

Eliminating special cases - a case study

Post by » Tue, 09 Dec 2003 17:00:20


But is it a good solution?

Take care, Ilja
 
 
 

Eliminating special cases - a case study

Post by ggroup » Tue, 09 Dec 2003 20:21:25


No.
Because unlike you, I can agree or disagree with anyone based on
*content* and regardless of allegiance (perceived or actual) .




No.
Lets see the entire impl of this persons' , and see whether it is full
of "abstractions" (such as those given) that are actually redundant or
irrelevant.

The formal specification camp bids :

- 5 mathematical relationships describing the properties of each of the
card "stack" types needed for this game.
- One basic card stack type.


What does the Emperor bid ... ??




Ah, I see.

You being unable to precisely/succinctly model a subject domain would
explain why the above (immediately seeing abstraction more powerful
than the intended context) would be very difficult for you.

It would also explain why you need to write "lots and lots of little
tests" whereas I do not.

You have my sympathies on these matters.


Regards,
Steven Perryman