Комментарии 56
Замечательно! Это очень вкусная тема — комбинаторный грамматический разбор. Не планируете ли вы продолжения, раскрывающего прочие достоинства аппликативного подхода: например, возможность статического анализа, невозможного в монадических парсерах. Я спрашиваю, поскольку сам подумывал написать об этом, но вдруг, у вас уже готов материал.
В этой статье стоит сказать, что при вашем определении типа Parser возможен автоматический вывод экземпляра класса Funtor для него. Либо очень компактный и симметричный "ручной вариант":
instance Functor Parser where
fmap f = Parser . (fmap . fmap . fmap) f . unParseиспользующий то обстоятельство, что и функция, и список и пара являются функторами. В этом сила и смысл классов типов.
Думала написать похожий туториал про монадические парсеры, но пока даже не могу предположить, когда руки дойдут. Дальше раскрывать тему аппликативного подхода не собиралась, так что с удовольствием почитаю, если вы про это напишете, мне тоже тема интересна.
Я старалась избегать в примерах таких конструкций, их красоту трудно понять новичкам, оно скорее может отпугнуть. Но надеюсь, что добравшиеся до комментариев осмыслят и оценят этот вариант, тут вся сила языка просматривается. С такими небольшими красивыми этюдами можно даже отдельный пост делать.
Я старалась избегать в примерах таких конструкций, их красоту трудно понять новичкам, оно скорее может отпугнуть. Но надеюсь, что добравшиеся до комментариев осмыслят и оценят этот вариант, тут вся сила языка просматривается. С такими небольшими красивыми этюдами можно даже отдельный пост делать.
Думала написать похожий туториал про монадические парсеры, но пока даже не могу предположить, когда руки дойдут.
Я с удовольствием почитаю. Спасибо вам за статью!
f#
Версия парсеров на другом языке. Практически один в один.
зачем такой изврат? если парсер комбинатор это StateT (трансформер монад) и тут можно какой угодно контейнер подставить
Затем, чтобы разобраться, что происходит. Проще всего использовать derive Functor, он выводится однозначно. StateT это верное решение, но не для туториала, придется слишком много тащить лишней инфраструктуры. Бесточечное определение, может быть, и выглядит колдовством, но оно отражает смысл преобразования: разворачиваем, заходим в "на дно" функтора, он у нас трехуровневый, и заворачиваем. При этом становится видно, что мы не делаем ничего лишнего.
Может мне кто-нибудь объяснить, откуда в Haskell такая любовь к однобкувенным идентификаторам? Почему никто не пишет predicateParser predicate =… вместо predP p =…?
Ни разу нигде не видел переменную типа больше одной буквы. Вот что, например, значат переменные типа в конструкции data SnapletInit b v, почему именно b и v а не a и z?
Ни разу нигде не видел переменную типа больше одной буквы. Вот что, например, значат переменные типа в конструкции data SnapletInit b v, почему именно b и v а не a и z?
Могу ошибаться, но думаю, что в данном случае «ноги растут» из алгебры. Там тоже иксы с игреками, а не CoordinateX, CoordinateY.
Даже не знаю, как правильно ответить на ваш вопрос, кроме как руками помахать и сказать, что «так принято», «все так делают», «меня так научили», «я так привыкла» и т.п.
Скорее всего это пришло из теории категорий. И сам язык располагает к использованию компактного синтаксиса, инфиксных синонимов и коротких имён в том числе.
Но надо сказать, что многобуквенные переменные типа не так уж и редко встречаются.
Скорее всего это пришло из теории категорий. И сам язык располагает к использованию компактного синтаксиса, инфиксных синонимов и коротких имён в том числе.
Но надо сказать, что многобуквенные переменные типа не так уж и редко встречаются.
В случае с объявлениями полиморфных типов, а уж тем более когда на типы налагаются ограничения классов типов, типа того, как здесь:
причина как раз вполне понятна. Название этого параметра не несёт никакой смысловой нагрузки и лишь выступает в качестве местозаполнителя. И вряд ли особая польза была бы, если это записывали как:
А вот почему внутри реализаций функций такая тяга к коротким переменным — загадка. Вероятно как и в случае с C причина кроется в возрасте и наследственности языка. Во времена становления Haskell и уж тем более во времена становления ML о читаемости кода ещё так не пеклись, и люди просто привыкли.
showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String)причина как раз вполне понятна. Название этого параметра не несёт никакой смысловой нагрузки и лишь выступает в качестве местозаполнителя. И вряд ли особая польза была бы, если это записывали как:
showVsPretty :: (Show itemToShow, PrettyPrint itemToShow) => itemToShow -> (String, String)А вот почему внутри реализаций функций такая тяга к коротким переменным — загадка. Вероятно как и в случае с C причина кроется в возрасте и наследственности языка. Во времена становления Haskell и уж тем более во времена становления ML о читаемости кода ещё так не пеклись, и люди просто привыкли.
Если вы мне хотели показать какой haskell понятный, то вы сделали строго противоположное.
applyP :: Parser (a -> b) -> Parser a -> Parser b
applyP (Parser p1) (Parser p2) = Parser f
where f s = [ (sx, f x) | (sf, f) <- p1 s, -- p1 применяется к исходной строке
(sx, x) <- p2 sf] -- p2 применяется к строке, оставшейся после предыдущего разбораЧто такое sx? Что такое p2 и зачем он, если есть p1? Что такое s? что такое x? Что такое f?
(Я вижу 'where', но мне всё равно не понятно что вы подразумевали под f в рамках вашей предметной области).
Да, если что, задача решается проще. Можно сделать композицию из f g h s d m l и всё получится. Что такое 'm' в данном примере вы вполне сами догадаетесь по контексту d и l.
С Haskell дела не имел, но часть Ваших вопросов всё равно звучит странно. В начале же всё написано понятным английским языком: применяем парсер p1 к парсеру p2, чтобы получить парсер f, совмещающий возможности обоих, где f, применённый к s, по определению выглядит вот так. Дальше, да, начинается чёрная магия.
Но почему нельзя назвать переменные более читабельно, например parser1, parser2 и resultParser?
Можно, но получится противоположная крайность (борщ борщ равно борщ фактори нью борщ, пожалуйста).
Здесь имена обладают такими особенностями:
* то что это «какой-то парсер» понятно и так — из конструкции (Parser p1) и из объявления типа.
* кроме того, что это какой-то парсер, в этом контексте про переменную ничего не известно — мы не можем её назвать там «bankAccountNumberParser». А имена «parser1» и «p1» несут примерно поровну информации (примерно нисколько — то, что это парсер, и так понятно).
* область видимости переменной — три строки. Если метод разрастётся до многих десятков строк, то лучше пусть будет «parser1», т.к. к середине метода читатель уже забудет, что видел конструкцию (Parser p1) в начале.
Вот имена «sx», «sf», имхо, выбраны не очень удачно. Но сходу не предложу значительно лучших имён.
Ещё тут зря используется одно имя «f» для разных переменных: одна для имени парсера, а другая в рамках list comprehension. Мой вариант:
(up: заменил совсем абстрактный икс на «a», так мне кажется лучше, потому что имя переменной совпадает с именем тИповой переменной — так понятно, что это то самое «а», которое в типе функции).
Здесь имена обладают такими особенностями:
* то что это «какой-то парсер» понятно и так — из конструкции (Parser p1) и из объявления типа.
* кроме того, что это какой-то парсер, в этом контексте про переменную ничего не известно — мы не можем её назвать там «bankAccountNumberParser». А имена «parser1» и «p1» несут примерно поровну информации (примерно нисколько — то, что это парсер, и так понятно).
* область видимости переменной — три строки. Если метод разрастётся до многих десятков строк, то лучше пусть будет «parser1», т.к. к середине метода читатель уже забудет, что видел конструкцию (Parser p1) в начале.
Вот имена «sx», «sf», имхо, выбраны не очень удачно. Но сходу не предложу значительно лучших имён.
Ещё тут зря используется одно имя «f» для разных переменных: одна для имени парсера, а другая в рамках list comprehension. Мой вариант:
applyP :: Parser (a -> b) -> Parser a -> Parser b
applyP (Parser p1) (Parser p2) = Parser $ \str ->
[ (p2remain, f a) | (p1remain, f) <- p1 str, -- p1 применяется к исходной строке
(p2remain, a) <- p2 p1remain] -- p2 применяется к строке, оставшейся после предыдущего разбора
(up: заменил совсем абстрактный икс на «a», так мне кажется лучше, потому что имя переменной совпадает с именем тИповой переменной — так понятно, что это то самое «а», которое в типе функции).
Ещё бы a/b p1/p2 осмыслено назвать. Чем они друг от друга отличаются?
Искусство придумывать названия — второе сложное искусство в IT.
Искусство придумывать названия — второе сложное искусство в IT.
А ничем не отличаются. Кроме типа.
В том смысле, что нам про них в данном контексте ничего не известно — это «какой-то парсер» и «какой-то ещё парсер».
А тип виден в первой строке, енкодить его в имя переменной — излишне при небольшой области видимости.
Имхо.
В том смысле, что нам про них в данном контексте ничего не известно — это «какой-то парсер» и «какой-то ещё парсер».
А тип виден в первой строке, енкодить его в имя переменной — излишне при небольшой области видимости.
Имхо.
Если вы не знаете как «это» назвать — ваша абстракция фигня. (какой бы красивой не была математика).
Например, это может быть inner parser или outer parser. Имена переменных, функций, классов и модулей — это самое важное в языке программирования.
Например, это может быть inner parser или outer parser. Имена переменных, функций, классов и модулей — это самое важное в языке программирования.
А чем отличается innerParser и parser1 (аналогично outerParser и parser2)? Только тем, что Ваши названия дополнительно подчёркивают семантику совершаемого действия? Так для этого у нас есть название метода, который ими оперирует.
Если нет разницы, значит абстрация плохая. Вплоть до самого алгоритма. Хорошая абстракция должна иметь вменяемые названия всего, чем оперирует, в каждый момент времени. Потому что альтернативой будет thing do thing to thing to make thing do things to things.
Так и запишем — последовательно применять несколько парсеров к одному участку исходных данных нельзя, всё надо делать за один раз, иначе у нас получается плохая абстракция.
Нет, это вы придумали. Я сказал, что плохая абстракция — это такая абстракция, в которой «жопа есть, а слова нет». Для серийных вещей есть списки и i-нотация, а для несерийных должны быть имена.
Это требование не из CS, это требование из software engineering.
Это требование не из CS, это требование из software engineering.
Ну, в данном случае «слово» есть — «парсер первый» и «парсер второй». Вы можете назвать какие-то другие их отличительные признаки, по которым можно назвать эти сущности? Если этих признаков нет — правильно ли я понимаю, что такая абстракция плоха?
Возможно, плоха реализация. Почему список из двух парсеров обрабатывается так, как будто это уникальные парсеры? Примените функцию «применить парсер» к списку парсеров.
А внутри неё будет точно такой же код, соединяющий их попарно, или гораздо более жуткий и громоздкий, в котором точно никаких вменяемых имён не придумать, который соединит все одним махом (второе — не уверен, что возможно, сам на Haskell не пишу). Или Вы полагаете, что как раз второй случай удастся реализовать более адекватно?
НЛО прилетело и опубликовало эту надпись здесь
Эта максима хороша, когда вы пишете прикладной код, где за каждой переменной стоит какая-то штука из вашего бизнеса (accountBalance это деньги на счету, numberOfBolts это количество болтов, итд).
Когда вы пишете достаточно абстрактный библиотечный код (как в примере в статье), то очень часто оказывается, что вам почти или совсем не важно, что скрывается за переменными. В таком случае вы никогда не сможете придумать осмысленные имена. Ну, предположим, вы пишете функцию, складывающую два числа (именно не сумму на счёте с поступившими деньгами, а вообще, функцию сложения для стандартной библиотеки). Как вы назовёте её параметры? «слагаемое» и «прибавляемое»? seriously? :)
В математике и среди программистов, пишущих абстрактный код, этот принцип несущественности назначения переменных (аргументов функций) настолько распространён, что есть противоположная максима: point-free notation, т.е. способ написания уравнений / кода, при котором имена переменных элиминируются полностью. Пример из хаскель-вики:
(имена fn, f, g и h в данном случае не обсуждаем). В данном примере нам настолько не важно, что такое «x», что мы его вообще предпочитаем не упоминать.
Disclamer: всем и так очевидно, что прикладной код пишется гораздо чаще, чем абстрактный библиотечный.
Когда вы пишете достаточно абстрактный библиотечный код (как в примере в статье), то очень часто оказывается, что вам почти или совсем не важно, что скрывается за переменными. В таком случае вы никогда не сможете придумать осмысленные имена. Ну, предположим, вы пишете функцию, складывающую два числа (именно не сумму на счёте с поступившими деньгами, а вообще, функцию сложения для стандартной библиотеки). Как вы назовёте её параметры? «слагаемое» и «прибавляемое»? seriously? :)
В математике и среди программистов, пишущих абстрактный код, этот принцип несущественности назначения переменных (аргументов функций) настолько распространён, что есть противоположная максима: point-free notation, т.е. способ написания уравнений / кода, при котором имена переменных элиминируются полностью. Пример из хаскель-вики:
it is clearer to write
let fn = f . g . h
than to write
let fn x = f (g (h x))
(имена fn, f, g и h в данном случае не обсуждаем). В данном примере нам настолько не важно, что такое «x», что мы его вообще предпочитаем не упоминать.
Disclamer: всем и так очевидно, что прикладной код пишется гораздо чаще, чем абстрактный библиотечный.
Я бы сказал, что в этом месте у нас плохой язык. Почему? Потому что я вижу, что f, .g, h в этом примере — это объекты из списка. Для списочных данных (у каждого из которых нет имени) должны быть функции списочные же.
Что-то вида: let chained_func = map(apply_in_chain, func_list)
Для любителей значков: let chained_func = . func_list.
Если кто-то в коде вам напишет:
b = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]Вы же его за это поругаете, правда? Так почему же для серийных объектов первого порядка (функий) такое исключение?
Я же написал: не обсуждаем имена f, g, h, fn; предположим, мы их заменили на какие-нибудь осмысленные:
Здесь «id» это какой-то идентификатор книги; в данном контексте нам не важно, откуда мы его достали и чему он равен; просто айди. Мы можем попытаться придумать более лучшее название, чем «id», потратить на это час и изобрести «anyBookIdentifier». Или мы можем вообще выкинуть его из кода.
it is clearer to write
let getAuthorSurname = getSurname . getAuthor . getBookById
than to write
let getAuthorSurname id = geSurname (getAuthor (getBookById id))
Здесь «id» это какой-то идентификатор книги; в данном контексте нам не важно, откуда мы его достали и чему он равен; просто айди. Мы можем попытаться придумать более лучшее название, чем «id», потратить на это час и изобрести «anyBookIdentifier». Или мы можем вообще выкинуть его из кода.
Уже лучше. Сильно лучше. Об имени надо думать. Если вы имена выкидываете, у вас образуется нечитаемый код. И вы говорили не про «пример», а про абстрактный библиотечный код.
Software engineering подразумевает, что код будут читать и перечитывать. И аннотации в виде осмысленных имён — это совершенно обязательное для промышленного кода.
Software engineering подразумевает, что код будут читать и перечитывать. И аннотации в виде осмысленных имён — это совершенно обязательное для промышленного кода.
А если у меня именно такой случай, что мне надо сделать композицию большого количества функций, природа каждой из которых мне неизвестна, так я примерно так и сделаю, как вы сказали: положу функции в список и применю к ним какую-нибудь свёртку, что-то типа foldr.
Очень плюсую. Как раз сидела думала, в какую бы ветку написать, что пост совсем не про коммерческую разработку и что к каждому вырванному из контекста куску кода с очень непонятными переменными прилагается несколько абзацев пояснений.
Или там будут одновременно функции startup(), startup2(), real_startup(). Или там prepareToSave(), beforeSave(), preSave(). Было бы смешно, но вот сам видел в продакшне.
Мне кажется, вы прицепились к самому простому, тривиальному и неинтересному вопросу в программировании. Дискуссия вышла длинная, но с контексте статьи и CS ни о чем. Столько же времени и слов можно было бы потратить на что-либо другое.
Если я в коде увижу вызов функции applyP p1 z, мне придется лезть или в документацию, или в исходники, или смотреть типы, чтобы понять, что это за функция. А, например, глядя в коде на вызов функции createSessionWebSocketMessageBrokerConfigurer messageBrokerConfigurerParams, сразу становится более-менее понятно, что тут происходит.
С перекрытием имени `f` и правда очень нехорошо вышло, спасибо, что ткнули, сама не заметила :( Но зато это иллюстрирует, как обстоят дела со связыванием в языке.
По поводу одинаковых названий переменных типа и переменных в коде, такое лично меня запутывало на ранних стадиях обучения (и не только меня, видела ещё пару студентов с такой проблемой буквально в этом семестре). Начинает казаться, что тут типы first-class. Скорее всего это тоже дело вкуса, но с тех пор сама так не пишу.
По поводу одинаковых названий переменных типа и переменных в коде, такое лично меня запутывало на ранних стадиях обучения (и не только меня, видела ещё пару студентов с такой проблемой буквально в этом семестре). Начинает казаться, что тут типы first-class. Скорее всего это тоже дело вкуса, но с тех пор сама так не пишу.
А ещё, есть такой эффект, думаю его замечали на любом языке: новичок пытается писать «усиленно понятный» код, называет переменные «loopCounter» или пишет комментарии вида «увеличиваем переменную на 1» — просто потому, что самому ему написанный код понятен с трудом из-за слабого знакомства с языком. Потом это постепенно проходит.
С «усиленно понятными комментариями» соглашусь, у меня у самого было, когда программированию учился. А вот сейчас, когда есть некоторое количество опыта, я стараюсь писать усиленно понятный код на любых языках, и зачастую назвать переменную loopCounter может быть хорошей идеей. В идеале код должен читаться так, как будто это не код, а описание того, что он делает. Кстати, если вместо использования крутых мегаконструкций в одно выражение использовать что-то попроще, то это потом и дебажить в случае чего легче.
loopCounter — это по ушам за это бить. Потому что "счётчик в цикле" нам и так видно. А что этот цикл считает?
Вот, смотрите:
for i, v in enumerate(g(d)):
f(v, i)Сравните с:
for sequential_num, emploee_name in enumerate(get_emploees(department)):
print_numbered_bage(emploee_name, sequential_num)В каком случае вы понимаете что я имел в виду?
P.S. Я думал про имя счётчика долго. Это моя третья попытка придумать выразительное имя. Вот если у нас бейджи нумерованные, что такое "номер на бейдже"?
Ну в первом варианте у вас что-то вроде библиотечной функции, где под d может быть что угодно, начиная от департамента и заканчивая списком победителей премии Дарвина.
А во втором — конкретная бизнес-логика.
Именно это вам и пытаются донести.
А во втором — конкретная бизнес-логика.
Именно это вам и пытаются донести.
Не надо использовать слово «бизнес-логика». Я предпочитаю «семантика». Смысловая нагрузка. Это может быть не бизнес-логика, а процесс машинного доказательства P!=NP, сути это не меняет. Имена переменных позволяют дать смысл коду, код без имён переменных смысла не имеет (т.к. никто не может сказать, что происходит, кроме IO).
Не надо использовать слово «бизнес-логика». Я предпочитаю «семантика».
Что, если кто-то предпочитает иначе?
Вообще, можно привести контрпример. Сравните (раз уж вы используете питон):
С
Вы действительно считаете что второй вариант лучше?
def add(a, b):
return a+b
С
def add_two_abstract_items(first_abstract_item, second_abstract_item):
return first_abstract_item + second_abstract_item
Вы действительно считаете что второй вариант лучше?
Именование переменных — это место, где программист может объяснить другому программисту что происходит. Я понимаю, что у хаскеля корни из математики и это заметно в нотации, но я обычно заворачиваю любые pull-request'ы у которых такой уровень информативности переменных.
В квадратных скобках это генераторное выражение, как например в Python. Слева от стрелки < — это деструктуризация результата применения парсера p1 к строке s. Т.е. кортеж из строки sf и функции f (которая в данном случае это значение (a -> b) для парсера p1). В втором кортеже x потому, что для парсера p2 нужно просто значение a (см. описание типа). Результат данного выражения это список кортежей из строк и результатов применения функции f из парсера p1 к значению из парсера p2 )))
Это можно было бы написать с помощью 2 вложенных циклов, если бы они были в Haskell. Тут достаточно настроить свой внутренний интерпретатор и научится читать декларативный код Haskell. В первую очередь обращать внимание на аннотацию типов, а само данное выражение проще читать справа-налево и снизу-вверх, а не наоборот.
Это можно было бы написать с помощью 2 вложенных циклов, если бы они были в Haskell. Тут достаточно настроить свой внутренний интерпретатор и научится читать декларативный код Haskell. В первую очередь обращать внимание на аннотацию типов, а само данное выражение проще читать справа-налево и снизу-вверх, а не наоборот.
Вот вы иронизируете, а вот документация к одной из самых известных библиотек на Хаскеле: hackage.haskell.org/package/lens-4.17/docs/Control-Lens-Lens.html
А вот часть списка определённых в ней функций: hackage.haskell.org/package/lens-4.17/docs/doc-index-60.html
Не встречала ещё тех, кто был бы к этой библиотеке равнодушен, её либо любят и везде используют (ведь названия операторов такие очевидные и интуитивно понятные), либо не используют никогда и другим не советуют.
А вот часть списка определённых в ней функций: hackage.haskell.org/package/lens-4.17/docs/doc-index-60.html
Не встречала ещё тех, кто был бы к этой библиотеке равнодушен, её либо любят и везде используют (ведь названия операторов такие очевидные и интуитивно понятные), либо не используют никогда и другим не советуют.
Тут две строчки. Всего две короткие симметричные строчки, все обозначения определены тут же. Типы объясняют что делает функция, компилятор подтверждает, что реализация верна. Да, нужно остановиться ненадолго, но с этим можно разобраться, и этот опыт будет полезен. И это не APL, не J в двух строчках на которых можно сломать ногу, здесь из абстракций только генерация списка.
fierce-katie, спасибо большое за статью. Действительно, она не об аппликативных парсерах per se, а о том, где и как стоит применять «эти страшные абстрации» — функторы, аппликативные функторы и т.д. И с этим статья отлично справляется, на мой взгляд.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Аппликативные парсеры на Haskell