According to Scott Lurndal <slp53@pacbell.net>:
>>If you want to support nested functions, it's not hard, you make
>>function pointers two words, the code pointer and the static chain.
>
>Why? Nested functions need access to containing function local _data_,
>not code. The actual generated code is independent of the containing
>function.

Sorry, I meant pointers to nested functions. You are quite right that
if you can't take the address of an internal function, the code is
straightforward.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

John Levine wrote:

> According to Scott Lurndal <slp53@pacbell.net>:
>>>If you want to support nested functions, it's not hard, you make
>>>function pointers two words, the code pointer and the static chain.

Quibble:

The conventional understanding is that a word is 32-bits* whereas by now
all address spaces are 64-bit capable. (*) except in x86 land where
word remains 16-bits (crikey) which makes "word" even less useful
when describing pointers.

>>
>>Why? Nested functions need access to containing function local _data_,
>>not code. The actual generated code is independent of the containing
>>function.

> Sorry, I meant pointers to nested functions. You are quite right that
> if you can't take the address of an internal function, the code is
> straightforward.

Say you have an array of pointers to nested recursive functions;
Each of these pointers was initialized at some depth of recursion,
and run into an indexed dereference of one of those pointers::

result = fun_p[k](arguments);

How do figure out where on the call-stack the scope of this particular
function being called resides ??

Then: is it possible to pass this nested function pointer through a
void * pointer and back to a nested function pointer and retain the
to access the function in the scope it was initialized ??

void *p = fun_p[k];
result = p(arguments);

On 2023-12-19 23:58, Thomas Koenig wrote:
> Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
>
>>> E.g., consider a numerical integration function integrate(f,lo,hi),
>>> which expects a function with one parameter f(x), and you want to
>>> integrate x^y (pow(x,y) in C), where y is, say, passed as parameter.
>>
>>
>> That is the canonical example, yes. But it happens I have never needed
>> to do numerical integration in my Ada programs. I do have some cases
>> where I have used locally instantiated generics with generic function
>> parameters in the way I described above. In Ada the integration example
>> would be declared thusly:
>>
>> generic
>> with function F (X : Float) return Float;
>> function Integrate (Lo, Hi : Float) return Float;
>>
>> although one would usually not limit it to a specific number type such
>> as Float, but would make this type also a generic (type) parameter.
>> IIRC, the ability to define numerical integration as a generic
>> subprogram, with the function to be integrated as a generic parameter,
>> was one of the reasons presented for omitting function pointers entirely
>> from original Ada (Ada 83).
>
> Interesting, thanks!
>
> Just one remark: Making numerical routines generic can be a bit
> problematic if constants depend on the accuracy of a type; things
> like tolerances for checks for convergence, number of coefficients
> in a polynomial (or Chebyshev) evaluation, quantities to divide by
> for numeric differentiation etc.

I certainly agree that the numerical analysis involved in implementing
something type-generic to a known accuracy is hard, and probably beyond
my skills. However, Ada provides a number of "attributes" that can be
used to query the properties of a floating-point type, including a
generic formal type, for example S'Model_Epsilon which shows the
accuracy of the floating-point type S. In principle, a generic algorithm
could adjust itself according to these properties.

For the full list of these attributes and their definitions, see
http://www.ada-auth.org/standards/22rm/html/RM-A-5-3.html and
http://www.ada-auth.org/standards/22rm/html/RM-G-2-2.html.

On 2023-12-20 0:37, MitchAlsup wrote:
> Thomas Koenig wrote:
>
>> Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
>
>>>> E.g., consider a numerical integration function integrate(f,lo,hi),
>>>> which expects a function with one parameter f(x), and you want to
>>>> integrate x^y (pow(x,y) in C), where y is, say, passed as parameter.
>>>
>>>
>>> That is the canonical example, yes. But it happens I have never
>>> needed to do numerical integration in my Ada programs. I do have some
>>> cases where I have used locally instantiated generics with generic
>>> function parameters in the way I described above. In Ada the
>>> integration example would be declared thusly:
>>>
>>>     generic
>>>        with function F (X : Float) return Float;
>>>     function Integrate (Lo, Hi : Float) return Float;
>>>
>>> although one would usually not limit it to a specific number type
>>> such as Float, but would make this type also a generic (type)
>>> parameter. IIRC, the ability to define numerical integration as a
>>> generic subprogram, with the function to be integrated as a generic
>>> parameter, was one of the reasons presented for omitting function
>>> pointers entirely from original Ada (Ada 83).
>
>> Interesting, thanks!
>
>> Just one remark: Making numerical routines generic can be a bit
>> problematic if constants depend on the accuracy of a type; things
>> like tolerances for checks for convergence,
>
> whether compiler constant arithmetic has the same numeric properties as
> compiled code instruction sequences,

Ada compilers are required to evaluate typeless constant arithmetic to
unbounded precision (as "bignums"). For example, the constant pi is
defined thusly in the standard package Ada.Numerics:

Pi : constant :=
3.14159_26535_89793_23846_26433_83279_50288_41971_69399_37511;

and all the digits are significant in any computation involving Pi and
other typeless constants.

Computation with typed constants is required to use the operations of
that type, so should match what the target code does.

On 19/12/2023 22:35, Niklas Holsti wrote:
> On 2023-12-19 20:12, Anton Ertl wrote:
>> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>>> In my own (non-critical) Ada programs, small nested subprograms are not
>>> unusual, but pointers to them are very rare (I don't recall a single
>>> case of it).
>>
>> That's interesting, because a major reason for using nested functions
>> (or, more generally, closures), is if you need to pass a function with
>> a given interface, but have to pass additional data to that function.
>
>
> In Ada, instead of passing a (nested) function pointer to some service
> that needs such a parameter, one can implement the service as a generic
> program unit, where the function to be passed is given as a generic
> parameter, and instantiate that generic locally in the nested context,
> thus binding the instance with the nested function.
>
> Depending on the way the compiler implements such generics (as macros,
> or with shared code) this may or may not be implemented by passing a
> function pointer, but even if it is, the compiler can use a "fat
> pointer" for this generic case, without being forced to use a fat
> pointer for all function pointers.
>

