Hacker News new | past | comments | ask | show | jobs | submit login
Closures and Objects Are Equivalent (2013) (c2.com)
70 points by Jtsummers on Nov 20, 2022 | hide | past | favorite | 63 comments



Reminds me of a university project I did 6 years ago: we had to compute a bunch of shortest paths in a large graph, during the computation of reach [^1]. There were a small number of sources but a large number of queries, that were not easily predictible in advance.

The assignment was quite computation intensive and advised to use C++ or Java.

I had a tradeoff to make on each source between computing a full Dijkstra's (distance to all other nodes) or multiple "lazy" Dijkstra's (stopping upon reaching the target node).

Instead, I had a nice idea: what if I could continue computations at the last known Dijkstra's state?

To implement it, I could either: - create an object, list all variables of my Dijkstra's and put them in a dict state - use an iterator that looks very much like the textbook Dijkstras's and use the `next()` Python method to pass queries, while the state variables AND the instruction pointer are stored in the closure

This is a really good illustration that `next` makes closures "mutable" and "callable" as the link states.

The resulting code of an "AWESOME ONLINE MEMOISED DIJKSTRA" as I wrote in the docstring back then is stupidly small and simple to read [^2]. It is also easy to call: `dijkstra_with_target(graph, source).send(target)`.

In the end, my Python code (executed with Pypy) outperformed all C++ and Java implementations by an order of magnitude.

I should write a blog post about this (and almost did here)!

[^1]: https://www.irif.fr/~kosowski/INF421-2016/problem.html

[^2]: https://github.com/louisabraham/INF421-project/blob/master/s...



This smart working Python vs hard working low level languages anecdote becomes even better when you consider that it's using the pure-python heap queue implementation.


Only for LISP people. To C++ programmers, an object is a struct with associated functions.

Then there's the confusion between lambdas and closures. They are not the same thing. Lambdas are simply anonymous functions, usually with funny syntax to make them easier to write in line. Closures are functions with data imported from an outer scope. Some languages separate the two.

Python and Javascript have nested functions which support closures, using standard function syntax.

Pascal and GCC C have nested functions which are not closures and cannot see outer dynamic scopes.


From a C++ perspective, any block with local variables in it is also basically a struct. And if some of those variables are function objects, then they're basically methods of that struct. So once you make such scopes into first-class entities, they automatically become objects.

This actually happened kinda sorta like that in Simula-67 (from which C++ lifted its object model, for the most part). They started with Algol-60, which has nested blocks, each of which can have variable and function declarations. Since they were interested in simulation of processes, execution of a single such block logically modelled a single process. The problem that they had is that, in a simulation, what you really need is multiple concurrent processes that can reference each other (to pass execution flow around). And so, they made those blocks into first-class entities in their own right, giving the programmer the means to control their lifetime explicitly and to reference them from other blocks - and thus objects were born.


> To C++ programmers, an object is a struct with associated functions.

And a closure is a function with associated state. They really are equivalent, in C++ as well as LISPs.


In GCC, local functions are both closures and first-class values. I'm not entirely sure how it's implemented on all architectures, but on x86, when you convert such a function to a function pointer, a stub is dynamically generated on the stack (which thus has to be executable) that pushes the frame pointer on top of all the arguments before jumping to the actual implementation, and the pointer then points at that stub.

In standard Pascal, functions are closures but not first-class values (can be passed as arguments to other functions, but cannot be returned or assigned to variables); a typical implementation would implement a function pointer as a tuple of function address and pointer to stack frame. Some dialects - notably, Turbo Pascal - don't allow pointers to local functions at all.


> In standard Pascal, functions are closures but not first-class values (can be passed as arguments to other functions, but cannot be returned or assigned to variables)

Interesting - being an absolute non-expert in closures - but isn't it the other way around? That is, in Pascal, functions are first-class values but not closures?

Unless I am miss something here, but functions can be assigned to variables:

  function add(a,b:integer):integer; { far; in Turbo Pascal }
  begin
    add := a + b;
  end;

  type MyFunc = function (a,b:integer):integer;

  var f:MyFunc;
      x:integer;

  begin
    f := add; { here we assigning a function to a variable }
    x := f(3,4);
  end;
