OOP, IP, FP and Hanoi Towers

This is some attempt to illustrate the significant differences between OOP, FP
(functional programming) and PI (imperative) and prove why PI
is the preferred style of thinking when solving problems.
I will try to do all this using the example of solving the problem of Hanoi towers.
Naturally, I do not pretend to be called an experienced OO, F or I
programmer, but still I have some skills, and I will try to
apply them to this task, but the course of my thoughts, most likely, is possible and, more
Moreover, it will be necessary to criticize, preferably constructively, in order
to achieve the truth.


First, let me remind you what the essence of the problem is. Initially given three rods: 1, 2, 3 - on
one of which is strung a turret of N circles of different radius so that a
circle of a smaller circle always lies on a circle of a larger radius. The program must make a
plan for shifting these circles from the rod to the rod so that the turret is
on another rod. At the same time, each shifting should preserve the
order of the circles - any circle can only lie on a circle of a larger
radius, or on an empty rod and only one of the
top circles on the rods can be shifted .
So, if a tower is initially given with a height of two circles lying on 1 rod,
and if you need to shift it to rod number 2, then one of the correct
sequence of
moves will be: 1 -> 3, 1 -> 2, 3 -> 2. B rules N -> M
only the numbers of the rods are used and they mean: shift the topmost
circle from rod N to rod M.
Functional approach. Considered first, as it provides a classic
'school' solution to the problem.
We need to build a function.

move N abc

A function that, according to the height of the turret, the initial rod a, the final rod b
and the additional rod c will produce a list of moves. Hmm ... Well, and from what other
functions can move be concocted? Compiling some functions from others is the essence of the
approach. We can come up with a function

movetoken ab

which transfers the circle from one rod to another, but there
will be no sense from it , because it is not clear how to call it. You need to
meditate a little and overshadow your brain with a brilliant functional concept:
we look at the first example and see, to transfer the turret, we must first
transfer its top to the auxiliary rod, move the lower circle to the
target, and then move the top of the turret to the same rod. At the same time, the
upper circles can be shifted to any rods, because everything
below them has a larger radius.
Hurrah. The problem is
solved. It remains only to understand what the function move must return and get down
to business. But here everything is simple, the FP does not give us any alternative. So for
a business. The implementation is sketchy and resembles what you can write in Haskell.

move N abc
// transfer one circle to the target turret
move 1 abc = (a, b)
// transfer the top to the rod c, transfer the big circle to the rod b,
// transfer the top from rod c to rod b
move N abc = move (N - 1) acb: (a, b): move (N - 1) cba
// well, and call something like this
print move 16 1 3 2 

Elegant, challenging.
But now an object oriented approach. First you need to select
objects. Well, with this, everything is simple: circles and rods, as well as the turret itself, because
we need a solution in the form of sending a message to some object. Something
like that.

tower.move (a, b, c)

Excellent. We have a turret, mugs and rods. And how to connect all this together
through sending messages? Hmm ... Honor the back of the head and decide that there is
no sense from the rods , from the one chip too, because it alone does not
affect anything . It remains to concentrate on the turret, scratch the pumpkin and say that the
turret, it turns out, consists of two objects: the top, which is also
a turret or missing, and a large circle at the base. Cool.
If we build the object like this, then the solution is again obvious. There is a turret asking to
jump to another rod using some auxiliary, then it
first asks to jump to the top of its auxiliary rod, then
moves its base to the target rod, and then asks to jump to
the top of this target rod. Great, now we’ll roll a couple of classes.
Everything is schematic and similar to Java. All methods are open and data is private.