That sounds very like lambdas in C++. It is much better than the way
nested functions in (extended) C sometimes have to be implemented, where
run-time generated trampoline functions on the stack are used to hide
the "fat" when a fat pointer would be safer and more efficient.

MitchAlsup wrote:
> EricP wrote:
>
>>
>> If one has super and User mode, and R,W,E enables, that's 6 PTE bits.
>> The PTE is very cramped so there is a big incentive to save any bits.
>> We can get that down to 3 PTE bits by throwing out the silly
>> combinations,
>> Write-only, Execute-only, Super:NoAccess+User:RWE,...
>
> If one uses a different page table for user and supervisor, you only
> need those 3-bits. In my case Guest OS has its own table and its own
> ASID completely separate from application. ASID plays the part of G
> (global).

Ok but all major OS's view the current process address space (P-space)
as directly addressable from system space (S-space), so the OS can reach
directly into the current process to read or write memory to pass args
to/from syscalls or deliver signals, etc.

To support this view of virtual memory on that platform all OS's would
need to maintain two parallel page tables to map each P-space twice,
one for user mode and one for super mode.

Niklas Holsti wrote:

> On 2023-12-20 0:37, MitchAlsup wrote:
>> Thomas Koenig wrote:
>>
>>> Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
>>
>>>>> E.g., consider a numerical integration function integrate(f,lo,hi),
>>>>> which expects a function with one parameter f(x), and you want to
>>>>> integrate x^y (pow(x,y) in C), where y is, say, passed as parameter.
>>>>
>>>>
>>>> That is the canonical example, yes. But it happens I have never
>>>> needed to do numerical integration in my Ada programs. I do have some
>>>> cases where I have used locally instantiated generics with generic
>>>> function parameters in the way I described above. In Ada the
>>>> integration example would be declared thusly:
>>>>
>>>>     generic
>>>>        with function F (X : Float) return Float;
>>>>     function Integrate (Lo, Hi : Float) return Float;
>>>>
>>>> although one would usually not limit it to a specific number type
>>>> such as Float, but would make this type also a generic (type)
>>>> parameter. IIRC, the ability to define numerical integration as a
>>>> generic subprogram, with the function to be integrated as a generic
>>>> parameter, was one of the reasons presented for omitting function
>>>> pointers entirely from original Ada (Ada 83).
>>
>>> Interesting, thanks!
>>
>>> Just one remark: Making numerical routines generic can be a bit
>>> problematic if constants depend on the accuracy of a type; things
>>> like tolerances for checks for convergence,
>>
>> whether compiler constant arithmetic has the same numeric properties as
>> compiled code instruction sequences,

> Ada compilers are required to evaluate typeless constant arithmetic to
> unbounded precision (as "bignums"). For example, the constant pi is
> defined thusly in the standard package Ada.Numerics:

> Pi : constant :=
> 3.14159_26535_89793_23846_26433_83279_50288_41971_69399_37511;

> and all the digits are significant in any computation involving Pi and
> other typeless constants.

> Computation with typed constants is required to use the operations of
> that type, so should match what the target code does.

What happens when the hosting machine makes a rounding error that the
target machine would not ?? {{Say, for example, the ADA routine changes
the rounding mode as it goes about its business, but the host compiler
does not see the rounding mode being changed ??}}

EricP wrote:

> MitchAlsup wrote:
>> EricP wrote:
>>
>>>
>>> If one has super and User mode, and R,W,E enables, that's 6 PTE bits.
>>> The PTE is very cramped so there is a big incentive to save any bits.
>>> We can get that down to 3 PTE bits by throwing out the silly
>>> combinations,
>>> Write-only, Execute-only, Super:NoAccess+User:RWE,...
>>
>> If one uses a different page table for user and supervisor, you only
>> need those 3-bits. In my case Guest OS has its own table and its own
>> ASID completely separate from application. ASID plays the part of G
>> (global).

> Ok but all major OS's view the current process address space (P-space)
> as directly addressable from system space (S-space), so the OS can reach
> directly into the current process to read or write memory to pass args
> to/from syscalls or deliver signals, etc.

My 66000 provides this. Guest OS can reach down into application VaS,
application cannot reach up into Guest OS VaS. When Guest OS accesses
its own VaS it uses its own ASID, when accessing application it uses
application ASID. The same analogue occurs in Guest HV reaching down
into Guest OS VaS. When Guest HV accesses its own VaS it uses 1-level
translation and its own ASID; when accessing Guest OS it uses 2-level
translation and Guest OS ASID.

Switching between levels is fast because all the required information
is loaded at all times. Switching contexts is fast because only 1
register needs to be written, the data is obtained as if the control
registers were a cache of the data at the written address.

> To support this view of virtual memory on that platform all OS's would
> need to maintain two parallel page tables to map each P-space twice,
> one for user mode and one for super mode.

