Comments 28
Статья чудесная, и хочется верить, что подобная компиляторная магия работает, но все-таки есть сомнения, в том что все композиции происходят бесшовно.
В вашем же коде например есть стек представлений списком. И в силу иммутабельности, каждая команда машины, изменяющая стек означает создание нового списка с соответствующими аллокациями памяти. Это действительно как-то оптимизируется в одну операцию, и все эти аллокации исчезают?
Сравнения с программой на С я не проводил, хотя и правда это интересно.
Я собрал тестовую задачу в которой склеил все программы-примеры и умножил моноидально ещё 10000 раз.
test = stimes 10000 $
push 8 <>
dup <> fact1 <> swap <>
dup <> fact2 <> swap <>
dup <> fact3 <> swap <>
push 54 <> gcd1 <>
dup <> push 20 <> powХвала ленивым вычислениям — этот монстр не создавался в памяти ни разу!
При запуске получилось 3 миллиона шагов выполнения программы.
Простое вычисление — 1.26 секунд
Простое вычисление, компиляция с флагом -O2 — 0.47 секунд
Простое вычисление (в монаде IO, -O2) — 0.35 секунд
Вычисление с логированием числа шагов (-O2) — 1.28 секунд
Вычисление с логированием числа шагов и кода (-O2) — 2.62 секунд. Замедление связано с ленивостью кортежа.
Вычисление с логированием используемой длины стека (-O2) — 65.24 секунд. Замедление связано с вычислением длины списка.
Вполне неплохо, в монаде IO компилятор оптимизирует вычисления максимально.
Наивная реализация решета эратосфена требует для массива 65000 ячеек 16 миллионов шагов и каждый в десятка два инструкций, так что, скорее всего, моя реализация здорово уступит решению на С: там прямая работа с памятью, а у меня — программная реализация вектора. Мы в разных категориях, и задачи у нас разные.
Моноид в категории Клейсли — это круто!!!
Посвятил часок вечером пятницы написанию варианта интерпретатора с внешней памятью (он в находится в репозитории). Разница в коде только в том, что команды PUT, GET, PUTI и GETI поселились в монаде IO, в которой есть возможность доступа к Vector.Mutable. После чего можно было приступить к тесту решетом Эратосфена.
При тех же условиях, что в статье про поросят (заполнение решетом памяти в 65536 ячейки, сто запусков):
чистый вариант (один прогон) — 43 сек! 100 прогонов — больше часа! Хаскель отстой, ФП — сферический конь в вакууме и т.д…
вариант с мутабельным вектором (тоже чистый, но запускаемый в монаде IO) — 9 сек на все сто прогонов!
С решением на Питоне для этого же компьютера я не сравнивал, но для меня было главное не победить кого-то. Основная задача — убедиться в том, что не изменяя принципам чистого функционального программирования, можно выбирать максимально подходящий вычислительный процесс, а так же что моноидальное решение легко расширяется и способно использовать эффективную внешнюю память.
Причём легко расширяемой!
Эпичная статья! Спасибо, я получил огромное наслаждение от прочтения.
Рад, что материал вызвал любопытство, значит, вы подошли к важному моменту и, возможно, готовы нырнуть в новую область. Алгебраический подход, действительно, очень свойственен функциональному программированию вообще и программированию на Haskell в частности. Он пронизывает всю архитектуру и экосистему языка, от системы типов до базовых принципов построения программ. Попытки просто взять и начать программировать по рецептам, как это можно делать в Javascript и Python, для Haskell быстро приводят к отторжению: сложно, неудобно, непонятно, не нужно. Если зацепило или соответствует складу характера, то наработка опыта приводит к глобальной перестройке подхода к разработке — к той самой математической магии. Хорошо это или плохо, не берусь судить, но из преимуществ отмечу: это последовательный подход, опирающийся не на опыт или эмпирику, а на строгие проверяемые рассуждения; он учит подмечать общие структуры и схемы вместе с их свойствами; он соответствует тому, что называется computer science.
Рад, что материал вызвал любопытство, значит, вы подошли к важному моменту и, возможно, готовы нырнуть в новую область.
Понимаете, у меня сейчас серьёзная проблема. Внуку подходит возраст, когда его надо уже приобщать к чему-то в этой проклятой жизни интересному. Вот я и думаю с чего начать… С кошерного, православного и духоскрепного С++ (ассемблер PDP-11 с которого начинал я сам, даже не рассматривается)? Или с жесткого, хулиганского и нигилистического хардкора типа хаскеля? Что такое группа, подгруппа и даже смежные классы, он благодаря моим усердным молитвам Одину и Джа, уже знает. Молодой да ранний :) Хочется чтобы мужик если уж не стал математиком, то во всяком случае умел в математике ориентироваться и применять её к практическим задачам. Ну и разумеется умение программировать, это вообще даже не обсуждается. Эта Ваша статья огромный плюс в пользу выбора хаскеля. Я мало что встречал по программированию столь же красивое. Беда в том, что хаскеля я не знаю от слова совсем. И освоить как следует тоже хронически не хватает времени… Я таварисчь очень и очень низкоуровневый. Между паяльником и клавиатурой, даже не знаю кто я больше, электронщик или программист. Плюс добротное, советское физико-математическое образование. Таких требуется не слишком много, но если уж потребовался, то специалист по рисованию формочек на джаваскрипте его никак не заменит. А такие как я в основном все уехали. Вот и приходится вместо тихой спокойной пенсии, за всех отдуваться. Где уж тут освоить что-то новое, ради своей бессмертной души и во благо единокровного внука… Вобщем просто интересно что Вы посоветуете. До нового года пока не горит. На новый год я хочу ему подарить хороший ноут, и с этого времени плотненько начать процесс приобщения. Вопрос С ЧЕГО это начинать…
Математика, по моему мнению — это, в первую очередь, дисциплина ума, во вторую — красота и только в третью — непосредственная польза. Поэтому приобщение к ней это благо, даже если математика не станет профессией. Хаскель и подобные языки вовсе не хулиганские: они жестко требуют согласованности всех частей программы. Строить архитектуру по принципу: "я художник, я так вижу", в них не получится. В JavaScript — можно, в С очень можно. Кривые хаки, гениальные хаки, если они удовлетворяют основному критерию — это работает, становятся классикой и живут десятилетиями, и это круто! ФП про другое. Огород абстракций сам по себе не нужен, важнее связи между ними и универсальные свойства, выходящие за пределы конкрентого представления. Тогда программирование становится исследованием предметной области, вместо набора рецептов. Правда, это интересно сильно не всем, но именно из исследований вырастают новые технологии. Моё убеждение: программиста (молодого человека) нужно знакомить со всеми парадигмами и предоставить выбор по складу ума и вкусу. Я предложил бы набор простых задач (из RosettaCode, например) дать решить на js, (C или Python) и на PureScript (Haskell) и пусть само сложится ощущение от этих подходов.
Для десяти, боюсь, чистое ФП жестковато будет. Лучше JavaScript или Python в котором показывать лямбды, отображения, свертки и т.д. Так у ученика больше свободы, а привычки вырабатываются.
А как научить? Если выдвигаться в сторону ФП, то мне кажется лучше все же давать язык в котором есть алгебраическая система типов (т.е. Haskell, а не Lisp допустим), т.к. она сама по себе играет большую роль в программировании. Базовый учебник по Haskell от начальных понятий до продвинутых тем — можно взять wikibook.
А вообще, по-правильному ФП надо начинать с комбинаторной логики и лямбда-исчисления — те основы (до комбинатора неподвижной точки и стратегий редукции лямбда-термов), которым учат студентов до того, как давать просто программирование в Haskell каких-то задачек. На мой взгляд это темы как раз для ребенка — стоит только правильно заинтересовать: ясность и простота концепций хорошо ляжет на такой же ясный незамутненный ум. И этот опыт как раз будет играть и как математический бэкграунд (хотя в школе тоже не понадобится). Подходящий (и на русском) базовый материал, наверное, вот (можно использовать и для самостоятельного изучения). Страничка курса — 2015 (который на видео), 2018 (только файлы).
Это большая и жутко интересная тема. Как активно преподающий программирование и студентам (ФП) и школьникам (кружок программирования), скажу, что большее значение имеют интересные задачи (не посчитать, а построить) и быстрый отклик обучающей среды (графика, интерактив), нежели язык. Красиво работать можно в любом языке. Но учащиеся ценят свободу и "настоящесть", так что Scratch не катит. И черепашья графика становится интересной после того, как черепашку они построили сами и "учат" её, понимая возможности и ограничения. Haskell дает невероятную свободу только после принятия его ограничений (как в боевых искусствах). Детям это непросто, может отпугнуть. Я привожу примеры на нём, чтобы "показать кунгфу" — то, к чего можно достичь.
Думаю, тут взаимные процессы. Работа в Haskell или PureScript — это живая математика, абстрактная алгебра, с которой можно экспериментировать, а значит, лучше понимать её на уровне "спинного мозга". По крайней мере, у меня — так.
Стековая машина на моноидах