• Lenses for Tree Traversals

    If there’s one thing compiler writers spill a lot of ink over, it’s tree traversals. Tree traversals are infuriatingly simple conceptually, but can be a lot of boilerplate to actually write. This post covers a couple of tricks that I’ve found useful recently using tools from lens.

    Let’s suppose we have a simply lambda calculus with some primitive integer operations.

    {-# LANGUAGE LambdaCase #-}
    {-# LANGUAGE DeriveFunctor #-}
    {-# LANGUAGE DeriveTraversable #-}
    {-# LANGUAGE RankNTypes #-}
    module LensesForTreeTraversals where
    import Control.Lens
    import Data.Monoid
    import Data.Functor.Foldable hiding (fold)
    import Data.Foldable
    type Name = String
    data Type = IntegerType | FunType Type Type
    data Term = 
        Var Name
        | Lam Name Type Term
        | App Term Term
        | Plus Term Term
        | Constant Integer

    We’d like to write a simple constant-folding pass over this AST. The algorithm is extremely simple, in prose:

    Recursively transform all the subterms, and if the resulting node is then the sum of two constants, replace it with a constant equal to their sum.

    We would really like to reach this level of clarity in our code. The subtlety, of course, is how we talk about “all the subterms”, and that will be the theme of this post.

    A naive implementation of the constant folding function is as follows:

    -- | Do the local part of the constant folding transformation.
    cf :: Term -> Term
    cf = \case
        Plus (Constant i1) (Constant i2) -> Constant (i1 + i2)
        x -> x
    constantFold :: Term -> Term
    -- Do the local transformation after recursively calling ourselves 
    -- on the subterms, if any
    constantFold t = cf $ case t of 
        Plus t1 t2 -> Plus (constantFold t1) (constantFold t2)
        Lam n ty t -> Lam n ty $ constantFold t
        App t1 t2 -> App (constantFold t1) (constantFold t2)
        x -> x

    Tediously, we have to explicitly pull out each subterm and call the function on it recursively, which is not only boilerplate, but error-prone (nothing will tell us if we’ve missed a subterm!).


    Now, we want to do something for every subterm, which sounds like the sort of thing we should be able to do with traverse. But it’s a pain to make Traversable work with our AST. In particular Traversable expects your type to have kind * -> *, i.e. to be able to “contain” values of any type. This isn’t really right for us: a term is like a monomorphic container of its subterms.

    Enter Traversals from lens. A traversal is very closely related to Traversable.traverse:

    -- traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
    -- type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t

    A Traversal is a traverse-like function, but it can be more specific if that’s appropriate. In particular, we can define a Traversal that only traverses the subterms of a term.

    (Maybe there’s a clever way to write traversals, but I do it the stupid way: take the effectful function and the value, and apply it to the subparts.)

    -- Traversal' a b = Traversal a a b b, useful if you're not doing clever stuff
    termSubterms :: Traversal' Term Term
    termSubterms f = \case
        Lam n ty t -> Lam n ty <$> f t 
        App t1 t2 -> App <$> f t1 <*> f t2
        Plus t1 t2 -> Plus <$> f t1 <*> f t2
        -- Terms without subterms. Note that you should *not* put 'f x' as the 
        -- RHS: that would say that the term was its own subterm!
        x -> pure x

    What does termSubterms do? It’s like traverse: you give it a function that does stuff to subterms, and it will give you one that does that to all the subterms of a particular term. It’s also usable with a lot of lens functions, for example, it’s a Setter so you can write to all the targets of a Traversal.

    Now we can write our constant folder more cleanly:

    constantFold2 :: Term -> Term
    -- 'over' applies a function to all targets of an optic, we can use it with a 
    -- 'Traversal' to apply the function to all of the things which it traverses 
    -- (the subterms)
    constantFold2 t = cf $ over termSubterms constantFold2 t

    I think this is pretty close to our original English specification!

    We can abstract this a little bit further to factor our the local part of the transformation. Then we get a nice little function transformOf which is already defined for us in Control.Lens.Plated.

    -- The real version is a bit more general than this
    -- transformOf :: Traversal' a a -> (a -> a) -> (a -> a)
    -- transformOf l f = go where go = f . over l go
    constantFold3 :: Term -> Term
    constantFold3 = transformOf termSubterms cf

    Folds and mixing Traversals

    As a bonus, we can also do folds. For example, let’s count the number of term nodes in a term.

    countTerms :: Term -> Sum Integer
    countTerms t = 
        -- The number of terms is 1...
        Sum 1 
        -- ... plus the number of terms in all the subterms
        <> foldMapOf termSubterms countTerms t

    Note that we don’t need to do any case analysis since the algorithm happens to be completely generic over the different kinds of term.

    This problem also gives us the opportunity to show off another very useful feature of Traversals: we can mix and match various different Traversals of the same type. In particular, we haven’t counted the types within our terms: if we care about the number of AST nodes then we should probably count them too!

    We need a couple more traversals: one to get the types within a term, and one to get the types within a type.

    termSubtypes :: Traversal' Term Type
    termSubtypes f = \case
        Lam n ty t -> Lam n <$> f ty <*> pure t 
        x -> pure x
    typeSubtypes :: Traversal' Type Type
    typeSubtypes f = \case
        FunType ty1 ty2 -> FunType <$> f ty1 <*> f ty2
        x -> pure x

    Now we can say how to count the nodes in a type, and how to count the nodes in a term. Again, this is completely generic and doesn’t need to do any case analysis.

    countTypeNodes :: Type -> Sum Integer
    countTypeNodes t = 
        -- The number of nodes is 1...
        Sum 1 
        -- ... plus the number of nodes in all the subtypes
        <> foldMapOf typeSubtypes countTypeNodes t
    countTermNodes :: Term -> Sum Integer
    countTermNodes t = 
        -- The number of nodes is 1...
        Sum 1 
        -- ... plus the number of nodes in all the subterms 
        <> foldMapOf termSubterms countTermNodes t
        -- ... plus the number of nodes in all the subtypes
        <> foldMapOf termSubtypes countTypeNodes t

    There are a bunch of other nice tools lens, although as ever that depends on your willingness to wade through it.

    Addendum: why not recursion-schemes?

    You can achieve some of these goals withe recursion-schemes. The style there is to define your type as a fixpoint of a “one-level” functor.

    data Term2F a = 
        Var2F Name
        | Lam2F Name Type a
        | App2F a a
        | Plus2F a a
        | Constant2F Integer
        deriving (Functor, Foldable, Traversable)
    type Term2 = Fix Term2F

    Now, recursion schemes is all about folds, so we can go ahead and “fold” (cata) our term into another term.

    cf' :: Term2F Term2 -> Term2F Term2
    cf' = \case
        Plus2F (Fix (Constant2F i1)) (Fix (Constant2F i2)) -> Constant2F (i1 + i2)
        x -> x
    constantFold4 :: Term2 -> Term2
    constantFold4 = cata (embed . cf') 

    Also, Term2F is of the right shape for Traversable, so we can use traverse as well!

    This is fine as far as it goes, but there are two major problems:

    1. recursion-schemes does badly with mutually recursive types. If this is a problem for you, you’ll realise pretty quickly.
    2. recursion-schemes is good at dealing with the sub-parts of the same type, but not those of different types.

    For example, let’s try and write countTermNodes.

    countTermNodes2 :: Term2 -> Sum Integer
    countTermNodes2 = cata f where
       f = \case
           Lam2F _ ty tc -> Sum 1 <> countTypeNodes ty <> tc
           x -> Sum 1 <> fold x

    The normal case is similarly concise, but there’s no way to handle the types generically. So we have to do the case for Lam manually, and we would have to do this for every term with a type in, if we had others.

    RESPONSES: This post by Oleg Grenrus tackles the mutually recursive traversals problem, and this comment by Chris Penner gives an alternative way of doing the recursion.

  • Shark curiosity

    Certain people (myself included) have a habit of reflexively attacking new arguments or ideas. Amanda Askell calls this “shark curiosity”: sharks bite things partly because their only real way of interacting with the world is their mouth, so biting is their way of finding out what something is.

    Taken literally this implies a rather bleak picture (you attack things because that’s the only way you know to interact with them!?). But I think that the point is rather that to the shark, biting is not necessarily an aggressive action. For curious sharks anyway!

    Collaborative biting

    This is intimately related to collaborative and combative discussions. Curious sharks feel like attacking an argument is collaborative, rather than combative. This may sound counter-intuitive, but I think it’s often a good attitude.

    Firstly, it requires you to be personally distanced from your ideas, so you don’t feel personally attacked if someone criticises your ideas. This is good: being personally invested in your ideas biases you towards them and makes it hard for you to abandon or modify them if they are wrong! And everyone is wrong – a lot.

    This switch in orientation is key to collaborative discussion. Rather than A versus B, it’s A and B versus the problem. The idea is something we both care about (a potential solution to the problem), so we both want to know if it works, and if not, how it is broken. In this frame, someone finding the flaws in your argument is great – it means they’re getting properly engaged in the problem!

    Secondly, it fosters an attitude of base scepticism towards ideas. One thing that studying philosophy taught me is that it’s incredibly easy to make convincing arguments for any and all sides of an issue. Most arguments are bad: unceasing critical thought is our main defence against this.

    Don’t be an asshole

    Of course, sometimes biting is aggressive. And human culture is complicated, so what signals an attack may be influenced by everything from the setting, to the audience, to the relative statuses of the participants. And plenty of people are just assholes. So sharks have to be very careful not to come across that way.

    For me, the most important thing I’ve learned is just to bite gently. Qualify your criticism with uncertain language to make it feel less strong; praise ideas before criticising them; work to establish a collaborative frame of discussion; and so on.

    Knowing your audience is also very important. Some people will be quite happy to get chomping, others will rarely if ever enjoy it. Be sensitive.

    Finally, as Askell says, be careful not to squash new ideas. New ideas are often bad until they’ve been worked on a lot – if we attack them too much we may persuade people to abandon them prematurely. The best thing I can think of is again to be collaborative: if you can see a hole but you think it’s fixable, say so! Maybe you can even work on the patching together.

  • Calling it a day

    From Annihilation by Jeff VanderMeer:

    “So we have nothing.”

    The surveyor ignored that, said “What do we do now?” It was clear she hated asking the question.

    “Eat dinner,” I said. “Take a little stroll along the perimeter to make sure the psychologist isn’t hiding in the bushes. Think about what we’re doing tomorrow.

    "”I’ll tell you one thing we’re not doing tomorrow. We’re not going back into the tunnel.”


    She glared at me.

    Sometimes you just have to call it a day. There’s nothing more you can do (or nothing you want to do), and the best things is to wait. Either for a change in the situation so you can do more, or a change in yourself so you can see what to do.

    Our circadian rhythm is something of a blessing here. Sleep allows time time to pass easily, and our minds to do their mysterious subconscious processing that defeats so many problems. And you have to do it, so “sleep on it” is much easier advice to take than “wait 8 hours and see what happens”.

    Sometimes I’ve wished I never had to sleep. I wonder how many odd, contingent benefits we would lose if we no longer slept. Perhaps we would be more patient… but I suspect the opposite.

  • Post-consequentialist agents

    John cares about nothing but making the most amount of money that he can. He comes to believe that the best way to do this is to start a new company, but also that companies are most likely to succeed when the founder is intrinsically motivated by the work of the company. So John immerses himself in a domain and cultivates an interest. When he finally starts his company, he does it out of a genuine obsession with the idea. He is successful and makes a lot of money.

    This is a prosaic example of an agent modifying themselves to the point at which they are not longer explicitly pursuing their original goals (although the idea is to achieve them nonetheless). Before immersing himself in his field, John1 primarily pursues money. Afterwards, John2 primarily pursues his startup idea, and is willing to sacrifice other ways to make easy money in order to work on it.

    Bernard Williams famously argued that consequentialism is self-effacing: as a theory it recommends that an agent not act according to it or even believe in it. But this is fine, and indeed really a sensible feature of goal-driven system. Believing in or acting according to a moral system is a feature of the world, and a such subject to assessment as to whether it furthers our goals. If an evil demon threatens to torture the world unless we all become Kantians, then we should by golly become Kantians. So we should not generally be surprised to see such “post-consequentialist” agents around.1

    Reflective vs thorough

    However, most consequentialists that I know adopt this as a kind of reflective non-consequentialism. That is, in your normal day-to-day life you act as a non-consequentialist, but when you reflect on your life you are a consequentialist. This is good, since it allows for ongoing correction of your non-consequentialist-but-supposedly-good-overall behaviours via meta-level consequentialist reflection.

    But consequentialist agents can certainly turn into thoroughly non-consequentialist agents who don’t even think consequentially at the meta level. This could happen deliberately, or perhaps just accidentally: if you spend enough time acting non-consequentially you may come to believe it even reflectively. In comparison to a reflective non-consequentialist, a thorough non-consequentialist is an unguided missile: they will keep executing the behavioural strategy that they initially decided on, and can’t correct course later. This is a pretty hefty cost, and risky in a rapidly changing world. We should try and keep the ability to reflectively correct ourselves according to whatever we think the true moral theory is unless there are circumstances that really penalise that.

    Layered reflectivity

    That said, people can have several layers of reflectivity. There is a saying which I have heard (probably falsely) attributed to the Japanese:

    A man has a false heart in his mouth for the world to see, another in his breast to show to his special friends and his family, and the real one, the true one, the secret one, which is never known to anyone except to himself alone, hidden only God knows where.

    I think many people have different modes of assessment that they deploy in different circumstances. It feels very different to do everyday reflection on my life versus deeper or broader assessment of it. So maybe even an apparently thorough non-consequentialist may keep consequentialism in their secret heart.

    1. When I wrote this I was thinking about consequentialism the moral theory, but the same arguments really apply to any value-maximizing goal system. Consequentialism is in many ways just a special case of “expected-value rationality” but applied to particularly moral aims. 

  • Moderating technological progress: a bitter pill

    From The Precipice: Existential Risk and the Future of Humanity by Toby Ord:

    Growing up, I had always been strongly pro-technology. If not for the plausibility of these unconsummated catastrophic risks, I’d remain so. But instead, I am compelled towards a much more ambivalent view. I don’t for a moment think we should cease technological progress—indeed, if some well-meaning regime locked in a permanent freeze on technology, that would probably itself be an existential catastrophe, preventing humanity from ever fulfilling its potential.

    But we do need to treat technological progress with maturity. We should continue our technological developments to make sure we receive the fruits of technology. Yet we must do so very carefully, and if needed, use a significant fraction of the gains from technology to address the potential dangers, ensuring that the balance stays positive. Looking ahead and charting the potential hazards on our horizon is a key step.

    This is oddly one of the things I find hardest to accept about existential risk. From a purely selfish point of view, I care much less about parting with my resources than about the idea that I might get to see less of the future.

    Imagine if well-managed general AI ushers in an era of wild progress: space elevators, life extension, world peace, the whole shebang. But - since we managed it well, it takes another 50 years to arrive and our generation is all dead by that point. That hurts. There’s a part of me that wants to rush and throw the dice just so I might get to see all that.

    But this is right and good. The whole point is to make sacrifices now to benefit others or the future. We should expect some of those sacrifices to hurt!1 Let us not be fair-weather altruists.

    So I agree with Ord: we should slow down development of dangerous technologies where it allows us to make them safer. And where it doesn’t currently help (e.g. because of competition between unscrupulous parties) that is a problem which we should try and solve (e.g. through international cooperation on regulation).

    1. They don’t all need to hurt: I think giving a fraction of your income is a sacrifice that many people in our society can manage without it actually hurting much at all.