Lottare con l'analisi applicativa

Question

Quindi sto provando a scrivere un parser complesso, usando solo Applicativo (il parser in questione non implementa nemmeno Monad).

Per parser banali, questo è abbastanza facile. Per quelli non banali ... non così tanto. L'interfaccia applicativa sembra forzarti violentemente a scrivere tutto in uno stile senza punti. Questo è estremamente difficile da affrontare.

Si consideri, ad esempio:

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

Ora proviamo a scrivere che l'utilizzo di applicativi:

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 

applicativo ha costretti me per mettere le associazioni variabile molto lontano dal punto in cui l'attuale parser è. (Ad esempio, cercare di confermare che as è in realtà destinata a sepBy argument ..., non è affatto facile verificare che non ho il conteggio sbagliato di _ modelli!)

Un'altra cosa molto poco intuitivo è che <*> applica una funzione di un valore, ma *> e <* sono solo sequenze puri. Ciò ha richiesto età per avvolgere la mia mente. Diversi nomi di metodi avrebbero reso questo molto, molto più chiaro. (Ma Monade sembra aver afferrato >> e <<, purtroppo.) Sembra che questi possono essere impilati, ottenendo le cose come

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

E 'piuttosto non ovvio che si può fare questo. E, per me, questo codice in realtà non è terribilmente leggibile. Ancora più importante, non ho ancora capito come gestire la raccolta di più valori mentre si eliminano più valori.

In tutto, mi trovo a desiderare di poter usare solo la notazione! In realtà non ho bisogno di cambiare gli effetti in base ai risultati precedenti; Io non lo ho bisogno del il potere di Monad. Ma la notazione è molto più leggibile. (Continuo a chiedermi se sarebbe effettivamente possibile implementarlo, puoi sintatticamente dire quando un particolare blocco può essere trasformato meccanicamente in applicativo?)

Qualcuno conosce un modo per aggirare questi problemi? In particolare, come posso spostare le associazioni delle variabili più vicino al parser a cui si legano?

Answer 1

Non ho davvero una soluzione per il problema, ma forse qualche intuizione potrebbe aiutare costruisci parser applicativi più facilmente. Quando si tratta di applicativo, ci sono due tipi di "sequencing" che deve essere presa in considerazione:

• Il sequenziamento delle operazioni di analisi: questo è ciò che determina l'ordine in cui si scrive il parser.
• Il sequenziamento dei valori sottostanti: questo è più flessibile, in quanto è possibile combinarli in qualsiasi ordine desiderato.

Quando le due sequenze si corrispondono bene, il risultato è una rappresentazione molto semplice e compatta del parser nella notazione applicativa.Per esempio:

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

Il problema è che quando la sequenza non corrispondono esattamente, bisogna massaggiare i valori alla base in modo che le cose funzionino (non è possibile modificare l'ordine dei parser):

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

Qui, al fine di calcolare il numero che devi fare una combinazione un po 'banale delle operazioni, che si fa con la funzione locale f.

Un'altra situazione tipica è che è necessario scarto un certo valore:

exponent = oneOf "eE" *> integer 

Qui, *> scarta il valore a sinistra, mantenere il valore a destra. L'operatore <* fa l'opposto, scartando il diritto e mantenendo la sinistra. Quando si dispone di una catena di tali operazioni, è necessario decodificare usando la sinistra-associatività:

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

Questo è artificiosa: in genere non si vuole fare questo. È meglio suddividere l'espressione in pezzi significativi (e preferibilmente dare nomi significativi). Un modello comune che si vedrà è:

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

C'è un piccolo avvertimento, però, se si vuole applicare qualcos'altro da p3 o se p3 costituito da più parti, si dovrà usare le parentesi:

-- 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) 

Ancora una volta, in queste situazioni spesso è meglio suddividere l'espressione in frammenti significativi con i nomi.

notazione applicativo, in un certo senso, forze si nel dividere i parser in blocchi logici in modo che sia più facile da leggere, in contrasto con la notazione monadica dove si poteva in teoria fare tutto in un blocco monolitico.

Answer 2

Scrittura di parser più piccoli. Ad esempio, i tuoi argomenti sembrano essere (argument[, argument…]). Che può essere facilmente espresso da

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

che è ancora abbastanza leggibile: un '(' seguita da spazi bianchi, argomenti separati da virgola e spazio, e un finale ')'. Lo stesso può essere fatto per la vostra result:

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

Come si può vedere, che è ancora leggibile: spazi arbitraria, seguito dal segno di uguale e un qualche tipo di risultato. Ora call è quasi banale:

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

Answer 3

Bene, il vostro esempio parser è artificialmente complicato.

Ci sono un sacco di occorrenze di trim che si può astrarre da:

token p = p <* trim 

Si possono anche astratto da qualcosa che si verifica tra una coppia di parentesi corrispondenti:

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

Ora quello che rimane è :

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

Infine, non si dovrebbero contare occorrenze di _, ma piuttosto imparare a utilizzare <$ e <*. Ecco le regole utili empiriche:

• Utilizzare solo *> nella combinazione foo *> p <* bar come ad esempio in parens sopra, in nessun altro luogo.

• Fai la tua parser hanno la forma f <$> p1 <*> ... <*> pn, e ora scegliere tra <$> e <$ nella prima posizione o tra <*> e <* in tutte le altre posizioni esclusivamente sulla questione se siete interessati al risultato del successivo parser . Se lo sei, usa la variante con il >, altrimenti usa quello senza. Quindi non devi mai ignorare alcun argomento in f, perché non riesci nemmeno ad accedervi. Nel caso ad esempio ridotta sopra, solo il token = è lasciato che non ci interessa, quindi possiamo dire

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

(Ciò presuppone che Call prende effettivamente solo questi tre argomenti.) I Supponiamo che questa versione sia più facile da leggere anche rispetto alla versione originale basata su do.

Per rispondere alla tua domanda più generale: Sì, è possibile riconoscere do -statements che non hanno bisogno della potenza di monadi. In poche parole, sono quelli che sono solo una sequenza di binding con uno return nella parte finale e tutte le variabili associate vengono utilizzate solo nell'ultimo return e da nessun'altra parte. C'è un proposal per aggiungerlo a GHC. (Personalmente, non ne sono un grande fan, tuttavia ritengo che la notazione applicativa sia più funzionale della notazione.)