class Tower {
// a - this is the rod on which the turret stands, useful for checks on
// invalid requests, e.g. move (1, 3) if the turret is at 1
// pivot. For FIG knows what request will come, one must be reliable and
// encapsulated. But there are no checks in the code.
        int N, a;
        Tower top;
        Tower (N, position) {
                if N> 1 {
                        top = new Tower (N - 1, a);
                }
                else {
                        top = null;
                }
                this.N = N;
                this.a = a;
        }
        List move (b, c) {// b - where to move, c - auxiliary rod
                List l;
                if top {
                        l.append (top.move (c, b));
                }
                l.append (a.toString + "->" + b.toString);
                if top {
                        l.append (top.move (b, a);
                }
                a = b; // moved to a new rod
                return l;
        }
}
// launch
System.out.print ((new Tower (N, 1)). Move (2, 3) .toString);

Wow, that was cool. They have lost elegance, but we have a cool
lens that can check errors for itself, is encapsulated, and
in general all that kind of person is pretty. The supposedly imperative approach will
merge even more elegance and the lenses will not give pretty ones, therefore, well,
it’s in the fig, in theory. But we, gritting our teeth and break through it.
So, what do we have in an imperative approach? Nothing: no functions, no objects.
Only the states of a certain region of memory and a description of the changes in these
states. In the state we can have lists of circles on each of the disks.
Hmm ... Not very optimistic. Well, lists and lists, but what to do with them? Hmm ...
Lists. Eureka, we still have a list of moves, some, but which?
For example, we have a list of moves for moving a turret two circles in height from the
first rod to the third through the second: 1 -> 2, 1 -> 3, 3 -> 2.
Excellent. What can be done with it? Well, for example, replace the column numbers.
For example, like this: 1 = 1, 2 = 3, 3 = 2. And get a program to transfer our
economy in two circles to the second core: 1 -> 3, 1 -> 2, 3 -> 2. Do you feel
what I mean?
If now we have a program for transferring a two-level economy to the second
column, then we can now put the third largest pancake on the third one, and
then, using the already known program for transferring a 2-economy, now with
the first rod to the second through the third, making a substitution in it:
1 = 2, 3 = 1, 2 = 3, we get a transfer program from the second rod to the
third through the first. And in the end, we will become the owners of a wonderful program to
transfer the 3-economy from the first rod to the third through the second. Etc.

It remains only to understand how to start such a development of the program. But
this is obvious: if the turret is of odd height, then the first move should be made
on the target rod, otherwise on the auxiliary one. The solution is written
in something similar to iscript.

nextblock (cmdnew, cmdold, f) {
        a = f [0]; // the current program is a permutation from a to b through c
        b = f [1]; // N top circles
        c = f [2];
        // move the (N + 1) circle from a to c
        listappend (cmdnew, {.from = a; .to = b;});
        f [0] = b; // generate a permutation from b to c through a
        f [1] = c;
        f [2] = a;
        i = cmdold.head; on i; i = i.next {
                listappend (cmdnew, {.from = f [i.from]; .to = f [i.to];});
        }
        f [0] = a; // now we have a permutation from a to c through b
        f [1] = c; // (N + 1) -farm
        f [2] = b;
}
solve (N, a, b, c) {
        f [0] = a;
        if N% 2 {
                f [1] = b;
                f [2] = c; 
        }
        or {
                f [1] = c;
                f [2] = b;
        }
        on N; N = N - 1 {
                nextblock (fl, sl, f);
                i = fl.head; on i; i = i.next {
                        print ("% 0 ->% 0 \ n", i.from, i.to);
                } 
                listmove (sl, fl); // move everything from the first list to the second
        }
}
solve (16, 2, 0, 1);

Hm. It will be longer than the option of FP or OOP. But let's compare this code and those
two options, and they can be considered similar to each other. Attention can be
paid to a couple of features.
Firstly, the program generation starts immediately, you do not have to wait a long
time until the recursion, which can be quite
long, ends , the complexity of the task in the moves grows exponentially. Meanwhile, well-known
moves can be sent for further parallel processing, for example, a
program for visualizing this very Hanoi game.
Secondly, the imperative code is able to work with an endless pyramid.
He generally doesn’t really need N, unless in order to determine the first
move.
Two recursive constructions cannot do this. Hmm ... A slight philosophical
digression: perhaps this is not within the power of a recursive construction just because of the
uncertainty with the first move. Recursion must always be defined. But
this is a remark for future analysis.
As a result, I personally (I emphasize: I personally do
not pretend to truth in the last resort ), the above reasoning leads to the next look at
programming approaches.
Programs should be considered precisely as dynamic systems, that is,
systems described by state changes.
When we start trying to
formulate functionality in the form of static mappings, as in
functional programming, we are forced to limit ourselves
1. in dynamics, since the value of the function must be calculated before we
can use it
2. in efficiency and distribution: if the calculated value
can potentially be used before its full calculation is completed, then in As part of the
classical FP, we have no way to do this.
Of course, solutions to these problems have been found: in ML there is the ability to write
imperative programs, in Haskell there are monads that
match the dynamics of imperative calculations with endless lists of values ​​that are the
trajectories of this dynamics - not the most convenient solution, imho.
When we try to look at programs as interacting through
special interfaces, objects, then we again lose dynamism. Because
objects in our intuitive representation correspond to processes that are
not at all, not to dynamic structures at all. In this example, in a natural
way (in my opinion, of course, but supported by many textbooks on
OOP, in which similar tasks, about 8 phrases, for example, are solved exactly this way),
an object was chosen: a turret. And we see what this abstraction leads to - the
immediate construction of a recursive algorithm, with all the ensuing
drawbacks.
Well, of course, in the case of implicit OOP, data generation for the visualizer
You can start immediately, as recursion reaches the first bottom, but it can
reach it for a very long time. In the framework of the FI, this can also be done, but somewhat more
confusing. In addition, we must not forget that we will not
be able to solve the problem with an infinite turret in the system of objects so chosen.
Due to the fact that OOP and FI limit the programmer in the ability to
see the dynamics in the task, I personally never use them in the design.
I focus on how the data should flow in the program and how it should
change, and this leads, in my opinion, to more beautiful and simple
solutions. Because the world is dynamic, because such design is much
closer to physical reality than objects or functions, because there are no
objects or functions in nature. There are only dynamic systems, as
modern physics is trying to prove to us. So why limit your mind to
focus on static models of reality, which are FP and
OOP? FP by its mathematical nature, and OOP for the reason that in a
modern form fixes consciousness on analogies with passive
material objects.
In fairness, it should be noted that in our example, the object could just
select a chain of moves, and build a
program similar to the imperative solution , BUT the OO programmer begins with a search for obvious objects, and not with
analysis of dynamics, which limits its design capabilities,
and this often leads to solutions more similar in
structure to FP. Within the framework of the FP approach, this could also potentially be
done, but much more difficult, and the infinite tower could
only be calculated in functional languages ​​with completely lazy execution; within the framework of the
lamda abstraction itself, such a calculation would be non-computable. Which again, by the way,
proves that a computer is much more than a Turing machine.
In addition, programming languages
that call themselves OO are also prone to such design . Objects in them are not
dynamic entities exchanging messages, as it was conceived back in
Smalltalk, namely static
abstract data types, no more. A dynamic object that lives its own
life is rather difficult to create. This is opposed even in distributed
technologies, the same CROBA, in
which objects come to life only upon request, and just the very possible
implementation method : launching a separate thread, and accessing shared data with the interface
using synchronization. This is already creating a full-fledged client-server
application. But OOP again inclines to create it not as a process,
but as a set of objects, which again turn out to be dead and non-dynamic
in nature. Between them it’s difficult to organize a real data stream, their
It’s difficult to run in parallel, because for this they need to be done by
servers again .
Meanwhile, some languages, which began as purely functional solutions,
eventually developed to provide the ability to create just such entities
- processes that exchange messages. Erlang and O'Caml, for example, but this
possibility is based on the imperative functionality of these
languages: monads or an explicit ability to store states. With a pure,
imperative structural approach, there are no problems at all:
Limbo, Ada, or something like IPC on UNIX.
Actually, the appeal is based on this (not only mine, by the way:
http://www.lysator.liu.se/c/pikestyle.html) abandon OOP and FI wherever
possible, and focus on analyzing data changes in
programs, on state properties, and on the logic of changes.
Another
retreat: modern physics considers it existent, and it is intuitively
clear that it preserves properties in the process of changes, without focusing on the
analysis of the dynamics in the program, it is impossible to accurately identify the stored properties, and
therefore objects. Such an analysis leads to more flexible solutions, and to more effective ones.
Interfaces, functions, modules, classes will arise naturally in the process
of program implementation. And they can be reused.