Category: история

Category was added automatically. Read all entries about "история".

|, me, hikki, ok

Моноиды и прочие ужасы

Не знаю откуда начать. В общем, в эту последнюю (уже сданную) сессию по «Языковым процессорам» было что-то типа домашнего задания, где был дан достаточно смешной язык программирования (операторы языка вписываются в двумерную матрицу, и переходы можно делать вверх-вниз-влево-вправо по всяким странным правилам) и нужно было по программе на этом языке построить Control-Flow граф и всячески его верифицировать, отвечая на вопросы типа «А может ли программа чисто теоретически завершиться?», «А может ли быть выход за пределы поля?», «А может ли быть чтение из переменной до записи в неё значения?» и тому подобных.
Не смотря на то, что реализовывать предлагалось на чём-то из списка [C++, C#, Java] я реализовал всё на Haskell, обильно комментируя весь код, чтобы его можно было понять даже не будучи знакомым с этим экзотерическим языком программирования. И, я думаю, мне это удалось.

Основная идея моего решения состояла в том, что на все задаваемые вопросы можно отвечать в терминах моноидов. Мне слишком лень тут устраивать какие-то туториалы по вездесущим моноидам и их использованию, и сегодня мне моё решение уже не кажется столь же умным, как казалось пару недель назад, и вообще пост не о том, как верифицировать Control-Flow графы с использованием моноидов. Просто скажу, что я вычленял из (направленного Control-Flow) графа некоторые деревья, для каждого узла дерева вычислял какое-то значение, а потом значения суммировал внутри каждого дерева и по всем деревьям.
Например, для ответа на вопрос «А может ли программа чисто теоретически завершиться?» для всех узлов графа без инструкции остановки это «какое-то» значение будет False, для узлов с инструкциями остановки — True, потом рассматриваем полученные элементы как моноид над булеанами с операцией дизъюнкции, суммируем, получаем ответ. Замечу также, что, поскольку там всё лениво вычисляется и суммируется, то этот способ не хуже, чем, например, поиск узлов с инструкцией остановки обходом в глубину с прерыванием обхода при первой найденной.

Вот теперь начинается интересное. В ответ на письмо со своей великой программой я, кроме всего прочего, получил вопрос «А есть ли вопросы о Control-Flow графе, на которые нельзя ответить с помощью моноидов?»
И вот в этом месте я задумался, и до сих пор не уверен, что правильно ответил на сей тонкий философский вопрос.

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

Однако, не смотря на завораживающие подробности написанного выше, я хотел написать совсем не об этом. Просто ехал я тут в автобусе домой, рассуждал о стрелках, комонадах и зипперах в хаскеле, и подумалось мне «А чего ради это люди вообще засовывают достаточно простые вещи в зипперы и комонады, подводя под простой алгоритм кучу вроде бы не очень и нужной математики, а потом долго радуются, что у них оно почему-то работает?». И я стал прикидывать сколько времени я потратил раскладывая в моноиды ответы на вопросы по «Языковым процессорам», сколько времени строчил код, сколько времени дебажил (ненавижу хаскелевский Data.Array!!! почему нельзя хотя бы строчку в программе сказать, где оно падает?) и сколько времени дописывал к нему комментарии, и стал сравнивать со временем, которое на такое же задание потратил ivansorokin, писавший его на плюсах.
И надумалось мне, что если сделать скидку на мою общую тормознутость, то даже если у меня результирующего функционального кода в n раз меньше, чем получается на плюсах, то и пишу я его примерно в n раз медленнее. Не знаю, может быть я такой тормоз, потому что меняю язык программирования на новый раньше, чем успеваю привыкнуть к старому (сейчас на Agda облизываюсь, например), но мне показалось, что просто на самом деле нифига нет никакой разницы на чём писать, и эти постоянные холиворы на тему Плюсы-vs-Хаскель и etc — бред.
На мой взгляд, существенная разница только в способе рассуждений, ибо на плюсах я бы делал какой-нибудь обход в глубину, с прерыванием в случае, если на задаваемый вопрос уже можно однозначно ответить, а на хаскеле я родил функцию из содержимого узла в элемент моноида, реализовал Foldable для моего графа, а дальше нижележащая математика всё сделала сама. Хорошо это или плохо — думайте сами.
С другой стороны, для хаскелевского кода, я по крайней мере, знаю как формально доказать его корректность, а в плюсах с этим как-то очень плохо.

Кстати, о «модульности и расширяемости» каждого решения тоже можно поспорить, другое дело, что, наверное, если в плюсах задаться реализацией мегаобщего фреймворка для обхода и преобразования структур, то какой-нибудь Foldable с Traversable и получатся (только на стероидах и итераторах, небось), если уже чего-то подобного нет.
|, me, hikki, ok

Пирамидки да календарики

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

Весьма часто, когда я прохожу мимо работающего в соседней комнате телевизора, там показывают какую-нибудь археологическую передачу (в спутнике даже целый канал есть почти только этому и посвящённый), где какие-то перцы ходят по всяким сооружениям из огроменных каменных глыб и рассуждают о том, как это всё построили и для каких целей. Мне всегда смешно и грустно смотреть такие передачи.
Не менее смешно и грустно смотреть передачи, где какие-то «алтернативно-одарённые» «археологи» рассуждают, о том, что расстановка пирамид/других штуковин на самом деле представляет созвездия «Ориона», строили пирамиды при помощи техники арендованной у инопланетян, и из соображений, что там по медианам этих конструкций течёт какая-то звёздная энергия, а такое расположение пирамид её усиливает и куда-то там направляет.

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

А теперь представим, что текущая цивилизация погибла в ядерной зиме, люди ушли в горы, забыли об электронах и создали цивилизацию, которая в качестве основной движущей силы использует, скажем, движение снежных лавин. Например, втыкают они в гору столбики по определённой системе, потом вызывают лавину, а после её схода какие-то столбики сметает нахрен, а какие-то остаются стоять, так вот те, что остались стоять — результат вычисления чего-то при помощи лавины. И научились они таким способом страшные вещи вычислять, типа движений воздушных масс в горах, и всячески этими вычислениями пользуются для передвижений при помощи аэропланов. А потом эта великая цивилизация развивается до уровня, когда у неё появляется куча дармоедов, и некоторые их них начинают называть себя «археологами» и идут копать заснеженные долины.
И вдруг они обнаруживают мой пустующий дом, полный остатков компьютерной техники и гнилых книжек. Естественно, что они знать ничего не знают, что всё самое нужно хранится на каких-нибудь SSD где-нибудь в Eee PC (да и с неработающим Eee PC они сделать своими технологиями всё равно ничего не могут) и делают выводы о происходившем по единственной доступной для чтения ими информации — обрывке гнилой страницы из советской книжки по технике безопасности обращения с ПЭВМ. Из чего эти «археологи» строят теорию, что мой дом — это церковь, а современные люди были страшно религиозными, ибо приходили сюда и молились целыми днями перед клавиатурой и монитором, и так им это нравилось, что сами они стали изучать процесс воздействия молитв на организм, и выработали правила под названием «Правила обращения с ПЭВМ», для того чтобы не испортить себе зрения или каких других органов яростным компьютеропоклонничеством. А, например, PDA или ноутбуки использовались в качестве портативных молитвенников, если вдруг срочно припрёт помолится в дали от храма. Обнаруженные CD-диски они примут за метательное оружие для походов в лес на охоту за дичью. И конечно, остатки небоскрёба Охты-центра подскажут им, что в этих местах были железные горы и люди зубами и молотками выгрызали в них железные балки, из балок этих строили здания в 50 этажей, а потом покрывали их мочевыми пузырями буйвола, которые использовались в качестве стен и стёкол. И плевать, что ни одного мочевого пузыря найдено не было, ведь все знают, что стены только из них делать и можно.
А потом среди этой лавинной цивилизации появятся «алтернативно-одарённые» «археологи» и они, на базе клочка бумаги с моим рисунком графа для задания по «Языковым процессорам», который решили проигнорировать «археологи», сделают вывод, что компьютеры-молитвенники располагались подобно созвездию «Скорпиона», и позволяли не только молиться но и передавать ментальную энергию на большие расстояния.

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

Короче, эта ваша археология, что официальном, что в альтернативном варианте какая-то абсолютная чушь, и уж точно никакая не «наука». «Не знаешь — не лезь», — я считаю. Копайте. Складывайте в музеи. Радуйтесь. Аминь.
|, me, hikki, ok

О лямбдо-графах. Tying the Knot

Ещё не так давно на фразу:
— На вашей лямбде нельзя представить, например, граф без использования монады IO.
ответить ничего существенного я не мог.

Щас небось напридумываю своей терминологии, поскольку как оно всё по русски будет — я без понятия.

Действительно, казалось бы, что чисто-функциональной (pure) структурой можно представлять только рекурсивные вложенные конструкции типа списков, деревьев и т.п.
Оказывается, что и структуры со сложными связями тоже можно. И без всякого IO. Трюк называется «Tying the Knot».

Пусть мы хотим записать чисто-функциональной структурой граф, представляющий собой квадрат (пронумеруем его вершины индексами от 1 до 4), с двумя дополнительными связями 1-3 и 2-4. Проще говоря, полный граф с четырьмя вершинами.


Рисовал в гимпе от руки, так что ногами не бить.

Тянуть резину не буду. Сразу скажу, что построить такую структуру можно следующим образом:
> -- Параметры конструктора GNode: id узла, [ссылки на другие элементы]
> data GR a = GNode a [GR a]
> 
> buildSquare :: GR Integer
> buildSquare =
>     let node1 = GNode 1 [node4, node2, node3]
>         node2 = GNode 2 [node1, node3, node4]
>         node3 = GNode 3 [node2, node4, node1]
>         node4 = GNode 4 [node3, node1, node2]
>     in node1

В общем, хитрость в том, что мы используем ссылки на объекты, которых ещё нет, но поскольку вычисления ленивы, то всем на это плевать.

Пытаться печатать такой граф напрямую — глупо. Потому вот ещё «умный» обход в глубину:

> toList g = toList' [] g
> toList' alreadySeen (GNode a links)
> | any (==a) alreadySeen = alreadySeen
> | otherwise = foldl (\seen link -> toList' seen link) (a:alreadySeen) links
>
> main = putStrLn $ show $ toList buildSquare


Что меня в этом забавляет, так это то, что такие вычисления нельзя свести к строгим (или я чего-то не понимаю), стоит добавить строгость в какую-нибудь часть определения buildSquare и всё сломается.
Раньше подобные штуки я видел только при рассмотрении свойств свободных теорем (free theorems), которые могут меняться в зависимости от строгости аргументов функции.