On 12/20/2023 6:10 AM, David Brown wrote:
> On 19/12/2023 22:35, Niklas Holsti wrote:
>> On 2023-12-19 20:12, Anton Ertl wrote:
>>> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>>>> In my own (non-critical) Ada programs, small nested subprograms are not
>>>> unusual, but pointers to them are very rare (I don't recall a single
>>>> case of it).
>>>
>>> That's interesting, because a major reason for using nested functions
>>> (or, more generally, closures), is if you need to pass a function with
>>> a given interface, but have to pass additional data to that function.
>>
>>
>> In Ada, instead of passing a (nested) function pointer to some service
>> that needs such a parameter, one can implement the service as a
>> generic program unit, where the function to be passed is given as a
>> generic parameter, and instantiate that generic locally in the nested
>> context, thus binding the instance with the nested function.
>>
>> Depending on the way the compiler implements such generics (as macros,
>> or with shared code) this may or may not be implemented by passing a
>> function pointer, but even if it is, the compiler can use a "fat
>> pointer" for this generic case, without being forced to use a fat
>> pointer for all function pointers.
>>
>
> That sounds very like lambdas in C++.  It is much better than the way
> nested functions in (extended) C sometimes have to be implemented, where
> run-time generated trampoline functions on the stack are used to hide
> the "fat" when a fat pointer would be safer and more efficient.

I believe Pascal, back in the 1970s implemented nested functions, though
I don't know how any specific implementation accomplished it. ISTM,
this is a nice mechanism for program development, allowing "iterative"
development.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

MitchAlsup wrote:
> EricP wrote:
>
>> MitchAlsup wrote:
>>> EricP wrote:
>>>
>>>>
>>>> If one has super and User mode, and R,W,E enables, that's 6 PTE bits.
>>>> The PTE is very cramped so there is a big incentive to save any bits.
>>>> We can get that down to 3 PTE bits by throwing out the silly
>>>> combinations,
>>>> Write-only, Execute-only, Super:NoAccess+User:RWE,...
>>>
>>> If one uses a different page table for user and supervisor, you only
>>> need those 3-bits. In my case Guest OS has its own table and its own
>>> ASID completely separate from application. ASID plays the part of G
>>> (global).
>
>> Ok but all major OS's view the current process address space (P-space)
>> as directly addressable from system space (S-space), so the OS can reach
>> directly into the current process to read or write memory to pass args
>> to/from syscalls or deliver signals, etc.
>
> My 66000 provides this. Guest OS can reach down into application VaS,
> application cannot reach up into Guest OS VaS. When Guest OS accesses
> its own VaS it uses its own ASID, when accessing application it uses
> application ASID. The same analogue occurs in Guest HV reaching down
> into Guest OS VaS. When Guest HV accesses its own VaS it uses 1-level
> translation and its own ASID; when accessing Guest OS it uses 2-level
> translation and Guest OS ASID.
>
> Switching between levels is fast because all the required information
> is loaded at all times. Switching contexts is fast because only 1
> register needs to be written, the data is obtained as if the control
> registers were a cache of the data at the written address.

How does these two ASIDs allow 3 bits in a PTE to grant different
access for the same page to user and OS? For example S:RW,U:RE

>> To support this view of virtual memory on that platform all OS's would
>> need to maintain two parallel page tables to map each P-space twice,
>> one for user mode and one for super mode.

EricP <ThatWouldBeTelling@thevillage.com> writes:
>MitchAlsup wrote:
>> EricP wrote:
>>
>>>
>>> If one has super and User mode, and R,W,E enables, that's 6 PTE bits.
>>> The PTE is very cramped so there is a big incentive to save any bits.
>>> We can get that down to 3 PTE bits by throwing out the silly
>>> combinations,
>>> Write-only, Execute-only, Super:NoAccess+User:RWE,...
>>
>> If one uses a different page table for user and supervisor, you only
>> need those 3-bits. In my case Guest OS has its own table and its own
>> ASID completely separate from application. ASID plays the part of G
>> (global).
>
>Ok but all major OS's view the current process address space (P-space)
>as directly addressable from system space (S-space), so the OS can reach
>directly into the current process to read or write memory to pass args
>to/from syscalls or deliver signals, etc.
>
>To support this view of virtual memory on that platform all OS's would
>need to maintain two parallel page tables to map each P-space twice,
>one for user mode and one for super mode.

ARMv8 maps each half separately. There is a separate translation table
for each half of the virtual address space, with the high-half holding
the kernel code and data, and the low half holding the user portion.

Each half has it's own translation table base register and each half
can use a different asid.

Context switch between processes simply requires reloading the
table base register for the lower half (TTBR0_EL1). No other
TLB maintainance is required unless the 16-bit ASID wraps.

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>I believe Pascal, back in the 1970s implemented nested functions, though
>I don't know how any specific implementation accomplished it.

AFAIK Pascal implementations all just use static links chains to the
enclosing scopes. So you access an outer local by following the link
chain as many levels as you cross scopes. Pascal allows passing
nested functions/procedures as parameters, but does not support
variables containing them, or any other first-class handling of them.
This avoids the upward funarg problem (as the Lispers call it). These
parameters consist of the code pointer and the static link pointer.

Modula-2 has nested procedures, and allows putting procedures in
variables, fields, etc., but eliminates the upward funarg problem by
only allowing to store global-level procedures in variables, not
nested procedures. So it went closer to C.

Oberon originally had nested procedures, and AFAIK similar rules to
Modula-2. When I asked Wirth in 2020 if he has a good example for the
use of nested procedures (I thought he would have, given that he kept
this feature for so many years), he told me that he had removed nested
functions in 2013 or so.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl wrote:

> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>I believe Pascal, back in the 1970s implemented nested functions, though
>>I don't know how any specific implementation accomplished it.

> AFAIK Pascal implementations all just use static links chains to the
> enclosing scopes. So you access an outer local by following the link
> chain as many levels as you cross scopes.

How does Pascal do this counting when there are recursive frames on
the stack ??

> Pascal allows passing
> nested functions/procedures as parameters, but does not support
> variables containing them, or any other first-class handling of them.
> This avoids the upward funarg problem (as the Lispers call it). These
> parameters consist of the code pointer and the static link pointer.

