Хватит спорить про функциональное программирование и ООП

    Пост содержит некоторое количество стёба, минздрав убедительно просит неподготовленного читателя воздержаться от прочтения.

    Статьи на тему «ФП лучше» или «ООП лучше» напоминают дебаты, что же лучше для обеда, вилка или ложка. Традиционно джуны начинали с ложки, но кто-то очень авторитетный однажды поведал, что ест только мясо и использует вилку, поэтому зародилась новая мода — есть вилкой. Ей едят и каши, и супы, и даже умудряются лакать смузи. Интернет завален статьями, какие мы молодцы, что научились есть смузи вилкой и преодолели все грабли. Это и смешно и грустно, с одной стороны, даёт конкурентное преимущество бывалым ребятам, которые показывают сверхрезультаты просто игнорируя этот хайп, с другой, приходится переучивать коллег и сотрудников, вычищая из их головы нанесённый ветром мусор. В этой статье я постараюсь рассказать своё видение, которое не претендует на абсолютную истину, но очень хорошо работает на практике

    Как принято в науке, начинём с определений. Классическое определение ООП включает в себя следование принципам наследования, инкапсуляции и полиморфизма. Но если у нас нет одного из этих составляющих, будет ли это ООП? И если нет, то что это будет? Пока занудная часть аудитории зависла над этим непрактичным и ничего нам не дающим вопросом, вспомним, что было до ООП. А до него было процедурное программирование. И основная идея ООП на тот момент была в связи данных и функций для их обработки. Идея простая, но довольно революционная, сложно представить насколько, но об этом позже.

    Функциональное программирование, в вольной трактовке, рассматривает программу как математическую формулу. Формулы хорошо формализуются и при одинаковых входных данных возвращают одинаковые выходные. Вся программа состоит из подпрограмм, следующих тем же принципам. Чем это отличается от того же процедурного программирования? ФП активно использует чистые функции, в идеале вся программа должна быть чистой функцией. Чистые функции не имеют сайд-эффектов, их можно легко мемоизировать, легко тестировать и т.п… Можно сказать, в чистых функциях основная идея и преимущество ФП.

    А теперь два вопроса:
    — Можем ли мы использовать чистые функции в ООП?
    — Можем ли мы привязывать функции к данным в ФП?
    Ответ на оба из них утвердительный. Статические методы классов могут быть чистыми, даже методы экземпляров можно считать чистыми, если они не создают сайдэффектов и мы рассматриваем свойства экземпляра класса как параметры. Границы классических определений раздуваются и кто-то может быть не согласен, но на практике это просто работает. И такие методы формализуются и тестируются ничуть не хуже, чем классические чистые функции, написанные по всем канонам. Про привязку методов к данным чуть сложнее, накладывают ограничения используемый язык и библиотеки. Скажем, в JavaScript это делается элементарно, не уверен за Haskell и Erlang. Теперь самое интересное, что это даёт, и почему уже ООП поднял такой хайп лет 20-30 назад. Если вы пишете небольшую программу — вы можете писать как хотите, кроме вашего чувства прекрасного это ни на что не влияет. Когда вы создаёте действительно большую программу — возникает проблема сложности. Не вычислительной сложности, считаем, что здесь мы делаем всё хорошо, а воспринимаемой сложности. Скажем, у вас есть 50 000 строк кода, и все они целесообразны. Как их организовать так, чтобы не сойти в с ума (или не уходить с работы в 11 ночи)? Мы не можем уменьшить количество операций, но можем уменьшить число связей между ними (в этом нам и помогает инкапсуляция). Мы скрываем сложную реализацию за простым интерфейсом и дальше работаем только с интерфейсом. Например, интернет — жутко сложная штука, но большинству разработчиков достаточно знания протокола HTTP, чтобы выполнять свою работу и оставить сетевой, физический и другие уровни сисадминам. Чем слабее связанность наших модулей, тем меньше сложности на этапе их интеграции между собой. Чем меньше один модуль знает про другой, тем меньше их связанность. Привязка методов к данным внутри модуля помогает нам избавиться от этого знания у потребителей модуля. В этом основное прагматическое преимущество ООП. Над чем? Над подходом без привязки данных и методов. ФП, как мы выяснили, про это не говорит. Вы можете передавать классы как аргументы в чистые функции, или можете использовать чистые функции как методы класса, одно другому не противоречит, а только дополняет.

    По практике, где работает преимущественно один подход, а где преимущественно другой? Когда я пишу бекенд на NodeJS, он сам собой как-то получается в функциональной парадигме. Почему? Потому что запрос на сервер — это по природе своей функция, с фиксированным инпутом и аутпутом. Функциональный подход ложится на серверные запросы очень естественно и код получается компактнее и гибче. Когда я создаю фронтенд для браузера — как правило лучше работает ООП, потому что кроме инпута и аутпута у нас есть поток пользовательских событий, а так же программные события, такие как начало и конец анимаций, запросы на сервер и т.п… Функциональный подход работал бы, если бы нужно было просто отрисовать статическую страничку без интерактива, при использовании ФП во фронтенде страдает либо интерактив, либо время разработки (по нашим замерам, раза в 3). Почему?

    Любая парадигма программирования базируется на определённой модели реальности, а модель это всегда упрощение. В ФП модель накладывает больше ограничений на мир, поэтому её проще формализировать. По той же причине, когда она становится не релевантна условиям задачи — она начинает требовать больше костылей. Например, ФП на фронтенде решили проблему пользовательского ввода созданием массива событий (экшенов, привет redux). Но это является нерелевантной абстракцией, которая кроме того, что бьёт по производительности, здорово увеличивает время разработки. Таким подходом можно создать todo-лист, но на действительно больших проектах придётся разбивать лбом кирпичи, а потом писать победные статьи для таких же несчастных. Для сравнения, когда мы писали биржевой терминал (на vanilla js, естественно) с canvas, svg и обновлением несколько раз в секунду по websockets, в некоторых часто обновляемых компонентах мы не удаляли div'ы, а переиспользовали, так как их пересоздание — сравнительно дорогая операция в браузере (и это важно, если у вас действительно большое приложение). Если вы программируете на ФП на фронте — у вас даже такой мысли не возникнет, так как вы уже смирились с иммутабельностью (кстати, замечательная вещь для работы с многопоточностью, которой в JS не бывает), с тем, что каждый экшн проходит через каждый редьюссер и другим хламом. С другой стороны, на бекенде часто получается обходиться без классов совсем, так как там, как раз, можно избежать расходов на их создание, так как условия задач очень релевантны модели ФП. Но, в основной массе, Java и PHP разработчики как раз не спешат изучать ФП, в первых рядах фронтендеры, которым это реально меньше всего нужно. Как упражнение для ума — интересно конечно, только программы получаются г… но, а кому-то ими пользоваться. При том, что фронтенд — сравнительно молодой раздел IT, и своих нерешённых задач там на несколько поколений. Чем, казалось бы, не упражнение для ума?
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 252

      0
      Функциональное программирование также хорошо тем, что отлично вписывается в концепцию формальной верификации: например, в нём гораздо меньше проблем с сайд-эффектами.
      Это упрощает создание отказоустойчивого софта.
        +12
        И использование только целых чисел хорошо тем, что отлично вписывается в концепцию формальной верификации. А с вещественными числами сплошной головняк: ошибки накапливаются, и уже непонятно, если прогамма выдала ответ 1.23, это 1.23±0.01 или 1.23±1000. Ну его нафиг, давайте лучше без вещественных вообще.
          +9

          Ну, и во многих областях это оправдано. Так появилась поддержка длинных целых и рациональных чисел с одной стороны, и всё более мощные символьные движки в повседневных задачах. Так что не зря упирались теоретики!

            0

            Давайте лучше откроем учебник по численным методам.

              0
              вот вы бы так функционально озабоченным отвечали: откройте учебник по ООП.
                +3
                А нужно ли открывать учебник по численным методам, если вы, скажем, пишите бухгалтерскую программу? И пытаться понять — откуда у вас взялось в балансе расхождение в копейку? Если можно вместо этого считать всё в копейках и не иметь проблем?

                Правда ведь заключается в том, что использования вещественных чисел действительно стоит избегать… просто иногда без них задача не очень решается…
                  0
                  старый добрый трюк, который почему-то очень редко пишут во всяких книгах и уроках
                    0
                    А как же классика — Bloch, J., Effective Java, 2nd ed, Item 48
                    0

                    Можно считать в копейках, пока не придут 1/5 копейки, логарифм и экспонента.

                      0
                      Там где могут придти 1/5 или 1/10000 копейки есть всё равно свои правила, позволяющие считать в целых числах.

                      Числа с плавающей точкой — зло. Иногда, впрочем, неизбежное зло, как я сказал — но всё равно зло.
                        0
                        Да, и если вы вовремя не округлите до копейки, то у вас не сойдётся итоговый баланс. Таким образом мы возвращаемся к расчёту в целых числах.
                        А то вот пользуюсь ипотечным калькулятором, автор которого не совсем округляет числа. И на данный момент реальные числа и расчёты в этом калькуляторе разбежались на копейку уже. И вот что в одной из сумм:
                        хххх.97000000003

                        Бухгалтерия вам будет благодарна за такое.
                          0
                          Оп! А в бухгалтерии-то 1С, а в этой платформе нет настоящих плавающих запятых. Ну точнее есть, но только на границе с внешним миром (и то не всегда) и в кишках математических функций, которые внутри с float/double работают (но параметры и результат — всё равно свои числа).
                          Тип «Число» в переменных это примерно как BigDecimal в Java (но, если ничего не изменилось за 5 лет, существенно менее эффективный). В БД в полях, доступных программисту конфигурации — Numeric из SQL (с ограничением длины и точности), который отображается в такой же ограниченный тип в памяти с достаточно необычным подходом к переполнению. Так что в бухгалтерии всё сойдётся :) Ну или не сойдётся по другой причине.

                          Классических Int, замечу, тоже почти-почти нет. И это имеет свою цену с точки зрения производительности — другой настолько тормозной системы в задаче «посчитай в цикле до миллиарда» даже среди интерпретаторов не найти.
                            0

                            Передадим в бухгалтерию (читай 1С) xxxx.97 миллиард раз (ну или она так прочитает наши хххх.97000000003 из CSV файлика), а у нас вместо вместо xxxx.970000000.00 в 1С итоговая сумма будет xxxx970000000.03 (если не напутал). В лучшем случае главбух объяснит гендиру, что программисты идиоты и считать не умеют, поэтому в годовой бухгалтерской и управленческой отчётности суммы различаются. А в худших может быть различие бухгалтерской и налоговой отчётности, или в суде клиент докажет, что его хотели обмануть на три копейки и получит компенсацию морального вреда и неполученной прибыли на 100500 тысяч, да ещё антимонопольщики за недобросовестную рекламу оштрафуют.

                    –1
                    Ну его нафиг, давайте лучше без вещественных вообще.

                    На самом деле, для любого практического применения можно обойтись только рациональными числами (если ошибаюсь — поправьте).

                    Например, для вычисления окружности Вселенной, измеренной в атомах водорода, нужно около 40 знаков числа пи. То есть, округляя до первых 100 знаков после запятой, мы гарантировано получим адекватные результаты для любых вычислений длинн в пределах наблюдаемой Вселенной с любой доступной нам (даже в теории) точностью.

                    То есть иррациональные числа это лишь удобная математическая абстракция, как плюс или минус бесконечность, которой не обязательно сущствует в реальном мире (особенно если время, пространство и другие величины квантуются).
                      +1
                      Более того, все интересные иррациональные числа вычислимы.
                    • НЛО прилетело и опубликовало эту надпись здесь
                      +1
                      При этом, писать, читать, дебажить код — гораздо тяжелее. Так что тяжело сказать что оно там упрощает.

                      Ну а писать код без сайд эффектов можно, и нужно и на императивных языках. К тому же они поддерживают функциональный плюшки тоже, можно использовать там, где удобно. Короче как всегда, правда посредине.
                      +10

                      Про вилку и ложку — это хорошо! А ведь есть ещё палочки и ножи всякие… Споры о том "что круче" парадоксальны в своей бесполезности. Ответ очевиден — лучше научиться владеть всеми приборами, и это не мешает иметь среди всех приборов любимый.
                      Например, я люблю считать на логарифмической линейке, хотя каждый день ею, конечно, не пользуюсь, для этого есть калькулятор. Но опыт работы с линейкой даёт зримое представление о преобразованиях, соответствующих вычислениям. Движения ползунка и бегунка превращают вычисления в буквальную манипуляцию: в преобразования руками, от которых приходит интуитивное геометрическое представление о поле чисел, имеющее под собой глубокое теоретико-групповое основание. Ответ не берётся из ниоткуда, а возникает в контексте масштаба и своеобразного "ландшафта" вычислений, так что проверка его правильности начинает согласовываться с интуицией. Это как знание города помогает понять, как тебя везёт таксист.
                      Подобные опыт и интуицию даёт работа в Лиспе и Хаскеле. С ними программа на JS или C# превращается не просто в набор рецептов, инструкций, а в те или иные вычислительные схемы или математические структуры с присущими им свойствами.
                      Но, полагаю, даже если жаркие дискуссии на темы "нужна ли программистам математика", "что круче: ФП или ООП" и т.п. постепенно отомрут, на смену им придёт что-то вроде: "кто круче, как программист: ИИ, корректно выполняющий ТЗ, или человек с его творчеством?". Мы уже видим начало этой эпохи, споря можно ли доверять машине управлять автомобилем на дороге.

                        –4
                        Как Иисус сказал!
                        0

                        Обычно самая сложная часть бэкенда (хайлоад не трогаем) — это обработка запросов с сайд — эффектами. И хорошо если синхронных с точки зрения клиента(браузера), чётко имеющих вход и выход. А если попутно ставится задание в очередь, о выполнении которого клиент потом уведомляется? Никак тут моделью функции, пускай и не чистой, не обойтись.

                          0
                          На мой взгляд обойтись всё-таки реально, особенно если отказаться от асинхронности.
                          А проверить выполнение задания клиент может и сам, даже без уведомлений.
                          Да, удобство снизится, зато безопасность и отказоустойчивость будут максимальны.

                          Во всяком случае, если не весь код можно сделать функциональным, то хоть его самую важную часть.
                          CMS, фреймворки, да и сами языки для веб-программирования содержат большое число различных функций, которые ничего не записывают и не сохраняют промежуточных значений.
                          Порой там находят опасные уязвимости, так что проверка формальными методами им бы не помешала.
                            +3
                            На мой взгляд обойтись всё-таки реально, особенно если отказаться от асинхронности.
                            А проверить выполнение задания клиент может и сам, даже без уведомлений.

                            То есть после выполнения запроса клиент должен постоянно пинговать сервер «где там мой ответ?» А если клиентов сотни тысяч? Сервер только и будет делать, что «пинги» разгребать.
                              0
                              Я ж говорю, самая важная часть бэкенда — обработка небезопасных (изменяющих состояние сервера) запросов. Не, можно какие-то монады прикрутить, чтобы и изменения были, и функционально было. Но стоит ли оно того, а если стоит, то кто платить будет?
                                +2
                                Вы как-то странно формулируете свое или-или. Монады — это не про «функционально или изменения». Это (в несколько примитивной форме) способ оформить изменения таким образом, чтобы их нельзя было сделать криво. Путем ограничения контекста, где их можно делать, лишь некоторыми функциями.

                                Возможно, и даже наверняка, это чего-то стоит. Но по большому счету разделение кода на чистые функции, и функции с побочным эффектами — это то, к чему так или иначе стоит стремиться.

                                Вот вы скажем имеете что-то против single responsibility principle? Посмотрите на это как на другую его сторону. Выделить побочные эффекты — это полезно. Вы можете всегда накодить тяп-ляп, и не сделать этого, точно также, как намешать в один метод или класс кучу функций. Так тоже можно, и так (увы) тоже работает.

                                Стоит ли оно того? Ну так это вам решать. Если сегодня нагавнокодили — это да, сегодня дешевле. А завтра? Ну вот и тут примерно так же.
                                  +1
                                  Я не считаю, что класс с состоянием, геттерами(хезерами, изерами, ...) и мутаторами нарушает SRP. Ну и я их разделяю в подавляющем большинстве случаев: геттеры возвращают что-то, мутаторы — нет (типа функций и процедур в Паскаль). Ну есть ещё фабрики, которые создают что-то и возвращают созданное. Иногда мутаторы возвращают свой инстанс для удобства использования в цепочке (билдеры вские). Зачем тут монады и вообще ФП? Оно бывает удобно (в основном для filter/map/reduce инлайн), то зачем больше его внедрять не понимаю.
                                    +1
                                    >Я не считаю, что класс с состоянием, геттерами(хезерами, изерами, ...) и мутаторами нарушает SRP.

                                    Я не совсем про это, вообще-то. Разве геттеры — это про композицию?

                                    >Зачем тут монады и вообще ФП?
                                    >Оно бывает удобно (в основном для filter/map/reduce инлайн), то зачем больше его внедрять не понимаю.

                                    Монады, если еще чуть упростить — это способ безопасной композиции. filter/map/reduce — это один частный случай. Для остальных частных случаев и внедряют обычно остальное. Этих случаев немножко больше, чем допустим имеется на сегодня в вашем (или моем) наборе инструментов. Ну так это нормально — никто не заставляет внедрять все сразу. Скажем, аппликативные функторы — это неплохое описание процесса валидации исходных данных, и оно тоже бывает удобно.

                                    Можно же и так зайти — зачем вам фабрики, если у вас есть билдеры всякие? Да в общем все затем же — чтобы к каждой задаче выбрать свой наиболее подходящий инструмент.
                                      0
                                      Переформулирую вопрос: почему вы считаете монады или ещё какие функциональные способы призводить сайд-эффекты (прежде всего изменения какого-то состояния) наиболее подходящими инструментами для этого? Чем созданные специально для инкапсулированного состояния объекты хуже?
                                        +2
                                        Я не говорил, что они наиболее подходящие. Я говорил, что они просто инструменты для композиции. И что вы скорее всего похожие инструменты все равно применяете, с теми же целями. Так что это был ответ на вопрос «зачем», без попытки сравнивать.

                                        >Чем созданные специально для инкапсулированного состояния объекты хуже?
                                        Не знаю, кто такие эти объекты. Давайте на простом примере, который вы точно знаете. List — это монада. Чем map лучше по сравнению с циклом for (a: list)? И по сравнению с циклом for (int i= 0; i< list.size(); i++)?

                                        По-моему, ответ очевиден — тем что map это как раз безопасная композиция. Я гарантировано знаю, что применяя при помощи map функцию String->Integer к List я точно получу List, и ничего иного. Причем исходного размера. А применяя filter — получу List, возможно меньшего размера. И сколько бы я их не компоновал, я не смогу эти правила нарушить, независимо от того, какими типами мы тут в List<?> манипулируем. То есть, она еще и универсальная.
                                          +1
                                          Я гарантировано знаю, что применяя при помощи map функцию String->Integer к List я точно получу List, и ничего иного.

                                          Нет, не знаете. Ну, то есть, знаете, но этого недостаточно.


                                          Гарантированно кем? Если сигнатурой, то терм map f _ = [] удовлетворяет высказыванию типу (a -> b) -> List a -> List b.


                                          Классического хаскеля не хватит, нужно притащить в formation rule возможность выражать типы { n : Int } -> (a -> b) -> Vect n a -> Vect n b. Что, впрочем, не помешает написать ерунду с идеей replicate n . f (head vec), там уже надо будет доказывать теоремки типа map id xs = xs.


                                          А filter тогда будет {n : Int} -> (a -> Bool) -> Vect n a -> (m ** Vect m a). Или -> (m ** Vect m a ** m `LEQ` n), если хочется больше строгости. Или ещё сложнее тип, если вы хотите поймать всю семантику filter (потому что filter f _ = [] снова удовлетворяет обоим этим типам). Или, опять же, теоремки. filter (const True) xs = xs, filter (const False) xs = [], all f (filter f xs) = True, всякое такое.

                                            0

                                            Самое главное — эти проверки и доказательства возможны, причём уже сейчас, так что глупо этим не пользоваться и спорить. Что подтверждает тезис, обозначенный в названии статьи.

                                              +1

                                              Я обычно очень активно проповедую проверки и доказательства на уровне типов, но сегодня я надену другую шляпу, раз вы сказали «уже сейчас».


                                              Какие языки у нас есть, в которых это возможно? Есть Coq, но это не язык программирования, программы из него экстрагируются куда-нибудь. Аналогично есть Agda, но это тоже не очень прикладной язык программирования (хотя стиль доказательств в ней мне ближе, чем в коке). Есть Idris, который язык, который вроде как всем идеален, ничего даже никуда не надо экстрагировать, но он пока ещё слишком молод и бажен. Написать формально верифицированную проверку строки на палиндромность на нём у меня не получилось, я упёрся в не очень разумное сообщение, что чё-то там нельзя матчить на LHS, и даже чтение исходников тайпчекера не помогло мне понять, что делать.

                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                  0
                                                  Ну, это уже скорее дело субъективное. Я лично сторонник proof-carrying code по разным соображениям (начиная хотя бы просто с изящества и простоты).
                                                  +1

                                                  Боюсь, что разочарую вас. Я имел в виду принципиальную возможность двигаться в этом направлении, если оставаться в рамках ФП. Пока же выкладки приходится делать "на бумажке". Но! Это возможно сделать. Я игрался с формальной верификацией некоего подмножества Java (практически, процедурным подмножеством, не выходящем за пределы Оберона) через триады Хоара. Очень быстро система неравенств становится неподъёмной, по моим ощущениям, экспоненциально. Инварианты циклов приходится писать самому, а это искусство и шаманство. После этого, возвращаясь к типам и индукции в ФП, с доказуемыми свойствами алгебраических структур, понимаешь, какой это кайф: надеть, наконец лыжи после того, как брел по пояс в мокром снегу. Но и лыжи пока приходится переставлять самому. Впрочем, пока ждем завтипов в Хаскеле, можно упражняться, отрабатывая технику на том что есть. Понятно же, что для того, чтобы написать грамотную рабочую спецификацию для автоматического верификатора, потребуется нехилая квалификация программиста. Но пока, насколько я вижу, именно ФП ведёт нас к возможности по-настоящему взлететь.

                                                    0
                                                    Я смотрю на все это проще. Даже если заменив цикл на map я просто более ясно выразил в коде свои намерения — я уже получил практическое преимущество. Ну то есть код становится лучше, даже если мы не можем доказать его правильность, мы хотя бы все одинаково понимаем его функции. И если в следующем релизе или через пару лет никто его не сломает, потому что неверно понял назначение этого куска — это уже хорошо. А это так и будет.
                                                  +1
                                                  >Нет, не знаете. Ну, то есть, знаете, но этого недостаточно.

                                                  Ну, это смотря по сравнению с чем. По сравнению с циклом, результат которого вообще без детального анализа непонятен — очень даже знаю. Собственно, я хотел сказать простую вещь — что map ограничивает изменения одним элементом списка, не позволяя функции менять структуру списка каким-то непредсказуемым способом.

                                                  Понятно, что могут быть какие-то еще эффекты, скажем в Java функция String->Integer легко может выкинуть исключение — но это означает, что функция определена не на всем множестве входных значений. И в Java я не могу этого выразить, да. Что совершенно не отменяет вполне практических преимуществ map в этом случае.
                                    +3

                                    Функциональному подходу нет необходимости заполнять всё вокруг. Оно тяготеет к маленьким самодостаточным ортогональным блокам и если в императивной архитектуре такие блоки использовать, то они не помешают. В Фотране (куда уж императивнее!) с 80-х годов есть модификатор pure, указывающий и программисту и компилятору, что определяемая функция чистая, что позволяет им делать определённые выводы как о коде функции, так и о коде, ее использующем.
                                    Операционную систему не сделать чистой по определению, но с некоторыми задачами ФП справляется отлично. Например, на моём ноутбуке, а также на домашнем и на рабочем десктопах стоит NixOS (Linux-дистрибутив построенный вокруг функционального ленивого (а значит, чистого) пакетного менеджера Nix), c оконным менеджером XMonad. И мне нужна их декларативность при настройке и переносе решений с машины на машину. Но это не позволяет мне говорить, что ФП решает все проблемы. Но оно очень неплохо встраивается в императивные решения, поскольку предлагает… чистые функции :)

                                      +1

                                      Я тоже пользуюсь NixOS, и при этом ещё до перехода на неё начал переписывать скипты, которые обычно писал на bash, на haskell, но только когда main = interact myPureFunction. Тогда гораздо легче отлаживать ошибки в них, а ещё можно скомпилировать и получить некую прибавку к скорости и производительности.


                                      А всё, что нельзя описать interact, лучше написать на классическом баше или перле — быстрее и читаемей.

                                        0
                                        А всё, что нельзя описать interact, лучше написать на классическом баше или перле — быстрее и читаемей.

                                        Нет. Написание скриптов на хаскелеподобных языках даёт ещё ряд других ништяков.


                                        Пора бы уже про это статейку наваять.

                                          0
                                          о, обязательно напишите!
                                          и еще чтобы с примерами «скриптов на хаскелеподобных языках» (мне действительно интересно).
                                            0

                                            Там ещё свободные монады будут.

                                              0

                                              Это, действительно, было бы очень полезно и для практики и для участия в холиварах с пруфами :)
                                              Вопрос не по теме. Присмотрел для перевода материал по freer monad, но сижу, чешу в затылке, как корректно перевести на русский freer: "ёщё более свободные", "освобождённые"… есть ли устоявшийся термин?

                                                0

                                                Неа, устоявшегося термина я не знаю.


                                                Но я где-то видел, что operational monads и freer monads отождествляют.

                                                  0

                                                  Ага! спасибо, посмотрю, operational переводится лучше, но они не тождественны, а связаны через Coyoneda. Интересно, сам Олег Киселёв как их называет?

                                            0
                                            ждем с нетерпением)
                                        0

                                        Одна из основных задач программирования — это изоляция сайд-эффектов. Если у вас допустим идёт работа с БД, то можно сохранять данные по мере вычисления и размазать логику работы с БД по всей программе. А можно сначала подготовить все данные, а потом сохранить их все разом. Это можно делать в любой парадигме, но, применяя ООП, про это, к сожалению, часто забывают.


                                        А если попутно ставится задание в очередь, о выполнении которого клиент потом уведомляется? Никак тут моделью функции, пускай и не чистой, не обойтись.

                                        В чём проблема? Или вы представляете какую-то одну божественную функцию, которая делает всё? Это не так работает.
                                        Постановка задания в очередь — это сайд-эффект, но тем не менее это никак не мешает вернуть какой-то ответ клиенту. А при выполнении задания, когда до него дойдёт очередь, уведомить клиента, например через веб-сокет.

                                          +1
                                          Изоляция сайд-эффектов — это не задача программирования, это способ держать его результат под контролем.

                                          Уведомление клиента через полчаса после возврата из функции — это тоже результат функции.
                                        0

                                        Когда код простой, можно и в процедурном стиле написать, то, что бэк на ноде выглядит функционально это скорее особенность ноды — в той же java обычный бэкэндщик будет вызывать блокирующие процедуры.
                                        Что касается переиспользования дивов — реакт с его функциональным подходом давно так делает, работа же с ивентами без стримов быстро превращается в спагетти.

                                          +12
                                          >Java и PHP разработчики как раз не спешат изучать ФП
                                          Хм. Вот люблю я, когда так вот обобщают. Видимо, это не Java разработчики когда-то довольно давно изобрели clojure — это хаскелисты прокрались в их ряды. Это не Java разработчики внедрили в Java 8 много всего разного от ФП, в частности, сделав функции наконец-то удобными в работе. Это все они, это их заговор, мы-то знаем, что настоящие Java разработчики не спешат изучать ФП.
                                            +2

                                            Гипотетически они не "не спешат", они не могут. Порог входа высокий.

                                              0
                                              Ну, всегда кто-то может, а кто-то нет. Это так было, есть и будет. Квалификация и опыт разные. Я про то и толкую, что Java разработчики тут вообще никаким боком. Есть задачи, где ФП нужнее или скажем ООП лучше подходит, есть разные люди, кто-то опытнее или способнее.
                                              0
                                              А уж в PHP элементы ФП чуть ли не с первой версии. С третьей — точно!
                                              +1
                                              Мне кажется, все холивары ООП против ФП и т.д. из-за смешения объектно-ориентированного дизайна и ООП.
                                              ИМХО, ООП — это расширение (даже просто синтаксический сахар) идей модульного программирования, а будут ли инстансы таких модулей «объектами» в смысле ОО дизайна — отдельный вопрос. Если экземпляр класса инкапсулирует состояние и ограничивает к нему доступ — это объект, а если нет, просто синтаксический артефакт. Классы, методы и остальное вторичны, реализовать суть: инкапсулировать состояние и ограничить возможность его изменения хоть через открытый интерфейс, хоть через передачу сообщений.
                                              При чем тут ФП? Мне кажется, вообще не при чем. Речь идет о выборе языка реализации, а это совсем другой круг вопросов.
                                              А вот разговор о подходах к дизайну — осмысленный! Что в конкретном случае продуктивнее — рассматривать систему, как набор функций или как совокупность объектов с состоянием, или как сочетание того и другого — в этом суть. И можно подобрать удобный инструмент. Иначе придется чесать правой рукой левое ухо и завинчивать гвозди отверткой.
                                              Простите за занудство.
                                                0
                                                На русском не принято употрелять «объектно-ориентированный дизайн», употребляется «объектно-ориентированное проектирование», тоже ООП.

                                                А многие холивары внутри ООП из-за смешения понятий «инкапсуляция» и «сокрытие». Инкапсуляция — это совмещение данных и методов, а сокрытие — ограничение работы с данными напрямую.
                                                  +1
                                                  ZanudaMode.On()

                                                  Инкапсуляция это «Упаковка» ответственности, а совмещение данных и методов это частный случай инкапсуляции в ООП. Например — можно инкапсулировать алгоритм в функцию (или в статик метод, если угодно). А сокрытие, это следствие инкапсуляции при хорошем дизайне.

                                                  ZanudaMode.Off()
                                                    0
                                                    Я же написал «внутри ООП» :)
                                                –16
                                                Накину немного говна на вентилятор:
                                                Мое определение ФП — непрофессиональное программирование, либо программирование для гуманитариев, которые не могут в абстрактное мышление. Какими бы чистыми там функции не были, когда их будет 100500 они в любом случае превратяться в черный ящик с макаронами.
                                                  +7
                                                  Так не адекватно предмету, что вызывает улыбку.
                                                    –3
                                                    Покажите мне хоть одну серьезную большую программу в ФП.

                                                    Пока что все топители за ФП, которых я встречал, были только одного типа. В институтах их сразу заставили писать в ООП, не объяснив зачем это все нужно, и теперь они вдруг видят, что можно писать без нудных классов, просто бери и фигач код напрямую и все типо работает. Особенно это характерно для фронтендов, которые гуманитарии у которых на странице два скрипта по 10 строчек и ООП им действительно толькко мешает.

                                                    Вакансии с условием «уметь в ФП» я тоже чтото не видел, что намекает.

                                                    Вы путаете ПОП и ФП. Изучить ФП очень трудно (на порядок труднее ООП) как раз по причине очень высокой абстракции…
                                                    dreesh, Ну и вот тем более! Если фронт-джун топит за ФП это говорит о том, что на самом деле он просто не хочет писать в ООП, а хочет писать код чистоганом. Никаким ФП тут на самом деле не пахнет.
                                                      +2
                                                      Покажите мне хоть одну серьезную большую программу в ФП.

                                                      Компилятор Haskell GHC написан на Haskell :) Можете сами в этом убедится Glasgow Haskell Compiler
                                                        +3
                                                        Покажите мне хоть одну серьезную большую программу в ФП.

                                                        Riak. RabbitMQ, ejabberd. Бекэнд WhatsApp. Прошивка для коммутатора AXD301, обеспечившая надежность 99,9999999%. Из Хаскеллового выбирайте сами вот тут — там и банки, и телескопы, и hardware design.
                                                          0

                                                          Ещё добавим по вакансиям:


                                                          https://www.google.com/amp/s/www.zdnet.com/google-amp/article/developer-jobs-here-are-the-coding-languages-that-are-paying-the-best/


                                                          Согласно этой статье, топ зарплат у F#, Ocaml, Clojure, Groovy, Perl, Rust, Erlang, Scala, Go, Ruby. Вот десяточка.


                                                          Угадай, сколько из них ФП?

                                                        +2
                                                        Вот как раз унаследовать автомобиль от транспортного средства «гуманитарии» могут, а вот представить его как функцию от комплектующих, конвейера и времени — нет. :)
                                                          +5
                                                          Вы путаете ПОП и ФП. Изучить ФП очень трудно (на порядок труднее ООП) как раз по причине очень высокой абстракции…
                                                            +1

                                                            Какой-то FUD про трудность.


                                                            Equational reasoning вполне естественно для человека, пока его не начинают портить. Монада — это просто любая ерунда, удовлетворяющая таким-то законам, вот такие-то очевидные три примера. Ну и так далее.

                                                          +4
                                                          Статьи на тему «ФП лучше» или «ООП лучше» напоминают дебаты, что же лучше для обеда, вилка или ложка.
                                                          Практика турпоходов показывает, что ложка лучше — все всегда берут ложки, но практически никто не берет с собой в поход вилку :)
                                                          Аналогично, ООП позволяет решать более широкий круг задач, если исходить из определения автора:
                                                          Функциональное программирование, в вольной трактовке, рассматривает программу как математическую формулу. Формулы хорошо формализуются и при одинаковых входных данных возвращают одинаковые выходные.
                                                          Добавим в код генерацию случайного числа или обработку события и при одинаковых входных данных не получим одинаковые выходных. Т.о., согласно данному определению, в ФП это недопустимо. А в ООП (и других парадигмах) допустимо. Или я не понял предложенного в статье определения?
                                                            0
                                                            >Или я не понял предложенного в статье определения?
                                                            Не совсем поняли. Впрочем, там сразу написано, что это вольная трактовка определения. На самом деле, прагматический подход к такому (написанию ГСЧ) состоит в том, чтобы выделить такие куски кода, которые являются чистыми, и остальные, которые либо взаимодействуют с внешним миром (IO), или не являются чистыми по другим причинам.

                                                            > обработку события и при одинаковых входных данных не получим одинаковые выходных
                                                            Это с чего бы? Если у вас есть состояние — то почему вы его не считаете частью входных данных? И дело не в том, допустимо это или нет. Дело в том, что выводы, которые вы (или компилятор) можете делать по поводу вот этого вот кода, они зависят от того, является ли кусок кода чистым.
                                                              0
                                                              Спасибо за разъяснение.
                                                              прагматический подход к такому (написанию ГСЧ) состоит в том, чтобы выделить такие куски кода
                                                              ГСЧ может быть и аппаратным, частью CPU. Тут выделить не получится и ФП не применимо (в вольной трактовке).
                                                              Если у вас есть состояние — то почему вы его не считаете частью входных данных?
                                                              Если событие происходит в ходе вычисления и влияет на него.
                                                                0
                                                                CPU это часть внешнего мира. То есть выделяется тоже (в хаскеле — в виде IO). В принципе, можно вольно считать, что весь доступный программе внешний мир — это часть входных данных (как оно в общем-то и есть). И он же — результат.

                                                                >Если событие происходит в ходе вычисления и влияет на него.
                                                                Все что влияет — это часть исходных данных, почему нет-то? Если обработка событий происходит по-разному — значит у вас есть какое-то состояние? В ФП его просто делают чуть более явным.
                                                                  0
                                                                  Все что влияет — это часть исходных данных, почему нет-то?
                                                                  Данных, но не исходных, а текущих. Простейший пример: функция последовательными приближениями долго вычисляет результат, мне надоело ждать, нажал кнопочку, функция должна вернуть, что упела вычислить на этот момент.
                                                                    0
                                                                    >успела вычислить на этот момент.
                                                                    Это такое вполне обычное состояние. Я повторюсь — ФП не означает, что у вас скажем не бывает состояния. Оно лишь означает, что вы такие случаи, когда вычисления от него зависят, явно выделяете. Если вы зависите от железа в реализации ГСЧ, то у вас и не может быть никакой абстракции чистой функции _в этом месте_, но вполне может быть в другом. И такое разделение само по себе полезно.

                                                                    Вот такой простой пример, не совсем в тему — один мой коллега очень любит в один метод всунуть две вещи — чтение данных из файла, и работу с этими данными. Из чего вытекает нехорошее следствие — чтобы этот код протестировать, мы вынуждены в тестах заводить реальные файлы, и иметь дело с файловой системой, со всеми вытекающими. Если же мы разделим метод на две части, одну которая читает данные из файла, и вторую, которая обрабатывает, то вторая почти автоматически становится функцией, причем чистой. Ну то есть я это к тому, что и в совершенно не ФП случае выделение побочных эффектов в виде файлов вполне себе полезная штука.
                                                                      0
                                                                      Ну то есть я это к тому, что и в совершенно не ФП случае выделение побочных эффектов в виде файлов вполне себе полезная штука.
                                                                      Полностью согласен. В моем примере вижу только одно решение:

                                                                      повторять
                                                                      список_аргументов := чистая_функция_очередное_приближение (список_аргументов);
                                                                      до_той_поры_пока чистая_функция_точность_достигнута (список_аргументов)
                                                                      или кнопочка_нажата;


                                                                      Т.е. две чистых функции, но всю программу в виде читой функции не оформить.
                                                                        0

                                                                        А это и не надо. Смысл ФП не в том, чтобы всё было чисто, а в том, чтобы явно видеть эффекты функций в типах.


                                                                        Поэтому, кстати, всякие хаскелисты смотрят на функциональщиков из клана лисперов с некоторым удивлением.

                                                                  0
                                                                  ГСЧ может быть и аппаратным, частью CPU

                                                                  Даже в императивном языке придется к нему обращаться явно.
                                                                    0
                                                                    Чистые функции не имеют сайд-эффектов
                                                                    Ok: никаких внешних переменных, видимых помимо аргументов, но в регистрах, стеке, где-то еще (зависит от железа и реализации) всегда есть мусор от предыдущих действий. Если мы будем читать этот мусор? М.б. не очень хороший ГСЧ, но одинаковых выходных не получим. Либо любой мусор признать аргументами (входными данными), но тогда список аргументов будет зависеть от устройства черного ящика — железа и реализации, т.е. никакой абстракции. Либо чистить весь мусор, что в общем виде м.б. проблематично. Либо везде прописывать уникальный код и тестировать все локальные переменные на неинициализированность. Как-то очень нечисто?
                                                                      0
                                                                      Вы забыли добавить в список деградацию структур процессора, памяти и остальных компонентов которые могут встретиться между ними и как то повлиять на результат вычислений…

                                                                        0
                                                                        Говорим про исправный комп, всякие сбои и деградации не в счет.
                                                                          0
                                                                          Либо везде прописывать уникальный код и тестировать все локальные переменные на неинициализированность. Как-то очень нечисто?

                                                                          Ну как бы код после компиляции будет отличаться в зависимости от целевой системы разве нет?


                                                                          На самом деле я уже не совсем понимаю предмет обсуждения. Как связанно явное обращение к ГСЧ и наличие мусора на стеке и регистрах

                                                                            0
                                                                            Вы сказали:
                                                                            Даже в императивном языке придется к нему [ГСЧ] обращаться явно.
                                                                            ИМХО использование локальной переменной с неопределенным значением (в качестве случайного числа) — не явное обращение к ГСЧ. Такие обращения можно отследить в ходе исполнения, если во все переменые при запуске программы (и при вызове функции) будет записано уникальное значение, нпр., FFF… Так ловили баг в древних Паскалях. В некоторых ЯП всегда записано значение по умолчанию, нпр., ноль.
                                                                        0

                                                                        Внезапно, доступ к неинициализированным переменным можно (и нужно) запретить. Либо всегда инициализировать их значением по умолчанию, как вы ниже заметили.

                                                                          0
                                                                          Следовательно, возращаясь к сравнению статьи: ложка лучше вилки, т.к. ООП не требует дополнительных мер к неинициализированным переменным)
                                                                            0

                                                                            ФП не требует переменных, так что ещё непонятно, что лучше.

                                                                              0
                                                                              ФП не требует переменных
                                                                              Сможете доказать это утверждение строго математически: Теорема. Любую функцию можно реализовать без использования переменных?
                                                                              И практически интересно: как спрограммировать в этом подходе решето Эратосфена?
                                                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                                                  0
                                                                                  Т.е. числа Фибоначчи считаем по самой долгой рекурсии с 2 рекурсивными вызовами? :)
                                                                                    +1

                                                                                    Зачем? fibs = 1 : 1 : zipWith (+) fibs (tail fibs).


                                                                                    Стотысячное число в интерпретаторе вывело меньше чем за секунду. И никаких переменных.

                                                                                      +2
                                                                                      Стотысячное число в интерпретаторе

                                                                                      «Скриптуха!» (С) :)
                                                                                        0
                                                                                        Как по мне, так это все игра в бисер: переменные появляются ровно в том месте, где аргументы превращаются в параметры (подобно тому, как бордюр превращается в поребрик).
                                                                                        0
                                                                                        Т.е. числа Фибоначчи считаем по самой долгой рекурсии с 2 рекурсивными вызовами? :)

                                                                                        Боже упаси! Рекурсивная функция не обязательно реализует рекурсивный процесс. если хочется организовать итерацию с "переменными" a и b:


                                                                                        fib n = go 0 1 n
                                                                                          where go a b n    
                                                                                                  | n == 1    = a
                                                                                                  | n == 2    = b
                                                                                                  | otherwise = go b (a+b) (n-1)

                                                                                        что эквивалентно псевдокоду:


                                                                                        a = 0; b = 1 
                                                                                        while (true)
                                                                                          if (n == 1) return a
                                                                                          if (n == 2) return b
                                                                                          a,b = b,a+b; n--

                                                                                        Но в функциональном решении пропустить инициализацию "переменных" нельзя никак.

                                                                                          0
                                                                                          Так нужны переменные a,b,n? Зачем слово «переменных» в кавычки ставить? ИМХО отлаживать проще, когда известно точное имя. Мне кажется, что переменные (пусть локальные) облегчают разработку.
                                                                                            0
                                                                                            Но ведь это не переменные.
                                                                                              0

                                                                                              Это не переменные, поскольку они не могут измениться, оставаясь в рамках процесса, описываемого функцией. Изменения происходят только на входе-выходе. Одно из отличий, в частности, состоит в том, что, в функциональном коде нет понятия времени и изменение наших "переменных" происходит одновременно: a,b = b,a+b, эквивалентное последовательности присвоений с буфером с = b; b = a+b; a = c.
                                                                                              Это не лучше и не хуже нормальных переменных, просто если проще описать вычислительный процесс итеративным, ФП этому не сильно помешает.

                                                                                                0
                                                                                                Понял. Может лучше сказать, что это переменные с особыми свойствами? ;) Так будет понятнее, чем «без переменных».
                                                                                                  +1
                                                                                                  Особой свойство этих переменных — они не перемениваются :)
                                                                                                    +1

                                                                                                    В англоязычной литературе используется слово binding, что лучше отражает суть. В русскоязычной аналога не придумал и всегда называют переменными, даже если они не изменяются.

                                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                          0
                                                                                          Сможете доказать это утверждение строго математически: Теорема. Любую функцию можно реализовать без использования переменных?

                                                                                          Сначала нужно будет строго определить понятие переменной.


                                                                                          В любом случае, SSA у компиляторов вполне обычных императивных языков как бы намекает.


                                                                                          И практически интересно: как спрограммировать в этом подходе решето Эратосфена?

                                                                                          На том же хаскеле в чистом коде оно спокойно делается.

                                                                                            0
                                                                                            SSA у компиляторов вполне обычных императивных языков как бы намекает.

                                                                                            Вы хотите сказать, что ФП — синтаксический сахар?
                                                                                              0

                                                                                              А почему не императивщина — синтаксический сахар? :)


                                                                                              К слову о решете, я тут добрался до ghci, и вот пример:


                                                                                              λ> erato = [ n | n <- [2..], all (/= 0) [ n `mod` n' | n' <- [2 .. n - 1] ] ]
                                                                                              λ> take 10 erato
                                                                                              [2,3,5,7,11,13,17,19,23,29]

                                                                                              Снова никаких переменных. Не очень оптимально, правда, можно зареюзить erato вместо списка [2..n-1], но это потребует включать мозг, а я сегодня уже устал что-то.

                                                                                                0
                                                                                                Может взаимно? и это, и то — сахар? ;)
                                                                                                  0

                                                                                                  Тезис Черча-Тьюринга тут где-то рядом.

                                                                                                0
                                                                                                ИМХО за деревьями не видно леса. Для вызова функции нужно пропихнуть что-то в стек, а на возврате выпихнуть — переменные в неявном виде. Выше Вы справедливо отметили:
                                                                                                Сначала нужно будет строго определить понятие переменной.
                                                                                                  0

                                                                                                  А тут функции нет. И вызова её нет. И стека тоже, в общем, нет.


                                                                                                  Эту всю ерунду проще рассматривать на fibs из примера выше. В общем, там нет функций, тип fibs — непосредственно список интов. Сам fibs на самом деле рецепт по вычислению fibs, который, конечно, где-то в глубине компилируется во вполне мутабельный код, но это деталь реализации, нас не сильно интересующая. Переменных в этом коде нет в том смысле, в котором нет изменения значения.

                                                                                                    0
                                                                                                    который, конечно, где-то в глубине компилируется во вполне мутабельный код, но это деталь реализации, нас не сильно интересующая
                                                                                                    В данном случае интересующая: если деталь скрытая — то не значит, что ее нет. Посмотреть ассемблер — будут там переменные, изменения значения.
                                                                                                      0

                                                                                                      А вот тут в дело вступает то обстоятельство, что задача трансляции (компиляции) по природе своей функциональна. Объектный код полностью определяется исходным кодом и текущим окружением (входными параметрами). На этом стоит вся система сборки дистрибутивов типа configure >> make. Так что если абстракция функциональности и теряется на каком-то уровне, то это происходит всегда одинаково и решение можно, в конце концов, верифицировать, добившись герметичности абстракции на верхнем уровне. GHC это уже умеет. То есть, нас, действительно могут не сильно интересовать детали реализации, покуда компилятор не нарушает некоторых нужных нам законов и инвариантов.

                                                                                                        0
                                                                                                        Ok. Готов допустить, что компилятор не нарушает. Но при этом не понял, чем эта абстракция удобнее, нпр., абстракции ООП? Тут нужно какое-то отдельное обоснование, т.к. может быть абстракция наоборот затрудняющая работу с кодом.
                                                                                                          0

                                                                                                          Запросто! Это как в задаче интегрирования. Есть алгебраический подход, а есть геометрический, есть спектральный, а есть аналитический по теореме Коши, наконец, можно численно, но и там, можно Симпсоном, можно Гауссом. Когда как удобнее. Полезно владеть всем.

                                                                                                            0
                                                                                                            Когда как удобнее. Полезно владеть всем.
                                                                                                            Если я правильно понял, есть случаи, когда ФП удобнее ООП — можете привести пример?
                                                                                                            И наоборот: когда ООП удобнее ФП — а пример такого случая?
                                                                                                            +1

                                                                                                            А она не удобнее, они вообще ортогональны.


                                                                                                            Вполне можно строить ООП на иммутабельных данных (см. того же Пирса). И обратно, можно иметь чистый функциональный код без мутабельных переменных, который за счёт, например, линейных типов будет разворачиваться в императивный инплейс-код — см. язык Clean, ну или Idris:


                                                                                                            umap : (a -> b) -> UList a -> UList b
                                                                                                            umap f [] = []
                                                                                                            umap f (x :: xs) = f x :: umap f xs

                                                                                                            «In the second clause, xs is a value of a unique type, and only appears once on the right hand side, so this clause is valid. Not only that, since we know there can be no other reference to the UList a argument, we can reuse its space for building the result! The compiler is aware of this, and compiles this definition to an in-place update of the list.» (курсив наш)

                                                                                                          0
                                                                                                          Вы не сможете эту изменчивость наблюдать средствами, предоставляемыми языком. Дальше уже начинается философия, но, ИМХО, именно это и значит, что переменных в вашем языке нет. А что там на уровне ассемблера, микрокода или волновых функций — неважно.
                                                                                                            0
                                                                                                            ИМХО это как раз плохо, когда нет переменных. Что-то скрыть не самоцель, а цель облегчить понимание и отладку. Или м.б. вместо отладки на высоком уровне исходного кода лезть в объектный код? Выше я привел примеры, в которых нельзя применить ФП — это случайные значения переменной и события. Мы ушли в сторону, выясняя, что можно без переменных. Но исходный пункт остался: видимо есть задачи, которые решаются ООП, но не ФП.
                                                                                                              +2
                                                                                                              Что-то скрыть не самоцель, а цель облегчить понимание и отладку. Или м.б. вместо отладки на высоком уровне исходного кода лезть в объектный код?

                                                                                                              А почему отсутствие переменных отменяет отладку? :)


                                                                                                              Другое дело, что она действительно не очень нужна. Я вот прямо сейчас параллельно на другом рабочем столе читаю книгу Окасаки и делаю упражнения в нём, тут как раз параграф про красно-чёрные деревья. Я набросал своё дерево, набросал простенький предикат для проверки инварианта, что у красных нод нет красных детей


                                                                                                              data Tree a
                                                                                                                = Empty
                                                                                                                | Node
                                                                                                                  { color :: Color
                                                                                                                  , left :: Tree a
                                                                                                                  , elt :: a
                                                                                                                  , right :: Tree a
                                                                                                                  }
                                                                                                                deriving (Eq, Show)
                                                                                                              
                                                                                                              noRedRedPath :: Tree a -> Bool
                                                                                                              noRedRedPath Empty = True
                                                                                                              noRedRedPath n@Node { left, right } = case color n of
                                                                                                                B -> recCond
                                                                                                                R -> recCond
                                                                                                                  && maybeColor left /= Just R && maybeColor right /= Just R
                                                                                                                where
                                                                                                                  maybeColor Node { color } = Just color
                                                                                                                  maybeColor Empty = Nothing
                                                                                                                  recCond = noRedRedPath left && noRedRedPath right

                                                                                                              и тест для него


                                                                                                                describe "RB trees general properties" $ do
                                                                                                                  ...
                                                                                                                  it "does not have red-red path" $  property $ \(lst :: [Int]) -> RB.noRedRedPath (foldr RB.insert RB.Empty lst)

                                                                                                              Quickcheck мне сказал входные данные, на которых валится тест:



                                                                                                              Мне больше не нужно ничего дебажить. Мне нужно вдумчиво смотреть на insert и balance, чтобы попытаться понять, какой случай я упустил. Зачем мне бегать дебаггером, какую новую информацию он мне даст?


                                                                                                              Выше я привел примеры, в которых нельзя применить ФП — это случайные значения переменной и события.

                                                                                                              Э, ну можно же. Модификация состояния (в том числе состояния ГПСЧ) — это эффект, а эффект моделируется монадой.

                                                                                                                0
                                                                                                                Мне нужно вдумчиво смотреть на insert и balance, чтобы попытаться понять, какой случай я упустил. Зачем мне бегать дебаггером, какую новую информацию он мне даст?
                                                                                                                Это уже не теория, а практика. Действительно в простых учебных задачах бывает достаточно просто хорошо подумать над результатами тестов. Но для более сложных отладчики себя зарекомендовали. Факт, что чем больше всяких возможностей для отладки — тем лучше. Дело не только в том чтобы найти баг, а чтобы найти его достаточно быстро.
                                                                                                                Э, ну можно же. Модификация состояния (в том числе состояния ГПСЧ) — это эффект, а эффект моделируется монадой.
                                                                                                                я не спорю: многое возможно. Но люди склонны совершать ошибки. Одна из типовых ошибок — непредсказуемое поведение функции.
                                                                                                                  0
                                                                                                                  Но для более сложных отладчики себя зарекомендовали. Факт, что чем больше всяких возможностей для отладки — тем лучше. Дело не только в том чтобы найти баг, а чтобы найти его достаточно быстро.

                                                                                                                  Компилятор для DSL — достаточно крупный проект?


                                                                                                                  Там подход с разбитием на мелкие тесты для разных юзкейсов и отладку через этакую дифференциальную диагностику ну просто отличнейше себя зарекомендовал. В моём опыте, по крайней мере. Отладчик ни разу не захотелось брать в руки.


                                                                                                                  Одна из типовых ошибок — непредсказуемое поведение функции.

                                                                                                                  И чистота системы типов отлично от этого защищает.

                                                                                                                    0
                                                                                                                    Компилятор для DSL — достаточно крупный проект?
                                                                                                                    Наверняка крупный, но у каждого проекта своя специфика. Для другого может не подойти.
                                                                                                                    И чистота системы типов отлично от этого защищает.
                                                                                                                    Как защищает в случае неинициализированных переменных?
                                                                                                                      0
                                                                                                                      Наверняка крупный, но у каждого проекта своя специфика. Для другого может не подойти.

                                                                                                                      Ну, у меня пока что такого опыта не было.


                                                                                                                      Как защищает в случае неинициализированных переменных?

                                                                                                                      Что-то я запутался. Мы о случайных величинах или об этом?

                                                                                                                        –1
                                                                                                                        Мы о случайных величинах или об этом?
                                                                                                                        В примере в качестве случайной величины я предложил использовать неинициализированную переменную. На практике кто-то может ее использовать и по ошибке. Как защититься от такой ошибки?
                                                                                                                          0
                                                                                                                          В примере в качестве случайной величины я предложил использовать неинициализированную переменную.

                                                                                                                          В каком языке? В C++ (да и в С, насколько я знаю) это UB, например, так что ваше предложение я, пожалуй, отвергну.


                                                                                                                          А значит, все использования неинициализированных переменных ошибочны, и, как я понимаю, вопрос снимается сам собой (на самом деле это не так, и ошибочны не все, но играть в C++ language lawyer'а мне не хочется, это занудно и не очень важно для данной дискуссии).

                                                                                                                            0
                                                                                                                            В каком языке?
                                                                                                                            ОО Паскаль (Дельфи-7).
                                                                                                                              +1

                                                                                                                              Там что, разрешают читать из неинициализированных переменных и выбирать на основе этого бранчи? И значение этой переменной действительно не определено?

                                                                                                                                0
                                                                                                                                Да. Можем взять другой ЯП — ассемблер)
                                                                                                                                  0
                                                                                                                                  Ну, в хаскеле или идрисе тоже можно FFI в сишечку взять и наворотить.
                                                                                                                        0

                                                                                                                        Мы же только что убедились, что в чистых функциональных языках переменных вообще нет — следовательно неинициализированных переменных быть не может :)

                                                                                                                          0
                                                                                                                          Тут путаница. Я понял, что глобальные переменные в ФП запрещены. А локальные? Могу в функции определить и использовать переменную? Аргументы функции — переменные? Результат — переменная?
                                                                                                                          • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                              0
                                                                                                                              Вы понимаете разницу между переменной и параметром?
                                                                                                                              Понимаю. В Паскале, нпр.:
                                                                                                                              function sinFi (fi :real) :real;
                                                                                                                              begin
                                                                                                                               Result := sin(fi);
                                                                                                                              end;
                                                                                                                              

                                                                                                                              Могу вызвать из другой функции:
                                                                                                                              function f2 :real;
                                                                                                                              begin
                                                                                                                               Result := sinFi(pi/2);
                                                                                                                              end;
                                                                                                                              

                                                                                                                              И так:
                                                                                                                              function f2(fi :real)  :real;
                                                                                                                              var
                                                                                                                               temp: real; // локальная переменная
                                                                                                                              begin
                                                                                                                               temp := sinFi(fi);
                                                                                                                               if temp>0.5 then
                                                                                                                               Result := temp*2
                                                                                                                              else
                                                                                                                               Result := temp*3;
                                                                                                                              end;
                                                                                                                              

                                                                                                                              Можно такое в рамках ФП. Или, чтобы избежать переменной, я должен сделать:
                                                                                                                              function f2(fi :real)  :real;
                                                                                                                              begin
                                                                                                                               if sinFi(fi)>0.5 then
                                                                                                                               Result := sinFi(fi)*2
                                                                                                                              else
                                                                                                                               Result := sinFi(fi)*3;
                                                                                                                              end;
                                                                                                                              

                                                                                                                              Result — переменная?
                                                                                                                                0

                                                                                                                                Функциональщик бы написал что-то вроде


                                                                                                                                f2 fi | sin fi > 0.5 = sin fi * 2
                                                                                                                                      | otherwise = sin fi * 3

                                                                                                                                или


                                                                                                                                f2 fi | s > 0.5 = s * 2
                                                                                                                                      | otherwise = s * 3
                                                                                                                                  where s = sin fi

                                                                                                                                или


                                                                                                                                f2 fi = s * if s > 0.5 then 2 else 3
                                                                                                                                  where s = sin fi

                                                                                                                                s особо не отличается от вашего temp.

                                                                                                                                  0
                                                                                                                                  s, как и мой temp — переменная? Значит переменные допустимы в ФП? Сколько раз вызывается sinFi в каждом примере?
                                                                                                                                    0
                                                                                                                                    Нет, не переменная, она ж не меняется.

                                                                                                                                    Сколько раз — зависит. Я бы ожидал, что с оптимизациями компилятор первые два варианта свернет в третий, во всех случаях давая вам один вызов.
                                                                                                                                      0
                                                                                                                                      Нет, не переменная, она ж не меняется.
                                                                                                                                      Как не меняется? Я так понял, что до выполнения оператора
                                                                                                                                      where s = sin fi

                                                                                                                                      s не определена, а после равна значению синуса аргумента fi.
                                                                                                                                        0
                                                                                                                                        Это не оператор, это уравнение, типа, видишь слово s — подставь определение из правой части.
                                                                                                                                          0
                                                                                                                                          видишь слово s — подставь определение из правой части.
                                                                                                                                          «подставь» — это команда (что в программировании называется оператором). Для ее выполнения, надо не только подставить значение синуса, но и вычислить его сначала. Или тут только подстановка, как в препроцессорах? Но тогда синус будет вычислятся 2 раза, а не один.
                                                                                                                                            0
                                                                                                                                            «подставь» — это команда (что в программировании называется оператором)

                                                                                                                                            Нет, это не команда для компьютера, это одна из возможностей интерпретации подобной записи. Впрочем, то, что написал Sirikid рядом, ещё лучше и ближе к тому, как оно на самом деле работает.


                                                                                                                                            А дальше играет роль стратегия вычислений.


                                                                                                                                            В хаскеле нестрогие вычисления, поэтому на самом деле в обе точки использования s будет подставлена ссылка на соответствующий thunk — что-то вроде микрофункции, его вычисляющей, которая при первом вычислении заменит себя на вычисленное значение (этакая мемоизация).


                                                                                                                                            Поэтому, например, в коде типа


                                                                                                                                            f2 phi | phi < 0.1 = 0
                                                                                                                                                   | otherwise = s * if s < 0.5 then 2 else 3
                                                                                                                                              where s = sin phi

                                                                                                                                            s будет вычислена от нуля до одного раза.


                                                                                                                                            Идрис, с другой стороны, строгий язык. Там все байндинги будут вычисляться сразу, но состояния неинициализированности у них тоже не будет — у вас просто синтаксически не получится обратиться к соответствующим байндингам, пока они не будут вычислены.

                                                                                                                                              0
                                                                                                                                              Т.е. переменные заменяются мемоизацией. Насколько это эффективно в плане времени исполнения? В сложных случаях можно опасаться, что компилятор не так поймет? И если не так, то сложно ли отловить такой баг?
                                                                                                                                                +1
                                                                                                                                                Т.е. переменные заменяются мемоизацией.

                                                                                                                                                При нестрогой стратегии вычислений. И не то что заменяются, просто это один из вариантов реализации байндингов.


                                                                                                                                                Насколько это эффективно в плане времени исполнения?

                                                                                                                                                Зависит. Матричные числодробилки так писать не надо (а надо взять, скажем, repa), а в иных случаях это может быть даже эффективнее — за счёт ленивости ненужные части не вычисляются (что, кстати, ещё и полезно для композабельности).


                                                                                                                                                В сложных случаях можно опасаться, что компилятор не так поймет?

                                                                                                                                                В третьем варианте трансляции вашего примера компилятору нечего не понимать (с точностью до багов в компиляторе, но это в любом языке может быть).


                                                                                                                                                В предыдущих вариантах есть расчёт на то, что компилятор поймёт, что sin phi вычисляется во всех ветках, поэтому он имеет право в сгенерированном коде вычислить sin phi один раз на входе в функцию, сделать код строгим и не генерировать никаких thunk'ов. Ну, то есть, типичный common subexpression elimination, несколько осложнённый тем фактом, что надо сохранять семантику программы с точки зрения ленивости (и именно программы — если функция f2 из моего предыдущего комментария везде инлайнится, и компилятор видит, что phi везде >= 0.1, то он имеет право снова добавить строгости и сразу вычислять sin phi на входе в функцию).

                                                                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                        0
                                                                                                                        Но для более сложных отладчики себя зарекомендовали.
                                                                                                                        У них очень узкая ниша, на самом деле. В Гугле, например, сняли разработчиков с GDB, когда выяснилось, что им пользуется ежедневно, в среднем, менее 5% разработчиков.

                                                                                                                        Вряд ли разработку google.com можно назвать «маленькой учебной задачей».
                                                                                                                          0
                                                                                                                          Вряд ли разработку google.com можно назвать «маленькой учебной задачей».
                                                                                                                          Нет, но как сказал выше:
                                                                                                                          у каждого проекта своя специфика
                                                                                                            0
                                                                                                            В подавляющем большинстве случаев (вроде есть какие-то лисп-процессоры функциональные) среда исполнения императивна. Императивные языки, да, сахар, но над императивными машкодами.
                                                                                                              0

                                                                                                              Это не решето Эратосфена. Тут наивный метод перебора всех чисел и проверки делимости на уже найденные простые числа. Даже после переиспользования erato вместо списка всех меньших чисел.


                                                                                                              Для поиска всех простых чисел до n этот алгоритм будет работать O(n^2 / log n). Может, если там соптимизированно "all /= 0" и не проверяет после первого несовпадения, тогда можно еще на log n поделить. Когда как честное решето эратосфена будет O(n log log n), что намного эффективнее.


                                                                                                              Да, наивному решету надо в log n раз больше памяти, но это лечится если ввести сегментацию — тогда оно будет занимать ассимптотически столько же памяти, что и ваш алгоритм. А если надо хранить не все простые, а, скажем, найти k-ое, то сегментированное решето потребует гораздо меньше памяти.

                                                                                                                0
                                                                                                                Да, наивному решету надо в log n раз больше памяти, но это лечится если ввести сегментацию — тогда оно будет занимать ассимптотически столько же памяти, что и ваш алгоритм. А если надо хранить не все простые
                                                                                                                Т.е. что-то надо хранить. Хранят в переменных (явных или неявных), но при этом постоянно говорят, что
                                                                                                                в чистых функциональных языках переменных вообще нет

                                                                                                                Так есть или нет? ИМХО если что-то хранить, то хранится в переменной. А иначе напоминает двоемыслие.
                                                                                                                  0

                                                                                                                  Просто эти переменные все с модификатором const и как бы неявные — в виде параметров у функций. Вызвали функцию — создали переменные.


                                                                                                                  Хотите к счетчику что-то прибавить — вызывайте рекурсивно функцию с +1 в параметре.


                                                                                                                  С одной стороны это создает кучу сложностей и ограничений. С другой убирает сайд-эффекты.

                                                                                                                    0
                                                                                                                    С одной стороны это создает кучу сложностей и ограничений. С другой убирает сайд-эффекты.
                                                                                                                    ИМХО в процедурном программировании сайд-эффекты убираются простыми ограничениями на глобальные переменные. Там это вопрос стиля. В ООП у каждого класса есть свойства и переменные, которые видны всем методам класса. Можно сказть, что там сайд-эффекты сознательно допустимы внутри класса и его потомков. И это бывает удобно. В ООП возможен плохой стиль, но ИМХО это не причина абстрактного ужаса перед сайд-эффектами. Не слишком ли их боятся?
                                                                                                                      0
                                                                                                                      У меня слишком много травматического опыта с отладкой императивных ООП-приложений, чтобы таки бояться.
                                                                                                                        0
                                                                                                                        А ФП — серебряная пуля?
                                                                                                                          0

                                                                                                                          Нет, но травматического опыта у меня с ним сильно меньше.

                                                                                                                            0
                                                                                                                            Подобный травматический опыт может зависеть от многих причин, поэтому высока вероятность ошибочных выводов на основе такого опыта.
                                                                                                                        +3

                                                                                                                        Мне импонирует ваше стремление разобраться! Переменное состояние и сайд-эффекты в ФП исключены вовсе не ради инкапсуляции, вернее не только ради неё. Если мы готовы принять это ограничение, то становятся возможными:


                                                                                                                        • Однозначный вывод типов по Хиндли-Милнеру, существенно более полезный, чем var или auto, поскольку он проникает на все уровни программы от сигнатуры функции до самых мелких её деталей. И это не для экономии нажатий клавиш при определении функции, а для настоящей и осознанной типобезопасности. Компилятор в чистых типизированных ФЯП не тестировщик и не надзиратель, а друг и помощник, подсказывающий и объясняющий программисту даже не в чём состоит ошибка, а что ему писать дальше. Это не автодополнение IDE доступных полей и методов, а подсказка сложных и очень нетривиальных решений, которые потом могут превратиться в научные разработки. Это круто и от этого уже трудно отказаться!
                                                                                                                        • "Типо-ориентированное программирование", несколько более широкое, чем data-driven design, поскольку на первый план выступают алгебраические свойства типов (и функций над ними), не нарушаемые изменением состояния.
                                                                                                                        • Внятная и доказуемая денотационная семантика, equational reasoning, настоящее unit-тестирование с автогенерацией тестов и property-based тестированием (Quickcheck появился в Haskell и только потом разошёлся по языкам).
                                                                                                                        • Выбор стратегии вычислений (строгая/ленивая), в чистом ФП не меняющая результат, а влияющая лишь на эффективность программы и на способы её декомпозиции (в ленивом Haskell декомпозиция вкусна до безобразия, одни только гиломормизмы и fusion чего стоят!).
                                                                                                                        • Принципиальное отсутствие в многопоточности гонок, и проблем с общими ресурсами.
                                                                                                                        • Наконец, осознанная свобода в выборе и конструировании семантики позволяет легко (правда, легко, монады не сложнее какого-нибуть преобразования Фурье или Лапласа, хоть и "ломают" по началу мозг) эмулировать и переменное состояние и эффекты, но со всеми перечисленными выше плюшками!
                                                                                                                          Отсутствие сайд-эффектов и переменных не цель ФП, а средство достижения гораздо больших целей. И, более того, если надо, я всегда могу их себе завести, но они гарантированно будут локальными и с тонко настраиваемой семантикой.
                                                                                                                          +1
                                                                                                                          Мне импонирует ваше стремление разобраться!
                                                                                                                          Спасибо Вам и всем, кто помогает мне разобраться! :)

                                                                                                                          Со своей стороны, в первую очередь хочу отметить, что мне импонирует дружелюбная атмосфера, сложившаяся в данном обсуждении. До этой статьи я периодически читал про ФП, у меня постепенно накапливались недоуменные вопросы, которые откладывал «на потом». И вот этот «потом» настал, и за пару дней узнал больше, чем раньше за гораздо более длительный срок. Поэтому надеюсь, что и в дальнейшем обсуждении сообщество проявит терпение, отвечая на дальнейшие, может, не самые удобные вопросы — у меня их еще много)

                                                                                                                          Пользуясь случаем, предложу идею, м.б. кого заинтересует: тут много наговорили, отвечая на вопросы чайника в ФП (т.е. меня). Предполагаю, что я не оригинален, и что у других ФП-чайников есть похожие вопросы, но не все они будут читать это объемное обсуждение. Может, кто из экспертов-знатоков ФП переформатирует это обсуждение в FAQ и опубликует в виде статьи на Хабре? Уверен, что такая публикация будет очень актуальна.

                                                                                                                          Хотя в данный момент я далек от того, чтобы перейти на ФП, но вижу, что здесь очень интересная философия и практика, есть над чем подумать. В любом случае любому программисту очень полезно ознакомиться с общими принципами для расширения кругозора. Думаю, что если и не перейду на ФП, это довольно мимолетное знакомство повлияет на мой стиль написания программ.

                                                                                                                          Теперь позвольте задать очередную порцию вопросов.
                                                                                                                          для настоящей и осознанной типобезопасности
                                                                                                                          Не понимаю, как вывод типов повышает типобезопасность. В вики читаю:
                                                                                                                          опустить тип идентификатора в определении с инициализацией (см. синтаксический сахар). Например:

                                                                                                                          var s = «Hello, world!»; // Тип переменной s (от string) выведен из инициализатора
                                                                                                                          ИМХО действительно сахар.
                                                                                                                          Это не автодополнение IDE доступных полей и методов, а подсказка сложных и очень нетривиальных решений, которые потом могут превратиться в научные разработки.
                                                                                                                          Это не преувеличение? Как это можно превратить в научную разработку? Есть пример?
                                                                                                                          «Типо-ориентированное программирование»
                                                                                                                          Не нашел в гугле и вики внятных определений. Можно пояснение и ссылку?
                                                                                                                          Принципиальное отсутствие в многопоточности гонок, и проблем с общими ресурсами
                                                                                                                          За счет чего отсутствие?

                                                                                                                            +1

                                                                                                                            Спасибо, это, действительно, многовато для комментария. Пройдёмся по вашим вопросам.


                                                                                                                            • Вывод типов в ФП распространяется не только на объявление параметров/констант, но и на типы всех выражений и функций. И работает он в "обе стороны", то есть, я могу явно написать тип определяемой функции, а потом спросить у компилятора каким должен быть тип того или иного (любого) подвыражения в её теле, используя т.н. дырки, (holes). Это лучше показать, но не в комментарии. С другой стороны, я могу написать тело функции, не указывая вообще ни одного типа, и компилятор постарается вывести самый общий полиморфный тип для неё (в статике, на этапе компиляции). Если не выйдет, он скажет что именно ему не понятно, и это будет либо моя ошибка, либо неоднозначность задачи, требующая явного сужения типа, что тоже полезно и открывает глаза на программу. Особенно приятно общаться с компиляторами PureScript или Elm, но и ghc в последние годы становится более дружелюбным (или это я учусь понимать его?). А вот работа с литералами-константами (из примера с var), как раз часто требует уточнения, поскольку в Haskell выражение 5 может означать либо целое число, либо число с плавающей точкой, либо, вообще, какой-нибудь тип-обертку типа Sum или Max. Компилятор очень постарается понять из контекста, что же это такое, но программист может его здорово запутать :)
                                                                                                                            • Я не преувеличил роль вывода типов в ФП в серьёзных исследованиях. Многие наши замечательные современники — асы ФП, создавшие целые концепции, вроде линз, кондуитов, или свободных монад, активно используют интерпретатор GHCi, как основной инструмент, получая от него ответы на вопросы (скажем, какой функтор нужно подставить в линзу, чтобы превратить его в геттер или сеттер) и целые доказательства (см. изоморфизм Карри-Ховарда) для своих идей, о чём с удовольствием рассказывают на конференциях и в блогах.
                                                                                                                            • Я нарочно взял словосочетание «типо-ориентированное программирование» в кавычки, это не официальный термин. Типы в ФП (типизированном) это нечто большее чем "множество допустимых значений, внутреннее представление данных и возможные операции над ними". Это основа дизайна программ, предоставляющая связи между типами и законы (в математическом смысле, а не в инженерном) им присущие. Типы параметризуют друг друга и сами образуют более общую структуру Kinds, всё это выводит работу с ними на уровень настоящего исчисления. Иногда это чертовски сложно и нетривиально, иногда чертовски красиво, но вот что для меня привлекательно: тут остаётся мало места традициям, моде и вкусовщине, присущим нашему делу. Вместо них теоремы, анализ и строгие выводы, которые можно использовать, спустя десятилетия и они не устаревают, а со временем получают развитие, как, например получилось с линейными типами.
                                                                                                                            • На последний вопрос отвечу аккуратно: отсутствие изменяемого состояния (концептуальное) заставляет писать код, в котором проблем с параллелизмом и конкурированием существенно меньше. Я не стану утверждать рекламным голосом, что в рамках ФП параллелизм станет лёгким и приятным как никогда, и теперь с этим справится даже ваша мама. Сложности всё равно остаются, но они, скажем так, иного уровня, поприятнее, что-ли.
                                                                                                                              0
                                                                                                                              Когда-то виртовский Паскаль и первые стандарты языка критиковали за то, что невозможно написать функцию умножения двух матриц в общем виде. Матрицы 5х5 — один тип, 6х6 — уже другой тип. Турбо Паскаль 3 и выше, и другие компиляторы имели расширения для обхода этой проблемы. Правда расширения не всегда удобные. Как в ФП решают эту проблему?
                                                                                                                              Это основа дизайна программ, предоставляющая связи между типами и законы (в математическом смысле, а не в инженерном) им присущие.
                                                                                                                              Не все матрицы можно умножать — размеры должны соответствовать. Можно в ФП задать такое правило на уровне типов?
                                                                                                                                0
                                                                                                                                Не все матрицы можно умножать — размеры должны соответствовать. Можно в ФП задать такое правило на уровне типов?

                                                                                                                                конечно можно (простейший пример)
                                                                                                                                  0

                                                                                                                                  Хаскель не лучший язык, чтобы на нём демонстрировать завтипы.


                                                                                                                                  Лучше


                                                                                                                                  multiply : { n, m, k : Nat} -> Mat a n m -> Mat a m k -> Mat a n k

                                                                                                                                  будет типом искомой функции. Можно обратить внимание, что обычные натуральные числа из уровня термов вполне себе работают на уровне типов.


                                                                                                                                  И ещё очень важно, что n, m, k могут быть и неизвестны до этапа исполнения (в отличие от, скажем, сиплюсплюсных шаблонов).

                                                                                                                                  0

                                                                                                                                  Зависит от ФП. В классическом хаскеле — увы, нет, его система типов для этого слишком сложна. В современном, реализованном в ghc — да, можно, но довольно уродливо. Лучше сразу брать языки типа Agda или Idris. Я там чуть ниже пример привёл.

                                                                                                                                +1
                                                                                                                                Не нашел в гугле и вики внятных определений. Можно пояснение и ссылку?

                                                                                                                                Можно почитать, например, Type-driven development with Idris.


                                                                                                                                Как пример для затравки и этакого экстремального случая — чтобы написать функцию для применения данной функции к каждому элементу вектора, вам достаточно написать сигнатуру функции типа myfmap : (a -> b) -> Vect n a -> Vect n b, чтобы потом тайпчекер с небольшой вашей помощью реализовал за вас её тело за 4 команды:


                                                                                                                                1. Generate definition. Тайпчекер за вас пишет черновик тела функции:
                                                                                                                                  myfmap : (a -> b) -> Vect n a -> Vect n b
                                                                                                                                  myfmap f xs = ?myfmap_rhs
                                                                                                                                2. Вектор — индуктивная структура данных, поэтому разумно воспользоваться разбором случаев по структуре вектора. Наводим курсор на xs, в редакторе выполняем команду case split, тайпчекер за нас пишет
                                                                                                                                  myfmap : (a -> b) -> Vect n a -> Vect n b
                                                                                                                                  myfmap f [] = ?myfmap_rhs_1
                                                                                                                                  myfmap f (x :: xs) = ?myfmap_rhs_2
                                                                                                                                3. Теперь рассмотрим каждый из случаев. Они довольно простые, поэтому тайпчекер может найти правильный терм справа от знака равно для каждого из случаев. Наводим на ?myfmap_rhs_1 и даём команду obvious proof search. Получаем
                                                                                                                                  myfmap : (a -> b) -> Vect n a -> Vect n b
                                                                                                                                  myfmap f [] = []
                                                                                                                                  myfmap f (x :: xs) = ?myfmap_rhs_2
                                                                                                                                4. Повторяем со второй веткой. Получаем
                                                                                                                                  myfmap : (a -> b) -> Vect n a -> Vect n b
                                                                                                                                  myfmap f [] = []
                                                                                                                                  myfmap f (x :: xs) = f x :: myfmap f xs

                                                                                                                                За счет чего отсутствие?

                                                                                                                                За счёт примитивов типа того же STM и проверок компилятором, что вы не делаете того, что не нужно делать.

                                                                                                                                  0
                                                                                                                                  Можно пояснение и ссылку?
                                                                                                                                  pragprog.com/book/swdddf/domain-modeling-made-functional и несколько более хардкорное www.manning.com/books/type-driven-development-with-idris
                                                                                                                                0
                                                                                                                                Я бы сказал, что в ООП сайд-эффекты не просто допустимы, а под них оно и было создано: только в вырожденных случаях типа DTO у методов класса нет сайд-эффектов, в остальных они должны быть. Но эти сайд-эффекты должны быть ограничены объектом в общем случае или заключаться в вызовах методов зависимостей.
                                                                                                                            0

                                                                                                                            Да, в однострочник с ленивостью и узлом полноценное решето у меня засунуть не получилось. Я что-то тупанул и думал, что переиспользование erato даст ту же сложность, но да, вы очевидно правы, спасибо, что поправили!


                                                                                                                            Тогда придётся делать рекурсивную функцию, которая берёт какой-нибудь Data.Array или тупо список (хотя тут чуть сложнее анализировать сложность в ленивом контексте) и из него что-нибудь вычёркивает. Но, в любом случае, снова никаких переменных.

                                                                                                                              +1
                                                                                                                              Тогда придётся делать рекурсивную функцию, которая берёт какой-нибудь Data.Array или тупо список (хотя тут чуть сложнее анализировать сложность в ленивом контексте) и из него что-нибудь вычёркивает.
                                                                                                                              Но, в любом случае, снова никаких переменных.

                                                                                                                              Ох и сомневаюсь я что тут что-то вообще хоть сколько-нибудь читаемое получится.


                                                                                                                              Вот в чем проблема-то, решето — по природе своей изменение массива по заданному правилу. Любая его реализация в чистом ФП будет костылем и эмулированием всех переменных и циклов, но через функции.


                                                                                                                              Как я уже писал, представьте что у вас все переменные const, и при изменении просто передавайте новые значения как параметры функции. Это и есть подход ФП.


                                                                                                                              Формально — никаких переменных и сайд эффектов. На практике код будет таким сложным, что это просто выдумывание себе проблем на ровном месте.


                                                                                                                              Для многих задач в этой парадигме можно сделать очень простой и понятный код. Для других задач чистое ФП все-таки не так хорошо подходит.

                                                                                                                                0
                                                                                                                                Для многих задач в этой парадигме можно сделать очень простой и понятный код. Для других задач чистое ФП все-таки не так хорошо подходит.
                                                                                                                                Спасибо. Что-то подобное я и ожидал услышать!
                                                                                                                                  0
                                                                                                                                  Ох и сомневаюсь я что тут что-то вообще хоть сколько-нибудь читаемое получится.

                                                                                                                                  Ну почему.


                                                                                                                                  erato = go [2..]
                                                                                                                                    where
                                                                                                                                      go (x:xs) = x : go (filter ((/= 0) . (`mod` x)) xs)

                                                                                                                                  Правда, я очень не люблю анализ сложности в подобных случаях (ленивость всё портит, а тупой переход к строгости даёт слишком плохую оценку сверху), но, по идее, это как раз эквивалентно последовательному вычеркиванию элементов.


                                                                                                                                  Получили, кстати, бесконечное решето.


                                                                                                                                  *Erato> take 10 erato
                                                                                                                                  [2,3,5,7,11,13,17,19,23,29]
                                                                                                                                  *Erato> take 100 erato
                                                                                                                                  [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]

                                                                                                                                  Реквестирую императивное бесконечное решето.

                                                                                                                                    0

                                                                                                                                    Но это опять не решето! Мне кажется, тут опять каждое число проверяется на делимость всеми предыдущими простыми. Это слабо отличается от изначального вашего алгоритма.


                                                                                                                                    Вы тут просто по определению делаете — списко всех чисел, которые не делятся ни на одно предыдещее число из списка.


                                                                                                                                    Суть решета же в том, что вы вычеркиваете только те числа, которые точно делятся на число x, делая прыжки +x по массиву, не проверяя делимость вообще.


                                                                                                                                    Реквестирую императивное бесконечное решето.

                                                                                                                                    Этот же метод (не решето!) в императиве также бесконечно очень просто делается. Да, тут ФП решение покороче будет. На задчах, где ФП действительно применимо, оно часто позволяет делать сильно более короткие решения. P.s. решето, к таким, по всей видимости, не относится.


                                                                                                                                    C++
                                                                                                                                    vector <int> ans;
                                                                                                                                    size_t i = 2;
                                                                                                                                    while (ans.size() < N) {
                                                                                                                                      bool prime = true;
                                                                                                                                      for (auto& p : ans) {
                                                                                                                                        if (i % p == 0) { 
                                                                                                                                          prime = false;
                                                                                                                                          break;
                                                                                                                                        }
                                                                                                                                      }
                                                                                                                                      if (prime)
                                                                                                                                        ans.push_back(i);
                                                                                                                                      ++i;
                                                                                                                                    }
                                                                                                                                      0
                                                                                                                                      Мне кажется, тут опять каждое число проверяется на делимость всеми предыдущими простыми. Это слабо отличается от изначального вашего алгоритма.

                                                                                                                                      Да, у меня не получилось изящно использовать erato в том варианте, этот ближе к тому, пожалуй.


                                                                                                                                      Суть решета же в том, что вы вычеркиваете только те числа, которые точно делятся на число x, делая прыжки +x по массиву, не проверяя делимость вообще.

                                                                                                                                      Когда вы говорите о сложности log log n, то что вы считаете за операцию? Проверку на делимость или вообще обращение к контейнеру?

                                                                                                                                        0
                                                                                                                                        Когда вы говорите о сложности log log n, то что вы считаете за операцию? Проверку на делимость или вообще обращение к контейнеру?

                                                                                                                                        За операцию считаются:


                                                                                                                                        • обращение к массиву.
                                                                                                                                        • арифметические операции (+, -, *, деления тут вообще нет).
                                                                                                                                        • проверка условия, условные/безусловные переходы.

                                                                                                                                        Грубо говоря, ассемблерные операции.


                                                                                                                                        Там log log n вылезает потому что n/2 + n/3 + n/5 + n/7 +… сходится к n log log n. Мы ведь сначала вычеркиваем каждое второе число (пишем false по индексу, прибавляем к индексу смещение, проверяем на конец массива). Потом каждое 3-е число, и т.д. Отдельно вылезает слагаемое +n, потому что надо каждый элемент во внешнем цикле проверить, и если число простое выписать его в ответ и запустить вычеркивание.

                                                                                                                                          +1

                                                                                                                                          А, ну, значит, на списках совсем никак. Пойду дальше пытаться позориться, на этот раз с действительно с массивами какими-нибудь.

                                                                                                                                            0

                                                                                                                                            Окей, как насчёт


                                                                                                                                            import qualified Data.IntSet as IS
                                                                                                                                            
                                                                                                                                            erato2 :: Int -> [Int]
                                                                                                                                            erato2 n = go $ IS.fromDistinctAscList [2..n]
                                                                                                                                              where
                                                                                                                                                go set | IS.null set = []
                                                                                                                                                       | let x = IS.findMin set = x : go (foldr IS.delete set [x, 2 * x .. n])

                                                                                                                                            IS.findMin константно для достаточно больших множеств, IS.delete тоже.

                                                                                                                                              0

                                                                                                                                              Не верю, как delete может быть константным. Если он лениво выполняется, то надо считать с ленивостью.


                                                                                                                                              Это уже больше похоже на решето, но я не могу разобраться в этом коде, ибо этот синтаксис мне чужд. Оно работает вообще? Можете его позапускать на больших n и подсчитать время работы? Хотя бы для n=100, 1000, 10000, 100000, 1000000 и посмотреть с какой скоростью оно растет?


                                                                                                                                              У меня такие подозрения, что ленивость delete тут всю суть поломает, ибо ему придется все предыдущие удаленные списки проверить на каждом элементе, что равносильно, опять же, проверке на делимость каждого числа всем предыдущими.

                                                                                                                                                0
                                                                                                                                                Не верю, как delete может быть константным. Если он лениво выполняется, то надо считать с ленивостью.

                                                                                                                                                Я сам не понимаю, как, но это не ленивость. С ленивостью всё за O(1) работает :)


                                                                                                                                                «Many operations have a worst-case complexity of O(min(n,W)). This means that the operation can become linear in the number of elements with a maximum of W — the number of bits in an Int (32 or 64).»


                                                                                                                                                См. доки, там и ссылки на папиры с описанием структуры данных есть. Я их не читал, правда.


                                                                                                                                                Оно работает вообще?

                                                                                                                                                Работает, для n = 1000 я даже ручками посмотрел и сравнил с прошлой версией:


                                                                                                                                                *Erato> and $ zipWith (==) erato (erato2 1000)
                                                                                                                                                True

                                                                                                                                                У меня такие подозрения, что ленивость delete тут всю суть поломает, ибо ему придется все предыдущие удаленные списки проверить на каждом элементе, что равносильно, опять же, проверке на делимость каждого числа всем предыдущими.

                                                                                                                                                А зачем все?


                                                                                                                                                В любом случае, окей, попробую ssh'нуться на полноценную машину и наваять там бенчмарк.

                                                                                                                                                  0

                                                                                                                                                  Побенчмаркал. И исходное erato, и последнее выглядят почти линейно, но константа у исходного существенно лучше.

                                                                                                                                                    0

                                                                                                                                                    Исходное erato ну никаким образом не может быть n log log n. До каких n вы его гоняли? Можно данные в студию?

                                                                                                                                                      0
                                                                                                                                                      До миллиона erato, до сотни тысяч вариант с IntSet. За данные мне стыдно, IntSet сливает подчистую на два-три порядка.
                                                                                                                                                        0

                                                                                                                                                        Дайте угадаю, до 10^6 erato у вас работает пару секунд? У меня сишное решето до миллиона срабатывает мгновенно. Для 10^9 меньше 10 секунд.


                                                                                                                                                        Чтобы было что сравнивать, подсчитайте сумму всех простых чисел до n включительно. Для 10^9 ответ 24739512092254535. Если ваше erato сработает хотя бы за минуту, я буду очень-очень-очень удивлен и признаю, что это действительно решето.

                                                                                                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                                                            0

                                                                                                                                                            И эта самая ассимптотика — o(N^2 / log^2 N).
                                                                                                                                                            Для малых N оно слабо отличается от правильного n log log n. Но для уже 10^6 вы результата будете ждать дольше, для 10^9 вы его не дождетесь.


                                                                                                                                                            Я прошу запустить наконец это решение чтобы наглядно доказать, что там не n log log n.

                                                                                                                                                      0
                                                                                                                                                      Побенчмаркал.
                                                                                                                                                      Бенчмаркать тут довольно бессмысленно. log₂ log₂ 1000000000 — это в районе 5, а log₂ 1000000000 — это в районе 30, так что на любых вменяемых объёмах вы log₂ log₂ N от log₂ N не отличите.

                                                                                                                                                      Тут нужно либо очень точно считать именно количество операций (а не время), либо нужны какие-то совершенно безумные объёмы.
                                                                                                                                                        0
                                                                                                                                                        Это уже следующий вопрос. Я не вижу практической разницы между log и loglog так-то, да.
                                                                                                                                                          0

                                                                                                                                                          Но erato, приведенное 0xd34df00d выше в ветке — не n log log n и даже не n log n. Оно n^2 / log^2 n.


                                                                                                                                                          Согласны что там любое простое число в ответе будет проверено на ненулевой остаток всеми предыдущими? Всего чисел n/logn, проверок — квадрат этого числа.

                                                                                                                                                            0
                                                                                                                                                            Не всеми, а до первого делителя.
                                                                                                                                                              0

                                                                                                                                                              Но оно же простое, там нет делителей! Это мы тут только оценку снизу считаем — только проверки для чисел, которые в ответ попадут. А все составные числа еще сколько-то операций добавят.

                                                                                                                                                                0
                                                                                                                                                                Но оно же простое, там нет делителей!

                                                                                                                                                                Так простых чисел до n примерно logn, так что мы сделаем nlogn делений для всех простых чисел вместе. На самом деле даже еще меньше, но это уже надо интегралы брать, а у меня лапки.


                                                                                                                                                                А все составные числа еще сколько-то операций добавят.

                                                                                                                                                                Именно. Добавят. Это не мультипликативный фактор.

                                                                                                                                                                  0

                                                                                                                                                                  Простых до n — примерно n/logn.


                                                                                                                                                                  Еще раз, каждое простое число в вашем erato будет проверено на делимость всеми предыдущими. Иначе, с какой стати ему попадать в ответ, а вдруг оно делится на какое-то число? Всего простых до N — N/logN. Кадое с каждым проверилось — всего квадрат пополам операций.


                                                                                                                                                                  Просто запустите уже ваше решение на n= 10^8 и 10^9. Императивное решение на C++ без каких-либо оптимизаций до 10^9 работает за 7 секунд на моей машине. Умножим на 10 для различий в машинах и компиляторах. Если вы так верите, что ваше erato быстрое — проврьте сначала, что оно отработает хотя бы за полторы минуты.

                                                                                                                                                                    0

                                                                                                                                                                    А, да, тогда вопрос снят.


                                                                                                                                                                    Сорри, я сейчас в самолётах с неработающим ssh'ем до адекватной машины, так что с запусками кода сложно.

                                                                                                                                                    0

                                                                                                                                                    О, знаменитая статья. Но время идёт и приведённое в ней решение уже выглядит переусложнённым. Но это очень, очень полезная статья!

                                                                                                                                                      0
                                                                                                                                                      Там какой-то ад на с. 7, я его не понимаю.
                                                                                                                                                    0
                                                                                                                                                    wataru:
                                                                                                                                                    Но это опять не решето!
                                                                                                                                                    Заходим на haskell.org. Рядом с большим логотипом наблюдаем:
                                                                                                                                                    primes = filterPrime [2..]
                                                                                                                                                      where filterPrime (p:xs) =
                                                                                                                                                        p : filterPrime [x | x <- xs, x `mod` p /= 0]

                                                                                                                                                    Что в переводе на человеческий означает, что из потока целых чисел [3 ..] автоматом отфильтровываются делящиеся на 2, из полученного таким образом потока выбрасываются числа делящиеся на 3, из этого потока далее выбрасываются все числа делящиеся на 5, и т.д.
                                                                                                                                                    Процесс как на картинке из википедии, где кресты разного цвета соответствуют разным уровням рекурсии:image

                                                                                                                                                    Вызовы filterPrime в хвосте формируемого списка при его рекурсивном раскрытии накладываются друг поверх друга, образуя вложенную матрёшку, а ленивость вычислений делает так, что следующий уровень рекурсии вызывает вычисления на предыдущем уровне рекурсии (и далее по цепочке на всех более ранних уровнях) только тогда, когда ему требуются новые данные из своего входного параметра xs для вычеркивания из этого (уже просеянного) списка следующего числа.
                                                                                                                                                      +1

                                                                                                                                                      Нет! koldyr в комментарии выше привел статью уже. Это распространенное заблуждение.


                                                                                                                                                      Ну вы запустите этот код на 1000,10000,100000,1000000, 10^7 чисел и померяйте время работы. Будет ближе к n^2 / log^2 n, чем честное n log log n у решета.


                                                                                                                                                      То, что там что-то лениво вычисляется не позволяет тупо сократить лишние вычисления. Просто посмотрите сколько раз у вас будет остаток вычисляться.


                                                                                                                                                      Вы сначала за n операций уберете все числа, деляещеся на 2. Потом за n/2 операций — все делящееся на 3. Потом за n*(1-1/2)*(1-1/3) — все делящееся на 5. И т.д.


                                                                                                                                                      Это сложно подсчитать прямо, но можно посмотреть с другой стороны: каждое число будет проверено для всех простых, которые меньше его минимального делителя, пока не будет выпилено на какой-то итерации. Если считать только проверки для простых чисел (а они еще происходят и для всех остальных чисел тоже), то оценка снизу количества операций тут (n/logn)^2. Вы уже для n=100000 ответа не дождетесь, в то время, как решето работает тут за доли секунды.

                                                                                                                                                        0
                                                                                                                                                        Я смотрел эту статью давно. Суть в том, чтобы улучшить производительность фильтра, генерирующего входящий поток, т.к. числа делящиеся на k есть каждое k-тое число, и нам просто не нужно к нему применять операцию деления и тестировать остаток. Это как колесо с шипами, которое катится по ленте целых чисел и выбивает каждое k-тое число, причем радиус колеса и количество шипов увеличивается после каждого полного оборота из-за нового найденного простого (не выбитого) числа. Это улучшение наивной реализации алгоритма решета Эратосфена. Суть представленной наивной реализации алгоритма (рассчитанной прежде всего на вау-эффект от элегантности рекурсивного решения) это не меняет. Это всё тот же алгоритм решета, каждое k-тое входное число там определяется наивно с помощью операции mod k.
                                                                                                                                                          0
                                                                                                                                                          Это всё тот же алгоритм решета.

                                                                                                                                                          Который работает за N^2/log^2N вместо N log log N. Который для N=10^7 чисел вы не дождетесь вообще, в отличии от нормального решета.


                                                                                                                                                          Это другой алгоритм. Для той же задачи, немного похожий, но другой!


                                                                                                                                                          Суть в том, что вычеркивать числа через k в массиве совсем не то же самое, что пройтись по всем числам в списке и вычеркнуть с нулевыми остатками.


                                                                                                                                                          Суть представленной наивной реализации алгоритма рассчитанной прежде всего на вау-эффект от элегантности рекурсивного решения это не меняет.

                                                                                                                                                          Да, решение элегантное, но уже для 10 миллионов чисел, в отличии от решета, тупо не работает за приемлемое время. Так-то, есть еще такой очень элегантный алгоритм для проверки числа на простоту:


                                                                                                                                                          return x > 1 && (x == 2 || x % 2 == 1);

                                                                                                                                                          В ФП стиле еще красивее будет. И очень просто и элегантно. И вау-эффектно. Но есть ньюанс для достаточно больших x.

                                                                                                                                                            0
                                                                                                                                                            Суть в том, что вычеркивать числа через k в массиве совсем не то же самое, что пройтись по всем числам в списке и вычеркнуть с нулевыми остатками.
                                                                                                                                                            Поясните на примере. Есть массив последовательных чисел начиная строго с единицы (а у нас в исходной задаче именно такие условия), допустим вот: [1 2 3 4 5 6 7 8 9 10 11]. Нужно вычеркнуть каждый третий элемент. В чем суть отличия от вычеркивания чисел с нулевым остатком от деления на 3? (Кроме производительности операции конечно.)

                                                                                                                                                            Так-то, есть еще такой очень элегантный алгоритм для проверки числа на простоту:

                                                                                                                                                            return x > 1 && (x == 2 || x % 2 == 1);


                                                                                                                                                            В ФП стиле еще красивее будет. И очень просто и элегантно. И вау-эффектно. Но есть ньюанс для достаточно больших x.
                                                                                                                                                            А «достаточно большие» x начинаются уже с 9?
                                                                                                                                                              0
                                                                                                                                                              Поясните на примере.

                                                                                                                                                              При вычеркивании каждого третьего числа, будет сделано 12/3=4 операции вычеркивания и еще столько же операций увеличения индекса (i+=3) и проверок на конец массива (i<12?). Т.е. суммарно 12 операций.


                                                                                                                                                              При вычеркивании чисел с остатком == 0, будет сделано 12 проверок на делимость, 12/3 вычеркиваний, 12 переходов к следующему элементу и 12 проверок на конец списка. 40 операций. Более чем в 3 раза больше.


                                                                                                                                                              Еще раз, решето на массиве просто пропускает 2/3 всех чисел, вообще не тратя на них операции. Ваш алгоритм со списком должен обработать все числа и посмотреть на остаток в каждом.


                                                                                                                                                              В итоге, эти лишние операции накапливаются для всех простых чисел и в сумме дают o(n^2/log^2 n), вместо O(n log log n). Что гораздо медленее для больших n.


                                                                                                                                                              А «достаточно большие» x начинаются уже с 9?

                                                                                                                                                              Да :)
                                                                                                                                                              Это был просто немного гипертрофированный пример, как ваш аргумент не совсем корректен. Если алгоритм работает плохо, то не так важно, насколько он красив.

                                                                                                                                          0
                                                                                                                                          SSA у компиляторов вполне обычных императивных языков как бы намекает.
                                                                                                                                          Вы хотите сказать, что ФП — синтаксический сахар?
                                                                                                                                          Я боюсь вы пропустили «мимо ушей» три буквы и потому не поняли смысла всей фразы.

                                                                                                                                          Современные компиляторы C++ (GCC, Clang, думаю, что и MSVC тоже) перед тем, как анализировать вашу программу и «думать» над тем, как превратить её в машинный код переводят её в так называемую SSA-форму. Фактически — это версия вашей программы в функциональном стиле. Где переменных в стиле императивных языков нет, а переменные в стиле функциональных языков (который вы там дальше в дискуссии обсуждаете) — есть. Ну а дальше уже — всё это «кладётся на архитектуру».

                                                                                                                                          Соответственно переходя от императивного языка к функциональному — вы, несколько парадоксальным образом, оказываетесь «ближе» к машине.
                                                                                                                                            0
                                                                                                                                            Спасибо. Я читал про SSA.
                                                                                                                                            Фактически — это версия вашей программы в функциональном стиле.
                                                                                                                                            По указанной ссылке я такого не нашел. И не очевидно, как это соотносится с определением ФП, предложенным в данной статье.
                                                                                                                                            Особо меня интересуют ГСЧ и обработка событий. Не вижу трудностей для:
                                                                                                                                            промежуточное представление, используемое компиляторами, в котором каждой переменной значение присваивается лишь единожды. Переменные исходной программы разбиваются на версии, обычно с помощью добавления суффикса, таким образом, что каждое присваивание осуществляется уникальной версии переменной.

                                                                                                                                            Но в обсуждаемой статье:
                                                                                                                                            Формулы хорошо формализуются и при одинаковых входных данн