Pull to refresh

Comments 128

Говорят, чтобы программировать на Haskell, не нужно знать о теории категорий. Но я не понимаю почему! Ведь идея простая: объекты и морфизмы с некими законами, можно выучить за пол часа.

К тому же, зная ее отпадает необходимость в метафорах для объяснения многих вещей. Например, есть в Haskell класс функтор, у которого имеется функция fmap.

fmap :: Functor f => (a -> b) -> f a -> f b

По-простому, она принимает чистую функцию и обернутое значение, разворачивает значение, применяет к нему нашу функцию, и заворачивает назад. Ну что это за детский сад з коробочками?

Функтор — это морфизм из одной категории в другую. Скажем, у нас есть категория Hask, где объекты — это типы, а морфизмы — функции. А теперь представим, что это не единственная категория, бывают и другие. Например, категория Maybe. На самом деле она подкатегория Hask, но это неважно. Для каждого типа A из Hask у нас есть соответствующий тип (объект) Maybe F в категории Maybe, и для каждой функции (морфизма) A -> B, функция Maybe A -> Maybe B.

Эти две категории формируют категорию категорий, где объекты — это категории, а морфизмы… (барабанная дробь) функторы.

Чтобы быть функтором, нужно уметь трансформировать объекты из A в Maybe A, и морфизмы из A -> B в Maybe A -> Maybe B. Первым занимается конструктор типов, например из Int мы можем сделать Maybe Int. Вторым же — функция fmap. Давайте посмотрим еще раз на ее тип: на самом деле она принимает один агрумент — функцию, и делает из нее функцию другой категории.

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

То, что мы можем построить категорию надо фукторами… Ну. Замечательно. Но что с того? Если я пишу, допустим, текстовый редактор, как это мне поможет?
На мой взгляд это упрощает ментальную модель происходящего. Мне, например, легче умственно перенести функцию из одной категории в другую, чем применять метафоры, которые, к тому же, не всегда подходят. Попробуйте поразворачивать коробочки с instance Applicative ((->) r), например.

> (+) <$> (*2) <*> (+10) $ 3
19
Но тут встаёт следующий вопрос: зачем разворачивать всё в коробочки и зачем переносить функции из одной категории в другую? Существует ли какой-нибудь существенный практический пример для этого?
Практический смысл функторов объяснить очень просто. Смысл в повторном использовании функций, которые у нас уже определены.

1. У нас есть нумерические типы (Int, Integer, Double, Float), для которых уже определена функция сложения (+).

2. У нас есть «обертки» для нумерических типов (например, список нумерических значений [1, 2, 3, 4], или значение Just 5 типа Maybe).

3. При помощи функтора fmap мы можем повторно использовать уже имеющуюся у нас функцию сложения (+) для «обернутых» нумерических значений, вместо того, чтобы писать новую функцию:
fmap (+ 1) [1, 2, 3, 4]
> [2, 3, 4, 5]

fmap (+ 1) (Just 5)
> Just 6


Применив «обертку» к типу А, мы, тем самым, получили новый тип Б. Тем не менее, мы можем, при помощи функторов, применять функции, определенные для типа А, к значениям типа Б.

Тем самым вы избавляетесь от необходимости определять отдельные функции для «обернутых» типов, что, без сомнения, уменьшит количество и времени, и кода, как при написании текстового редактора, так и при написании других программ.
А чем это всё отличается от обычного map? Или обычного цикла for?
Циклов в Хаскелле нет. А map — это просто синоним fmap для списков. Со списками вы можете употреблять как map, так и fmap, а с другими «обернутыми» значениями нужно употреблять fmap.

instance Functor [] where 
fmap = map
Вообще, одно из главных отличий функциональных языков от императивных, которое нужно понять, и которое обычно мешает императивщикам приучиться мыслить в функциональном стиле — это оперирование в терминах коллекций значений, а не на уровне отдельного значения в коллекции. То есть нужно перейти на более высокий уровень абстракции. Именно поэтому в функциональных языках нет циклов (потому что там вы думаете, что нужно сделать с каждым отдельным элементом коллекции), но есть функции высшего порядка, которые работают с коллекциями целиком.

Если пытаться подобрать аналогию из реального мира, то, когда перед функциональщиком стоит задача расставить мебель в комнате, он мыслит категориями единиц мебели (диван, стул, стол, кресло и т.д.), а императивщик — категориями частей, из которых состоит мебель (досточки, гаечки, шурупчики и т.д.). Оба подхода имеют право на существование, просто функциональный подход основан на более высоком уровне абстракции.
> Если пытаться подобрать аналогию из реального мира, то, когда перед функциональщиком стоит задача расставить мебель в комнате, он мыслит категориями единиц мебели (диван, стул, стол, кресло и т.д.), а императивщик — категориями частей, из которых состоит мебель (досточки, гаечки, шурупчики и т.д.). Оба подхода имеют право на существование, просто функциональный подход основан на более высоком уровне абстракции.

Скорее не так. «императивщик» думает: «диван двигаем сюда, потом кресло сюда, люстру прикручиваем к потолку. Нет — сначала шкаф поставим, а то диван дверной проем загораживает». А «функциональщик» так: «диван здесь, кресло здесь, шкаф тут. Вперед, компилятор, я пойду кофе попью».
Суть в том что в функциональных язык код фокусируется на результате, а в императивных — на процессе.
Суть в том что в функциональных язык код фокусируется на результате, а в императивных — на процессе.
Это уже к вопросу декларативность/императивность.
Если взять Real World Haskell, то и «функциональщик» делает точно так же. Иначе, зачем бы пришлось выдумывать do в LISP и монады (с примерно тем же сахаром в синтаксисе) в Haskell? Большинство математических алгоритмов не говоря уже о чисто технических именно так и устроены: делай это-1, потом это-2, потом это-3. Конечно, это можно перевести на язык: это-3 — штука, которая состоит из это-2 и чего-то ещё, а это-2 — это штука, которая состоит из это-1 и чего-то ещё. Но такое выражение — уже результат применения техники программирования к изначальной постановке.

Другое дело, что сообщество зачем-то поддерживает некоторую иллюзию о том, что порядок этот в императивных и функциональных языках задаётся по-разному. Но на самом деле, это же не так. Оператор последовательного исполнения ";" вполне себе можно описать в виде lambda-функции.

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

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

Так что… Ну. Не всё тут так радужно и не сводится к «вперёд, компилятор!».
Иначе, зачем бы пришлось выдумывать do в LISP и монады (с примерно тем же сахаром в синтаксисе) в Haskell?

Вы говорите про все монады или только про IO?

Что делает этот код?

cartProd :: [a] -> [b] -> [(a, b)]
cartProd l r = do l' <- l
                  r' <- r
                  [(l', r')]


См также
Я могу ошибаться, но насколько я помню историю, монады в Haskell сперва появились для описания интерфейса с системами ввода/вывода, а потом уже были перенесены на другие конструкции. То есть, первично было желание реализовать последовательности действий, с которыми были существенные проблемы.
Вы правы это было первичное назначение. Но сейчас это более общая концепция.

en.wikipedia.org/wiki/Monad_(functional_programming)#History
IMHO, это всё фигня и пассатижы. Потому что…

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

Раздел между функциональным и императивным стилями мышления лежит, определённо, в чём-то ином.

2. Циклы в функциональном программировании есть. Цикл — это же не for или while. Цикл — это повторное исполнение кода. На уровне машинных команд тоже нет никаких for или while, а циклы есть. И если я цикл записываю в виде рекурсии, то это тоже не означает, что этого цикла нет. Потому что, когда мы перейдём к определению семантики этой рекурсивной конструкции, семантика же не появляется из воздуха. Мы должны будем рассмотреть либо операционную семантику, в которой повторное применение рекурсивных функций будет просто явно прописано. Либо мы должны будем рассмотреть денотационную семантику, в которой будет явно прописан метод решения рекурсивных уравнений через поиск неподвижной точки. А это тоже, в некотором смысле цикл, потому что надо последовательно применять генерирующую функцию саму к себе, при вычислении (уж простите мне мою корявую запись) lim (n -> бесконечность) F^n(дно).
Если брать конечный результат, то да — разницы между циклами и рекурсией никакой. Но если рассматривать то, каким образом этот результат достигается, то разница есть: в циклах вы оперируете на уровне каждого отдельного значения в коллекции, а в рекурсии вы оперируете на уровне коллекции целиком. То есть разница — в уровне абстракции. Как современные императивные языки абстрагируются от машинного кода, так и функциональные языки абстрагируются от уровня отдельных элементов коллекции.
Это несколько спорное утверждение, потому что зачастую в рекурсии нужно писать что-то вроде: для первого элемента в списке сделай это, а для оставшихся элементов в списке сделай то. Чем это не работа с отдельными элементами?
Обычно это после оптимизации. Нормальная функциональная рекурсивная функция разбивает коллекцию на две части и вызывает себя два раза. В её теле особый случай не первый элемент, а коллекция из одного элемента или пустая.
В рекурсии вы оперируете правилом вывода и паттерн-матчингом, что таки работа с маленьким набором элементов коллекции. На уровне коллекции вы оперируете при использовании операций типа fold, хотя это тоже неявный цикл.
Аналогия с реальным миром такая.

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

