Showing posts with label design. Show all posts
Showing posts with label design. Show all posts

Thursday, January 17, 2013

Java (OOP) is sux from the very beginning

I knew for a while that composition must be used instead of inheritance. I just realized that there is no one example (stackoverflow was asked explicitly) when inheritance would be preferred. Never! The very inheritance, the cornerstone of OOP (Java is OOP), is considered a bad practice! Integer extends Number, FilterInputStream extends InputStream, which extends Closable. Java begins with Object whereby every other object inherits a dozen of fields (lock, hash, class) and 11 methods (wait, getHash, getClass) from it.

Notably however, design pattern experts who make us thinking that inheritance is evil and stone age structural composition must always be used instead, promote OOP and the idea that we must replace conditionals with polymorphism! (which is achievable only through inheritance in OOP languages). For no reason [1], [2], [3]!

Update The last bullet is that tight coupling between functions and data is bad.

Wednesday, January 16, 2013

Automatic (shared attributes-based) subclassing

In my design hierarchy I simulate a language whereby all objects have some type. It is the same as instances refer the class they belong to. The class (identically, a type) is nothing more than a set of properties (aka attributes or fields), common to all instances (aka objects) of the class. Now, there is a flyweight pattern which says that to save memory we must factor out the common invariants rather than copy them into every instance. For instance, you have a Boolean object, which refers class Boolean and bears a bit of information. However, all immutable instances that bear constant True in them, could just refer a subclass of Boolean, BooleanTrue and elimiate the need to bear the bit of information. The flyweight reference matches with the type reference. This coincidence motivated me to think that is is ok because classes are exactly the invariants, shared by instances. The BoolTrue could also simultaneouly represent a class and instance (multiinheritance) at the same time so that not even instances (and thus instance refs to the class) are necessary. You have only two instances: BoolFalse and BoolTrue! Whenever you need a boolean value, you just refer one of them.


Suppose you have an object that may be an
Object
  category: signal, variable, constant
  direction: none, intput, output, both

Theoretically, we have only 3x4 = 12 subclasses of object.  For the million of instances, I would like to allocate no more than 12 objects. If object has additional fields, e.g. location attribute (row:int, col:int), all input signals with the same location (say x0, y0) would be a subclass of InputSignalObject. Here, we must fix the field order (like in ROBDD) in order to prevent InputSignal and SignalInput appearing in our space and mistreat them as different classes (I think that only arrays of arrays are possible to program whereas conceptually we have a 2d array).

Secondly, because of combinatorial explosion, we can subclass only enumerations (creating a subclass for every point(x,y) might be an overkill) it might be good to create subclasses lazily, on-demand, when the instances are instantiated. The root class, redirects object construction, enumerates the enumeration-type fields and redirects the construction to the subclass to a subclass.

so that at each level a set of classes is created. Though, multiple levels can be combined if their fields always come together. For instance, OutputConstant can have concrete fields dir=Out and category=Const, since no path from Const to anything else exists. This might be especially true for classes with discrete range and reference fields because they do not split as enums.

There is a flyweight pattern but it does not consider the common base as a part of class.

I blur the line between class and its instances. As class comes down to only one instance, it represents the class. Suppose a million of boolean instances mapped to only two, True and False instances which are also classes. It should be a huge saver!

Is it a DB, OOP or Computer Science topic? I see that greatest lower bouńd of two objects can be tracked with (Featherweight) Typestates. The typestates are types, whose level of instance initialization can be tracked. But, I do not understand those articles very well.

This dream happens to be in on the track started by advise to save memory via polymorhpism-based parametrizing.

Saturday, January 12, 2013

Device Interface for Chinig and Flexible Data Pumping

Thinking about proper interface for the mad mp3 library, I have come to the following generalization. So, I'm discussing chaining of programmatic devices.

There are three types of devices: data producers, processors and consumers. You chain them together to produce some output. The input and output devices can be network sockets, files and audio devices, for instance. The examples of processors are decoders. Suppose, you get mp3 input from a file/network, decode it and output to audio card. Input devices have read method, output devs have write. It is reasonable, therefore, to have both on intermediate devices. Modern audio libraries are so sophisticated that I believe you could use one for any processing of any data, using their plug-in mechanism. I propose a simple one.

