Shared Generic Instance Code

Shared Generic Instance Code

[david scott gibson]

Hi.  Could someone summarize the advantages and disadvantages of
having an Ada compiler that when compiling generic units generates
code that may be shared by multiple instances?  On the negative side,
I suspect that it increases compiler complexity and could result in
slower executables.  On the positive side, it could reduce the size of
executables and perhaps reduce the amount of recompilation in system
generation.  Are there other issues such as interaction with other
Ada language features or the presumed utility of code sharing, that
make one approach more attractive than the other?

Dave

Re: Shared Generic Instance Code

[Robert A Duff]

In article <5hrkhkINN9ip@snoopy.cis.ohio-state.edu>,
david scott gibson <dgibson@snoopy.cis.ohio-state.edu> wrote:
>Hi.  Could someone summarize the advantages and disadvantages of
>having an Ada compiler that when compiling generic units generates
>code that may be shared by multiple instances? ...

Well, you pretty much listed the trade-offs.

As far as implementation complexity: Probably the easiest thing is to
macro-expand.  Second easiest is to always share.  I don't think that's
a lot harder -- you just thunk-ize everything imaginable.  But
always-share is extremely inefficient in some cases.  Most complex is of
course to *sometimes* share.  This is of course the most efficient,
because you can make the trade-offs based on the individual situation.
For example, suppose you have a generic with a "type T is range <>;"
formal.  The best thing might be to create one copy of the code for each
size of integer that gets passed in.

Ada 95 makes code sharing a little bit easier than Ada 83, because the
contract model is fixed.

One thing that makes code-sharing hard is exceptions: if inside the
generic, you declare an exception, then the semantics is that each
instance has a distinct exception.  That's a bit of a pain if you're
sharing code.  The Ada 9X project considered allowing such exceptions to
all be lumped into one, but that idea was rejected due to upward
incompatibility.

Ada 95 has several rules that are specifically intended to help out with
code sharing.  There are comments about that in the AARM.  For example,
the rule that says, if you say P'Access inside a generic body, and P is
declared inside that same body, then the resulting access value can't
escape to the outside.  (The workaround is to declare P in the private
part.)

It is essentially impossible (IMHO) to share code for the *spec* of a
generic.  When I talk about code sharing, I mean sharing code for the
bodies of instances.

One issue with code-sharing is rep clauses.  Suppose you have a generic
formal type with discriminants.  If the actual type has a rep clause
that puts the discriminants in some weird place, then the instance is
supposed to obey that.  So you can't code-share, unless you're willing
to pass in information about the layout, and have the generic use that
information when referencing the discriminants.  E.g. pass in a thunk.
That's inefficient.  Better to share only in the usual case, where there
is no rep clause on the actual.  But that adds complexity to the
compiler.

It's unfortunate that all compilers don't take the same view of sharing,
because it really hurts portability.  There are some styles of generic
usage that work well if you can code-share, but generate horrendously
huge executables if not, making those styles impractical on some
compilers.

At least for Ada 83, there exist compilers that always share, and that
never share, and that sometimes share.  In the sometimes-share cases,
there are various restrictions on what can be shared, different for
different compilers.

- Bob

Re: Shared Generic Instance Code

[Robert Dewar]

Bob said

<<As far as implementation complexity: Probably the easiest thing is to
macro-expand.  Second easiest is to always share.  I don't think that's
a lot harder -- you just thunk-ize everything imaginable.  But
always-share is extremely inefficient in some cases.  Most complex is of
course to *sometimes* share.  This is of course the most efficient,
because you can make the trade-offs based on the individual situation.
For example, suppose you have a generic with a "type T is range <>;"
formal.  The best thing might be to create one copy of the code for each
size of integer that gets passed in.>>


Note that the *sometimes* share approach is what DEC implements, and also
what their patent is about.

Re: Shared Generic Instance Code

[Nick Roberts]