Функциональщик
Берет пустую комнату, добавляет единицу мебели и… возвращает новую комнату но уже с мебелью. И делает он это рекурсивно: каждый раз откусывая головушку списка имеющейся мебели, пока мебель не иссякнет.
Тогда эта серия специально для вас! Возможно, вы сможете найти в ней ответы на свои вопросы, или даже реальную пользу. Я верю в автора, он потрясающе пишет на многочисленные темы, и я верю, что этот труд действительно сможет открыть новые горизонты для тех, кто захочет и разберется. Если что, в конце статьи есть ссылка на предисловие, там описана в том числе и мотивация за всем этим.
Большая часть программирования — это не столько алгоритм, сколько согласование между элементами алгоритма, он же — клей.
Собственно, функторы — один из универсальных клеев.
Например, shock_one вам привёл пример: у нас есть 4 элемента:
3, (+10), (*2) и (+).
Как нам соеденить эти разнородные элементы?
Используем 3 клея: фунткор (<$>), аппликативный функтор (<*>), аппликацию ($).
Итого, получаем
(+) <$> (*2) <*> (+10) $ 3

Вуаля!

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

Теория же категорий пришла в программирование совсем не из размышлений об облегчении труда, а для решения фундаментальной математической проблемы решения рекурсивных уравнений, определяющих некие объекты. Множество lambda-выражений задаёт нечто вида T: T -> T, и в полный рост встаёт вопрос: что, чёрт возьми, такое это самое T? Явно не обычное множество. Вот, в рамках категорий и семантических доменов ответ на вопрос даётся. Функторы и натуральные преобразования возникают уже в рамках самой теории категорий, как метод универсального языка для описания категорий. Насколько я могу дилетантски судить, это всё связано с ответов на вопрос: а можем ли мы задавать объекты категорий при помощи одних лишь морфизмов. Но как мне это всё может помочь программировать? Вот чего я не понимаю. Все примеры, которые приводятся, ну просто очень искусственные. Кроме, пожалуй, списков. Но это такая мелкая частная проблема, что совсем не интересно.

Интересным был бы пример какой-нибудь такой: допустим, нам надо посчитать спектр матрицы, функторы помогут нам в этой задаче так-то и так-то. Или во внедрении этой задачи в другую задачу, если речь идёт о клее. Ну, или не знаю… При перемножении больших чисел через преобразование Фурье. Ну, то есть, в задаче, где есть реальные проблемы со сложностью кода. Было бы неплохо показать, в каком месте теория категорий срабатывает лучшее теории типов.
Попытаюсь вам объяснить. Но для этого вам нужно попытаться переформулировать свой вопрос «В какой конкретной задаче мне может помочь функтор?» и сформулировать его на более высоком уровне абстракции: «Как функторы могут мне помочь в программировании вообще?» (т.е. в решении любых задач, а не какой-то конкретной).

Что такое функторы, монады и прочие концепции в Haskell? Это шаблоны, которые реализованы в языке для того, чтобы нам было легче решать различные классы задач:

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

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

ОК, у нас есть значения, обернутые в контекст. Но что нам делать, если мы хотим как-то трансформировать это значение? Можно написать отдельные функции для трансформации значения, «обернутого» в контекст. Но можно не плодить лишний код, а использовать еще один шаблон — функторы. С помощью этого шаблона мы можем применять функции, определенные для значений без контекста, к значениям, обернутым в контекст. И опять таки — мы можем использовать этот шаблон во всех случаях, когда нам нужно применять «чистую» функцию к значениям, «обернутым» в любой контекст.

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

Можно ли программировать на Haskell, не зная или не понимая этих концепций? Да, можно. Но их знание и понимание облегчает программирование.

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

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

И позвольте, в заключение, «перевести» некоторые ваши вопросы на «ООП-язык», чтобы вы лучше поняли, что рассматриваемые понятия — это не алгоритмы, а концепции:

То, что мы можем ввести классы объектов… Ну. Замечательно. Но что с того? Если я пишу, допустим, текстовый редактор, как это мне поможет?


Повторюсь: вот пишу я текстовый редактор, где мне могут пригодиться классы объектов?


Интересным был бы пример какой-нибудь такой: допустим, нам надо посчитать спектр матрицы, объекты помогут нам в этой задаче так-то и так-то. Ну, или не знаю… При перемножении больших чисел через преобразование Фурье. Ну, то есть, в задаче, где есть реальные проблемы со сложностью кода. Было бы неплохо показать, в каком месте объектный подход срабатывает лучше теории типов.


Надеюсь, стало понятнее ;)).
Эти математические теории помогли создать эти языковые концепции, но вы же можете научиться управлять самолетом, не изучая всю ту физику, которая помогла создать летательные аппараты? Конечно.
Неудачный пример. Управление самолётом требует базового понимания аэродинамики. То потом можно внезапно удивиться перед смертью, почему набирая высоту оказался в плоском штопоре… Можно, например, сказать, что оно не требует, скажем, серьезного понимания сопромата.
Я не говорю, что вы не должны знать физику вообще. Но для управления самолетом вам не нужно знать физику в объеме, который необходим для создания вами самолета.
Как вы, наверное, знаете, обычные функции в Haskell — это аналог функций в математике. Они зависят исключительно от своих аргументов, и сколько бы раз вы их ни вызывали с одними и теми же результатами, столько же раз вы будете получать один и тот же результат. Это позволяет нам получать распараллеливание вычислений «из коробки», так как нам неважно, в каком порядке будут выполняться вычисления.

IMHO, это некоторое заблуждение. Для классических математических отображений, действительно не важно, в каком порядке будут выполняться вычисления. Но lambda-выражения не задают классические математические отображения. Потому что множества таких отображений не могут быть решением уравнения (я об этом говорил раньше) T: T → T.

И для этих lambda-выражений, на самом деле, порядок вычисления (то есть, порядок beta-редукций) очень даже имеет значение. Порядок вычисления просто задаётся всегда явно, через структуру lambda-абстракций. Иначе, никакой бы разницы между foldr и foldl не было бы. Автоматического и бесплатного параллелизма тоже в функциональном программировании нет, ну, если не прибегать к старым, добрым низкоуровневым ухищрениям типа компиляции map в LLVM с последующей векторизацией. Сама же классическая структура вычисления map весьма далека от «параллельной».

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

Ну, то есть, проблема создана искусственно? Ведь, на самом деле, существуют и другие строгие высокоуровневые абстракции для алгоритмов. Допустим, есть та же CSP Чарльза Хоара, в которой вычисления — это процессы, что гораздо, гораздо, несравненно, несравненно ближе к происходящему при исполнении программ в компьютерах. Или есть, допустим, теория абстрактных машин состояний Гуревича, которая без всяческих проблем позволяет определять системы с вводом/выводом. Почему обязательно нужно так напирать именно на lambda-исчисление, как на некую uber-абстракцию, если для реального программирования требуется вводить дополнительные обёртки и прочее, прочее? Я просто до сих пор не вижу profit-а.

Повторюсь: вот пишу я текстовый редактор, где мне могут пригодиться классы объектов?

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

Так же я могу рассуждать о монадах: монады — это такой pattern, который позволяет легче описывать (исключительно за счёт синтаксического сахара, потому что описания тех же цепочек операций через >>= и return — ещё тот адский ад) вычисления, в которых необходим threading какого-нибудь состояния. Но даже для монад совершенно не ясно, какой profit можно получить от рассуждения о них в терминах теории категорий. Это всё вполне себе укладывается в теорию типов и в классы типов.

А вот уже о функторах как-то рассуждать не получается. Ну, то есть, вот абстрактно — это действительно так и есть, некая штука, которая позволяет отображать морфизмы из одной категории в другую… Но это чрезмерно абстрактное описание. Хочется конкретного примера с рассуждением в терминах функторов, отличных от fmap. Примеров мне не хватает для осознания. Как я уже говорил, я читал книгу Real World Haskell, и там что-то никаких рассуждений в терминах именно теории категорий нет. Разве только сказано, что термин «монада» взят из этой теории.

Надеюсь, стало понятнее ;)).

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

То есть низкоуровневее?
Естественнее я бы сказал. Не низкоуровневее. Вполне можно описывать процессы, события которых масштабны и абстрагируют цепочки многих других событий. Вполне можно описать нечто вроде: пользователь перепрошил свой iPhone.
Во фразе «ближе к происходящему при исполнении программ в компьютерах» я прочитал низкоуровневость. В том случае, когда сам компьютер по себе не является предметной областью.
Ну. Я имел в виду вычислительные процессы вообще, а не конкретно ассемблеры там всякие. Плохо сформулировал, прошу прощения.
Тут вопрос, кому интересно вычисление как процесс, а не его результат?
Почему бы не задуматься о том, что результатами вычисления являются процессы? Ведь, почему-то, идея о том, что результатом вычисления является функция находит отклик в умах многих :) Но на самом деле, идея о том, что результат вычисления — это процесс гораздо более естественна, как мне кажется. Потому что функцию надо к чему-то применять (а кто её применяет?). Если же размышлять в терминах процессов, то зажигание пиксела на экране в результате вычисления вполне себе естественная штука, просто эволюция одного процесса привела к формированию другого.
Нас интересует горящий пиксель или процесс его зажигания?
Горение пиксела — это тоже процесс. На интересует и то, и другое: и как он горит (это для инженеров-электронщиков), и как его зажечь (для программистов), и интерфейс между этими процессами.
«Порядок вычисления просто задаётся всегда явно, через структуру lambda-абстракций. Иначе, никакой бы разницы между foldr и foldl не было бы. „

Конечно задавая зависимости мы в какой-то мере задаем порядок вычисления. Но не полностью (например, теоретически можно вычислить при foldl f z [f1,f2] мы можем вычислить z, f1 и f2 в любом порядке и частично вычислить f по мере готовности аргументов).

