← All posts tagged Haskell

Macil
Haskell repa repa-flow (http://hackage.haskell.org/package/repa-flow), очередная stream-библиотека от которой не хочется орать: «Нет! Нет! Только не мой мозг, ебучие пришельцы!!!» Существует уже достаточно давно, в рамках работы над 4-й «репой», правда, слегка потеряла импульс развития.

Пост, главным образом из-за бумажки: Polarized Data Parallel Data Flow benl.ouroborus.net Также, рекомендую обратить внимание на ссылки [1] и [2] оной, это ещё одна стрим-библиотечка в iteratee-стиле, но с блекжеком и шлюхами (линейной логикой Жирара).
Macil
Haskell parsers github.com hackage.haskell.org
Очередной комбинаторный парсер для лексического анализа. Токены определяются в виде простых свёрток.

Относительно новый (первый коммит 2016-08-08), поэтому фич у него немного Если чо, эти же ребята пишут repa.

Эх, эту бы тулзу мне бы да год назад... Теперь уже без надобности.
Macil
? Haskell sockets С ужасом осознал, что соврешенно не умею писать сетевые проги на Х-е. В общем, есть клиент что-то типа недоджсонрпц, который: а) может в произвольный момент послать сообщение серверу; б) в любое произвольное время может получить сообщение от сервера. С тем как увязывать запрос-ответ проблем нет, а вот как это выглядит с точки зрения сокетов и/или ИО-менеджера? Есть ли какой-то идиоматичный пример на Х-е?
Macil
Haskell — Девушка, мне пжалста полкило зигохистоморфических препроморфизмов!
— Молодой человек, не выпендривайтесь! Вот вам скрученные функторы[1] и пиздуйте отсюда!