Mad library provides you with a mp3 decoder. Before using it, you initialize the lib by providing input, output, error and other callbacks to it. To decode a file, I suppose, you use a thread to call decode() method which will invoke in callback to get the data from the input and out callback to write the result to output. This is not convenient for chining. Suppose, we read the data from another decoder or encoder of similar kind. The only way to run both would be to use two pipelined threads. However, there is no reason add complexity and load processor with multiple contexts and insidious synchronization. There is no need for more threads (virtual processors) on a computer that the number of real processors.

The interface convenient for chining, which can additionally be run by a single thread would be:
input.read -> filter1 -> filter2 -> ... -> output.write .

The filters have read and write methods. You perform the data pumping by spinning with your thread in one of the links reading from input and writing to the output. For instance:

//prepare the chain
createChain();

// choose a link to drive
in = input;
out = in.next;

// pump
int size;
while ((size = in.read(buf, BUF_SIZE)) != 0)
out.write(buf, size);

Writing into an intermediate node, pushes data into it. It makes some processing (it is useless otherwise) and writes the data into its next node. Reading the data from intermediate node would cause read callbacks in the object, invoking the read method of its predecessor node in the chain. In this uniform way, we can drive any data chains by a single thread. The interface would be blocking for this reason and simplicity. I call the nodes 'devices'. All the communication devices already implement the read and write methods.

Nothing prevents you to use more threads with pipeline nodes to enable more threads for multiprocessor computers. The architecture can be further optimized by hiding all the chain implementation code into an io library. User just builds a chain of required devices and invokes its pump() method. It will exit on EOF at the input.

This approach is also universal being not addressed/intended for specific language/platform. I admit there are more convenient interface standards and going to investigate this. For instance, Java allows for uniform chaining with their InputStreamFilter interface. This is good, since it is a standard, the uniform interface which simplifies the life preventing loads of useless work. You read data from input chain and feed them into an output chain. You are constrained to use only one point for pumping the data. A read on the input stream will call the underlying stream, which will call the underlying stream, etc. This approach is simple but limited. A simple example consider a BufferStream. In Java, you have two objects depending on whether you need to buffer the input or output. And you should have two objects for everything. Otherwise, you may not be able to build a chain in some situations. For instance, there you may be forced to buffer output feeding it to mp3 decoder, while there is only mp3 decoder input stream which exists.

My approach: a filter object with input and output interface. You build a chain by connecting output of preceding node with input for the next.

filter = new Filter();
filter.setOutput(someNode.input)

Of course, there should be convince constructors, like in java allowing one-statement chining:
Filter (predcessor.out) -- creates a filter, which input is linked to the pred output
Filter (follower.in) -- creates a filter, which output is linked
Filter (predcessor.in, follower.out) -- creates completely linked filter


My approach enforces existence of both the the input and output interfaces on the plug-ins. On the other hand, it is not hard to create at output stream given an input stream and vice versa. So when You have a decoder, from which you can only read decoded PCM, you can easily create an output stream, which decodes your written data and forwards it into underlying stream. Am I wrong?


In this discussion, Processor, Filter and intermediate note are synonims.

Saturday, July 28, 2007

A Circular Fixed Size Log File Concept

This is a story on adding a line of text to a log file.

It is not good that the log file grows infinitely. Since the outdated records are normally of no use anyway, the file can be made circular -- whether of limited line numbers or limited size. The first better addresses the obsolescence issue while the latter better controls the storage resource and thus is of more preference in the embedded real-time systems, where resources are preallocated.


Here, EOL, NL, LF, CRLF and '\n' all are the same newline character.

When created, it is filled with arbitrary characters. The first line of fixed size keeps a pointer to begin and end of the buffer. Reader reads records from the start; writer appends lines to the end. Written a message, the writer moves the writing pointer to the end of just-written line and reading position is shifted beyond the end of overwritten record if writer crosses the reader position.