Это все равно что заявлять что задание зависимостей в make file это все равно что задание порядка их сборки в командном файле.

Разумеется при каких то конкретных способах описания зависимостей им соответствует ровно один порядок вычисления. Например в языке clean для этого вводят специяльный тип World (состояние мира). Описывая зависимости типа:

НужныйМнеЧайник = ПоставленныйНаПлиту(СНалитойВодой(ПустойЧайник)) мы задаем порядок в котором мы наливаем чайник и ставим на огонь, но можем это и не делать, если нам это не важно.И поддействия внутри каждого из этих действий могут выполняться независимо друг от друга.

foldr и foldl как я понимаю управляют ассоциативностью а не порядком вычисления.
Ну. Собственно, прядок вычисления и определяется ассоциативностью.

Конечно задавая зависимости мы в какой-то мере задаем порядок вычисления. Но не полностью (например, теоретически можно вычислить при foldl f z [f1,f2] мы можем вычислить z, f1 и f2 в любом порядке и частично вычислить f по мере готовности аргументов).

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

Порядок надо фиксировать. И, поэтому, никакой параллельности именно из lambda-выражений выжать не получается. Нужны дополнительные внешние абстракции… Ну, типа параллелящего компилятора.

НужныйМнеЧайник = ПоставленныйНаПлиту(СНалитойВодой(ПустойЧайник)) мы задаем порядок в котором мы наливаем чайник и ставим на огонь, но можем это и не делать, если нам это не важно.И поддействия внутри каждого из этих действий могут выполняться независимо друг от друга.

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

«Да. Но функциональное программирование так не работает.»

Приведите определение, по которому вы не считаете приведенное функциональным программированием.
Эмс. Ну у функционального программирования есть же определение. Это lambda-абстракции, которые применяются друг к дружке и редуцируются. Чтобы Ваша формула превратилась в функциональную программу Вам надо зафиксировать способ описания абстракций и их применения. И тогда порядок будет полностью задан. Вы обязаны это сделать. Без такой определённости чайник может не никогда не закипеть, всё залипнет на каком-нибудь внутреннем цикле проверки: «а достаточно ли воды в чайнике».

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

Так в том-то и фишка. Чтобы оно (lambda-выражение) вычислилось, мы обязаны задать способ вычислений. И это часть семантики языка. Ещё раз повторюсь: ошибочно называть lambda-термы функциями. Они похожи на классические функции в математике, но таковыми не являются. Когда некто пишет в функциональном языке f: A -> B, он задаёт не отображение, а семантический домен с двумя типами и конструктором "->". Свойства у этих доменов намного более тонкие, чем свойства обычных математических функций, для которых порядок вычисления не имеет значения.
Откуда вы взяли это определение?

Вот из википедии:

«In computer science, functional programming is a programming paradigm, a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.»

Порядок вычисления может не быть частью семантики языка. Так же можно сказать, что C++ однозначно задает набор ассемблерных инструкций в которые надо превратить операторы => программировать на C++ все равно, что писать на ассемблере, к тому же последнее естественнее для компьютеров.

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

Из двух классических книг: «Типы в языках программирования» и «Design and concepts in programming languages» и из работы «Semantic Domains» Дана Скотта. Собственно, в Wikipedia написано то же самое: evaluation of mathematical functions… Каков математический смысл этого процесса оценки? Как раз цепочка beta-редукций выражения до его нормальной формы. При этом, чтобы получать нормальную форму, необходимо придерживаться определённого порядка вычислений. Если применять их произвольно и «параллельно», то в общем случае можно никогда не получить эту самую нормальную форму, то есть результат вычисления.

При этом, изменение состояний и изменяемые данные запросто можно описать кучей функциональных конструкций и вполне программировать с их применением не выходя за рамки парадигмы.
Отвечать как поможет цикл while в подсчёте Фурье пробразования — не буду. Ибо вы скажете, что это уже давно можно сделать через for.

Тем более, что основные катеории более абстрактны, чем while.
Но теория категорий может помочь и конкретно.

В императивных язках как правило мыслят линейно, ветвлением и циклами.
С помощью стрелок (Arrow) можно мыслить блок-схемно (2мерно)
www.haskell.org/arrows/syntax.html
Сложные программы куда проще писать, используя блок-схемы, чем линейно.
Многие FRP (рективное программирование — аналог программирования по запросу(dataflow programming)), основаны на стрелках. Ибо проще.

С помощью линз (которые сами основаны на функторах) в Хаскеле можно работать с данными как с объектами.

Надо обходить коллекции и деревья — испольузйте Обходители (Traversable), необходимо подсумировать что-то по коллекции или дерву — сворачивайте (Foldable).

Хотите что-то соединять — используйте моноиды.

Теория категрий — универсальные механизмы. Матеметику ж всё равно не обмануть. Так почему бы не использовать её себе во благо?!
В императивных язках как правило мыслят линейно, ветвлением и циклами.
С помощью стрелок (Arrow) можно мыслить блок-схемно (2мерно)
www.haskell.org/arrows/syntax.html
Сложные программы куда проще писать, используя блок-схемы, чем линейно.
Многие FRP (рективное программирование — аналог программирования по запросу(dataflow programming)), основаны на стрелках. Ибо проще.


Ещё раз повторю свой тезис: способ мышления программиста зависит от предметной области, а не от языка программирования. Кроме того, была огромная движуха во времена становления GUI-интерфейсов на тему программирования в виде блок-схем и прочих визуальных концепций. Систем была разработана туёвая хуча, но не одна не пошла в промышленность. Потому что сложные программы в виде блок-схем нереально сложно разрабатывать. Слишком тяжело прослеживать все эти стрелки. Стрелки в Haskell, кстати, обладают тем же самым свойством: нереально сложно понять, что же имел в виду автор. И это не зависит от привычки к программированию на Haskell. Я видел, как один адепт Haskell разбирался с кодом Frag, в котором этих стрелок очень много. Он именно что сидел и пытался на бумажке нарисовать структуру кода и частенько матерился, потому что ошибался.

dataflow programming не основан на стрелках. Там стрелки, то есть, что рисуется в виде стрелок — это совсем не стрелки Haskell, не морфизмы, а бинарные отношения, которые не являются функциями, и для которых композицию не так-то просто определить в общем виде, и автоматически они не получаются.

Теория категрий — универсальные механизмы. Матеметику ж всё равно не обмануть. Так почему бы не использовать её себе во благо?!

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

Пока все примеры с категориями, которые я видел, ограничиваются, повторюсь, какими-то примитивными задачами, в которых особенности подхода с категориями не видны.
Ещё раз повторю свой тезис: способ мышления программиста зависит от предметной области, а не от языка программирования. Кроме того, была огромная движуха во времена становления GUI-интерфейсов на тему программирования в виде блок-схем и прочих визуальных концепций. Систем была разработана туёвая хуча, но не одна не пошла в промышленность. Потому что сложные программы в виде блок-схем нереально сложно разрабатывать.
Не совсем так. То же самое FBD нашло свою нишу в промышленной автоматике за счёт довольно низкого порога вхождения и кажущейся простоты (хотя там ещё активно используются схемы релейной автоматики/ladder diagrams и нечто похожее на классические блок-схемы).

Грубо говоря, на fbd можно научить «писать» условную обезьяну и она сможет щелкать релюшкой/мигать диодом, но создание чего-либо мало-мальски сложного превращается в ад, нагромождение костылей со значительной стоимостью поддержки и модификации.

С другой стороны, аналогичные «графические» способы построения систем нашли ужасное применение в описании бизнес-процессов (см. BPMN и BPEL, но, возможно, захочется это развидеть).
1) Способ мышления всё же зависит от языка. В том числе и программирования.
Одно дело мыслить на русском, другое — на английском. Одно дело на Си, другое дело на Яве, третье дело на Хаскеле.
Не сильно, но зависит.

2) На счёт универсальности и реальности.
Функциональщики нашли 100500 способов написать функцию факториала, но были разочарованы, когда узнали, что быстро работают лишь некоторые из них, алгоритмы которых давным-давно написаны императивщиками.

3) Где возникают категории…
Тут так.
Смотрите на определение класса и что необходимо определить в инстансе.
Если вы это обеспечите, то тогда вы можете использовать всю библиотеку (а возможно даже не одну эту библиотеку).

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

Например, на заре создания Хаскеля и моднад, пришла необходимость комбинировать монады. Дабы не плодить копи-пасту, придумали самое простое (и до сих пор самое распространённое решение) — монадные трансформаторы.
Но тут возник тот же самый вопрос — дублирование кода для монад и для их трансформаторов.
Придумали новый тип данных:
newtype Identity a = Identity { runIdentity :: a }

instance Monad Identity where
    return a = Identity a
    m >>= k  = k (runIdentity m)

тогда любые монады стали лишь синонимами трансформаторов, например,
type State s = StateT s Identity

Универсальные механизмы помогают искать.
hackage.haskell.org/package/layers-0.1/docs/Documentation-Layers-Overview.html
Например, тут очень интересная документация по монадным слоям — следующий этап комбинаций монад. Открытых благодаря категориям.
Спасибо, это уже кое-что. Но, вот у тех, кто в танке (это я о себе сейчас), никак не сходится.

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

Но, ведь, на самом деле, это всё обман трудящихся. Всё равно, в итоге IO будет написана на Си и всё сведётся к обращениям к операционной системе, которая даже чисто теоретически не может быть «функциональной».

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