> Modula-2 has nested procedures, and allows putting procedures in
> variables, fields, etc., but eliminates the upward funarg problem by
> only allowing to store global-level procedures in variables, not
> nested procedures. So it went closer to C.

> Oberon originally had nested procedures, and AFAIK similar rules to
> Modula-2. When I asked Wirth in 2020 if he has a good example for the
> use of nested procedures (I thought he would have, given that he kept
> this feature for so many years), he told me that he had removed nested
> functions in 2013 or so.

> - anton

Scott Lurndal wrote:

> EricP <ThatWouldBeTelling@thevillage.com> writes:
>>MitchAlsup wrote:
>>>
>>
>>To support this view of virtual memory on that platform all OS's would
>>need to maintain two parallel page tables to map each P-space twice,
>>one for user mode and one for super mode.

> ARMv8 maps each half separately. There is a separate translation table
> for each half of the virtual address space, with the high-half holding
> the kernel code and data, and the low half holding the user portion.

> Each half has it's own translation table base register and each half
> can use a different asid.

> Context switch between processes simply requires reloading the
> table base register for the lower half (TTBR0_EL1). No other
> TLB maintainance is required unless the 16-bit ASID wraps.

Oddly enough; I did not know this until reading this paragraph--and
yet, I converged on apparently the same scheme.

mitchalsup@aol.com (MitchAlsup) writes:
>Anton Ertl wrote:
>
>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>I believe Pascal, back in the 1970s implemented nested functions, though
>>>I don't know how any specific implementation accomplished it.
>
>> AFAIK Pascal implementations all just use static links chains to the
>> enclosing scopes. So you access an outer local by following the link
>> chain as many levels as you cross scopes.
>
>How does Pascal do this counting when there are recursive frames on
>the stack ??

The static scope level is independent of recursion. Note that this
kind of implementation has a static link in addition to the dynamic
link.

E.g., consider

procedure a(...)
procedure b(...)
procedure c(...)
begin
b(...)
end;
begin
c(...);
end;
begin
b(...);
end;

After a few levels of recursion you have dynamic and static chains like this:

dynamic: c->b->c->b->c->b->a
static: --^--------------^

And upon the next call to b:

dynamic: b->c->b->c->b->c->b->a
static: --------------------^

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

EricP wrote:

> MitchAlsup wrote:
>> EricP wrote:
>>
>>> MitchAlsup wrote:
>>>> EricP wrote:
>>>>
>>>>>
>>>>> If one has super and User mode, and R,W,E enables, that's 6 PTE bits.
>>>>> The PTE is very cramped so there is a big incentive to save any bits.
>>>>> We can get that down to 3 PTE bits by throwing out the silly
>>>>> combinations,
>>>>> Write-only, Execute-only, Super:NoAccess+User:RWE,...
>>>>
>>>> If one uses a different page table for user and supervisor, you only
>>>> need those 3-bits. In my case Guest OS has its own table and its own
>>>> ASID completely separate from application. ASID plays the part of G
>>>> (global).
>>
>>> Ok but all major OS's view the current process address space (P-space)
>>> as directly addressable from system space (S-space), so the OS can reach
>>> directly into the current process to read or write memory to pass args
>>> to/from syscalls or deliver signals, etc.
>>
>> My 66000 provides this. Guest OS can reach down into application VaS,
>> application cannot reach up into Guest OS VaS. When Guest OS accesses
>> its own VaS it uses its own ASID, when accessing application it uses
>> application ASID. The same analogue occurs in Guest HV reaching down
>> into Guest OS VaS. When Guest HV accesses its own VaS it uses 1-level
>> translation and its own ASID; when accessing Guest OS it uses 2-level
>> translation and Guest OS ASID.
>>
>> Switching between levels is fast because all the required information
>> is loaded at all times. Switching contexts is fast because only 1
>> register needs to be written, the data is obtained as if the control
>> registers were a cache of the data at the written address.

> How does these two ASIDs allow 3 bits in a PTE to grant different
> access for the same page to user and OS? For example S:RW,U:RE

I was planning on ignoring access rights when a more privileged thread
accesses less privileged data.

>>> To support this view of virtual memory on that platform all OS's would
>>> need to maintain two parallel page tables to map each P-space twice,
>>> one for user mode and one for super mode.

Anton Ertl [2023-12-20 21:37:44] wrote:
> mitchalsup@aol.com (MitchAlsup) writes:
>>Anton Ertl wrote:
>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>>I believe Pascal, back in the 1970s implemented nested functions, though
>>>>I don't know how any specific implementation accomplished it.
>>> AFAIK Pascal implementations all just use static links chains to the
>>> enclosing scopes. So you access an outer local by following the link
>>> chain as many levels as you cross scopes.
>>How does Pascal do this counting when there are recursive frames on
>>the stack ??
> The static scope level is independent of recursion. Note that this
> kind of implementation has a static link in addition to the dynamic
> link.

Maybe I'm missing something but I think Pascal's display is "orthogonal"
to the issue discussed before of how to stuff together a code pointer
together with a pointer to its associated data.

Pascal's display is one possible representation of closures, but it
doesn't save you from the need to use a kind of "fat pointer" for the
first-class functions.

What saves Pascal is that first-class functions aren't first class at
all, so Pascal can safely and easily represent them any way it likes,
including as a pair of two values (a pointer to the code, and a pointer
to a stack frame, typically).

It's harder in C because some code wants to be able to convert
a function pointer to a `void*` and back, so you usually want to make it
fit into the size of a normal pointer.

Stefan

