Pull to refresh

Comments 28

Очень интересная статья, спасибо. Побольше бы такого контента на Хабре!
А все-таки интересно, насколько быстро такая реализация работает по сравнению с той статьей, где на C? Вы не пробовали замерить время на аналогичных примерах?

Статья чудесная, и хочется верить, что подобная компиляторная магия работает, но все-таки есть сомнения, в том что все композиции происходят бесшовно.

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

Сравнения с программой на С я не проводил, хотя и правда это интересно.


Я собрал тестовую задачу в которой склеил все программы-примеры и умножил моноидально ещё 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 сек на все сто прогонов!
С решением на Питоне для этого же компьютера я не сравнивал, но для меня было главное не победить кого-то. Основная задача — убедиться в том, что не изменяя принципам чистого функционального программирования, можно выбирать максимально подходящий вычислительный процесс, а так же что моноидальное решение легко расширяется и способно использовать эффективную внешнюю память.

UFO just landed and posted this here

Добавил в статью ссылку на репозиторий.

UFO just landed and posted this here
Постскриптум прекрасен! Как и вся статья, по-больше бы такого на Хабре, спасибо!
очень хорошо показаны сразу несколько реализаций стековой виртуальной машины.
Причём легко расширяемой!
Поучительно. Создается какое-то смутное впечатление, что программирование (структурирование и осмысление задачи) в терминах моноидальных типов, их комбинаций и морфизмов очень близко духу и сути ФП вообще :)

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

Честно всё прочитал, но увы, мало что понял. Я хаскелем только начинаю интересоваться, всё всерьёз никак нет времени взяться. Статья несколько не моего уровня. Так что закинул к себе в закладки и буду возвращаться ещё не раз и не два. Но один серьёзный вопрос всё-таки возник. Скажите, такой как в этой статье сильно алгебраизированный тип рассуждений и разработки, это норма в хаскеле (и вообще в ФП)? Или это во-первых достаточно специфическая задача и во-вторых именно такой стиль Вы хотели показать?

Рад, что материал вызвал любопытство, значит, вы подошли к важному моменту и, возможно, готовы нырнуть в новую область. Алгебраический подход, действительно, очень свойственен функциональному программированию вообще и программированию на Haskell в частности. Он пронизывает всю архитектуру и экосистему языка, от системы типов до базовых принципов построения программ. Попытки просто взять и начать программировать по рецептам, как это можно делать в Javascript и Python, для Haskell быстро приводят к отторжению: сложно, неудобно, непонятно, не нужно. Если зацепило или соответствует складу характера, то наработка опыта приводит к глобальной перестройке подхода к разработке — к той самой математической магии. Хорошо это или плохо, не берусь судить, но из преимуществ отмечу: это последовательный подход, опирающийся не на опыт или эмпирику, а на строгие проверяемые рассуждения; он учит подмечать общие структуры и схемы вместе с их свойствами; он соответствует тому, что называется computer science.

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

Понимаете, у меня сейчас серьёзная проблема. Внуку подходит возраст, когда его надо уже приобщать к чему-то в этой проклятой жизни интересному. Вот я и думаю с чего начать… С кошерного, православного и духоскрепного С++ (ассемблер PDP-11 с которого начинал я сам, даже не рассматривается)? Или с жесткого, хулиганского и нигилистического хардкора типа хаскеля? Что такое группа, подгруппа и даже смежные классы, он благодаря моим усердным молитвам Одину и Джа, уже знает. Молодой да ранний :) Хочется чтобы мужик если уж не стал математиком, то во всяком случае умел в математике ориентироваться и применять её к практическим задачам. Ну и разумеется умение программировать, это вообще даже не обсуждается. Эта Ваша статья огромный плюс в пользу выбора хаскеля. Я мало что встречал по программированию столь же красивое. Беда в том, что хаскеля я не знаю от слова совсем. И освоить как следует тоже хронически не хватает времени… Я таварисчь очень и очень низкоуровневый. Между паяльником и клавиатурой, даже не знаю кто я больше, электронщик или программист. Плюс добротное, советское физико-математическое образование. Таких требуется не слишком много, но если уж потребовался, то специалист по рисованию формочек на джаваскрипте его никак не заменит. А такие как я в основном все уехали. Вот и приходится вместо тихой спокойной пенсии, за всех отдуваться. Где уж тут освоить что-то новое, ради своей бессмертной души и во благо единокровного внука… Вобщем просто интересно что Вы посоветуете. До нового года пока не горит. На новый год я хочу ему подарить хороший ноут, и с этого времени плотненько начать процесс приобщения. Вопрос С ЧЕГО это начинать…