То есть, вроде как, понятно, что вот есть у меня задача написать текстовый редактор, замечательно. И мне говорят (условно): а ты сформулируй ей в терминах монад, функторов и морфизмов, и тогда теория категорий тебе поможет. Но я-то как раз не понимаю того, чем мне поможет формулирование этой задачи в этих терминах. Я понимаю, как мне поможет формулировка в терминах CSP. Но вот как перейти к категориям — это выше моего понимания. Хотя, повторюсь, я, хоть и с трудом, но могу понять эти все категориальные рассуждения о проблемах теории категорий. Но вот мостика с реальностью у меня не складывается. Поэтому и butt-hurt.

Снова повторюсь: почему бы кому-нибудь не взяться и не описать то, как сделать текстовый редактор на Haskell? И как в этом проекте поможет ТК?
1) На счёт «в итоге IO будет написана на Си и всё сведётся к обращениям к операционной системе, которая даже чисто теоретически не может быть «функциональной»»

а. Если мы говорим о GHC, то он написан на Хаскеле. И всё сводится не к Си, а к машинному коду. Кстати, Си тоже транслируется в машинный код. Только зачем думать в рамках регистров и тактов — ума не приложу.

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

в. Операционная система видится Хаскелю как монада состояний, то есть мало того, что видит функционально, Хаскель ещё умудряется видеть операционную систему ЧИСТОЙ (без побочных эффектов).

2) Мыслить надо категориями для того, чтобы не изобретать велосипеды каждый раз, когда надо соединить несколько элементов, а использовать готовые, эффективные и давно оттестированные.
Когда вы создаёте объект, вы его шпигуете кучей ненужного мусора для того, чтобы он мог общаться с миром (с другими объектами).
На Хаскеле, когда вы создаёте новый тип данных, вы его категориризуете (делаете, если можно, монадой, функтором, линзой, обходимым, строковым, ...) и вы можете уже голый тип данных использовать с полной эффективностью.
Вот предположим, вы пишите свой редактор.
Создали объекты — написанный_текст, сохранение стрингов
Как вы напишите сохранение?

А на Хаскеле ответ таков
data MyText = MyText  { .... }

instance Show MyText where
   show t = ....

save :: FileName -> MyText -> IO ()
save f t = saveFile f (show t)


А на ООП вы почти наверняка будете городить что-то вроде
class MyText 
{
  ....

  public function save() { .... } 
}

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

Разница к тому же ещё в том, что изначально в объект надо закладывать всё что нужно для будущей жизни, а если хочется расширить — придётся наследовать.
На Хаскеле, в данных мы храним не более, чем данные.
Подключиться к любой категории можно и потом (если это возможно). И сразу пользоваться всеми плодами библиотеки, которая использует эту категорию.
Сразу скажу спасибо за ещё более конкретный пост. Несколько прояснеяет восприятие. Но пока всё ещё butt-hurt и возражения.

1. Термин «Си» я использовал не буквально, а в качестве синонима для не функциональных «грязных» вычислений. Дело совсем не в машинном коде, а именно в модели вычислений. Операционная система не может быть «чистой» монадой состояний, хотя бы из-за необходимости поддерживать общий доступ к тем или иным системным объектам (не ООП). Поэтому, когда Haskell смотрит на ОС, как на чистую монаду состояний, это и есть «обман трудящихся». Зачем так притворяться, когда есть формальные модели вычислений, которые позволяют учесть существование ввода-вывода и взаимодействия?

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

Но, в данном случае, интересно, какие именно размышления в терминах ТК приводят именно к такому вот решению в Haskell? Лично мне кажется, что это простой здравый смысл. Хорошо разработанные интерфейсы, не более.

Но если такое решение можно получить «автоматически», то есть, просто формально рассуждая в терминах ТК, было бы интересно узнать о такой цепочке рассуждений.

3. А можете пояснить, что именно подразумевается в следующей фразе?

и вы можете уже голый тип данных использовать с полной эффективностью

4. Разница к тому же ещё в том, что изначально в объект надо закладывать всё что нужно для будущей жизни, а если хочется расширить — придётся наследовать.

Не обязательно. Существуют разнообразные методы конструирования объектов. Миксины, например. Или же прототипы, как в JavaScript.

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

А чем это отличается от интерфейсов Go или характеристик (traits) в Rust? То есть, не является ли категория просто очередным синонином для термина интерфейс?
1) То, что кто-то вас считает человеком, а я — юзером, не говорит о том, что прав кто-то, а я не прав. Правы мы оба. Вы человек и вы юзер одновременно.
ОС — действительно чистая монада состояний (без учёта исключений, которые можно конвертировать в чистые данные, если есть необходимость). Тут нет никаких противоречий с точкой зрения императивных языков.
Собственно, это одно из первый открытий Хаскеля — наконец-то найден мостик что такое императивный язык с точки зрения Хаскеля (да и вообще любого чистого функционального языка) — это чистый функциональный язык действующий в композиции монад — состояний и исключений.
И тут нет подвоха.

3) Упрощённо говоря, объект — это данные + функции, объясняющие как с ним работать.
В Хаскеле — новый тип данных — это данные отдельно. Так же отдельно создаются тип-классы, которые объясняют как работать с выбранной категорией. И, дабы можно работать с новым типом данным, его подключают к нужной категории когда хотят, и имеют доступ к функиям категорий.
Чем-то напоминает объекты шиворот на выворот.

5) Да, тип-классы похожи на интерфейсы, собственно, трейты для Руста создатели пытались сделать подобным тип-классам Хаскеля.
Более всего похожи тип-классы на roles из Перла.

Отличия:
а. Трейты и интерфейсы к объектам подключаютя на момент описания класса. Подключения типов данных к тип-классам (инстансы) происходят «перед» использованием, вернее независимо
б. Кроме того, поведение трейта/интерфейса определяются в момент создания самого интерфеса, тип-классы тоже, но как правило, в тип-класс вставляются лишь минимально-нобходимое количество функций, а основные «плюшечные» функции пишутся отдельно и независимо.
Например, есть класс Eq — класс сравнения. Содержит лишь 3 функции: (==), (/=), cmp. А я могу написать отдельно функцию (напр. пересечение списков)
intersect_list :: Eq a => [a] -> [a] -> [a]

И я смогу использовать эту функцию с моим типом данных, ничего не меняя ни в тип-классе, ни в определении моего типа данных. Я могу независимо подключить мой тип данных к «категории» Eq и использовать мой тип данных с функией пересечений списков.
1. Чистая же означает «без эффектов». Но смысл ОС как раз в управлении эффектами. Не понятно, как она может быть чистой. Я согласен, конечно, что её можно вписать в интерфейс чистой монады состояний, но сама ОС не может таковой сущностью являться. Ну прилетел ей пакет из интернета, как это описать в терминах монады состояний?

3. Не понятно, что означает, «подключить к категории». Это реализовать тот или иной интерфейс? Или как? В приведённом же примере, всё равно, надо реализовать show и save. Или особенностью является то, что можно всё писать не в одном месте, а по мере необходимости? Так то же самое есть в JavaScript или Go. Тут, видимо, для осознания мной особенностей КТ-подхода, нужно понять, что такое «подключить категорию».

5. Тип-классы это и есть категории?

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

Речь идёт о том, что мы можем в любом месте написать instance и определить функции для этого интерфейса?

5.б. А разве в любых других системах, поддерживающих интерфейсы, дело обстоит не точно так же? В чём тут именно ТК-особенность?
Читаю я ваш диалог, и мне кажется, что вас жестко дезинформируют. Нет никакого «подключить к категории». Категории — это инструмент для размышлений над задачей, а не паттерн кодирования.
Давайте, я прокомментирую точку зрения автавтора статей.
ТК — это основа системы типов в хаскелле. Тут нужно заметить, что в хаскелле система типов не как в других языках, тут она не только про перенос ошибок на время компиляции, но и про общую корректность программы, так что используется она на полную катушку. Именно поэтому паттерны программирования в хаскелле тесно связаны с системой типов, и чтобы думать о задачах согласованно с принятыми в хаскелле паттернами полезно знать ТК.
Вы можете возразить, мол это все про хаскелль, при чем тут я? Оказывается, что хаскеллевый подход потрясающе решает ряд задач, которые не под силу ООП и другим стилям: например, композиция примитивов concurrency. При этом понятно, что дело не в хаскелле, а в паттернах и в их основе — ТК, так что ее знание полезно каждому программисту, а не только функциональщикам.
ТК — это основа системы типов в хаскелле. Тут нужно заметить, что в хаскелле система типов не как в других языках, тут она не только про перенос ошибок на время компиляции, но и про общую корректность программы, так что используется она на полную катушку.

Да нет же. Система типов в Haskell вполне описывается стандартными методами теории типов. Нет никакой необходимости притягивать к этой системы ТК за уши. И система типов в Haskell не такая уж и продвинутая, как в некоторых других системах: Coq, ATS. Система типов в ML вполне себе сопоставима по мощности с системой типов в Haskell. В Haskell же работает всё тот же алгоритм W Хиндли-Милнера.

В том-то и заключается часть моего butt-hurt. Я всё читаю книги о типах, но никто из классиков даже не заикается о ТК (точнее, ссылки есть, но очень косвенные: для того, чтобы пояснить рекурсивные уравнения, ссылаются на теорию семантических доменов и концепцию оператора неподвижной точки, а в статьях по семантическим доменам ссылаются на работы по ТК в качестве альтернативного более абстрактного подхода, но там ещё есть ссылки и на теорию Мартина-Лёфа, и некоторые другие).

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

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