Robert A Duff <bobduff@world.std.com> wrote in article
<E7zEos.w3@world.std.com>...
> In article <5hrkhkINN9ip@snoopy.cis.ohio-state.edu>,
> david scott gibson <dgibson@snoopy.cis.ohio-state.edu> wrote:
> >Hi.  Could someone summarize the advantages and disadvantages of
> >having an Ada compiler that when compiling generic units generates
> >code that may be shared by multiple instances? ...
> 
> Well, you pretty much listed the trade-offs.
[snip]

Don't get confused between 'thunking' and mere indirect jumping/calling. A
thunk is where a direct jump/call vector is replaced at runtime (and is
thus a one-time thing per execution). I think what you are suggesting is
just passing in jump/call vectors, which would be jumped/called to by an
indirect jump/call instruction. The vectors could change (by being passed
in as hidden parameters) for each instantiation.

Nick.

Re: Shared Generic Instance Code

[Robert A Duff]

In article <01bc4155$221728e0$2dfb82c1@xhv46.dial.pipex.com>,
Nick Roberts <Nick.Roberts@dial.pipex.com> wrote:
>Don't get confused between 'thunking' and mere indirect jumping/calling. A
>thunk is where a direct jump/call vector is replaced at runtime (and is
>thus a one-time thing per execution).

I don't think that's right.  I once spoke with Mike Woodger about this
(around 1992 or so).  He was involved in the original Algol 60, and I
think that's where the term "thunk" originated.  Algol 60 has
call-by-name, so if you pass a parameter to a procedure, let's say the
formal is X, and the actual is A[I], then "Y := X;" reevaluates the
value of A[I], and "X := Y" reevaluates the address of A[I].  Note that
I might have changed in the meantime, or might be a function call that
returns different results each time.  My understanding is that the
"thunk" was a *pair* of pointers-to-procedures, used to implement
call-by-name.  One procedure for getting the value, and one for getting
the address, of the actual parameter.

I believe the term "thunk" then mutated, to mean a *single* procedure,
when passed (implicitly) as a parameter, by a compiler, to implicitly
implement some feature of a programming language.  That's how *I* used
the term.  I admit that it's a bastardization of the original usage, as
explained to me by Woodger.

Your usage of the term, as poking the called-address of a call
instruction (or jump instruction) is not familiar to me.  Do you have
any references that use it that way?  Let's hear some etymology for your
use of the term.

Woodger was not sure where the term came from, but he thought it might
have been the past tense of "think", as in, the compiler is generating a
piece of code that does the "thinking" about where the actual parameter
is (two pieces of code, actually), so the "thinking has been thunk."  He
had another theory about it, which I've forgotten.  I could look it up,
but that would involve digging into deep stacks of paper long since
buried in the back corners of my office.  ;-)  I think it had to do with
the sound "thunk" which was made by something-or-other.

>...I think what you are suggesting is
>just passing in jump/call vectors, which would be jumped/called to by an
>indirect jump/call instruction. The vectors could change (by being passed
>in as hidden parameters) for each instantiation.

That's exactly what I'm suggesting (except that it would always be a
call, never a jump).  Is it wrong to call that a "thunk"?

Etymology is fun.  :-)

- Bob

P.S. It just occurred to me to look up "thunk" in "The Hacker's
Dictionary", edited by Eric Raymond, foreward and cartoons by Guy
Steele, Jr.  It says:

"1. A piece of coding which provides an address".  And various other
stuff which I don't feel like typing in.  Definitions 1 and 2 match what
I'm saying; definition 3 matches what you're saying.  And then it has a
"Historical note" that more-or-less matches what I said above about
past-tense-of-think, and also, the sound "thunk".  Interesting.  I guess
we're both right.

Re: Shared Generic Instance Code

[Nick Roberts]

Robert A Duff <bobduff@world.std.com> wrote in article
<E8585p.AE7@world.std.com>...
> In article <01bc4155$221728e0$2dfb82c1@xhv46.dial.pipex.com>,
> Nick Roberts <Nick.Roberts@dial.pipex.com> wrote:
> >Don't get confused between 'thunking' and mere indirect jumping/calling.
A
> >thunk is where a direct jump/call vector is replaced at runtime (and is
> >thus a one-time thing per execution).
> 
> I don't think that's right.  I once spoke with Mike Woodger about this
> (around 1992 or so).  He was involved in the original Algol 60, and I
> think that's where the term "thunk" originated.  
[etc.]


