On 2023-12-21 14:29, Terje Mathisen wrote:
> Niklas Holsti wrote:

[snip]

>> 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.

[snip]

> And still, 50 digits is only ~170 bits, so not enough to do arbitrary
> parameter reductions (which requires ~1100 bits).

Ada compilers are explicitly allowed to define Ada.Numerics.Pi with more
digits if they want to do so (which sort of introduces a portability
problem, oops...)

I believe they are also allowed to use a more precise approximation of
pi in the numerical library functions.

Thomas Koenig wrote:
> 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.

BTW this requires a RWE stack.
The x64 gfortran is considerably simpler.
It stuffs two MOV reg,imm and a CALL instructions on the stack at RSP+8,
copies RSP+8 to RDI, calls test_MOD which jumps to RDI.

bar.0:
mov rdi, QWORD PTR [r10]
jmp xxx_
__test_MOD_t:
jmp rdi
foo_:
sub rsp, 56
mov edx, -17599 // REX MOV reg,imm
mov ecx, -17847 // REX MOV reg,imm
mov QWORD PTR [rsp], rdi
lea rdi, [rsp+8]
mov WORD PTR [rsp+8], dx
mov edx, OFFSET FLAT:bar.0
mov QWORD PTR [rsp+40], 0
mov DWORD PTR [rsp+10], edx
mov WORD PTR [rsp+14], cx
mov QWORD PTR [rsp+16], rsp
mov DWORD PTR [rsp+24], -1864106167 // REX CALL
call __test_MOD_t
add rsp, 56
ret

EricP wrote:

> Thomas Koenig wrote:
>> 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.

> BTW this requires a RWE stack.
> The x64 gfortran is considerably simpler.
> It stuffs two MOV reg,imm and a CALL instructions on the stack at RSP+8,
> copies RSP+8 to RDI, calls test_MOD which jumps to RDI.

> bar.0:
> mov rdi, QWORD PTR [r10]

Where is R10 made to point at i ??

> jmp xxx_
> __test_MOD_t:
> jmp rdi
> foo_:
> sub rsp, 56
> mov edx, -17599 // REX MOV reg,imm
> mov ecx, -17847 // REX MOV reg,imm
> mov QWORD PTR [rsp], rdi
> lea rdi, [rsp+8]
> mov WORD PTR [rsp+8], dx
> mov edx, OFFSET FLAT:bar.0
> mov QWORD PTR [rsp+40], 0
> mov DWORD PTR [rsp+10], edx
> mov WORD PTR [rsp+14], cx
> mov QWORD PTR [rsp+16], rsp
> mov DWORD PTR [rsp+24], -1864106167 // REX CALL
> call __test_MOD_t
> add rsp, 56
> ret

MitchAlsup wrote:
> EricP wrote:
>
>> Thomas Koenig wrote:
>>> 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.
>
>> BTW this requires a RWE stack.
>> The x64 gfortran is considerably simpler.
>> It stuffs two MOV reg,imm and a CALL instructions on the stack at RSP+8,
>> copies RSP+8 to RDI, calls test_MOD which jumps to RDI.
>
>> bar.0:
>> mov rdi, QWORD PTR [r10]
>
> Where is R10 made to point at i ??
>
>> jmp xxx_
>> __test_MOD_t:
>> jmp rdi
>> foo_:
>> sub rsp, 56
>> mov edx, -17599 // REX MOV reg,imm
>> mov ecx, -17847 // REX MOV reg,imm
>> mov QWORD PTR [rsp], rdi
>> lea rdi, [rsp+8]
>> mov WORD PTR [rsp+8], dx
>> mov edx, OFFSET FLAT:bar.0
>> mov QWORD PTR [rsp+40], 0
>> mov DWORD PTR [rsp+10], edx
>> mov WORD PTR [rsp+14], cx
>> mov QWORD PTR [rsp+16], rsp
>> mov DWORD PTR [rsp+24], -1864106167 // REX CALL
>> call __test_MOD_t
>> add rsp, 56
>> ret

-17847 = BA4A = REX.WX MOV r10,imm64
mov QWORD PTR [rsp],rdi copies i in rdi to the bottom of stack [RSP].
mov WORD PTR [rsp+14],cx stuffs REX.WX MOV r10,imm64 onto stack
mov QWORD PTR [rsp+16],rsp copies RSP onto stack after REX.WX MOV, r10,imm64

At execution REX.WX MOV r10,imm64 loads prior rsp that points to i into r10
bar.0:
mov rdi, QWORD PTR [r10] loads i into rdi

Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
> 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.

It would be interesting to see how Ada compilers handle nested
functions. Would it be possible to create an Ada equivalent
of https://godbolt.org/z/e5cr9EoE3 (I hope the syntax is clear)
and post it?

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 ??

There are two kind of frame links: the dynamic links point just to the frame of
the caller, the static link to the lexically enclosing frame.

Something like (in a C-like syntax with nested function):

void f() {
int fv;

void f1() {
use(fv);
}

void f2() {
int f2v;

void f2a(int r) {
if (r != 0) {
f2a(r-1);
}
f1();
fv += 42;
f2v += 36;
}

f2a(3);

}
}

would be translated as (in a C-like syntax without nested function and with
the dynamic link handled by the C compiler if one is needed):

struct __f_frame {
int fv;
};

struct __f2_frame {
struct __f_frame* parent;
int f2v;
}

void f1(struct __f_frame* parent) {
use(parent->fv);
}

void f2a(struct __f2_frame* parent, int r) {
if (r != 0) {
f2a(parent, r-1);
}
f1(parent->parent);
parent->parent->fv += 42;
parent->f2v += 36;
}

void f2(struct __f_frame* parent) {
struct __f2_frame local_frame;
local_frame.parent = parent;
f2a(&local_frame, 3);
}

void f() {
struct __f_frame local_frame;
f2(&local_frame);
}

Yours,

--
Jean-Marc

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

[...]

> 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.

There is a significant benefit to well-done nested functions, where
well-done means full closures, syntactically lightweight, and
allowing an anonymous expressional form, often called a lambda:
the ability to define first-class control structures in the
language, rather than needing control structures built into the
language. See for example blocks in Smalltalk.

On Fri, 15 Dec 2023 14:30:25 +0000, Quadibloc wrote:

> Is the CPU even the place for sandboxing? A genuinely effective sandbox
> would involve a physical separation between the protected computer and
> the one connected to the Internet, after all. But that isn't
> convenient...

In a different thread, I've finally fleshed this out.

One has the "real" computer, which is built for speed, and which may
therefore have some limitations to its security. So that computer isn't
connected directly to the Internet.

But it controls a subordinate computer which does connect to the Internet.

That computer should be completely unable to write to the only memory it
is capable of loading executable code from. Instead, its parent, the real
computer, loads all executable code into that memory.

This scheme was used by the old Bell system Electronic Switching System,
and I think that it produces pretty good security.

That computer would then have a subordinate computer of its own. This
third computer is used to run things like the implementation of JavaScript
with a just-in-time compiler. It uses 486-style tecnology; that is, its
an in-order processor (no Spectre) running slowly enough that its DRAM
is not subject to Rowhammer.

So a malicious web site would have to execute vulnerabilities created by
software bugs inside the third computer, and these would presumably ge
gradually eliminated as attacks are detected. It wouldn't have the
hardware vulnerabilities which are difficult to get rid of to use.

And then, in order to get at the hard drives of the computer, it would have
to attack the "real" computer at the top level. But between it and that is
a computer with zero ability to execute code that it can write or modify.

To me, that seems like a desert that malware can't cross. (A vulerability
could be created, of course, if the second computer was allowed to execute
external programs by means of an _interpreter_ instead of a just-in-time
compiler. So making interpreters available within the secondary computer
that talks to the Internet must be recognized as a practice to avoid.)

John Savard

Tim Rentsch wrote:

> There is a significant benefit to well-done nested functions, where
> well-done means full closures, syntactically lightweight, and
> allowing an anonymous expressional form, often called a lambda:
> the ability to define first-class control structures in the
> language, rather than needing control structures built into the
> language. See for example blocks in Smalltalk.

How do pointers to nested functions interact with try-throw-catch ??

Do you use the stack as it is now ?? or how it was when the closure was
constructed ??

According to MitchAlsup <mitchalsup@aol.com>:
>Tim Rentsch wrote:
>
>> There is a significant benefit to well-done nested functions, where
>> well-done means full closures, ...

>How do pointers to nested functions interact with try-throw-catch ??
>
>Do you use the stack as it is now ?? or how it was when the closure was
>constructed ??

The usual answer is that you unwind the stack to its state at try, and
if you then call something that uses stack frames below that, you
lose.

Or you can do spaghetti stacks, where the stack can be forked and you
keep all the frames around that might be reactivated. See Scheme and
Smalltalk.

--
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 MitchAlsup <mitchalsup@aol.com>:
>>Tim Rentsch wrote:
>>
>>> There is a significant benefit to well-done nested functions, where
>>> well-done means full closures, ...

>>How do pointers to nested functions interact with try-throw-catch ??
>>
>>Do you use the stack as it is now ?? or how it was when the closure was
>>constructed ??

> The usual answer is that you unwind the stack to its state at try, and
> if you then call something that uses stack frames below that, you
> lose.

> Or you can do spaghetti stacks, where the stack can be forked and you
> keep all the frames around that might be reactivated. See Scheme and
> Smalltalk.

Thanks.

mitchalsup@aol.com (MitchAlsup) writes:

> Tim Rentsch wrote:
>
>> There is a significant benefit to well-done nested functions, where
>> well-done means full closures, syntactically lightweight, and
>> allowing an anonymous expressional form, often called a lambda:
>> the ability to define first-class control structures in the
>> language, rather than needing control structures built into the
>> language. See for example blocks in Smalltalk.
>
> How do pointers to nested functions interact with try-throw-catch ??
>
> Do you use the stack as it is now ?? or how it was when the closure was
> constructed ??

I see you got your question answered. That's good.

Note that Smalltalk doesn't have exceptions built into the
language. When exceptions were added to the Smalltalk
environment, no changes were needed to the language or
the VM - just defining some methods in the right places.

John Levine <johnl@taugh.com> writes:
>According to MitchAlsup <mitchalsup@aol.com>:
>>Tim Rentsch wrote:
>>
>>> There is a significant benefit to well-done nested functions, where
>>> well-done means full closures, ...
>
>>How do pointers to nested functions interact with try-throw-catch ??
>>
>>Do you use the stack as it is now ?? or how it was when the closure was
>>constructed ??
>
>The usual answer is that you unwind the stack to its state at try, and
>if you then call something that uses stack frames below that, you
>lose.

It's not clear to me what you mean with "below", but anyway:

In the usual exception-handling variant (as exists in, e.g., Java)
where you cannot continue at the throwing site, you just restore
setup, including the stack pointer and the frame pointer (and thus
the static and the dynamic link) to what it was at the "try". The
same holds for Pascal's goto to a label in a statically surrounding
procedure; the more usual exception mechanisms find the try-catch
block dynamically, but that makes no difference after the target of
the throw has been determined.

If the static link was invalid after the "try", it was invalid before
the "try", too; many languages and their implementations are designed
to avoid that, either by preventing closures that live after the
procedure that created them has finished (e.g., Pascal and Modula-2),
or by keeping such closures in garbage-collected memory rather than
the stack (e.g., Scheme).

>Or you can do spaghetti stacks, where the stack can be forked and you
>keep all the frames around that might be reactivated. See Scheme and
>Smalltalk.