On 20/12/2023 23:26, Stefan Monnier wrote:
> Anton Ertl [2023-12-20 21:37:44] wrote:
>> mitchalsup@aol.com (MitchAlsup) writes:
>>> Anton Ertl wrote:
>>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>>> I believe Pascal, back in the 1970s implemented nested functions, though
>>>>> I don't know how any specific implementation accomplished it.
>>>> AFAIK Pascal implementations all just use static links chains to the
>>>> enclosing scopes. So you access an outer local by following the link
>>>> chain as many levels as you cross scopes.
>>> How does Pascal do this counting when there are recursive frames on
>>> the stack ??
>> The static scope level is independent of recursion. Note that this
>> kind of implementation has a static link in addition to the dynamic
>> link.
>
> Maybe I'm missing something but I think Pascal's display is "orthogonal"
> to the issue discussed before of how to stuff together a code pointer
> together with a pointer to its associated data.
>
> Pascal's display is one possible representation of closures, but it
> doesn't save you from the need to use a kind of "fat pointer" for the
> first-class functions.
>
> What saves Pascal is that first-class functions aren't first class at
> all, so Pascal can safely and easily represent them any way it likes,
> including as a pair of two values (a pointer to the code, and a pointer
> to a stack frame, typically).
>
> It's harder in C because some code wants to be able to convert
> a function pointer to a `void*` and back, so you usually want to make it
> fit into the size of a normal pointer.
>

Converting between function pointers and data pointers (like void*) is
undefined behaviour in C. Of course, some people want to do that
regardless, and on many platforms you can probably get away with it if
you are lucky. On some platforms, however, data pointers and function
pointers are different sizes. (There are even some platforms where
pointers to different types of data are different sizes.)

But you /are/ allowed to convert back and forth between different
function pointer types in C, which means function pointers are always
the same size. And for efficiency, that would generally be the smallest
size that works for normal functions - i.e., typically just the address
in memory of the function's code.

So what saves C is that nested functions are not part of the language!
And when you have extensions that support nested functions, such as
supported by gcc, if the function really needs a fat pointer you have a
trampoline on the stack to hide that and make it look like a normal
"thin" pointer.

mitchalsup@aol.com (MitchAlsup) writes:
>EricP wrote:
>
>> MitchAlsup wrote:
>>> EricP wrote:
>>>
>>>> MitchAlsup wrote:
>>>>> EricP wrote:
>>>>>
>>>>>>
>>>>>> If one has super and User mode, and R,W,E enables, that's 6 PTE bits.
>>>>>> The PTE is very cramped so there is a big incentive to save any bits.
>>>>>> We can get that down to 3 PTE bits by throwing out the silly
>>>>>> combinations,
>>>>>> Write-only, Execute-only, Super:NoAccess+User:RWE,...
>>>>>
>>>>> If one uses a different page table for user and supervisor, you only
>>>>> need those 3-bits. In my case Guest OS has its own table and its own
>>>>> ASID completely separate from application. ASID plays the part of G
>>>>> (global).
>>>
>>>> Ok but all major OS's view the current process address space (P-space)
>>>> as directly addressable from system space (S-space), so the OS can reach
>>>> directly into the current process to read or write memory to pass args
>>>> to/from syscalls or deliver signals, etc.
>>>
>>> My 66000 provides this. Guest OS can reach down into application VaS,
>>> application cannot reach up into Guest OS VaS. When Guest OS accesses
>>> its own VaS it uses its own ASID, when accessing application it uses
>>> application ASID. The same analogue occurs in Guest HV reaching down
>>> into Guest OS VaS. When Guest HV accesses its own VaS it uses 1-level
>>> translation and its own ASID; when accessing Guest OS it uses 2-level
>>> translation and Guest OS ASID.
>>>
>>> Switching between levels is fast because all the required information
>>> is loaded at all times. Switching contexts is fast because only 1
>>> register needs to be written, the data is obtained as if the control
>>> registers were a cache of the data at the written address.
>
>> How does these two ASIDs allow 3 bits in a PTE to grant different
>> access for the same page to user and OS? For example S:RW,U:RE
>
>I was planning on ignoring access rights when a more privileged thread
>accesses less privileged data.

ARMv8 has PAN (privileged access never) which can be used to prevent
access by privileged code to unprivileged code and data. The bit
(in the PSR) can be set and reset by the kernel, so the kernel will
explicitly reset it when accessing user data, and set it otherwise.

If the kernel accesses nonprivileged data while PAN is set, it will fault.

https://developer.arm.com/documentation/102376/0100/Permissions-attributes

On Wed, 20 Dec 2023 21:09:44 +0000, mitchalsup@aol.com (MitchAlsup)
wrote:

>Anton Ertl wrote:
>
>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>I believe Pascal, back in the 1970s implemented nested functions, though
>>>I don't know how any specific implementation accomplished it.
>
>> AFAIK Pascal implementations all just use static links chains to the
>> enclosing scopes.

@Anton: implementation dependent - some use displays instead.

>So you access an outer local by following the link
>> chain as many levels as you cross scopes.
>
>How does Pascal do this counting when there are recursive frames on
>the stack ??

To access non-local, non-global things (variables, functions, etc.)
nested functions require that the definition scopes be tracked through
the chain of function calls.

To this end there are 2 different kinds of links: by convention
referred to as 'static' and 'dynamic'.

dynamic = who called who
static = who defined who

The stack frame in a language - such as Pascal - having nested
functions contains both kinds of links. The dynamic link is the same
as in C: it just points to the immediate caller. The static link,
however, points to the last created frame of the function that
/defined/ the currently executing function.

[view with a fixed width font]

Expanding a bit on Anton's example, consider:

A defines B and C
B defines D
C defines E

A runs
A calls B
B calls D
D calls C
C calls E
E calls E
E calls A
A calls B
B calls D
D calls B

dynamic: A <- B <- D <- C <- E <- E <- A <- B <- D <- B
static : ^
: ^-----
: ^-----
: ^---------------
: ^-----
: ^----------
: ^
: ^-----
: ^-----
: ^---------------

