Pull to refresh

OOP, IP, FP и Ханойские башни

Reading time9 min
Views1.7K
Это некоторая попытка проиллюстрировать значительные отличия между ООП, ФП
(функциональное программированием) и ИП (императивным) и доказать, почему ИП
является предпочтительным стилем размышлений при решении задач.
Всё это попробую сделать на примере решения задачи о ханойских башнях.
Естественно, я не претендую на то, чтобы называться опытным ОО, Ф или И
программистом, но всё же кое-какие у меня навыки есть, и я попробую их
применить к этой задаче, но ход моих размышлений, скорее всего, можно и, более
того, нужно, будет подвергнуть критике, желателько конструктивной, дабы
достичь истины.


Сначала напомню в чём суть задачи. Изначально даны три стержня: 1, 2, 3 — на
один из которых нанизана башенка из N кругов разного радиуса так, что на круге
большего радиуса всегда лежит круг меньшего. Программа же должна составить
план перекладывания этих кругов со стержня на стержень так, чтобы башенка
оказалась на другом стержне. При этом, каждое перекладывание должно сохранять
упорядоченность кругов — любой круг может лежать только на круге большего
радиуса, или на пустом стержне и перекладывать можно только один из самых
верхних кругов на стержнях.
Так, если изначально дана башенка высотой в два кружка, лежащая на 1 стержне,
и если её нужно переложить на стержень номер 2, то одной из правильных
последовательностей
ходов будет: 1 -> 3, 1 -> 2, 3 -> 2. В правилах N -> M
используются только номера стержней и они обозначают: переложить самый верхний
кружок со стержня N на стержень M.
Функциональный подоход. Рассматривается первым, так как даёт классическое
'школьное' решение задачи.
Нам нужно построить функцию.

move N a b c

Функция, которая по высоте башенки, начальному стержню a, конечному стержню b
и дополнительному стержню c выдаст список ходов. Хм… Ну и из каких других
функций можно состряпать move? Составление одних функций из других — суть
подхода. Мы можем придумать функцию

movetoken a b

которая переносит кружок с одного стержня на другой, но толку от неё никакого
не будет, потому что не понятно, как её вызывать. Надо немного
помедетировать и осенить свой мозг гениальной функциональной концепцией:
смотрим на первый пример и видим, чтобы перенести башенку, мы должны сначала
перенести её верх на вспомогательный стержень, переместить нижний кружочек на
целевой, а потом на этот же стержень переместить верх башенки. При этом
верхние кружочки можно перекладывать на любые стержни, потому что всё, что
ниже них имеет больший радиус.
Ура. Задача
решена. Остаётся только понять, что должна возвращать функция move и браться
за дело. Но тут всё просто, иной альтернативы списку ФП нам не даёт. Итак, за
дело. Реализация схематична и напоминает то, что можно написать на Haskell.

move N a b c
// перенос одного кружочка на целевую башенку
move 1 a b c = (a, b)
// перенос верха на стержень c, перенос большого кружочка на стержень b,
// перенос верха со стержня c на стержень b
move N a b c = move (N - 1) a c b : (a, b) : move (N - 1) c b a

// ну, а вызываем примерно так
print move 16 1 3 2 

Элегантно, оспорить сложно.
Но теперь объектно ориентированных подход. Сперва надо выделить
объекты. Ну с этим всё просто: кружки и стержени, а так же сама башенка, ведь
нам нужно решение в виде посылки сообщения некоторому объекту. Что-нибудь
вроде.

tower.move(a, b, c)

Отлично. У нас есть башенка, кружки и стержни. И как это всё связать воедино
через посылку сообщений? Хм… Почещем затылок и решим, что от стержней вообще
никакого толку нет, от одной фишки тоже, потому что она одна ни на что не
влияет. Остаётся сосредоточиться на башенке, почесать тыковку и сказать, что
башенка-то, оказывается состоит из двух объектов: верхушки, которая тоже
является башенкой или отсутствует, и большого кружка в основании. Классно.
Если мы так построим объект, то решение опять же очевидно. Есть башенку просят
перепрыгнуть на другой стержень, используя некоторый вспомогательный, то она
сначала просит перепрыгнуть на вспомогательный стержень свою верхушку, затем
двигает своё основание на целевой стержень, а затем просит перепрыгнуть на
этот целевой стержень свою верхушку. Отлично, сейчас накатаем пару классов.
Всё схематично и похоже на Java. Все методы открыты, а данные закрыты.

class Tower {
//      a - это стержень, на котором башенка стоит, полезно для проверок на
//      неверные запросы, например move(1, 3), если башенка стоит на 1
//      стержне. Ибо фиг знает, какой запрос придёт, надо быть надёжными и
//      инкапсулированными. Но проверок в коде нет.
        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 - куда передвинуть, c - вспомогательный стержень
                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; // переехали на новый стержень