> Some dialects - notably, Turbo Pascal - don't allow pointers to local functions at all.

I know what you mean here, but that's not entirely true. In Turbo Pascal you had two ways to receive a pointer to a function:

1.) the way just shown, and here you are right, Turbo Pascal doesn't allow local functions, but that’s because how local functions in Turbo Pascal were implemented. Local functions have a hidden parameter (a 16-bit pointer to the caller's stackframe) pushed onto the stack, how do you handle this hidden parameter when you deal with a function pointer with a defined function signature? To avoid headaches I guess Hejlsberg simply choose to not allow local functions here.

2.) via a regular pointer - you simply store the function address in a pointer variable (or pass the function address to a pointer parameter), so:

  procedure MyProc;

  { a local function }
  function sub(a,b:integer):integer; { far; in TP }
  begin
    sub := a - b;
  end;

  type MyFuncHidden = function (a,b:integer; hidden:word):integer;

  var p:pointer;
      x:integer;

  begin
    p := @sub; { assigning a local function to a variable }
    x := MyFuncHidden(p)(7,8,0);
  end;
The problem here, now you as a programmer are in charge of handling the parameter passing.

Look at the implementation of ForEach/FirstThat in the Turbo Vision library. Both ForEach and FirstThat accept local functions as parameter (and only local functions).


Function pointer types are a Turbo Pascal extension; in standard (Wirth/ISO) Pascal, you cannot have "type = function" etc, you can only use that syntax to declare arguments of function type. So they're not first-class values. They're closures because they capture the enclosing environment (variables).

In your second example, what you're doing is the equivalent of reinterpret_cast between two incompatible pointer types (if they were compatible, you could have just assigned @sub to a variable of type MyFuncHidden). You cannot safely assume that your new signature faithfully corresponds to what the compiler does under the hood - that's an implementation detail. Furthermore, in this case, your function doesn't even try to access variables from the outer scope, and this would break if it did.


> Then there's the confusion between lambdas and closures. They are not the same thing. Lambdas are simply anonymous functions, usually with funny syntax to make them easier to write in line. Closures are functions with data imported from an outer scope. Some languages separate the two.

I remember a few years ago saying that I found the naming of anonymous functions in Rust "closures" rather than "lambdas" weird since most of the time they're used they don't close over anything. Someone responded by saying that all of them closed over something, it just sometimes was unit (the empty tuple type in Rust, essentially the equivalent of "void" when used as a return type). I didn't find it super compelling at the time, although over the years learning more about how much the ownership and borrowing system influenced the way that closures needed to be used in Rust (e.g. having separate traits for functions that close over shared borrows, mutable borrows, and owned values) has made me at least understand why the fact that they close over things is worth emphasizing.


Also anonymous functions in programming languages didn't historically always or even usually have lexical scope (= be closures).

Eg Lisp had lambda expressions for a long time (20 years? 30 years?) before lexical scoping made it in. Python also had its lambda and nested functions for a long time before lexical scopes came to the language. The namesake, lambda calculus, doesn't have it (I think?).


> The namesake, lambda calculus, doesn't have it (I think?).

Lambdas in the Lambda Calculus have to be closures, how else would you build functions of multiple arguments? Think:

  λx.λy.(x + y)
If they weren't closures, `x` would be unbound in the inner lambda.


Ah, right. And apparently this was a prime motivation to for the first Lispy closures implementation, which was called... Scheme. https://en.wikisource.org/wiki/Scheme:_An_Interpreter_for_Ex...

"we have implemented an interpreter for a LISP-like language, SCHEME, based on the lambda calculus [Church]"


> an object is a struct with associated functions.

That's true, and if you add an “apply” operator (`operator ()`), then your thing becomes a “function object” and your instance variables are the closure environment. quod erat demonstrandum.


Honestly both names are really terrible. It took me an embarrassing amount of time to understand what a closure is just because "closure" and "closing over" are hilariously obtuse names for what is a very simple concept.

It would be clearer if people just called them function objects. They are effectively the same thing, just with nicer syntax for declaring them. Or even just "anonymous functions". I'm not sure the fact that they have data automatically attached to them is really enough to warrant a completely different and confusing name.


