I both agree and disagree with you. It is nearly impossible to make one post that communicates strongly to all audiences. If you use an example problem simple enough to be understood by everyone, you almost certainly give up some of the nuänces that would be surfaced by a more complex problem to solve.
Likewise, using a language like JavaScript that is popular but doesn't embrace modern FP, you necessarily end up reinventing a lot of wheels like composition and chaining and partial application.
This can be very instructive for the newcomer, but is nothing but incidental complexity for the more experienced functional programmer.
In the end, I think the world benefits from authors not trying to be all things to all people. We all win if there are a variety of posts about a similar subject, using different languages and solving different complexities of problem.
So yes, 100% this post is not going to meet a lot of programmers' needs. But if there is some set of programmers--no matter how small--for whom it is a good fit, then let's agree that it's valuable and well-written for iuts target audience.
Just to make it explicit; I'm not suggesting Javascript for communicating this type of posts. Without strong typing, this kind of refactoring will immediately become a spaghetti of screaming ducks.
Defunctionalisation is a not-so-rare pattern to encounter and I humbly think choosing a non C-like language to explain it is a waste of opportunity to introduce it to people who can benefit it most (i.e network programmers, game scripting tools programmers, distributed systems programmers etc).
The discussion in this comment section (for this post) is so far friendly. The author is kindly giving up personal time to engage with the readers. There are even people who posted real code pieces to elaborate the topic for people who had hard time to follow. If this is not HN at its best, I don't know what is.
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.
https://docs.microsoft.com/en-us/dotnet/api/system.linq.expr...
https://docs.microsoft.com/en-us/dotnet/csharp/programming-g...
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]."
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."
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.
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.
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.
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.
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...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.
> 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.
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!
Your example in the "Testability" section doesn't involve HOFs. I thought it was interesting to view that example as an instance of defunctionalisation.
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.
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.
The only way to make it the norm is to make it the norm.
Maybe someone sees this...
type Expr =
| Const of int
| CustomOneArg of (int -> int) * Expr
| CustomTwoArgs of (int -> int -> int) * Expr * Expr
...instead of this... interface Expr {
}
class Const extends Expr {
public Integer val;
public (Integer val) {
this.val = val;
}
}
class CustomOneArg extends Expr {
public Function<Integer, Integer> fun;
public int val;
public (Function<Integer, Integer> fun, Integer val) {
this.fun = fun;
this.val = val;
}
}
class CustomTwoArgs extends Expr {
public BiFunction<Integer, Integer, Integer> fun;
public Integer valA;
public Integer valB;
public (BiFunction<Integer, Integer, Integer> fun, Integer valA, Integer valB) {
this.fun = fun;
this.valA = valA;
this.valA = valB;
}
}
... and thinks "I should look into this more".That said, I don't want to put words into the author's mouth, but this particular article looks more "by FPers for FPers" than FP advocacy.
Many programmers have used these techniques even outside FP and would be able to understand it one concept at a time - they aren't advanced concepts to me. It's more that it isn't "easy reading"; but it seems its for an internal audience with assumed background knowledge.
The example you gave is similar to a discriminated union in ML but it is not as robust because the language will not check that every match expression (probably an if-instanceof-ladder in Java) handles every case.
That being said, I may not be the article’s target audience.
I thought, "Okay, great, you're working in a language where you already effectively have to think of it as, 'I'm not telling you how to do this, just defining the concepts.' Fine, but the language has already done most of the work that you ascribed to defunctionalzation. It's already very highly abstracted."
I would have hoped to see defunc appended to an environment that didn't already have the functional lattice to build off of.
And for my part, yes, I have worked with Haskell, enough to do some programs in Project Rosalind and build some codebreakers for classical ciphers, but I still find it hard to read and debug. It just isn't conducive to conceptually breaking down what the code is doing into bite-size pieces. That's probably because I, like most programmers, probably grew up with a procedural mindset and started from languages that enforce procedural thinking. But I suspect it goes beyond that, in being harder to reason about logic as "apply this function to this function to this function which operates on this".
I don't think this is really the same thing. You're discussing the object level; I'm discussing the meta-level.
Haskell is based around "define the concepts as you would naturally define them and I'll use that definition to create a program". However, this is entirely implicit in the language. Defunctionalisation explicitly reifies this, allowing the language to discuss how it does it.
I see your point as basically "what's the use of continuations? I already have `goto`".
>I see your point as basically "what's the use of continuations? I already have `goto`".
If I were trying to convince skeptics about the merits of structured programing (i.e. no goto), I wouldn't start from Java and merrily introduce try/catch in that context. I start from a BASIC program, explain the semantics of e.g. a while loop, and replace some program's gotos with while loops, and then tackle increasingly "stubborn" gotos.
And yes, I hope you would be able to explain the benefits of continuations to a goto-fanatic, regardless of how much inferential distance there is.
If you want to learn basic functional programming, look for basic functional programming tutorials.
I'm a strong advocate of pseudocode. I've had a few situations where I explained something online in Python, people complained they didn't know Python and couldn't understand it, so I just sort of arbitrarily change the syntax a bit so its inconsistent, and people reacted much better to it. Throw in a curly bracket and semicolon, maybe an arrow or two, write a line in English sometimes, invent syntax on the fly and then use completely different syntax on the next line. You wound think that would harm comprehension, but actually I've found that it focuses people on what's important and gives them an idea of what to follow along with (the ideas, instead of the syntax which is different from one line to the other).
That said, ADTs and pattern matching I can see needing care to making the article understandable to people on the fringes of your target audience, but if you can't handle functions and recursion, then you're not a programmer with the sufficient expertise to make use of the article in the first place. The target is already functional programmers who know enough about functional programming that stating a problem in purely functional terms is a requirement for the refactoring technique. If you can't state things in terms of first order functions and recursion, then you can't perform the underappreciated tool for which the article is based on.
In conclusion, use pseudocode and imagine your audience is slightly sleep deprived from having a screaming baby at home.
Looking up the definition on wikipedia definitely didn't help: "In mathematics, an initial algebra is an initial object in the category of F-algebras for a given endofunctor F". Oof, I think I would need semesters worth of higher level university math to even begin to understand that.
I'm probably just not the target audience for this, but I frequently think people avoid functional languages because they (appear to) require an understanding of math that the vast majority of coders have never been exposed to.
The code examples are given assuming the reader already knows the language and runtime -- not once in the article does it say what this language is or explain the syntax/grammar rules. I would take it to mean this isn't meant for a broad audience, or the author has made a common curse of knowledge[0] mistake.
[0]: "The curse of knowledge is a cognitive bias that occurs when an individual, communicating with other individuals, unknowingly assumes that the others have the background to understand." https://en.wikipedia.org/wiki/Curse_of_knowledge
Parenthetical aside: I could have been rescued from this by a sufficiently advanced Markdown renderer, and in fact the HTML source is annotated with `lang-fsharp`, but that metadata did not make its way up to the reader.
On one hand, it feels similar, especially if the Command class is "sealed".
On the other hand, it feels like completely the opposite since the command classes contain the code they execute and act like lambdas.
I guess you could apply a visitor pattern on top of the command pattern to make it truly like defunctionalization. I hope nobody actually does this.
In a proper functional language, you do not need objects for the latter, as you can directly compose functions.
That being said, the ability to add more operations than just "execute" to your commands allows you to emulate the features of deep embedding (e.g., serialization). But you have to extend every command for a single new operation (read up on the expression problem). That style is known as tagless in the FPL community, btw.
I learned Lisp and was into Clojure for awhile - do I write it professionally? No, but I've adopted some of its ideas and tenets in my own code for work.
And many programmers use JavaScript so they could easily start adopting this mechanism in their actual programs.
German verbs and subjects is backward in order to English sentence structures.
It's not necessary to Cobolize everything to make it superficially acceptable to people who refused to learn basic language.
1. Serializable, scriptable configuration parsing (i.e used widely in video games such as visual novels)
2. RPC over network where request/response paradigm isn't applicable (i.e a distributed state machine, language server etc)
Both of these can be worked around with existing techniques but they can also benefit from defunctionalization for much better debug-ability.
In my comment, I stated that even non-junior programmers have hard time reading these kind of articles and I believe they already deal with problems like 1 and 2 in their career.
Well, it depends. My experience is that being aware of how lambda lifting/defunctionalization works actually makes first-class functions/HOFs a lot easier to understand as a language feature, even to a novice programmer. It's precisely the "missing link" between that language feature and the usual case of first-order functions/subroutines. Same for other "high-level" features known from FP and other programming paradigms - there are way too many of those to list them, really.
There are a lot of "senior programmers/developers/engineers/whatever other term you want to use" that don't know about these techniques. More broadly they don't know about a lot of the features and functionalities of functional programming and more generally higher order (as in function) programming paradigms.
If we don't write introductory articles in a way that those outside the subfield can grasp them, we are alienating large groups of new-guard and old-guard programmers who could benefit greatly from understanding the techniques that not only help them improve their code and productivity, but also the techniques that allow them to use high level features without paying for the cost of them.
Anecdote: I've worked with a senior engineer on a C++ project. We used C++11 but effectively we wrote C++98 style code because they had largely unfounded fears of not only the performance impacts of utilising new features and FP paradigms in their codebase, but also the debugging and readability impacts of using them. I found that many of the articles and videos I would send them to try to ease those fears ended up falling flat due to them not targetting his audience. It took me slowly writing up internal memos and presentations on these various features, and showing how they came at little to no cost while providing their benefits for our team to actually start using them. Now they like to joke about how "In 2019 I did the impossible and helped drag them kicking and screaming into 2011".
On your last comment: You claim that we shouldn't need to "Cobalize everything to make it superficially acceptable to people who refused to learn basic language" but the issue is a matter of priorities. For a new engineer learning the language is important however for senior engineers and leadership, these are not the most important concerns. The important stuff is the following in order:
- Actually delivering a product.
- Making the product stable, easy to maintain, easy to debug/validate/test, and easy to modify/improve without introducing issues.
- Making sure that the product ages well, handles staff churn without losing design intent, and doesn't unnecessarily accrue technical debt.
- Ensuring that new staff can be easily on-boarded and become productive.
It should come to no surprise that senior staff are hesitant to waste time on what could potentially be fads or misinformed design choices. They won't waste time on learning something they don't think will be useful or pay off and as a result, unless introductory content includes them in the intended audience, they never will get a chance to find value in these concepts.
One last note: Sorry if I rambled a bit, I'm typing this up real quick while I take a break and I've been a bit all over the place recently. If I don't seem clear about anything, ask me to clarify and I will.
Don't get me wrong, I love functional programming. I use Haskell and OCaml with joy. I also read about Idris, F#, Elixir and such quite often but I can also remember when all of this was alien to me.
Useful advice requires accessible set of examples and the very first example in this article (basic calculator) already make use of sum types, pattern matching, higher order functions and recursion, in a programming language with a relatively low adoption rate.
I don't know a solution to this issue without giving extra burden to the author. They can use one pure functional language alongside with a widely used, strongly typed language (Typescript, C++ etc) in their examples but that's probably too much to ask for.
Maybe my understanding of the target audience is wrong and my whole criticism is obsolete. Please correct me if that is the case.
I have friends with 5+ years of industry experience with languages like C#, Javascript, Java, PHP and they tend to verify my claims about accessibility of these type of articles.
Does anyone agree/disagree?