Борьба с аппликативным разбором

Question

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

Для тривиальных парсеров это довольно просто. Для нетривиальных ... не так много. Аппликативный интерфейс, похоже, сильно заставляет вас писать все в стиле без ограничений. С этим очень сложно справиться.

Рассмотрит, например:

call = do 
    n <- name 
    char '(' 
    trim 
    as <- sepBy argument (char ',' >> trim) 
    char ')' 
    trim 
    char '=' 
    r <- result 
    return $ Call {name = n, args = as, result = r} 

Теперь давайте попробуем написать, что с помощью Аппликативного:

call = 
    (\ n _ _ as _ _ _ _ r -> Call {name = n, args = as, result = r}) <$> 
    name <*> 
    char '(' <*> 
    trim <*> 
    sepBy argument (const const() <$> char ',' <*> trim) <*> 
    char ')' <*> 
    trim <*> 
    char '=' <*> 
    trim <*> 
    result 

Аппликативных имеет заставил меня поставить переменные привязки очень далеко от того, где фактического парсер. (Например, попробуйте подтвердить, что as на самом деле связан с sepBy argument ..., это совсем не просто, чтобы убедиться, что я не получил неправильный подсчет из _ моделей!)

Другого очень неинтуитивное то, что <*> применяет функцию к значение, но *> и <* - это просто чистое упорядочение. Это взяло для возрастов, чтобы обернуть мой разум вокруг. Имена разных методов сделали бы это намного, намного яснее. (Но Монада, кажется, схватил >> и <<, к сожалению.) Кажется, что они могут быть сложены, давая такие вещи, как

exit = 
    "EXIT:" *> 
    trim *> 
    name <* 
    char '(' <* 
    trim <* 
    char ')' <* 
    trim 

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

В целом, я нахожусь желающим, чтобы я мог просто использовать нотацию! Мне действительно не нужно изменять эффекты, основанные на предыдущих результатах; Я не нужно власти Монады. Но обозначение настолько читаемо. (Я продолжаю задаваться вопросом, действительно ли возможно реализовать это: можете ли вы синтаксически сказать, когда конкретный блок do может быть механически преобразован в аппликативный?)

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

Answer 1

У меня действительно нет решения проблемы, но, возможно, какая-то интуиция может помочь вам легче создавать аппликативные парсеры. Когда дело доходит до Аппликативного, есть два вид «последовательность», которые должны быть принято во внимание:

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

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

data Infix = Infix  Double  Operator  Double 
infix  = Infix <$> number <*> operator <*> number 

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

number = f <$> sign <*> decimal <*> exponent 
    where f sign decimal exponent = sign * decimal * 10 ^^ exponent 

Вот для того, чтобы вычислить число, которое вы должны сделать несколько нетривиальное сочетание операций, которая осуществляется с помощью локальной функции f.

Другая типичная ситуация такова, что вам нужно отбрасывание некоторое значение:

exponent = oneOf "eE" *> integer 

Здесь *> сбрасывает значение на левой стороне, сохранить значение справа. Оператор <* делает противоположное, отбрасывая правый и удерживая левый. Когда у вас есть цепочка таких операций, вы должны расшифровать их, используя левую ассоциативность:

p1 *> p2 <* p3 *> p4 <* p5 ≡ (((p1 *> p2) <* p3) *> p4) <* p5 

Это искусственно надуманное: вы вообще не хотите, чтобы это сделать. Лучше разбить выражение на значимые части (и предпочтительно дать осмысленные имена). Один общий шаблон, который вы видите:

-- discard the result of everything except `p3` 
p1 *> p2 *> p3 <* p4 <* p5 

Существует небольшой нюанс, хотя, если вы хотите применить что-то еще p3 или если p3 состоит из нескольких частей, вам придется использовать круглые скобки:

-- applying a pure function 
f <$> (p1 *> p2 *> p3 <* p4 <* p5) ≡ p1 *> p2 *> (f <$> p3) <* p4 <* p5 

-- p3 consists of multiple parts 
p1 *> p2 *> (p3' <*> p3'') <* p4 <* p5) 

Опять же, в этих ситуациях часто бывает просто просто разбить выражение на значимые фрагменты с именами.

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

Answer 2

Написать меньше парсеров. Например, ваши аргументы выглядят как (argument[, argument…]). Это может быть легко выражено

argListP :: Parser [Argument] 
argListP = char '(' *> trim *> argument `sepBy` (char ',' *> trim) <* char ')' 

который до сих пор вполне читаемым: а «(» с последующим пробелом, аргументов, разделенных запятой и пробелом, и завершающего «)». То же самое можно сделать для вашего result:

resultP :: Parser Result 
resultP = trim *> char '=' *> result 

Как вы можете видеть, что до сих пор читаем: произвольное пустое пространство, а затем знак равенства и какой-то результат. Теперь call почти тривиальным:

call :: Parser Call 
call = Call <$> name <*> argListP <*> resultP 

Answer 3

Ну, ваш пример анализатор искусственно сложно.

Есть много вхождений trim, что вы можете абстрагироваться от:

token p = p <* trim 

Вы также можете абстрагироваться от чего-то, что происходит между парой соответствующих скобок:

parens p = token (char '(') *> p <* token (char ')') 

Теперь то, что осталось, :

call = 
    (\ n as _ r -> Call {name = n, args = as, result = r}) <$> 
    name <*> 
    parens (sepBy argument (() <$ token (char ','))) <*> 
    token (char '=') <*> 
    result 

И, наконец, вы не должны учитывать вхождения _, но скорее научитесь использовать <$ и <*. Вот полезные Эмпирические правила:

• *> Используйте только в сочетании foo *> p <* bar, например, в parens выше, больше нигде.

• Сделайте ваши парсеры имеют вид f <$> p1 <*> ... <*> pn, и теперь выбирать между <$> и <$ в первом положении или между <*> и <* во всех других позициях исключительно на вопрос о том, вы заинтересованы в результате последующего синтаксического анализа вы , Если да, используйте вариант с >, в противном случае используйте тот, который отсутствует. Тогда вам не нужно игнорировать любые аргументы в f, потому что вы даже не получаете к ним доступа. В восстановленном примере, приведенном выше, только = маркер остается, что мы не заинтересованы, поэтому мы можем сказать

  call = Call <$> name 
        <*> parens (sepBy argument (() <$ token (char ','))) 
        <* token (char '=') 
        <*> result 
  

(Это предполагает, что на самом деле Call принимает только эти три аргумента.) I 'd утверждают, что эту версию легче читать, чем ваша оригинальная версия на основе do.

Чтобы ответить на ваш более общий вопрос: Да, можно распознать do -значения, которым не нужна сила монадов. Проще говоря, это те, которые являются лишь последовательностью привязок с return в самом конце, и все связанные переменные используются только в финале return и нигде больше. Для добавления этого в GHC есть proposal. (Лично я не большой поклонник этого, однако, я считаю, что аппликативная нотация более функциональна, чем примечание.)