Оказывается, что хаскеллевый подход потрясающе решает ряд задач, которые не под силу ООП и другим стилям: например, композиция примитивов concurrency.

А можно это заявление конкретизировать примерами?
1) Чистая — да, это без эффектов.
Но смысл ОС как раз в управлении эффектами
Если быть точным, то смысл ОС — управление доступами и ресурсами.

Давайте я попытаюсь аллегориями пояснить.
Ваши высказывания по ОС подобны — «ноль не может быть числом, это же нет числа».
Я парирую — «ноль — это обычное число».
Вы — «но ведь суть нуля — в том, что нету числа!»
Тем не менее, попытаюсь сказать, что всё же «ноль — это обычное число, ибо с нулём можно делать всё, что и с числом. Если что-то крякает как утка и плавает как утка — это и есть утка».

ОС с точки зрения чистой функциональщины — это монада состояний, потому что ОС подчиняется законам монад состояний.
Если утка плавает как поплавок, и всплывает как поплавок, утка и есть поплавок.
Это никак не противоречит, что ОС — управление эффектами.
Это изоморфные понятия, или говоря проще — что в лоб, что по лбу.

5) Категории — это филосовское понятие. Тип-классы, это то, что отражает взаимосвязи, в том числе и категории. Для упрощения, в первом приближении, можно считать, что да, одно и то же.
Если быть точным — тип-классы — это релизация ad hoc полиморфизма (смахивает на перегрузку функций).

3 + 5.a) Подключить — да, имелось в виду реализовать интерфейс.

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

Давайте я попытаюсь аллегориями пояснить.
Когда я говорю о категориях, это подобно «есть такое изобретение — целые числа, в итоге очень удобно универсально работать с натуральными и отрицательными числами как с целыми, если описать натуральные как целые и отрицательные как целые».
Или это же кодом:
-- library1.hs
data Natural = ...

-- library2.hs
data Negative = ...

-- library3.hs
class ToInteger a where
  to_int :: a -> Integer

-- library4.hs
instance ToInteger Natural where
  to_int :: Natural -> Integer
  to_int = fromNatural

-- library5.hs
instance ToInteger Negative where
  to_int :: Negative -> Integer
  to_int = multiply (-1) . fromNegative

-- app.hs
any_add :: ToInteger a => a -> a -> Integer
any_add x y = ineger_add (to_int x) (to_int y)

Несмотря на то, что пример утрированный, примерно так работает тип-класс Num с любыми числами.
Вы парируете «Ну, я всегда могу поработать с отрицательными как с отрицательными, а с натуральными как с натуральными. Всё равно же и вы и я пишем в общем-то одинаковый код, если надо будет поработать одновременно и натуральными и негативными. В чём резон целых чисел? Ну это математическая придумка, как это использовать в написании текстового редактора».
И будет у вас
class Natural {
...
function type() {..}
function add_nat (Natural $b) { ... }
function add_neg (Negative $b) { ... }
function add_any ($b) {if ($b->type() == "Natural") return $this->add_nat($b);...}
}

class Negative {
...
function type() {..}
function add_nat (Natural $b) { ... }
function add_neg (Negative $b) { ... }
function add_any ($b) {if ($b->type() == "Natural") return $this->add_nat($b);...}
}

И если я вас совсем замучаю, то вы ещё допишите обёртку к этим двум
class Integer {
...
function type() {..}
function add_any ($b) {...}
}

Лучше станет, но не намного. Захотите рефакторить под:
trait Type {
  type () { ... } 
}

trait AddAny {
add_any($b) { ...}
}

class Natural extends Type, AddAny {
...
function type() {..}
function add_nat (Natural $b) { ... }
function add_neg (Negative $b) { ... }
function add_any ($b) {if ($b->type() == "Natural") return $this->add_nat($b);...}
}

class Negative  extends Type, AddAny {
...
function type() {..}
function add_nat (Natural $b) { ... }
function add_neg (Negative $b) { ... }
function add_any ($b) {if ($b->type() == "Natural") return $this->add_nat($b);...}
}

class Integer extends Type, AddAny {
...
function type() {..}
function add_any ($b) {...}
}

Вы не сможете, в разных библиотеках находятся, да и кода не существенно меньше.

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

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

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

Например, есть библиотека aeson, которая автоматически преобразует JSON в ваш тип данных и наоборот.

Например, есть библиотека Parsec и ей подобные, это комбинаторные парсеры, которые на выходе получают ваши данные, а не набор массивов (как в перл-образном парсере). Да и само описание парсера — просто и легко читается.
Написать на монадическом парсере компилятор/интерпретор языка программирования — очень просто (без учёта эффективности и ресурсов), так как очень просто писать правильные грамматики для них.

Можно ли всё это написать на Яве или Си? Можно.
Можно ли подобно Хаскелю писать? Можно. Именно поэтому и воруют идеи императвщиков и функциональщиков и те, и другие.
Только категории показывают как это сделать универальнее.
Мне кажется, Вы специально выдумываете корявые не-Haskell :) Лично я поступил бы совершенно точно так же, как и Вы в Haskell — написал бы преобразование в общий тип. Собственно, это классическое решение.

Только категории показывают как это сделать универальнее.

Так вот я и пытаюсь спросить: как именно? Давайте остановимся на приведённом Вами примере с числами. Где именно в нём работает ТК?
В приведённом примере чистая математика.
Это универсальное решение. Потому что именно так в алгебре описаны натуральные, отрицательные и целые числа.
Я ТК знаю поскольку постольку, поэтому не могу точно сказать, является ли ToInteger категорией.
В данной переведённой статье на Хабре рассказывается про такую категорию как композиция.
Я тут тоже её употребил:
(.) :: (b -> c) -> (a -> b) -> a -> c

to_int = multiply (-1) . fromNegative

Кстати, ТК нашла, что можно композицию ещё обобщить:
class Category cat where
  id  :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

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

В алгебре кольцо целых чисел совсем не так определяют.

Кстати, ТК нашла, что можно композицию ещё обобщить:

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

2) Тут есть как положительный ответ, так и отрицательный.
Полжительный ответ — композицию можно применять к любым «категориям», в том числе и к стрелкам.

Отрицательный ответ состоит в том, что технически Хаскель был развит под малосвязанные тип-классы, и когда начинается применяться ТК в полном объёме, он начинает неадекватно себя вести. Разработчики думают над разрешением подобных проблем. А пока означает, что лучше использовать более специализированные решения.
ОС с точки зрения чистой функциональщины — это монада состояний, потому что ОС подчиняется законам монад состояний.
Если утка плавает как поплавок, и всплывает как поплавок, утка и есть поплавок.
Это никак не противоречит, что ОС — управление эффектами.
Это изоморфные понятия, или говоря проще — что в лоб, что по лбу.


Как именно подчиняется? Как при помощи такой монады описать получение IP-пакета из внешнего мира?
IO. Все изменения во внешнем к программе мире, включая состояние ОС инкапсулированы в обьекте типа IO (). Благодаря тому, что IO — это монада, этот обьект может состоять из множества действий типа IO a: получений пакетов, выводов в файлы и прочего внешнего.
Так в том-то и проблема, что они не инкапсулированы в объект типа IO (). IO не реализует операционную систему, а только лишь предоставляет к ней интерфейс. И реализовать ОС в терминах чистых вычислений невозможно. Ещё раз вопрос повторю: опишите, пожалуйста, процесс получения IP-пакета из сети в терминах lambda-выражений.
Не знаю в деталях, как это происходит. Если вы опишите по шагам достаточно подробно, можно будет подумать.
На самом деле, можно даже попробовать нечто более простое: приём байта по RS-232:

1. Контроллер слушает провод, когда он получает 8 байтов транзисторы в нём переключаются и выдают байт в специальное устройство FIFO — очередь.

2. Очередь формирует прерывание, если там установлена определённая комбинация контрольных битов.

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

4. В этой программе написано, какие сигналы нужно поформировать на внешних шинах, чтобы в определённую ячейку памяти (или регистр) сохранить очередной байт из FIFO.
Чистая функция, это такая у которой результат зависит только от аргументов. В императивной программе результат зависит не только от аргументов, он и от глобального состояния (состояния мира). Таким образом можно представить императивную программу, как функциональную, у которой у каждой чистой функции приписан еще один аргумент — текущее_состояние_мира и еще одно возвращаемое значение — новое состояние мира.

См как устроено IO в языке clean clean.cs.ru.nl/download/html_report/CleanRep.2.2_11.htm

Так как мир нельзя копировать то такие функции приходится выстраивать в цепочки — step3(step2(step1(world)))

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

world1, byte = receiveByte(world0)
world2, handle = openFile(world1, filename)
world3 = writeToFile(world2, handle, byte)

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

Это и называется монадой IO — функции встроенные в цепочку с приписанным им значением определённого типа (состояние мира).

