About Values, Lenses, Update-in, Assoc-in, C# and F#

2012-08-15

People seem to find that my blog posts overall have a quite negative touch. And while this might scare off the small number of my readers, this post will continue the series.

Some months ago, I took some time to take a look at functional programming languages again and found F# to be a suitable contenter to expand my knowledge in this field. At that time, functional programming wasn’t quite new to me. A decade ago, I wrote a few tools in Haskell, but soon lost interest, because I were quite disappointed from the hurdles introduced by interopability issues with existing C libraries.

Now, with F#, all the .NET APIs are accessible from within the language and the IDE support looks quite reasonable.

Then I played around a little, tried to spawn some actors and soon got addicted to the elegance of immutability, which seemed to be – at first sight – strongly supported by F#.

F#’s declarations are by default immutable. Records, a means to create abstract data types, are immutable and offer a convenient syntax to create a copy with individual members changed.

This all looked great and motivated me to try F# for a larger project. And while I do think that F# is perfectly capable to create large and reliable software, I don’t think that F#’s immutibility support can scale up to real world requirements (I’d love you to prove me wrong in this regard!).

All this came up to me yesterday again, when I watched Rich Hickey’s keynote “The Value of Values'”, in which Rich strongly advocates the use values over anything else.

And while I really do like to use value types, and I don’t actually care so much about a small performance hit involved, I do see one missing feature from F# that hinders me using value types.

That is, the possibility to change value types that are complex in nature:

Nested, associative, tree or graph-like values are hard to change in F# (and most other languages), because the burden of rebuilding all the referencing structures up to the root is up to the developer.

There is no language support yet that can be used to update a value that is deeply nested inside an immutable data type. And that’s probably one of the most missed feature that dragged me back to C# where I feel most comfortable with.

One other related feature that I miss, are macros. Macros could probably be used to implement many of the features that are missing from F# and – while I am not exactly sure – may be used to implement what’s required to handle complex value types.

I am not alone with this viewpoint. For statically typed funcional languages there are several implementations of “Lenses” and even a suggestion to implement Lenses in F#. Lenses are composible accessors that can be used to modify nested values and automatically copy and update data structures without changing what was already there. A nice idea, but obviously an implementation detail that should be baked into the language or at least be automatically generated.

I’ve tried to implement automatic lenses in F# by using a type provider that should create a lense for each member. But sadly, type providers can not be parameterized over types.

But there are simpler alternatives to lenses. As you might know, Rich, who brought us the wonderful word “complected” (another word for coupled, but with a strong negative undertone), also created Clojure, a dynamically typed, functional language. And while he is advocating the use value types, Clojure, which is not pure in any respect (it’s heavily “complected” with the JVM, for example), includes two macros that do exactly what other languages miss:

These are the update-in and assoc-in macros, which can be used to copy and update nested immutable data types in one go. For quite a while now, these two macros induced a lot of language-envy in me, and after watching Rich’s talk about values yesterday, I tried to implement update-in for C#. My first humble steps are on Github and the project is called Facts. The implementation is based on Reflections and while using Reflections is actually pretty slow but can be optimized, the slowest part is the recurring creation of the expression tree that is used to identify the member chain. And for that, which causes about 5/6th of the performance hit, I can not see an optimization option yet.

In the current version, a simple update with one member is about 300 times slower than a manual copy and in-place update. That’s hard to digest.

If nothing new comes up over the next few days, I will probably start looking into modifying complex immutable structures by using a method similar to continuation passing style programming, in which each continuation updates only a part of a nested immutable data structure.

If you like to start a discussion about handling complex immutable data types or want to share any of your related experience, please leave a comment below or contact me on twitter.