Pascal Calling Convention

Pascal Calling Convention

[Shark8]

I was looking around for a way to use the Pascal calling convention in
GNAT; particularly because I thought it might be nice to do the GUI-
stuff in good old Delphi 5 and the application itself in Ada. All
easily doable via DLL or, possibly, through the $L compiler directive
which specifies a .obj file to link to.

-- I found a utility to convert between .o and .obj; so that's not a
problem. Though if someone knows a way to
-- have GNAT emit .obj files instead of .o I'd like to hear it.

The problem comes with the conventions... I'd like to be able to
interface w/o using stdcall or cdecl calling convention and directly
use the Pascal calling convention within my Ada texts. According to
this page ( http://gcc.gnu.org/onlinedocs/gnat_ugn_unw/Stdcall-Calling-Convention.html
) the STDCALL convention *is* the Pascal calling convention; both are
callee clean-up of the stack however, according to wikipedia (and
http://www.swissdelphicenter.ch/torry/showcode.php?id=1233 ) there is
a difference: left-to-right vs. right-to-left parameter passing.

This could also be a good nugget of information if I decide to use BP7
to write an OS loader & runtime for that OS; I had an OS written in
BP7 to the point where it could display a command-line, read
[keyboard] commands, and change the display-mode... when trying to
port that code to Ada apparently it failed to load properly due to the
non-existent runtime's requirement.
{True, it would be limited to 32-bits; but there isn't going to be a
shortage of 32-bit CPUs for a while.}

Re: Pascal Calling Convention

[Yannick Duchêne (Hibou57)]

Hello Shark,

Le Wed, 23 Mar 2011 22:37:55 +0100, Shark8 <onewingedshark@gmail.com> a  
écrit:
> I was looking around for a way to use the Pascal calling convention in
> GNAT; particularly because I thought it might be nice to do the GUI-
> stuff in good old Delphi 5 and the application itself in Ada. All
> easily doable via DLL or, possibly, through the $L compiler directive
> which specifies a .obj file to link to.
>
> -- I found a utility to convert between .o and .obj; so that's not a
> problem. Though if someone knows a way to
> -- have GNAT emit .obj files instead of .o I'd like to hear it.
You should not ask for GNAT to do it, rather to GNU ld which GNAT relies  
on (it does not have an internal linker). GNU ld does not support MS  
Windows object file format, as far as I know (the only Windows specific  
format it supports, it the one for compiled resource files data).

> The problem comes with the conventions... I'd like to be able to
> interface w/o using stdcall or cdecl calling convention and directly
> use the Pascal calling convention within my Ada texts. According to
> this page (  
> http://gcc.gnu.org/onlinedocs/gnat_ugn_unw/Stdcall-Calling-Convention.html
> ) the STDCALL convention *is* the Pascal calling convention; both are
> callee clean-up of the stack however, according to wikipedia (and
> http://www.swissdelphicenter.ch/torry/showcode.php?id=1233 ) there is
> a difference: left-to-right vs. right-to-left parameter passing.
As Delphi is Windows only, I suppose you want the Windows API calling  
convention (tell me if I'm wrong). On Windows, this is 1) Parameters  
pushed from right to left : like C 1) The callee clean the stack : like  
Pascal. This is not the same as the Pascal calling convention, which push  
parameters from left to right. I believe GNU docs is wrong here, when it  
says the Pascal calling convention is the calling convention for Windows  
API (wrong on both sides).

I never owned a Delphi compiler, so I could not tell for Delphi proper  
object files.

> This could also be a good nugget of information if I decide to use BP7
> to write an OS loader & runtime for that OS; I had an OS written in
> BP7 to the point where it could display a command-line, read
> [keyboard] commands, and change the display-mode... when trying to
> port that code to Ada apparently it failed to load properly due to the
> non-existent runtime's requirement.
The Borland Pascal 7 runtime was/is simple enough; there should be a way  
to emulate it on top of the Ada runtime, which is more complete.

> {True, it would be limited to 32-bits; but there isn't going to be a
> shortage of 32-bit CPUs for a while.}
I hope too they will live for a long time again  (I don't want to see  
millions of machines discharged and thrown away to Africa).


-- 
Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour  
les chiens.
“ c++; /* this makes c bigger but returns the old value */ ” [Anonymous]

Re: Pascal Calling Convention

[Randy Brukardt]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 3175 bytes --]

"Yannick Duch�ne (Hibou57)" <yannick_duchene@yahoo.fr> wrote in message 
news:op.vstkpc1rule2fv@index.ici...
Le Wed, 23 Mar 2011 22:37:55 +0100, Shark8 <onewingedshark@gmail.com> a
�crit:
...
>> The problem comes with the conventions... I'd like to be able to
>> interface w/o using stdcall or cdecl calling convention and directly
>> use the Pascal calling convention within my Ada texts. According to
>> this page ( 
>> http://gcc.gnu.org/onlinedocs/gnat_ugn_unw/Stdcall-Calling-Convention.html
>> ) the STDCALL convention *is* the Pascal calling convention; both are
>> callee clean-up of the stack however, according to wikipedia (and
>> http://www.swissdelphicenter.ch/torry/showcode.php?id=1233 ) there is
>> a difference: left-to-right vs. right-to-left parameter passing.
>As Delphi is Windows only, I suppose you want the Windows API calling 
>convention (tell me if I'm wrong). On Windows, this is 1) Parameters 
>pushed from right to left : like C 1) The callee clean the stack : like 
>Pascal. This is not the same as the Pascal calling convention, which push 
>parameters from left to right. I believe GNU docs is wrong here, when it 
>says the Pascal calling convention is the calling convention for Windows 
>API (wrong on both sides).

This is news to me, and I wrote the pragma Import support in Janus/Ada. 
Parameter passing in all of the Windows conventions (including C!) is 
left-to-right. But perhaps whomever wrote that was confused by the fact that 
the x86 stack grows downward, so the left parameter is the one at the 
highest address on the stack. Even so, it is the first one pushed.

In any case, the Microsoft Pascal calling convention eventually because 
StdCall, and neither is substantially different than what is done in Ada. 
I'd expect that Delphi uses the same calling convention or something pretty 
similar. So I'd probably just try it to see.

(Of course, if you wanted to *buy* a compiler, it probably would not be hard 
to provide real Delphi support in Janus/Ada. But of course that isn't 
happening without customers, and I'm sure the same is true for GNAT.)

                                   Randy.


I never owned a Delphi compiler, so I could not tell for Delphi proper
object files.

> This could also be a good nugget of information if I decide to use BP7
> to write an OS loader & runtime for that OS; I had an OS written in
> BP7 to the point where it could display a command-line, read
> [keyboard] commands, and change the display-mode... when trying to
> port that code to Ada apparently it failed to load properly due to the
> non-existent runtime's requirement.
The Borland Pascal 7 runtime was/is simple enough; there should be a way
to emulate it on top of the Ada runtime, which is more complete.

> {True, it would be limited to 32-bits; but there isn't going to be a
> shortage of 32-bit CPUs for a while.}
I hope too they will live for a long time again  (I don't want to see
millions of machines discharged and thrown away to Africa).


-- 
Si les chats miaulent et font autant de vocalises bizarres, c'est pas pour
les chiens.
" c++; /* this makes c bigger but returns the old value */ " [Anonymous] 

Re: Pascal Calling Convention

[ytomino]

Hello,

On Mar 24, 6:37 am, Shark8 <onewingedsh...@gmail.com> wrote:
> I was looking around for a way to use the Pascal calling convention in
> GNAT; particularly because I thought it might be nice to do the GUI-
> stuff in good old Delphi 5 and the application itself in Ada. All
> easily doable via DLL or, possibly, through the $L compiler directive
> which specifies a .obj file to link to.

In the first, Delphi's default calling convertion is "register" (=
fastcall),
not pascal. And, GNAT does not support fastcall,
moreever fastcall of gcc is different than fastcall of Windows.
Probably you have to change calling convertion in Delphi-side.

http://docwiki.embarcadero.com/RADStudio/XE/en/Procedures_and_Functions#Calling_Conventions

> -- I found a utility to convert between .o and .obj; so that's not a
> problem. Though if someone knows a way to
> -- have GNAT emit .obj files instead of .o I'd like to hear it.

That sounds good!
How it work about gcc-runtime? (memomry manager, exception handling,
etc)

Re: Pascal Calling Convention

[Yannick Duchêne (Hibou57)]

Le Thu, 24 Mar 2011 01:24:41 +0100, Randy Brukardt <randy@rrsoftware.com>  
a écrit:
> This is news to me, and I wrote the pragma Import support in Janus/Ada.
> Parameter passing in all of the Windows conventions (including C!) is
> left-to-right. But perhaps whomever wrote that was confused by the fact  
> that
> the x86 stack grows downward, so the left parameter is the one at the
> highest address on the stack. Even so, it is the first one pushed.
While I read you, I can't avoid thinking you must be true, as this is the  
only way to get variable number of parameters working for C. What is  
confusing also, is that assembly program sometime use the stack as an  
array : allocated room on the stack, and then do something looking like  
[ebp+0] := ... [ebp+4] := ... and so on. But I feel to remember parameter  
passing order for WinAPI is the reversed one than C. I will have a test  
tomorrow to check (I am not running Windows right now).


-- 
Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour  
les chiens.
“ c++; /* this makes c bigger but returns the old value */ ” [Anonymous]

Re: Pascal Calling Convention

[Shark8]

On Mar 23, 6:43 pm, Yannick Duchêne (Hibou57)
<yannick_duch...@yahoo.fr> wrote:
> Le Thu, 24 Mar 2011 01:24:41 +0100, Randy Brukardt <ra...@rrsoftware.com>  
> a écrit:> This is news to me, and I wrote the pragma Import support in Janus/Ada.
> > Parameter passing in all of the Windows conventions (including C!) is
> > left-to-right. But perhaps whomever wrote that was confused by the fact  
> > that
> > the x86 stack grows downward, so the left parameter is the one at the
> > highest address on the stack. Even so, it is the first one pushed.
>
> While I read you, I can't avoid thinking you must be true, as this is the  
> only way to get variable number of parameters working for C. What is  
> confusing also, is that assembly program sometime use the stack as an  
> array : allocated room on the stack, and then do something looking like  
> [ebp+0] := ... [ebp+4] := ... and so on. But I feel to remember parameter  
> passing order for WinAPI is the reversed one than C. I will have a test  
> tomorrow to check (I am not running Windows right now).

Yes-ish.
In the 16-bit world [Win 3.11] WinAPI params were pushed with Left-to-
Right [Pascal convention];
in the 32-bit world Win32API params are pushed Right-to-Left (like C,
but with calee cleanup, like Pascal calling convention).

http://en.wikipedia.org/wiki/X86_calling_conventions

Re: Pascal Calling Convention

[Shark8]

On Mar 23, 5:25 pm, Yannick Duchêne (Hibou57)
<yannick_duch...@yahoo.fr> wrote:
> The Borland Pascal 7 runtime was/is simple enough; there should be a way  
> to emulate it on top of the Ada runtime, which is more complete.

I think we crossed wires; I was thinking about implementing the Ada
runtime
via BP7; this would (in theory) allow me to compile Ada 'normally' (w/
o
having to mess with making a zero footprint and Standard) and load it
up as
the OS... this would give me the advantage of being able to run the OS
as
either "just another program" [for testing and such] and also as the
actual
OS for a machine.

(That setup is actually pretty useful for debugging; it's what I used
before though with DOS & BP7 rather than Windows & Delphi.)

> > {True, it would be limited to 32-bits; but there isn't going to be a
> > shortage of 32-bit CPUs for a while.}
>
> I hope too they will live for a long time again  (I don't want to see  
> millions of machines discharged and thrown away to Africa).

*nod* - Just because it's "old" doesn't mean it's not effective...
The Mosin-Nagant and the 1911-design are proof of that, though in the
realm of firearms rather than computers.

Re: Pascal Calling Convention

[Shark8]

On Mar 23, 6:38 pm, ytomino <aghi...@gmail.com> wrote:
> Hello,
>
> On Mar 24, 6:37 am, Shark8 <onewingedsh...@gmail.com> wrote:
>
> > I was looking around for a way to use the Pascal calling convention in
> > GNAT; particularly because I thought it might be nice to do the GUI-
> > stuff in good old Delphi 5 and the application itself in Ada. All
> > easily doable via DLL or, possibly, through the $L compiler directive
> > which specifies a .obj file to link to.
>
> In the first, Delphi's default calling convertion is "register" (=
> fastcall),
> not pascal. And, GNAT does not support fastcall,
> moreever fastcall of gcc is different than fastcall of Windows.
> Probably you have to change calling convertion in Delphi-side.
>
> http://docwiki.embarcadero.com/RADStudio/XE/en/Procedures_and_Functio...

Yep, I know that it's not the default.
But it *does* have Pascal calling convention capability.
And, to be honest, I *don't want* variable parameters passed in the
OS;
so, as someone observed, if the right-to-left parameter passing is the
only way for it to be handled then designing the OS in such a way so
as
to preclude even that possibility sounds like a good idea to me.

{Like Null-exclusion or subranges; I can design out possible errors/
complexities.}

> > -- I found a utility to convert between .o and .obj; so that's not a
> > problem. Though if someone knows a way to
> > -- have GNAT emit .obj files instead of .o I'd like to hear it.
>
> That sounds good!
> How it work about gcc-runtime? (memomry manager, exception handling,
> etc)

I'm not sure.
I haven't "played around" with it enough yet.

Re: Pascal Calling Convention

[Keith Thompson]

Dennis Lee Bieber <wlfraed@ix.netcom.com> writes:
> On Thu, 24 Mar 2011 01:43:57 +0100, Yannick Duchêne (Hibou57)
> <yannick_duchene@yahoo.fr> declaimed the following in comp.lang.ada:
>
>> [ebp+0] := ... [ebp+4] := ... and so on. But I feel to remember parameter  
>> passing order for WinAPI is the reversed one than C. I will have a test  
>> tomorrow to check (I am not running Windows right now).
>
> 	Could it be (hypothesis) that it is the parameter /evaluation/ order
> which is reversed?
>
> 	That is, does
>
> 	i = 0;
> 	someC(i++, i++, i++);
>
> produce
> 		(0, 1, 2)
> or
> 		(2, 1, 0)

On my system, it produced (2, 1, 0), but this doesn't mean anything.
In C, the order of evaluation of function arguments is explicitly
unspecified.  Furthermore, in this particular case, the multiple
modifications to the same object without an intervening sequence
point mean that the behavior of the program is undefined; it
could legitimately print "a suffusion of yellow" or cause your
keyboard to explode.  (C's "undefined behavior" is very much like
Ada's "erroneous execution" -- and IMHO C chose a better term to
describe it.)

Furthermore, the order of evaluation of the argument expressions
isn't *necessarily* related to the order in which the results are
pushed onto the stack (assuming there even is a stack).

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

Re: Pascal Calling Convention

[Gautier write-only]

On Mar 23, 10:37 pm, Shark8 wrote:

> I was looking around for a way to use the Pascal calling convention in
> GNAT; particularly because I thought it might be nice to do the GUI-
> stuff in good old Delphi 5 and the application itself in Ada. All
> easily doable via DLL or, possibly, through the $L compiler directive
> which specifies a .obj file to link to.

If you start the GUI from scratch, it is perhaps a good idea to
consider using GWindows instead.
Did you have a look ? The library is there: http://sf.net/projects/gnavi/
You can use ResEdit http://www.resedit.net/ for the GUI design, the
code generator (GWenerator) packaged with GWindows, that generates the
appropriate packages in the background.
Add to it free graphical elements like from there: http://www.iconarchive.com/
and you can make absolutely sexy UIs for Windows, all with GNAT,
without any worry about DLLs, pragmas, calling conventions, etc., all
for free! Tempting, isn't it ? Basically you press F4 in GPS and you
get your .exe ... (in the automatic mode, the GWenerator also calls
gnatmake, so you don't even need to press a key!)
Cheers
______________________________________________________________
Gautier's Ada programming -- http://gautiersblog.blogspot.com/
NB: follow the above link for a valid e-mail address

Re: Pascal Calling Convention

[Marco]

You might want to try this free ObjectAda compiler for Windows:

ftp://ftp.cs.kuleuven.be/pub/Ada-Belgium/mirrors/pal/userdocs/htm/cdcat/aonixcmp.htm

I haven't used it in over 10 years so not sure if it supports what you need.

Re: Pascal Calling Convention

[Yannick Duchêne (Hibou57)]

Le Fri, 25 Mar 2011 13:47:58 +0100, Marco <prenom_nomus@yahoo.com> a écrit:

> You might want to try this free ObjectAda compiler for Windows:
>
> ftp://ftp.cs.kuleuven.be/pub/Ada-Belgium/mirrors/pal/userdocs/htm/cdcat/aonixcmp.htm
>
> I haven't used it in over 10 years so not sure if it supports what you  
> need.

Last updated: 1997 (15 years old, which means probably as much tens of  
bugs still not fixed; otherwise, that's OK)
Support: Ada 95 (may be OK, but could be better if used for learning or  
promiting)
Platform: Windows only (a bare minimum nowadays, is Windows [the  
unavoidable one] + BSD or Linux [the cheap one or web server one])

But I agree this is nice of this to be there.

-- 
Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour  
les chiens.
“ c++; /* this makes c bigger but returns the old value */ ” [Anonymous]

Re: Pascal Calling Convention

[Yannick Duchêne (Hibou57)]

Le Thu, 24 Mar 2011 03:04:45 +0100, Shark8 <onewingedshark@gmail.com> a  
écrit:
> Yes-ish.
> In the 16-bit world [Win 3.11] WinAPI params were pushed with Left-to-
> Right [Pascal convention];
> in the 32-bit world Win32API params are pushed Right-to-Left (like C,
> but with calee cleanup, like Pascal calling convention).
>
> http://en.wikipedia.org/wiki/X86_calling_conventions
Confusing enough indeed, thanks for clarifications (I should have not said  
anything; and funny to see how I was pretty sure and was finally wrong).

-- 
Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour  
les chiens.
“ c++; /* this makes c bigger but returns the old value */ ” [Anonymous]

Re: Pascal Calling Convention

[Robert A Duff]

Keith Thompson <kst-u@mib.org> writes:

> Dennis Lee Bieber <wlfraed@ix.netcom.com> writes:
>> 	i = 0;
>> 	someC(i++, i++, i++);

> On my system, it produced (2, 1, 0), but this doesn't mean anything.
> In C, the order of evaluation of function arguments is explicitly
> unspecified.  Furthermore, in this particular case, the multiple
> modifications to the same object without an intervening sequence
> point mean that the behavior of the program is undefined; ...

True, and writing code that can cause undefined behavior is generally a
Bad Thing.  But it doesn't seem like such a bad thing to deliberately
use undefined behavior when trying to figure out what an implementation
is up to "under the hood".  Just don't assume too much -- after all,
the compiler might choose left-to-right order in one case, but not
in another case, for efficiency reasons.

>...it
> could legitimately print "a suffusion of yellow" or cause your
> keyboard to explode.

True, according to the C standard.  But I'm pretty sure that there's
some other standard that will prevent it from blowing up my keyboard.
;-)

By the way, when explaining what "undefined behavior" means, why does
everybody choose a spectacular example, like exploding keyboards,
or seg faults?  I think the worst thing of all is when undefined
behavior does exactly what you want it to do, leaving a latent
bug that will rear its ugly head years later, when you change
some code totally unrelated to the bug, or upgrade your compiler,
or...

>...(C's "undefined behavior" is very much like
> Ada's "erroneous execution" -- and IMHO C chose a better term to
> describe it.)

"very much like"?  Is there any difference at all?  (Other than
the fact that C has more of it, I mean.)

I agree on the terms.  An even better term, IMHO, would be
"unpredictable behavior".

> Furthermore, the order of evaluation of the argument expressions
> isn't *necessarily* related to the order in which the results are
> pushed onto the stack (assuming there even is a stack).

There must be a stack.  But you're right -- parameters might be
passed in registers, or some other way, and there's no reason
to assume that the evaluation order will match the way they're
passed.

- Bob

Re: Pascal Calling Convention

[Hyman Rosen]

On 3/25/2011 12:04 PM, Robert A Duff wrote:
> There must be a stack.

Why?

Re: Pascal Calling Convention

[Robert A Duff]

Hyman Rosen <hyrosen@mail.com> writes:

> On 3/25/2011 12:04 PM, Robert A Duff wrote:
>> There must be a stack.
>
> Why?

Because Ada supports recursion, which implies a LIFO data structure --
a stack.  One per task, in fact.

- Bob

Re: Pascal Calling Convention

[Hyman Rosen]

On 3/25/2011 1:09 PM, Robert A Duff wrote:
> Hyman Rosen<hyrosen@mail.com>  writes:
>
>> On 3/25/2011 12:04 PM, Robert A Duff wrote:
>>> There must be a stack.
>>
>> Why?
>
> Because Ada supports recursion, which implies a LIFO data structure --
> a stack.  One per task, in fact.

Recursion just implies that when a procedure is called (or when any
local scope is entered) it is allocated a separate set of its local
variables. That can be done with tree-like allocation structures
instead of a stack. In continuation-passing languages with garbage
collection, returning from a procedure or exiting a scope does not
imply freeing the variables of that scope, because that scope can
be re-entered.

Re: Pascal Calling Convention

[Keith Thompson]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:
> Keith Thompson <kst-u@mib.org> writes:
>> Dennis Lee Bieber <wlfraed@ix.netcom.com> writes:
>>> 	i = 0;
>>> 	someC(i++, i++, i++);
>
>> On my system, it produced (2, 1, 0), but this doesn't mean anything.
>> In C, the order of evaluation of function arguments is explicitly
>> unspecified.  Furthermore, in this particular case, the multiple
>> modifications to the same object without an intervening sequence
>> point mean that the behavior of the program is undefined; ...
>
> True, and writing code that can cause undefined behavior is generally a
> Bad Thing.  But it doesn't seem like such a bad thing to deliberately
> use undefined behavior when trying to figure out what an implementation
> is up to "under the hood".  Just don't assume too much -- after all,
> the compiler might choose left-to-right order in one case, but not
> in another case, for efficiency reasons.

Keep in mind that "undefined" behavior doesn't just mean that the code
will do one of N reasonable things.  It means that the compiler is
permitted to *assume*, for the sake of optimization, that no undefined
behavior will occur during the execution of the program.

This particular case is relatively straightforward, but there have
been some serious bugs caused by this kind of thing.  One example
that springs to mind: some code read from uninitialized memory as
a source of entropy for pseudo-random number generation (not the
only source).  That seems like a reasonable thing to do, but the
compiler optimized away the code that did the reading, resulting
in some really bad "random" numbers.

>>...it
>> could legitimately print "a suffusion of yellow" or cause your
>> keyboard to explode.
>
> True, according to the C standard.  But I'm pretty sure that there's
> some other standard that will prevent it from blowing up my keyboard.
> ;-)

Or from blowing up your rocket?

> By the way, when explaining what "undefined behavior" means, why does
> everybody choose a spectacular example, like exploding keyboards,
> or seg faults?  I think the worst thing of all is when undefined
> behavior does exactly what you want it to do, leaving a latent
> bug that will rear its ugly head years later, when you change
> some code totally unrelated to the bug, or upgrade your compiler,
> or...

Agreed.

>>...(C's "undefined behavior" is very much like
>> Ada's "erroneous execution" -- and IMHO C chose a better term to
>> describe it.)
>
> "very much like"?  Is there any difference at all?  (Other than
> the fact that C has more of it, I mean.)

There's no actual difference that I'm aware of.  I was just being
cautious.

> I agree on the terms.  An even better term, IMHO, would be
> "unpredictable behavior".

Except that there's no requirement that the behavior must be
unpredictable.

An implementer is free to define the behavior of some construct
whose behavior is not defined by the language standard.  At least
in C, this is a common way to provide extensions.

>> Furthermore, the order of evaluation of the argument expressions
>> isn't *necessarily* related to the order in which the results are
>> pushed onto the stack (assuming there even is a stack).
>
> There must be a stack.  But you're right -- parameters might be
> passed in registers, or some other way, and there's no reason
> to assume that the evaluation order will match the way they're
> passed.

We've had some lengthy arguments about this over in comp.lang.c.

Yes, an implementation for a language that supports recursion must
have a stack, in sense of a last-in first-out data structure for
activation records.

But the word "stack" is also used to refer to a contiguous chunk
of memory whose "top" is indicated by the address stored in a
"stack pointer".  The stack is grown or shrunk by adding to or
subtracting from the stack pointer (not necessarily respectively).
The last-in first-out "stack" of activation records is implemented
using this kind of hardware stack on almost all implementations of
both C and Ada -- but neither language standard requires that it
must be done this way.  For example, I've heard about IBM mainframe
implementations in which each new activation record is allocated
from something like a heap, so there's no necessary relationship
among the addresses of local variables for successive calls.

I note that the word "stack" doesn't even appear in the C standard,
which manages to describe function calling without using the concept.
Ada refers in passing to stacks for tasks an interrupts; I'm not
sure what kind of requirement that imposes.

I have no doubt that you're aware of all this, but some readers might
interpret your (quite correct) statement that "There must be a stack"
to mean that there must be a contiguous hardware stack, managed via
a stack pointer register, that grows and shrinks linearly in memory.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

ObjectAda [was: Pascal Calling Convention]

[Gautier write-only]

On Mar 25, 4:38 pm, Yannick Duchêne (Hibou57) wrote:

> Last updated: 1997 (15 years old, which means probably as much tens of  
> bugs still not fixed; otherwise, that's OK)

I'm afraid you are jumping into conclusions...
- the latest free, fully functional (but with limited amount of units
and lines of code per unit) version is the v.7.2.2 SE dated 2001

> Support: Ada 95 (may be OK, but could be better if used for learning or  
> promiting)

Sure but even the 7.2.2 SE is still finding bugs that GNAT doesn't,
e.g.
http://groups.google.com/group/comp.lang.ada/browse_frm/thread/10b4863a0a2cf267/
Of course the reverse may be true as well.
Anyway, I test my various Ada projects with both OA and GNAT before
being convinced it is "kosher" or "halal" Ada...

> Platform: Windows only (a bare minimum nowadays, is Windows [the  
> unavoidable one] + BSD or Linux [the cheap one or web server one])

Windows only ? Wait...
http://www.atego.com/products/aonix-objectada-for-windows/
http://www.atego.com/products/aonix-objectada-for-linux/
http://www.atego.com/products/aonix-objectada-for-unix/
http://www.atego.com/products/aonix-objectada-raven/
http://www.atego.com/products/aonix-objectada-real-time/

> But I agree this is nice of this to be there.

Isn't it ;-) ?
______________________________________________________________
Gautier's Ada programming -- http://gautiersblog.blogspot.com/
NB: follow the above link for a valid e-mail address

Re: ObjectAda [was: Pascal Calling Convention]

[Marco]

On Saturday, March 26, 2011 1:39:53 AM UTC-7, Gautier write-only wrote:
> 
> I'm afraid you are jumping into conclusions...
> - the latest free, fully functional (but with limited amount of units
> and lines of code per unit) version is the v.7.2.2 SE dated 2001

  Do you have a link to this newer download?

Re: Pascal Calling Convention

[Robert A Duff]

Hyman Rosen <hyrosen@mail.com> writes:

> On 3/25/2011 1:09 PM, Robert A Duff wrote:
>> Hyman Rosen<hyrosen@mail.com>  writes:
>>
>>> On 3/25/2011 12:04 PM, Robert A Duff wrote:
>>>> There must be a stack.
>>>
>>> Why?
>>
>> Because Ada supports recursion, which implies a LIFO data structure --
>> a stack.  One per task, in fact.
>
> Recursion just implies that when a procedure is called (or when any
> local scope is entered) it is allocated a separate set of its local
> variables. That can be done with tree-like allocation structures
> instead of a stack.

I'm not sure exactly what you mean by these tree-like things, but I think
each branch of that tree is really a stack.

I'll make an even bolder claim:  Even without recursion and tasking,
there is always an implicit stack in Ada.  That's because of the way
block statements and procedure calls are defined -- local variables
are created and destroyed (and initialized and finalized) in a LIFO
manner, and that's a stack, no matter how that stack is implemented.

>...In continuation-passing languages with garbage
> collection, returning from a procedure or exiting a scope does not
> imply freeing the variables of that scope, because that scope can
> be re-entered.

Sure, but that's not Ada.

- Bob

Re: Pascal Calling Convention

[Robert A Duff]

Keith Thompson <kst-u@mib.org> writes:

> Keep in mind that "undefined" behavior doesn't just mean that the code
> will do one of N reasonable things.  It means that the compiler is
> permitted to *assume*, for the sake of optimization, that no undefined
> behavior will occur during the execution of the program.
>
> This particular case is relatively straightforward, but there have
> been some serious bugs caused by this kind of thing.

Indeed.

>...One example
> that springs to mind: some code read from uninitialized memory as
> a source of entropy for pseudo-random number generation (not the
> only source).  That seems like a reasonable thing to do, but the
> compiler optimized away the code that did the reading, resulting
> in some really bad "random" numbers.

It doesn't seem reasonable to me.  Uninitialized variables do not
contain random data.  They contain arbitrary data.  And it's quite
likely that such arbitrary data happens to be the same every time,
or has some other non-random pattern.  Bad Guys sometimes exploit
such patterns to cause security problems.

>>>...it
>>> could legitimately print "a suffusion of yellow" or cause your
>>> keyboard to explode.
>>
>> True, according to the C standard.  But I'm pretty sure that there's
>> some other standard that will prevent it from blowing up my keyboard.
>> ;-)
>
> Or from blowing up your rocket?

;-)