You can see the dynamic links simply reflect the call chain. The
static links however, jump around and appear to form multiple chains.

The top level function A has no enclosing scope, so its static link is
to self. However, B, C, D and E all can access things defined in
enclosing scopes by following the chain of static links: e.g., a D
instance has a link to the last B instance, and that B instance has a
link to the last A instance.

Obviously there has to be a way to FIND the last instance of a scope
as it may be deep in the stack. The /simplest/ way is to mark each
frame with a small integer identifying their static nest level: e.g.,
A = 1, B = 2, C = 2, D = 3, E = 3

A 'display' is another way to implement non-local, non-global access
which uses an array of frame pointers rather than a 'chain' of static
links woven through the stack frames. Accessing an enclosing scope is
simply an indirection through display[target scope].

When entering a function at nest level N, the value of display[N] is
saved in the frame and display[N] set to point to the last instance of
the enclosing level N-1 frame. Exiting the function, display[N] is
restored from the saved value.

This makes /maintaining/ a display a bit most costly than using static
links - ie. a static link can simply be abandoned. However, if there
is significant use of things from multiple deep scopes [where 'deep'
is 2 or more scopes away], the display will be faster to use.

Only display elements at or (numerically) lower than the nest level of
the current function can (legally) be used - e.g., a function at level
3 can use display[1] .. display[3], whereas using display[4] or higher
would constiture an error.

So, assuming the same example as above:

A defines B and C
B defines D
C defines E

display[ 1 2 3 4 5 6 ]
A runs [ A . . . . . ] L = 1
A calls B [ A A . . . . ] L = 2
B calls D [ A A B . . . ] L = 3
D calls C [ A A b . . . ] L = 2
C calls E [ A A C . . . ] L = 3
E calls E [ A A C . . . ] L = 3
E calls A [ A a c . . . ] L = 1
A calls B [ A A c . . . ] L = 2
B calls D [ A A B . . . ] L = 3
D calls B [ A A b . . . ] L = 2

'L' indicates the current run level (after the call). Display values
at nest levels greater than the current run level are shown as
lowercase: they ARE still in the array, but (theoretically) are not
accessible from the currently running function.

Although it sort of /looks/ like the display is a stack, the elements
at indices greater than the current nest level still are in the array
and MAY still have meaning.

Unfortunately, there is a limit to how complex an example can be shown
here ... a far more complicated example would be required to show
saving and restoring values.

Using displays also interacts with threading: the display is part of
the thread state. However, thread local storage works fine for this -
in use displays tend to be cached quite effectively and so there is
little or no need for special hardware to handle them.

You might ask "who makes multiple deep accesses to different frames?"
That's a fair question to which I don't have a good answer. Displays
fell out of favor ... not because they were troublesome, but rather
because better compilation methods were developed to turn nested
functions into flat closures (which could be in heap or on stack) and
these mostly removed the need for either displays or static links.

YMMV.

>> Pascal allows passing
>> nested functions/procedures as parameters, but does not support
>> variables containing them

@Anton: again, implementation dependent. Standard Pascal (ISO and
ANSI) does not recognize 'function pointer' variables, but some
extended Pascals did.

>> , or any other first-class handling of them.
>> This avoids the upward funarg problem (as the Lispers call it). These
>> parameters consist of the code pointer and the static link pointer.

Yes, in Standard Pascal you could only call functions defined at the
same nesting level or in an enclosing levels WITHIN THE SAME SCOPE
CHAIN. In the example above E couldn't call D because their
definition scopes are disjoint.

However, again, some extended Pascals did allow cross scope calls
using pointers provided the caller and callee both were within a
common enclosing scope. IOW there were implementations in which you
could create a pointer to E in A and then call E from D.

>> Modula-2 has nested procedures, and allows putting procedures in
>> variables, fields, etc., but eliminates the upward funarg problem by
>> only allowing to store global-level procedures in variables, not
>> nested procedures. So it went closer to C.
>
>> Oberon originally had nested procedures, and AFAIK similar rules to
>> Modula-2. When I asked Wirth in 2020 if he has a good example for the
>> use of nested procedures (I thought he would have, given that he kept
>> this feature for so many years), he told me that he had removed nested
>> functions in 2013 or so.

Yes, for complex code, simple nested functions often are inadequate
and you need (not necessarily 'first-class' but) persistent closures.

[Consider that closures in Lisp really are 2nd class because they must
be bound to a symbol in order to be stored/persisted. In Scheme where
they ARE 1st class, they can be stored and passed around - including
upward - just like any other value.]

>> - anton

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>Anton Ertl [2023-12-20 21:37:44] wrote:
>> mitchalsup@aol.com (MitchAlsup) writes:
>>>Anton Ertl wrote:
>>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>>>I believe Pascal, back in the 1970s implemented nested functions, though
>>>>>I don't know how any specific implementation accomplished it.
>>>> AFAIK Pascal implementations all just use static links chains to the
>>>> enclosing scopes. So you access an outer local by following the link
>>>> chain as many levels as you cross scopes.
>>>How does Pascal do this counting when there are recursive frames on
>>>the stack ??
>> The static scope level is independent of recursion. Note that this
>> kind of implementation has a static link in addition to the dynamic
>> link.
>
>Maybe I'm missing something but I think Pascal's display is "orthogonal"
>to the issue discussed before of how to stuff together a code pointer
>together with a pointer to its associated data.

Certainly. For example, AFAIK Pascal implementations do not use a
display, but just follows static links (but maybe somebody with more
knowledge can correct me). Cohen [cohen91] described how to use a
display for type inclusion tests. IIRC Wirth wrote a letter in reply
where he stated that he had tried to use a display for accessing outer
locals around 1970, but found that it hurt performance, and that he
was happy that this technique was useful for something after all.

