F# functional way to transform DU based ASTs

Question

In OOP land, take for example Roslyn and it's syntax rewriters, using visitor pattern. This is very nice, as there is already a base rewriter class, that defines all visit methods with do nothing, and I just have to override the methods that I care about.

What would be a comparable solution with the DU kind of ASTs?

Eg if I would like to write a function that visits every node of an AST parsed with the following snippet (not made by me))

I can write transformer functions like so

// strip all class type modifiers because of reasons
let typeTransformer (input:CSharpType) : CSharpType =
    match input with
    | Class (access, modifier, name, implements, members) ->
        Class (access, None, name, implements, members)
    | _ -> input

let rec nameSpaceTransformer typeTransformer (input:NamespaceScope) : NamespaceScope =
    match input with
    | Namespace (imports, names, nestedNamespaces) ->
        Namespace (imports, names, List.map (nameSpaceTransformer typeTransformer) nestedNamespaces)
    | Types (names, types) ->
        Types (names, List.map typeTransformer types)

This is already pretty cumbersome, but it gets worse and worse, the deeper one gets into the tree. Does this representation just not lend itself to these kinds of transformations?

Edit: what I am actually looking for, is a way where I can define just the specific transform functions that will then be automatically applied to the correct nodes, while everything else remains unchanged.

Here is my best try so far on a simplified example (Fable REPL) Note the last 2 lets after the comment, in later usage, one should only need to write those 2 and then call transform replaceAllAsWithBsTransformer someAstRoot with an actual AST instance. Of course this solution does not work correctly, because it would require recursive records. (eg the transformMiddleNode function should really ask for a the transformer record itself and ask for it's transformLeaf member).

This is the part where I have trouble with, and which I would say is nicely solved by OOP visitor pattern, but I can't figure out how to mirror it successfully here.

Edit 2:

At the end of the day, I went with just implementing an actual visitor class in the form of

type Transformer() =
    abstract member TransformLeaf : Leaf -> Leaf
    default this.TransformLeaf leaf = id leaf
    abstract member TransformMiddleNode : MiddleNode -> MiddleNode
    default this.TransformMiddleNode node =
        match node with
        | MoreNodes nodeList ->
            List.map this.TransformMiddleNode nodeList
            |> MoreNodes
        | Leaf leaf -> this.TransformLeaf leaf |> Leaf
    abstract member TransformUpperNode : UpperNode -> UpperNode
    default this.TransformUpperNode node =
        match node with
        | MoreUpperNodes nodeList ->
            List.map TransformUpperNode nodeList |> MoreUpperNodes
        | MiddleNodes nodeList ->
            List.map TransformMiddleNode nodeList |> MiddleNodes
        ...

and then I can define specific transformations like:

type LeafTransformer()
    inherit Transformer()
    override this.TransformLeaf leaf = someLeafTransformation leaf

where someLeafTransformation: Leaf -> Leaf This is not any worse than the OOP solution (is essentially the same, except the "bottom level" visitor interfaces are replaced by pattern matching.

Answer 1

what I am actually looking for, is a way where I can define just the specific transform functions that will then be automatically applied to the correct nodes, while everything else remains unchanged.

I wrote an AST transformation library called FSharp.Text.Experimental.Transform that does exactly this. Coincidentally I've already written a C# grammar definition so I was able to use to try out your "strip class modifiers" problem.

Your solution, implemented using this library, starts by feeding the C# grammar definition into the GrammarProvider type provider. The type provider will provide methods for parsing the input text, and provides a type for each non-terminal in the grammar.

open FSharp.Text.Experimental.Transform

type CSharp = GrammarProvider<"csharp.grm">

Next, you define your transformation function that just operates on the nodes you care about. Since you care about transforming the modifiers for a class, you'll target the ClassModifier* part of the ClassDefinition grammar production

// This function replaces any list of class modifiers with the empty list
let stripClassModifiers (_: CSharp.ClassModifier list) = []

Finally, you parse the input text, apply your transformation function, then unparse to a string:

CSharp.ParseFile("path/to/program.cs").ApplyOnePass(stripClassModifiers).ToString()

The ApplyOnePass() method will perform a single pass over the AST, applying your stripClassModifiers transformation wherever it finds a list of class modifiers and leaving all the other nodes untouched.

The library contains more powerful methods for more complex transformations, but I hope the example above suffices to illustrate the idea. See the library documentation for tutorials, examples, API reference, and more details on what it can do.

Answer 2

Certainly the code you posted is doing it the "functional way". It's not clear to me exactly how this is "cumbersome" or "gets worse the deeper one gets into the tree". I think the key concept here is just to write your functions as concisely as possible (but not so concise they become unreadable!) and then figuring out the right mix of helper functions and higher level functions that rely on those, plus good comments where needed.

Your first function could just be this:

let transformModifier input =
    match input with
    | Class (a, modifier, c, d, e) -> (a, None, b, c, d)
    | _ -> input

This is less verbose, but still readable. In fact, it's probably more readable as it's obvious now that the only thing this does is change the class modifier.

Perhaps you will want to create other functions that modify classes, and compose these using >>, then call them from a larger function that walks the whole tree.

The ultimate readability of the code is going to be mostly up to you (IMO).

There are good discussions of AST transformations in the books Expert F# and F# Deep Dives.