The Quest For Nice Tree Transforms seems to be a common one among compiler nerds. Now, most gang-of-four design patterns strike me as “things you do when you don’t have a sufficiently powerful language”, but it turns out that at least for Rust, the visitor pattern, when implemented a certain way, solves this very nicely. A little tedious to get all the boilerplate written the first time, but after that it pretty much Just Works.
The trick is to have a visitor with visit_thing() methods that you can easily overload to implement what you want, and then have walk_thing() methods which do one step of recursion and call back into the visit_*() methods. Upon inspection it looks like their fmap() approach does the same thing, which is pretty metal. When I (and others) tried a functor/recursion scheme style pattern I had a map() function that did all the walking and each transformation just returned a new node without having to call fmap(), but that ends up horribly rife with special cases.
It’s been a little while since I read the “gang of four” book, but IIRC the key concept of the design patterns isn’t to explicitly create a class called “Iterator” or a “Visitor” class with a visit() method, but to use the pattern name to describe the design. Admittedly, it’s a difficult to get that message from the original book because it’s steeped in OOP dogma.
In Lisp, if I do this:
(defun process-item (some-thing)
;; Do other stuff
(print some-thing)))
(map nil #'process-item (fetch-some-list-of-items ...)))
I’m conceptually using the Visitor pattern, since the code is visiting each item and performing some action on it.
It is possible to create a clunky “Visitor” base class (or mixin) and then require sub-classes that override a “visit_thing()” method, but that’s an implementation detail, and not required to use the pattern.
I like the idea of Design Patterns, but I think they got a bad rap being so closely associated with OOP.
I don’t know Swift nor Rust, but from the description, this sounds like something I’ve done a few times in D. Here’s a somewhat similar example from my DOM library: https://opendlang.org/library/source/arsd.dom.d.html#L4253 going for 25 lines - it returns a wrapped DOM Element that takes any method that returns another Element (or subclass), string, or void and wraps them up to return a similarly wrapped thing.
So consider original code like element.querySelector("foo").innerHTML. You’re supposed to check for null each step - querySelector returns null if foo is not found, then null.innerHTML is a null pointer deref and thus a program crash.
But if you use that MaybeNullElement wrapper, if it is null, it doesn’t deref it and just returns another MaybeNullElement, kicking the can down the road, until something returns string or void, which are harmless. (…actually looking at my code there, I didn’t wrap it if non-null, so it might not work if done multiple levels, but that’s an easy fix). That one opDispatch function is similar to a compile-time method_missing; it lets you forward the name and arguments right along, so this one little 25 line thing applies to the entire object with its dozens of properties and methods. It also possible to wrap them all via a foreach loop over the allMembers trait - compile-time reflection.
So this same technique ought to apply to the other transforms the blog author has in mind too.
A related thing to the idea of tree transforms is the visitor pattern, as other comments mention, but what I like for that is a multiple dynamic dispatch. That’s basically what visitor does, but again something you can automate a great deal in D: https://opendlang.org/library/arsd.mvd.html - view source and you’ll see the implementation is < 100 lines (followed by 100 lines of unit tests) - since it does compile time reflection to loop over function params, then some runtime type checks to see the dynamic type of an object compared to the static types of the function to dispatch to the most derived implementation available in the set.
So, if you provide a void foo(DerivedType d) it will be preferred over a generic void foo(Object d), with the generic one taking all other objects passed in. All return values must be compatible though, but it does this fairly generically too, returning the most specialized common type of the available overloads (so if one returned Object, all will be converted to Object, but if they all returned DerivedType, it’d respect that in the output too).
The combination of compile time reflection and runtime information in generated functions is pretty cool to play with.
The Quest For Nice Tree Transforms seems to be a common one among compiler nerds. Now, most gang-of-four design patterns strike me as “things you do when you don’t have a sufficiently powerful language”, but it turns out that at least for Rust, the visitor pattern, when implemented a certain way, solves this very nicely. A little tedious to get all the boilerplate written the first time, but after that it pretty much Just Works.
The trick is to have a visitor with
visit_thing()methods that you can easily overload to implement what you want, and then havewalk_thing()methods which do one step of recursion and call back into thevisit_*()methods. Upon inspection it looks like theirfmap()approach does the same thing, which is pretty metal. When I (and others) tried a functor/recursion scheme style pattern I had amap()function that did all the walking and each transformation just returned a new node without having to callfmap(), but that ends up horribly rife with special cases.It’s been a little while since I read the “gang of four” book, but IIRC the key concept of the design patterns isn’t to explicitly create a class called “Iterator” or a “Visitor” class with a visit() method, but to use the pattern name to describe the design. Admittedly, it’s a difficult to get that message from the original book because it’s steeped in OOP dogma.
In Lisp, if I do this:
I’m conceptually using the Visitor pattern, since the code is visiting each item and performing some action on it.
It is possible to create a clunky “Visitor” base class (or mixin) and then require sub-classes that override a “visit_thing()” method, but that’s an implementation detail, and not required to use the pattern.
I like the idea of Design Patterns, but I think they got a bad rap being so closely associated with OOP.
Indeed. This reminds me of a comment of mine.
Absolutely delightful, thank you!
I think this is the exact problem described in https://www.microsoft.com/en-us/research/wp-content/uploads/2003/01/hmap.pdf by Simon Peyton-Jones
I don’t know Swift nor Rust, but from the description, this sounds like something I’ve done a few times in D. Here’s a somewhat similar example from my DOM library: https://opendlang.org/library/source/arsd.dom.d.html#L4253 going for 25 lines - it returns a wrapped DOM
Elementthat takes any method that returns anotherElement(or subclass),string, orvoidand wraps them up to return a similarly wrapped thing.So consider original code like
element.querySelector("foo").innerHTML. You’re supposed to check for null each step - querySelector returns null if foo is not found, then null.innerHTML is a null pointer deref and thus a program crash.But if you use that
MaybeNullElementwrapper, if it is null, it doesn’t deref it and just returns another MaybeNullElement, kicking the can down the road, until something returns string or void, which are harmless. (…actually looking at my code there, I didn’t wrap it if non-null, so it might not work if done multiple levels, but that’s an easy fix). That oneopDispatchfunction is similar to a compile-timemethod_missing; it lets you forward the name and arguments right along, so this one little 25 line thing applies to the entire object with its dozens of properties and methods. It also possible to wrap them all via aforeachloop over the allMembers trait - compile-time reflection.So this same technique ought to apply to the other transforms the blog author has in mind too.
A related thing to the idea of tree transforms is the visitor pattern, as other comments mention, but what I like for that is a multiple dynamic dispatch. That’s basically what visitor does, but again something you can automate a great deal in D: https://opendlang.org/library/arsd.mvd.html - view source and you’ll see the implementation is < 100 lines (followed by 100 lines of unit tests) - since it does compile time reflection to loop over function params, then some runtime type checks to see the dynamic type of an object compared to the static types of the function to dispatch to the most derived implementation available in the set.
So, if you provide a
void foo(DerivedType d)it will be preferred over a genericvoid foo(Object d), with the generic one taking all other objects passed in. All return values must be compatible though, but it does this fairly generically too, returning the most specialized common type of the available overloads (so if one returned Object, all will be converted to Object, but if they all returned DerivedType, it’d respect that in the output too).The combination of compile time reflection and runtime information in generated functions is pretty cool to play with.