@Article{cohen91,
author = "Norman H. Cohen",
title = "Type-Extension Type Tests Can Be Performed In Constant
Time",
journal = "ACM Transactions on Programming Languages and
Systems",
volume = "13",
number = "4",
pages = "626--629",
month = oct,
year = "1991",
refs = "2",
checked = "19940624",
source = "Dept. Library",
keywords = "class, descriptor, display, extensible data type,
inheritance, membership test, object-oriented
programming, type extension, type test",
note = "Technical Correspondence",
abstract = "Wirth's proposal for type extensions includes an
algorithm for determining whether a give value belongs
to an extension of a given type. In the worst case,
this algorithm takes time proportional to the depth of
the type-extension hierarchy. Wirth describes the loop
in this algorithm as ``unavoidable,'' but in fact, the
test can be performed in constant time by associating a
``display'' of base types with each type descriptor.",
xref = "Wirth:acm:toplas:1988",
reffrom = "Corney:Gough:plasa:1994",
}

>Pascal's display is one possible representation of closures, but it
>doesn't save you from the need to use a kind of "fat pointer" for the
>first-class functions.

Correct.

>What saves Pascal is that first-class functions aren't first class at
>all, so Pascal can safely and easily represent them any way it likes,
>including as a pair of two values (a pointer to the code, and a pointer
>to a stack frame, typically).

Even first-class closures are not a problem. The easiest way is to
let them be a type of two machine words, a code pointer and an
environment pointer.

>It's harder in C because some code wants to be able to convert
>a function pointer to a `void*` and back, so you usually want to make it
>fit into the size of a normal pointer.

Even first class closures that are represented in one machine word are
not a problem. Just box the two words and pass a pointer to that box.

The problem is an ABI that passes function pointers as code pointers
and where calling a function pointer performs an indirect call to the
passed pointer. I.e., a typical C ABI.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Niklas Holsti wrote:
> On 2023-12-20 0:37, MitchAlsup wrote:
>> Thomas Koenig wrote:
>>
>>> Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
>>
>>>>> E.g., consider a numerical integration function integrate(f,lo,hi),
>>>>> which expects a function with one parameter f(x), and you want to
>>>>> integrate x^y (pow(x,y) in C), where y is, say, passed as parameter.
>>>>
>>>>
>>>> That is the canonical example, yes. But it happens I have never
>>>> needed to do numerical integration in my Ada programs. I do have
>>>> some cases where I have used locally instantiated generics with
>>>> generic function parameters in the way I described above. In Ada the
>>>> integration example would be declared thusly:
>>>>
>>>>     generic
>>>>        with function F (X : Float) return Float;
>>>>     function Integrate (Lo, Hi : Float) return Float;
>>>>
>>>> although one would usually not limit it to a specific number type
>>>> such as Float, but would make this type also a generic (type)
>>>> parameter. IIRC, the ability to define numerical integration as a
>>>> generic subprogram, with the function to be integrated as a generic
>>>> parameter, was one of the reasons presented for omitting function
>>>> pointers entirely from original Ada (Ada 83).
>>
>>> Interesting, thanks!
>>
>>> Just one remark: Making numerical routines generic can be a bit
>>> problematic if constants depend on the accuracy of a type; things
>>> like tolerances for checks for convergence,
>>
>> whether compiler constant arithmetic has the same numeric properties
>> as compiled code instruction sequences,
>
>
> Ada compilers are required to evaluate typeless constant arithmetic to
> unbounded precision (as "bignums"). For example, the constant pi is
> defined thusly in the standard package Ada.Numerics:
>
>     Pi : constant :>        3.14159_26535_89793_23846_26433_83279_50288_41971_69399_37511;
>
> and all the digits are significant in any computation involving Pi and
> other typeless constants.
>
> Computation with typed constants is required to use the operations of
> that type, so should match what the target code does.
>
And still, 50 digits is only ~170 bits, so not enough to do arbitrary
parameter reductions (which requires ~1100 bits).

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

David Brown <david.brown@hesbynett.no> schrieb:

> So what saves C is that nested functions are not part of the language!
> And when you have extensions that support nested functions, such as
> supported by gcc, if the function really needs a fat pointer you have a
> trampoline on the stack to hide that and make it look like a normal
> "thin" pointer.

I looked at what the Fortran compilers I could lay my hands on did
with the following code, which uses a contained subroutine inside
a subroutine:

module test
contains
subroutine t(f)
interface
subroutine f()
end subroutine
end interface
call f()
end subroutine
end module

subroutine foo(i)
use test
integer, intent(inout):: i
call t(bar)
contains
subroutine bar()
call xxx(i)
end
end

Interestingly, every compiler I could lay my hands on on short
notice (gfortran for several architectures, ifort, xlf, the new
flang for llvm) used trampolines.

See https://godbolt.org/z/nv5nr934q , which is for POWER and
contains a call to a subroutine suggestively called
__trampoline_setup.

On Wed, 20 Dec 2023 23:51:40 +0100
David Brown <david.brown@hesbynett.no> wrote:

