I'm trying to explain this in as much brevity as I can, but this will be a long post.

> What do you mean by "at runtime"? The only language that I'm familiar with that really lets you define them at runtime is Lisp.

Lisp is not the only language that allows this. This is why I mentioned JavaScript at the end of my last comment. In general, it would be easy for a scripting language to support this feature. What's more interesting is that some compiled languages do as well. For example, Chicken Scheme. Scheme being a form of Lisp supports first-class functions, and Chicken Scheme being a compiled form of Scheme does as well.

An example from JavaScript:

function ValueAlerter(x)
{
return function () {
window.alert(x);
}
}

Any time this function is called (ValueAlerter), a new unnamed function is created that references the closure of ValueAlerter.

It's possible to write the same thing with a named function.

function ValueAlerter(x)
{
function result() {
window.alert(x);
}
return result;
}

Note that this is, using prototypes, generally how OOP is implemented in JavaScript.

> > Lambdas are essentially syntactic sugar.

> Do you mean that lambdas are essentially syntactic sugar for creating functions at runtime? Because C++ has lambdas, and if you mean "lambdas = creating functions at runtime = functions as first-class values", well, C++ has lambdas...

> Could you clarify? I'm sorry, but I'm having trouble seeing what distinctions you're trying to draw.

When a language feature is called syntactic sugar, it means that it makes certain ideas easier to express, but it doesn't create new functionality. An example in C++ is the -> operator. The alternative to writing a->b is (*a).b which is more cumbersome.

So no, lambdas do not allow you to create "functions" at runtime (when speaking of our complete definition of a first-class function). I would assume that a C compiler is able to isolate the code in a lambda into its own function, so it is equivalent to writing a separate function, depending on how it is referenced. The `auto' type also facilitates this because newer C++ features involve certain types which cannot be used by the programmer.

So you can think of C++ lambdas as a sort of macro for writing code locally. It's similar to using

a = p ? x : y;

instead of

if (p) a = x; else a = y;

in that it is a language feature that allows for the programmer to type less for the same result.

--

For a more illustrated example, think of a basic sequence of function calls. Function A calls B, and B calls C. The callstack in a C++ program for this sequence would look like this:

A()
B()
C()

The computer's stack looks like this when it is executed:

Top of the Stack
----
A's local variables.
----
B's local variables.
----
C's local variables.
----
Bottom of the Stack

Now, it's possible for C() to create a function and store that somewhere. In a C++ lambda, with a captured local variable, this dynamic function would have a reference to one of C()'s local variables. In a JavaScript or Lisp program, this dynamic function would also have access to one of C()'s locals. This is fine if the dynamic function is called when C() is still in scope.

If, however, this is stored in a result that is accessible from A() and it is executed after B() is out of scope, and this function references a local value from C(), then the reference would look something like this:

Top of the Stack
----
A's local variables.
----
Bottom of the Stack
----
Garbage
----
Garbage (Reference to C() variable)
----

So basically, native C or C++ functions cannot be first-class with this model of computation, while it's trivial for Lisp and Scheme. Now it is possible to use this sort of paradigm with a number of templates, libraries, strategies, added language features, but nothing that approaches native first-class functions.

Making a sincere implementation of this would be more daunting than creating a new language.