How to represent an algorithm as a class?

I am trying to understand how to design classes which take an input, do some processing, and return a result. More specifically, should the object store the intermediate results between function calls as state, or should all methods be static, and pass params around.

Example: I am currently working on a class which detects, and removes headers & footer from pages in a document. The algorithm steps are outlined below:

HeaderFooterFilter

removeHeaderFooterText(pages) ->
  candidates = getBoundaryBlocks(pages);
  toRemove = detectRepeatingBlocks(candidates);
  removeBlocks(toRemove);

So my question is, should pages, candidates, toRemove be members of the class, or should the methods be static and pass them around?

Is there a design-pattern which deals with algorithm classes?

Before discussion, notice that

When given a business use case, object-oriented programmers can usually arrive at some consensus about how the surface design (the partitioning of responsibilities between classes, and the publicly accessible methods and properties of these classes) should look like.

On the other hand, when given an algorithm,

Object-oriented programmers can still arrive at some consensus about the surface design, based on the inputs, steps (process), and outputs.
There is much less consensus about how the algorithm’s internals shall be partitioned, because those belongs to implementation detail which the algorithm’s user would not be concerned about.
Object-oriented design does not prescribe ways to design algorithms. The algorithm’s basic framework should be decided first, and then an object-oriented design (encapsulation) can be produced.
If the algorithm’s basic framework needs to be changed, for example, to exploit a faster algorithm that has a requirement for a different framework, most of that object-oriented design would have to be re-done.
Object-oriented algorithm design is an entirely different topic, with an emphasis on fundamental (functional) building blocks that are reusable across many different types of algorithms. A consequence is that there is higher code reusability. The drawback is that it would have required the designers to adopt a different approach to algorithms, which is not typically taught in schools.

As far as object-oriented design is concerned, the breakdown of an algorithm into steps depends on whether the algorithm itself is better seen, from its user’s point of view, as being executed in one single step, or as multiple steps.

Keep in mind that the algorithm’s user doesn’t need to know how the steps are decomposed, unless the user has a need to intervene between the steps, such as:

Interrupt the algorithm in between two steps,
Inspect the algorithm’s data in between two steps,
Alter the algorithm’s settings in between two steps,
etc.

If the algorithm is better seen as a single step, the object-oriented implementation can choose to hide all of the implementation details, leaving only the “inputs, process, outputs” visible to the user. Furthermore, one can provide a factory method or a utility function that takes the input and computes the output. This factory or utility method can make use of the object-oriented implementation.

In general it is better to store the algorithm states (mutable data) in the object itself, and make them private. There are exceptions:

Not if doing so increases confusion. For example, if pages means one thing in some parts of the algorithm, and then pages is rewritten with something different in other parts of the algorithm. If this is the case,
- They should be given different and descriptive names to avoid confusion.
- If the pages has its own state transitions (like a state machine), that logic should be extracted into its own class.

Class design for algorithms that are parallelized

If it is being used by its users concurrently (being called from multiple threads), the algorithm needs to either freeze (its data becomes immutable after the main computation has finished), or it needs lock-based protection.

If the algorithm itself is parallelized,

Mutable states should be partitioned, and each worker should have exclusive access to its piece of mutable state.
The algorithm’s execution should be partitioned into phases. Once a phase has completed, the phase’s output data becomes frozen.

There is nothing wrong with writing pure functions as statics in object oriented programming. Given your example, it does not appear necessary to make instance fields out of the intermediate results.

However, you should be prepared to refactor when and if necessary, into a real object. Several reasons you may need to do that are:

You choose to define the algorithm via an interface (or abstract base
class) so you can have
different implementations. Then you need multiple classes for the
varied implementations, and you will need an object to hold the
state, which in this case the state is the choice among the algorithms.
You realize that you need more than one operation (function) on the
object and it must persist state in between these invocations.

I am trying to understand how to design classes which take an input, do some processing, and return a result.

There is a principle in object orientated design called “Tell, don’t ask”

What this generally means is you tell an object to change itself, you don’t ask an object for data that you then manipulate some where else.

So when thinking about how to manage something like this in OO design you need to keep coming back to your objects and what they themselves do. In general you don’t have an object that takes input from another objects, because you make the objects themselves do the work.

So taking your example there are a number of immediate design issues that spring up. You are passing a collection of pages into an unnamed object that will then process them. It is probably better to let the pages themselves handle this.

So instead of

removeHeaderFooterText(pages)

try instead

pages.each |page|
    page.removeHeaderFooterText

Nothing then outside of the page object itself has to know how the heck to remove header and footer text from the page.

You have the steps to achieve this as

getBoundaryBlocks
detectRepeatingBlocks
removeBlocks

Straight away a a noun jumps out, “Boundary Blocks”. A page has boundary blocks, so there shouldn’t be something outside of the Page object concerned with getting boundary blocks out of the page

class Page
    def removeHeaderFooterText
        page_blocks.each |block|
            if block.repeating_block?
               page_blocks.delete(block)

See you have an object in there of a block, which itself knows how to determine if it is a repeating block or not. If it is the page removes it. The page doesn’t care how the block determines if it is a repeating block or not.

This is just a quick example. To be honest I’m not up on my document layout terminology so this might not quite match what you are trying to do.

tl;dr version

The point is that in object orientated design an “algorithm” will not be represented as a single list of procedural operations to carry out.

It will instead be a set of interactions between objects. As Adele Goldberg said about Smalltalk, one of the earliest object orientated languages, “In Smalltalk, everything happens some where else”

You will (should) never have a list of algorithmic procedural instructions to carry out an algorithm. You will instead of a number of interacting objects, each with a small unit of behaviours, that working together will produce the outcome of the algorithm. Every object is a self contained unit of behaviour and the system achieves its goals by each of these units telling other units to do something.

The issue of course with this is it requires a very different way of thinking about problems and algorithms, which is why often claims of object orientated design fall back on procedural design.

If removeHeaderFooterText is an atomic operation, then the solution is simple. Your class for implementing the algorithm will have one public entry point. In pseudo code, it would look something like this:

class HeaderFooterFilter
{
    public removeHeaderFooterText(pages);
};

No caller should ever be concerned with how removeHeaderFooterText works. All they need to know is what it does. Internally, you can do whatever you want. You can completely replace the internals someday if you want. As long as your entry point remains the same, callers don’t have to change anything.

As an implementation detail, this can be done as a static. I tend to avoid static in these situations, because it is a little simpler handling concurrency.

Filed under: softwareengineering - @ 02:35

Thẻ: language-agnostic, object-oriented

Thiết kế website giá rẻ

Danh mục

How to represent an algorithm as a class?