The name is unfortunate because it's distinct from the other meaning of "closure" in mathematics (e.g. as in "transitive closure") but it's definitely not captured by "function objects" nor by "anonymous functions". Function objects may close over nothing, either by virtue of being pure functions or by having unbound variables resolved in dynamic scope. Similarly, they're not always anonymous, and anonymous functions are just as often closing over nothing (if not more often - lots of trivial map/filter/reduce are pure).


> Function objects may close over nothing

So you're saying a closure that happens to not close over any variables is no longer a closure? I don't think many programming languages agree with that. For instance C++: https://en.cppreference.com/w/cpp/language/lambda or Rust: https://doc.rust-lang.org/book/ch13-01-closures.html

They both use "closure" in all cases even if the function doesn't actually bind any scope variables.

We don't have a special name for functions that take 0 parameters. I don't think a special name is warranted here either.


Not sure what you're saying, Rust specifically calls out the degenerate case of "closures" as having very different behavior:

Non-capturing closures are closures that don't capture anything from their environment. They can be coerced to function pointers (e.g., fn()) with the matching signature.

There's value in deference to practicality - we want to treat n-ary closures and all n-ary functions the same way much of the time so we should make it easy to write functions which accept both which means they should be nameable via the same succint type - but we also shouldn't confuse that practicality for formalism.

> We don't have a special name for functions that take 0 parameters.

Only because we have generalized "nullary", "unary", etc. We know that e.g. a nullary pure function must also be a constant function. There are similar useful implications we can draw for "non-capturing closures" that makes them a distinct type in the formal sense, even if not in the "this is the type a particular language attaches to the resulting variable/value" sense.

But what does any of this have to do with your original point? I don't think anyone claimed closures aren't a kind of function, only that "function objects" is not synonymous with them. Most languages, including obviously Rust and C++, have functions objects which aren't closures


> I'm not sure the fact that they have data automatically attached to them is really enough to warrant a completely different and confusing name.

It is, since the lifetime implications are profound - either in form of dangling pointers, or in form of local variables outliving their execution frame.


Nope, the lifetime implications are a completely separate dimension. You can still have closures that don't retain any reference to variables with different lifetimes, e.g. using `[=]` in C++ or `move` in Rust.

Also, we don't have a separate name for structs that contain references/pointers and structs that don't do we?


> Also, we don't have a separate name for structs that contain references/pointers and structs that don't do we?

Languages name things they need to help their implementation. In Go, such types are named ("pointer-ful" and "pointer-free"), because they are allocated differently to assist GC. In C++, they're not but instead we have e.g. PODs which other languages don't need to name, because of other optimizations C++ wants to do.


We don't because those pointers are explicit. But they're not with closures, even with something as low-level as [&] in C++.