Математика, по моему мнению — это, в первую очередь, дисциплина ума, во вторую — красота и только в третью — непосредственная польза. Поэтому приобщение к ней это благо, даже если математика не станет профессией. Хаскель и подобные языки вовсе не хулиганские: они жестко требуют согласованности всех частей программы. Строить архитектуру по принципу: "я художник, я так вижу", в них не получится. В JavaScript — можно, в С очень можно. Кривые хаки, гениальные хаки, если они удовлетворяют основному критерию — это работает, становятся классикой и живут десятилетиями, и это круто! ФП про другое. Огород абстракций сам по себе не нужен, важнее связи между ними и универсальные свойства, выходящие за пределы конкрентого представления. Тогда программирование становится исследованием предметной области, вместо набора рецептов. Правда, это интересно сильно не всем, но именно из исследований вырастают новые технологии. Моё убеждение: программиста (молодого человека) нужно знакомить со всеми парадигмами и предоставить выбор по складу ума и вкусу. Я предложил бы набор простых задач (из RosettaCode, например) дать решить на js, (C или Python) и на PureScript (Haskell) и пусть само сложится ощущение от этих подходов.

Для десяти, боюсь, чистое ФП жестковато будет. Лучше JavaScript или Python в котором показывать лямбды, отображения, свертки и т.д. Так у ученика больше свободы, а привычки вырабатываются.

Нафиг. Это только мозги калечить. Разве что каждый раз объяснять, что подобные языки только чтобы быстро написать что-то не очень большое и не очень сложное. По моему опыту, если нет сильной статической типизации, для серьёзных проектов язык непригоден. А показывать лямбды и свертки можно и в хаскеле. Благо с jupyter он дружит, что сильно облегчает процесс.
С одной стороны погрузить ребенка в «мир» функционального программирования на самой ранней стадии, когда его разум еще не «испорчен» естественной концепцией императивного программирования (утонуть в которой ему не удастся избежать начиная со школьных уроков информатики) имеет смысл. С другой стороны мне кажется, эти знания, наверное, навряд ли понадобятся и будут полезны ему в ближайшие 8 лет — не знаю.

А как научить? Если выдвигаться в сторону ФП, то мне кажется лучше все же давать язык в котором есть алгебраическая система типов (т.е. Haskell, а не Lisp допустим), т.к. она сама по себе играет большую роль в программировании. Базовый учебник по Haskell от начальных понятий до продвинутых тем — можно взять wikibook.

А вообще, по-правильному ФП надо начинать с комбинаторной логики и лямбда-исчисления — те основы (до комбинатора неподвижной точки и стратегий редукции лямбда-термов), которым учат студентов до того, как давать просто программирование в Haskell каких-то задачек. На мой взгляд это темы как раз для ребенка — стоит только правильно заинтересовать: ясность и простота концепций хорошо ляжет на такой же ясный незамутненный ум. И этот опыт как раз будет играть и как математический бэкграунд (хотя в школе тоже не понадобится). Подходящий (и на русском) базовый материал, наверное, вот (можно использовать и для самостоятельного изучения). Страничка курса — 2015 (который на видео), 2018 (только файлы).

Это большая и жутко интересная тема. Как активно преподающий программирование и студентам (ФП) и школьникам (кружок программирования), скажу, что большее значение имеют интересные задачи (не посчитать, а построить) и быстрый отклик обучающей среды (графика, интерактив), нежели язык. Красиво работать можно в любом языке. Но учащиеся ценят свободу и "настоящесть", так что Scratch не катит. И черепашья графика становится интересной после того, как черепашку они построили сами и "учат" её, понимая возможности и ограничения. Haskell дает невероятную свободу только после принятия его ограничений (как в боевых искусствах). Детям это непросто, может отпугнуть. Я привожу примеры на нём, чтобы "показать кунгфу" — то, к чего можно достичь.

P.S. Да, насчет проблем чисто воспитательных не беспокойтесь. Я его уже учил рукопашке и в школе он всем п@зды даёт. Так что знает, что деда Женя фигни не посоветует. Вопрос ЧЕМУ учить… Я сам воспитан на классике. Но то что функциональщина это наше будущее, ни капли не сомневаюсь, по множеству причин. Вопрос КАК этому ребёнка научить, если сам этим не особо владею…
Ещё вопрос вытекающий из первого. Народ, если кто реально в таком стиле что-то пишет. Как, обратное влияние ощущается? В смысле помогает ли использование такого стиля лучше понимать алгебру (а пожалуй и вообще математику)?
Скорее обратное: понимание математики позволяет лучше понимать такой вот стиль.

Думаю, тут взаимные процессы. Работа в Haskell или PureScript — это живая математика, абстрактная алгебра, с которой можно экспериментировать, а значит, лучше понимать её на уровне "спинного мозга". По крайней мере, у меня — так.

PureScript это спасибо. Слыхал про него немного, сейчас обязательно гляну подробнее. Веб-программированием я тоже немного занимаюсь, хотя и чисто для себя(хотя и надеюсь кое-что из своих поделок продавать). Сейчас пишу на typescript. Очень интересно было бы иметь инструмент не только помогающий писать код, но и развивающий мозги.
Sign up to leave a comment.

Articles