If the message is longer than the file, it is written at the file start and is ended by ellipsis ... char. Or log exception is to be thrown?

The lines can be read by line readers. Reading the last line wraps to the file beginning if no EOL is present at the EOF.

Sunday, May 6, 2007

Rollbacks -- Destructors for successfully and partially conustructed objects.

keywords: try-except, try-finally, constructor-destructor, allocate-free, create-free, deallocate, dispose




Dealing with exceptions within a method
Normally, any programming task involves allocation of resources (memory, system object, file, device, etc), their use and disposal. Schematically, this can be exelmplified by the following listing:
-- Listing 1 --
res1 = allocate_res1();
res2 = allocate_res2();
use(res1, res2);
free(res2);
free(res1);

The example with two resources can be easily extended to n resources. The problem is that allocation and use of resources may cause errors (mem not available, dev does not support an op). The errors interrupt the normal flow of execution and unwind the call stack untill the error is 'caught' and processed. In the languages that do not support exceptions you are taught to do like in listings 2, 3 or 4:
-- Listing 2 --
if (res1 = allocate_res1()) {

if (res2 = allocate_res2()) {
if (!a_use(res1, res2)) {
print("a failed");
goto use_failure;
}

if (!b_use(res1, res2)) {
print("b failed");
goto use_failure;
}

use_failure:
free(res2);
} else
print("could not alloc res2");

free(res1);

} else
print("could not alloc res1");



-- Listing 3 --
res1 = allocate_res1();
if (!res1) {// failure
print("failure allocating res1");
goto exit;
}
res2 = allocate_res2();
if (!res2) {// failure
print("failure allocating res2");
goto res1_rollback;
}

if (!a_use(res1, res2)) {
print("a failure");
goto res2_rollback;
}

if (!b_use(res1, res2)) {
print("b failure");
goto res2_rollback;
}

res2_rollback:
free(res2);

res1_rollback:
free(res1);

exit: // nothing to free


-- Listing 4 --

res1 = null;
res2 = null;

res1 = allocate_res1();
if (!res1) {
print("res1 allocation failed");
goto release;
}

res2 = allocate_res2();
if (!res2) {
print("res2 allocation failed");
goto release;
}

if (!a_use(res1, res2)) {
print("a failure");
goto release;
}

if (!b_use(res1, res2)) {
print("b failure");
goto release;
}

release:
if (res1) free(res1);
if (res2) free(res2);


The first observation is that error handling inflates code multiple times. It is a serious issue therefore. The repeated code patterns could be C-macros generated to some extent. The widely-propagated approach presented in listing 4 additionally entails two additional redundant sections: preallocation initialization and if-initialized check in release. This additional code bloat degrades both code managability by human, storage , compilation and runtime processing overhead. Let's call it a 'wasting approach'.

In exception-enabled languages, the amount of coding can be considerably reduced altogether with gotos elemination:
-- Listing 5 --
Win32Check(DWord RetVal, context) {
if (RetVal = 0)
raise Win32Exception.Create(context);
}

Win32Check(res1 = allocate_res1(), "allocating res1");

// allocation was successfull, enter try-finally for res1
try {
Win32Check(res2 = allocate_res2(), "allocating res2");
try { // res2 try-finally
Win32Check(a_use(res1, res2), "execution of a");
Win32Check(b_use(res1, res2), "execution of b");
} finally {
free(res2);
}
} finally {
free(res1);
}
free(res2);

When the library is exception-aware, the code is further simplified to:
-- Listing 6 --
Res1 res1 = new Res1();
try { // try-finally to deallocate res1
Res2 res2 = new Res2()
try {
res1.use(res2);
res2.use(res1);
} finally {
res2.Free();
}
} finally {
res1.Free();
}


I do not understand the pinheads that still insist on wasting approach under single-finally section:
-- Listing 7 --
Res1 res1 = null; // initialize to invalids
Res2 res2 = null;
...
Resn resn = null;
try {
res1 = new Res1();
res2 = new Res2();
res1.use(res2);
res2.use(res1);
} finally {
if (res1 != null) res1.Free(); // check for initialized before calling free
if (res2 != null) res2.Free();
...
if (resn != null) resn.Free();
}



