A lambda is just a function without a name. (This feature tends to come with special syntax, although it doesn't have to.)

A nested function is a function defined inside another function which can access the variables of the enclosing function. (A nested function can be a lambda, but it doesn't have to be. Some languages have named nested functions. A lambda doesn't have to be a nested function; it doesn't have to pull in any variables from an outer scope.)

A closure is a nested function which can outlive the outer function, keeping its data alive. (A closure can be named, the usual case in Python and Javascript, or anonymous. So a closure need not be a lambda.)

Closures are easy to implement in garbage collected languages, but hard in explicitly allocated ones, because extending the lifetime of the imported data gets complicated.

So the options are:

- Lambda without any external data access -- typical use, comparison function for a sort.

- Lambda with external data access, but not outliving its enclosing function - typical use, iteration expression

- Named function with no external data access. Typical use, a local function in languages that don't do local functions well, such as C.

- Named function with external data access, not outliving its enclosing function. Typical use, internal function within a function to avoid passing extra parameters.

- Named function with external data access, outliving its enclosing function. A true closure, but not a lambda. Typical use, saving state for a callback in Javascript by passing the function to something that will save it and invoke it later. An object, really. This was how LISP did objects.

- Lambda function with external data access, outliving its enclosing function. A true closure. Same uses as above, but in different languages.

Most languages offer some subset of these six options.

A good example in C++ would be:

- A function (non capturing/lambda) is created with

  auto f = [] { ... };

  auto s = "...";
  auto f = [&] { s; ... };

However, the resulting assembly for both couldn't be more different. The Lambda case is as raw as any normal C function type, which the closure case creates a C++ class that closes over the outer method's state. If you're not a seasoned C++ engineer, this nuance will be lost on you.

It's fair to say that everyone should understand Lambda Calculus rules, but that makes the language less accessible to new-comers. In the case for non-systems languages, you can blur the lines with ease, but something Rust and C++ just cannot afford to do. That makes understanding the nuance important to be effective.

I think your broader point still holds but perhaps could do with a clearer example

But as always, depends on where you come from. I mostly deal with lisp languages nowadays, so guessing it's just my view that the line quoted above seems complex enough to not be interested one bit in Rust.

The equivalent in Haskell would be "compose :: (a -> a) -> (a -> a) -> a -> a", which lacks "impl" because it boxes all closures (each closure in Rust has its own type), and lacks "Fn" because it doesn't care about what kind of access the closure needs to its context (Rust distinguishes between Fn, FnMut and FnOnce). Still, the Rust is only a tiny bit more complicated than the Haskell.

    #![feature(trait_alias)]

    trait Map<T> = Fn(T) -> T;
    fn compose <T>(f1: impl Map<T>, f2: impl Map<T>) -> impl Map<T> {
      |n| f1(f2(n))
    }

template<typename T> using Map = std::function<T (T)>;

    fn compose<T>(
        f1: impl Fn(T)->T,
        f2: impl Fn(T)->T
    ) -> impl Fn(T)->T
    {
        // both arguments as well as the returned value 
        // are functions which take and return the generic type T.
        // (to be precise, they implement the Fn trait).
    }
    
    let returned_function = compose(|val| val == 1, |val| val < 0);
    let value: bool = returned_function(true);

  fn compose<T, F: Fn(T)->T>(f1: F, f2: F) -> F {

    fn compose<T, F: Fn(T) -> T, G: Fn(T) -> T>(f: F, g: G) -> impl Fn(T) - > T

    fn compose<T, F, G>(f: F, g: G) -> impl Fn(T) -> T
      where F: Fn(T) -> T, G: Fn(T) -> T

https://doc.rust-lang.org/nightly/std/iter/trait.Iterator.ht...

... and `impl Trait` exists to be able to have return types which are difficult, verbose, or impossible to name.

  fn compose<T, F: Fn(T) -> T>(f1: F, f2: F) -> F

  fn compose<T, F: Fn(T) -> T>(f1: F, f2: F) -> F {
    f1
  }

  let clos = |x| 2 * x;
  compose(clos, clos);

    compose(|x| x, |x| x)

It's a fun little thing, and a good example of why impl Trait in argument position is a really nice addition to Rust, even though based on what we were originally excited about (impl Trait in return position for returning Iterators and other such things), the argument position form didn't seem so important.

Bt then again, maybe it depends on where you come from.

  fn new_invoke(f: impl Fn(f64)->f64, x: f64) -> f64 {
      f(x)
  }

In the case of functions, this difference probably doesn’t matter, because you normally can’t name the type of a function anyway, and are extremely unlikely to wish to; but in other cases being able to type the turbofish can matter for ergonomics.

As an arbitrary example, take std::convert::Into::into: the type parameter is on the trait rather than the method, so you can’t do `x.into::<T>()`, but if you need to constrain the type you must do so otherwise, e.g. `let y: T = x.into();` or `<_ as Into<T>>::into(x)`. (In that case in particular, you’d write `T::from(x)` instead, but there won’t always be such an ergonomic replacement.)

Fearless refactoring is one of the prime benefits of Rust.

With Rust, programmers have to spend most of their mental energy worrying about management of memory, which has largely been automated already.

I always go back to this quote from Andrei Alexandrescu (creator of D):

  A disharmonic personality. Reading any amount of Rust code evokes the
  joke "friends don't let friends skip leg day" and the comic imagery of
  men with hulky torsos resting on skinny legs. Rust puts safe, precise
  memory management front and center of everything. Unfortunately,
  that's seldom the problem domain, which means a large fraction of the
  thinking and coding are dedicated to essentially a clerical job (which
  GC languages actually automate out of sight). Safe, deterministic
  memory reclamation is a hard problem, but is not the only problem or
  even the most important problem in a program. Therefore Rust ends up
  expending a disproportionately large language design real estate on
  this one matter. It will be interesting to see how Rust starts bulking
  up other aspects of the language; the only solution is to grow the
  language, but then the question remains whether abstraction can help
  the pesky necessity to deal with resources at all levels.

There will be more innovation in GC that will make manual memory management even more useless. In a lot of cases the JVM does a better job of freeing memory than a programmer. I don't want to spend my time programming worrying about the same thing (memory) that K&R did in the 70s. I don't want to bet against innovation and technology.

Given that most of my Rust programs have involved graph-heavy data structures, I'd like to see you explain why it's impossible for me to have written what I have written.

It's not like this is not well-known. Rust users admit it. GUIs are hard to write in Rust because of the limitations of RAII+borrow checker based memory. You have to rely on ref counted pointers which can become very complicated to deal with in cyclic dependencies and long-lived references common in GUIs. This problem is not unique to Rust either. C++ makes it hard to write GUIs too, but hacks are used to get around the language like Qt's moc or Microsoft's old CLI extensions to C++.

All non-GC languages are crippled for application programming. Sure, there are domains where GC cannot ever work, like signal processing or kernel dev. In these places I'd much rather see Rust used than C++.

:confused:

That said, it's one thing to admit the costs of Rust's model. It's another to argue about the implications of that cost--i.e. the degree to which it makes Rust non-viable long-term. On that point I have no opinion, except to say that for complex application development I've been very happy using Lua as a glue language, and many others have been happy using GC'd languages for complex logic. But that's more of a neutral factoid as it both diminishes Rust's relative costs and benefits. Whether it augurs in favor of Rust or not depends on your starting point. Plus, language success is less dependent on merit than we'd like to believe.

[1] Note that LPeg is far more than a PEG engine (like Rust pest), as strict PEG engines are incapable of parsing DER, which is context-sensitive. In addition to its extensions (e.g. runtime matches), what makes LPeg so simple is that you don't even need intermediate graph representations. You can transform subtrees in the grammar inline, mixing function transforms and intermediate captures to your hearts content. This is difficult to explain and more difficult to appreciate until you see and use it in action.

Furthermore the challenge with concurrent GC is that max memory utilization is difficult to contain and difficult to make performance deterministic. So yes it has advantages. It also has severe disadvantages for the types of low-level efficient things Rust is meant for. Remember. Rust is meant to replace the existing problems that people reach for C/C++. That’s the space it’s competing in - embedded programming, operating systems, browsers, etc. There are problems that other languages are better suited for. Python, Ruby, Java are easier to work with not only because of GC. Java in particular pays an even larger cost due to not supporting value types and is still struggling afaik to integrate them properly into the GC which inhibits programmer-aided optimization of memory usage/layout.

Also, I’ll note that Swift and Objective-C are pretty easy to work with for memory management (on the level of Java) despite not having GC and get quite close to the performance of C/C++/Swift.

The challenges with GC that you handwave away has been what’s been said about GC ever since the beginning. Perhaps it’s time to admit that GC isn’t the silver bullet you think it is?

> and get quite close to the performance of C/C++/Swift.

In some cases, identical performance. ;)

Backreferences are hard in Rust, so a BB instead maintains its index into a Vec<BB>, owned by the function. But this index is just a number: ownership is not modeled, it is not statically checked, and it may fall out of sync. It is effectively a slow, weird (though sandboxed) raw pointer.

You can write this stuff in Rust, but it is awkward and Rust cannot bring its strengths to bear. Rust assumes a tree-like ownership model and if you fall off that path, it can’t help much. Graphs aren’t trees so Rust is less helpful here.

In my experience (unless I've misunderstood what you're trying to say) this is the fastest way to write graphs because of how much more cache-friendly it is than having to chase a load of pointers.

Suppose the parent maintains an array of children

  Node*

  Node**

In the Rust example, to do the same would take an extra few steps and probably miss the cache. I think speculative execution would favor the pointer method.

  #include <chrono>
  #include <iostream>
  #include <memory>
  
  static constexpr size_t MAX_NODES = 1 << 27;
  
  struct Node {
   size_t index_self;
   Node** ptr_self = nullptr;
  };
  
  struct TopLevel {
   Node** ptr_children;
   size_t n = 0;
   explicit TopLevel() : ptr_children(new Node*[MAX_NODES]) {}
   ~TopLevel() { delete[] ptr_children; }
   void add(const std::shared_ptr<Node>& descendant) {
    if (n < MAX_NODES) {
     ptr_children[n] = descendant.get();
     descendant->index_self = n;
     descendant->ptr_self = &ptr_children[n];
     n += 1;
    }
   }
  };
  
  int main(void) {
   TopLevel top_level{};
   for (int i = 0; i < MAX_NODES; ++i) {
    auto node = std::make_shared<Node>();
    top_level.add(node);
   }
   // access by pointer
   {
    auto t_0 = std::chrono::high_resolution_clock::now();
    Node** it = &top_level.ptr_children[0];
    for (int i = 0; i < MAX_NODES; ++i) {
     Node* via = *(*it)->ptr_self;
     it += 1;
    }
    auto t_1 = std::chrono::high_resolution_clock::now();
    std::cout
        << "Via pointer: "
        << std::chrono::duration_cast<std::chrono::nanoseconds>(
        t_1 - t_0)
        .count()
        << " ns\n";
   }
   // access by index
   {
    auto t_0 = std::chrono::high_resolution_clock::now();
    Node* it = top_level.ptr_children[0];
    auto idx = it->index_self;
    for (int i = 0; i < MAX_NODES; ++i) {
     Node* via = top_level.ptr_children[idx];
     idx += 1;
    }
    auto t_1 = std::chrono::high_resolution_clock::now();
    std::cout
        << "Via index: "
        << std::chrono::duration_cast<std::chrono::nanoseconds>(
        t_1 - t_0)
        .count()
        << " ns\n";
   }
   return 0;
  }

  % clang++ -O3 bench.cc && ./a.out
  Via pointer: 90 ns
  Via index: 41 ns

> With Rust, programmers have to spend most of their mental energy worrying about management of memory, which has largely been automated already.

This is a common misunderstanding. I think the word "automated" is misleading, and suggest that we should look at two phases of memory management: the plan and the execution.

In traditional low-level languages like C, you plan how to manage memory and you write code to execute that plan yourself. Your code may not match the plan, thus all sort of problems ensues.

In languages with GC, you are allowed to not think how to manage memory and GC will execute their own inferred plan... until it is not. At some point you are forced to think how to manage memory and also tune GC and/or code to fit to your belated plan. This point may not be reached (simple scripts) or can be delayed much further (good modern GC), of course, so it still remains very useful.

In (a typical use case of) Rust, you plan how to manage memory but give that plan to the compiler to check if the plan is executed correctly. The compiler also generate code for common executions that you don't have to. So the execution is mostly automated (or rather, delegated), while planning is not.

A common theme here is that you can't avoid at least the planning once you've got past a threshold. If GC would supplant even that planning, you won't need value types at all; isn't that what the generation hypothesis is all about? But many languages with GC but not value types now get them. While it can be argued that Rust's affine typing is not sufficient to capture some common memory management patterns [1], that fact doesn't diminish the value of explicit memory management planning, and thus Rust's.

[1] And I think it is actually true! Indeed, I believe affine typing plus GC can be actually better than affine typing or GC alone (and value types mimic a good subset of this). There are some Rust libraries for tracing GC (e.g. [2]) as a starting point.

[2] https://github.com/Manishearth/rust-gc

Yes! That's awesome! I want the set of programs I can write to be small, but still large enough to contain correct programs.

For example, I really like statically typed languages! But what is static typing? It's rules that reduce the set of valid programs. In a dynamically typed language, 'def double(x): x*2; double(os.Open("foo"))' or other such nonsense is a valid program that errors out at runtime reliably. In a statically typed language, that program is not valid. Woo! That's a whole class of programs that do bad stuff which aren't valid anymore!

If rust restricts the set of valid programs to those that structure the ownership of data more rigidly, I'll take it!

I do realize that rust has escape hatches that let you model those things when you need to, but I'll gladly take a language that pushes programmers away from difficult to reason about data-ownership-models even if it doesn't prevent all such cases.

Especially not the type of programmers Rust is appealing to. They seem to be more excited by WebAssembly than the stuff that actual low latency people worry about, like tuning obscure FPGAs and vectorizing math code. These are industries like audio processing, SpaceX, industrial equipment manufacturers, self-driving cars, high frequency trading. Definitely not code targeting x86_64 cloud VMs or iPhones.

In hard real-time environments they do not even do memory management. They just statically allocate the whole heap and never malloc or free while the program is running. So even if Rust is better at memory management, it won't make them switch from C because it wasn't an issue.

The idea is to have a DSL inside Rust that essentially has haskell semantics. This allows you to write performance sensitive code in Rust and then marshall it into Gluon where you can do high level manipulations with type safety before you unmarshall into a performance sensitive section again.

To me the failure of Rust is more that it didn't go full-on-haskell syntax wise and (to a lesser extent) that there isn't a specification (or some standards) beyond the test suite.

That's true of all static type systems.

Also, the whole point of Rust is to cover cases where performance and memory management are important. If you can use a GC'd langauge for you program, then pick one of the many fantastic existing ones.

Here is a good read about it: https://blog.plan99.net/modern-garbage-collection-911ef4f8bd...

A subtle point often missed is that if you want the anonymous structure of your closure itself to own a value, so that you can have a closure with a `'static` lifetime (which lives forever) that still could be called multiple times, you must use move keyword. If you just move the values into the closure manually, your closure will be a `FnOnce` since the compiler will mistakenly believe that you want to move that value each time the closure gets invoked, which can only happen once if the moved value doesn't implement `Copy`. In constrast, if you use the `move` keyword, compiler will correctly move the value into the anonymous structure of the closure itself during its construction, and the closure will be a `FuMut` and/or `Fn` as long as you don't consume the said value in the closure.

> The idea that I can touch variables that have gone out of scope (and that have ostensibly been GC'd)

You can't touch variables that have been garbage collected, indeed. A variable captured in a closure will have a reference to it and therefore not be garbage collected until the closure itself goes out of scope and is garbage collected.

Closures allow encoding some state into a function, which is especially useful for higher order functions that return specialized functions, for example. This is, for example, how decorators in Python work - a function is captured in a closure, which is then referenced and called by a new function wrapping the original function.

It's sort of a contrary opinion but I prefer to be explicit about state, and closures are sort of silently bundling up state for you behind the scenes. It's not very apparent from the syntax.

I think languages should have a lighter-weight syntax for classes and that would subsume many use cases for closures.

-----

While I've never programmed in PHP, it appears PHP actually has a pretty nice solution for this problem! You declare the variables captured using 'use':

https://stackoverflow.com/questions/1065188/in-php-what-is-a...

    $callback =
        function ($quantity, $product) use ($tax, &$total)

Since then, though, I've come to doubt my conclusion, for two reasons:

1. The same thing is true of, for example, static types; but using type inference or dynamic typing often makes your code easier rather than harder to read. (Some wag said something to the effect that dynamic typing is what you do when it's simultaneously so trivial to see that your program has no type errors that you can do it in your head and so difficult that you don't want to spend the time to do the proof.)

2. There isn't a really compelling difference to me between the closure in

    ^(x < 2 ifTrue: [ 1 ] ifFalse: [ (x - 1) factorial ])

    fetch(json).then(r => widget.displayJson(r.json()))

    (let ((overlay (make-overlay beg end)))
      (overlay-put overlay 'face (or face 'highlight)))

That is, inner blocks of control structures implicitly capture variables from their outer scope all the time, and this is mostly not a problem; and closures are a useful technique to make it possible to extend the set of control structures. (As it happens, let in Emacs Lisp is implemented as a built-in special form, but in Scheme it's normally implemented as a macro that puts the inner block into a closure.)

Maybe part of the reason is the lifetime: the example with fetch() is in fact socking away a reference to widget until after the HTTP response comes back, so aliasing bugs and space leaks are possible, while the other two examples aren't. This might be a reason implicit closures are so much more popular in functional programming languages: aliasing bugs are not a problem for immutable data, and nobody expects to be able to predict how much memory their functional program will need anyway.

I believe that would be 'lambda-lifting', i.e. taking a lambda which has free variables, adding those free variables to its input variables, moving the lambda out into the top- level, and modifying the call site to pass in the no-longer-free-variables. That should give you completely reasonable lifetimes and only require the stack.

It gets trickier when you want functions to be able to return functions. For instance:

  add(a, b) {
    a + b
  }

  myFun() {
    var add5 = x -> add(5, x);
    var add6 = x -> add(6, x);
    add5(1) + add6(2)
  }

I think this might be due to your mental model of GC not quite matching the way it's usually implemented (at least, in traditional GC, as opposed to reference counting); most GC gives no guarantees that memory will immediately be cleaned up once the last reference goes out of scope, just that it will happen some time in the future (usually the next time it checks). Languages like Rust (and C++, if you use destructors) will inline the memory cleanup at the end of the scope, but this is pretty explicitly not what will happen in a garbage-collected language.

Note also that this isn't really any different than the fact that a variable can go out of scope and not be cleaned up if another reference to it exists. Consider the following Java-esque code:

    void setNewChild(Parent parent) {
        var child = new Child();
        parent.child = child;
    } 

But in this example the last reference hasn't gone out of scope, the last reference is in the closure. If the GC ignored closures and acted as if last reference had gone out of scope then there's a chance that that variable would be cleaned up before the closure gets called, which would make closures completely useless.

As with any other syntactic sugar, it's easy to reason about the behavior once you know what the syntax desugars into.

One classic example I see with beginning programmers all the time is the order of the parts of a for loop.

e.g.

    for(initialization statement; bounds check expression; increment statement) {
      ...
    }

    {
      initialization statement;
      while (bounds check expression) {
        ...
        increment statement;
      }
    }

Closures aren't much different. In Rust, if anything, they're less magic, because you have to be explicit about the lifetime of the closure relative to the references it's borrowing.

There's just a subtle detail to keep in mind here: both "continue" and "break" are syntactic sugar for "goto", and when converting a "for" loop into a "while" loop, you have to also convert "continue" to a "goto" to a label just before the increment statement.

    const Counter = () => {
      let counts = new Map();

      return {
        reset: () => {
          counts = new Map();
        },

        count: (key) => {
          const count = counts.get(key) + 1;
          counts.set(key, count);
          return count;
        }
      }
    }

    const items = ['apple', 'apple', 'banana', 'canteloupe'];
    const counter = Counter()

    items.forEach(item => {
      console.log(item + ": count is", counter.count(item));
    })

    counter.reset();
    // do some more counting now

https://pdfs.semanticscholar.org/73a2/e3c03f799956aa5a3188e4...

This is just one way to do it, but it's an efficient way, and easy to understand.

  #include <functional>
  #include <iostream>
  auto foo(double a) -> std::function <double(double)> {
      return [&a](auto x) {
          return x + a;
      };
  }
  int main() {
      auto f = foo(2.0);
      std::cout << f(1.0) << std::endl;
      std::cout << f(1.0) << std::endl;
  }

  3
  1

  fn foo(a: f64) -> impl Fn(f64) -> f64 {
      |x: f64| -> f64 { x + a }     
  }          
  fn main() {                
      let f = foo(2.0);      
      println!("{}", f(1.0));                                                     
      println!("{}", f(1.0));                                                     
  } 

  error[E0597]: `a` does not live long enough
   --> test01.rs:2:27
    |
  1 | fn foo(a: f64) -> impl Fn(f64) -> f64 {
    |                   ------------------- opaque type requires that `a` is borrowed for `'static`
  2 |     |x: f64| -> f64 { x + a }
    |     ---------------       ^ borrowed value does not live long enough
    |     |
    |     value captured here
  3 | }
    |  - `a` dropped here while still borrowed

  fn foo(a: f64) -> impl Fn(f64) -> f64 {
      move |x: f64| -> f64 { x + a }
  }          
  fn main() {                
      let f = foo(2.0);      
      println!("{}", f(1.0));                                                     
      println!("{}", f(1.0));                                                     
  }

  3
  3

  let foo a =
      fun x -> x +. a
  in
  let f = foo 2.0 in
  Printf.printf "%f\n" (f 1.0);
  Printf.printf "%f\n" (f 1.0);

  3.000000
  3.000000

Beyond that, my point is that a garbage collector can track the use of variables and memory extremely well, which makes the process of constructing closures moderately easy. We can have closures without garbage collection, but then we must be careful about who and what owns this memory. C++ does not enforce this, but Rust does, which is one of its benefits.

fn foo<'a>(a: &'a f64) -> impl Fn(f64) -> f64 + 'a { ....

but it doesn't work

Pretty much. When implementing closures, the variables that are going to be used by the nested functions are allocated on the heap instead of on the stack. The nested function is then set up to receive a pointer to the outer variables as an additional parameter.

If you want to read more about it, the word to search for would be "closure conversion"

http://matt.might.net/articles/closure-conversion/

It's unfortunate the the Wikipedia article for closure conversion now redirects to the article about Lambda Lifting. They are related but aren't quite the same thing.

Yup. A "first class" closure is just reifying some arguments of a future function call and bundling them up nicely in a struct/record. This is especially clear in languages that support currying, since that means you'll literally be building that record step-by-step - only after a full set of arguments is provided does a true function call really occur.

As a concrete example, the `compose` method given should clearly be the same for `Fn`, `FnOnce`, and `FnMut`. Can we write it once and reuse it for `Fn`, `FnOnce` and `FnMut`? If not, why not?

Also, what happens when you compose one function with FnMut and another with just Fn? The answer is clearly FnMut. These three traits are related by a subtyping relationship. I don't know enough Rust to answer the question of whether such a hypothetical compose function can return the right one from this hierarchy.