The computer I'm typing on does not control rockets, so I think doing
things like i++ + ++i won't have any effect on any rockets.
Laws of physics makes it unlikely.  ;-)

>> By the way, when explaining what "undefined behavior" means, why does
>> everybody choose a spectacular example, like exploding keyboards,
>> or seg faults?  I think the worst thing of all is when undefined
>> behavior does exactly what you want it to do, leaving a latent
>> bug that will rear its ugly head years later, when you change
>> some code totally unrelated to the bug, or upgrade your compiler,
>> or...
>
> Agreed.

Good.  I think folks like you and me who understand what "undefined
behavior" means in C, or "erroneous behavior" in Ada, ought to explain
it that way.

Too many programmers are puzzled by the concept, which has important
implications for language designers (like me).

>>>...(C's "undefined behavior" is very much like
>>> Ada's "erroneous execution" -- and IMHO C chose a better term to
>>> describe it.)
>>
>> "very much like"?  Is there any difference at all?  (Other than
>> the fact that C has more of it, I mean.)
>
> There's no actual difference that I'm aware of.  I was just being
> cautious.
>
>> I agree on the terms.  An even better term, IMHO, would be
>> "unpredictable behavior".
>
> Except that there's no requirement that the behavior must be
> unpredictable.
>
> An implementer is free to define the behavior of some construct
> whose behavior is not defined by the language standard.  At least
> in C, this is a common way to provide extensions.

I don't understand your objection:

    "Undefined behavior" means "the language standard doesn't define the
    behavior".

    "Unpredictable behavior", means "you can't predict the behavior
    based on the language standard".

Either way, some particular implementation might define the behavior, or
allow you to predict the behavior.  Seems like the same thing, to me.

The message to convey is "Don't do that!".

>>> Furthermore, the order of evaluation of the argument expressions
>>> isn't *necessarily* related to the order in which the results are
>>> pushed onto the stack (assuming there even is a stack).
>>
>> There must be a stack.  But you're right -- parameters might be
>> passed in registers, or some other way, and there's no reason
>> to assume that the evaluation order will match the way they're
>> passed.
>
> We've had some lengthy arguments about this over in comp.lang.c.
>
> Yes, an implementation for a language that supports recursion must
> have a stack, in sense of a last-in first-out data structure for
> activation records.

Right.  See my other post, where I claim that's true even without
recursion, assuming the language defines LIFO procedure calls.
Without recursion and multi-threading, maybe the address of every
call frame is known at compile/link time, but still, variables
are being created and destroyed in LIFO order.

Local variables in Ada or C are not like static variables in C,
even if you eliminate recursion.

> But the word "stack" is also used to refer to a contiguous chunk
> of memory whose "top" is indicated by the address stored in a
> "stack pointer".  The stack is grown or shrunk by adding to or
> subtracting from the stack pointer (not necessarily respectively).
> The last-in first-out "stack" of activation records is implemented
> using this kind of hardware stack on almost all implementations of
> both C and Ada -- but neither language standard requires that it
> must be done this way.  For example, I've heard about IBM mainframe
> implementations in which each new activation record is allocated
> from something like a heap, so there's no necessary relationship
> among the addresses of local variables for successive calls.
>
> I note that the word "stack" doesn't even appear in the C standard,
> which manages to describe function calling without using the concept.
> Ada refers in passing to stacks for tasks an interrupts; I'm not
> sure what kind of requirement that imposes.
>
> I have no doubt that you're aware of all this,..

Thanks for your confidence.  ;-)  Yes, I'm aware.

>...but some readers might
> interpret your (quite correct) statement that "There must be a stack"
> to mean that there must be a contiguous hardware stack, managed via
> a stack pointer register, that grows and shrinks linearly in memory.

Thanks for the clarification.  I agree with the above, and of course I
agree that the stack doesn't have to be a contiguous block of memory.
But why do you call that "contiguous stack" thing a "hardware stack"?
I mean, on most architectures, push/pop are implemented by subtract/add
instructions on the stack pointer register.  That's not a whole lot of
"hardware support for stacks".  The hardware has instructions that
support implementing arrays, and linked lists, too, but we don't call them
"hardware arrays" or "hardware linked lists".

OK, on x86, there are push/pop instructions.  But most stack
manipulation is still just subtract/add.  Call pushes a return address.
Enter/leave instructions are stack-oriented, but nobody uses those,
because they're slow.  Maybe "the stack" on x86 could be called a
"hardware stack", but it's pretty marginal in practice.

By the way, "the stack" in GNAT is split into primary and secondary
stacks.  I still call those, taken together, "a stack".

- Bob

Re: Pascal Calling Convention

[Florian Weimer]

* Keith Thompson:

> keyboard to explode.  (C's "undefined behavior" is very much like
> Ada's "erroneous execution" -- and IMHO C chose a better term to
> describe it.)

But there is undefined behavior because the standard says so, and
undefined behavior because it's not specified at all (perhaps
accidentally).  "Erroneous execution" doesn't suffer from this
problem.

Re: ObjectAda [was: Pascal Calling Convention]

[Gautier write-only]

On Mar 26, 3:05 pm, Marco <prenom_no...@yahoo.com> wrote:

>   Do you have a link to this newer download?

http://www.ada-deutschland.de/AdaTourCD/AdaTourCD2004/entwicklungsumgebung/Software/ObjectAda7.22/zip.zip

From this page:
http://www.ada-deutschland.de/AdaTourCD/AdaTourCD2004/index_tools.html

Another cool thing with OA is that they manage more of the toolchain
themselves, with obvious advantages:
- the assembler output is readable, with references to the Ada source
code
- the debugger is integrated to the IDE and with the expected
robustness for a debugger
______________________________________________________________
Gautier's Ada programming -- http://gautiersblog.blogspot.com/
NB: follow the above link for a valid e-mail address

Re: Pascal Calling Convention

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message 
news:wccbp0xy5hu.fsf@shell01.TheWorld.com...
...
> Thanks for the clarification.  I agree with the above, and of course I
> agree that the stack doesn't have to be a contiguous block of memory.
> But why do you call that "contiguous stack" thing a "hardware stack"?
> I mean, on most architectures, push/pop are implemented by subtract/add
> instructions on the stack pointer register.  That's not a whole lot of
> "hardware support for stacks".  The hardware has instructions that
> support implementing arrays, and linked lists, too, but we don't call them
> "hardware arrays" or "hardware linked lists".
>
> OK, on x86, there are push/pop instructions.  But most stack
> manipulation is still just subtract/add.  Call pushes a return address.
> Enter/leave instructions are stack-oriented, but nobody uses those,
> because they're slow.  Maybe "the stack" on x86 could be called a
> "hardware stack", but it's pretty marginal in practice.

I can't speak for Keith, but most of the hardware architectures that I've 
worked on have had at least some architectual support for a "hardware" 
stack. Not only the Push/Pop instructions of the X86 for instance, but also 
the special SS stack segment register. The 68K also had a dedicated stack 
register and some special instructions for call/ret. Even the Unisys U2200 
mainframe had a stack segment and special instructions for call/ret and 
stack frames.

I agree that these things aren't that different than add or subtract, but 
given the way that they're documented (as a hardware-supported stack in each 
case), I think it is pretty obvious that these things exist. (Inventing your 
own terminology and ignoring the standard view of an architecture is a good 
way to confuse everyone who talks to you...)

                         Randy.

Re: Pascal Calling Convention

[Robert A Duff]

Florian Weimer <fw@deneb.enyo.de> writes:

> But there is undefined behavior because the standard says so, and
> undefined behavior because it's not specified at all (perhaps
> accidentally).  "Erroneous execution" doesn't suffer from this
> problem.

I don't see the difference.  How do you know I didn't leave out
something important when I wrote some part of the Ada RM?
Of course, I tried not to, and I'm sure people writing the C
standard did, too.

Of course, there are always things outside the standard.  Neither C
nor Ada standard will tell you what happens if you run your program
under a debugger, and modify a constant while stopped at a breakpoint.
Or stop a program that is in the middle of doing "delay X;".
Or what happens if you unplug the computer while running a C or Ada
program.

- Bob

Re: Pascal Calling Convention

[Florian Weimer]

* Robert A. Duff:

> Florian Weimer <fw@deneb.enyo.de> writes:
>
>> But there is undefined behavior because the standard says so, and
>> undefined behavior because it's not specified at all (perhaps
>> accidentally).  "Erroneous execution" doesn't suffer from this
>> problem.
>
> I don't see the difference.  How do you know I didn't leave out
> something important when I wrote some part of the Ada RM?
> Of course, I tried not to, and I'm sure people writing the C
> standard did, too.

It's just when I say something is "undefined", it's not clear in what
category it is.  That's why I think the label is confusing.

Re: Pascal Calling Convention

[Robert A Duff]

Florian Weimer <fw@deneb.enyo.de> writes:

> It's just when I say something is "undefined", it's not clear in what
> category it is.  That's why I think the label is confusing.

OK, I see what you mean.  Yes, it is a little confusing.

But many programmers have a lot of trouble understanding the concept
itself, no matter what it's called.  People learn to program by
experiment.  By experiment, you can learn that signed integer
arithmetic in C wraps around.  But that's wrong.

- Bob

Re: Pascal Calling Convention

[Adam Beneschan]

On Mar 26, 7:24 pm, "Randy Brukardt" <ra...@rrsoftware.com> wrote:
> "Robert A Duff" <bobd...@shell01.TheWorld.com> wrote in messagenews:wccbp0xy5hu.fsf@shell01.TheWorld.com...
> ...
>
> > Thanks for the clarification.  I agree with the above, and of course I
> > agree that the stack doesn't have to be a contiguous block of memory.
> > But why do you call that "contiguous stack" thing a "hardware stack"?
> > I mean, on most architectures, push/pop are implemented by subtract/add
> > instructions on the stack pointer register.  That's not a whole lot of
> > "hardware support for stacks".  The hardware has instructions that
> > support implementing arrays, and linked lists, too, but we don't call them
> > "hardware arrays" or "hardware linked lists".
>
> > OK, on x86, there are push/pop instructions.  But most stack
> > manipulation is still just subtract/add.  Call pushes a return address.
> > Enter/leave instructions are stack-oriented, but nobody uses those,
> > because they're slow.  Maybe "the stack" on x86 could be called a
> > "hardware stack", but it's pretty marginal in practice.
>
> I can't speak for Keith, but most of the hardware architectures that I've
> worked on have had at least some architectual support for a "hardware"
> stack. Not only the Push/Pop instructions of the X86 for instance, but also
> the special SS stack segment register. The 68K also had a dedicated stack
> register and some special instructions for call/ret. Even the Unisys U2200
> mainframe had a stack segment and special instructions for call/ret and
> stack frames.

I've worked with several RISC machines that don't have this kind of
support, though.  There are, of course, calling conventions for those
machines that programmers follow (if they want their programs to
cooperate in any way with other software), and conventionally one
particular register is designated the stack register.  But from a
hardware standpoint, there's nothing special about the register, in
the sense that there are no instructions that operate on that register
that aren't available on all general registers, and nothing else
special about how the register is implemented in hardware (such as
being one of a few designated registers that are saved when an
interrupt occurs).  I don't know what the definition of "hardware-
supported stack" is, but it seems like having a special stack register
would be one necessary characteristic.

                              -- Adam

Re: Pascal Calling Convention

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> I can't speak for Keith, but most of the hardware architectures that I've 
> worked on have had at least some architectual support for a "hardware" 
> stack. Not only the Push/Pop instructions of the X86 for instance, but also 
> the special SS stack segment register.

True, but nobody uses the SS register in any nontrivial way, anymore.
The segmentation stuff of 8086 is pretty much vestigial at this point.

>...The 68K also had a dedicated stack 
> register and some special instructions for call/ret. Even the Unisys U2200 
> mainframe had a stack segment and special instructions for call/ret and 
> stack frames.
>
> I agree that these things aren't that different than add or subtract, but 
> given the way that they're documented (as a hardware-supported stack in each 
> case), I think it is pretty obvious that these things exist. (Inventing your 
> own terminology and ignoring the standard view of an architecture is a good 
> way to confuse everyone who talks to you...)

But we're not talking about "an architecture".  We're talking about
the implementation of Ada (or any other language that has LIFO call
semantics -- no full closures, continuations...).  On ANY architecture.

As Adam pointed out in another reply, many machines have a stack pointer
register, but purely as a software convention.  On such machines, one
still usually implements the stack as a contiguous region of memory,
with the SP pointing to the top.  I don't want to call that thing
a "hardware stack" -- rather, "contiguous stack" or something.
(Even there, GNAT has a secondary stack, which is a linked list
in at least some cases.  Not a linked list of call frames, but
a linked list of memory blocks, each of which can contain
multiple call frames.)

And somebody (Hyman, I think) pointed to some IBM machines where the
stack is normally implemented as a linked list.  Still a stack,
in my book.

"Stack" is a pretty well-understood term in computer science,
and I think if an x86-centric person insists that "the stack"
must be a certain way based on the hardware/architecture,
they're the one inventing confusing terminology.
Keith is trying to clarify, by calling that contiguous thing
a "hardware stack", but I'm saying the word "hardware" doesn't
capture the intended meaning.

- Bob

Re: Pascal Calling Convention

[Hyman Rosen]

On 3/26/2011 4:46 PM, Robert A Duff wrote:
> It doesn't seem reasonable to me.  Uninitialized variables do not
> contain random data.  They contain arbitrary data.  And it's quite
> likely that such arbitrary data happens to be the same every time,
> or has some other non-random pattern.  Bad Guys sometimes exploit
> such patterns to cause security problems.

Time for my favorite data structure! This is a structure which
represents an unordered set of the integers [0,N) and which has
constant time initialization, insertion, deletion, and membership
test. It relies on reading uninitialized data as some arbitrary
value. Compilers which regard doing this as undefined behavior
will break the code. I'm going to write it in C++, but it should
be straightforward to translate to Ada:

template <unsigned N>
class set
{
     unsigned n;    // number of members in set
     unsigned d[N]; // members are in d[0..n-1]
     unsigned s[N]; // d[s[k]] == k if k is a member
     // unspecified elements of d and s are arbitrary

public:
     set() : n(0) { }
     bool has(unsigned k)
         { return k < N && s[k] < n && d[s[k]] == k; }
     void add(unsigned k)
         { if (k < N && !has(k)) { d[n] = k; s[k] = n++; }
     void del(unsigned k)
         { if (has(k)) { unsigned i = s[k]; d[i] = d[--n]; s[d[i]] = i; }
     void clr() { n = 0; }
};

Re: Pascal Calling Convention

[Adam Beneschan]

On Mar 28, 1:29 pm, Hyman Rosen <hyro...@mail.com> wrote:
> On 3/26/2011 4:46 PM, Robert A Duff wrote:
>
> > It doesn't seem reasonable to me.  Uninitialized variables do not
> > contain random data.  They contain arbitrary data.  And it's quite
> > likely that such arbitrary data happens to be the same every time,
> > or has some other non-random pattern.  Bad Guys sometimes exploit
> > such patterns to cause security problems.
>
> Time for my favorite data structure! This is a structure which
> represents an unordered set of the integers [0,N) and which has
> constant time initialization, insertion, deletion, and membership
> test. It relies on reading uninitialized data as some arbitrary
> value. Compilers which regard doing this as undefined behavior
> will break the code. I'm going to write it in C++, but it should
> be straightforward to translate to Ada:

I hope your "favorite data structure" comment was sarcastic.  I would
expect this code to behave incorrectly a large portion of the time;
specifically, if I read the code right, once you add any element to
the set, the program is likely to think 0 is in the set whether you've
added it or not.

                        -- Adam



> template <unsigned N>
> class set
> {
>      unsigned n;    // number of members in set
>      unsigned d[N]; // members are in d[0..n-1]
>      unsigned s[N]; // d[s[k]] == k if k is a member
>      // unspecified elements of d and s are arbitrary
>
> public:
>      set() : n(0) { }
>      bool has(unsigned k)
>          { return k < N && s[k] < n && d[s[k]] == k; }
>      void add(unsigned k)
>          { if (k < N && !has(k)) { d[n] = k; s[k] = n++; }
>      void del(unsigned k)
>          { if (has(k)) { unsigned i = s[k]; d[i] = d[--n]; s[d[i]] = i; }
>      void clr() { n = 0; }
>
>
>
> };

Re: Pascal Calling Convention

[Hyman Rosen]

On 3/28/2011 5:16 PM, Adam Beneschan wrote:
> I hope your "favorite data structure" comment was sarcastic.  I would
> expect this code to behave incorrectly a large portion of the time;
> specifically, if I read the code right, once you add any element to
> the set, the program is likely to think 0 is in the set whether you've
> added it or not.

I wrote the code from memory so it's possible I made a mistake,
but I don't think you're correct - you're likely not reading the
code right.

Re: Pascal Calling Convention

[Adam Beneschan]

On Mar 28, 2:26 pm, Hyman Rosen <hyro...@mail.com> wrote:
> On 3/28/2011 5:16 PM, Adam Beneschan wrote:
>
> > I hope your "favorite data structure" comment was sarcastic.  I would
> > expect this code to behave incorrectly a large portion of the time;
> > specifically, if I read the code right, once you add any element to
> > the set, the program is likely to think 0 is in the set whether you've
> > added it or not.
>
> I wrote the code from memory so it's possible I made a mistake,
> but I don't think you're correct - you're likely not reading the
> code right.

OK, I've looked at it again and you may be right.  However, it's also
not a relevant example; I don't see how any compiler could reasonably
detect that the code is going to read a value that hasn't been set,
given that such reads are reads of array elements using indexes that
aren't known at compile time.  Maybe a really clever compiler that
inlines can see (from the code that uses this structure) that the
first operation is "add" which calls "has" which is going to read a
value in the "s" array before anything has been set; on the other
hand, a compiler that's that clever will also figure out that "n" has
to be 0 at that point which means that it can determine s[k] < n will
necessarily be false without having to read from the array at all.
Anyway, I think the sort of code Keith was talking about involved a
single variable that was read when uninitialized---probably was never
set to anything at all in the program---which is much more plausible
for a compiler to treat as an "undefined" operation.

On top of that, I don't see why anyone would prefer this over the
trivial structure that just allocates N bytes, initializes them to 0,
and sets a byte to 1 to add an element to the set, etc.  That
structure has non-constant initialization, but so what?
Initialization will only take place once for a set; the other
operations are likely to be performed a lot more, and your code
performs multiple indexed accesses for every operation instead of just
one.  And the initialization can often be done with a single machine
instruction.

                                   -- Adam

Re: Pascal Calling Convention

[Georg Bauhaus]

On 3/29/11 12:08 AM, Adam Beneschan wrote:
> On Mar 28, 2:26 pm, Hyman Rosen<hyro...@mail.com>  wrote:
>> On 3/28/2011 5:16 PM, Adam Beneschan wrote:
>>
>>> I hope your "favorite data structure" comment was sarcastic.  I would
>>> expect this code to behave incorrectly a large portion of the time;
>>> specifically, if I read the code right, once you add any element to
>>> the set, the program is likely to think 0 is in the set whether you've
>>> added it or not.
>>
>> I wrote the code from memory so it's possible I made a mistake,
>> but I don't think you're correct - you're likely not reading the
>> code right.
>
> OK, I've looked at it again and you may be right.  However, it's also
> not a relevant example; I don't see how any compiler could reasonably
> detect ...

Won't this example of a set be the kind of Ada program that Ada 2012
analyzers (of aspect annotations) are waiting for?

> On top of that, I don't see why anyone would prefer this over the
> trivial structure that just allocates N bytes, initializes them to 0,
> and sets a byte to 1 to add an element to the set, etc.

I think one can expand the example with little effort to become an
efficient hashed set/map, one that requires very little run-time
support in comparison to Ada.Containers.*, I should think.
(It might have start as one, sorry in case I haven't seen this,
or misrepresent it.)

A transliteration attempt follows, with these additions in mind.

pragma Profile(Ravenscar);
pragma Restrictions (No_Allocators);

generic
     type unsigned is mod <>;
     N : unsigned;  -- capacity, hash(d) < N!
     type t is private;  -- values in sets (maps)
     with function hash (d : t) return unsigned;
     -- must return the `k` parameter of set (map) operations
package Sets is

     type set is tagged private;
     function has(this : set; k : unsigned) return Boolean;
     procedure add(this : in out set; k : unsigned; data : t);
     procedure del(this : in out set; k : unsigned);
     procedure clr(this : in out set);

private
     type uptr is array (unsigned range <>) of unsigned;
     type dptr is array (unsigned range <>) of t;
     type set is tagged record
         n : unsigned := 0;
         d : dptr(0 .. Sets.N - 1);
         s : uptr(0 .. Sets.N - 1);
         -- `hash(d(s(k))) = k` if `d` has been stored at `k`
     end record;
end Sets;

package body Sets is

     function has(this : set; k : unsigned) return Boolean is
         n : unsigned renames this.n;
         s : uptr renames this.s;
         d : dptr renames this.d;
     begin
         return k < Sets.N and then s(k) < n and then hash(d(s(k))) = k;
     end has;

     procedure add(this : in out set; k : unsigned; data : t) is
         n : unsigned renames this.n;
         s : uptr renames this.s;
         d : dptr renames this.d;
     begin
         if k < Sets.N and then not this.has(k) then
             d(n) := data; s(k) := n; n := n + 1;
         end if;
     end add;

     procedure del(this : in out set; k : unsigned) is
         n : unsigned renames this.n;
         s : uptr renames this.s;
         d : dptr renames this.d;
     begin
         if this.has(k) then
             declare i : unsigned := s(k);
             begin n := n - 1; d(i) := d(n); s(hash(d(i))) := i;
             end;
         end if;
     end del;

     procedure clr(this : in out set) is
         n : unsigned renames this.n;
     begin
         n := 0;
     end clr;

end sets;

Re: Pascal Calling Convention

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message 
news:wcck4fjc99j.fsf@shell01.TheWorld.com...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>
>> I can't speak for Keith, but most of the hardware architectures that I've
>> worked on have had at least some architectual support for a "hardware"
>> stack. Not only the Push/Pop instructions of the X86 for instance, but 
>> also
>> the special SS stack segment register.
>
> True, but nobody uses the SS register in any nontrivial way, anymore.
> The segmentation stuff of 8086 is pretty much vestigial at this point.

Not relevant to this discussion, but I think that's sad, as a lot of the 
security problems inherent in buffer overflows would have been avoided by 
simply keeping separate code and data segments. That would prevent code on 
the stack from being executed. (We found a lot of problems in Janus/Ada by 
keeping the code and data segments in our DOS Extender compilers completely 
separate; it's been quite a bit harder to find those problems on Windows or 
Unix systems that don't properly separate them.) The problem with segments 
is segments that are too small, not the basic idea.

...
> "Stack" is a pretty well-understood term in computer science,

Yes, of course.

> and I think if an x86-centric person insists that "the stack"
> must be a certain way based on the hardware/architecture,
> they're the one inventing confusing terminology.

Right again. But it seems to me that is a straw man.

> Keith is trying to clarify, by calling that contiguous thing
> a "hardware stack", but I'm saying the word "hardware" doesn't
> capture the intended meaning.

It does on most architectures. I don't believe I've ever seen a modern 
architecture without some sort of Call/Return instructions. Some of them 
allow use of any register, so there isn't a dedicated stack register.

In any case, I read your reply as saying that it didn't make sense to ever 
refer to a "hardware stack", which makes no sense to me. As soon as you are 
talking about hardware or implementations, you are talking in a 
target-specific way, so it doesn't make much sense to make any 
generalizations. It makes perfect sense to talk about a hardware stack on an 
X86; if you are talking about some other target, maybe not.

                                     Randy.

Re: Pascal Calling Convention

[Hyman Rosen]

On 3/28/2011 6:08 PM, Adam Beneschan wrote:
> On top of that, I don't see why anyone would prefer this over the
> trivial structure that just allocates N bytes, initializes them to 0,
> and sets a byte to 1 to add an element to the set, etc.  That
> structure has non-constant initialization, but so what?
> Initialization will only take place once for a set; the other
> operations are likely to be performed a lot more, and your code
> performs multiple indexed accesses for every operation instead of just
> one.  And the initialization can often be done with a single machine
> instruction.

I didn't invent this data structure - I came across it in a paper and
kept track of it because it made for a very good interview question.
It's a structure no one has ever seen before, it's easy to describe
and it's easy to program the operations. (Needless to say, many of the
people to whom I've given the exercise fail miserably.)

And it's a good program to keep at hand to serve as a counterexample
when programming languages want access to uninitialized data to be
undefined behavior. It's more sensible to regard such data as having
arbitrary but fixed values, subject to a validity check.

The particular need described in the paper was for a kind of graph
where sets of nodes needed to be created and torn down quickly, and
where such a set could potentially have millions of members while it
typically only had a handful. They needed to avoid the initialization
cost of setting many elements to zero, and this is the structure they
invented. (In any case, you can't tell someone to go use an O(N) data
structure when they've told you they want an O(1) one.)

Re: Pascal Calling Convention

[Hyman Rosen]

On 3/28/2011 6:08 PM, Adam Beneschan wrote:
> I don't see how any compiler could reasonably
> detect that the code is going to read a value that hasn't been set,
> given that such reads are reads of array elements using indexes that
> aren't known at compile time.

If the language rules say it's undefined behavior, I had better not
just go ahead and do it anyway, hoping that the compiler won't notice!

> On top of that, I don't see why anyone would prefer this over the
> trivial structure that just allocates N bytes, initializes them to 0,
> and sets a byte to 1 to add an element to the set, etc.  That
> structure has non-constant initialization, but so what?

Aside from the O(1) initialization (which you cannot just dismiss as
unnecessary), this structure also provides O(n) (rather than O(N))
iteration over the members. This is actually a question I asked when
I used this for interviews - when is this structure better than the
straightforward bit-per-member version? The answer is when the typical
number of members is much smaller than the maximum number, and indeed
that was the situation described by the authors who invented this.

Re: Pascal Calling Convention

[Shark8]

On Mar 28, 8:32 pm, "Randy Brukardt" <ra...@rrsoftware.com> wrote:
> Not relevant to this discussion, but I think that's sad, as a lot of the
> security problems inherent in buffer overflows would have been avoided by
> simply keeping separate code and data segments. That would prevent code on
> the stack from being executed. (We found a lot of problems in Janus/Ada by
> keeping the code and data segments in our DOS Extender compilers completely
> separate; it's been quite a bit harder to find those problems on Windows or
> Unix systems that don't properly separate them.) The problem with segments
> is segments that are too small, not the basic idea.

...but aren't segments, in 32-bit machines, capable of doing 4GB?
But I see what you mean about data/code segment separation... though
it can
also be a source of frustration if you want to do some self-modifying
code.

Re: Pascal Calling Convention

[stefan-lucks]

On Tue, 29 Mar 2011, Georg Bauhaus wrote:

> A transliteration attempt follows, with these additions in mind.

Very nice, indeed. Here is a bare minimum version, which is closer to the 
original proposal. Note that in Ada we don't need to perform the explicit 
check for K < N, unlike C++.

pragma Profile(Ravenscar);
pragma Restrictions (No_Allocators);

generic
    type Elements is mod <>;
package USets is

    type Set is tagged private;

    function Has(This  : Set; K : Elements) return Boolean;
    -- K has been stored in This

    procedure Add(This : in out Set; K: Elements);
      -- Insert K into This. Don't do anything if K is already there.

    procedure Del(This : in out Set; K: Elements);
      -- Remove K from This. Don't do anything if K isn't there.

    procedure clr(This : in out Set);
      -- Set This to the empty set.

private
   type A_Type is array (Elements) of Elements;
   subtype Counter_Type is Integer range 0 .. Integer(Elements'Last)+1;
    type Set is tagged record
        N    : Counter_Type := 0;
        S, D : A_Type; -- if I is in Set then D(S(I))=I
    end record;
end USets;

---------

package body USets is

   function Has(This : Set; K: Elements) return Boolean is
      N: Counter_Type renames This.N;
      S: A_Type renames This.S;
      D: A_Type renames This.D;
   begin
      return Integer(S(K)) < N and then D(S(K))=K;
   end Has;

   procedure Add(This : in out Set; K: Elements) is
      N: Counter_Type renames This.N;
      S: A_Type renames This.S;
      D: A_Type renames This.D;
   begin
      if not This.Has(K) then
         D(Elements(N)) := K; S(K) := Elements(N); -- now D(S(K))=K;
         N := N + 1;
      end if;
   end Add;

   procedure Del(This : in out Set; K: Elements) is
      N: Counter_Type renames This.N;
      S: A_Type renames This.S;
      D: A_Type renames This.D;
   begin
      if This.Has(K) then
         declare
            I: Elements := S(K);
         begin
            N := N - 1;
            D(I) := D(Elements(N)); S(D(I)) := I;
         end;
      end if;
   end Del;

   procedure Clr(This : in out Set) is
      N : Counter_Type renames This.N;
   begin
      N := 0;
   end Clr;
end USets;

---------

The original C++ from Hyman Rosen was

template <unsigned N>
class set
{
    unsigned n;    // number of members in set
    unsigned d[N]; // members are in d[0..n-1]
    unsigned s[N]; // d[s[k]] == k if k is a member
    // unspecified elements of d and s are arbitrary

public:
    set() : n(0) { }
    bool has(unsigned k)
        { return k < N && s[k] < n && d[s[k]] == k; }
    void add(unsigned k)
        { if (k < N && !has(k)) { d[n] = k; s[k] = n++; }
    void del(unsigned k)
        { if (has(k)) { unsigned i = s[k]; d[i] = d[--n]; s[d[i]] = i; }
    void clr() { n = 0; }
};



-- 
------ Stefan Lucks   --  Bauhaus-University Weimar  --   Germany  ------
               Stefan dot Lucks at uni minus weimar dot de
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Pascal Calling Convention

[Hyman Rosen]

On 3/29/2011 8:23 AM, stefan-lucks@see-the.signature wrote:
> Very nice, indeed. Here is a bare minimum version, which is closer to the
> original proposal. Note that in Ada we don't need to perform the explicit
> check for K < N, unlike C++.

This <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.7319&rep=rep1&type=pdf>
is the original paper: Briggs & Torczon, "An efficient representation for sparse sets".
There's also discussion here:
<http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html>

Re: Pascal Calling Convention

[Robert A Duff]

Hyman Rosen <hyrosen@mail.com> writes:

>...This is actually a question I asked when
> I used this for interviews - when is this structure better than the
> straightforward bit-per-member version?

That's a pretty good interview question.  Much better than the
silly puzzles some folks use.  Or the infamous "tell me your
strengths and weaknesses".

I saw this data structure in a compiler textbook, and it referenced the
Briggs paper, which I have not read.  It is indeed an interesting
algorithm.  Of course, as I'm sure you know, it's completely wrong
in most higher-level languages, including Ada (in which the compiler
is allowed to raise an exception), and C++ (in which the compiler
is allowed to do anything at all).

- Bob

Re: Pascal Calling Convention

[Robert A Duff]

Hyman Rosen <hyrosen@mail.com> writes:

> And it's a good program to keep at hand to serve as a counterexample
> when programming languages want access to uninitialized data to be
> undefined behavior. It's more sensible to regard such data as having
> arbitrary but fixed values, subject to a validity check.

Just because you know of one algorithm that could use that semantics?!
(OK, I know of one other case.  Sort of.)

If I wanted to add this "feature" to Ada, I'd do so via an attribute:
T'Arbitrary_Value returns an arbitrary value of type T.  Then:

    My_Array := (1..1_000_000 => Integer'Arbitrary_Value);

can be implemented in zero machine instructions.  You really don't want
to use arbitrary values by accident.

At least with "undefined behavior", or "erroneous execution" the
compiler can have a mode that detects uninit vars at run time, which can
be useful for debugging.  GNAT has a mode that detects most uninit vars
at run time (although using uninit is no longer erroneous in Ada).

- Bob

Re: Pascal Calling Convention

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

>...The problem with segments 
> is segments that are too small, not the basic idea.

One problem with segments is that you need twice as many address
bits to address the same amount of memory.  If you give me a 64-bit
address that has a 32-bit segment number and a 32-bit offset,
they're too small, and not enough of them (for some purposes).
I'd rather have a 64-bit flat address space.  So maybe you give
me a 128-bit address.  Now there are plenty of segments and they're
plenty big, but you've hugely increased the size of all my pointer-heavy
data structures, causing all my programs to run slower.  In that case,
I still want a 64-bit flat address space.

And if you don't like buffer overruns, use any langauge that
prevents them (like Ada and many others).  Note that x86 segmentation
won't do array-bounds checking correctly, so the compiler has to
implement it in software anyway.  (Think about a packed array
of Boolean.)

>> Keith is trying to clarify, by calling that contiguous thing
>> a "hardware stack", but I'm saying the word "hardware" doesn't
>> capture the intended meaning.
>
> It does on most architectures. I don't believe I've ever seen a modern 
> architecture without some sort of Call/Return instructions.

Most RISC machines I've seen have call/ret, but they are not stack
instructions.  Call saves the return address in a register.
Ret jumps based on the content of a register.  It's up to
software to push/pop return addresses on a stack.

I'll grant you that the term "hardware stack" might make sense
in the x86 context, and some others.

>... Some of them 
> allow use of any register, so there isn't a dedicated stack register.
>
> In any case, I read your reply as saying that it didn't make sense to ever 
> refer to a "hardware stack", which makes no sense to me.

It's not what I meant.

>... As soon as you are 
> talking about hardware or implementations, you are talking in a 
> target-specific way, ...

Not at all.  The statement "All Ada implementations must use a stack
to implement procedure calls, because the semantics are FIFO."
is talking about implementations, but it's not target-specific.

Keith was just trying to clarify that that statement doesn't imply
anything about the way the stack is implemented.  He is, of course,
right.  He's also right that it needs clarification, because some
people think call/return stacks must be contiguous chunks of memory.
Or they think they always are contiguous, and there are no machines
(or languages!) where it makes sense to do otherwise.

>...so it doesn't make much sense to make any 
> generalizations.

And it's a generalization, and it makes sense, and it's even true
(that "All Ada ... stack ...").

>...It makes perfect sense to talk about a hardware stack on an 
> X86; if you are talking about some other target, maybe not.

- Bob

Re: Pascal Calling Convention

[Adam Beneschan]

On Mar 29, 11:30 am, Robert A Duff <bobd...@shell01.TheWorld.com>
wrote:
> Hyman Rosen <hyro...@mail.com> writes:
> > And it's a good program to keep at hand to serve as a counterexample
> > when programming languages want access to uninitialized data to be
> > undefined behavior. It's more sensible to regard such data as having
> > arbitrary but fixed values, subject to a validity check.
>
> Just because you know of one algorithm that could use that semantics?!
> (OK, I know of one other case.  Sort of.)
>
> If I wanted to add this "feature" to Ada, I'd do so via an attribute:
> T'Arbitrary_Value returns an arbitrary value of type T.  Then:
>
>     My_Array := (1..1_000_000 => Integer'Arbitrary_Value);
>
> can be implemented in zero machine instructions.  You really don't want
> to use arbitrary values by accident.

If that feature were added, I'd want the language to specify that the
value of the attribute must be a valid value for the subtype.  (Maybe
that's what you meant and didn't say so explicitly?)  That would still
be a no-op if every bit pattern would be a valid value, which would be
the case for Integer (or for the first subtype of a "mod 2**32" or
"mod 2**64" type on most machines, which I think would be needed to
make Hyman's example work).

                                -- Adam

Re: Pascal Calling Convention

[Randy Brukardt]

"Shark8" <onewingedshark@gmail.com> wrote in message 
news:e927347b-4f90-471a-b574-878e655eba89@34g2000pru.googlegroups.com...
On Mar 28, 8:32 pm, "Randy Brukardt" <ra...@rrsoftware.com> wrote:
>> Not relevant to this discussion, but I think that's sad, as a lot of the
>> security problems inherent in buffer overflows would have been avoided by
>> simply keeping separate code and data segments. That would prevent code 
>> on
>> the stack from being executed. (We found a lot of problems in Janus/Ada 
>> by
>> keeping the code and data segments in our DOS Extender compilers 
>> completely
>> separate; it's been quite a bit harder to find those problems on Windows 
>> or
>> Unix systems that don't properly separate them.) The problem with 
>> segments
>> is segments that are too small, not the basic idea.
>
>...but aren't segments, in 32-bit machines, capable of doing 4GB?

Right. That's why it is sad that operating systems stopped using them when 
they moved to 32-bit. In the 16-bit systems, the segments could be too 
small, which made things messy to use, but that is much less of a problem 
for 32-bit segments.

>But I see what you mean about data/code segment separation... though
>it can also be a source of frustration if you want to do some 
>self-modifying
>code.

But that's actually a feature. To do self-modifying code, you have to ask 
the OS for a read-write-execute code/data segment. The vast majority of 
programs have no good reason for doing that, so they would have no way to 
execute injected code (presuming that the compiler run-time does not include 
unused APIs). That alone would have made programs safer, by blocking most of 
the avenues that buffer overflows could have been exploited.

One could even imagine that using that API would require elevated 
permissions and signed executables (although I think that was not something 
that was worried about in 1990).

Of course, recent OSes have been trying to graft this sort of security back 
on (breaking lots of code), but that all could have been avoided if the code 
and data had been truly separate in the first place.

                              Randy.

Re: Pascal Calling Convention

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message 
news:wccy63xspih.fsf@shell01.TheWorld.com...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>
>>...The problem with segments
>> is segments that are too small, not the basic idea.
>
> One problem with segments is that you need twice as many address
> bits to address the same amount of memory.  If you give me a 64-bit
> address that has a 32-bit segment number and a 32-bit offset,
> they're too small, and not enough of them (for some purposes).
> I'd rather have a 64-bit flat address space.  So maybe you give
> me a 128-bit address.  Now there are plenty of segments and they're
> plenty big, but you've hugely increased the size of all my pointer-heavy
> data structures, causing all my programs to run slower.  In that case,
> I still want a 64-bit flat address space.

You're thinking completely wrong. You almost never would want an address of 
any arbitrary memory, so the segment is almost always implicit. All of the 
data goes into a data segment; you never have data addresses that point 
somewhere else. All of the code goes into a code segment, you never have 
code addresses that point somewhere else.

In the rare case that you need extra segments (such as implementing 
'Address), yes the addresses are a bit longer. But those cases are so rare 
that you'll hardly ever see them in practice. (Also, there is no reason for 
segment numbers to be more than 16 bits, there should never be more than a 
handful per program.) The size of System.Address in Janus/Ada was 48-bits 
(16 bit segment, 32 bit offset); we finally changed that to drop the segment 
for the Windows version just a couple of years ago because it was (very) 
occassionally causing trouble. The code generator still understands the 
48-bit type.

And the maximum segment size should always be the same as the maximum 
address space (32-bits on a 32-bit machine, 64-bits on a 64-bit machine). 
Although I think you could make an argument for a 48-bit segment size and 
16-bit segment value size on a 64-bit machine; 48-bits comes close to the 
maximum amount of memory that will be constructable in a digital machine.

> And if you don't like buffer overruns, use any langauge that
> prevents them (like Ada and many others).

One use of pragma Suppress or an interface to the OS or one bug and that 
"protection" is gone.

99% of the time, executing data is a bug. Why allow it by default?

> Note that x86 segmentation
> won't do array-bounds checking correctly, so the compiler has to
> implement it in software anyway.  (Think about a packed array
> of Boolean.)

That's not relevant to my point, which is simply that not allowing the 
execution of data in the default case would prevent almost all code 
injection attacks (usually accomplished via buffer overflows, but there are 
lots of other ways). There is no protection against clobbering data, and I 
don't think there can be any (besides the software techniques) unless the 
hardware supports very fine-grained memory management -- and that is likely 
to be far too much of a drag on performance.

...
>>... As soon as you are
>> talking about hardware or implementations, you are talking in a
>> target-specific way, ...
>
> Not at all.  The statement "All Ada implementations must use a stack
> to implement procedure calls, because the semantics are FIFO."
> is talking about implementations, but it's not target-specific.

I think it is also close to junk. The semantics are FIFO is fine, but 
anything about the underlying data structure is bogus. Unless you are 
equating FIFO with stack in all cases, which I don't agree with. A stack is 
FIFO, but I don't think that implies that all data structures that are FIFO 
are stacks.

Anyway, this is a pointless discussion. Let's go back to discussing whether 
membership is a set operation. ;-)

                      Randy.

Re: Pascal Calling Convention

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> 99% of the time, executing data is a bug. Why allow it by default?

Ah, I didn't realize you were mainly focused on that issue.
I agree 100% that executing data is usually a bug, and should
be prevented by default.

But you don't need segments for that.  Paging hardware can do it.
(Well, you don't need segments in hardware.  The O.S. concocts
something like "segments" based on paging.  And protects code.)

>> Not at all.  The statement "All Ada implementations must use a stack
>> to implement procedure calls, because the semantics are FIFO."
>> is talking about implementations, but it's not target-specific.
>
> I think it is also close to junk. The semantics are FIFO is fine, but 
> anything about the underlying data structure is bogus. Unless you are 
> equating FIFO with stack in all cases, which I don't agree with. A stack is 
> FIFO, but I don't think that implies that all data structures that are FIFO 
> are stacks.

Of course we both mean "LIFO", not "FIFO" above.

> Anyway, this is a pointless discussion. Let's go back to discussing whether 
> membership is a set operation. ;-)

OK, fair enough.  ;-)

I'd still like to hear Keith's take on all this, if he's still
listening.

- Bob

Re: Pascal Calling Convention

[Robert A Duff]

Adam Beneschan <adam@irvine.com> writes:

> If that feature were added, I'd want the language to specify that the
> value of the attribute must be a valid value for the subtype.

Yes.

>...(Maybe
> that's what you meant and didn't say so explicitly?)  That would still
> be a no-op if every bit pattern would be a valid value, which would be
> the case for Integer (or for the first subtype of a "mod 2**32" or
> "mod 2**64" type on most machines, which I think would be needed to
> make Hyman's example work).

Perhaps the feature would only be allowed on such (sub)types.
You'd need some way to declare such types.  "Type T is
at least 1..1_000_000, possibly larger, but make sure
all bit patterns are meaningful."  Or maybe require that
T'Base have this property for all integer types T.

I don't think you want this feature for floats and pointers.

Records and arrays?

But it's such a corner case, I doubt you really want this feature
at all!  ;-)

By the way, I invented this feature some years ago, when I read about
the data structure Hyman mentioned.  I said to myself, "That's
interesting.  I wonder how I'd design a high-level language in
which that thing could be written (correctly, and portably)."

- Bob

Re: Pascal Calling Convention

[Phil Clayton]

On Mar 29, 1:23 pm, stefan-lu...@see-the.signature wrote:
> The original C++ from Hyman Rosen was
>
> template <unsigned N>
> class set
> {
>     unsigned n;    // number of members in set
>     unsigned d[N]; // members are in d[0..n-1]
>     unsigned s[N]; // d[s[k]] == k if k is a member
>     // unspecified elements of d and s are arbitrary
>
> public:
>     set() : n(0) { }
>     bool has(unsigned k)
>         { return k < N && s[k] < n && d[s[k]] == k; }
>     void add(unsigned k)
>         { if (k < N && !has(k)) { d[n] = k; s[k] = n++; }
>     void del(unsigned k)
>         { if (has(k)) { unsigned i = s[k]; d[i] = d[--n]; s[d[i]] = i; }
>     void clr() { n = 0; }
>
> };

Interesting.  It's worth noting that if N is equal to the number of
keys representable by unsigned and every key is added to the set, n++
in the final add will 'overflow' because n (of type unsigned) needs to
be able to have the range 0 .. N, i.e. N + 1 distinct values.  I doubt
this would cause a problem in practice because
1. unsigned is likely to be at least 32 bits these days(?) so N will
be much smaller;
2. these are designed for sparse arrays, there is a low probability of
filling the entire array.

Clearly I'm not the first person to notice this though...

On Mar 29, 1:23 pm, stefan-lu...@see-the.signature wrote:
>    type Elements is mod <>;
>    ...
>    subtype Counter_Type is Integer range 0 .. Integer(Elements'Last)+1;

Phil

Re: Pascal Calling Convention

[Adam Beneschan]

On Mar 30, 5:50 am, Robert A Duff <bobd...@shell01.TheWorld.com>
wrote:
> Adam Beneschan <a...@irvine.com> writes:
> > If that feature were added, I'd want the language to specify that the
> > value of the attribute must be a valid value for the subtype.
>
> Yes.
>
> >...(Maybe
> > that's what you meant and didn't say so explicitly?)  That would still
> > be a no-op if every bit pattern would be a valid value, which would be
> > the case for Integer (or for the first subtype of a "mod 2**32" or
> > "mod 2**64" type on most machines, which I think would be needed to
> > make Hyman's example work).
>
> Perhaps the feature would only be allowed on such (sub)types.

Well, if this feature actually *were* added (ha), it should probably
be allowed on any discrete subtype.  Using it on a subrange wouldn't
gain you much:

   subtype T is Integer range 1 .. 100;
   type T_Array is array (natural range <>) of T;
   X : T_Array (1..100) := (others => T'Arbitrary_Value);

A compiler would most likely just generate the same code as (others =>
T'First).  But it still would be useful to have this available in case
T is a generic formal type.

                           -- Adam

Re: Pascal Calling Convention

[Robert A Duff]

Adam Beneschan <adam@irvine.com> writes:

> Well, if this feature actually *were* added (ha), it should probably
> be allowed on any discrete subtype.  Using it on a subrange wouldn't
> gain you much:
>
>    subtype T is Integer range 1 .. 100;
>    type T_Array is array (natural range <>) of T;
>    X : T_Array (1..100) := (others => T'Arbitrary_Value);
>
> A compiler would most likely just generate the same code as (others =>
> T'First).  But it still would be useful to have this available in case
> T is a generic formal type.

What would it do for "subtype T is Integer range 1..0;"?  ;-)

- Bob

Re: Pascal Calling Convention

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message 
news:wccei5o233l.fsf@shell01.TheWorld.com...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>
>> 99% of the time, executing data is a bug. Why allow it by default?
>
> Ah, I didn't realize you were mainly focused on that issue.
> I agree 100% that executing data is usually a bug, and should
> be prevented by default.
>
> But you don't need segments for that.  Paging hardware can do it.
> (Well, you don't need segments in hardware.  The O.S. concocts
> something like "segments" based on paging.  And protects code.)

True enough, but I was focused primarily on the existing capabilities of the 
80386 (which is the CPU that most of the current OSes started on). This chip 
had segments with the "right" permissions, while the paging stuff had little 
permission control. (And no OS or OS extension that I know of in that time 
frame used that permission control.)

Also, I think there is a (minor) advantage to separate code and data address 
spaces, in that makes it harder still to do something that fools the OS into 
executing data. If you have no executable access to the data address space, 
there is no possible bug that would allow data execution.

In any event, this was completely obvious to me even back in the days of the 
DOS Extender. All of the DOS Extenders gave you a totally flat address 
space, but they all also had a way to get a new segment. So I had Janus/Ada 
create a stub data segment in the executable file, and the first thing the 
runtime did was create a new (full-size) data segment, moved the stack 
there, and removed all references to the writable code segment registers. 
This helped fix a lot of bugs, because wild execution trapped instantly, 
rather than running for quite a while before crashing. It's too bad I can't 
do that on Windows, because I have some problems that I've been unable to 
debug with wild code execution -- I haven't been able to identify where it 
goes wrong.

                                   Randy.

Re: Pascal Calling Convention

[tmoran]

> (detectting executing data as code) It's too bad I can't
> do that on Windows, because I have some problems that I've been unable to
> debug with wild code execution -- I haven't been able to identify where it
> goes wrong.
   What does software/hardware Data Excecution Prevention do on Vista etc?
(Other than generate spurious errors.)

Re: Pascal Calling Convention

[Robert A Duff]

tmoran@acm.org writes:

>    What does software/hardware Data Excecution Prevention do on Vista etc?

I believe DEP causes the operating system to set per-page protections so
data is not executable, by default.  The checks are done in hardware.
And of course code pages are not writeable by default.  A process can
request other page protections.  Requires newer versions of x86.

Linux can do the same thing.

This is pretty old technology.  x86 is just recently catching up.

> (Other than generate spurious errors.)

We eliminated almost all trampolines from GNAT, so newer versions
won't cause such spurious errors.

- Bob

Re: Pascal Calling Convention

[Phil Clayton]

On Mar 30, 2:42 pm, Phil Clayton <phil.clay...@lineone.net> wrote:
> On Mar 29, 1:23 pm, stefan-lu...@see-the.signature wrote:
>
>
>
> > The original C++ from Hyman Rosen was
>
> > template <unsigned N>
> > class set
> > {
> >     unsigned n;    // number of members in set
> >     unsigned d[N]; // members are in d[0..n-1]
> >     unsigned s[N]; // d[s[k]] == k if k is a member
> >     // unspecified elements of d and s are arbitrary
>
> > public:
> >     set() : n(0) { }
> >     bool has(unsigned k)
> >         { return k < N && s[k] < n && d[s[k]] == k; }
> >     void add(unsigned k)
> >         { if (k < N && !has(k)) { d[n] = k; s[k] = n++; }
> >     void del(unsigned k)
> >         { if (has(k)) { unsigned i = s[k]; d[i] = d[--n]; s[d[i]] = i; }
> >     void clr() { n = 0; }
>
> > };
>
> Interesting.  It's worth noting that if N is equal to the number of
> keys representable by unsigned

Except that it can't be because N is also of type unsigned so there
can't be 'overflow' either. I didn't see that in the template
argument. Ignore me.

Phil

Re: Pascal Calling Convention

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message 
news:wccsju4i6f2.fsf@shell01.TheWorld.com...
> tmoran@acm.org writes:
>
>>    What does software/hardware Data Excecution Prevention do on Vista 
>> etc?
>
> I believe DEP causes the operating system to set per-page protections so
> data is not executable, by default.  The checks are done in hardware.
> And of course code pages are not writeable by default.  A process can
> request other page protections.  Requires newer versions of x86.

Right. This moves the permissions from the segments (where Intel had put 
them) to the page table, because OS writers didn't want to take advantage of 
the possibilities of segments. (We wouldn't need 64-bit OSes, with all of 
their incompatibilities, anywhere near as soon had the OSes used segments in 
the first place.)

The two approaches are equivalent, except for the irrational fears of 
certain developers. The effect was to make the X86 much less safe that it 
could have been.

>> (Other than generate spurious errors.)
>
> We eliminated almost all trampolines from GNAT, so newer versions
> won't cause such spurious errors.

Glad to hear it. I turned on DEP on my machine, since I knew that Janus/Ada 
couldn't cause problems with it (and if it did, I wanted to fix them). But I 
couldn't run GNAT very successfully, so I had to turn it back off.

                       Randy.