Is it possible to have nested functions, without having closures, in a lexically scoped language which has first class functions?

Question

A closure is a record storing a function, together with an environment: A mapping associating each free variable of the function (variables that are used locally, but defined in an enclosing scope) with the value or reference to which the name was bound when the closure was created. (Wikipedia)

Here is what I understand. A function can access to 3 types of variables (Let's assume JavaScript):

1. Parameters: The parameters of a function.
2. Local variables: The variables defined inside of a function. (but not the variables defined in a nested function. That is, a function cannot access variables defined in another function, where this another function is defined inside the function we are talking about)
3. Free variables: The variables defined outside of the function. That is, the function can access the variables defined in the function which surrounds our function, and the variables defined in the function which surrounds the function that surround our function, etc.

Of these 3 types, the values of the variables of type 1 and 2 are well known at the time a function is called. However, the variables of type 3 can have any value at the time a function is called. To the best of my knowledge, this is a property of dynamically scoped languages. That is, AFAIK, in lexically scoped languages, we cannot have such situation.

That's where a closure comes into scene. A closure binds the free variables of a function. Hence, there isn't any variable which doesn't have a well known value, at the time a function is called.

So, my question is the following:

Are closures a must have in lexically scoped languages, which allow nested functions and which have first class functions?

To me, it seems like so. Because if nested first class functions are allowed in a language without having closures, then this means that the free variables will have non-deterministic values at the time a function is called. But AFAIK, having non-deterministic values is a property of dynamically scoped languages. Hence, I claim:

If a language claims to be lexically scoped, and if a language allows nested first class functions, then, by definition, every function in that language is (must be) a closure.

I am correct in this?

Answer 1

I don't think your conclusion is true.

function outer1() {
  const foo = 42;

  function inner1() {};
}

In this case, inner1 is not a closure, but it is a nested function. It simply doesn't use any identifiers from the surrounding scope.

function outer2() {
  const foo = 42;

  function inner2() { return foo; };

  return inner2();
}

Here, inner2 does use foo, but inner2 never leaves the scope of outer2, and thus doesn't "close over" its surrounding environment. It is not a closure.

function outer3() {
  const foo = 42;

  function inner3() { return 23; };

  return inner3;
}

Here, inner3 does leave the scope of outer3, but it doesn't use any free variables. Again, not a closure.

function outer4() {
  const foo = 42;

  function inner4() { return foo; };

  return inner4;
}

Only inner4 is actually a closure: it leaves the scope of outer4 and closes over its environment and "takes it with it".

So, as you can see, it is perfectly possible to have nested functions which aren't closures in a lexically scoped language, as long as at least one of the following is true:

1. the nested function has no access to the surrounding environment
2. the nested function does not leave the scope of the surrounding environment

To be fair, I can't think of a language that has those restrictions, though. But there are similar restrictions on by-ref captured variables in C++ lambdas, I think. A C++ lambda that captures a variable by-reference can either not use that variable or not leave the scope. If it does both, the result is undefined behavior (and will most likely result in an illegal memory access).