Imho, the latter, in addition to being the waste approach, defeats OOP. The exceptions are mostly feature of good OOP languages and are intended to replace the 'big switch' solution of structural programming by polymorphism:
-- Listing 8 --
void draw(shape)
switch (shape) {
case point: drawPoint();
case line: drawLine();
case circle: drawCircle();
...
}

in OOP is implemented by a set of shape classes:
class Point extends Shape() {
void draw() {
...

class Circle extends Shape() {
void draw() {
...

void draw(shape) {
shape.draw();
}


I would like to ask them: what is the advantage of conditional resource release if we know that object should be released only if it has created successfully and we know that it has created successfully if construction succeeded? IMO, the try-finally is exactly for the purpose to be used after every successful allocation:
-- Listing 9 --
obj = create()
try
use(obj)
finally
free(obj)


We have revised the simple allocate-use-deallocate blocks that are typically found in routines. But what if allocation, use and release are spread across different routines? Use of constructors and destructors implies such separation. Such scattered code cannot use try-finally to ensure the release of resources.


Con- and De-structors
Constructors are intended for initialization of object fields. Since objects consist of some other subobjects, it is natural for constructors to allocate these basic parts. This typically involves memory but also can include opening of files, synchronization objects, connections and other devices. Destructors are used to free the allocated resouces. It is responsibility of user to call a destructor, once object is created. Destructors must not raise errors/exceptions because this stucks user -- he neither can proceed nor exit (deallocation of resources is usually done at program/routine exit). But what if an exception occurs in constructor so that it cannot proceed and exits with failure? We cannot just jump to the finalization section code because there is no one in the constructor. Neither destructor can be merely called on an object that is incomple/invalid.

In Delphi, an exception in constructor calls the destructor. In Java, destrucor methods are class-specific and constructor is free to clean-up anyway in case of exception. So, constructor and destructor must agree on disposing partially constructed objects. The waste-approach is widely recommended:
res1 = nil; // init to unallocated flag
res2 = nil;

try
res1 = Res1.Create();
res2 = Res2.Create();

// use resoucres

finally
if res1 <> nil then Res1.Free
if res2 <> nil then res2.Free;
end;

When we know the order of the resources allocation, the deallocation checks can be optimized. Here is how I did it in plain C:

Resourse1 r1;
Resourse2 r2;
...

// allocation check macro
#define CHECK_ALLOC(alloc_func, success_rollback, err_msg) \
if (!func_alloc) { \ // allocation failure
print(err_msg); \ //
deinit(rollback); \ // destroy the partially created object
} else \
rollback = success_rollback; // success, advance the rollback marker


void init() {
rollback = nothing; // a local variable to track the progress
CHECK_ALLOC(r1 = alloc1(), rb_r1, "allocating r1");
CHECK_ALLOC(r2 = alloc2(), rb_r2, "allocating r2");
..
}

void deinit(rollback_point) { // partial destructor
switch (rollback_point) {
case rb_rn: release(rn);
...
case rb_r2: release(r2);
case rb_r1: release(r1);
case nothing: // nothing to deallocate
}
}

void deinit() { // normal destructor
deinit(rb_rn); // start cleaning up from the last allocated resource
}


The idea is that if allocation fails, the progress is rolled back starting from the top point reached. If everything is allocated OK, the object is created and can be destroyed by deinit(). The proposed ideal constructor-destructor organization allows to share the same deallocation code for both normal workflow and errors in constructor.

The code is trivialized by exceptions in decent OOP languages that automatically check every result. This not only considerably reduces the code complexity but also ensures that no check is omitted (destructor is the same as above):

void Create() {

rollback = nothing; // define a local variable to keep building progress
try {
r1 = alloc1(); rollback = rb_r1; // allocation error throws an error
r2 = alloc1(); rollback = rb_r2;
..
} except (Exception e) { //rollback on catch
Free(rollback);
throw; // re-throw
}
}