                return l;
        }
}

// запуск
System.out.print((new Tower(N, 1)).move(2, 3).toString);

Ух, это было круто. В элегантности утратили, зато у нас есть классный
объектик, который может проверять себе ошибки, является инкапсулированным и
вообще всем таким из себя симпатичным. Предположительно императивный подход
сольёт ещё больше элегантности и объективков не даст симпатичных, поэтому, ну
его на фиг, по идее. Но мы, скрепя зубы и через него прорвёмся.
Так, а что у нас есть в императивном подходе? Ничего: ни функций, ни объектов.
Разве только состояния некоторой области памяти и описание изменений этих
состояний. В состоянии у нас могут быть списки кружочков на каждом из дисков.
Хм… Не очень оптимистично. Ну списки и списки, а что с ними делать? Хм…
Списки. Эврика, у нас же ещё есть список ходов, каких-то, но каких?
Например, есть у нас список ходов для переноса башенки высотой в два кружка с
первого стержня на третий через второй: 1 -> 2, 1 -> 3, 3 -> 2.
Отлично. Чего с ним можно сделать? Ну, наример, заменить номерки столбиков.
Например так: 1 = 1, 2 = 3, 3 = 2. И получить программу для переноса нашего
хозяйства в два кружочка на второй стержень: 1 -> 3, 1 -> 2, 3 -> 2. Чуете к
чему я клоню?
Если теперь у нас есть программа для переноса двухуровнего хозяйства на второй
столбик, то на третьий мы теперь можем положить третий по величине блин, а
потом, используя уже известную программу по переносу 2-хозяйства, тперь уже с
первого стержня на второй через третий, сделав в ней подстановку:
1 = 2, 3 = 1, 2 = 3, мы получим программу переноса со второго стержня на
третий через первый. И в итоге станем обладателями чудесной программы по
переносу 3-хозяйства с первого стержня на третий через второй. И так далее.

Остаётся только понять, с какого хода начать такую вот развёртку программы. Но
это очевидно: если башенка нечётной высоты, то первый ход должен быть сделан
на целевой стержень, в противном случае на вспомогательный. Решение написано
на чём-то похожем на iscript.

nextblock(cmdnew, cmdold, f) {
        a = f[0]; // текущая программа - это перестановка с a на b через c
        b = f[1]; // N верхних кружков
        c = f[2];

        // передвигаем (N + 1) кружочек с a на c
        listappend(cmdnew, { .from = a; .to = b; });

        f[0] = b; // сгенерируем перестановку с b на c через 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; // теперь у нас перестановка с a на c через b
        f[1] = c; // (N + 1)-хозяйства
        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); // перенести всё из первого списка во второй
        }
}

solve(16, 2, 0, 1);

