OOP, IP, FP and Towers of Hanoi
This is some attempt to illustrate the significant differences between OOP, OP
(functional programming) and PI (imperative) and prove why PI
is the preferred style of thinking when solving problems.
I'll try to do all this using the example of solving the problem of the Hanoi towers.
Naturally, I do not pretend to be called an experienced OO, F, or AND
a programmer, but I still have some skills, and I will try them
apply to this problem, but the course of my thinking is most likely possible and, more
In addition, it will be necessary to criticize, constructively, in order
reach the truth.
First, let me remind you of the essence of the problem. Initially, three rods are given: 1, 2, 3 - on
one of which is a turret strung out of N circles of different radii so that the circle
a larger radius always has a smaller circle. The program should make
the plan of shifting these circles from the rod to the rod so that the turret
turned on another rod. In this case, each shift must save
ordering of circles - any circle can lie only on a larger circle
radius, or on an empty rod and you can only shift one of the most
upper circles on rods.
So, if a turret with a height of two circles, which lies on 1 rod, was originally given,
and if it needs to be shifted to rod number 2, then one of the correct
sequences
moves will be: 1 -> 3, 1 -> 2, 3 -> 2. In the rules N -> M
only the numbers of the rods are used and they mean: to shift the uppermost
circle from rod N to rod M.
Functional approach. Considered first because it gives the classic
'school' problem solving.
We need to build a function.
The function, which is the height of the turret, the initial rod a, the final rod b
and an extra bar c will display a list of moves. Hmm ... Well, from what other
functions can concoct move? Compilation of some functions from others - the essence
approach. We can come up with a function
')
which transfers a circle from one rod to another, but there is no sense from it
will not, because it is not clear how to call it. Need a little
pomedetirovat and overshadow your brain with a brilliant functional concept:
We look at the first example and see, in order to transfer the turret, we must first
transfer its top to the auxiliary rod, move the lower circle to
target, and then on the same rod to move the top of the turret. Wherein
the upper circles can be shifted to any rods, because all that
below them has a larger radius.
Hooray. Task
solved. It remains only to understand what the move function must return and take
for the cause. But everything is simple, it does not give us any alternative to the OP list. So for
a business. The implementation is schematic and resembles what you can write in Haskell.
Elegant, difficult to challenge.
But now the object-oriented approach. First you need to select
objects. Well, this 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. Anything
like.
Fine. We have turrets, cups and rods. And how to tie it all together
through the sending of messages? Hmm ... We will honor the back of the head and decide that from the rods in general
There is no sense, from one chip, too, because it is not for nothing
affects. It remains to focus on the turret, scratch the pumpkin and say that
the turret, it turns out, consists of two objects: the top, which also
is a turret or missing, and a large circle at the bottom. Cool.
If we construct the object in this way, then the solution is again obvious. Have a turret ask
jump over to another rod using some auxiliary then she
first asks to jump over its top to the auxiliary rod, then
moves its base on the target rod and then asks to jump on
this target rod is its tip. Great, now let's roll a couple of classes.
Everything is schematic and similar to Java. All methods are open and data is closed.
Wow, that was awesome. In elegance lost, but we have a cool
an object that can check for errors is encapsulated and
In general, all such a likable. Presumably imperative approach
merge even more elegance and lenses will not give cute, so, well,
its in figs, in theory. But we, reluctantly and break through his teeth.
So, what do we have in the imperative approach? Nothing: no functions, no objects.
Is it only the state of a certain area of ​​memory and a description of the changes of these
states. In the state, we may have lists of circles on each of the disks.
Hmm ... Not very optimistic. Well lists and lists, and what to do with them? Hmm ...
Lists. Eureka, we still have a list of moves, some, but which ones?
For example, we have a list of moves for transferring a turret two circles high with
the first rod to the third through the second: 1 -> 2, 1 -> 3, 3 -> 2.
Fine. What can you do with it? Well, for example, replace the number plates.
For example: 1 = 1, 2 = 3, 3 = 2. And get a program for transferring our
households in two circles on the second rod: 1 -> 3, 1 -> 2, 3 -> 2. Feel to
What am I getting at?
If now we have a program for transferring a two-level farm to the second
column, then on the third we can now put the third largest pancake, and
then, using the already well-known program for transferring 2-households, tper already with
the first rod to the second through the third, making a substitution in it:
1 = 2, 3 = 1, 2 = 3, we get the 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 for
transferring the 3-farm from the first rod to the third through the second. And so on.
It remains only to understand from which move to start such a program development. But
this is obvious: if the turret is of odd height, then the first move must be made
on the target rod, otherwise on the auxiliary. Solution is written
on something like iscript.
Hm It will be longer than the option OP or OOP. But let's compare this code and those
two options, and they can be considered similar to each other. Attention can
draw on a couple of features.
First, program generation starts immediately, no need to wait long
time until the recursion is over, which may be enough
long, the complexity of the problem in moves grows exponentially. Meanwhile famous
moves can be sent for further parallel processing, for example,
A program to visualize this very Hanoi game.
Secondly, the imperative code is able to work with an infinite down pyramid.
He doesn’t really need N at all, except to determine the first
move
Two recursive constructions can not do this. Hmm ... A little philosophical
digression: perhaps this is beyond the power of recursive construction just because
uncertainty with the first move. Recursion must always be defined. But
This is a note for future analysis.
In the end, I personally (I emphasize: I personally, the ultimate truth
I do not pretend) the above reasoning inclines to the next look at
approaches to programming.
Programs need to be considered exactly as dynamic systems, that is,
systems described by state changes.
When we start trying
formulate the functionality in the form of static mappings, as in
functional programming, we are forced to limit ourselves
1. dynamically, since the value of a function must be calculated before we
we can use it
2. in efficiency and distribution: if the calculated value is potentially
can be used before its full calculation, then within
We do not have the ability to do classic OP.
Of course, solutions to these problems were found: in ML you can write
imperative programs, in Haskell there are monads that imperative dynamics
The calculations assign to each other infinite lists of values ​​that are
The trajectories of this dynamic are not the most convenient solution, imho.
When we try to look at programs as interacting through
special interfaces, objects, we again lose our dynamism. Because
the objects in our intuitive view correspond at all to the processes
not at all dynamic structures. In this example, the natural
way (in my opinion, of course, but supported by many textbooks on
OOP, in which similar tasks, about 8 frèzes, for example, are exactly how they are solved),
object was selected: turret. And we see what this abstraction leads to -
immediate construction of a recursive algorithm, with all the consequences
disadvantages.
Well, of course, in the case of an implicit OOP, data generation for the visualizer
you can start right away as the recursion reaches the first bottom, but it can
reach it very long. As part of the OP, this can also be done, but several
confusing. In addition, we must not forget that we do not
we can solve the problem with the infinite tower in the chosen system of objects.
It is precisely because OOP and FP limit the programmer’s ability to
see the dynamics in the task, personally I 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 design is much
closer to physical reality than objects or functions because there is no
objects or functions in nature. There are only dynamic systems, like trying
prove to us modern physics. So why limit your mind
focus on static models of reality, which are the FP and
OOP? OP by its mathematical nature, and OOP for the reason that in
modern form captures the mind on analogies with passive
material objects.
In fairness it should be noted that in our example the object could be
choose just a chain of moves, and build a similar imperative solution
the program, BUT OO, the programmer begins with a search for obvious objects, and not with
analysis of the dynamics, which limits its design capabilities,
and this often leads him to decisions that are more similar in their
structure on the OP. Within the framework of the OP approach, this could also potentially be
but much more difficult to do, and it would be possible to cheat the endless turret
only in functional languages ​​with completely lazy execution, within the framework of
the same lamda-abstraction, such a calculation will be non-computable. What again, by the way,
It proves that a computer is much more than a Turing machine.
In addition, programming languages ​​incline to such design,
who call themselves OO. In them, objects are not
dynamic messaging entities as it was intended back in
Smalltalk, namely static
abstract data types, no more. A dynamic object that lives its own
life is quite difficult to create. It resists even in distributed
technologies, the same croba, in
which objects come to life only upon request, and just the very possible way
implementations: launching a separate thread, and accessing shared data with an interface
using synchronization. This is the creation of a full-fledged client-server.
applications coming out. But the PLO, again, is inclined to create it not in the form of a process,
but in the form of a set of objects, which again turn out to be dead and non-dynamic
at its core. It is difficult to organize a real data flow between them, their
difficult to run in parallel, because for this they need to be done again
servers.
Meanwhile, some languages, which began as purely functional solutions, in
eventually evolved to provide the ability to create just such entities
- processes exchanging messages. Erlang and O'Caml, an example, but this
the opportunity is based on the close to the imperative functionality of these
Languages: on monads or the explicit ability to store states. When clean
imperative structural approach with this in general no problems:
Limbo, Ada or something like IPC on UNIX.
Actually the call is based on this (not only mine, by the way:
http://www.lysator.liu.se/c/pikestyle.html ) refuse OOP and OP wherever
Only this is possible, and focus on analyzing data changes in
programs, on properties of states and on the logic of changes.
The next
retreat: modern physics considers existing, yes it is intuitive
it is clear that it preserves the properties in the process of change, without focusing on
analysis of the dynamics in the program can not accurately identify the saved properties, and
hence the objects. Such an analysis leads to more flexible solutions, and to more effective ones.
Interfaces, functions, modules, classes will arise naturally in the process.
implementation of the program. And they can be reused.
(functional programming) and PI (imperative) and prove why PI
is the preferred style of thinking when solving problems.
I'll try to do all this using the example of solving the problem of the Hanoi towers.
Naturally, I do not pretend to be called an experienced OO, F, or AND
a programmer, but I still have some skills, and I will try them
apply to this problem, but the course of my thinking is most likely possible and, more
In addition, it will be necessary to criticize, constructively, in order
reach the truth.
First, let me remind you of the essence of the problem. Initially, three rods are given: 1, 2, 3 - on
one of which is a turret strung out of N circles of different radii so that the circle
a larger radius always has a smaller circle. The program should make
the plan of shifting these circles from the rod to the rod so that the turret
turned on another rod. In this case, each shift must save
ordering of circles - any circle can lie only on a larger circle
radius, or on an empty rod and you can only shift one of the most
upper circles on rods.
So, if a turret with a height of two circles, which lies on 1 rod, was originally given,
and if it needs to be shifted to rod number 2, then one of the correct
sequences
moves will be: 1 -> 3, 1 -> 2, 3 -> 2. In the rules N -> M
only the numbers of the rods are used and they mean: to shift the uppermost
circle from rod N to rod M.
Functional approach. Considered first because it gives the classic
'school' problem solving.
We need to build a function.
move N abc
The function, which is the height of the turret, the initial rod a, the final rod b
and an extra bar c will display a list of moves. Hmm ... Well, from what other
functions can concoct move? Compilation of some functions from others - the essence
approach. We can come up with a function
')
movetoken ab
which transfers a circle from one rod to another, but there is no sense from it
will not, because it is not clear how to call it. Need a little
pomedetirovat and overshadow your brain with a brilliant functional concept:
We look at the first example and see, in order to transfer the turret, we must first
transfer its top to the auxiliary rod, move the lower circle to
target, and then on the same rod to move the top of the turret. Wherein
the upper circles can be shifted to any rods, because all that
below them has a larger radius.
Hooray. Task
solved. It remains only to understand what the move function must return and take
for the cause. But everything is simple, it does not give us any alternative to the OP list. So for
a business. The implementation is schematic and resembles what you can write in Haskell.
move N abc // transfer one circle to the target turret move 1 abc = (a, b) // transfer of the top to the rod c, transfer of a large circle to the rod b, // transfer the top from the rod c to the rod b move N abc = move (N - 1) acb: (a, b): move (N - 1) cba // well, we call something like this print move 16 1 3 2
Elegant, difficult to challenge.
But now the object-oriented approach. First you need to select
objects. Well, this 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. Anything
like.
tower.move (a, b, c)
Fine. We have turrets, cups and rods. And how to tie it all together
through the sending of messages? Hmm ... We will honor the back of the head and decide that from the rods in general
There is no sense, from one chip, too, because it is not for nothing
affects. It remains to focus on the turret, scratch the pumpkin and say that
the turret, it turns out, consists of two objects: the top, which also
is a turret or missing, and a large circle at the bottom. Cool.
If we construct the object in this way, then the solution is again obvious. Have a turret ask
jump over to another rod using some auxiliary then she
first asks to jump over its top to the auxiliary rod, then
moves its base on the target rod and then asks to jump on
this target rod is its tip. Great, now let's roll a couple of classes.
Everything is schematic and similar to Java. All methods are open and data is closed.
class Tower {
// a is the pivot on which the turret stands, useful for checks on
// invalid requests, for example move (1, 3), if the turret is at 1
// rod. For FIG know what kind of request will come, you 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 bar
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 awesome. In elegance lost, but we have a cool
an object that can check for errors is encapsulated and
In general, all such a likable. Presumably imperative approach
merge even more elegance and lenses will not give cute, so, well,
its in figs, in theory. But we, reluctantly and break through his teeth.
So, what do we have in the imperative approach? Nothing: no functions, no objects.
Is it only the state of a certain area of ​​memory and a description of the changes of these
states. In the state, we may have lists of circles on each of the disks.
Hmm ... Not very optimistic. Well lists and lists, and what to do with them? Hmm ...
Lists. Eureka, we still have a list of moves, some, but which ones?
For example, we have a list of moves for transferring a turret two circles high with
the first rod to the third through the second: 1 -> 2, 1 -> 3, 3 -> 2.
Fine. What can you do with it? Well, for example, replace the number plates.
For example: 1 = 1, 2 = 3, 3 = 2. And get a program for transferring our
households in two circles on the second rod: 1 -> 3, 1 -> 2, 3 -> 2. Feel to
What am I getting at?
If now we have a program for transferring a two-level farm to the second
column, then on the third we can now put the third largest pancake, and
then, using the already well-known program for transferring 2-households, tper already with
the first rod to the second through the third, making a substitution in it:
1 = 2, 3 = 1, 2 = 3, we get the 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 for
transferring the 3-farm from the first rod to the third through the second. And so on.
It remains only to understand from which move to start such a program development. But
this is obvious: if the turret is of odd height, then the first move must be made
on the target rod, otherwise on the auxiliary. Solution is written
on something like iscript.
nextblock (cmdnew, cmdold, f) {
a = f [0]; // current program is a permutation from a to b through c
b = f [1]; // N top circles
c = f [2];
// move (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 with a to c through b
f [1] = c; // (N + 1) households
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 OP or OOP. But let's compare this code and those
two options, and they can be considered similar to each other. Attention can
draw on a couple of features.
First, program generation starts immediately, no need to wait long
time until the recursion is over, which may be enough
long, the complexity of the problem in moves grows exponentially. Meanwhile famous
moves can be sent for further parallel processing, for example,
A program to visualize this very Hanoi game.
Secondly, the imperative code is able to work with an infinite down pyramid.
He doesn’t really need N at all, except to determine the first
move
Two recursive constructions can not do this. Hmm ... A little philosophical
digression: perhaps this is beyond the power of recursive construction just because
uncertainty with the first move. Recursion must always be defined. But
This is a note for future analysis.
In the end, I personally (I emphasize: I personally, the ultimate truth
I do not pretend) the above reasoning inclines to the next look at
approaches to programming.
Programs need to be considered exactly as dynamic systems, that is,
systems described by state changes.
When we start trying
formulate the functionality in the form of static mappings, as in
functional programming, we are forced to limit ourselves
1. dynamically, since the value of a function must be calculated before we
we can use it
2. in efficiency and distribution: if the calculated value is potentially
can be used before its full calculation, then within
We do not have the ability to do classic OP.
Of course, solutions to these problems were found: in ML you can write
imperative programs, in Haskell there are monads that imperative dynamics
The calculations assign to each other infinite lists of values ​​that are
The trajectories of this dynamic are not the most convenient solution, imho.
When we try to look at programs as interacting through
special interfaces, objects, we again lose our dynamism. Because
the objects in our intuitive view correspond at all to the processes
not at all dynamic structures. In this example, the natural
way (in my opinion, of course, but supported by many textbooks on
OOP, in which similar tasks, about 8 frèzes, for example, are exactly how they are solved),
object was selected: turret. And we see what this abstraction leads to -
immediate construction of a recursive algorithm, with all the consequences
disadvantages.
Well, of course, in the case of an implicit OOP, data generation for the visualizer
you can start right away as the recursion reaches the first bottom, but it can
reach it very long. As part of the OP, this can also be done, but several
confusing. In addition, we must not forget that we do not
we can solve the problem with the infinite tower in the chosen system of objects.
It is precisely because OOP and FP limit the programmer’s ability to
see the dynamics in the task, personally I 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 design is much
closer to physical reality than objects or functions because there is no
objects or functions in nature. There are only dynamic systems, like trying
prove to us modern physics. So why limit your mind
focus on static models of reality, which are the FP and
OOP? OP by its mathematical nature, and OOP for the reason that in
modern form captures the mind on analogies with passive
material objects.
In fairness it should be noted that in our example the object could be
choose just a chain of moves, and build a similar imperative solution
the program, BUT OO, the programmer begins with a search for obvious objects, and not with
analysis of the dynamics, which limits its design capabilities,
and this often leads him to decisions that are more similar in their
structure on the OP. Within the framework of the OP approach, this could also potentially be
but much more difficult to do, and it would be possible to cheat the endless turret
only in functional languages ​​with completely lazy execution, within the framework of
the same lamda-abstraction, such a calculation will be non-computable. What again, by the way,
It proves that a computer is much more than a Turing machine.
In addition, programming languages ​​incline to such design,
who call themselves OO. In them, objects are not
dynamic messaging entities as it was intended back in
Smalltalk, namely static
abstract data types, no more. A dynamic object that lives its own
life is quite difficult to create. It resists even in distributed
technologies, the same croba, in
which objects come to life only upon request, and just the very possible way
implementations: launching a separate thread, and accessing shared data with an interface
using synchronization. This is the creation of a full-fledged client-server.
applications coming out. But the PLO, again, is inclined to create it not in the form of a process,
but in the form of a set of objects, which again turn out to be dead and non-dynamic
at its core. It is difficult to organize a real data flow between them, their
difficult to run in parallel, because for this they need to be done again
servers.
Meanwhile, some languages, which began as purely functional solutions, in
eventually evolved to provide the ability to create just such entities
- processes exchanging messages. Erlang and O'Caml, an example, but this
the opportunity is based on the close to the imperative functionality of these
Languages: on monads or the explicit ability to store states. When clean
imperative structural approach with this in general no problems:
Limbo, Ada or something like IPC on UNIX.
Actually the call is based on this (not only mine, by the way:
http://www.lysator.liu.se/c/pikestyle.html ) refuse OOP and OP wherever
Only this is possible, and focus on analyzing data changes in
programs, on properties of states and on the logic of changes.
The next
retreat: modern physics considers existing, yes it is intuitive
it is clear that it preserves the properties in the process of change, without focusing on
analysis of the dynamics in the program can not accurately identify the saved properties, and
hence the objects. Such an analysis leads to more flexible solutions, and to more effective ones.
Interfaces, functions, modules, classes will arise naturally in the process.
implementation of the program. And they can be reused.
Source: https://habr.com/ru/post/9390/
All Articles