Но в отличие от императивного программирования, у нас есть другие монады. Например если мы уберем требование уникальности типа приписываемого значения у нас может быть вычисления встроенные в расходящиеся и сливающиеся цепочки. Так же в императивной программировании состояние мира одно, а в функциональном программировании может быть много «мирков» с изолированным состоянием, таким образом мы легко видим, какие вычисления могут повлиять на какие, а на какие не могут.
Вы не очень хорошо понимаете суть. Дело в том, что побочных эффектов нет. Просто не бывает.
Люди их придумали у себя в голове.
Давайте, я раскрою мысль.
Вот вы, когда думаете о побочных эффектах, вы думаете о машине тьюринга, там где ячейки и команды, и естественным для программиста, но противоестественным для математика образом рассуждаете: раз есть ячейки, то есть и побочные эффекты. А делаете вы так потому, что ассоциируете ячейки с оперативной памятью. Так вот, это в корне не то, как задумывалось (могу ошибаться, не знаю, что думал лично Тьюринг, но знаю математику явления). Так вот, фактически машина тьюринга — конечный автомат. И, вопреки распространенному заблуждению в конечном автомате нет никакого состояния, а слественно, и побочных эффектов. А есть там множество состояний и рекурсивно применяемый эндоморфизм этого множества: все очень чисто и математично.
Так вот: побочных эффектов не бывает. Их придумали программисты, не осилившие математику, и скопировавшие образ мысли о программе с реализации в железе.
А монады — это не волшебная сложная конструкция, а естественная проекция идеи конечного автомата. Это состояние и эффекты — действительно сложные и неестественные концепции для алгоритмиста, позаимствованые у железячников.
Неа. На самом деле, у машины Тьюринга тоже нет никаких эффектов, потому что нет никакого ввода/вывода и взаимодействия с внешним миром или хотя бы даже с другими машинами Тьюринга. Когда я думаю об эффектах, я думаю о значениях, которые появляются в вычислении не из начальных данных. А как ни крути, что МТ, что вычисление любого lambda-выражения (хоть типизированного, хоть нет) не может привести к появлению в вычислении значений, которые не зависят от начальных данных.

Побочные эффекты бывают. Если бы их не было, то в компьютерах не было бы смысла :) Ошибаются как раз математики, которые не смогли понять программирования, и хотят нас — программистов — убедить, что это мы ничего не понимаем. Но я повторюсь, существуют строгие математические формализмы, описывающие эффекты в вычислениях: CSP и ASM. То есть, существуют математики, которые смотрят на вычисления иначе.

Совершенно не понятно, почему именно функция и связанные с ней заморочки должна быть признана основой вычислительного мироздания.
Ну вот я программист по профессии, и считаю вашу точку зрения неверной, так что вот, я нашел проблему в вашей логике =)
Основная проблема возникла, когда возник Хаскель — как написать функцию getLine :: String, так чтобы с одними и теми же входными данными (а в данной функции их нет) было бы одинаковое значение.
И нашли полезный тип данных — IO a. С помощью него нашли и описали функцию.
getLine :: IO String

А вот избавиться от IO нельзя.
То есть не существует функции
fromIO :: IO a -> a

IO a является монадой, поскольку выполняет 3 правила монад (тут (==) является псевдо-Хаскелем):
1) Левой идентичности
f <=< return  ==  f

2) Правой идентичности
return <=< f  ==  f

3) Ассоциативности
f <=< (g <=< h)  ==  (f <=< g) <=< h

Где
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
f >=> g     = \x -> f x >>= g

(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
(<=<)       = flip (>=>)

Хочу заметить, что тип данных IO a является не только монадой, но и функтором, аплликативным функтором,…

Получить пакет — импортируем Network.Socket.
Там есть например, такая функция
inet_addr :: String -> IO HostAddress

Ну или функции работы с сокетами
Эх… Это не описание процесса получения пакета из сети, это описание того, как воспользоваться тем, что ОС умеет получать эти пакеты. Я не спорю, что это большое достижение: придумать чисто функциональный интерфейс к ОС. Но это только интерфейс. Функциональность ОС при помощи таких абстракций не выразить.
Как вы можете говорить, что это нельзя сделать? Вы попробовали и доказали, что нельзя? Ну не писал еще никто сетевых драйверов на хаскелле, это дело времени.
И, если честно, я не понимаю, к чему вообще этот разговор, статья-то не о хаскелле, а о ТК — о основе паттернов корректного написания кода.
Эмс. Так доказательство же тривиальное. Haskell — чистый, в программе ничего не может случиться, если оно не описано в этой программе. Программа — это один поток вычисления без ввода/вывода, если хотите. А пакет прилетает совершенно из другого потока. Нет такого lambda-выражения, которое описывает пару независимых потоков вычисления. Хотя бы по той причине, что никакое lambda-выражение не может описать запуск другой программы.

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

Монады — это всего лишь общий интерфейс для таких эмуляций и реально независимых процессов. Это та тонкость, на которую никто почему-то не обращает внимание в среде Haskell-истов. А она очень важная, о ней много размышлял Робин Милнер.

Что же до ОС на Haskell, то сообщество очень давно грозится её сделать (с 2005 года). И даже есть попытки разной степени успешности: LightHouse, Kinetic, The H Interface. Но они все требуют реализации какого-нибудь микроядра на Си или Ассемблере. Обычно, берут L4 и обвешивают его разнообразными монадами через Foreign. И там даже есть драйверы клавиатуры и мышки.

И это имеет прямое отношение к топику. Ибо я всё пытаюсь понять, какое отношение ТК имеет к программированию вне Haskell-мира.
Программа это не один поток вычисления, программа — это набор функций — как их вычислять — это дело компилятора.

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

Можно поступить примерно так же как авторы Squeak:
1. Описать машину как класс типов
2. Написать ограниченный эмулятор машины внутри Haskell программы
2. Выбрать подмножество Haskell, которое легко транслируется в машинный код и написать на нем компилятор Haskell
3. Скомпилировать компилятор Haskell в машинный код путём трансляции кода компилятора на ограниченном подмножества Haskell в машинный код.

Тот есть примитивы мы не «реализовываем» а просто отображает хаскельный eDSL для эмулятора машины в машинный код.

Только так никто не делает, потому, что проще через C. см главу Smalltalk to C Translation тут
ftp.squeak.org/docs/OOPSLA.Squeak.html

Щас такое распространено для JavaScript (см. Например WebSharper)

То есть мы представляем ассемблера, как частный случай хаскела с ограничениями, после чего пишем на этом ассемблерохаскеле компилятор хаскела и транслирует его самим собой.
Аналогичный подход использован в PyPy. Первая часть этого проекта — RPython — ограниченное подмножество Python, пригодное для статического анализа, плюс немного расширений, которое транслируется в C и далее компилируется. Именно на RPython написан сам интерпретатор PyPy, что даёт дополнительную гибкость в разработке самого интерпретатора.
Ну, собственно, я с этим и не спорю. Смоделировать поведение компьютера на Haskell можно. Но прицепить Haskell к компьютеру без дополнительных выходящих за рамки самого Haskell конструкций — нет. При чём даже, мне кажется, к компьютеру, точнее, виртуальной машине, которая исполняется самим же Haskell-ом. Там всё равно должен быть какой-то вариант ввода/вывода, который должен описываться внешними по отношению к языку низкоуровневыми библиотеками.

Какое выражение Haskell заставит компилятор сгенерировать инструкцию вида: wr some-pci-address, some-value. Проблема заключается в повторных записях/чтениях по одному и тому же адресу.

Ну, то есть, меня очень легко опровергнуть, если написать выражение Haskell, которое заставит компилятор генерировать такую инструкцию.
В описанном бутстрапе после шага 2 возникает такой компилятор.
Пусть возникает. Но что он должен уметь делать? И что я должен буду писать в самом Haskell?
1. Компилировать restricted Haskell (eDSL манипулирующий моделью машины) в машинный код.
2. Так как restricted Haskell это Haskell — то на нем можно написать рантайм для хаскеля и компилятор (вернее переписать ту часть, которая написана на C)
Мотом можно сделать embedded restricted Haskell и интегрировать его в сам Haskell.

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

Как-то так.

кстати

1. mutable уже есть внутри монады IO

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

drop 1 (drop 2 someList)

не приводит к порождению новой структуры в памяти, а просто удаляет 3 элемента из не в два этапа.

P.S. Я не настоящий хаскелист, я просто немножко изучал концепции некоторое время назад из интереса, так что, в каких-то деталях могу ошибаться.
1) Меня удивляет, что вы желаете иметь ОС от Хаскеля.
Работающих ОС в мире не так уж и много, но те, которые есть, вполне успешно решают проблемы. Нет надобности в новых ОС.
Отсутствие написанной ОС — не означает, что её нельзя написать. В том числе и на Хаскеле.

2) «Haskell — чистый, в программе ничего не может случиться, если оно не описано в этой программе.»
Тут, всё верно, но похоже, вы путаете Хаскель с лямбда-исчислением.

3) Нет такого lambda-выражения, которое описывает пару независимых потоков вычисления.
Я даже больше скажу — ни одно лямбда-выражение не описывает вычисления вообще.
Ага, всё таки путаете.
Хотите ли вы сказать, что на Хаскеле нельзя описать ВСЁ. А именно, в нём могут быть функции, которые не описаны в терминах самого Хаскеля. Есть такие. Как и в любом другом языке. Те же шаблоны в Си++ не совсем Си++, даже больше — совсем не Си++.
Только что это меняет? В Хаскеле можно создать до 40к одновременных легковесных потока, в которых будет производится вычисление.
Реализуется это с помощью встроенных функций par, pseq пакета Control.Parallel.
Или чистые потоки ST из пакета Control.Monad.ST.
Или использовать конкурентные потоки из Control.Concurrent прежде всего при помощи функции forkIO :: IO () -> IO ThreadId

4) Монады — это всего лишь общий интерфейс для таких эмуляций и реально независимых процессов.
Хорошо, что хоть не говорите, что комплексные числа — это всего лишь эмуляция квадратных корней отрицательных чисел. )))
А монада — это всего лишь Monad (category_theory)

