The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Another question on generics

Is there a language that allows runtime instantiation of a generic?  Is this related to partial specialization of a template in C++, or do I have that wrong in my head?  (I think it's not the same actually, but I want to make sure.)

Instantiation may not be the term I am looking for.  Perhaps I mean specification?

Actually, what I'm wondering is if it's possible have generics that are exportable from a library.  If it's a static library, a linker that generates code at linktime could do it (I know those exist), but how would that work with a shared library?  I suppose you could have a really sophisticated system that does RTTI and handles code generation at runtime, but that strikes me as really ugly.

Is this dynamic typing?
Aaron F Stanton Send private email
Thursday, November 18, 2004
 
 
I don't believe it's possible to do exactly what you're wanting to do.  The best I can think to try is to implement your algorithm in terms of an abstract class argument rather than a type parameter, but then you've got an inheritance relationship you're probably wanting to avoid.

Of course, I can see the benefit in doing what you want; but I don't know if runtime code generation is in the works for C++.  Might wanna throw this out to comp.lang.c++.moderated.
Mike Bland Send private email
Thursday, November 18, 2004
 
 
Whoops, I just realized you weren't asking about C++ specifically...  Sorry.
Mike Bland Send private email
Thursday, November 18, 2004
 
 
It's ok.  I kinda figured I'd get at least one C++ oriented response, since it's so widely used and has templates.  I'd be stunned if I got a Fortran 77 response, though.  :)
Aaron F Stanton Send private email
Thursday, November 18, 2004
 
 
Do you mean development by contract?

Where some object, whatever its written in, defines what it will promise to do.  This isn't quite the same as implementing an interface as an interface isn't the object itself but the means of marshalling between objects. 

But,theoretically you can use an interface to an object to discover what it contracts to do, because the interface can ask the object on the other side of the divide.

Not that I'm aware of any automatic linkage so that you could write object Y that then discovers if object X has the right contract at runtime.  If there was then you could have runtime tables of abstracted objects.
Simon Lucy Send private email
Thursday, November 18, 2004
 
 
I am not sure I understood your question, but I think that .Net does that (for the subset of C++ templates it supports). The CLI code has information about the template parameters so that you can create new instances of templates from an assembly. Or so I am lead to understand.

This in theorically possible with other languages with the same concept (C++ too) but requires 'richer' object files and a smarter linker (which no C++ implementation has, and maybe is not possible according to the current C++ standart).
Whatever
Thursday, November 18, 2004
 
 
If I understand the problem, it could be done with dynamic linking (COM, Python import, EJB server factory, etc).
Tom H
Thursday, November 18, 2004
 
 
If I understand you correctly, it is possible in any dynamically typed programming language such as Python.

In Python, it doesn't matter what is the type of a certain object (although you can test for it explicitly), as long as a certain object behaves in a desired manner - your code would work fine.

This is possible because Python is a dynamically typed programming language, supports operator overloading and exceptions aren't expensive.
Pythonic Send private email
Thursday, November 18, 2004
 
 
Is Python a purely interpreted language, or can it be compiled to native code?
Aaron F Stanton Send private email
Thursday, November 18, 2004
 
 
I hear Psyco is essentially JIT compiling for Python, though I haven't experienced it personally.
http://psyco.sourceforge.net/introduction.html

Languages like Lisp have been compiled since nearly the earliest days, so I think a more pressing question is about finding whether a community has produced an efficient compiler, rather than whether it is capable of doing so. </pedantic>
Tayssir John Gabbour Send private email
Thursday, November 18, 2004
 
 
Bytecode interpreted. It can't be easily compiled to native code precisely because it supports things like not caring for variable types or the "instantiated generics"... :)
ping?
Thursday, November 18, 2004
 
 
Python is a byte-code interpreted language. Although it is possible to freeze (or package) a Python program (in byte-code form) with Python23.dll and other DLLs and redistribute it. To achieve this, you can use something like py2exe.