Fascinating, Captain. Here's what I find in Craig Servin's hacker guide
(usually pretty authoritative) ...

<<<

thunk

/thuhnk/ n.



1. "A piece of coding which provides an address", according to P. Z.
Ingerman, who invented thunks in 1961 as a way of binding actual parameters
to their formal definitions in Algol-60 procedure calls. If a procedure is
called with an expression in the place of a formal parameter, the compiler
generates a thunk to compute the expression and leave the address of the
result in some standard location. 

2. Later generalized into: an expression, frozen together with its
environment, for later evaluation if and when needed (similar to what in
techspeak is called a `closure'). The process of unfreezing these thunks is
called `forcing'. 

3. A stubroutine, in an overlay programming environment, that loads and
jumps to the correct overlay. Compare trampoline. 

4. People and activities scheduled in a thunklike manner. "It occurred to
me the other day that I am rather accurately modeled by a thunk --- I
frequently need to be forced to completion." --- paraphrased from a plan
file. Historical note: There are a couple of onomatopoeic myths circulating
about the origin of this term. The most common is that it is the sound made
by data hitting the stack; another holds that the sound is that of the data
hitting an accumulator. Yet another holds that it is the sound of the
expression being unfrozen at argument-evaluation time. In fact, according
to the inventors, it was coined after they realized (in the wee hours after
hours of discussion) that the type of an argument in Algol-60 could be
figured out in advance with a little compile-time thought, simplifying the
evaluation machinery. In other words, it had `already been thought of';
thus it was christened a `thunk', which is "the past tense of `think' at
two in the morning". 


>>>

So, I knew of the latter meaning (no 2), and you of the earlier one (no 1).
We _were_ both right!

And yes, a little bit of history/culture/whatever is interesting, without
taking it _too_ seriously, perhaps!

Nick.

Re: Shared Generic Instance Code

[Robert Dewar]

Bob Duff said

<<I believe the term "thunk" then mutated, to mean a *single* procedure,
when passed (implicitly) as a parameter, by a compiler, to implicitly
implement some feature of a programming language.  That's how *I* used
the term.  I admit that it's a bastardization of the original usage, as
explained to me by Woodger.

Your usage of the term, as poking the called-address of a call
instruction (or jump instruction) is not familiar to me.  Do you have
any references that use it that way?  Let's hear some etymology for your
use of the term.>>


I don't really regard this as a mutation, to me a thunk is simply a
situation where an implicit procedure is passed. Yes Algol-60 call
by name sometimes involves two procedures for a parameter (but not
always).

I agree that the second usage is a peculiar mutation, I have never heard
it used before, whereas the first usage is widely understood.

Re: Shared Generic Instance Code

[Joel VanLaven]

david scott gibson (dgibson@snoopy.cis.ohio-state.edu) wrote:
: Hi.  Could someone summarize the advantages and disadvantages of
: having an Ada compiler that when compiling generic units generates
: code that may be shared by multiple instances?  On the negative side,
: I suspect that it increases compiler complexity and could result in
: slower executables.  On the positive side, it could reduce the size of
: executables and perhaps reduce the amount of recompilation in system
: generation.  Are there other issues such as interaction with other
: Ada language features or the presumed utility of code sharing, that
: make one approach more attractive than the other?

: Dave

Well, I'll not summarize but make one point.  Environments that use code
sharing may have an easier (more human intuitive) time with with source
level debugging.  In order to set a breakpoint generic unit n a multi-
instance environment one must know which instance.  In a code-sharing
situation the code being debugged is more intuitively linked to the
source code.  Such things can certainly be overcome, but will probably
add complexity to the compiler and/or debugger (that was supposed to be
simpler).
-- 
-- Joel VanLaven

Re: Shared Generic Instance Code

[Robert A Duff]

In article <1997Apr1.201631.28634@ocsystems.com>,
Joel VanLaven <jvl@ocsystems.com> wrote:
>...  Such things can certainly be overcome, but will probably
>add complexity to the compiler and/or debugger (that was supposed to be
>simpler).

IMHO, a debugger should let you set a breakpoint in a particular
instance, or in all instances.  It shouldn't matter whether or not the
code is shared among some or all instances.  Yes, I agree that makes the
debugger more complex than it might otherwise be.

- Bob

Re: Shared Generic Instance Code

[Robert Dewar]

Bob Duff said

<<IMHO, a debugger should let you set a breakpoint in a particular
instance, or in all instances.  It shouldn't matter whether or not the
code is shared among some or all instances.  Yes, I agree that makes the
debugger more complex than it might otherwise be.>>

We have done a fairly extensive job of surveying requirements in this area,
and what we have found is that the much more important requirement is to
breakpoint a particular instantiation. The feature for breakpointing in
all isntantiations is considered much lower priority by most of our
users ... 

Not that it is so difficult to do ...

Re: Shared Generic Instance Code

[Robert A Duff]

In article <dewar.859987657@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>Not that it is so difficult to do ...

The difficulties are different depending on whether you share code or
not.  GNAT does not.  If you want to break in a particular instance, and
its code is shared with other instances, then the debugger has to set a
breakpoint, but carefully ignore it when the current instance is the
wrong one.  Not that big of a deal, but the debugger has to know
*something* about it.

Similar to issues about debugging inlined subprograms (only backwards).

- Bob

Re: Shared Generic Instance Code

[Robert Dewar]

Joel says

<<Well, I'll not summarize but make one point.  Environments that use code
sharing may have an easier (more human intuitive) time with with source
level debugging.  In order to set a breakpoint generic unit n a multi-
instance environment one must know which instance.  In a code-sharing
situation the code being debugged is more intuitively linked to the
source code.  Such things can certainly be overcome, but will probably
add complexity to the compiler and/or debugger (that was supposed to be
simpler).>.

That's certainly a valid point. On the other hand, shared generics add a lot
of complexity to a compiler. There is also a problem of patents. DEC holds
patents on the implementation of shared generics which make it less worth
while to investigate this approach.

A programmer definitely has to be aware of whether generics are shared or not.
In most compilers, generics are not shared (Rational and RR are notable
exceptions, and the DEC 83 compiler also does a fairly complete job of
generic sharing -- see above note on patents).

If generics are NOT shared, then you want to factor generic and non-generic
code as much as possible. Have a look at how Integer_IO is done in GNAt to
see an example of this in action.

Back to debugging: it is tricky to deal with non-shared generic instances
in debuggers. In GNAT we have the first step, the compiler fully understands
source locations with respect to generics (you can see that from the
error messages, which pinpoint the template and instantiation locations).

We are working now on passing this information through to GDB, and have
some interesting ideas on how this might be done.

Robert Dewar
Ada Core Technologies

Re: Shared Generic Instance Code

[Robert A Duff]

In article <dewar.859987468@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>... There is also a problem of patents. DEC holds
>patents on the implementation of shared generics which make it less worth
>while to investigate this approach.

I'm not convinced it's a valid patent.  There was a paper written by
Gary Bray at Intermetrics, which outlines essentially the same approach,
and, I believe, predates the DEC work by several years.

- Bob

Re: Shared Generic Instance Code

[Pat Rogers]

david scott gibson <dgibson@snoopy.cis.ohio-state.edu> wrote in article
<5hrkhkINN9ip@snoopy.cis.ohio-state.edu>...
> Hi.  Could someone summarize the advantages and disadvantages of
> having an Ada compiler that when compiling generic units generates
> code that may be shared by multiple instances?  On the negative side,
> I suspect that it increases compiler complexity and could result in
> slower executables.  On the positive side, it could reduce the size of
> executables and perhaps reduce the amount of recompilation in system
> generation.  Are there other issues such as interaction with other
> Ada language features or the presumed utility of code sharing, that
> make one approach more attractive than the other?

The nature of the generic formal parameters can impose a performance
penalty when code sharing is used.  Anything that requires the
implementation to distinguish between different instances at run-time will
cost you.  Not all parameters will do so; it isn't always the case that
code sharing imposes a penalty, but for example, passing formal subprograms
parameters may do it, as well as formal objects of mode "in out",
etc.......  There's always a trade-off.  For real-time applications, this
is yet another of those cases that require you to know what you are doing,
and is often applicable when comparing languages: the ever-popular "How
come when I recode this well-understood piece of code into ADA it is so
slow?" comes time mind.  (Yes, I put the Ada in upper case on purpose
there:)

