Closures and Objects Are Equivalent (2013)
wiki.c2.com
wiki.c2.com
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...
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.
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.
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?).
Lambdas in the Lambda Calculus have to be closures, how else would you build functions of multiple arguments? Think:
λx.λy.(x + y)
"we have implemented an interpreter for a LISP-like language, SCHEME, based on the lambda calculus [Church]"
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)
And a closure is a function with associated state. They really are equivalent, in C++ as well as LISPs.
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.
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.
It is, since the lifetime implications are profound - either in form of dangling pointers, or in form of local variables outliving their execution frame.
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.
And, yes, what [=] produces is not a closure, by definition (but it's still a lambda).
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.
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.
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
let x
fn setx(v) {x = v}
fn getx() {return x}
x = 5; getx() // 5
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
int x;
struct GetxFunctionObject {
int& x;
int operator()() { return x; }
};
const auto getx = GetxFunctionObject { x };
getx(); // 5
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
I can't recall the details if multiple closures captures the same variable, might be the "obvious" solution of a shared data-class instance.
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.
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.
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;
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;
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).
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.
And inheritance and polymorphism, which I don’t think you can reproduce with closures.
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.
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.
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.
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.
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?
You can do whatever you can do with one of them, with the other one.
Actors as well.
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.
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).
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 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.
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.
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}))()
https://news.ycombinator.com/item?id=9363635 - April 12, 2015 (45 comments)
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...
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.
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.
- - - -
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.