#parsing #haskell #monads #monad-transformers
#синтаксический анализ #haskell #монады #монада-трансформеры
Вопрос:
Многие из используемых мной комбинаторов Parsec имеют такой тип, как:
foo :: CharParser st Foo
CharParser
определяется здесь как:
type CharParser st = GenParser Char st
CharParser
таким образом, является синонимом типа, включающим GenParser
, сам определяемый здесь как:
type GenParser tok st = Parsec [tok] st
GenParser
тогда синоним другого типа, назначенный с помощью Parsec
, определяется здесь как:
type Parsec s u = ParsecT s u Identity
Итак, Parsec
это частичное применение ParsecT
, само перечисленное здесь с типом:
data ParsecT s u m a
наряду со словами:
«ParsecT s u m a — это анализатор с типом потока s, типом состояния пользователя u, базовой монадой m и типом возвращаемого значения a».
Что такое базовая монада? В частности, что происходит, когда я использую CharParser
анализаторы? Я не вижу, куда она вставлена в стеке. Есть ли связь с использованием list монады в монадическом синтаксическом анализе в Haskell для возврата нескольких успешных синтаксических анализов из неоднозначного анализатора?
Ответ №1:
В вашем случае базовой монадой является Identity
. Однако ParsecT отличается от большинства монадных преобразователей тем, что он является экземпляром Monad
класса, даже если параметр типа m
таковым не является. Если вы посмотрите на исходный код, вы заметите отсутствие « (Monad m) =>
» в объявлении экземпляра.
Итак, тогда вы спрашиваете себя: «Если бы у меня был нетривиальный стек монад, где бы он использовался?»
На этот вопрос есть три ответа:
-
Используется для
uncons
извлечения следующего токена из потока:class (Monad m) => Stream s m t | s -> t where uncons :: s -> m (Maybe (t,s))
Обратите внимание, что
uncons
принимаетs
(поток токеновt
) и возвращает его результат, завернутый в вашу монаду. Это позволяет делать интересные вещи во время или даже во время процесса получения следующего токена. -
Он используется в результирующем выводе каждого анализатора. Это означает, что вы можете создавать анализаторы, которые не касаются входных данных, но выполняют действие в базовой монаде и используют комбинаторы для привязки их к обычным анализаторам. Другими словами,
lift (x :: m a) :: ParsecT s u m a
. -
Наконец, конечный результат RunParsecT и friends (пока вы не создадите до точки, где
m
заменяется наIdentity
) возвращает их результаты, завернутые в эту монаду.
Между этой монадой и монадой из монадического синтаксического анализа в Haskell нет связи. В этом случае Хаттон и Мейер ссылаются на экземпляр monad для самого ParsecT. Тот факт, что в Parsec-3.0.0 и более поздних версиях ParsecT стал преобразователем монады с базовой монадой, не имеет отношения к статье.
Однако, я думаю, вы ищете то, куда делся список возможных результатов. В Hutton и Meijer анализатор возвращает список всех возможных результатов, в то время как Parsec упорно возвращает только один. Я думаю, что вы смотрите на m
в результате и думаете про себя, что список результатов должен скрываться где-то там. Это не так.
Parsec из соображений эффективности предпочел первый соответствующий результат в списке результатов Хаттона и Мейера. Это позволяет отбросить как неиспользуемые результаты в конец списка Хаттона и Мейера, так и в начало потока токенов, потому что мы никогда не возвращаемся назад. В parsec, учитывая комбинированный синтаксический анализатор, a <|> b
если a
потребляется какой-либо ввод b
, он никогда не будет оценен. Способ обойти это — try
который вернет состояние туда, где оно было, в случае a
сбоя, а затем вычислит b
.
В комментариях вы спросили, было ли это сделано с помощью Maybe
или Either
. Ответ «почти, но не совсем». Если вы посмотрите на функции с низким рычагом run*
, вы увидите, что они возвращают алгебраический тип, который сообщает, что входные данные о погоде были израсходованы, затем второй, который выдает либо результат, либо сообщение об ошибке. Эти типы работают примерно так Either
, но даже они не используются напрямую. Вместо того, чтобы растягивать это дальше, я отсылаю вас к сообщению Антуана Латтера, в котором объясняется, как это работает и почему это делается таким образом.
Ответ №2:
GenParser определяется в терминах Parsec, а не ParsecT. Parsec, в свою очередь, определяется как
type Parsec s u = ParsecT s u Identity
Итак, ответ заключается в том, что при использовании CharParser базовой монадой является монада Identity.
Комментарии:
1. Спасибо, я отредактировал свой вопрос, чтобы включить этот шаг. Итак, это основа monad transformer. Я полагаю, что это не имеет никакого отношения к неоднозначному синтаксическому анализу, описанному в статье Хаттона / Мейера. Итак, появляется ли такое использование монады списка где-либо в анализаторе Parsec? Является ли Parsec только неоднозначным? Если да, то это кодируется с использованием
Maybe
илиEither
?2. Базовая монада не используется самим parsec, поэтому она не влияет на неоднозначность.
3. Я думаю, о чем я пытался спросить, так это о взаимосвязи между монадой list в статье Хаттона / Мейера; и типами Consumpted и Reply , используемыми в Parsec.