Re: Shared Generic Instance Code

[Jon S Anthony]

In article <E80ry3.Epv@world.std.com> bobduff@world.std.com (Robert A Duff) writes:

> In article <dewar.859987468@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
> >... There is also a problem of patents. DEC holds
> >patents on the implementation of shared generics which make it less worth
> >while to investigate this approach.
> 
> I'm not convinced it's a valid patent.  There was a paper written by
> Gary Bray at Intermetrics, which outlines essentially the same approach,
> and, I believe, predates the DEC work by several years.

I'm not Mr. Patent Lawyer, but I've had to look into this kind of
stuff over the last few months.  My understanding is that unless
Intermetrics or Gary Bray took out a patent for their approach (prior
to the DEC filing), the prior "written up" idea is not sufficient to
"invalidate" the patent.  Also, it seems that you can't patent an idea
per se - you have to specify how to produce a complete realization of
it.  But to be honest, this stuff seems really opaque to me...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Shared Generic Instance Code

[Robert A Duff]

In article <JSA.97Apr2153627@alexandria>, Jon S Anthony <jsa@alexandria> wrote:
>I'm not Mr. Patent Lawyer, but I've had to look into this kind of
>stuff over the last few months.  My understanding is that unless
>Intermetrics or Gary Bray took out a patent for their approach (prior
>to the DEC filing), the prior "written up" idea is not sufficient to
>"invalidate" the patent.

