Infinite loop resulting from uniplate

[treeowl]

@ThreeFx discovered an infinite loop falsely ascribed to Bound. The problem is definitely not there. Here's a smaller test case:

{-# LANGUAGE DeriveDataTypeable #-}

module Main (main) where
import           Control.Lens hiding (List)
import           Control.Lens.Plated
import           Data.Data (Data)
import           Data.Data.Lens (uniplate)

data Expr a   = Var   a
              | List  [Expr a]
              | Apply (Expr a) (Expr a)
              | Lam   (Expr (Maybe a))
              | Nop
              deriving (Data, Show)

main = do
         print ex
         putStrLn "Okay so far!"
         print $ transform removeTest ex
         putStrLn "We only get here after ^C!"

ex :: Expr String
ex = List [ Apply (Var "test") $ List [Var "arg1", Var "arg2"]
          , Apply (Var "two") (Var "three")]

removeTest :: Expr String -> Expr String
removeTest = \expr -> case expr of
                        Apply (Var "test") _ -> Nop
                        _ -> expr

instance Data a => Plated (Expr a) where
  plate = uniplate

As I noted in the earlier ticket, disabling caching in Data.Data.Lens by defining

readCacheFollower _ _ = Nothing

seems to solve the problem. Unfortunately, the code in this module is dangerous, opaque, and has virtually no comments, so I can't guess what the problem is.

[treeowl]

Oh, one likely-important point I forgot to copy over: the Lam constructor (which is unused here) must be present to trigger the problem. The fact that it is non-regular seems likely to be critical. The same happens (less directly) in the original Scope example.

[glguy]

You'll have to stick with tinplate for this type instead of uniplate.

[treeowl]

@glguy, there doesn't seem to be any documentation of restrictions on uniplate. Do you know what they are, or what causes this problem when they're violated?

[glguy]

No, I don't know exactly why uniplate loops on this type. I also don't think that this type is a good candidate for a Plated instance due to the non-regular recursion you've identified above. It will be surprising to some users that plate can’t visit the expression inside the Lam constructor.

[ThreeFx]

@glguy Indeed, that surprises me. Is there a common workaround for this issue? I want to combine Bound and Plated and it is a severe limitation if I can't visit Scope expressions

[phadej]

@ThreeFx when you go under the Scope, the Expr a becomes Expr (Var a).

I'm not sure what you are doing, but if it's about some kind of optmisation path, check how ermine does it in Ermine.Core.Optimizer

[ekmett]

Plated and bound like techniques currently don't mix. We'd ultimately need to support a sort of higher-rank traversal to handle the combination:

e.g.

Applicative f => (forall i. a i -> f (b i)) -> s j -> f (t j)

this same thing arises in walking well-typed EDSLs or using multicompos-like tricks for something like the jmacro expression/statement divide.

Up until now I've gone and rolled my own combinators and 'higher order traversals' by hand whenever the need has arisen. It isn't clear how to package this up nicely in the existing lens package, though, as such combinators aren't compatible with anything else in lens.

If we had a more general notion of a functor that could work on kinds like (k -> ) -> (k -> ) then we could collapse things into a form where they'd use the same combinators lens offers, but lens probably can't be the package that provides such functionality, not while retaining compatibility with base.

[ThreeFx]

@ekmett Are there other solutions apart from writing my own higher-order traversals? I'm not that keen on doing that and probably lack some experience in that department.

Edit edit: Don't mind this, I used stuff the wrong way.

[treeowl]

Regardless of what can and can't be fixed in the grander scheme, I think one thing that should be fixed is the exception behavior. The functions using exceptions should really use a custom Exception type and catch only that type; I shouldn't be able to "unstick" computation by hitting ^C.

[glguy]

That's a good idea. There are two uses of try that shouldn't be catching SomeException. While one of these clearly seems to be trying to catch FieldException, it isn't clear to me what the other one is catching exactly. Is it looking for evaluation of undefined? In that case we should be using throw SomeCustomType instead.