And, yes, what [=] produces is not a closure, by definition (but it's still a lambda).


Sorry, why wouldn't closing over a variable by value count as a closure? In fact in many functional languages you can't tell the difference.


In functional languages where you can't tell the difference, like ML or Haskell, values are bound directly to variables, so capturing the value is closing over the variable. But in C++, variables represent storage locations which contain values, so if you copy the value, you're not really closing over the variable (unless it's const).

To look at it from another perspective, if a closure closes over the variable, then references to that variable inside the closure should behave the same as references to that variable outside of it. If you can change the variable value outside, and it's not reflected inside the closure, then it's not really the same variable inside and outside.


“Anonymous function” simply means no name, that would be equally confusing. For “function objects”, closures may be more than just a nice syntax for it. E.g. two closures may share a symbol:

  let x
  fn setx(v) {x = v}
  fn getx() {return x}
And that symbol still lives in scope:

  x = 5; getx() // 5
It may be not the best name, but these nuances beg for a distinct one.


> For “function objects”, closures may be more than just a nice syntax for it.

Not in any language I've used. I'm not sure what language you've used but in C++ you would have written:

  int x;
  const auto getx = [&]() { return x; };
  x = 5;
  getx(); // 5
But that's exactly the same as this:

  int x;
  struct GetxFunctionObject {
    int& x;
    int operator()() { return x; }
  };
  const auto getx = GetxFunctionObject { x };
  getx(); // 5
(Something like that anyway; it's been a while since I wrote C++)


In Delphi, closures are implemented pretty much exactly as your second variant. They're implemented using a compiler-generated class.

A difference is that you can't specify capture type, all captured variables are stored as fields in the class, and any outer references (such as x here) are replaced to use the field in the instance:

    struct GetxFunctionObject {
      int x;
      int operator()() { return x; }
    };
    const auto getx = GetxFunctionObject();
    getx.x = 5; // compiler automatically changes "x = 5" to this
    getx(); // 5
Modulo any it's-too-early-in-the-morning-to-write-C++ mistakes I made.

I can't recall the details if multiple closures captures the same variable, might be the "obvious" solution of a shared data-class instance.


GCC C nested functions do have access to outer lexical scopes: http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Nested-Functions...

But dynamic scope is a wholly another thing, most languages with closures don't have it. One exception I know is Clojure where you can declare variables explicitly as dynamically scoped, and it can be used eg as an alternative to passing around a context map when handling requests in a server style program. (And Elisp had dynamic scoping first, then closures added as a add-on feature)


In Common Lisp, all globals are dynamically scoped. Lexical scoping only exists in limited scopes (e.g. a function body). There are non-standard extensions provided by many compilers to expose lexical globals. You can also kind of hackily create your own “lexical global” using a simple symbol macro, but it has some serious caveats.


> an object is a struct with associated functions

And inheritance and polymorphism, which I don’t think you can reproduce with closures.


Inheritance and polymorphism: https://okmij.org/ftp/Scheme/oop-in-fp.txt

The link at the bottom is dead, but here's the same file at his current site: https://okmij.org/ftp/Scheme/pure-oo-system.scm

You can reproduce these with closures, though you'll need more plumbing since it's not built into the language.


> more plumbing since it's not built into the language

Well, sure - you can "reproduce" encapsulation, inheritance and polymorphism in plain-old C (heck, I've done it in Cobol), too. I'm not sure that's really the same, though.


I would state it slightly differently: Closures are for FP what objects are for OOP.

When you create a closure you are in fact creating an instance of a Function. In FP functions are "first class citizens", therefore it must be easy to create new (instances of) Functions. In FP you can do that by calling some code that creates a closure, not only by providing new source-code for a new Function-definition.

Note Function Definition is not a function.

What can you do with a closure? You can call it. What can you do with an object? You can not call it. You can only call one of its methods.


I believe the equivalent here means formally equivalent.

But, really, you can use each of them to emulate the other.

If you want to emulate objects with functions, you just have your function return a bag of closures over the state. Your first function is effectively a constructor.

To emulate functions with objects, you just create a single method class. Or do something real fancy with Scala's apply and/or C++'s ClassName::operator()() so it looks like a normal call, if you are so inclined.


> To emulate functions with objects, you just create a single method class.

You still can not "call the object" you can only call its single method.

But I see what you are saying I think. You can accomplish similar things with closures and objects.

For them to be "equivalent" I think should mean there is nothing you can do with closures that you can not do with objects, and vise versa. I don't know if that is the case, is it?


That's what the term "formally equivalent" means here.

You can do whatever you can do with one of them, with the other one.

Actors as well.


Right but then we get back to the Turing completeness. You can do with any Turing machine whatever you can do with any other Turing machine. You just have to do it a little differently.

I'm not sure if https://wiki.c2.com/?ClosuresAndObjectsAreEquivalent

gives us a constructive proof however. There is a poll in there. Let's vote if this is so, or not. :-)

Interesting discussion however in there.


> You just have to do it a little differently.

No, my point is that you don't have to do it any differently (unless you mean the machine does different things, in which case that really depends on your compiler).

The note here is that depending on your language, syntax may make the emulation difficult/cumbersome.

If you have classes, you can emulate closures by creating a class that takes the state to close over as constructor arguments, and executes the body of the function as a single method.

If you have closures, you can emulate objects by taking state and returning a bag of functions, which emulate methods. If you need polymorphism, you can call the "parent" closure and just replace the closures in the resulting bag that you need to override.

You can use these to solve problems without altering your approach (though, once again, syntax may be burdensome depending on the language).


> you don't have to do it any differently

The code you write must be different, depending on if you write closures or objects. The way you call upon closures vs. objects also requires different syntax. You must write different code, you must "do it differently".

But I agree they do pretty much a similar thing. You however must write different code depending on which approach you choose, and depending on your language there are pros and cons to each.


> The way you call upon closures vs. objects also requires different syntax.

The syntax isn't what I'm talking about. I'm talking about the patterns.

> You however must write different code depending on which approach you choose

Only code that is different in syntax, not code that is conceptually different.


> What can you do with a closure? You can call it. What can you do with an object? You can not call it. You can only call one of its methods.

These are congruent, assuming an Alan Kay-ish definition of OOP (as per Smalltalk and Ruby et al). A collaborator object does not call another object's methods, but rather sends it a message. Consequently, there is only one logical interface.

This is one reason that Erlang is sometimes described as one of the most OOP languages, despite possessing distinctly functional fundamentals.


> What can you do with a closure? You can call it. What can you do with an object? You can not call it.

It's a good thing Lua doesn't have objects!

Because in Lua, you can call a table if it has a `__call` metamethod, this is valid Lua:

   (setmetatable({a = 5}, {__call = function(t) return t.a end}))()
which returns 5.


Closure Oriented programming is described in Let Over Lambda[0], objects in Lisp.

[0][https://letoverlambda.com/index.cl/guest/chap2.html]


If you squint enough, all Turing complete concepts are equivalent to one another.


Yeah but you have to squint considerably harder to see (arbitrary size) ints as equivalent to objects compared to seeing lexical closures as equivalent to objects.


That level of squinting is equivalent to replacing a human eye with a light sensor.


It seems similar to the old-time joke of a monk-senior all-knower engineer and a junior, where the latter tries to find “The Truth” and comes back with The answer three times, OOP, FP and actors, and it turns out that they are all the same.


Apparently only one past submission with comments:

https://news.ycombinator.com/item?id=9363635 - April 12, 2015 (45 comments)


Thanks! we can throw in a couple other related ones I suppose:

Closures and Objects Are Equivalent - https://news.ycombinator.com/item?id=9363635 - April 2015 (45 comments)

Objects vs closures - https://news.ycombinator.com/item?id=1982080 - Dec 2010 (17 comments)

Objects are a poor man's closures (2003) - https://news.ycombinator.com/item?id=1241717 - April 2010 (38 comments)

--

Edit: I put 2013 above since the page says "last edited 2013" - but most of this content must be much older...


Closures don’t have inheritance or any of the other machinery that object oriented programming typically comes with.

Perhaps saying they are light weight objects (where objects has its meaning as instances of classes) is a good way of saying it.

The realisation that closures and objects are very similar is one of the main turning points in becoming proficient in both OOP and Functional Programming, it was for me at least.


Delegation can model inheritance or other OOP semantics. If you squint your eyes delegation and lexical scope nesting kinda resemble each other.


Not quite. Inheritance needs a "tying the knot" construction, because a base-class method can call a method that may have been overridden in a derived class. So you need an indirection step for any call to an overridable method, which cannot be modeled by simple delegation. Of course this is really a misfeature (outside of pure abstract base classes that, like interfaces or traits, don't implement their defined methods), which is at the root of the well-known "fragile base class" problem. It means implementation-inheritance is inherently non-modular, even though literally everything else in OOP was specifically intended to enable and promote modularity.


This is especially true in JavaScript. Inheritance between classes is implemented using delegation and the global scope is dynamic.


Not all OO languages even have inheritance.

I would argue that the only two features that are mandatory to call something "object-oriented" is 1) the notion of object identity, and 2) some kind of dynamic method dispatch.


I would agree


Depends on which language, in c++ you can inherit from the type of a closure as it's just another object type


C2.com is the ur-wiki.


The WikiWikiWeb indeed.


Nice content but what in the heck is up with all the camel case links?


That’s how the first wikis worked. You didn’t explicitly mark links to other pages. Instead, camel-case words were links by definition, and page titles accordingly were camel-case words. See https://wiki.c2.com/?JoinCapitalizedWords.


Huh neat, thank you for the explanation


Just like hammers and mallets are equivalent, yeah?

- - - -

Recursion and loops are equivalent. They both just compile to branches with negative offsets, eh?

- - - -

If you take enough LSD everything is equivalent to everything else.


Turing equivalence is a hell of a drug.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: