From Newsgroup: comp.arch

On Sat, 14 Mar 2026 09:34:55 -0700, Tim Rentsch
<tr.17687@z991.linuxsc.com> wrote:

George Neuner <gneuner2@comcast.net> writes:

On Sat, 14 Feb 2026 20:40:26 -0800, Tim Rentsch
<tr.17687@z991.linuxsc.com> wrote:

Returning to the main area of discussion - it occurs to me that we
may have different operational assumptions about the situations
where nested functions (or lambda expressions) are called. In
particular, there is an important distinction between a call where
it is known which nested function/lambda is being called, and a call
where that is not known, for example by virtue of having been passed
as a function argument, with the call being done through a formal
parameter.

I make no assumptions about whether a closure can outlive the call
chain that created it - unless the function is so simple as to be able
to be /compiled/ inline, that pretty much is a given.

But there is an operational difference between a 1st class closure
which is stored or passed upward and may be called from anywhere, and
a 2nd class closure which, if stored or passed at all, will be called
only at or below the scope that defined it.

And similarly, the ways in which the compiler can treat the closure
are different.



I know you [Tim] know this, but for sake of others following along,
there are two general methods for compiling a closure:

The first is "closure conversion" in which the function's stack based
free variables are relocated into a heap allocated structure. The
function is modified to take an additional "environment" pointer, and
to access its free variables from the structure rather than the stack.
All the call sites then are modified to pass the address of the
"environment" structure.

The second is "lambda lifting" which modifies the function such that
its free variables become explicit arguments. All of its call sites
are modified to pass those variables.


The question of which method makes more sense depends on what use will
be made of the closure. If the closure's "name" [symbol or pointer]
can be stored into a data structure for some unknown use later, then a
variant of closure conversion is the only /safe/ way to do it.

However, there are many cases where - even with anonymous functions -
the use is delimited and guaranteed to be at or below the scope that
defined the closure. This is quite common in FP languages, and even
in C++[*]. If the free variables are guaranteed to be in scope, there
is no need to relocate them.


[*] C++ closures are objects that can be stored and passed around, but
witness what happens if you bind some free data by reference and it is
no longer available when the closure is invoked. BOOM!

This distinction is analogous to calling an outside
function using its name versus calling a function through pointer
to function, where it isn't known what the pointer might point to.
When calling a function using the function's name, it is possible to
expand the function body inline. (The inline expansion might be
done at link time, but conceptually that is no different.)

Conversely, when calling through a pointer-to-function, doing an
inline expansion isn't feasible in general, because we don't know
what function is going to be called, and also there might be more
than one. The same sort of distinction occurs with calls to nested
functions (or equivalently lambdas).

Agreed WRT inlining - it generally is not possible to inline a closure
function at the call site.


But WRT calling a function through a pointer, there is little
difference vs calling it by name: in either case the compiler (or
linker) simply needs to know the function's signature [or a dumb
C-like calling convention]. Compiling a call can involve syntactic
swizzling and/or passing hidden arguments: witness object method
calls in C++.


In Lisp or Scheme every function is anonymous. If you want to "save"
it for use later, you bind it to a name.

When you "defun" or "define" the mental picture is of creating a named function, but in reality[+] you are creating two objects: a named
symbol, and an anonymous function which then is bound to the symbol.


E.g. in Scheme, there is no difference [apart from syntax] between

(define foo (x y) ...)
and
(define foo (lambda (x y) ...))

In either case you call it by (foo x_arg y_arg) and refer to it by
foo whenever you need it, e.g., (map foo ... )

Additionally you can (define fie foo) or (let ((fie foo)) ... )
either of which makes fie refer to the same object as foo.
[Functions are objects. This are analogous to copying a pointer.]

Yet there are Schemes that can inline function uses given the proper circumstances.


[+] In both Lisp and Scheme, local functions (closures or simple) that
only ever are passed downward can be bound to compiler generated
"internal" names rather than programmer named symbols. This is an implementation detail.

Also Lisp can't quite manage the simple use shown above because Lisp
allows dual binding both a data object and a function object to the
same symbol. In context, when the symbol itself is data, you need to
use a different syntax to specify that you want to use its function
binding rather than its data binding.
Not particularly relevant here, but included for completeness.

The key point is that when packaging up a nested function plus data
into a closure, they all have to look the same: one pointer to
function and one pointer to data. That's because down the line the
ultimate caller doesn't know where the closure came from, so all
closures have to be structurally identical.

All uses of the function must call the function in the same way. This
is true regardless of whether it is a closure or simple function.

In the case of the closure, however, there is no requirement that
there be only "one pointer to [environment] data". That is just one
way of doing it.


Note that lambda lifting can be done partially, and it also can be
combined with closure conversion by creating the closure as a
trampoline which calls the lifted function passing environment data as arguments.

Trampoline? Two calls instead of one? Why would you do this?

Well, it might make sense if the function works with, e.g., multiple
(or multi-dimensional) arrays, and the computation performed is such
that the code will be more performant if the function is given
pointers to the data rather than having to figure them out every time.

This, of course, depends on many things such as: source language, CPU addressing capabilities, available runtime information (dope vectors?
limits, etc.), and on the compiler's optimization (or not) of address computations.

Analogous arguments can be made for any complex data structures that
could end up in a closure's environment [doesn't matter read-only or read-write]. What is best to do is, at best, an ad hoc metric ...
there are no rules.

When I talk about closures, my built-in assumption is that what is
being talked about is the don't-know-who-is-being-called case. Any
direct call to a nested function doesn't need a closure (there might
be one as a matter of convenience, but there doesn't have to be), so
any idea of adjusting call the call sites doesn't apply when we're
talking about closures (again, to be clear, in the way I use the
term closure).

My sense now is that you are talking (mostly? exclusively?) about
the direct call case. Is that a fair read of your comments?

Yes, sort of.

My initial response (to Mitch) mainly was concerned with the block
structured, delimited 2nd class case where it is possible to know
whether free variables would still be in scope at the call sites.

It is good that you brought up the 1st class case. It is important
that people understand the whole picture rather than just a piece of
it.


Yes, closure conversion provably handles any use case. Just realize
that it may not be the most performant way to do it. ;-)

--- Synchronet 3.21f-Linux NewsLink 1.2