5)Ибо я всё пытаюсь понять, какое отношение ТК имеет к программированию вне Haskell-мира.
От математики никуда программисты не убегут. Будут ли они знать, что такое монады или нет.
Зачем нужен универсальный клей Момент? И зачем нужен скотч?
Когда вы захотите бумагу соединить — есть канцелярский клей. Если надо хорошо соединить — есть ПВА. Для дерева эпоксидный клей, для металла — заклёпки и сварка,…
Зачем существует Момент?
Да именно затем — можно канцелярским, эпоксидным или ПВА. А можно Моментом. Или скотчем.
Хаскель — это Момент и Скотч прежде всего (это не значит, что ПВА пользоваться нельзя).

Изучай Хаскель во благо!
1. С одной стороны, это чисто научный мой интерес: можно написать ОС на Haskell или нельзя? С другой, это всё к вопросу об универсальности подхода. Мне так часто говорят, насколько Haskell крутой, что я задумываюсь о том, чтобы начать использовать его на практике. Но если на нём нельзя написать ОС, то это означает, что для моей области деятельности он не подходит. ОС — это просто общеизвестный аналог тех задач, которые стоят передо мной.

3. На Си++ можно написать ОС, без использования других языков программирования и без ассемблера. Затем написать компилятор Си++ и обработку шаблонов. В этом смысле уровень самодостаточности Си++ много выше, чем уровень самодостаточности Haskell. Он, конечно, не абсолютный, где-то в процессоре должно быть прошито, по какому адресу необходимо начинать исполнять первую инструкцию, и это вне Си++.

Ну. Си++, конечно, достаточно кривой язык. Но он более универсален в сравнении с Haskell. Так получается. Компилятор Си++ можно заставить генерировать определённый машинный код, который необходим для взаимодействия с физическим компьютером. А вот компилятор Haskell — не понятно. Вполне возможно, это я чего-то не понимаю.

5. Как я уже и сказал, lambda-исчислением и ТК математические формализмы для программ не ограничиваются. Есть ещё CSP, ASM, есть теория Успенского и Клини. Много есть формализмов. В том числе и с «клеем». CSP — это один сплошной «клей». Но при помощи этого варианта «клея» можно склеить ОС, а при помощи TK, пока ещё не понятно, как.

Это я к вопросу о том, так ли уж универсальны варианты композиции, предлагаемые ТК, в сравнении с композициями вычислений, предлагаемыми другими формализмами?
На Хаскеле можно написать код ОС. Единственное, что эффективность написанного кода в части взаимодействия с железом будет не на высоте. Просто никто не занимался оптимизацией в этой части.
Хаскель создавался как академический язык для того, чтобы попробовать, что такое «чистое» и «ленивое» программирование. Вся популярность Хаскеля — следствие мощи, которую случайно заложили в язык.
Си же напротив, специально создавался для написания ОС, а именно — Юникса. Линукс тоже написан на Си. Виндовс написан на Си++.
Если нужно написать ОС, Хаскель — не лучий вариант.

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

Это я к вопросу о том, так ли уж универсальны варианты композиции, предлагаемые ТК, в сравнении с композициями вычислений, предлагаемыми другими формализмами
ТК не говорит КАК, а говорит можно или нет.
На Хаскеле можно написать код ОС. Единственное, что эффективность написанного кода в части взаимодействия с железом будет не на высоте. Просто никто не занимался оптимизацией в этой части.

Так вот меня академически и интересует, как можно на Haskell описать это взаимодействие? Эффективность тут не важна, важен сам принцип. Пока то, что я видел — это библиотеки на Си или Ассемблере с интерфейсом монады.

Си же напротив, специально создавался для написания ОС, а именно — Юникса. Линукс тоже написан на Си. Виндовс написан на Си++.

Кстати, было бы интересно описать при помощи ТК те особенности Си, которые делают разработку на нём ОС более эффективной. Если ТК такая универсальная, то должен быть некий подход.

Если нужно написать ОС, Хаскель — не лучий вариант.

Какой-нибудь JavaScript тоже не лучший вариант для этого. Однако, на JavaScript общение с оборудованием — дело естественное. Хотя, наверное, Вы справедливо отметите, что если мы добавим в JavaScript некий встроенный, допустим, конструктор для массива, который отображает всю физическую память системы для прямой работы с регистрами устройств, то это будет аналогом IO. И, видимо, прямую адресацию памяти в Си можно трактовать точно так же. Но возникает вопрос о прерываниях, о многопроцессорных системах.

Думаю CSP можно описать в рамках ТК, так как CSP можно описать в рамках теории множеств.

Описать можно… Но тут возникает вот какой вопрос. Процессы тоже можно задавать рекурсивными уравнениями, похожими на уравнения рекурсивных типов в Haskell. Но при этом для описания процессов и для описания их взаимодействия и композиции не нужно прибегать к ТК. Какой-то в этом всём подвох и butt-hurt лично для меня.
Asm.js он совсем «не такой» :) Это способ дополнительной типизации JavaScript-а в помощь JIT-компилятору
Это способ писать такой ограниченный Js чтоб его было легко транслировать в машкод ну или в C но при этом эти программы остаются js

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

просто в asm.js вводятся ограничения что программа должна работать с большим типизированным массивом и для каждой инструкции типы должны быть выводимы. А в asm.hs — что программа должна быть функцией возвращающей последовательность функций СостояникМашиныДо -> СостояниеМашиныПосле.

При этом даже можно не использовать монаду IO достаточно просто абстрактно определить семантику этих функций.

То есть семантику asm определяем как частный случай семантики Haskell относительно модельной машины
Да, но, всё равно, что-то же должно превратить эту последовательность функций в машинный код. То есть, это всё необходимо будет выгрузить во-вне, и тут опять вылезет IO.
Ну да. Типизированный ассемблер. С такими Microsoft играется со времён проекта Singularity. Но возникает вопрос: каким образом компилятор запишет результат трансляции на диск или в память? Для этого понадобится IO, написанная неким внешним способом.

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

Ну, как бы да, но… Мы просто написали ещё один компилятор. И компилятора, всё равно, два.
«Ну, как бы да, но… Мы просто написали ещё один компилятор. И компилятора, всё равно, два.»

Дык после переписывания Io на Haskell и интеграции компилятора в asm.hs, старый можно выкинуть и у нас просто будет один компилятор который сам себя компилирует только для частного случая когда код соответствует ограничению из asm.hs мы его можем хорошо оптимизировать
Мне кажется, несколько не так. После выкидывания IO, у нас будет компилятор Haskell, который будет генерировать программы, которые будут генерировать ассемблер для IO. Язык один, но есть такой вот дополнительный шаг. Какой-то есть в этом всём намёк на неподвижные точки, IMHO.
Не, я имел ввиду не это, а подход как у asm.js — определить семантику машины как частный случай монады state, затем определить программу как последовательность известных преобразований состояния, затем скомпилировать вычислитель этой последовательности в эквивалентный код для существующего процессора
А как это поможет соорудить IO?
В данный момент я перевожу следующую главу книги, там есть и ремарка про пакеты по сети =)
Добавляем в компилятор условие, что если код соответствует ограничениям asm.hs и мы его вызываем для особого типа, который мы обозначим как «реальная машина», то такой код мы переводим в машинный код, и вставляем в место его вызова call.

Делаем единственный способ получения типа «реальная машина» из Io.

Потом переписываем на asm.hs те части Io, которые еще не на самом Haskell.

То есть нам ее обязательно выполнять функции шаг за шагом — мы можем выполнить над кодом любые преобразования, так, чтобы только результат был такой же. Как, например, jit для байткода Java не обязан эмулировать все промежуточные вычисления, а может для каких-то частных случаев преобразовать стековый jбайткод в регистровый машинный, ничего ее знающий о стеке, а оптимизатор SQL не обязан сначала выполнять декартовое произведение таблиц, а потом фильтровать результат, а может поменял местами
Ну, да… Можно и так. Но это уже выводит нас из концепции компилятора, выдающего безопасный код. То есть, мы должны предусмотреть в нём реализацию на низком уровне небезопасных примитивов, которые могут снести всю soundness системы типов. По мне так лучше уж вариант с двумя компиляторами. Вариант с двумя компиляторами, второй из которых позволяет выдавать машинный код, представляется более разумным.

К тому же, если идти по пути низкоуровневых примитивов, то гораздо проще сделать какие-нибудь примитивы для записи в память. Этого будет достаточно.

Ок. Можно считать, что проблема записи определённого значения по определённому адресу решена. Осталась ещё одна важная проблема: прерывания. Оно, конечно понятно, что если мы умеем писать всё, что угодно, по любому адресу, то через память и будем организовывать взаимодействие. Но это ничем не отличается тогда от Си… Profit только в том, что эти взаимодействия будут ограничены определёнными функциями.

Хорошо. Убедили. Спасибо.
>>>Ну, да… Можно и так. Но это уже выводит нас из концепции компилятора, выдающего безопасный код.

1. Безопасный код — это некий устоявшийся компромисс. Например в случае C# передать документы пользователя в АНБ — это безопасный код, а Acess Violation небезопасный. Если мы генерируем код для реальной машины в любом случае решение будет не гарантированно безопасным. Не важно как это делается — в помощью монады IO или чистыми функциями так как может быть ошибка.

2. Мы можем ввести ключ компилятора -enable_asm и тогда мы не сможем скомпилировать такой код для реальной машины если не включим этот ключ (например мы не будем предоставлять в монаде IO функцию runAsm)