Really?  I was under the impression that a patent isn't valid if there's
"prior art", whether or not that prior art was patented.  Otherwise, it
seems like you could go around patenting all kinds of old inventions
that people have been using for hundreds of years.  (I'm not Mr. Patent
Lawyer either!)

There's also the issue of whether the patented thing is "obvious", which
is of course harder to prove.

>...  Also, it seems that you can't patent an idea
>per se - you have to specify how to produce a complete realization of
>it.

That agrees with my understanding.

>...But to be honest, this stuff seems really opaque to me...

Me too.

- Bob

Re: Shared Generic Instance Code

[Robert Dewar]

Jon, it is probably better if you not give legal opinions on patents unless
you have studied the area. You say

<<I'm not Mr. Patent Lawyer, but I've had to look into this kind of
stuff over the last few months.  My understanding is that unless
Intermetrics or Gary Bray took out a patent for their approach (prior
to the DEC filing), the prior "written up" idea is not sufficient to
"invalidate" the patent.  Also, it seems that you can't patent an idea
per se - you have to specify how to produce a complete realization of
it.  But to be honest, this stuff seems really opaque to me...>>

This is completely wrong, prior art does NOT have to be in the form
of patents.

Re: Shared Generic Instance Code

[Bill Keen]

In article <dewar.859987468@merv>, Robert Dewar <dewar@merv.cs.nyu.edu>
writes
> On the other hand, shared generics add a lot
>of complexity to a compiler. 

He also says Gnat does not share code between generic instances.

But surely the mechanism for shared code is already there because of
dynamic instantiations like this.

with text_io;
procedure p (x : integer) is
  subtype T is integer range 0..x;
  package Tio is new text_io.integer_io(T);
begin
  Tio.put(0);
end;

It cannot add complexity if it alredy exists.

-- 
Bill Keen

Re: Shared Generic Instance Code

[Robert Dewar]

iBill Keen said

<<But surely the mechanism for shared code is already there because of
dynamic instantiations like this.

with text_io;
procedure p (x : integer) is
  subtype T is integer range 0..x;
  package Tio is new text_io.integer_io(T);
