daniels@biles.com (Brad Daniels) writes:

>Fergus Henderson <fjh@mundil.cs.mu.OZ.AU> wrote:
>...
>>The only limitation is that with operating systems that are
>>extremely uncooperative, you need to use a trampoline stack
>>whose size must be determined at compile time.  However, many C
>>implementations for operating systems such as DOS require that
>>the size of the normal function call stack be determined at
>>compile time, and users have been able to cope with this, so
>>it doesn't seem like a crippling restriction.
>
>I assume you mean "trampoline heap" rather than "trampoline stack",
>yes?  The pool of pre-generated trampolines acts much more like a
>heap than a stack, since you have a fixed number, and the lifetime of
>each may be as long as the program.

No, I meant a stack, but I was thinking about nested function closures;
you need a trampoline heap if you want object closures rather than just
nested function closures.

>Particularly in applications which
>use trampolines extensively for declaring callbacks (which tend to exist
>for most of the program's lifetime), the pool could get to be unpleasantly
>large.

Sure, and for highly recursive programs, a fixed-size call stack would be
equally unpleasant.  Yet we seem to have been able to put up with fixed-size
call stacks on DOS.  It's a quality of implementation issue.

Remember the fixed size trampoline heap limit would only need to apply if
all of the following conditions hold:

 1.  The operating system doesn't support mapping the same
     code page into multiple parts of the address space.
AND
 2.  The operating system doesn't support dynamic link libraries
AND
 3.  The operating system doesn't support dynamic code generation.

Can anyone name a single platform for which all of those conditions
hold?  I can't.

>Don't get me wrong;  I'd really like to see some kind of bound function
>pointers, but I'm not convinced a static pool of pregenerated trampolines
>is the right answer, and I don't know how many platforms would support
>dynamic code generation at all, let alone efficiently.

Every platform that GNU C runs on except for ULTRIX supports dynamic
code generation, or so I've heard.

If the platform supports dynamic code generation, but doesn't do it
efficiently, then as you suggested we can use a trampoline heap and do
the dynamic code generation only when we need to allocate another page
of trampolines.

>I'm still not sure that would cover all environments, though.

For say 99% of environments, there is a solution that would work just
fine, with reasonable efficiency and no fixed limits.  For the
remaining 1% of environments where you have a really uncooperative
operating system, we have to put up with a slightly unpleasant fixed
limit.  Big deal!

--
Fergus Henderson - fjh@munta.cs.mu.oz.au

fjh@munta.cs.mu.OZ.AU (Fergus Henderson) writes:
>Every platform that GNU C runs on except for ULTRIX supports dynamic
>code generation, or so I've heard.

The GNU C port to SCO Xenix doesn't support dynamic code generation
either.  SCO Xenix will let you generate code dymamically, but the
technique is more than a little obscure.

      Ross Ridge

kanze@us-es.sel.de (James Kanze) writes:

>fjh@munta.cs.mu.OZ.AU (Fergus Henderson) writes:
>
>|> Could you be more specific about how the 386 in protected mode doesn't
>|> support code generation at run-time?
>
>At any rate, I should have been clearer.  It is obviously possible
>*if* the OS co-operates; map two separate segments (one writeable, one
>executable) to the same physical address.

OK, so code generation at runtime _is_ fine as far as the hardware
is concerned.

>And of course, if the OS doesn't co-operate, you are sunk anyway.

No, that's not correct.  As I said in my previous post:

>|> There is an alternative implementation that maintains compatibility
>|> with C function pointers and yet doesn't require creating code at
>|> runtime.  (It helps if your OS allows you to map the same page of
>|> read-only code to multiple pages in the address space, but even
>|> this is not essential.)

[...]
>it is considered undesirable to adapt a standard that cannot be
>implemented on *all* architectures (under the existing OS, and even
>using the existing linker!).

I repeat, *doesn't require creating code at runtime*.
The alternative implementation to which I was referring _can_ be
implemented on all architectures, as far as I am aware.

The only limitation is that with operating systems that are
extremely uncooperative, you need to use a trampoline stack
whose size must be determined at compile time.  However, many C
implementations for operating systems such as DOS require that
the size of the normal function call stack be determined at
compile time, and users have been able to cope with this, so
it doesn't seem like a crippling restriction.

--
Fergus Henderson - fjh@munta.cs.mu.oz.au

In article <9407521.17643@mulga.cs.mu.oz.au>,
Fergus Henderson <fjh@mundil.cs.mu.OZ.AU> wrote:
...
>The only limitation is that with operating systems that are
>extremely uncooperative, you need to use a trampoline stack
>whose size must be determined at compile time.  However, many C
>implementations for operating systems such as DOS require that
>the size of the normal function call stack be determined at
>compile time, and users have been able to cope with this, so
>it doesn't seem like a crippling restriction.

I assume you mean "trampoline heap" rather than "trampoline stack",
yes?  The pool of pre-generated trampolines acts much more like a
heap than a stack, since you have a fixed number, and the lifetime of
each may be as long as the program.  Particularly in applications which
use trampolines extensively for declaring callbacks (which tend to exist
for most of the program's lifetime), the pool could get to be unpleasantly
large.

Don't get me wrong;  I'd really like to see some kind of bound function
pointers, but I'm not convinced a static pool of pregenerated trampolines
is the right answer, and I don't know how many platforms would support
dynamic code generation at all, let alone efficiently.  Actually, I suppose
the efficiency concern could be handled by making a dynamically extensible
trampoline pool on architectures that support dynamic code generation.  It
might also be able to make the pool extensible by dynamically loading share-
able librariess or DLL's.  I'm still not sure that would cover all environ-
ments, though.

- Brad
------------------------------------------------------------------------
+ Brad Daniels                  | "Let others praise ancient times;    +
+ Biles and Associates          |  I am glad I was born in these."     +
+ These are my views, not B&A's |           - Ovid (43 B.C. - 17 A.D.) +
------------------------------------------------------------------------

kanze@us-es.sel.de (James Kanze) writes:

>g2devi@cdf.toronto.edu (Robert N. Deviasse) writes:
>
>|>           void register_dispatcher(int windowID,void (*)(Message));

>|> Using closures we could write:
>
>|>     class Window {
>|>          int windowID;
>|>          virtual void dispatcher(Message);
>|>          // ...
>|>          void register() {
>|>               void callback(Message msg) { return dispatcher(msg); }
>|>               register_dispatcher(windowID,callback);
>|>          }
>|>     };
>
>|> Now all messages to windowID are forwarded to the object associated with
>|> windowID. This, I don't believe can be simulated using another current
>|> C++ idiom.
>
>I don't believe that it would even be possible to implement this.
>In principle, the function 'callback' must be able to access the local
>variables/parameters of 'register'.  (If not, there is no real reason
>other than scope to make it nested.)  These variables/parameters are
>in fact in a stack frame, or some similar record.  On returning from
>register, this frame disappears.

Sure it is.  I think CLOS does something like that.  But in the general
case it requires garbage collection of (some) stack frames, or the
equivalent - which is something that won't happen in C++.

Probably Robert Deviasse was thinking of code like this:

     class Window {
          int windowID;
          virtual void dispatcher(Message);
          void callback(Message msg) { return dispatcher(msg); }
          void register() {
               register_dispatcher(windowID, callback);
          }
     };

Here the expression `callback' is an abbrevation for `&(this->callback)',
and creates an object closure.  The space allocated for the closure
can be deallocated when the Window is destroyed.

>In the particular case in question, the only 'parameter' of interest
>is the this pointer; this *can* be simulated by means of a struct
>containing a Window* and a void (Window::*)( Message ).
>
>Of course, the window system will not understand this new type of
>pointer, nor be able to call a function through it.  But since some
>architectures will *require* a new kind of pointer to implement
>closure (the alternative requires generating code at run-time, not
>supported by, amongst others, 80386+ in protected mode),

Could you be more specific about how the 386 in protected mode doesn't
support code generation at run-time?  GNU C for Linux, DOS, OS/2, SysV
etc. produces code that runs in protected mode and which generates
trampoline code at run-time.  Last time I looked, I think it worked
fine.  What's the problem?

>any support
>of this will require adding this new pointer type (or changing the
>format of existing pointers), and the window system won't understand
>this either.

There is an alternative implementation that maintains compatibility
with C function pointers and yet doesn't require creating code at
runtime.  (It helps if your OS allows you to map the same page of
read-only code to multiple pages in the address space, but even
this is not essential.)

--
Fergus Henderson - fjh@munta.cs.mu.oz.au

In article <9406621.16679@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU
(Fergus Henderson) writes:

|> >Of course, the window system will not understand this new type of
|> >pointer, nor be able to call a function through it.  But since some
|> >architectures will *require* a new kind of pointer to implement
|> >closure (the alternative requires generating code at run-time, not
|> >supported by, amongst others, 80386+ in protected mode),

|> Could you be more specific about how the 386 in protected mode doesn't
|> support code generation at run-time?  GNU C for Linux, DOS, OS/2, SysV
|> etc. produces code that runs in protected mode and which generates
|> trampoline code at run-time.  Last time I looked, I think it worked
|> fine.  What's the problem?

I have no real experience with the 386 in protected mode, so I am just
going on what I have been told.  I have been told that a segment
cannot be both executable and writable.

At any rate, I should have been clearer.  It is obviously possible
*if* the OS co-operates; map two separate segments (one writeable, one
executable) to the same physical address.  And of course, if the OS
doesn't co-operate, you are sunk anyway.  Even if the hardware does
allow it, only the OS can set up a segment that is both protected and
writable.

Of course, under DOS, there is no problem, since you aren't in
protected mode to begin with.  I'm not sure how the various extenders
do this.  (Funny, I once actually wrote assembler code to change
modes, and never really looked at what was going on.)

I am surprised by SysV though.  I would have thought that the standard
configuration for Unix had a write-protected 'text' segment, and all
of the other segments non-executable.  Again, though, just supposition
on my part.  (It's the way I'd have done it.)

|> >any support
|> >of this will require adding this new pointer type (or changing the
|> >format of existing pointers), and the window system won't understand
|> >this either.

|> There is an alternative implementation that maintains compatibility
|> with C function pointers and yet doesn't require creating code at
|> runtime.  (It helps if your OS allows you to map the same page of
|> read-only code to multiple pages in the address space, but even
|> this is not essential.)

I know of the alternative implementations, using trampolines.  I
doubt, however, that the committee would accept any proposal which
would *require* such an implementation.  It seems to be common
knowledge (whether true or not is another story) that there exist
implementations where memory cannot be both writable and executable,
and it is considered undesirable to adapt a standard that cannot be
implemented on *all* architectures (under the existing OS, and even
using the existing linker!).
--
James Kanze                       email: kanze@lts.sel.alcatel.de
GABI Software, Sarl., 8 rue du Faisan, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                   -- Beratung in industrieller Datenverarbeitung

In article <1994Mar1.115904.5945@cdf.toronto.edu>
g2devi@cdf.toronto.edu (Robert N. Deviasse) writes:

|> What John is refering to is something different. True function closures
|> are extremely useful in callbacks. Let me give you an example. Suppose
|> and event-oriented OS (like Windows+DOS or X+UNIX or ...) has a function:
|>           void register_dispatcher(int windowID,void (*)(Message));
|> This function registers the event-dispatcher for the window identified using
|> windowID. Using closures we could write:

|>     class Window {
|>          int windowID;
|>          virtual void dispatcher(Message);
|>          // ...
|>          void register() {
|>               void callback(Message msg) { return dispatcher(msg); }
|>               register_dispatcher(windowID,callback);
|>          }
|>     };

|> Now all messages to windowID are forwarded to the object associated with
|> windowID. This, I don't believe can be simulated using another current
|> C++ idiom.

I don't believe that it would even be possible to implement this.

In principle, the function 'callback' must be able to access the local
variables/parameters of 'register'.  (If not, there is no real reason
other than scope to make it nested.)  These variables/parameters are
in fact in a stack frame, or some similar record.  On returning from
register, this frame disappears.

In the particular case in question, the only 'parameter' of interest
is the this pointer; this *can* be simulated by means of a struct
containing a Window* and a void (Window::*)( Message ).

Of course, the window system will not understand this new type of
pointer, nor be able to call a function through it.  But since some
architectures will *require* a new kind of pointer to implement
closure (the alternative requires generating code at run-time, not
supported by, amongst others, 80386+ in protected mode), any support
of this will require adding this new pointer type (or changing the
format of existing pointers), and the window system won't understand
this either.
--
James Kanze                       email: kanze@lts.sel.alcatel.de
GABI Software, Sarl., 8 rue du Faisan, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                   -- Beratung in industrieller Datenverarbeitung

In article <KANZE.94Mar3210706@slsvhdt.us-es.sel.de> kanze@us-es.sel.de (James Kanze) writes:
>In article <1994Mar1.115904.5945@cdf.toronto.edu>
>g2devi@cdf.toronto.edu (Robert N. Deviasse) writes:
>
>|> What John is refering to is something different. True function closures
>|> are extremely useful in callbacks. Let me give you an example. Suppose
>|> and event-oriented OS (like Windows+DOS or X+UNIX or ...) has a function:
>|>           void register_dispatcher(int windowID,void (*)(Message));
>|> This function registers the event-dispatcher for the window identified using
>|> windowID. Using closures we could write:
>
>|>     class Window {
>|>          int windowID;
>|>          virtual void dispatcher(Message);
>|>          // ...
>|>          void register() {
>|>               void callback(Message msg) { return dispatcher(msg); }
>|>               register_dispatcher(windowID,callback);
>|>          }
>|>     };
>
>|> Now all messages to windowID are forwarded to the object associated with
>|> windowID. This, I don't believe can be simulated using another current
>|> C++ idiom.
>
>I don't believe that it would even be possible to implement this.
>
>In principle, the function 'callback' must be able to access the local
>variables/parameters of 'register'.  (If not, there is no real reason
>other than scope to make it nested.)  These variables/parameters are
>in fact in a stack frame, or some similar record.  On returning from
>register, this frame disappears.
>
>In the particular case in question, the only 'parameter' of interest
>is the this pointer; this *can* be simulated by means of a struct
>containing a Window* and a void (Window::*)( Message ).
>
>Of course, the window system will not understand this new type of
>pointer, nor be able to call a function through it.  But since some
>architectures will *require* a new kind of pointer to implement
>closure (the alternative requires generating code at run-time, not
>supported by, amongst others, 80386+ in protected mode), any support
>of this will require adding this new pointer type (or changing the
>format of existing pointers), and the window system won't understand
>this either.

What you say is true if the closures are of limitted extent (allocated on
the stack), but not if the closures are of unlimitted extent (allocated on
the heap). For closures of unlimitted extent, you need some form of
garbage collection, or be content with memory leaks.


Basically, in the case of unlimitted extent, each time you take the address
of a closure, you generate the following heap object:
         struct Closure_with_Activation_Record {
            Closure_Function* actual_closure_pointer;
            ActivationRecord  data_used_by_the_closure;
         };

Then, you can use the actual_closure_pointer as a regular function pointer
-- the actual_closure_pointer uses the associated data_used_by_the_closure
as an activation record. If the function is a nonrecursive inlined function,
this is all that's needed to attach the closure pointer to it's activation
record (you need to generate one of these for each pointer to an "instance"
of the closure). However, if the function is not, one more level of
indirection is required since you don't have access to the source code of
the actual closure to attach the activation record.

Basically, all you need to do is to define a function that know where it's
"static" (from it's perspective) activation record is. Each "instance" of
the closure is associated with only one such "static" activation record.
It's a little difficult to explain/understand, but if you draw a few pictures
and experiment a bit it should be clear what really needs to be done.



Adding the keywords "limitted" to denote closures of limitted extent, and
"closure" to help qualify pointers to closures would increase the chances
for optimization so that let levels of indirection can be decreased in certain
cases.

Of course, this is a lot of extra trouble for the C++ implementor and since
it more or less requires garbage collection also be added to the language
(if you want to have unlimitted extent), it's no surprise that closures
haven't been accepted into the working paper. However, I do believe that
in the next revision of the language both will be accepted since both can
be extremely valuable and there is quite a bit of experience in these two
language features.

>--
>James Kanze                       email: kanze@lts.sel.alcatel.de
>GABI Software, Sarl., 8 rue du Faisan, F-67000 Strasbourg, France
>Conseils en informatique industrielle --
>                   -- Beratung in industrieller Datenverarbeitung



Take care
    Robert

--
/----------------------------------+------------------------------------------\
| Robert N. Deviasse               |"If we have to re-invent the wheel,       |
| EMAIL: g2devi@cdf.utoronto.ca    |  can we at least make it round this time"|
+----------------------------------+------------------------------------------/

In article <CLq2Fu.Jt3@ucc.su.OZ.AU>, maxtal@physics.su.OZ.AU (John Max Skaller) writes:
|>
|>  However, this doesnt apply to all rejected extensions.
|> Some were rejected for reasons that dont apply to vendors,
|> in particular "not enough time" and "no existing practice".
|>
|>  Some of the extensions I proposed I'd plead with
|> vendors to implement, exactly so we can get enough experience
|> with them to Standardise them in the next Standard.
|>
|>  These include nested functions

My response to this - blech.  Some of the worst spagetti code I have
ever seen otuside of Fortran has been in Pascal, due to its nested
functions.  That is the code was *less* understandable because of
the use of nested functions, not more so.  Just figuring out what the
code *does* and *where* is a major chore in these programs - to the
extent that I hate having to update them.

|> and object closures,
|> for example, which are easy to implement, extremely useful,

Well, object closures may be useful, but I do not see any use for
nested functions except writing obscure code.

--
swf@elsegundoca.ncr.com  sarima@netcom.com

The peace of God be with you.

In article <CLq2Fu.Jt3@ucc.su.OZ.AU>, maxtal@physics.su.OZ.AU (John Max Skaller) writes:
>  Some of the extensions I proposed I'd plead with
> vendors to implement, exactly so we can get enough experience
> with them to Standardise them in the next Standard.
>
>  These include nested functions

I believe C++ already supports nested functions. This code:

    int main () {
        struct { int nested_func () {return 0;} } foo;
        return foo.nested_func();
    }

compiles and runs fine on my machine. I wish the syntax weren't so
odd though.

> and object closures,
> for example, which are easy to implement, extremely useful,

I agree. Except maybe with the "easy to implement" part - that
discussion's gone around and around here before.

garry

--
Garry Wiegand --- garry@ithaca.com --- Ithaca Software, Alameda, California

In article <CLz7x9.81r@ithaca.com>, garry@ithaca.com (Garry Wiegand) writes:

> I believe C++ already supports nested functions. This code:

>     int main () {
>         struct { int nested_func () {return 0;} } foo;
>         return foo.nested_func();
>     }

> compiles and runs fine on my machine. I wish the syntax weren't so
> odd though.

This isn't a `proper' nested function, you've just declared the class
inside a restricted scope.  Try compiling:

 int main (int argc, char *argv[]) {
  struct {
   int nf() { return argc; }
  } foo;
  return foo.nf();
 }

The function cannot access the automatic variables or the arguments of
main.  A `real' nested function would be able to do precisely this.
For instance:

 #include <stdio.h>
 int main (int argc, char**argv) {
  int nf () { return argc; }
  printf("%d\n",nf());
  return 0;
 }

compiles under gcc, which supports nested functions as an extension to C.

-- Olaf Weber

In article <CLzF7z.IGC@cwi.nl> olaf@cwi.nl (Olaf Weber) writes:
>In article <CLz7x9.81r@ithaca.com>, garry@ithaca.com (Garry Wiegand) writes:
>
>> I believe C++ already supports nested functions. This code:
>
>>     int main () {
>>         struct { int nested_func () {return 0;} } foo;
>>         return foo.nested_func();
>>     }
>
>> compiles and runs fine on my machine. I wish the syntax weren't so
>> odd though.
>
>This isn't a `proper' nested function, you've just declared the class
>inside a restricted scope.  Try compiling:
>
> int main (int argc, char *argv[]) {
>  struct {
>   int nf() { return argc; }
>  } foo;
>  return foo.nf();
> }
>
>The function cannot access the automatic variables or the arguments of
>main.  A `real' nested function would be able to do precisely this.
>For instance:
>
> #include <stdio.h>
> int main (int argc, char**argv) {
>  int nf () { return argc; }
>  printf("%d\n",nf());
>  return 0;
> }
>
>compiles under gcc, which supports nested functions as an extension to C.

But this does work:

 #include <stdio.h>
 int main (int argc, char**argv) {
                struct _ {
     _(int& ac,char**& av) : ac(argc), av(argv) {}
     int& argc;
     char**&argv;

     int nf () { return argc; }
     int nv () { return argv; }
  } nested(argc,argv);

  printf("%d\n",nested.nf());
  return 0;
 }

It's ugly and error-prone but it works.

What John is refering to is something different. True function closures
are extremely useful in callbacks. Let me give you an example. Suppose
and event-oriented OS (like Windows+DOS or X+UNIX or ...) has a function:
          void register_dispatcher(int windowID,void (*)(Message));
This function registers the event-dispatcher for the window identified using
windowID. Using closures we could write:

    class Window {
         int windowID;
         virtual void dispatcher(Message);
         // ...
         void register() {
              void callback(Message msg) { return dispatcher(msg); }
              register_dispatcher(windowID,callback);
         }
    };

Now all messages to windowID are forwarded to the object associated with
windowID. This, I don't believe can be simulated using another current
C++ idiom.

>
>-- Olaf Weber

Take care
    Robert

--
/----------------------------------+------------------------------------------\
| Robert N. Deviasse               |"If we have to re-invent the wheel,       |
| EMAIL: g2devi@cdf.utoronto.ca    |  can we at least make it round this time"|
+----------------------------------+------------------------------------------/