> On 20/12/2023 23:26, Stefan Monnier wrote:
> > Anton Ertl [2023-12-20 21:37:44] wrote:
> >> mitchalsup@aol.com (MitchAlsup) writes:
> >>> Anton Ertl wrote:
> >>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
> >>>>> I believe Pascal, back in the 1970s implemented nested
> >>>>> functions, though I don't know how any specific implementation
> >>>>> accomplished it.
> >>>> AFAIK Pascal implementations all just use static links chains to
> >>>> the enclosing scopes. So you access an outer local by following
> >>>> the link chain as many levels as you cross scopes.
> >>> How does Pascal do this counting when there are recursive frames
> >>> on the stack ??
> >> The static scope level is independent of recursion. Note that this
> >> kind of implementation has a static link in addition to the dynamic
> >> link.
> >
> > Maybe I'm missing something but I think Pascal's display is
> > "orthogonal" to the issue discussed before of how to stuff together
> > a code pointer together with a pointer to its associated data.
> >
> > Pascal's display is one possible representation of closures, but it
> > doesn't save you from the need to use a kind of "fat pointer" for
> > the first-class functions.
> >
> > What saves Pascal is that first-class functions aren't first class
> > at all, so Pascal can safely and easily represent them any way it
> > likes, including as a pair of two values (a pointer to the code,
> > and a pointer to a stack frame, typically).
> >
> > It's harder in C because some code wants to be able to convert
> > a function pointer to a `void*` and back, so you usually want to
> > make it fit into the size of a normal pointer.
> >
>
> Converting between function pointers and data pointers (like void*)
> is undefined behaviour in C. Of course, some people want to do that
> regardless, and on many platforms you can probably get away with it
> if you are lucky.

On both leading general-purpose computing platforms, i.e. on Windows and
on Posix-compatibles, you don't have to be lucky: this type of
conversion is guaranteed to work. Period. In both cases it is an
integral part of dynamic linking APIs.

> On some platforms, however, data pointers and
> function pointers are different sizes. (There are even some
> platforms where pointers to different types of data are different
> sizes.)
>
> But you /are/ allowed to convert back and forth between different
> function pointer types in C, which means function pointers are always
> the same size. And for efficiency, that would generally be the
> smallest size that works for normal functions - i.e., typically just
> the address in memory of the function's code.
>
> So what saves C is that nested functions are not part of the
> language! And when you have extensions that support nested functions,
> such as supported by gcc, if the function really needs a fat pointer
> you have a trampoline on the stack to hide that and make it look like
> a normal "thin" pointer.
>
>

On 21/12/2023 14:22, Michael S wrote:
> On Wed, 20 Dec 2023 23:51:40 +0100
> David Brown <david.brown@hesbynett.no> wrote:
>
>> On 20/12/2023 23:26, Stefan Monnier wrote:
>>> Anton Ertl [2023-12-20 21:37:44] wrote:
>>>> mitchalsup@aol.com (MitchAlsup) writes:
>>>>> Anton Ertl wrote:
>>>>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>>>>> I believe Pascal, back in the 1970s implemented nested
>>>>>>> functions, though I don't know how any specific implementation
>>>>>>> accomplished it.
>>>>>> AFAIK Pascal implementations all just use static links chains to
>>>>>> the enclosing scopes. So you access an outer local by following
>>>>>> the link chain as many levels as you cross scopes.
>>>>> How does Pascal do this counting when there are recursive frames
>>>>> on the stack ??
>>>> The static scope level is independent of recursion. Note that this
>>>> kind of implementation has a static link in addition to the dynamic
>>>> link.
>>>
>>> Maybe I'm missing something but I think Pascal's display is
>>> "orthogonal" to the issue discussed before of how to stuff together
>>> a code pointer together with a pointer to its associated data.
>>>
>>> Pascal's display is one possible representation of closures, but it
>>> doesn't save you from the need to use a kind of "fat pointer" for
>>> the first-class functions.
>>>
>>> What saves Pascal is that first-class functions aren't first class
>>> at all, so Pascal can safely and easily represent them any way it
>>> likes, including as a pair of two values (a pointer to the code,
>>> and a pointer to a stack frame, typically).
>>>
>>> It's harder in C because some code wants to be able to convert
>>> a function pointer to a `void*` and back, so you usually want to
>>> make it fit into the size of a normal pointer.
>>>
>>
>> Converting between function pointers and data pointers (like void*)
>> is undefined behaviour in C. Of course, some people want to do that
>> regardless, and on many platforms you can probably get away with it
>> if you are lucky.
>
> On both leading general-purpose computing platforms, i.e. on Windows and
> on Posix-compatibles, you don't have to be lucky: this type of
> conversion is guaranteed to work. Period. In both cases it is an
> integral part of dynamic linking APIs.

Nope.

POSIX requires that an object of type "void *" can hold a pointer to a
function. But it does not require that a conversion between a function
and a data pointer is defined. Not only is this code not guaranteed to
have defined behaviour or work as you might expect, but a conforming C
compiler is obliged to issue a diagnostic about it:

void (*foo)(void);

foo = (void (*)(void) dlsym(handle, "foo");

What /does/ work, for any POSIX system, is:

*(void ** )(&foo) = dlsym(handle, "foo");

<https://pubs.opengroup.org/onlinepubs/009696899/functions/dlsym.html>

Note that having the same size - and even the same representation - is
not all that is needed for things to work as naïvely as you might assume
in C.

And of course, the C world is vastly greater than just the "leading
general-purpose computing platforms", and it includes targets where
function pointers and data pointers are significantly different. Some
platforms (including quite popular ones in their day, like DOS) support
different memory models where data and code pointers can be big and
flexible or small and efficient. Things that work on one platform might
not work on others. The C language - defined by the standards - gives a
common subset. If you are writing in C, and you have not specified a
particular target but you rely on target-specific features, your code
relies on luck.

>
>> On some platforms, however, data pointers and
>> function pointers are different sizes. (There are even some
>> platforms where pointers to different types of data are different
>> sizes.)
>>
>> But you /are/ allowed to convert back and forth between different
>> function pointer types in C, which means function pointers are always
>> the same size. And for efficiency, that would generally be the
>> smallest size that works for normal functions - i.e., typically just
>> the address in memory of the function's code.
>>
>> So what saves C is that nested functions are not part of the
>> language! And when you have extensions that support nested functions,
>> such as supported by gcc, if the function really needs a fat pointer
>> you have a trampoline on the stack to hide that and make it look like
>> a normal "thin" pointer.
>>
>>
>
>