Хм. Подлиннее будет, чем вариант ФП или ООП. Но давайте сравним этот код и те
два варианта, а их можно считатать похожими друг на друга. Внимание можно
обратить на пару особенностей.
Во-первых, генерация программы начинается немедленно, не нужно ждать долгое
время до тех пор, пока закончится рекурсия, которая может быть достаточно
долгой, сложность задачи в ходах растёт экспоненциально. Между тем известные
ходы можно отправлять на дальнейшую параллельную обработку, например,
программе по визуализации этой самой ханойской игры.
Во-вторых, императивный код способен работать с бесконечной вниз пирамидой.
Ему вообще N не особо нужно, разве только для того, чтобы определить первый
ход.
Двум рекурсивным построениям такое не под силу. Хм… Небольшое философское
отступление: возможно это не под силу рекурсивному построению как раз из-за
неопределённости с первым ходом. Рекурсия всегда должна быть определённой. Но
это так, замечание для будущего анализа.
В итоге, лично меня (подчёркиваю: лично меня, на истинность в последней инстанции
не претендую) приведённые рассуждения склоняют к следующему взгляду на
подходы к программированию.
Программы нужно рассматривать именно как динамические системы, то есть,
системы, описываемые изменениями состояний.
Когда мы начинаем пытаться
сформулировать функциональность в виде статичных отображений, как в
функциональном программировании, мы вынужденно ограничиваем себя
1. в динамике, так как значение функции должно быть вычислено прежде, чем мы
сможем им воспользоваться
2. в эффективности и распределённости: если вычисляемое значение потенциально
можно использовать до того, как его полный расчёт закончен, то в рамках
классического ФП у нас нет никаких возможностей это сделать.
Конечно, решения этим проблемам найдено: в ML есть возможность писать
императивные программы, в Haskell есть монады, которые динамике императивных
вычислений ставят в соответствие бесконечные списки значений, которые являются
траекториями этой динамики — не самое удобное решение, imho.
Когда же мы пытаемся смотреть на программы, как на взаимодействующие через
специальные интерфейсы, объекты, то мы опять теряем динамизм. Потому что
объекты в нашем интуитивном представлении соответствуют совсем не процессам,
совсем не динамичным структурам. В рассматриваемом примере, естественным
образом (по моему мнению, конечно, но подкреплённому многими учебниками по
ООП, в которых похожие задачи, о 8 ферьзях, например, именно так и решаются),
был выбран объект: башенка. И мы видим, к чему приводит такая абстракция — к
немедленному построению рекурсивного алгоритма, со всеми вытекающими
недостатками.
Ну, конечно, в случае импративного ООП, генерацию данных для визуализатора
можно начинать сразу же, как рекурсия достигнет первого дна, но она может
достигать её очень долго. В рамках ФП это тоже можно сделать, но несколько
запутанней. Кроме того, не нужно забывать про то, что мы не
сможем в так выбранной системе объектов решать задачу с бесконечной башенкой.
Именно из-за того, что ООП и ФП ограничивают программиста в возможности
увидеть динамику в задаче, лично я никогда не пользуюсь ими при проектировании.
Сосредотачиваюсь на том, как должны в программе течь данные и как они должны
изменяться и это приводит, на мой взгляд к более красивым и простым
решениям. Потому что мир динамичный, потому что такое проектирование гораздо
ближе к физической реальности, чем объекты или функции, потому что нет ни
объектов, ни функций в природе. Есть лишь динамические системы, как пытается
доказать нам современная физика. Так зачем же свой разум ограничивать
сосредоточенностью на статичных моделях реальности, которыми являются ФП и
ООП? ФП по своей математической природе, а ООП по той причине, что в
современной форме фиксирует сознание на аналогиях с пассивными
материальными объектами.
Справедливости ради нужно отметить, что в нашем примере объектом можно было бы
выбрать как раз цепочку ходов, и построить аналогичную императивному решению
программу, НО ОО программист начинает с поисков очевидных объектов, а не с
анализа динамики, чем ограничивает свои возможности по проектированию,
и это приводит его зачастую к решениям более похожим по своей
структуре на ФП. В рамках же ФП подхода такое тоже потенциально можно было бы
сделать, но намного сложнее, а бесконечную башенку обсчитывать можно было бы
только в функциональных языка с полностью ленивым исполнением, в рамках самой
же lamda-абстракции такое вычисление будет невычислимым. Что ещё раз, кстати,
доказывает, что компьютер — это гораздо больше, чем машина Тьюринга.
Кроме того, к подобному проектированию склоняют и языки программирования,
которые зовут себя ОО. В них объекты — это не
динамичные сущности, обменивающиеся сообщениями, как это задумывалось ещё в
Smalltalk, а именно статичные
абстрактные типы данных, не более. Динамичный же объект, который живёт своей
жизнью, создать довольно сложно. Это противятся даже в распределённых
технологиях, та же CROBA, в
которой объекты оживают только лишь по запросам, и просто сам возможный способ
реализации: запуск отдельной нити, и доступ к разделяемым данным с интерфейсом
при помощи синхронизации. Это уже создание полноценного клиент-серверного
приложения выходит. Но ООП опять же склоняет создавать его не в виде процесса,
а в виде набора объектов, которые опять же получаются мёртвыми и нединамичными
по своей сути. Между ними сложно организовать настоящий поток данных, их
сложно запускать параллельно, потому что для этого их опять нужно делать
серверами.
Между тем некоторые языки, начавшиеся в виде чисто функциональных решений, в
итоге развились до предоставления возможности создавать именно такие сущности
— процессы, обменивающиеся сообщениями. Erlang и O'Caml, тому примером, но эта
возможность основывается на близкой к импаративной функциональности этих
языков: на монадах или явной возможности хранить состояния. При чистом
императивном структурном подходе с этим вообще никаких проблем не возникает:
Limbo, Ada или нечто подобное IPC в UNIX.
Собственно на этом основан призыв (не только мой, кстати:
http://www.lysator.liu.se/c/pikestyle.html) отказываться от ООП и ФП везде, где
только это возможно, и сосредотачиваться на анализе изменений данных в
программах, на свойствах состояний и на логике изменений.
Очередное
отступление: современная физика считает существующим то, да это и интуитивно
понятно, что сохраняет свойства в процессе изменений, не сосредотачиваясь на
анализе динамике в программе нельзя точно выявить сохраняемые свойства, а
следовательно и объекты. Такой анализ приводит к более гибким решениям, и к более эффективным.
Интерфейсы, функции, модули, классы возникнут естественным образом в процессе
реализации программы. И их можно будет использовать повторно.

Tags:
Hubs:
+12
Comments54

Articles