Some help wanted in class design -- Immutability

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi folks,

I’d appreciate some input on a design problem I’m having trouble with.

I have a class CompactFunction, which is basically an implementation of
an MDD (Multi-Valued Decision Diagram), a generalisation of a BDD
(http://en.wikipedia.org/wiki/Binary_decision_diagram). This is
expanded to model non-determinism, with a whole bunch of methods that
make it suitable for modelling the transition function of a tree automaton.

The class Automaton models, guess what, an automaton. It is immutable.
(I like immutability, it helps keeping an overview.) Since it contains
a function, which can be asked for, CompactFunction should be immutable too.

OTOH, I want to be able to create this function step-by-step, adding
transitions one after the other. This is needed for some manipulations
(determinisation, minimisation), and to offer a way to create initial
functions in the first place. Until now, I had a CompactFunctionBuilder
for this. It builds a decision tree from the transitions it gets, and
reduces that tree when getFunction() is invoked.

However, my preliminary implementation of reduction has an error, which
makes a reduction of the function that has been built necessary. The
problem is the following: no function builder is used here, since
transitions are not computed one by one, but based on the graph
structure of MDD. However, reduction is implemented in the builder.

This leads me to think I should get rid of the builder class and put the
reduction logic in the function itself. But then I would have to allow
adding single transitions too, which would loose the immutability of the
CompactFunction class.

And here’s my query, for anyone so kind to read this far: what would be
the right way to go here?
- - implement the reduction in CompactFunction too (sort of duplicating
most of the work of the builder), and keeping the builder
- - make CompactFunction mutable, providing some sort of protection if one
asks for an automaton’s function (mind that an MDD is a graph, so
copying is complicated and expensive), getting rid of the builder
- - other suggestions?

I’d be happy to clarify if things are too vague.

Thanks,
H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFF5bzCe+7xMGD3itQRAhJtAJ4nmA6TonYWfmeif6J92eIoqfAahwCdERDw
ujXE+dAnjPTjhQsKHpEJX/w=
=6kkB
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hendrik Maryns schreef:

Hi folks,

I’d appreciate some input on a design problem I’m having trouble with.

I have a class CompactFunction, which is basically an implementation of
an MDD (Multi-Valued Decision Diagram), a generalisation of a BDD
(http://en.wikipedia.org/wiki/Binary_decision_diagram). This is
expanded to model non-determinism, with a whole bunch of methods that
make it suitable for modelling the transition function of a tree automaton.

The class Automaton models, guess what, an automaton. It is immutable.
(I like immutability, it helps keeping an overview.) Since it contains
a function, which can be asked for, CompactFunction should be immutable too.

OTOH, I want to be able to create this function step-by-step, adding
transitions one after the other. This is needed for some manipulations
(determinisation, minimisation), and to offer a way to create initial
functions in the first place. Until now, I had a CompactFunctionBuilder
for this. It builds a decision tree from the transitions it gets, and
reduces that tree when getFunction() is invoked.

However, my preliminary implementation of reduction has an error, which
makes a reduction of the function that has been built necessary. The
problem is the following: no function builder is used here, since
transitions are not computed one by one, but based on the graph
structure of MDD. However, reduction is implemented in the builder.

This leads me to think I should get rid of the builder class and put the
reduction logic in the function itself. But then I would have to allow
adding single transitions too, which would loose the immutability of the
CompactFunction class.

And here’s my query, for anyone so kind to read this far: what would be
the right way to go here?
- implement the reduction in CompactFunction too (sort of duplicating
most of the work of the builder), and keeping the builder
- make CompactFunction mutable, providing some sort of protection if one
asks for an automaton’s function (mind that an MDD is a graph, so
copying is complicated and expensive), getting rid of the builder
- other suggestions?

I’d be happy to clarify if things are too vague.

Well, doesn’t really surprise me that I got no answer here (yet), but
after thinking about it for a while, I decided to go the same way I do
with Sets: declare an interface that allows some methods to throw an
UnsupportedOperationException, and create a class ImmutableFunction,
then let my compact function be mutable, implementing the interface, but
wrap it in the immutable Automaton class.

Getting to work now...

Comments still welcome, though.
H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFF5rhje+7xMGD3itQRAhQvAJ4pG80mpY8ThP4BfuNBbDfhjXanggCeMhA6
kKfJEGRaypNPu6B6JDpyUeE=
=h5JV
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hendrik Maryns schreef:

Hendrik Maryns schreef:









Well, doesnt really surprise me that I got no answer here (yet), but
after thinking about it for a while, I decided to go the same way I do
with Sets: declare an interface that allows some methods to throw an
UnsupportedOperationException, and create a class ImmutableFunction,
then let my compact function be mutable, implementing the interface, but
wrap it in the immutable Automaton class.

Getting to work now...

And in doing this, still another solution is emerging: have Automaton
use an interface, which does not include the muting methods. Since it
returns its function as an instance of this interface, the muting
methods will still not be available. They will, if somebody casts it
down to a specific implementation, but I think I will take that risk, in
favour of cleaner design and one level less of nesting.

Comments still welcome, though.
H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFF5u8/e+7xMGD3itQRAkXoAJ0XQ7flxz5v6gyRBoZEedCxtdjAbACfZRt3
xYr27RRG8L0Bh2G14niM5T8=
=v1nA
-----END PGP SIGNATURE-----

 

[Chris Uppal]

However, my preliminary implementation of reduction has an error, which
makes a reduction of the function that has been built necessary. The
problem is the following: no function builder is used here, since
transitions are not computed one by one, but based on the graph
structure of MDD. However, reduction is implemented in the builder.

I may be misunderstanding you, but if you are considering changing your
architecture because of a bug in your own code, then I strongly urge you not
to. Fix the bug !

You have (what sounds like) a nice, clean, understandable architecture; with
well-defined roles for all the objects. The only good reason for changing that
design is if this problem is showing you that the design isn't as good as it
sounds (the roles are badly assigned, for instance).

I would say that the way each object has a clear role to perform is more
important (quite a lot more important) than any consideratations of mutability.
So make the design right, /then/ consider which objects, if any, can be made
logically immutable. Only /then/ consider what implementation tricks and
techniques you can use to implement that immutability (and make sure that
whatever tricks you choose don't warp your initial design).

Still, if you are finding that your original design was wrong in that the
Builder should never have had responsibility for reducing the tree, then you
can change the design. Maybe the Builder's only responsibility is to know how
to build the initial tree (before any reduction, etc). If so then its role is
reduced, but still coherent. But maybe now it's name is a little misleading --
it could be seen as more of a /description/ of a tree (a specification for the
tree in some logical space, distinct from the messy optimised version which
will finally be used when the automaton executes).

(BTW, I'm currently facing similar kinds of design problems in a related space:
runtime specifications of grammars, and derivations of parsers for those
grammars. I'm having trouble working out which of the Grammar, the Parser, the
GrammarBuilder (if I decide to add these), or the caller of the code, should be
responsible for ensuring that whatever modifications to the Grammar
(potentially of several sorts) are made in order to ensure that the Parser
(also of several sorts) is able to implement the grammar....)

-- chris

 

[Lew]

And in doing this, still another solution is emerging: have Automaton
use an interface, which does not include the muting methods. Since it
returns its function as an instance of this interface, the muting
methods will still not be available. They will, if somebody casts it
down to a specific implementation, ...

Not if the immutable version is a subclass of the mutable version, and
overrides the mutators. Also not if the immutable version is a copy of the
mutable one or a wrapper for one that delegates to the mutable class's accessors.

- Lew

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Chris Uppal schreef:

I may be misunderstanding you, but if you are considering changing your
architecture because of a bug in your own code, then I strongly urge you not
to. Fix the bug !

Hm, almost too late by now, I’ve been jamming into it already, and
reverting would be as big a pain as going on, I’m afraid.

You have (what sounds like) a nice, clean, understandable architecture; with
well-defined roles for all the objects. The only good reason for changing that
design is if this problem is showing you that the design isn't as good as it
sounds (the roles are badly assigned, for instance).

Makes sense. Only: how to decide this last point? I think the bug (and
new insights) suggest the design wasn’t that good (it was a temporary
implementation for testing originally), but it is difficult to draw the
line here.

I would say that the way each object has a clear role to perform is more
important (quite a lot more important) than any consideratations of mutability.
So make the design right, /then/ consider which objects, if any, can be made
logically immutable. Only /then/ consider what implementation tricks and
techniques you can use to implement that immutability (and make sure that
whatever tricks you choose don't warp your initial design).

Makes sense again. Maybe now I am confusing roles in that I make a
function responsible for building itself.

Still, if you are finding that your original design was wrong in that the
Builder should never have had responsibility for reducing the tree, then you
can change the design. Maybe the Builder's only responsibility is to know how
to build the initial tree (before any reduction, etc). If so then its role is
reduced, but still coherent. But maybe now it's name is a little misleading --
it could be seen as more of a /description/ of a tree (a specification for the
tree in some logical space, distinct from the messy optimised version which
will finally be used when the automaton executes).

Sounds good. Maybe I can move only the reduce() method into the
function, but make it package accessible, such that the builder has
access to it if it is finished, and the function can use it itself.

(BTW, I'm currently facing similar kinds of design problems in a related space:
runtime specifications of grammars, and derivations of parsers for those
grammars. I'm having trouble working out which of the Grammar, the Parser, the
GrammarBuilder (if I decide to add these), or the caller of the code, should be
responsible for ensuring that whatever modifications to the Grammar
(potentially of several sorts) are made in order to ensure that the Parser
(also of several sorts) is able to implement the grammar....)

Yes, that sounds very similar.

Thank you very much, your comments are very useful to show me some more
angles to look at the problem.

H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFF6AA7e+7xMGD3itQRAsN8AJ4kcfvAJ2nWN3EcHqhztNmktVCX3ACeKXqP
+WemJ0jizVBIpig2Iz7dms0=
=0cBh
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Lew schreef:

Not if the immutable version is a subclass of the mutable version, and
overrides the mutators. Also not if the immutable version is a copy of
the mutable one or a wrapper for one that delegates to the mutable
class's accessors.

Hm, yes, I had a wrapper initially, but thought I could do without if I
offer people only the interface, which does not have the mutators. That
is not safe for casting. But I probably will change the design once
more, after reading Chris’s post.

As for subclassing: I try to use that only where it is really necessary,
in this case a decorator would do as well.

Thanks, H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFF6AC3e+7xMGD3itQRAvE9AJ9Hwe3nhalXcU7I4QF9TDTYTiXdFACff5Dg
BLZQTCVLLpOyjJU0U/NcEl4=
=AFWJ
-----END PGP SIGNATURE-----