begin
  Tio.put(0);
end;

It cannot add complexity if it alredy exists.>>

Robert replies:

Sorry, I don't get the point. Yes, GNAT can handle this case. No, there
is no special complexity in handling this case (note that the base type
of T, which is what of course is significant, is always Integer).

Shared code would add a LOT of complexity. Consider for example a generic
formal type "digits <>". Now this code must handle all possible lengths
of floating-point. 

This is easy if you have only one length (that's what the Rational compiler
used to do), or if you do everything in the longest type, and don't worry
too much that you are cheating on operatoins like Unchecked_Conversion
(that's what RR used to do),

but to do it right with multiple fpt precisions, and not introduce a big
efficiency penalty -- that's hard, and close to impossible, respectively!

Obviously any Ada compiler would be happy to share certain instantiations.
For examle, if we instantiate Integer_IO three times all for type Integer,
tha's probably pretty easy to share! However, even the mechanism to sometimes
share in the simple cases introduces a lot of complexity. In fact as Bob
pointed out, the sometimes share solution is probably harder than either
of the "pure" solutions.

Re: Shared Generic Instance Code

[Fergus Henderson]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>Shared code would add a LOT of complexity. Consider for example a generic
>formal type "digits <>". Now this code must handle all possible lengths
>of floating-point. 
>
>This is easy if you have only one length (that's what the Rational compiler
>used to do), or if you do everything in the longest type, and don't worry
>too much that you are cheating on operatoins like Unchecked_Conversion
>(that's what RR used to do),

Could you be a bit more specific about what you mean by "cheating
on operations like Unchecked_Conversion"?  In what sense did RR "cheat"?

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Shared Generic Instance Code

[Robert Dewar]

<<Could you be a bit more specific about what you mean by "cheating
on operations like Unchecked_Conversion"?  In what sense did RR "cheat"?>>

Please note that the "cheat" here is in quotations for a very good reason,
and it was probably wrong of me to use such a loaded word even in quotes.

What RR does is to simply convert everything to the longest floating-point
type, and the generic bodies semantics are entirely determined by the
resulting longest floating-point semantics.

Mostly that's fine, since the RM allows extra precision to be used at
any time, and a compiler is free to do all caculations in longest form
floating-point, as long as it does not let things go out of range (in
Ada 95, since the predefined floating-point types are unconstrained,
even that is allowed if you are using these predefined types).

But there are cases where you can definitely tell that something funny
is going on, and one is unchecked conversion. If you do an unchecked
conversion within the generic body of a formal type T whose actual is
32-bit floating-point, you will see an image of the 64-bit conversion
of the number. That's "wrong", although RR argued that the semantics
of unchecked conversion are not well enough defined to say that this
is wrong. I mildly disagree, but the important thing is that the ACVC
tests do not test this case, so the RR implementation is valid in the
sense that it can be validated. I don't think we ever really clearly
resolved the issue of whether it is conforming. It's a marginal issue
certainly.

More significant in practical terms is the cost of going to this
"widest type" approach. In the case of integer arithmetic for example,
this may mean that a simple integer division becomes a call to the
expensive runtime 64-bit software division routine, even though all
types are in fact a generic formal which in an instance is normal
32-bit integer which could be handled efficiently. The macro aproach
will of course do the efficient thing in this case.

If you follow the idea of sometimes-share, then if you have a single
generic formal of type range <> a reasonable approach would be to
have N separate versions of the body, one for each integer base type
in the implementation. There are three problems with this approach:

  1. It introduces a lot of complexity into the compiler, linker etc.

  2. It does not scale well. What if there are ten integer formals
     and 5 base types. We certainoly can't generate 5**10 versions
     of the body, so we have to gt into the even greater complexity
     of delaying the decisions on what bodies to generate -- by no
     means impossible -- the DEC compiler does this, at least to some
     degree.

  3. The DEC patent may intefere (I offer no opinion on whether this
     patent is valid or not, but note that the mere existence of even
     an invalid patent is problematic).

There are lots of subtleties in the sometimes share case. For example,
suppose you have a generic with a formal of (<>) and the generic uses
'Image. It is highly likely that Wide_Character has to be handlede
very specially, since I canno imagine an implementation that actually
materializes the image table for wide character. In the all sharing
case you have to thunk the image function (as well as lots of other
similar things).

Note that this tunking is really complicated by the fact that you cannot
tell what might need thunking by looking at the generic spec. This means
tha the only simple approach is to thunk everything (in the RR case,
they could have thunk'ed unchecked conversoin -- the reason they did
not is that they did not want to pay the efficiency price).;

Re: Shared Generic Instance Code

[Robert A Duff]

In article <sO6r4AADiBRzEwoj@marnhull.demon.co.uk>,
Bill Keen  <billy@marnhull.demon.co.uk> wrote:
>In article <dewar.859987468@merv>, Robert Dewar <dewar@merv.cs.nyu.edu>
>writes
>> On the other hand, shared generics add a lot
>>of complexity to a compiler. 
>
>He also says Gnat does not share code between generic instances.
>
>But surely the mechanism for shared code is already there because of
>dynamic instantiations like this.

No, it's not *nearly* that simple.  Yes, your example is sharing code
between multiple (run-time) instances, but they're all essentially the
same.  That is, a macro-expanding implementation works just fine in this
example (and yes, the expanded "macro" machine code might get invoked
many times), and still generate just one copy of the code.

Consider, for example: can you share code for "is new
Text_IO.Integer_IO(Integer)" and "is new
Text_IO.Integer_IO(Super_Long_Integer)", where Super_Long_Integer is
range 0..2**1000, which might be accepted by some (mythical,
unfortunately) implementation.

>with text_io;
>procedure p (x : integer) is
>  subtype T is integer range 0..x;
>  package Tio is new text_io.integer_io(T);
>begin
>  Tio.put(0);
>end;
>
>It cannot add complexity if it alredy exists.

Sorry, but shared-code generics are far more complex than you imply
here.

- Bob

Re: Shared Generic Instance Code

[Corey Minyard]

jsa@alexandria (Jon S Anthony) writes:

> 
> In article <E80ry3.Epv@world.std.com> bobduff@world.std.com (Robert A Duff) writes:
> 
> > In article <dewar.859987468@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
> > >... There is also a problem of patents. DEC holds
> > >patents on the implementation of shared generics which make it less worth
> > >while to investigate this approach.
> > 
> > I'm not convinced it's a valid patent.  There was a paper written by
> > Gary Bray at Intermetrics, which outlines essentially the same approach,
> > and, I believe, predates the DEC work by several years.
> 
> I'm not Mr. Patent Lawyer, but I've had to look into this kind of
> stuff over the last few months.  My understanding is that unless
> Intermetrics or Gary Bray took out a patent for their approach (prior
> to the DEC filing), the prior "written up" idea is not sufficient to
> "invalidate" the patent.  Also, it seems that you can't patent an idea
> per se - you have to specify how to produce a complete realization of
> it.  But to be honest, this stuff seems really opaque to me...
> 

I'm not Mr. (US) Patent Lawyer either, but from my understanding of
patent law, if something is patented that had previously been
published, the patent is invalid.  In fact, it might even be illegal.
If it was not published or was kept as a trade secret, the patent will
still stand but the company that kept it as a trade secret is exempt.

I wish the US Supreme Court would nuke all these software patents in
the US.  I'm not sure what goes on in other countries.

-- 
Corey Minyard               Internet:  minyard@acm.org
  Work: minyard@nortel.ca       UUCP:  minyard@wf-rch.cirr.com

Re: Shared Generic Instance Code

[Jon S Anthony]

In article <dewar.860071111@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Jon, it is probably better if you not give legal opinions on patents unless
> you have studied the area. You say

You actually think this is "legal opinion"???!?!?!?  Get real.  I
merely said that I had to look into some of this stuff and talked with
some patent lawyers.  Doesn't mean I understand the area - in fact I
admit that I don't!

> <<I'm not Mr. Patent Lawyer, but I've had to look into this kind of
> stuff over the last few months.  My understanding is that unless
> Intermetrics or Gary Bray took out a patent for their approach (prior
> to the DEC filing), the prior "written up" idea is not sufficient to
> "invalidate" the patent.  Also, it seems that you can't patent an idea
> per se - you have to specify how to produce a complete realization of
> it.  But to be honest, this stuff seems really opaque to me...>>

I'd say there is more than enough disclaimer in here to not take this
particularly seriously!!


> This is completely wrong, prior art does NOT have to be in the form
> of patents.

You realize of course that this comment (indicating that _everything_
I said is wrong) implies that you believe that this stuff is _NOT_
really opaque to me.  And thus, by your measure, I should be taken
seriously on the subject after all!

Criminey...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Shared Generic Instance Code

[Robert Dewar]

Regading "patent lawyer" post from Jon

Actually I meant to send that as email, and canceled it soon after I
accidentally posted it, but you saw it too fast :-) Sorry about that.

The problem here is that the area of copyrights and patents is a complex
one, and it is AMAZING how much misinformation is spread around by
well meaning people.

The view you presented is (a) completely wrong and (b) potentially
damaging, since it encourages people to patent rather than publish
for no good reason.

I cannot imagine ANY "patent lawyer" even vaguely suggesting such an
obvious misinterpretation of prior art!


P.S. actually I find my newsreader can't send you email, something
in your jheaders is vey strange, i see @alexandria, and nothing else)

