Understanding Rust Lambdas from a Compiler’s Perspective

Annoyingly, the article appears behind somewhat of a paywall, though there seem to be ways around it.

3 Likes

"Lambdas", "closures"... Meh, back in the day we just called them "call backs" :slight_smile:

The article seems to mix up a few concepts of functional programming.

lambdas in modern programming denote pure, anonymous functions. These functions are "pure" because they do not reference variables outside their scope.

The notion of “pure” in programming usually refers to absence of side-effects. In languages (like Rust) without a codified notion of purity, lambdas aren’t pure functions, either. On the other hand, capturing of variables does not compromise purity, and all pure functional langues will support lambdas with capturing.

Consider the following Rust example, where a lambda is used to add two locally declared variables:

foo(|x, y| x + y);

In contrast, closures are anonymous functions that capture variables from their surrounding scope. For example:

let y = 1i32;
foo(|x| x + y);

While both lambdas and closures serve as anonymous functions, lambdas are rooted in theoretical foundations, whereas closures are practical extensions that allow for external variable capture — a detail primarily of interest to compiler implementations.

The theoretical foundations (you mention lambda calculus yourself) typically always include a notion of lambdas that does allow variable capture. In fact, lambda calculus without variable capture would be entirely useless. Hence I’d say it’s plainly wrong to claim that closures (which is the term used in the article to denote “lambdas + variable capture”) are but a practical extension, and not founded in theory.


These three implementations of invoke provide different functionalities. It shouldn't be the compiler's role to decide which implementation to use, as this choice should be left to the user to determine the correct contract. Consequently, Rust offers three lambda traits for selection: FnOnce, Fn , and FnMut. If a user specifies foo(f: impl FnOnce(i32) -> i32) , the compiler generates invoke(self, x: i32) -> i32.

Note that while it’s true that choosing between different Fn* traits is usually a deliberate user choice, and function signatures expecting FnOnce or FnMut or Fn being passed a closure expression does influence the implementations for that closure, note that outside of this case (closure expression directly passed to a place declaring a specific expected Fn* trait bound) the compiler does “decide” (or rather infer) which implementations to choose, based on the body of the closure, and how it accesses captured variables.

Fn requires a non-consuming borrow of the lambda, making FnOnce incompatible in contexts where Fn is expected, due to its ownership-consuming nature. Conversely, Fn can be used where FnOnce is required, leading to the inheritance chain Fn <: FnMut <: FnOnce.

Minor nit: I don’t think this should necessarily be called an “inheritance chain”, as Rust doesn’t do typical “inheritance” like class hierarchies from OOP. I think there’d be value in calling out the relation between these traits as what it is, namely a subtrait/supertrait relationship.

7 Likes

Well, Lisp dates back to 1960 and I’m pretty sure the first version already had the lambda form :slight_smile:

It would be interesting to have a Rust compiler mode with immutable variables. On-the-other-hand proposals I've seen which are going to restrict as usize casting are rather intimidating enough.

There's a famous series of papers about this precise issue, though compiler research has come a long ways since then.

3 Likes

10 posts were split to a new topic: Are there more new programming languages now than there used to be?