ABC (Yet Another Bittorrent Client) comes to mind.
Pythonic Send private email
Thursday, November 18, 2004
 
 
Consider looking at an ML.  They provide generics with separate compilation - although I don't think there are any MLs that do dynamic linking, so it's not quite what you're thinking of.

BTW, Pythonic, the ability to use an object of any type where it has a compatible interface is certainly cool, but it's not a feature of "dynamic typing".  It's possible in statically-typed languages, too.  OCaml does it.  You just need to have functions where the static type of a parameter can be something like "any object with a method 'to_string' that takes no parameters and returns a string".

Of course, it's certainly interesting to note that a lot of static-typing research at the moment is going into coming up with ways to assign static types to all the things the dynamic-typing advocates want to be able to do... :)
Iago
Friday, November 19, 2004
 
 
I went back and looked over the Java version of that book earlier mentioned.  It's even better than I remembered.  Plenty of good stuff in there.
Aaron F Stanton Send private email
Friday, November 19, 2004
 
 
I've never used OCaml, although it's interesting to find such a thing in a statically typed language. Btw, this capability does help you avoid creatng deeper hierarchies and defining tons of interfaces.

It seems as if dynamically typed languages can also not get away with being truly dynamically typed. They have to explicitly define the type once data is to be dumped in a database.
Pythonic Send private email
Friday, November 19, 2004
 
 
"Is there a language that allows runtime instantiation of a generic?"

Don't know if there's a *language* that allows this, but .NET supports runtime generation of code, I believe, but I consider this more "systemy" than "languagey". It's like having a library containing a compiler that you can call at run time. You would then run this over your generic, slotting in your preferred types. Dot Net may well have this already since C# is getting generics support.


"Is this related to partial specialization of a template in C++?"

I read this as though you're asking "what is partial specialisation"?

No. Partial specialization of a C++ template is where you write a template, say a generic "swap()" function:

template<typename T> void swap( T &a, T &b )
{ ... general case swapping code ... }


Initially, the compiler uses your swap() template for *all types*.

However, let's say there's a mega fast way of swapping integers that relies on a special technique, and you want to code this technique "manually" because you know the compiler won't auto-generate it from the template. To do this, you'd write a separate swap() function with the same shape signature as the template, but slotting in the actual types you want to use:

void swap( int &a, int &b )
{ ... mega fast code for ints ... }

Thereafter, for all call sites that call the "swap" function, the compiler will check (at compile time) to see if any "specialised" versions can be used. If not, it falls back and instantiates the template.

string s1, s2;
...
swap( s1, s2 );
// The above calls the template version 'coz
// there ain't a special swap() for strings

int a, b;
...
swap( a, b ); // this calls our specialised version



On generics exportable from statically linked libs:

For C++ this isn't how it's done. That's why STL is delivered as a load of header files! Any client code wanting to use templates must #include the header that contains the template code laid bare.


"a linker that generates code at linktime could do it (I know those exist)"

Hmmmm.. Not sure they exist. But please prove me wrong. By traditional definition a linker that generates code must be having some kind of mid-life identity crisis, because this is usually considered the "compiler back end".



"I suppose you could have a really sophisticated system that does RTTI and handles code generation at runtime, but that strikes me as really ugly."

This sounds like we're coming full circle back to the .NET thing I mentioned above. Dunno if that's ugly as such, probably more overkill? To me, it sounds like you're looking in the wrong place for the solution to your issue.



"Is this dynamic typing?"

The fast answer to this is: Dynamic typing is when actual parameter types are discovered at run time.

Imagine writing algorithms in C# that use type "object" as their parameters, and use C#'s interfaces to tell the objects to do things. Code is not generated at run-time to do this! The language generates ONE version of the function which at run-time spends its life inspecting the object "type tags" (RTTI info), and from that looking up functions addresses in tables.

Static typing is where we don't refer to class "object" in our source listings, instead, we refer to exact class names, and call functions directly, rather than using interfaces. No need to inspect type tags, no need for function address lookup tables.


Hope this confuses you more now ;)
Jonathan Send private email
Friday, November 19, 2004
 
 
The link time generation were research projects, I believe.  I'll have to do some digging to find those links.

