1. 15
  1. 10

    Here’s the formalisation you’re looking for:

    Both objects and closures are modelled by a particular pattern involving existential types.

    Here’s the definition of closures:

    type Fn a b = exists e. {
      env : e,
      code : (e, a) -> b
    apply : (Fn a b, a) -> b
    apply(f, x) = f.code(f.env, x)

    And here’s a “mutable counter” object that’s often used in OO examples:

    type Counter = exists s. {
      state : s,
      next : s -> (),
      read : s -> int
    new : Counter
    new = {
      state = Ref.new(0),
      next = Ref.modify (+ 1), 
      read = Ref.get
    next : Counter -> ()
    next c = c.next c.state
    read : Counter -> int
    read c = c.read c.state

    The pattern has a generic name: the greatest fixed point of a functor (I will expand on this by request). Types that can be represented by the greatest fixed point of a functor are called conductive types, or codatatypes.

    Objects and closures are both codatatypes.

    1. 3

      the greatest fixed point of a functor

      So I know what a (greatest) fixed point of a function is. I know an analytical way to calculate it and, as is often necessary, a numerical way to approximate it. What I’ve never managed to figure out is what the relationship between that kind of fixed point and the fixed point mentioned here is. What is the function here, how do you verify this is the greatest fixed point and why does it even matter that it is a fixed point in the first place?

      1. 2

        The fixed point of a function f : A -> A is some x \in A such that f(x) = x.

        Category theory generalised this definition by replacing “set” with “category”, “element” with “object”, “function” with “functor”, and “equality” with “isomorphism”.

        So a fixed point of a functor f : C -> C is some object x of C such that f(x) is isomorphic to x.

        These fixed points form a category, and the greatest fixed point of a functor is the terminal object in that category. I won’t go further in relating this to set/order theory beyond saying that “top” elements are often analogous to terminal objects.

        To show that a type is the greatest fixed point of a functor, show that for every fixed point of this functor, there’s a unique morphism from that fixed point to the greatest fixed point.

        The greatest fixed point of functors on Type looks like this: type GFP (f : Type -> Type) = exists x. { seed : x, unfold : x -> f x }. Proofs are left to the reader :)

        We can show that GFP fis isomorphic to Closure a b for a particular choice of f. The same goes for Counter. In general, each codatatype is characterised by a functor.

        For closures, that functor is type ClosureF a b x = a -> b, and for the counter it’s type CounterF x = { next : (), read : int }.

        The fixed point machinery is trivialised in the examples I gave, because they’re not self-referential. An infinite stream is an example of a “corecursive” (self-referential) codatatype. It is characterised by this functor: type StreamF a x = { head : a, tail : x }.

        At this point I’m running out of steam. I’ll finish by saying: all this theory (algebraic + coalgebraic semantics) doesn’t really matter to programmers. But codata is a concept that programmers use every day without realising. The next step is to provide explicit access to that concept in programming languages.

        Other resources:

        • Adámek, J., & Koubek, V. (1979). Least fixed point of a functor. Journal of Computer and System Sciences, 19(2), 163-178. - explains the least fixed point of a functor, which is the dual to the greatest fixed point.
        • Haskell’s recursion-schemes package - fixed points, folds, unfolds, and fusion
        1. 1

          OK, thank you, that does clarify some things. What are the properties of the GFC of a functor that makes the Type it represents interesting/useful? Are there examples of someone coming upon some functor and, perhaps unexpectedly, discovering its GFC is a useful Type? So what I’m trying to understand with these questions is: why is it interesting that certain Types are GFC’s of certain functors? What can one do with that knowledge? If it enables us to sometimes discover/construct new useful Types, then that would finally explain to me why we would want to know this.

      2. 1

        The pattern has a generic name: the greatest fixed point of a functor (I will expand on this by request).

        Would be great to read more on this; while the concept itself is intuitively clear to me, I’d very much like to hear what people can get out of a formalized version (pointers to reading material welcome).

        1. 1

          Here’s a response I wrote for another poster: https://lobste.rs/s/ajgdnb/illustrating_duality_closures_objects#c_jgwwru

          Hopefully you also find it helpful.

          1. 1

            I’m not sure about the generic form of the pattern, but Codata in Action is all about the connection between objects and codata and so might be interesting to look at. I’ve not had the chance to sit down and digest it personally though. Looking through the earlier sections seem reasonably accessible. There’s some more detailed technical parts later on, but if your not comfortable with that you can always jump off there and perhaps skip to the conclusion.

          2. 1

            Thanks so much for explaining this! I really appreciate it.

          3. 9

            I can’t emphasize how much this changed how the way i program

            I was writing the first version of my language (peacock) in functional style JavaScript & then at some point i realized all these closures were just messy ad hoc immutable classes.

            Over a few iterations i landed in OO ruby & i never thought id say this years ago but OO is really really beautiful, over time i started to introduce more mutation when it called for it & i found the end result was significantly simpler & more maintainable code.

            Moral of the story is dogma like “OO is bad”, “mutation is bad” is not only wrong, but such a limiting & IMO boring way to view the world.

            1. 3

              i realized all these closures were just messy ad hoc immutable classes.

              What is messy or ad hoc about them?

              I’ve coded a lot in both ruby and JS and my sense is that, like the article says, the differences are cosmetic.

              1. 2

                With a closure you don’t list your data members, they’re just implicitly closed over. Sometimes that’s nice. Sometimes you want it to be explicit instead.

                1. 2

                  There’s a lot I could say that could easily result in a blog post of length. But to sum up where I stand -

                  • This isn’t a comparison of JS object/prototype/class system vs ruby classes (though I think they are very different) since I wasn’t using the object system in my JS implementation.

                  • I strongly believe so-called cosmetic differences are one of the most important factors on day to day programming quality & happiness.

              2. 5

                Let’s make this a lot simpler (not for anyone who’s already posted in the thread because I can tell that y’all get it, but for anyone else who’s lurking):

                Closures are functions that carry some of their own data with them. Object instances are data that carry some of their own functions with them.

                For example, imagine you had a speak-some-text() function that you wanted to carry a text and keep track of where in the text you are so you can speak the next part and then place a new bookmark. A closure can do that.

                Or, if you had a book object that had members such as text and position and a method speak-at-current-position(). An object instance can do that.

                So as you see you can do kind of the same thing.

                What’s frustrated me in the past with object systems is when all I needed was a normal first-class function, I didn’t need to carry any state or data, but I had to make an object (with no members and a single method) anyway (because this was when Java didn’t have first class functions, maybe they still don’t, it was 15 years ago, IDC), and in order to make the object I had to make a class, it was a hole schlep for what’s trivial and like two characters in a language with first class functions like shell scripting, JS, or lisp.

                What’s frustrated me in the past with SICP-style “closures are objects”, the kind of overwrought closing over a symbol-message dispatch (making kind of a Smalltalk or Obj-C style implementation), is that there’s no inheritance; you can work around that easily enough with composition or adapters but sometimes you just want a beautiful concise object system. ♥

                Overall I prefer closures and use them all the time and I very rarely want an object system. When I do it’s because I’m trying to solve a Simula type problem like a GUI or a set of actors such as monsters in a video game.

                1. 1

                  What’s frustrated me in the past with SICP-style “closures are objects”, the kind of overwrought closing over a symbol-message dispatch (making kind of a Smalltalk or Obj-C style implementation), is that there’s no inheritance; you can work around that easily enough with composition or adapters but sometimes you just want a beautiful concise object system

                  There are so many object systems in Scheme to choose from that do provide inheritance one way or another. I always found the prototypical inheritance based prometheus very elegant (to the point that I misguidedly used it in the SSQL egg), but there’s of course also coops etc if you want something more fancy.

                  1. 1

                    I’ve used coops a lot ♥ and of course tinyclos back in the day of C3.

                    A lot of my love for objects were out of the support for generic methods. These days since I have my match-generics I can get by with just records or call-tables most of the time.

                    1. 1

                      That’s the beauty of Scheme, you can just create (or pick) the exact best thing for your use case. Whereas with your Java example you were basically stuck with what the language offered (unless you went the route of generating code)

                      1. 2

                        Which I did, and I used Chicken to generate the code (both Java code and matching XSLT code) ♥

                        1. 1

                          hehe, epic!

                  2. 1

                    Do you know any open source project where I can see usage of this kind of closure (ie. grouping data and function to have “object like” structure)? I saw the SICP example linked in another post of this thread and I’m really interested to see concrete (“real world”) usage in a project.

                    1. 1

                      Here’s a simple example from my own 7off:

                      (define warn-once
                        (let ((warnings '()))
                          (lambda (trigger str)
                            (when (and trigger (not (member str warnings)))
                      	(warning str)
                      	(set! warnings (cons str warnings))))))

                      Here is one example of usage (deep in another loop):

                      (warn-once (< 3 level) "Documents with header levels 4 and above might be better to split up into sub pages.")

                      (< 3 level) is checked in the current scope, and if it’s true, we print a warning message, but we only do it once. The data in the function is the mutable list “warnings” that gets appended to with every new warning we see.

                      That’s how most often use ‘em, where I want the external interface of a function (in this case just a warn-once function with two arguments: a trigger and a string to print if the trigger’s true) but with different behavior based on internal state (in this case whether or not we’ve printed this string before. This is side-effects btw, not pure FP.

                      Here’s how I’d write the same thing today with brev:

                      (define-closure (seen (call-table)) (warn-once trigger str)
                        (when (and trigger (not (seen str)))
                          (warning str)
                          (seen str #t)))

                      It’s the same interface, and also seen inside of it (instead of the list of “warnings” being appended to) is a closure that keeps track of the strings it has seen.

                  3. 3

                    Using closures to implement objects that respond to messages is also famously done in SICP. If you take this to its limit, you can implement a full class-based object system (even with a meta object protocol, if you like) using only closures.

                    1. 3

                      I gave a talk about this symmetry at BOB 2020 in Berlin. I’m linking the org-mode slides here in case people are interested. They discuss the symmetry in practice, and also some theoretical / more advanced elements.

                      Something that people often don’t recognize is that, while the Expression Problem suggests that OO programs are make it easier to add new data cases, while FP make it easier to add new operations (without modifying existing code), in practice in my experience readability is also affected: it’s easier to read code where all the logic is in the same place, so FP code makes operations easier to read and OO code makes “data cases” easier to read. I think this has potential consequence for code visualization tools.

                      1. 2

                        Yes, if you have lots of types and few methods, OO wins; if you have many methods and very few types, imperative (or FP) wins. Where both break down are those cases where you have lots of types (or objects) and lots of methods.

                        1. 1

                          Omigosh thanks for putting this amazing material out there. Also your second paragraph is blowing my mind. Amazing!

                        2. 3

                          Python is not a great language for demonstrating this though because you have to use nonlocal to assign to any closure variables. Going further, objects, closures, and just plain old passing a lot of arguments are all roads to the same end.

                          1. 2

                            You’re 100% right.

                          2. 2

                            This is very easy to show in Common Lisp:

                            (defun make-person-object (&key (name) (age))
                              (let ((person-age age)
                                    (person-name name))
                                (lambda (message &rest args)
                                    ((eq message :print)
                                     (format t "Person ~s aged ~a~%" person-name person-age))
                                    ((eq message :set-age)
                                     (setf person-age (car args)))
                                    ((eq message :get-age)
                                    (t (error "Person does not handle ~a message" message))))))
                            (defparameter *bob (make-person-object :name "Bob" :age 42))
                            (funcall *bob* :print)
                            (funcall *bob* :set-age 43)
                            (funcall *bob* :print)
                            (format t "Bob is: ~a~%" (funcall *bob* :get-age))
                            ;; And you can do interesting things like:
                            (disassemble *bob*)
                            1. 2

                              Absolutely, as a Lisper myself, I had to swallow plenty of pride to use Python for this particular example. I quite like the code you posted in this comment.