[1] cse.iitk.ac.in
Macil
Haskell Возникла тут задачка нагенерировать «тестовых» примеров некого формата данных. Чем сейчас модно и молодёжно сношать генеративные грамматики на Х-е?
Macil
? GCC Haskell А можно Х-й Cmm преобразовать в Гццшный TREE? Ну, и дальше «по команде»: GIMPLE, RTL, асм. Из главных плюшек — LTO, конечно. Ну, может быть и оптимизаицй каких-нибудь перепадёт.
Macil
Windows GCC Haskell C binutils *пиздец Натолкнулся на доставляющую фичу бинутилза под PE/COFF. Что GCC, что GHC вставляют что-то типа .ident "Compiler Version" в генерируемые ассемблерные файлы. Для GCC это отключается по -fno-ident, для GHC — хрен знает.
Под ELF никаких проблем: создаётся секция .comment в объектнике, которая: а) не гузится в память; б) с флагом MERGE (дубли схлопываются при линковке). Т.е. в результате в исходном бинарнике получается секция с «подписями» всех компиляторов, когда-либо участвовавших в его создании. Удобно.
Для PE/COFF... Ну, вы поняли... В объектнике создаётся секция .rdata$zzz, которая мало того с флагами ALLOC и LOAD, так ещё дефолтный линк-скрипт аппендит её к .rdata бинарника. В результате, мусор в конце секции .rdata.
И если в 7.10.2 он занимал небольшое количество относительно размера бинарника, то в 7.10.3 со сменой тулчейна ситуация значительно ухудшилась.
Решение:
1. Подвергнуть живительному экстерминатусу секцию .rdata$zzz во всех объекниках и статических библиотеках strip --strip-unneeded --keep-file-symbols -R .rdata$zzz сделает своё дело. Увы, strip обламывается на HsBase из-за громадного размера, поэтому придётся вручную упаковывать/распаковывать.
2. Добавить строчку в линк-скрипт (перед .rdata) DISCARD : {*(rdata$zzz)}
Увы, хрен его знает как это сделать в GHC.
Гугл молчит, так что прошу распространить.
А вообще, эта «фича», мне кажется, может смело номинироваться на премию «Просос года». Даже боязно смотреть как обстоят дела с «официальными» сборками опенсорса под венду.
Macil
? Haskell plsql Котаны! Встала тут задача статического анализа PL/SQL. Вернее даже не собственно PL/SQL, а адского «объектно-ориентированного» расширения на котором написана деби^W бизнес-логика одной «широко известной в узких кругах» системы. Так что проприетарные тулзы за сотни нефти малость бесполезны.
Хватился, а на Х-е даже парсера PL/SQL нету. Мож у кого-то возникала потребность? Мож у кого-то есть наработки (хоть какие-то!!!), похрен на кривость и законченность. Ну не с нуля же писать! Со своей сороны обещаю полный гихаб/опенсорс/паблик домейн...
И да, подкиньте плз книжек/бумажек уровня «Статический анализ (похрен чего) для чайников». Можно и не для чайников. На вырост, лол! А то теоретическую часть вопроса представляю себе слабовато...
Macil
Haskell XML Кто о чём, а вшивый — о бане, в смысле, об очередной модели XML.
Если мы рассмотрим XML как цепочку символов StartTag a, EndTag a, Content a (или как говорят в соответствующей литературке — SAX), то совсем нетрудно будет заметить что он относится к классу языков сбалансированных скобок, т.е. не является регулярным.
Это не является проблемой самой по себе: мы всегда можем построить КА для разбора конкретной цепочки, и даже множества цепочек... Чем, собственно говоря, и занимаемся путём ваяния XML-схем различной степени упоротости.
А если есть способ? Нет понятно дело, можно перейти на новый уровень, взять МП-автомат и невозбранно юзать контекстно-свободные грамматики. Но тогда мы теряем всю алгебраическую вкусноту, присущую регулярным языкам... А в реальном мире алгебраические свойства регулярных языков куда важнее, чем возможность допускать более «широкие» множества цепочек!
Нет. Именно способ разбирать языки сбалансированных скобок, сохраяняя при этом все свойства регулярных языков. Как оказалось — есть!
Интуитивным объяснением почему КА не может разбирать языки сбалансированных скобок является отсутствие «памяти» . А если эту память можно присобачить?
Встречайте: Nested Word Automata (автоматы вложенных цепочек), а точнее его практическую реализацию Visibly Pushdown Automata.
Идея в том, что данный автомат жрёт три разных типа символов: «call» — обозначается как <a, «internal» — обозначается как a и «return» — обозначается как a>. Соответственно и функция переходов распадается на три: для символов «call» принимает текущее состояние и входящий call-сивол и возвращает следующее состояние и сивол который нужно засунуть на вершину стека, для «internal» принимает текущее состояние и входящий internal-символ и возвращает следующее состояние (т.е. как обычный КА), для «return» принимает текущее состояние, входящий internal-символ и символ с вершины стека и возвращает следующее состояние.
Т.е. в резултате мы получили класс МП-автомата, который не может за один символ запихивать и выпихивать символ из стека. Это повлияло на количество распознаваемых языков, но позволило сохранить свойства регулярных языков!
Более того, если у нас есть дерево t(a, b(c, d), e), то мы его можем закодировать как цепочку <t <a a> <b <c c> <d d> b> <e e> t>, т.е. ровно по такому же принципу как это делают SAX-парсеры.
За последний десякток лет была масса исследований на эту тему. С подборкой можно ознакомиться
madhu.cs.illinois.edu
cis.upenn.edu
Основополагающя статья Adding nesting structure to words: cis.upenn.edu
Слайды: cis.upenn.edu (с них лучше начать).

А теперь пара вопросов касательно первотега:
1. Неоднократно слышал что applicative-парсеры описывают регулярные языки. Где можно об этом почитать?
2. Кто-нибудь сталкивался с реализациями МП-автоматов на Х-е? Будут полезны также всякие LR/GLR/LALR реализации.

P.S.: Сабж применяется не только к XML, и вообще первоначально применялся для анализа программ, отсюда и call- и return- терминология.