38

This question started out from

  1. My translating of "ML for the Working Programmer" (WorldCat) by L. C. PAULSON to F# which uses functors for the examples.
  2. Eventual desire to translate "Purely Functional Data Structures" (WorldCat) by Chris Okasaki which uses functors.
  3. Reading "CATEGORIES TYPES AND STRUCTURES - An Introduction to Category Theory for the working computer scientist" (WorldCat) by Andrea Asperti and Giuseppe Longo.
  4. Not understanding it all, mostly the category theory.

SML.NET can do functors and worked with Microsoft .NET.
* See: SML.NET User Guide Section 4.8.2 Class types and functors?

I keep seeing that F# cannot do true functors because of some limitation in Microsoft .NET.
* Can ML functors be fully encoded in .NET (C#/F#)?
* Any workaround for functor?

So if SML.NET could do functors on .NET then why can't F#? What did SML.NET do that F# can't?

The more I learn about functors coming from category theory, the more I see the beauty of them and desire to have them in F#.

EDIT

In a pursuit to better understand the relation between category theory and functional programming see these Q&A at CS:StackExchange.

Community
  • 1
  • 1
Guy Coder
  • 24,501
  • 8
  • 71
  • 136
  • Since people have this question stared, I am adding a link to this paper as they might find the paper of interest. [Physics, Topology, Logic and Computation: A Rosetta Stone](http://arxiv.org/pdf/0903.0340v3.pdf) – Guy Coder Jun 30 '14 at 12:16
  • Of interest: [Generics of a Higher Kind](http://adriaanm.github.io/files/higher.pdf) and [What is a higher kinded type in Scala?](http://stackoverflow.com/questions/6246719/what-is-a-higher-kinded-type-in-scala) and [Add Higher Order Generics to F# - (Type Classes)](https://visualstudio.uservoice.com/forums/121579-visual-studio/suggestions/2228766-add-higher-order-generics-to-f-type-classes-) – Guy Coder Feb 28 '16 at 13:56
  • Of interest: [Global operator overloading in F#](http://stackoverflow.com/questions/19682432/global-operator-overloading-in-f) and [FsControl - An F# base library with standard ad-hoc polymorphic functions over primitive types.](https://github.com/gmpl/FsControl) – Guy Coder Feb 28 '16 at 14:47
  • Of interest: [experimental-functors](https://github.com/jack-pappas/experimental-functors) – Guy Coder Jul 05 '16 at 23:13
  • Of interest: [Lightweight higher-kinded polymorphism](https://ocamllabs.github.io/higher/lightweight-higher-kinded-polymorphism.pdf) – Guy Coder Dec 06 '16 at 14:12
  • Of interest: [A categorical approach to Proof-as-Programs](http://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Berger.pdf) – Guy Coder Apr 23 '18 at 19:46
  • Of interest: [The Difference between Recursion & Induction](http://blog.ezyang.com/2013/04/the-difference-between-recursion-induction/) - Not perfect for the question, but nice to know. – Guy Coder Feb 07 '19 at 14:06
  • Of interest: Haskell [Applicative functor](https://wiki.haskell.org/Applicative_functor) – Guy Coder Mar 20 '19 at 14:09
  • Of interest: [A lightweight library of abstractions for Higher-kinded programming in F#](https://github.com/palladin/Higher) – Guy Coder Aug 26 '19 at 09:51
  • Of interest: [The Essence of Compiling with Continuations](https://slang.soe.ucsc.edu/cormac/papers/pldi93.pdf) - Not directly related, but if you like researching these areas (functional language design and compilation) then this might be of value. Many more links from where I found the first one. [Is LLVM a good backend for Functional languages?](https://www.reddit.com/r/ProgrammingLanguages/comments/8ggx2n/is_llvm_a_good_backend_for_functional_languages/) – Guy Coder Sep 23 '19 at 19:13
  • Of interest: [How Monads are considered Pure?](https://stackoverflow.com/q/39438091/1243762) – Guy Coder Nov 30 '19 at 14:55
  • Of interest: [Are there algebraic data types outside of sum and product?](https://stackoverflow.com/q/59509294/1243762) – Guy Coder Jan 18 '20 at 10:22
  • Of interest: [Categorical Unification](http://umu.diva-portal.org/smash/get/diva2:142802/FULLTEXT01.pdf) – Guy Coder Jan 18 '20 at 15:03
  • Of interest: [F# Applicative - how I get my head around this kind of black magic spell](https://hardt.software/applicative-how-i-get-my-head-around-it/) – Guy Coder Feb 24 '20 at 10:16
  • Of interest: [apply considered harmful](https://github.com/dsyme/fsharp-presentations/blob/master/design-notes/rethinking-applicatives.md) – Guy Coder Feb 24 '20 at 10:32
  • Of interest: Applied Category Theory by Ken Scambler - [YouTube](https://www.youtube.com/watch?v=iwvl0tBJhoM) – Guy Coder Oct 27 '20 at 10:29
  • Of interest: [From design patterns to category theory by Mark Seemann](https://blog.ploeh.dk/2017/10/04/from-design-patterns-to-category-theory/) - Just found this and have not read it so may remove in future. Part of this [collection](https://gist.github.com/haskie-lambda/55f74dba1f3c1a2408ce545d4984159b#category-theory) – Guy Coder Jul 28 '21 at 12:07
  • Of interest: [Functors, Applicatives, And Monads In Pictures](https://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html) – Guy Coder Oct 21 '21 at 16:24

1 Answers1

41

There's no fundamental limitation of .NET that stops functors from being implemented in F#. True, they can't be represented directly in .NET metadata, but neither can other F# language features like union types. Compilers for languages with functors (e.g., Standard ML, OCaml) have a pass called defunctorize; it works just like C++ template expansion, in that it "flattens" the functors by specializing them into normal modules.

The F# compiler could do the same thing, but you then have to ask: how will this be exposed to other .NET languages? Since functors can't be directly encoded in the .NET type system, you'd need to come up with some way to represent them; and if that representation is difficult/impossible to use from C# or VB.NET, would it still make sense to include F# functors? A non-trivial part of F#'s success comes from it's ability to easily interop (in both directions) with C# and VB.NET.

EDIT: Don't get me wrong -- I'd love to have functors in F#, they'd be really useful to handle a few cases which are currently painful and/or impossible to implement without them. I'm just pointing out that the main reason the language doesn't yet (and maybe won't ever) have functors is that the interop issue hasn't been solved; the metadata-encoding issue is actually the easy part.

EDIT 2: Code for the defunctorize pass of MLton: defunctorize.fun

Update: I had a thought about how functors actually could be expressed within the .NET type system, so I put together a little experiment. It isn't pretty, but it works -- so now we know it's at least plausible that F# could one day support functors. In practice, the complexity you see in my experimental code would all be hidden by the compiler/language. If you want to check it out: experimental-functors

Jack P.
  • 11,487
  • 1
  • 29
  • 34
  • 1
    +1 - You likely hit the nail on the head with interop. Any idea how functors in SML.NET appeared to other .NET languages? – Daniel Feb 08 '13 at 17:18
  • @Daniel Does this help? [Adventures in Interoperability: The SML.NET Experience](http://research.microsoft.com/pubs/67332/p53-benton.pdf) – Guy Coder Feb 08 '13 at 17:27
  • @GuyCoder: Thanks, but I don't see anything about how functors are represented in CIL in there. Based on what Jack said, should I assume a functor is "defunctorized" into several standard modules and appear thus to other .NET languages? – Daniel Feb 08 '13 at 17:41
  • @Daniel Yes -- if you read the paper GuyCoder linked to, in section 3.10 it states that some types can be marked as "exportable" and everything else, like functors, is internal to the assembly. – Jack P. Feb 08 '13 at 17:42
  • Here's a twist. Can C# be extended with functors then they might/could work with F# fuctors. – Guy Coder Feb 08 '13 at 18:12
  • @GuyCoder -- Maybe. But again -- should they? And then what about VB.NET, IronPython, IronRuby, Eiffel, etc.? – Jack P. Feb 08 '13 at 18:44
  • Where did you learn about defunctorize? This is turning up lots of good interanl info on ML compilers, especially MLton. – Guy Coder Feb 08 '13 at 19:03
  • 4
    As far as I know: OCaml does not use a defunctorizer. Functors are internally implemented as mappings from records to records. In a module A parameterized by another module B, referring to a value from B is actually like getting a record field. This is also true of functional values, which means that any call to a function from B is made through a closure, without inlining or other optimizations. Thus, defunctorized code may be faster. – David Monniaux Apr 05 '13 at 19:04
  • 4
    @JackP. "how will this be exposed to other .NET languages?". The same way units of measure are exposed, i.e. don't expose it? – J D Oct 18 '13 at 12:06
  • @JonHarrop As it turns out, it might be possible to support functors in F# *and* express them in a way which would be reasonably straightforward to use from other .NET languages. I updated my response with a link to an experimental implementation that illustrates how this could work. – Jack P. Jan 19 '14 at 21:08
  • @JackP. I saw your code a week ago. Thanks. When I get time I will look into deeper but I am sure I will have many questions. If only F# had a preprocessor. – Guy Coder Jan 20 '14 at 00:16
  • @GuyCoder I'm happy to answer any questions you have about the code. I'm glad F# doesn't have a preprocessor though; while a preprocessor (e.g., `camlp4`) does make implementing certain code constructs easier and also provides a way for users to add ad-hoc language extensions, all the code I've ever seen, in any language, that heavily uses the preprocessor is nearly impossible for outside developers to understand and also adds significant complexity to maintaining the code. I think it'd be good enough if F# added functor support to the language someday. – Jack P. Jan 20 '14 at 02:38