Re: Shared Generic Instance Code

[Bill Keen]

My post was prompted by thought that if the generic actual parameters
can be determined at compile time then the code for a generic instance
can be a straight inline expansion of the body. But if not, then the
generated code must contain some mechanism for choice. I thought this
constituded code sharing, though I see that the subject is much wider.
But my curiosity is aroused. How do compilers (does GNAT) deal with this
distinction?

-- 
Bill Keen

Re: Shared Generic Instance Code

[Robert Dewar]

Bill Keen said

<<My post was prompted by thought that if the generic actual parameters
can be determined at compile time then the code for a generic instance
can be a straight inline expansion of the body. But if not, then the
generated code must contain some mechanism for choice. I thought this
constituded code sharing, though I see that the subject is much wider.
But my curiosity is aroused. How do compilers (does GNAT) deal with this
distinction?>>

GNAT uses macro expansion for all generic specs and bodies. There is nothing
about the compilation model or structure of GNAT that dictates this choice,
it is a deliberate design choice that favors efficiency over space. Eventually
it would be nice to implement generic sharing at least on an optional basis.

Re: Shared Generic Instance Code

[Tom Moran]

> design choice that favors efficiency over space
Though I haven't done a lot of timing studies, I have the distinct
impression that big generics can *drastically* slow down compilation
(Gnat 3.04a NT/95).  I presume the macro is essentially expanded and
recompiled each time it's instantiated?

Re: Shared Generic Instance Code

[Nick Roberts]

Tom Moran <tmoran@bix.com> wrote in article <3346F7E8.78E6@bix.com>...
> > design choice that favors efficiency over space
> Though I haven't done a lot of timing studies, I have the distinct
> impression that big generics can *drastically* slow down compilation
> (Gnat 3.04a NT/95).  I presume the macro is essentially expanded and
> recompiled each time it's instantiated?
> 

I think he means efficiency (i.e. greater executional speed) of the output
executable, not of the compilation process itself.

Nick.

Re: Shared Generic Instance Code

[Robert Dewar]

<<Though I haven't done a lot of timing studies, I have the distinct
impression that big generics can *drastically* slow down compilation
(Gnat 3.04a NT/95).  I presume the macro is essentially expanded and
recompiled each time it's instantiated?>>

Compiling a macro expanded generic is indeed like compiling the source,
it should be no slower or no faster. Big generics are best avoided if
you are working with a compiler without shared generics and you plan
to do many instantiations, as I mentioned before, have a look at the
GNAT implementation of Integer_IO or Float_IO to see what I mean by
this.

But in any case I was talking about runtime efficiency, not compile
time speed, when I said that macro instantiated generics will generally
be significantly more efficient.