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)!
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.
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?).
> 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).
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.
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.
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.
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.
> 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?
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.
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.
> 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.
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.
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.
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.
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.
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.
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.
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...