3. так как asm.hs выполняющийся на настоящей машине у нас явно помечается соотетсвующим типом, мы можем изолировать unsafe код и постепенно уменьшать его количества.

4. Система типов может позволить нам вводит более и более безопасный ассемблер вводя какие-то более высокоуровневые операции (типа циклов) и какие-то правила композиции этих операций

«Но это ничем не отличается тогда от Си… Profit только в том, что эти взаимодействия будут ограничены определёнными функциями.»

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

Можно их изолировать при помощи написания на другом языке или при помощи описания на Haskell — разница в том, что на каких-то других беднее система типов и меньше возможности отключить то, что нам не нужно. Ну и конечно, экосистема для C есть большая готовая, а для asm.hs ее нет :)
ApeCoder очень неплохо ответил по этому поводу!

Заострю внимание на следующих моментах, которые возможно несколько запутаны.

1) Вы почему-то желаете видеть чистую математическую функцию, которая знает как управлять процессором, созданным на архитектуре фирмы Интел в США в 70х годах 20 века.

2) Чистая функция — та, которая без побочных эффектов, но это НЕ означает, что вообще без эффектов.

3) В большинстве случаев язык Ассемблер — не совсем язык, а мнемоники машинных команд, поэтому он не так уж и страшен.
Компьютер ведь по прежнему понимает лишь машинный код )).
GHC по умолчанию транслирует в нативный код (ассемблер) или в код для LLVM компилятора.

4) Вы почему-то видите связь между теорией категорий и возможности/невозможности существования чистой функции работы с процессором.
Теория же категорий не говорит ничего про это. Зато, если есть такая функция, и есть другая функция, то ТК говорит, как их можно соединить.

5) Что касается IO. Это не написано в стандарте, но основной компилятор, GHC на самом деле имеет дырку — RealWorld, а IO — всего лишь оболочка над ним. Думаю, вполне можно написать ОС на Хаскеле даже сейчас, только кому это надо?!
1. Не обязательно этими процессорами. Не важно какими именно. Но, то ли к счастью, то ли к сожалению, все процессоры устроены примерно одинаково, если рассматривать их в этой проекции. Да и управлять надо не процессором, а оборудованием. Я же не настаиваю на том, что это обязательно должна быть инструкция записи в память, но просто технически у нас нет других инструментов. Да и не факт, что они возможны. Потому что нам в реальном мире нужно сопрягать не чистые математические функции, а процессы.

2. Чистая означает «вообще без эффектов». Это определение.

4. Не. Я не вижу связь между ТК и какой-нибудь невозможностью. Я спрашиваю, как мне ТК может помочь в том, чтобы написать ОС. ApeCoder, конечно, хорошо написал. Но категории тут ни при чём. Фактически, он предложил, как оставаясь в рамках системы типов Haskell прикрутить примитивы, которые компилятор будет узнавать как машинные инструкции. Ну, замечательно. Но, ведь, в этом нет никаких рассуждений о категориях, морфизмах и функторах… А хотелось бы услышать о них.

5. Ну люди пытаются написать, но только у них не получается именно на Haskell. Эту самую «дырку RealWorld-а» заполняют кодом на Си. Если расширить компилятор так, как предлагает ApeCoder, то можно будет написать на таком вот модифицированном Haskell, но это уже будет несколько странный Haskell.
1) Всем управляет процессор, а процессор управляется машинными бинарными командами. Которые выдаёт программа.
Для того, чтобы создать ОС, необходимо лишь отправлять машинные команды.
Что тут такого нечистоплотного? )))

5) Я ещё раз напоминаю, что компилятор Хаскеля (GHC) написан на Хаскеле, и RealWorld, равно как прямой доступ к памяти — тоже. Хотя там используется субХаскель.

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

5. Если субХаскель — это STG (ну, язык ядра Haskell, без сахара), то там ничего такого нет.
Я думаю параллельность можно представить как то, что у нас есть n потоковфункций меняющих real world и мы можем их перемешивать. (либо вставлять кусочки одного потока после кусочков другого, либо выполнять две функции от одного состояния а потом объединять миры)
5. В чем странность этого haskell? только в том, что есть некие типы данных, описывающие предметную область «модель компьютера». Еще мы знаем о том, что если мы наложим некоторые ограничения на вид функции, то это будет выполняться существенно быстрее. Можно так же сделать другую реализацию такого класса типов которая будет вычисляться внутри Haskell безо всяких монад IO.
Странность в том, что мы можем написать какую-нибудь инструкцию записи в память и снести тем самым весь процесс вычисления. Конечно, unsafe и мы сами виноваты. Но вот проблема в том, что в рамках теории процессов, мы можем отказаться от необходимости таких произвольных доступов. У нас просто будет процесс, который отвечает за своё устройство. И нам нет никакой необходимости заниматься чем-то небезопасным. Ну, видимо, в Haskell мы можем напорождать кучу монад для разных устройств… Эх. Только вот программирование будет потом каким-то адским адом из lift-ов. Но… В принципе, это IO и обычный пользователь не увидит.
Это зависит от того, насколько полную модель мы захотим составить — если нам надо иметь возможность «записать число по адресу XXX» то как это не моделируй оно небезопасно. Надо как-то переходить к друг им понятиям типа «присвоить значение элементу массива». Но все равно надо будет как-то объяснять процессору, какие адреса он будет читать и писать и на этом этапе будет возможна ошибка.

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

Так вот она говорит о соединении функций. А я же утверждаю, что в реальном мире нам надо уметь соединять не функции, а процессы. Допустим, процесс исполнения одной инструкции процессором и процесс исполнения следующей. Или что-то типа этого. И для такого объединения у нас есть CSP. И не понятно, зачем нам нужна TK в данном случае.
Процесс — это ленивая функция :: [a] -> [b]!
Он принимает какие-то сигналы типа a и посылает сигналы типа b.
В хаскеле это все очень естественно и понятно из за ленивости, и я прекрасно понимаю, как сложно увидеть такое непривычному человеку, и как раз математика (ТК в частности) помогает учиться видеть такие вот обобщения и унификации.
Нет. Известны две «классические» формализации процессов — это pi-исчисление Милнера и CSP Хоара. Ни в одном из них процессы не являются ленивыми функциями. В pi-исчислении я разбираюсь только на формальном уровне. Но как обстоит дело в CSP могу описать на «интутивном» уровне.

Процесс — это сущность, которая при возникновении некоторого события превращается в другой процесс. Процессы не описываются списком входящих сигналов и исходящих сигналов. Они описываются множествами трасс (traces). Если смотреть на процессы абстрактно то они, скорее, соответствуют рекурсивным типам. А не одному какому-то типу.

Через концепцию «событие -> превращение в новый процесс» уже описывается приём и передача сообщений или сигналов.

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

В принципе, у Милнера похожая концепция. Но я не смогу на качественном «интуитивном» уровне описать эту абстракцию.
Если есть 2 процесса, то ТК может вам сказать как их соеденить!

Есть замечательный пакет на Хаскее — Pipes.

Там всё можно рассматривать в качестве потребителей, производителей, соеденителей и эффектов.
Тут hackage.haskell.org/package/pipes-4.1.4/docs/Pipes-Core.html показывается как использовать категории.
Все типы данных рассматриваются как частные случаи одного типа данных:
data Proxy a' a b' b m r
    = Request a' (a  -> Proxy a' a b' b m r )
    | Respond b  (b' -> Proxy a' a b' b m r )
    | M          (m    (Proxy a' a b' b m r))
    | Pure    r

Там очень красивые картинки/диаграммы, как оно работает и какие использованы категории.
А если есть 200 процессов? Да ещё таких, что половина из них порождается по запросам пользователей?
Диаграммы, конечно, красивые. Да, язык категорий используется. Только вот нифига не понятно. Хотя бы пример был бы какой-нибудь приведён. А то такое ощущение, что это Pipes ради Pipes. Игра ума и только. Как при помощи этих Pipes написать, допустим, какую-нибудь примитивную вещь, допустим такую (пример на Bash):

echo $((`cat file-1.txt | wc -l` + `cat file-2.txt | wc -l`))

Это вывод суммы количества строк в двух файлах. Тут запускается 4 процесса, которые работают параллельно.
Если вас интересует конкурентные методы самих Pipes, то тут:
Pipes Concurrent Tutorial
Как раз с примерами.
А тут Perfect streaming using `pipes-bytestring` можно почитать автора библиотеки, как легко можно баш-подобные функции писать.

На счёт параллельного и конкурентного Хаскеля вообще, то можете почитать он-лайн
Parallel and Concurrent Programming in Haskell

Да, хоть 2000 процессов в зависимости от действий пользователя. Главное, чтобы памяти хватило )))
Ну, как и следовало ожидать, всё делается через forkIO. А посоветуйте что-нибудь почитать именно об этом самом RealWorld. Мне никогда не попадалось на глаза.
О RealWorld не так уж много и написано.
Однако, код GHC является открытым, так что можно покопаться в сырцах.
Из статей — неплохо описано тут Unraveling the mystery of the IO monad и тут Understanding the RealWorld

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


К сожалению, возможность написания функций с side effect вынуждает смотреть в реализацию объекта, ибо документация может врать или не описывать некоторые use case'ы. И это верно как для ООП, так и для функционального подхода.
Но в математике и в функциях Haskell композиция направлена справа-налево.

Haskell достаточно мощный язык, чтобы можно было легко сделать наоборот:
(?) = flip (.)

И тогда f . g эквивалентно g ? f
Также легко реализовать пайпы:
(&) = flip ($)
Sign up to leave a comment.

Articles