Paren parser problems

[Fuuzetsu]

I was investigating why clever Haskell mode works as bad as it does (again). I have several findings

1. Paren parser (Yi.Syntax.Paren.parse) forces whole result even when it is going to be thrown away.

That is, open a file, only screenfull gets loaded. Edit any part, the (lazy) parser for the rest of the file runs in full then we run another parse for the screenfull.

Basically it seems it's written poorly and needs to be greedy

2. Parse (Parser.Incremental.Parse) violates basic laws. ap /= <*>. Fun exercise is replacing pure <$> pTree with replicateM 1 pTree and watching it crash. Indeed these two things aren't equivalent:

--      pExpr = (:) <$> pTree <*> (pure [])
      pExpr = (\x -> [x]) <$> pTree

3. Indent parser seems ok, just paren parser seems completely fucked. Efforts trying to find the fault in lexer/scanner/etc runners might be better concentrated in verifying that first. I checked other modes using identical runners and they didn't exhibit that behaviour.

[noughtmare]

@Fuuzetsu

You say the paren parser is greedy, but does that also mean that all Parser.Incremental parsers are greedy when they should be lazy, or is only the paren parser affected? With "indent parser" do you mean the indent parsing in the layoutHandler function in Yi.Syntax.Layout? I couldn't find another module that dealt with indent parsing.

[Fuuzetsu]

I think problem lies in paren parser only, or rather not in underlying library.

I forgot exactly what I meant by indent parser but I believe it is thr name for one of the other haskell mode parsers (which do not exhibit the bug).

You can see the bug by adding tracing into the underlying Alex code and see the position and tokens it consumes. It then becomes easy to try other modes and see uf the problem persists.

[noughtmare]

I found the problem: the adjustBlock function.

Changing

  & modeAdjustBlockA .~ adjustBlock

to

  & modeAdjustBlockA .~ (\_ _ -> return ())

fixes the greedy behaviour.

[Fuuzetsu]

Aha, I'm going to blame adjustBlock -> getSubtreeSpan -> getLastElement; we should definitely fix the monad/applicative too though… Good find.

[noughtmare]

Just for the record: the adjustBlock situation is "solved" by 3f6df01

[noughtmare]

I think ap == <*> is not actually a law, the Monad class only has left identity right identity and associativity as laws. I think in our case ap is not <*> because ap cannot do certain optimizations that are possible with the applicative interface.

[Fuuzetsu]

(<*>) = ap should always hold. You don't even have to understand why, you can just look at Monad typeclass which explicitly tells you this. https://hackage.haskell.org/package/base-4.10.1.0/docs/Control-Monad.html#t:Monad

[noughtmare]

Ah, I didn't see that part. But still, what if a type can do optimizations if it is applicative, but can't do those if it is monadic? Should it just not be an instance of Monad, or should it have some kind of newtype wrapper?

[Fuuzetsu]

You're free to implement (<*>) in more efficient way than ap but the result has to be the same. See some comments on https://stackoverflow.com/questions/46913472/how-exactly-does-the-ap-applicative-monad-law-relate-the-two-classes .

A famous example is Haxl where >>= (and therefore ap) results in sequential evaluation but (<*>) is parallel. See https://hackage.haskell.org/package/haxl-0.5.1.0/docs/src/Haxl.Core.Monad.html#GenHaxl . In the end result is the same so the laws hold.

[noughtmare]

I think something similar is happening in Parser.Incremental, it has intermediate states that are not equal, but running both parsers on the same text should yield the same result (or maybe bottom). There might be a mistake in the implementation that causes it to misbehave. I will do some testing on this.

You say:

replacing pure <$> pTree with replicateM 1 pTree and watching it crash

Do you mean it goes into an infinite loop? You could view an infinite loop as just a very inefficient implementation.

But overall I agree that we should do some more research on this.

[Fuuzetsu]

IIRC it outright crashed. Anyway those parsers are based on a paper, might be worth reading that first. Maybe someone "optimised" original code and broke it.

[noughtmare]

@Fuuzetsu can you link to the code where pTree is defined?

[Fuuzetsu]

yi/yi-mode-haskell/src/Yi/Syntax/Paren.hs

Line 120 in 51855c9

pTree :: P TT (Tree TT)

?

[noughtmare]

I am able to reproduce it! (turns out (<*) /= flip (>>)...)

[noughtmare]

I have replaced parse and parse' with:

parse :: P TT (Tree TT)
parse = liftM Expr (parse' tokT tokFromT)

parse' :: (TT -> Token) -> (Token -> TT) -> P TT [Tree TT]
parse' toTok _ = liftM2 const pExpr eof
    where
      -- parse a special symbol
      sym c = symbol (isSpecial [c] . toTok)

      pleaseSym c = recoverWith errTok <|> sym c

      pExpr :: P TT (Expr TT)
      pExpr = liftM2 (:) pTree pExpr <|> pure []

      pBlocks = (liftM Expr pExpr) `sepBy1` sym '.' -- the '.' is generated by the layout, see HACK above
      -- note that we can have empty statements, hence we use sepBy1.

      pTree :: P TT (Tree TT)
      pTree = (liftM3 Paren (sym '(') pExpr (pleaseSym ')'))
          <|> (liftM3 Paren (sym '[') pExpr (pleaseSym ']'))
          <|> (liftM3 Paren (sym '{') pExpr (pleaseSym '}'))

          <|> (liftM Block (liftM3 (\_ a _ -> a) (sym '<') pBlocks (sym '>'))) -- see HACK above

          <|> (liftM Atom (symbol (isNoise . toTok)))
          <|> (liftM Error (recoverWith (symbol (isSpecial "})]" . toTok))))

And that seems to still work (i.e. I opened some haskell files with cleverMode after recompiling yi and nothing crashed).