From the viewpoint of what to do that's pretty similar to the case
above: if the catch block can decide to continue at the throwing
place, before entering the catch block, the frame pointer is restored
to where it was at the "try", but the stack pointer is not. If the
catch block decides to continue at the throw, the frame pointer (and
the stack pointer, if changed in the meantime) is restored to the
value at the throw; If the catch block decides to continue after the
catch block, the stack pointer is restored to the depth at the "try".

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

On Thu, 04 Jan 2024 08:17:05 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

>John Levine <johnl@taugh.com> writes:
>>According to MitchAlsup <mitchalsup@aol.com>:
>>>Tim Rentsch wrote:
>>>
>>>> There is a significant benefit to well-done nested functions, where
>>>> well-done means full closures, ...
>>
>>>How do pointers to nested functions interact with try-throw-catch ??
>>>
>>>Do you use the stack as it is now ?? or how it was when the closure was
>>>constructed ??
>>
>>The usual answer is that you unwind the stack to its state at try, and
>>if you then call something that uses stack frames below that, you
>>lose.
>
>It's not clear to me what you mean with "below", but anyway:

Functions defined in scopes enclosed by the function containing the
"try".

The stack POV is reversed: the frame for function containing the "try"
would be lower in the stack, and frames for any enclosed functions
would be higher (closer to the top) in the stack.

>In the usual exception-handling variant (as exists in, e.g., Java)
>where you cannot continue at the throwing site, you just restore
>setup, including the stack pointer and the frame pointer (and thus
>the static and the dynamic link) to what it was at the "try". The
>same holds for Pascal's goto to a label in a statically surrounding
>procedure; the more usual exception mechanisms find the try-catch
>block dynamically, but that makes no difference after the target of
>the throw has been determined.

But that won't necessarily work in a language like Scheme where a
saved closure might use functions enclosed by the "try".
[Depends on the implementation of closures.]

>If the static link was invalid after the "try", it was invalid before
>the "try", too; many languages and their implementations are designed
>to avoid that, either by preventing closures that live after the
>procedure that created them has finished (e.g., Pascal and Modula-2),
>or by keeping such closures in garbage-collected memory rather than
>the stack (e.g., Scheme).

The static link is not invalid after the try - but it MAY become
invalid after a throw.

>>Or you can do spaghetti stacks, where the stack can be forked and you
>>keep all the frames around that might be reactivated. See Scheme and
>>Smalltalk.

As John mentioned, one possible implementation of closures is to
preserve the stack frames that are referenced [note: not necessarily
the whole call chain - just the referenced scope chain]. Static links
within the preserved chain of frames would remain valid.

>From the viewpoint of what to do that's pretty similar to the case
>above: if the catch block can decide to continue at the throwing
>place, before entering the catch block, the frame pointer is restored
>to where it was at the "try", but the stack pointer is not. If the
>catch block decides to continue at the throw, the frame pointer (and
>the stack pointer, if changed in the meantime) is restored to the
>value at the throw; If the catch block decides to continue after the
>catch block, the stack pointer is restored to the depth at the "try".

Microsoft's Structured Exception Handling (SEH) includes the ability
to continue from the exception point.

Lisp exceptions include the ability to continue from multiple
(re-entry) points following the throw.

>- anton

On 12/21/2023 12:41 AM, Anton Ertl wrote:
> 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.
>

In my case, I have function pointers as narrow code pointers, and also
closures (as a C language extension), which look just like normal
function pointers.

Though the current implementation is that a closure is a pointer to a
blob of machine code that loads its own address into a designated
register and then branches to the actual entry point for the function
(with the captured bindings for the closure following the machine-code
blob).

Granted, this implementation still favors non-closure function pointers
as the default case.

At present, this was implemented by having a mechanism to allocate RWE
memory objects (via one of the special case values passed to
"_malloc_cat()").

> - anton