News for hackers. Stuff that matters.
Re:Defunctionalisation: An underappreciated tool for writing... by Smaug123 on Monday March 09, 2020 @10:14AM (#22525472)
I (author) agree with you. The target audience of this post was originally my coworkers, if I even targeted it at all; but there is certainly room in the world for more basic explanations targeted at people who aren't used to the idioms of functional programming.

The trouble is really that defunctionalisation is much, much easier if you've got sum types, pattern-matching, and higher-order functions. (It's not clear to me that it has any use at all if you don't have higher-order functions.) Is it worth the time trying to implement this sort of pattern in C#? I don't know. Insofar as C# is nice to write, it's because the IDE writes so much of the boilerplate for you, and no IDE is set up to admit this kind of pattern.

Re:Defunctionalisation: An underappreciated tool for writing... by barrkel on Monday March 09, 2020 @04:29PM (#22529396)
C#'s Expression<T> is almost exactly what you use in your example, baked into the language - you specify a lambda but the compiler emits construction of an expression tree.

https://docs.microsoft.com/en-us/dotnet/api/system.linq.expr...

https://docs.microsoft.com/en-us/dotnet/csharp/programming-g...

Re:Defunctionalisation: An underappreciated tool for writing... by Smaug123 on Wednesday March 11, 2020 @03:00AM (#22543724)
Indeed, we have used `Expr` and the `ReflectedDefinition` attribute internally in F#. However, if the user is capable of giving you literally anything, you'll struggle to optimise it! We've found it important to artificially restrict what the user can give us, by explicitly modelling the domain.
Re:Defunctionalisation: An underappreciated tool for writing... by jrandm on Monday March 09, 2020 @03:32PM (#22528867)
If you happen to see this, during an editing pass it would help to include information about what language you're using to present your code examples when the article is standalone for a wide audience.

Something like:

"For this section and the next, let us imagine the guts of a very basic calculator application, expressed in the initial algebra style, using [your language and environment]."

Re:Defunctionalisation: An underappreciated tool for writing... by jerf on Monday March 09, 2020 @11:18AM (#22526056)
"(It's not clear to me that it has any use at all if you don't have higher-order functions.)"

It can be done. There are plenty of C codebases that end up having something defunctionalized eventually. It's arguably one of the main pressures that causes Greenspun's 10th Rule [1] to be so accurate; as your codebase grows the odds that you'll be forced to defunctionalize something significant in your code goes to 100%.

It isn't any fun, though.

[1]: "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."

Re:Defunctionalisation: An underappreciated tool for writing... by syrak on Monday March 09, 2020 @01:34PM (#22527469)
> It's not clear to me that it has any use at all if you don't have higher-order functions.

The very origin of defunctionalization is to emulate higher-order functions in a language without them.

https://en.wikipedia.org/wiki/Defunctionalization

> defunctionalization refers to a compile-time transformation which eliminates higher-order functions, replacing them by a single first-order apply function.

Re:Defunctionalisation: An underappreciated tool for writing... by samatman on Monday March 09, 2020 @04:23PM (#22529355)
The author has indicated that this blog post was an internal communique which escaped confinement, so this isn't intended as criticism:

For a general audience, linking the first instance of the string "defunctionalization" to this Wikipedia article would help people get up to speed. I'm not embarrassed to admit that I had never heard of it, and as a consequence I'm learning more from the Wiki than I learned from the Fine Article.

Re:Defunctionalisation: An underappreciated tool for writing... by Smaug123 on Monday March 09, 2020 @05:48PM (#22530206)
It didn't exactly escape confinement; rather, I originally wrote much of this content for internal purposes and then realised it would be good to publish it externally.

True, since I linked "closure" I should probably have linked the main topic of the article. Honestly, though, I'm not sure the Wikipedia article is very comprehensible at all; I'm hoping mine is more so.

Re:Defunctionalisation: An underappreciated tool for writing... by samatman on Monday March 09, 2020 @10:53PM (#22532342)
It's not a great Wikipedia entry, agreed.

I was left wondering if the topic is inherently that difficult or if this is just another case of le Wik being kinda dense for maths and comp sci. Looking around a bit at other links in this thread, I'm gathering it's the latter.

Re:Defunctionalisation: An underappreciated tool for writing... by louthy on Monday March 09, 2020 @05:51PM (#22530248)
Here's [1] the first example in C# (using language-ext [2] to provide unions)

    static void Main()
    {
        var expr = TwoArg.New(Add.New(), Constant.New(1), Constant.New(1));
        var res = ExprModule.Interpret(expr);
    }

    [Union]
    public interface OneArgFunction
    {
        OneArgFunction Negate();
        OneArgFunction Custom1(Func<int, int> x);
    }

    [Union]
    public interface TwoArgFunction
    {
        TwoArgFunction Add();
        TwoArgFunction Subtract();
        TwoArgFunction Custom2(Func<int, int, int> x);
    }

    [Union]
    public interface Expr
    {
        Expr Constant(int x);
        Expr OneArg(OneArgFunction f, Expr x);
        Expr TwoArg(TwoArgFunction f, Expr x, Expr y);
    }
        
    public static class OneArgFunctionModule
    {
        public static Func<int, int> Interpret(OneArgFunction f) => f switch
        {
            Negate _         => x => -x,
            Custom1 (var fn) => fn
        };
    }
        
    public static class TwoArgFunctionModule
    {
        public static Func<int, int, int> Interpret(TwoArgFunction f) => f switch
        {
            Add _            => (x, y) => x + y,
            Subtract _       => (x, y) => x - y,
            Custom2 (var fn) => fn
        };
    }

    public static class ExprModule
    {
        public static int Interpret(Expr e) => e switch
        {
            Constant (var x)             => x,
            OneArg (var f, var x)        => OneArgFunctionModule.Interpret(f)(Interpret(x)),
            TwoArg (var f, var x, var y) => TwoArgFunctionModule.Interpret(f)(Interpret(x), Interpret(y)),
        };
    }

[1] https://gist.github.com/louthy/54e216373d71b7fb4ceb5c619ea32...

[2] https://github.com/louthy/language-ext/

Re:Defunctionalisation: An underappreciated tool for writing... by balfirevic on Monday March 09, 2020 @07:46PM (#22531216)
Hey, when did language-ext get roslyn-based code generation? That's awesome!

Do you know if it's widely used yet? Any insights/gotchas to share? I see it's using CodeGeneration.Roslyn.BuildTime, I wanted to use it to make my own sum types library for c# for some time now, but never got around to it.

Re:Defunctionalisation: An underappreciated tool for writing... by louthy on Tuesday March 10, 2020 @08:06AM (#22534701)
A more in-depth reply :)

> Do you know if it's widely used yet?

Not sure which project you mean?

* Roslyn code-gen - not many

* LanguageExt.Core - yes, lots - 1.6 million downloads on nuget and counting

* LanguageExt.CodeGen - not much from what I can tell, but that might be because there's the runtime Record system that makes a type have structural equality/ordering/hashing and serialisation by just deriving it from Record<TYPE>, i.e.

    public class Person : Record<Person>
    {
        public readonly string Name;
        public readonly string Surname;
        public Person(string name, surname) => 
           (Name, Surname) = (name, surname)
    }
It builds the IL and compiles it on first-use, so it's code-gen without any of the hassle of setting up the tool chain.

Some of the additional benefits of using the CodeGen instead is that the With function and lenses are built automatically, but that might not be enough to make people use it. Also, things like [Union] and [Free] (monad) are relatively new, so perhaps it wasn't compelling enough until recently. There's obviously benefits to compiling the code up-front rather than generating the IL, so I'd expect it to pick up over time.

I and my team certainly use it a lot ;)

> Any insights/gotchas to share? I see it's using CodeGeneration.Roslyn.BuildTime

None really, the CodeGeneration.Roslyn.BuildTime hasn't had much love, and a new version they built (to support plugins) just fundamentally didn't work, so it clearly wasn't tested properly. But, the version I'm using is stable right now, I just can't migrate to .NET Standard 2.1 until they bring the new one out, so that is a limiting factor for me at the moment.

Re:Defunctionalisation: An underappreciated tool for writing... by balfirevic on Tuesday March 10, 2020 @08:38AM (#22534866)
> LanguageExt.CodeGen - not much from what I can tell

Yes, I meant that one.

> None really, the CodeGeneration.Roslyn.BuildTime hasn't had much love, and a new version they built (to support plugins) just fundamentally didn't work, so it clearly wasn't tested properly. But, the version I'm using is stable right now, I just can't migrate to .NET Standard 2.1 until they bring the new one out, so that is a limiting factor for me at the moment.

Ah, that's too bad. Visual Studio 2019 finally has a really nice and frictionless way to do code generation, but it is pretty complicated to bootstrap all the stuff that CodeGeneration.Rosylin takes care of. I wish Microsoft sponsored or supported it in some way. There is also a fork of it at https://github.com/mwpowellhtx/Code.Generation.Roslyn, but I don't know how well it works.

Thanks for all the answers!

Re:Defunctionalisation: An underappreciated tool for writing... by louthy on Monday March 09, 2020 @08:46PM (#22531602)
I guess about a year or so. I have some docs on the wiki re the code-gen features. I’m writing this on my phone atm, so I’ll do a fuller reply to your qs when I’m back in front of my PC

https://github.com/louthy/language-ext/wiki/Code-generation

Re:Defunctionalisation: An underappreciated tool for writing... by Chris_Newton on Monday March 09, 2020 @01:11PM (#22527148)
The idea of producing a description of some effectful computation that is later interpreted instead of generating the effects directly is certainly applicable more widely than just functional programming. For example, the Command pattern described in the book Design Patterns is broadly analogous in object-oriented programming and provides similar advantages. (Edit: On reflection, the Interpreter pattern might be a better example, but the main point stands.)
Re:Defunctionalisation: An underappreciated tool for writing... by edflsafoiewq on Monday March 09, 2020 @10:19AM (#22525514)
> It's not clear to me that it has any use at all if you don't have higher-order functions

Your example in the "Testability" section doesn't involve HOFs. I thought it was interesting to view that example as an instance of defunctionalisation.

Re:Defunctionalisation: An underappreciated tool for writing... by Smaug123 on Monday March 09, 2020 @10:24AM (#22525569)
I guess that's true. It was my inner compiler-writer speaking there. (To match defunctionalisation with the initial algebra pattern does require HOFs in all but the simplest cases, I think.)
Re:Defunctionalisation: An underappreciated tool for writing... by efdee on Monday March 09, 2020 @12:35PM (#22526757)
> Insofar as C# is nice to write, it's because the IDE writes so much of the boilerplate for you, and no IDE is set up to admit this kind of pattern. No offense, but it kind of sounds like you haven't worked with C# since 2001 or so.
Re:Defunctionalisation: An underappreciated tool for writing... by Smaug123 on Monday March 09, 2020 @12:40PM (#22526797)
I certainly wouldn't describe myself as a C# expert, true. I interact with it on a weekly basis, but no more than that. Please make allowances for the fact that I am spoiled by F#!
Re:Defunctionalisation: An underappreciated tool for writing... by bedatadriven on Monday March 09, 2020 @06:27PM (#22530594)
I'm lead developer of a quite large Java code base and I found the artivle super helpful in giving a name and shape to something I've half observed but really come to appreciate.

Over the past two years we've been slowly moving our code base in this direction general, eliminating Exceptions, for example, in favor of more detailed Result<ValueT, ErrorT> return types.

With lamdas, writing this kind of code does require more boilerplate in Java, but it's getting better.

Nonetheless, ADTs and pattern matching are sorely missed. The Visitor pattern is an alternative and is well worth it for key data structures, but is too verbose for one off usage.

Re:Defunctionalisation: An underappreciated tool for writing... by sitkack on Monday March 09, 2020 @12:29PM (#22526696)
You can agree, but it doesn't mean you should have changed anything you did. The only thing I would add is the meta analysis you have included here. To write your post in a language without those features would have either made it into OOsagne or tripled the lines of code.

The metaidea is to stay at a richer abstraction level for longer, and then drop down in the last moment for execution? One doesn't always have a chance to do this, being able to detect when to apply the technique would be a good lesson.

Rather than reworking the post to meet the imperative programmers in their safe space, it could entice them into your crystal palace.