A really interesting bit you've written there.  Thanks.

The compiler design in Java book describes parametric polymorphism, both explicit and implicit.  Partial specialization seems to be explicit function overloading that takes precedence over the default implementation specified by the template.  C++ uses explicit parametric polymorphism in its templates.  Is there a language with implicit that uses the equivalent of partial specialization?

Which form would make a language more productive for developers, explicit or implicit?
Aaron F Stanton Send private email
Friday, November 19, 2004
 
 
I can't answer your last question.

I did discover an interesting set of papers on the Pizza project, which seems to be involved with adding generics to Java, which contrasts two implementations.

http://pizzacompiler.sourceforge.net/doc/pizza-translation.pdf

I guess I don't need to suggest having a poke about on Google...
Jonathan Send private email
Friday, November 19, 2004
 
 
Not sure if this helps you...

Ada has generics. It is strictly a compiled language with strong, static typing. However, I don't see where this type of generics couldn't be dynamic, if you used an O-O language and take some inspiration from the .NET "delegates".

In Ada, you specify the generic formal parameters as being specific categories of types (e.g., a numeric, an enumeration or a pointer) when you create the generic specification and body. So the generic module can be compiled into an executable library module. Just as you can't create an instance of an abstract class, you can't just invoke an Ada generic module. This is different from the C++ templates, that are macros because the generic formal parameters allow any type/signiture.

Ada requires you to define a generic instantiation in order to produce a module you can actually invoke. You specify the intatiation's name and the generic actual parameters (actual data types, functions, procedures, etc.) to be plugged in for the generic formal parameters to form an instantiation. This is sort of like forming a concrete class from an abstract one, by filling in the actual method implementations.

For example, I could have a generic package for sorted linked lists of "pointer to ..." types. Generic formal parameters are a pointer type and function for comparing two "pointer to ..." types. I can pre-compile this, because all pointers look the same, as does a call to a function with two pointer arguments that returns a boolean.

Ada has "attributes" which include compiler-generated type support values and functions. For examples, an enumeration has attributes such as "first," "last," "next," "prev," "ordinal" and "value". These allow you to write generic code, and are automatically factored into the generic instantiation. From a compiler implementation standpoint, an Ada type is really an instance of a metaclass (e.g., enumeration, pointer, etc.), which plugs into generic modules to form instantiations. This solves the minor problems caused by Ada allowing you to specify non-sequential ordinal values to be used for representing each enumeration value.

A lot of what you get from the instantiation is just strong type checking that the user semantics match. I.e., I can't mix enumeration for "day of week" with enumeration for "sign of zodiac," I must be consistent. So the generic code can simply be reused. A linked list instantiated for "pointer to string" cannot have a "pointer to integer" added to it. Also, the comparison function cannot have a "pointer to enumeration" argument or be inadvertently passed a "pointer to string."

Ada doesn't really indicate if a generic instantiation creates more than a dictionary entry, or a full code module. The intent was to allow the generic module to be executed, but compilers were allowed to create optimized instantiations where desirable. For example, I can optimize if no ordinal values for the enumerations are specified, so the compiler can use sequential integers starting with zero, and fitting in a single byte.

So, I don't see where a suitable language couldn't allow the generic instantiations to be declared at run time. Ada can't do this because it doesn't have any way to reference a module except by a static name reference in code. An O-O language that supports interfaces, composition, metaclasses (to arbitrary depth) and RTTI should work.

The "metaclasses (to arbitrary depth)" may be a rub. This definitely can be done with Lisp. If you can find the original book "Smalltalk-80: The Language and Its Implementation" there is a discussion in Chapter 16 "Protocol for Classes" that describes what I call the "Smalltalk Twist" because it reminds me of the twist in a paper strip that creates a single surface Moebus loop. Its what allows all objects to be instances of a class, which in turn is an instance of Class, which is in turn an object and hence an instance of a subclass of itself. I'm not sure if this is getting you into the theoretical shark waters that make Denotational Semantics such "interesting reading" for the mathematically minded.
Dave Lathrop Send private email
Friday, November 19, 2004
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz