Комментарии 253
Это упрощает создание отказоустойчивого софта.
Ну, и во многих областях это оправдано. Так появилась поддержка длинных целых и рациональных чисел с одной стороны, и всё более мощные символьные движки в повседневных задачах. Так что не зря упирались теоретики!
Давайте лучше откроем учебник по численным методам.
Правда ведь заключается в том, что использования вещественных чисел действительно стоит избегать… просто иногда без них задача не очень решается…
Можно считать в копейках, пока не придут 1/5 копейки, логарифм и экспонента.
Числа с плавающей точкой — зло. Иногда, впрочем, неизбежное зло, как я сказал — но всё равно зло.
Тип «Число» в переменных это примерно как BigDecimal в Java (но, если ничего не изменилось за 5 лет, существенно менее эффективный). В БД в полях, доступных программисту конфигурации — Numeric из SQL (с ограничением длины и точности), который отображается в такой же ограниченный тип в памяти с достаточно необычным подходом к переполнению. Так что в бухгалтерии всё сойдётся :) Ну или не сойдётся по другой причине.
Классических Int, замечу, тоже почти-почти нет. И это имеет свою цену с точки зрения производительности — другой настолько тормозной системы в задаче «посчитай в цикле до миллиарда» даже среди интерпретаторов не найти.
Передадим в бухгалтерию (читай 1С) xxxx.97 миллиард раз (ну или она так прочитает наши хххх.97000000003 из CSV файлика), а у нас вместо вместо xxxx.970000000.00 в 1С итоговая сумма будет xxxx970000000.03 (если не напутал). В лучшем случае главбух объяснит гендиру, что программисты идиоты и считать не умеют, поэтому в годовой бухгалтерской и управленческой отчётности суммы различаются. А в худших может быть различие бухгалтерской и налоговой отчётности, или в суде клиент докажет, что его хотели обмануть на три копейки и получит компенсацию морального вреда и неполученной прибыли на 100500 тысяч, да ещё антимонопольщики за недобросовестную рекламу оштрафуют.
Ну его нафиг, давайте лучше без вещественных вообще.
На самом деле, для любого практического применения можно обойтись только рациональными числами (если ошибаюсь — поправьте).
Например, для вычисления окружности Вселенной, измеренной в атомах водорода, нужно около 40 знаков числа пи. То есть, округляя до первых 100 знаков после запятой, мы гарантировано получим адекватные результаты для любых вычислений длинн в пределах наблюдаемой Вселенной с любой доступной нам (даже в теории) точностью.
То есть иррациональные числа это лишь удобная математическая абстракция, как плюс или минус бесконечность, которой не обязательно сущствует в реальном мире (особенно если время, пространство и другие величины квантуются).
Ну а писать код без сайд эффектов можно, и нужно и на императивных языках. К тому же они поддерживают функциональный плюшки тоже, можно использовать там, где удобно. Короче как всегда, правда посредине.
Про вилку и ложку — это хорошо! А ведь есть ещё палочки и ножи всякие… Споры о том "что круче" парадоксальны в своей бесполезности. Ответ очевиден — лучше научиться владеть всеми приборами, и это не мешает иметь среди всех приборов любимый.
Например, я люблю считать на логарифмической линейке, хотя каждый день ею, конечно, не пользуюсь, для этого есть калькулятор. Но опыт работы с линейкой даёт зримое представление о преобразованиях, соответствующих вычислениям. Движения ползунка и бегунка превращают вычисления в буквальную манипуляцию: в преобразования руками, от которых приходит интуитивное геометрическое представление о поле чисел, имеющее под собой глубокое теоретико-групповое основание. Ответ не берётся из ниоткуда, а возникает в контексте масштаба и своеобразного "ландшафта" вычислений, так что проверка его правильности начинает согласовываться с интуицией. Это как знание города помогает понять, как тебя везёт таксист.
Подобные опыт и интуицию даёт работа в Лиспе и Хаскеле. С ними программа на JS или C# превращается не просто в набор рецептов, инструкций, а в те или иные вычислительные схемы или математические структуры с присущими им свойствами.
Но, полагаю, даже если жаркие дискуссии на темы "нужна ли программистам математика", "что круче: ФП или ООП" и т.п. постепенно отомрут, на смену им придёт что-то вроде: "кто круче, как программист: ИИ, корректно выполняющий ТЗ, или человек с его творчеством?". Мы уже видим начало этой эпохи, споря можно ли доверять машине управлять автомобилем на дороге.
Обычно самая сложная часть бэкенда (хайлоад не трогаем) — это обработка запросов с сайд — эффектами. И хорошо если синхронных с точки зрения клиента(браузера), чётко имеющих вход и выход. А если попутно ставится задание в очередь, о выполнении которого клиент потом уведомляется? Никак тут моделью функции, пускай и не чистой, не обойтись.
А проверить выполнение задания клиент может и сам, даже без уведомлений.
Да, удобство снизится, зато безопасность и отказоустойчивость будут максимальны.
Во всяком случае, если не весь код можно сделать функциональным, то хоть его самую важную часть.
CMS, фреймворки, да и сами языки для веб-программирования содержат большое число различных функций, которые ничего не записывают и не сохраняют промежуточных значений.
Порой там находят опасные уязвимости, так что проверка формальными методами им бы не помешала.
На мой взгляд обойтись всё-таки реально, особенно если отказаться от асинхронности.
А проверить выполнение задания клиент может и сам, даже без уведомлений.
То есть после выполнения запроса клиент должен постоянно пинговать сервер «где там мой ответ?» А если клиентов сотни тысяч? Сервер только и будет делать, что «пинги» разгребать.
Возможно, и даже наверняка, это чего-то стоит. Но по большому счету разделение кода на чистые функции, и функции с побочным эффектами — это то, к чему так или иначе стоит стремиться.
Вот вы скажем имеете что-то против single responsibility principle? Посмотрите на это как на другую его сторону. Выделить побочные эффекты — это полезно. Вы можете всегда накодить тяп-ляп, и не сделать этого, точно также, как намешать в один метод или класс кучу функций. Так тоже можно, и так (увы) тоже работает.
Стоит ли оно того? Ну так это вам решать. Если сегодня нагавнокодили — это да, сегодня дешевле. А завтра? Ну вот и тут примерно так же.
Я не совсем про это, вообще-то. Разве геттеры — это про композицию?
>Зачем тут монады и вообще ФП?
>Оно бывает удобно (в основном для filter/map/reduce инлайн), то зачем больше его внедрять не понимаю.
Монады, если еще чуть упростить — это способ безопасной композиции. filter/map/reduce — это один частный случай. Для остальных частных случаев и внедряют обычно остальное. Этих случаев немножко больше, чем допустим имеется на сегодня в вашем (или моем) наборе инструментов. Ну так это нормально — никто не заставляет внедрять все сразу. Скажем, аппликативные функторы — это неплохое описание процесса валидации исходных данных, и оно тоже бывает удобно.
Можно же и так зайти — зачем вам фабрики, если у вас есть билдеры всякие? Да в общем все затем же — чтобы к каждой задаче выбрать свой наиболее подходящий инструмент.
>Чем созданные специально для инкапсулированного состояния объекты хуже?
Не знаю, кто такие эти объекты. Давайте на простом примере, который вы точно знаете. List — это монада. Чем map лучше по сравнению с циклом for (a: list)? И по сравнению с циклом for (int i= 0; i< list.size(); i++)?
По-моему, ответ очевиден — тем что map это как раз безопасная композиция. Я гарантировано знаю, что применяя при помощи map функцию String->Integer к List я точно получу List, и ничего иного. Причем исходного размера. А применяя filter — получу List, возможно меньшего размера. И сколько бы я их не компоновал, я не смогу эти правила нарушить, независимо от того, какими типами мы тут в List<?> манипулируем. То есть, она еще и универсальная.
Самое главное — эти проверки и доказательства возможны, причём уже сейчас, так что глупо этим не пользоваться и спорить. Что подтверждает тезис, обозначенный в названии статьи.
Боюсь, что разочарую вас. Я имел в виду принципиальную возможность двигаться в этом направлении, если оставаться в рамках ФП. Пока же выкладки приходится делать "на бумажке". Но! Это возможно сделать. Я игрался с формальной верификацией некоего подмножества Java (практически, процедурным подмножеством, не выходящем за пределы Оберона) через триады Хоара. Очень быстро система неравенств становится неподъёмной, по моим ощущениям, экспоненциально. Инварианты циклов приходится писать самому, а это искусство и шаманство. После этого, возвращаясь к типам и индукции в ФП, с доказуемыми свойствами алгебраических структур, понимаешь, какой это кайф: надеть, наконец лыжи после того, как брел по пояс в мокром снегу. Но и лыжи пока приходится переставлять самому. Впрочем, пока ждем завтипов в Хаскеле, можно упражняться, отрабатывая технику на том что есть. Понятно же, что для того, чтобы написать грамотную рабочую спецификацию для автоматического верификатора, потребуется нехилая квалификация программиста. Но пока, насколько я вижу, именно ФП ведёт нас к возможности по-настоящему взлететь.
Ну, это смотря по сравнению с чем. По сравнению с циклом, результат которого вообще без детального анализа непонятен — очень даже знаю. Собственно, я хотел сказать простую вещь — что map ограничивает изменения одним элементом списка, не позволяя функции менять структуру списка каким-то непредсказуемым способом.
Понятно, что могут быть какие-то еще эффекты, скажем в Java функция String->Integer легко может выкинуть исключение — но это означает, что функция определена не на всем множестве входных значений. И в Java я не могу этого выразить, да. Что совершенно не отменяет вполне практических преимуществ map в этом случае.
Функциональному подходу нет необходимости заполнять всё вокруг. Оно тяготеет к маленьким самодостаточным ортогональным блокам и если в императивной архитектуре такие блоки использовать, то они не помешают. В Фотране (куда уж императивнее!) с 80-х годов есть модификатор pure, указывающий и программисту и компилятору, что определяемая функция чистая, что позволяет им делать определённые выводы как о коде функции, так и о коде, ее использующем.
Операционную систему не сделать чистой по определению, но с некоторыми задачами ФП справляется отлично. Например, на моём ноутбуке, а также на домашнем и на рабочем десктопах стоит NixOS (Linux-дистрибутив построенный вокруг функционального ленивого (а значит, чистого) пакетного менеджера Nix), c оконным менеджером XMonad. И мне нужна их декларативность при настройке и переносе решений с машины на машину. Но это не позволяет мне говорить, что ФП решает все проблемы. Но оно очень неплохо встраивается в императивные решения, поскольку предлагает… чистые функции :)
Я тоже пользуюсь NixOS, и при этом ещё до перехода на неё начал переписывать скипты, которые обычно писал на bash, на haskell, но только когда main = interact myPureFunction. Тогда гораздо легче отлаживать ошибки в них, а ещё можно скомпилировать и получить некую прибавку к скорости и производительности.
А всё, что нельзя описать interact, лучше написать на классическом баше или перле — быстрее и читаемей.
и еще чтобы с примерами «скриптов на хаскелеподобных языках» (мне действительно интересно).
Одна из основных задач программирования — это изоляция сайд-эффектов. Если у вас допустим идёт работа с БД, то можно сохранять данные по мере вычисления и размазать логику работы с БД по всей программе. А можно сначала подготовить все данные, а потом сохранить их все разом. Это можно делать в любой парадигме, но, применяя ООП, про это, к сожалению, часто забывают.
А если попутно ставится задание в очередь, о выполнении которого клиент потом уведомляется? Никак тут моделью функции, пускай и не чистой, не обойтись.
В чём проблема? Или вы представляете какую-то одну божественную функцию, которая делает всё? Это не так работает.
Постановка задания в очередь — это сайд-эффект, но тем не менее это никак не мешает вернуть какой-то ответ клиенту. А при выполнении задания, когда до него дойдёт очередь, уведомить клиента, например через веб-сокет.
Когда код простой, можно и в процедурном стиле написать, то, что бэк на ноде выглядит функционально это скорее особенность ноды — в той же java обычный бэкэндщик будет вызывать блокирующие процедуры.
Что касается переиспользования дивов — реакт с его функциональным подходом давно так делает, работа же с ивентами без стримов быстро превращается в спагетти.
Хм. Вот люблю я, когда так вот обобщают. Видимо, это не Java разработчики когда-то довольно давно изобрели clojure — это хаскелисты прокрались в их ряды. Это не Java разработчики внедрили в Java 8 много всего разного от ФП, в частности, сделав функции наконец-то удобными в работе. Это все они, это их заговор, мы-то знаем, что настоящие Java разработчики не спешат изучать ФП.
ИМХО, ООП — это расширение (даже просто синтаксический сахар) идей модульного программирования, а будут ли инстансы таких модулей «объектами» в смысле ОО дизайна — отдельный вопрос. Если экземпляр класса инкапсулирует состояние и ограничивает к нему доступ — это объект, а если нет, просто синтаксический артефакт. Классы, методы и остальное вторичны, реализовать суть: инкапсулировать состояние и ограничить возможность его изменения хоть через открытый интерфейс, хоть через передачу сообщений.
При чем тут ФП? Мне кажется, вообще не при чем. Речь идет о выборе языка реализации, а это совсем другой круг вопросов.
А вот разговор о подходах к дизайну — осмысленный! Что в конкретном случае продуктивнее — рассматривать систему, как набор функций или как совокупность объектов с состоянием, или как сочетание того и другого — в этом суть. И можно подобрать удобный инструмент. Иначе придется чесать правой рукой левое ухо и завинчивать гвозди отверткой.
Простите за занудство.
А многие холивары внутри ООП из-за смешения понятий «инкапсуляция» и «сокрытие». Инкапсуляция — это совмещение данных и методов, а сокрытие — ограничение работы с данными напрямую.
Мое определение ФП — непрофессиональное программирование, либо программирование для гуманитариев, которые не могут в абстрактное мышление. Какими бы чистыми там функции не были, когда их будет 100500 они в любом случае превратяться в черный ящик с макаронами.
Пока что все топители за ФП, которых я встречал, были только одного типа. В институтах их сразу заставили писать в ООП, не объяснив зачем это все нужно, и теперь они вдруг видят, что можно писать без нудных классов, просто бери и фигач код напрямую и все типо работает. Особенно это характерно для фронтендов,
Вакансии с условием «уметь в ФП» я тоже чтото не видел, что намекает.
Вы путаете ПОП и ФП. Изучить ФП очень трудно (на порядок труднее ООП) как раз по причине очень высокой абстракции…dreesh, Ну и вот тем более! Если фронт-джун топит за ФП это говорит о том, что на самом деле он просто не хочет писать в ООП, а хочет писать код чистоганом. Никаким ФП тут на самом деле не пахнет.
Покажите мне хоть одну серьезную большую программу в ФП.
Компилятор Haskell GHC написан на Haskell :) Можете сами в этом убедится Glasgow Haskell Compiler
Покажите мне хоть одну серьезную большую программу в ФП.
Riak. RabbitMQ, ejabberd. Бекэнд WhatsApp. Прошивка для коммутатора AXD301, обеспечившая надежность 99,9999999%. Из Хаскеллового выбирайте сами вот тут — там и банки, и телескопы, и hardware design.
Ещё добавим по вакансиям:
Согласно этой статье, топ зарплат у F#, Ocaml, Clojure, Groovy, Perl, Rust, Erlang, Scala, Go, Ruby. Вот десяточка.
Угадай, сколько из них ФП?
Статьи на тему «ФП лучше» или «ООП лучше» напоминают дебаты, что же лучше для обеда, вилка или ложка.Практика турпоходов показывает, что ложка лучше — все всегда берут ложки, но практически никто не берет с собой в поход вилку :)
Аналогично, ООП позволяет решать более широкий круг задач, если исходить из определения автора:
Функциональное программирование, в вольной трактовке, рассматривает программу как математическую формулу. Формулы хорошо формализуются и при одинаковых входных данных возвращают одинаковые выходные.Добавим в код генерацию случайного числа или обработку события и при одинаковых входных данных не получим одинаковые выходных. Т.о., согласно данному определению, в ФП это недопустимо. А в ООП (и других парадигмах) допустимо. Или я не понял предложенного в статье определения?
Не совсем поняли. Впрочем, там сразу написано, что это вольная трактовка определения. На самом деле, прагматический подход к такому (написанию ГСЧ) состоит в том, чтобы выделить такие куски кода, которые являются чистыми, и остальные, которые либо взаимодействуют с внешним миром (IO), или не являются чистыми по другим причинам.
> обработку события и при одинаковых входных данных не получим одинаковые выходных
Это с чего бы? Если у вас есть состояние — то почему вы его не считаете частью входных данных? И дело не в том, допустимо это или нет. Дело в том, что выводы, которые вы (или компилятор) можете делать по поводу вот этого вот кода, они зависят от того, является ли кусок кода чистым.
прагматический подход к такому (написанию ГСЧ) состоит в том, чтобы выделить такие куски кодаГСЧ может быть и аппаратным, частью CPU. Тут выделить не получится и ФП не применимо (в вольной трактовке).
Если у вас есть состояние — то почему вы его не считаете частью входных данных?Если событие происходит в ходе вычисления и влияет на него.
>Если событие происходит в ходе вычисления и влияет на него.
Все что влияет — это часть исходных данных, почему нет-то? Если обработка событий происходит по-разному — значит у вас есть какое-то состояние? В ФП его просто делают чуть более явным.
Все что влияет — это часть исходных данных, почему нет-то?Данных, но не исходных, а текущих. Простейший пример: функция последовательными приближениями долго вычисляет результат, мне надоело ждать, нажал кнопочку, функция должна вернуть, что упела вычислить на этот момент.
Это такое вполне обычное состояние. Я повторюсь — ФП не означает, что у вас скажем не бывает состояния. Оно лишь означает, что вы такие случаи, когда вычисления от него зависят, явно выделяете. Если вы зависите от железа в реализации ГСЧ, то у вас и не может быть никакой абстракции чистой функции _в этом месте_, но вполне может быть в другом. И такое разделение само по себе полезно.
Вот такой простой пример, не совсем в тему — один мой коллега очень любит в один метод всунуть две вещи — чтение данных из файла, и работу с этими данными. Из чего вытекает нехорошее следствие — чтобы этот код протестировать, мы вынуждены в тестах заводить реальные файлы, и иметь дело с файловой системой, со всеми вытекающими. Если же мы разделим метод на две части, одну которая читает данные из файла, и вторую, которая обрабатывает, то вторая почти автоматически становится функцией, причем чистой. Ну то есть я это к тому, что и в совершенно не ФП случае выделение побочных эффектов в виде файлов вполне себе полезная штука.
Ну то есть я это к тому, что и в совершенно не ФП случае выделение побочных эффектов в виде файлов вполне себе полезная штука.Полностью согласен. В моем примере вижу только одно решение:
повторять
список_аргументов := чистая_функция_очередное_приближение (список_аргументов);
до_той_поры_пока чистая_функция_точность_достигнута (список_аргументов)
или кнопочка_нажата;Т.е. две чистых функции, но всю программу в виде читой функции не оформить.
ГСЧ может быть и аппаратным, частью CPU
Даже в императивном языке придется к нему обращаться явно.
Чистые функции не имеют сайд-эффектовOk: никаких внешних переменных, видимых помимо аргументов, но в регистрах, стеке, где-то еще (зависит от железа и реализации) всегда есть мусор от предыдущих действий. Если мы будем читать этот мусор? М.б. не очень хороший ГСЧ, но одинаковых выходных не получим. Либо любой мусор признать аргументами (входными данными), но тогда список аргументов будет зависеть от устройства черного ящика — железа и реализации, т.е. никакой абстракции. Либо чистить весь мусор, что в общем виде м.б. проблематично. Либо везде прописывать уникальный код и тестировать все локальные переменные на неинициализированность. Как-то очень нечисто?
Либо везде прописывать уникальный код и тестировать все локальные переменные на неинициализированность. Как-то очень нечисто?
Ну как бы код после компиляции будет отличаться в зависимости от целевой системы разве нет?
На самом деле я уже не совсем понимаю предмет обсуждения. Как связанно явное обращение к ГСЧ и наличие мусора на стеке и регистрах
Даже в императивном языке придется к нему [ГСЧ] обращаться явно.ИМХО использование локальной переменной с неопределенным значением (в качестве случайного числа) — не явное обращение к ГСЧ. Такие обращения можно отследить в ходе исполнения, если во все переменые при запуске программы (и при вызове функции) будет записано уникальное значение, нпр., FFF… Так ловили баг в древних Паскалях. В некоторых ЯП всегда записано значение по умолчанию, нпр., ноль.
Внезапно, доступ к неинициализированным переменным можно (и нужно) запретить. Либо всегда инициализировать их значением по умолчанию, как вы ниже заметили.
ФП не требует переменныхСможете доказать это утверждение строго математически: Теорема. Любую функцию можно реализовать без использования переменных?
И практически интересно: как спрограммировать в этом подходе решето Эратосфена?
Т.е. числа Фибоначчи считаем по самой долгой рекурсии с 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--Но в функциональном решении пропустить инициализацию "переменных" нельзя никак.
Это не переменные, поскольку они не могут измениться, оставаясь в рамках процесса, описываемого функцией. Изменения происходят только на входе-выходе. Одно из отличий, в частности, состоит в том, что, в функциональном коде нет понятия времени и изменение наших "переменных" происходит одновременно: a,b = b,a+b, эквивалентное последовательности присвоений с буфером с = b; b = a+b; a = c.
Это не лучше и не хуже нормальных переменных, просто если проще описать вычислительный процесс итеративным, ФП этому не сильно помешает.
SSA у компиляторов вполне обычных императивных языков как бы намекает.
Вы хотите сказать, что ФП — синтаксический сахар?
невозможно строго доказать или опровергнуть
Сначала нужно будет строго определить понятие переменной.
который, конечно, где-то в глубине компилируется во вполне мутабельный код, но это деталь реализации, нас не сильно интересующаяВ данном случае интересующая: если деталь скрытая — то не значит, что ее нет. Посмотреть ассемблер — будут там переменные, изменения значения.
А вот тут в дело вступает то обстоятельство, что задача трансляции (компиляции) по природе своей функциональна. Объектный код полностью определяется исходным кодом и текущим окружением (входными параметрами). На этом стоит вся система сборки дистрибутивов типа configure >> make. Так что если абстракция функциональности и теряется на каком-то уровне, то это происходит всегда одинаково и решение можно, в конце концов, верифицировать, добившись герметичности абстракции на верхнем уровне. GHC это уже умеет. То есть, нас, действительно могут не сильно интересовать детали реализации, покуда компилятор не нарушает некоторых нужных нам законов и инвариантов.
Запросто! Это как в задаче интегрирования. Есть алгебраический подход, а есть геометрический, есть спектральный, а есть аналитический по теореме Коши, наконец, можно численно, но и там, можно Симпсоном, можно Гауссом. Когда как удобнее. Полезно владеть всем.
Мне нужно вдумчиво смотреть на insert и balance, чтобы попытаться понять, какой случай я упустил. Зачем мне бегать дебаггером, какую новую информацию он мне даст?Это уже не теория, а практика. Действительно в простых учебных задачах бывает достаточно просто хорошо подумать над результатами тестов. Но для более сложных отладчики себя зарекомендовали. Факт, что чем больше всяких возможностей для отладки — тем лучше. Дело не только в том чтобы найти баг, а чтобы найти его достаточно быстро.
Э, ну можно же. Модификация состояния (в том числе состояния ГПСЧ) — это эффект, а эффект моделируется монадой.я не спорю: многое возможно. Но люди склонны совершать ошибки. Одна из типовых ошибок — непредсказуемое поведение функции.
Компилятор для DSL — достаточно крупный проект?Наверняка крупный, но у каждого проекта своя специфика. Для другого может не подойти.
И чистота системы типов отлично от этого защищает.Как защищает в случае неинициализированных переменных?
Мы же только что убедились, что в чистых функциональных языках переменных вообще нет — следовательно неинициализированных переменных быть не может :)
Вы понимаете разницу между переменной и параметром?Понимаю. В Паскале, нпр.:
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 — переменная?
Нет, не переменная, она ж не меняется.Как не меняется? Я так понял, что до выполнения оператора
where s = sin fi
s не определена, а после равна значению синуса аргумента fi.
видишь слово s — подставь определение из правой части.«подставь» — это команда (что в программировании называется оператором). Для ее выполнения, надо не только подставить значение синуса, но и вычислить его сначала. Или тут только подстановка, как в препроцессорах? Но тогда синус будет вычислятся 2 раза, а не один.
Но для более сложных отладчики себя зарекомендовали.У них очень узкая ниша, на самом деле. В Гугле, например, сняли разработчиков с GDB, когда выяснилось, что им пользуется ежедневно, в среднем, менее 5% разработчиков.
Вряд ли разработку google.com можно назвать «маленькой учебной задачей».
Вряд ли разработку google.com можно назвать «маленькой учебной задачей».Нет, но как сказал выше:
у каждого проекта своя специфика
Это не решето Эратосфена. Тут наивный метод перебора всех чисел и проверки делимости на уже найденные простые числа. Даже после переиспользования erato вместо списка всех меньших чисел.
Для поиска всех простых чисел до n этот алгоритм будет работать O(n^2 / log n). Может, если там соптимизированно "all /= 0" и не проверяет после первого несовпадения, тогда можно еще на log n поделить. Когда как честное решето эратосфена будет O(n log log n), что намного эффективнее.
Да, наивному решету надо в log n раз больше памяти, но это лечится если ввести сегментацию — тогда оно будет занимать ассимптотически столько же памяти, что и ваш алгоритм. А если надо хранить не все простые, а, скажем, найти k-ое, то сегментированное решето потребует гораздо меньше памяти.
Да, наивному решету надо в log n раз больше памяти, но это лечится если ввести сегментацию — тогда оно будет занимать ассимптотически столько же памяти, что и ваш алгоритм. А если надо хранить не все простыеТ.е. что-то надо хранить. Хранят в переменных (явных или неявных), но при этом постоянно говорят, что
в чистых функциональных языках переменных вообще нет
Так есть или нет? ИМХО если что-то хранить, то хранится в переменной. А иначе напоминает двоемыслие.
Просто эти переменные все с модификатором const и как бы неявные — в виде параметров у функций. Вызвали функцию — создали переменные.
Хотите к счетчику что-то прибавить — вызывайте рекурсивно функцию с +1 в параметре.
С одной стороны это создает кучу сложностей и ограничений. С другой убирает сайд-эффекты.
С одной стороны это создает кучу сложностей и ограничений. С другой убирает сайд-эффекты.ИМХО в процедурном программировании сайд-эффекты убираются простыми ограничениями на глобальные переменные. Там это вопрос стиля. В ООП у каждого класса есть свойства и переменные, которые видны всем методам класса. Можно сказть, что там сайд-эффекты сознательно допустимы внутри класса и его потомков. И это бывает удобно. В ООП возможен плохой стиль, но ИМХО это не причина абстрактного ужаса перед сайд-эффектами. Не слишком ли их боятся?
Мне импонирует ваше стремление разобраться! Переменное состояние и сайд-эффекты в ФП исключены вовсе не ради инкапсуляции, вернее не только ради неё. Если мы готовы принять это ограничение, то становятся возможными:
- Однозначный вывод типов по Хиндли-Милнеру, существенно более полезный, чем
varилиauto, поскольку он проникает на все уровни программы от сигнатуры функции до самых мелких её деталей. И это не для экономии нажатий клавиш при определении функции, а для настоящей и осознанной типобезопасности. Компилятор в чистых типизированных ФЯП не тестировщик и не надзиратель, а друг и помощник, подсказывающий и объясняющий программисту даже не в чём состоит ошибка, а что ему писать дальше. Это не автодополнение IDE доступных полей и методов, а подсказка сложных и очень нетривиальных решений, которые потом могут превратиться в научные разработки. Это круто и от этого уже трудно отказаться! - "Типо-ориентированное программирование", несколько более широкое, чем data-driven design, поскольку на первый план выступают алгебраические свойства типов (и функций над ними), не нарушаемые изменением состояния.
- Внятная и доказуемая денотационная семантика, equational reasoning, настоящее unit-тестирование с автогенерацией тестов и property-based тестированием (Quickcheck появился в Haskell и только потом разошёлся по языкам).
- Выбор стратегии вычислений (строгая/ленивая), в чистом ФП не меняющая результат, а влияющая лишь на эффективность программы и на способы её декомпозиции (в ленивом Haskell декомпозиция вкусна до безобразия, одни только гиломормизмы и fusion чего стоят!).
- Принципиальное отсутствие в многопоточности гонок, и проблем с общими ресурсами.
- Наконец, осознанная свобода в выборе и конструировании семантики позволяет легко (правда, легко, монады не сложнее какого-нибуть преобразования Фурье или Лапласа, хоть и "ломают" по началу мозг) эмулировать и переменное состояние и эффекты, но со всеми перечисленными выше плюшками!
Отсутствие сайд-эффектов и переменных не цель ФП, а средство достижения гораздо больших целей. И, более того, если надо, я всегда могу их себе завести, но они гарантированно будут локальными и с тонко настраиваемой семантикой.
Мне импонирует ваше стремление разобраться!Спасибо Вам и всем, кто помогает мне разобраться! :)
Со своей стороны, в первую очередь хочу отметить, что мне импонирует дружелюбная атмосфера, сложившаяся в данном обсуждении. До этой статьи я периодически читал про ФП, у меня постепенно накапливались недоуменные вопросы, которые откладывал «на потом». И вот этот «потом» настал, и за пару дней узнал больше, чем раньше за гораздо более длительный срок. Поэтому надеюсь, что и в дальнейшем обсуждении сообщество проявит терпение, отвечая на дальнейшие, может, не самые удобные вопросы — у меня их еще много)
Пользуясь случаем, предложу идею, м.б. кого заинтересует: тут много наговорили, отвечая на вопросы чайника в ФП (т.е. меня). Предполагаю, что я не оригинален, и что у других ФП-чайников есть похожие вопросы, но не все они будут читать это объемное обсуждение. Может, кто из экспертов-знатоков ФП переформатирует это обсуждение в FAQ и опубликует в виде статьи на Хабре? Уверен, что такая публикация будет очень актуальна.
Хотя в данный момент я далек от того, чтобы перейти на ФП, но вижу, что здесь очень интересная философия и практика, есть над чем подумать. В любом случае любому программисту очень полезно ознакомиться с общими принципами для расширения кругозора. Думаю, что если и не перейду на ФП, это довольно мимолетное знакомство повлияет на мой стиль написания программ.
Теперь позвольте задать очередную порцию вопросов.
для настоящей и осознанной типобезопасностиНе понимаю, как вывод типов повышает типобезопасность. В вики читаю:
опустить тип идентификатора в определении с инициализацией (см. синтаксический сахар). Например:ИМХО действительно сахар.
var s = «Hello, world!»; // Тип переменной s (от string) выведен из инициализатора
Это не автодополнение IDE доступных полей и методов, а подсказка сложных и очень нетривиальных решений, которые потом могут превратиться в научные разработки.Это не преувеличение? Как это можно превратить в научную разработку? Есть пример?
«Типо-ориентированное программирование»Не нашел в гугле и вики внятных определений. Можно пояснение и ссылку?
Принципиальное отсутствие в многопоточности гонок, и проблем с общими ресурсамиЗа счет чего отсутствие?
Спасибо, это, действительно, многовато для комментария. Пройдёмся по вашим вопросам.
- Вывод типов в ФП распространяется не только на объявление параметров/констант, но и на типы всех выражений и функций. И работает он в "обе стороны", то есть, я могу явно написать тип определяемой функции, а потом спросить у компилятора каким должен быть тип того или иного (любого) подвыражения в её теле, используя т.н. дырки, (holes). Это лучше показать, но не в комментарии. С другой стороны, я могу написать тело функции, не указывая вообще ни одного типа, и компилятор постарается вывести самый общий полиморфный тип для неё (в статике, на этапе компиляции). Если не выйдет, он скажет что именно ему не понятно, и это будет либо моя ошибка, либо неоднозначность задачи, требующая явного сужения типа, что тоже полезно и открывает глаза на программу. Особенно приятно общаться с компиляторами PureScript или Elm, но и ghc в последние годы становится более дружелюбным (или это я учусь понимать его?). А вот работа с литералами-константами (из примера с
var), как раз часто требует уточнения, поскольку в Haskell выражение5может означать либо целое число, либо число с плавающей точкой, либо, вообще, какой-нибудь тип-обертку типаSumилиMax. Компилятор очень постарается понять из контекста, что же это такое, но программист может его здорово запутать :) - Я не преувеличил роль вывода типов в ФП в серьёзных исследованиях. Многие наши замечательные современники — асы ФП, создавшие целые концепции, вроде линз, кондуитов, или свободных монад, активно используют интерпретатор GHCi, как основной инструмент, получая от него ответы на вопросы (скажем, какой функтор нужно подставить в линзу, чтобы превратить его в геттер или сеттер) и целые доказательства (см. изоморфизм Карри-Ховарда) для своих идей, о чём с удовольствием рассказывают на конференциях и в блогах.
- Я нарочно взял словосочетание «типо-ориентированное программирование» в кавычки, это не официальный термин. Типы в ФП (типизированном) это нечто большее чем "множество допустимых значений, внутреннее представление данных и возможные операции над ними". Это основа дизайна программ, предоставляющая связи между типами и законы (в математическом смысле, а не в инженерном) им присущие. Типы параметризуют друг друга и сами образуют более общую структуру Kinds, всё это выводит работу с ними на уровень настоящего исчисления. Иногда это чертовски сложно и нетривиально, иногда чертовски красиво, но вот что для меня привлекательно: тут остаётся мало места традициям, моде и вкусовщине, присущим нашему делу. Вместо них теоремы, анализ и строгие выводы, которые можно использовать, спустя десятилетия и они не устаревают, а со временем получают развитие, как, например получилось с линейными типами.
- На последний вопрос отвечу аккуратно: отсутствие изменяемого состояния (концептуальное) заставляет писать код, в котором проблем с параллелизмом и конкурированием существенно меньше. Я не стану утверждать рекламным голосом, что в рамках ФП параллелизм станет лёгким и приятным как никогда, и теперь с этим справится даже ваша мама. Сложности всё равно остаются, но они, скажем так, иного уровня, поприятнее, что-ли.
Это основа дизайна программ, предоставляющая связи между типами и законы (в математическом смысле, а не в инженерном) им присущие.Не все матрицы можно умножать — размеры должны соответствовать. Можно в ФП задать такое правило на уровне типов?
Не все матрицы можно умножать — размеры должны соответствовать. Можно в ФП задать такое правило на уровне типов?
конечно можно (простейший пример)
Тогда придётся делать рекурсивную функцию, которая берёт какой-нибудь Data.Array или тупо список (хотя тут чуть сложнее анализировать сложность в ленивом контексте) и из него что-нибудь вычёркивает.
Но, в любом случае, снова никаких переменных.
Ох и сомневаюсь я что тут что-то вообще хоть сколько-нибудь читаемое получится.
Вот в чем проблема-то, решето — по природе своей изменение массива по заданному правилу. Любая его реализация в чистом ФП будет костылем и эмулированием всех переменных и циклов, но через функции.
Как я уже писал, представьте что у вас все переменные const, и при изменении просто передавайте новые значения как параметры функции. Это и есть подход ФП.
Формально — никаких переменных и сайд эффектов. На практике код будет таким сложным, что это просто выдумывание себе проблем на ровном месте.
Для многих задач в этой парадигме можно сделать очень простой и понятный код. Для других задач чистое ФП все-таки не так хорошо подходит.
Для многих задач в этой парадигме можно сделать очень простой и понятный код. Для других задач чистое ФП все-таки не так хорошо подходит.Спасибо. Что-то подобное я и ожидал услышать!
Но это опять не решето! Мне кажется, тут опять каждое число проверяется на делимость всеми предыдущими простыми. Это слабо отличается от изначального вашего алгоритма.
Вы тут просто по определению делаете — списко всех чисел, которые не делятся ни на одно предыдещее число из списка.
Суть решета же в том, что вы вычеркиваете только те числа, которые точно делятся на число x, делая прыжки +x по массиву, не проверяя делимость вообще.
Реквестирую императивное бесконечное решето.
Этот же метод (не решето!) в императиве также бесконечно очень просто делается. Да, тут ФП решение покороче будет. На задчах, где ФП действительно применимо, оно часто позволяет делать сильно более короткие решения. P.s. решето, к таким, по всей видимости, не относится.
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;
}Когда вы говорите о сложности log log n, то что вы считаете за операцию? Проверку на делимость или вообще обращение к контейнеру?
За операцию считаются:
- обращение к массиву.
- арифметические операции (+, -, *, деления тут вообще нет).
- проверка условия, условные/безусловные переходы.
Грубо говоря, ассемблерные операции.
Там log log n вылезает потому что n/2 + n/3 + n/5 + n/7 +… сходится к n log log n. Мы ведь сначала вычеркиваем каждое второе число (пишем false по индексу, прибавляем к индексу смещение, проверяем на конец массива). Потом каждое 3-е число, и т.д. Отдельно вылезает слагаемое +n, потому что надо каждый элемент во внешнем цикле проверить, и если число простое выписать его в ответ и запустить вычеркивание.
Не верю, как delete может быть константным. Если он лениво выполняется, то надо считать с ленивостью.
Это уже больше похоже на решето, но я не могу разобраться в этом коде, ибо этот синтаксис мне чужд. Оно работает вообще? Можете его позапускать на больших n и подсчитать время работы? Хотя бы для n=100, 1000, 10000, 100000, 1000000 и посмотреть с какой скоростью оно растет?
У меня такие подозрения, что ленивость delete тут всю суть поломает, ибо ему придется все предыдущие удаленные списки проверить на каждом элементе, что равносильно, опять же, проверке на делимость каждого числа всем предыдущими.
Исходное erato ну никаким образом не может быть n log log n. До каких n вы его гоняли? Можно данные в студию?
Дайте угадаю, до 10^6 erato у вас работает пару секунд? У меня сишное решето до миллиона срабатывает мгновенно. Для 10^9 меньше 10 секунд.
Чтобы было что сравнивать, подсчитайте сумму всех простых чисел до n включительно. Для 10^9 ответ 24739512092254535. Если ваше erato сработает хотя бы за минуту, я буду очень-очень-очень удивлен и признаю, что это действительно решето.
Побенчмаркал.Бенчмаркать тут довольно бессмысленно. log₂ log₂ 1000000000 — это в районе 5, а log₂ 1000000000 — это в районе 30, так что на любых вменяемых объёмах вы log₂ log₂ N от log₂ N не отличите.
Тут нужно либо очень точно считать именно количество операций (а не время), либо нужны какие-то совершенно безумные объёмы.
Но erato, приведенное 0xd34df00d выше в ветке — не n log log n и даже не n log n. Оно n^2 / log^2 n.
Согласны что там любое простое число в ответе будет проверено на ненулевой остаток всеми предыдущими? Всего чисел n/logn, проверок — квадрат этого числа.
Но оно же простое, там нет делителей! Это мы тут только оценку снизу считаем — только проверки для чисел, которые в ответ попадут. А все составные числа еще сколько-то операций добавят.
Простых до n — примерно n/logn.
Еще раз, каждое простое число в вашем erato будет проверено на делимость всеми предыдущими. Иначе, с какой стати ему попадать в ответ, а вдруг оно делится на какое-то число? Всего простых до N — N/logN. Кадое с каждым проверилось — всего квадрат пополам операций.
Просто запустите уже ваше решение на n= 10^8 и 10^9. Императивное решение на C++ без каких-либо оптимизаций до 10^9 работает за 7 секунд на моей машине. Умножим на 10 для различий в машинах и компиляторах. Если вы так верите, что ваше erato быстрое — проврьте сначала, что оно отработает хотя бы за полторы минуты.
Но это опять не решето!Заходим на haskell.org. Рядом с большим логотипом наблюдаем:
primes = filterPrime [2..]
where filterPrime (p:xs) =
p : filterPrime [x | x <- xs, x `mod` p /= 0]Что в переводе на человеческий означает, что из потока целых чисел [3 ..] автоматом отфильтровываются делящиеся на 2, из полученного таким образом потока выбрасываются числа делящиеся на 3, из этого потока далее выбрасываются все числа делящиеся на 5, и т.д.
Процесс как на картинке из википедии, где кресты разного цвета соответствуют разным уровням рекурсии:
Вызовы filterPrime в хвосте формируемого списка при его рекурсивном раскрытии накладываются друг поверх друга, образуя вложенную матрёшку, а ленивость вычислений делает так, что следующий уровень рекурсии вызывает вычисления на предыдущем уровне рекурсии (и далее по цепочке на всех более ранних уровнях) только тогда, когда ему требуются новые данные из своего входного параметра
xs для вычеркивания из этого (уже просеянного) списка следующего числа.Нет! 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 ответа не дождетесь, в то время, как решето работает тут за доли секунды.
Это всё тот же алгоритм решета.
Который работает за N^2/log^2N вместо N log log N. Который для N=10^7 чисел вы не дождетесь вообще, в отличии от нормального решета.
Это другой алгоритм. Для той же задачи, немного похожий, но другой!
Суть в том, что вычеркивать числа через k в массиве совсем не то же самое, что пройтись по всем числам в списке и вычеркнуть с нулевыми остатками.
Суть представленной наивной реализации алгоритма рассчитанной прежде всего на вау-эффект от элегантности рекурсивного решения это не меняет.
Да, решение элегантное, но уже для 10 миллионов чисел, в отличии от решета, тупо не работает за приемлемое время. Так-то, есть еще такой очень элегантный алгоритм для проверки числа на простоту:
return x > 1 && (x == 2 || x % 2 == 1);В ФП стиле еще красивее будет. И очень просто и элегантно. И вау-эффектно. Но есть ньюанс для достаточно больших x.
Суть в том, что вычеркивать числа через k в массиве совсем не то же самое, что пройтись по всем числам в списке и вычеркнуть с нулевыми остатками.Поясните на примере. Есть массив последовательных чисел начиная строго с единицы (а у нас в исходной задаче именно такие условия), допустим вот: [1 2 3 4 5 6 7 8 9 10 11]. Нужно вычеркнуть каждый третий элемент. В чем суть отличия от вычеркивания чисел с нулевым остатком от деления на 3? (Кроме производительности операции конечно.)
Так-то, есть еще такой очень элегантный алгоритм для проверки числа на простоту:А «достаточно большие» x начинаются уже с 9?
return x > 1 && (x == 2 || x % 2 == 1);
В ФП стиле еще красивее будет. И очень просто и элегантно. И вау-эффектно. Но есть ньюанс для достаточно больших x.
Поясните на примере.
При вычеркивании каждого третьего числа, будет сделано 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?
Да :)
Это был просто немного гипертрофированный пример, как ваш аргумент не совсем корректен. Если алгоритм работает плохо, то не так важно, насколько он красив.
Я боюсь вы пропустили «мимо ушей» три буквы и потому не поняли смысла всей фразы.SSA у компиляторов вполне обычных императивных языков как бы намекает.Вы хотите сказать, что ФП — синтаксический сахар?
Современные компиляторы C++ (GCC, Clang, думаю, что и MSVC тоже) перед тем, как анализировать вашу программу и «думать» над тем, как превратить её в машинный код переводят её в так называемую SSA-форму. Фактически — это версия вашей программы в функциональном стиле. Где переменных в стиле императивных языков нет, а переменные в стиле функциональных языков (который вы там дальше в дискуссии обсуждаете) — есть. Ну а дальше уже — всё это «кладётся на архитектуру».
Соответственно переходя от императивного языка к функциональному — вы, несколько парадоксальным образом, оказываетесь «ближе» к машине.
Фактически — это версия вашей программы в функциональном стиле.По указанной ссылке я такого не нашел. И не очевидно, как это соотносится с определением ФП, предложенным в данной статье.
Особо меня интересуют ГСЧ и обработка событий. Не вижу трудностей для:
промежуточное представление, используемое компиляторами, в котором каждой переменной значение присваивается лишь единожды. Переменные исходной программы разбиваются на версии, обычно с помощью добавления суффикса, таким образом, что каждое присваивание осуществляется уникальной версии переменной.
Но в обсуждаемой статье:
Формулы хорошо формализуются и при одинаковых входных данных возвращают одинаковые выходные.Про эту проблему для событий и ГСЧ уже говорил в данном обсуждении.
Еще раз уточню: исхожу из определения обсуждаемой статьи.
del
Так вышло, но детерминистическая генерация псевдо-случайных чисел тоже функциональна по своей природе. Недетерминизм возникает лишь на входе в цепочку генератора, а это может быть точкой входа в функциональную программу.
Для RosettaCode я писал "Змейку" на Haskell. И там генерация случайного расположения "еды" для змеи вся прячется в одной полиморфной функции в рамках MonadRandom, так как будто бы генератор у нас есть и он возьмёт затравку, когда понадобится, но нам пока не важно откуда. При этом код выглядит так, будто бы в мире змейки уже существуют все будущие координаты в которых еда "случайно" появится (как в беременной самке тли хранятся уже беременные самки и т.д.), это следствие ленивости.
Когда же, наконец, мы в точке входа в программу (функция main) инициализируем змейкин мир, тогда в качестве экземпляра MonadRandom оказывается IO (без неё-то всё равно никак) и вот ни пользователь, ни змейка уже "не знают" где появится очередной фрукт.
Это может показаться трюкачеством, но по-существу вся программа говорит только о том, что делать змейке, получившей сигнал от пользователя или при встрече с едой, и не более. Откуда возьмутся еда и сигналы пользователя, змейке знать не обязательно, об этом заботится только функция main, которая отправляет её в "реальный мир", либо в его детерминистическую эмуляцию (монаду ST) для отладки.
Этот пример не призван показать превосходство ФП перед императивным программированием. Он про то, что многие как кажется чисто императивные задачи гладко ложатся на функциональную парадигму, не требуя лишних шаманств и костылей (если не считать костылями то, что не понимаешь с первого раза).
при одинаковых входных данных не получим одинаковые выходных.Это допустимо в ФП? В определении сказано обратное.
Это допустимо в ФП? В определении сказано обратное.
Тут надо учитывать, что входными данными можно считать все действия пользователя, состояние файлов в файловой системе, данные в базе данных, даже генератор случайных чисел. Если входные данные абсолютно одинаковые получим одинаковый результат.
Разумеется, обычно нет необходимости точно повторять все выходные данные для всей программы, достаточно, чтобы каждая часть программы давала одинаковый результат при одинаковых входных данных.
Тут надо учитывать, что входными данными можно считать все действия пользователя, состояние файлов в файловой системе, данные в базе данных, даже генератор случайных чисел.В результате получим проблемы по обработке событий в ходе вычислений. Еще один интересный вопрос: как при таком подходе возможна многопоточность? Мьютекс — это входные данные?
В результате получим проблемы по обработке событий в ходе вычислений
Какого именно рода проблема? Дайте реальный пример.
как при таком подходе возможна многопоточность?
Прекрасно возможно, разумеется, если разумно использовать внешние ресурсы (не завязываться на ресурсы не поддерживающие многопоточность и т.п.). Опишите какие проблемы вы тут видите.
Мьютекс — это входные данные?
Вы про мьютексы операционной системы? Нет, но языки высокого уровня (не только функциональные) от них напрямую не зависят.
Вы про мьютексы операционной системы?Я про средства синхронизации внутри программы (всякие семафоры и т.д.)
Опишите какие проблемы вы тут видите.Обычные проблемы синхронизации: гонки, общая область памяти для обмена данными между потоками, т.е. глобальные переменные и запоминание текущих состояний, и т.п.
Какого именно рода проблема? Дайте реальный пример.
Выше приводил пример:
Простейший пример: функция последовательными приближениями долго вычисляет результат, мне надоело ждать, нажал кнопочку, функция должна вернуть, что успела вычислить на этот момент.
вижу только одно решение:
повторять
список_аргументов := чистая_функция_очередное_приближение (список_аргументов);
до_той_поры_пока чистая_функция_точность_достигнута (список_аргументов)
или кнопочка_нажата;
Т.е. две чистых функции, но всю программу в виде читой функции не оформить.
У вас и так уже кнопочки и GUI есть, значит, там заведомо есть что-то нечистое.В этом я вижу проблему. Если функция
чистая_функция_очередное_приближение надолго задумывается, то в императивном языке вставлю в нее Application.ProcessMessages, чтобы нажатие кнопочки почувствовала. А в ФП моя функция перестанет быть чистой.
А нас в школе эта задачка рассмтривалась не то на третьем, не то на четвёртом занятии при использовании RL'я (такой очень-очень урезанный Lisp, где нет даже строк и чисел).
И новички без опыта программирования — писали вообще без вопросов. Вот как раз людям с опытом программирования их опыт сильно мешал.
Выше обсуждается другой пример — решето Эратосфена. Этот быстрый алгоритм в чистой функциональщине очень сложно сделать. Придется тупо циклы/переменные эмулировать.
Придется, но это, правда, не "очень сложно"!
Так никто пока и не привел чего-то, работающего за n log log n. Это далеко не тривиально вложенные циклы эмулировать на рекурсии.
Вот решение, вполне прямолинейное и наивное.
import Control.Monad.Primitive
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as M
eratosphenesArray :: Int -> IO (M.MVector (PrimState IO) Bool)
eratosphenesArray size = M.replicate size True >>= sieve 2
where
sieve k m
| k*k >= size = return m
| otherwise = do
next <- M.read m k
m <- if next then fill (2*k) k m else pure m
sieve (k+1) m
fill n k m
| n+k > size = return m
| otherwise = M.write m n False >> fill (n+k) k mзаполняет массив значениями True и False согласно оригинальному замыслу, в двух вложенных циклах (sieve и fill). Сигнатура страшная, но алгоритм прост как пробка.
Если надо список простых чисел (индексы со значениями True), то можно написать такое:
eratosphenes :: Int -> IO [Int]
eratosphenes size = do
a <- eratosphenesArray size
elemIndices True . V.toList <$> V.freeze aРезультаты прогона на ноуте (сплошная линия — n*log(log(n))):
Немного прокомментирую это решение. Я использовал Data.Vector.Unboxed.Mutable только для эффективности. От этой структуры здесь лишь конструктор M.replicate и функции доступа M.read b M.write. На месте этой структуры могли быть немутабельные векторы, Array (или даже список со всеми вытекающими проблемами эффективности). Программа и её результат бы от этого не изменились, только сигнатура. И то, её я не писал вручную, мне рассказал о ней компилятор :)
Именно этот выбор определил то, что результат будет "жить" в IO. Но ровно эту же программу можно погрузить в чистую ST, в любом случае, она принципиально императивна, что не помешало мне реализовать её в Haskell.
Циклы реализованы через рекурсию, вполне прямолинейно, в виде хвостового вызова. Из магии только монадические штучки >> и >>=, которые можно рассматривать как пайпы.
И, наконец, я нарочно написал тело цикла sieve так, чтобы он "выглядел" как изменение переменной m, чтобы показать, что если уж мы мыслим наш алгоритм императивно, то его можно и выразить императивным кодом, не изменяя принципам ФП. Мы не монахи и императивность не грех, если всё делать аккуратно, с благословения компилятора.
В бенчмарке использовался вариант с преобразованием в список, чтобы честно. Оно добавило константу, но оставило асимптотику.
Это да. Мне хотелось продемонстрировать не столько чистое ФП, сколько его выразительность и гибкость. Если требуют решето именно Эратосфена и именно двойным циклом и именно с вычёркиваем, то… и это можно.
А так, есть классные функциональные решения тут и тут. Но они уже не совсем то решето, о котором обычно рассуждают.
Для своих нехитрых нужд я бы взял ваш однострочник и не заморачивался. Для криптографии какой-нибудь — быстрый императивный код через FFI, но я в ней мало смыслю, если честно.
Я имел в виду не задачу криптографии в целом, а генерацию простых чисел (если таковая, действительно ставится при факторизации больших чисел, опять же, могу напутать по незнанию). Эта генерация, по существу, чиста и может быть встроена в чистый код, но имплементирована может быть как угодно, лишь бы эффективно. Впрочем, тут мне лучше умолкнуть.
если таковая, действительно ставится при факторизации больших чиселВесь смысл использования больших простых чисел в крипте — в использовании настолько больших чисел, чтобы факторизация не работала, однако.
Ну да, но их же нужно откуда-то брать. И при этом не забивать память гигами нулей и единиц, используя решето, и не тратить на это даже секунды. Я далёк от теории чисел, но понимаю, что есть более эффективные способы, хотя бы, вероятностные — генерим случайное большое число и тестируем каким-нибудь Миллером-Рабином.
STM по-прежнему находится в центре интенсивных исследованийВидимо технология еще слишком молодая для тотального использования.
А в чём проблемы?
Выше приводил пример.
Ну офигеть недостаток.М.б. нет, но из общих соображений многие молодые технологии бывают несовершенными. В любом случае выбор желателен: чем больше возможностей — тем лучше.
Как принято в науке, начинём с определений. Классичесткое определение ООП включает в себя следование принципам наследования, инкапсуляции и полиморфизма. Но если у нас нет одного из этих составляющих, будет ли это ООП? И если нет, то что это будет? Пока занудная часть аудитории зависла над этим непрактичным и ничего нам не дающим вопросом, вспомним, что было до ООП. А до него было процедурное программирование. И основная идея ООП на тот момент была в связи данных и функций для их обработки. Идея простая, но довольно революционная, сложно представить насколько, но об этом позже.
Объединение вместе данных и функций также изначальной идеей ООП не являлось. См. Alan Kay definition of object orintied или, например, Джо Армстронг интервьюирует Алана Кея, насколько я помню, от части в этом видео Алан рассказывает какие идеи вкладывал в это понятие, и что его парадигма должна была привнести в мир большее, чем язык Симула, в котором впервые была реализована модель объектов
Споры об ООП vs ФП считаю бессмысленными по следующим причинам
— Конечно же, каждый понимает под этими терминами что-то своё, только что мы вот уже 3 определения выделили.
— Есть более важные вещи которые нужно изучать чтобы писать качественный код, вот ими как раз стоит заниматься.
— ООП и ФП не противоречат друг другу по своей натуре. Erlang — отличный пример ФП языка сохранившего и до сих пор полноценно релизующиго изначальные идеи ООП благодаря наличию легковесных, независимых, общающихся между собой объектов. Объектами в данном случае являются легкие независимые потоки, который обмениваются сообщениями, и перезапускать который можно прямо в рантайме не ломая систему
Ну и да, холиварная тема далее — по поводу процедурного программирования, оно никуда не делось. До сих пор есть огромная кодовая база написанная и пополняющаяся кодом в процедурном стиле, будь это Java, PHP, или что ещё, экземпляры классов, часто представляют собой лишь набор связанных(или нет) данных которые вытягиваются и устанавливаются через геттеры/сеттеры из внешних процедур. Это лишь ещё одно дополнение к моему тезису о безполезности споров ООП vs фп.
Вторая глава — построение абстракций с помощью данных, хоть и похоже на ООП, но не про него. Современное, общепринятое понятие ООП обязательно включает в себя полиморфизм, инкапсуляцию и наследование. При абстрагировании с помощью данных используется максимум — инкапсуляция.
Где про это в SICP написано?
Но, если вы увидите как сделать вызов (пусть ИмяП (функция-создатель параметры)) а чтобы потом работал вызов (пусть результат (имяМетодаИмяП параметры)), то неужели будет трудно сделать двух таких функций-создателей, что они будут принимать разные параметры, функция-создатель-сын внутри вызовет функцию-создатель-отец (привет наследование), а вызов имяМетода будет корректно работать с результатами обеих функций-создателей — в том числе и через внутреннюю ссылку на результат из функции-создателя-отца (привет полиморфизм)?
Когда я пишу бекенд на NodeJS, он сам собой как-то получается в функциональной парадигме.
Мне доводилось видеть некоторое дерьмо, когда бекенд писали на, простите за ругательство, недостойное приличного человека, — "NodeJS". В этом контексте данное предложение невольно вызывает судорожный смех.
Хватит спорить про функциональное программирование и ООП