Sorry again for the delay, unquestionably I am not getting mail. I will begin to poll the forum for now on.
How cool, I got pretty enlightening answers! Thanks!
@gugamilare: It seems your code for is-function-or-lambda-p is broken? "fun" is undefined, "membar" is a mispell (I think) and "arg" is unused. The idea in your code is interesting, but read on, I will show an example I am able to carry out in C++ but I have had no success in Lisp yet.
@Ramarren: Function call overhead is only low if either the body of the function takes long to execute or the function itself is called a few times. Otherwise (specially when it gets called a lot in an inner loop to carry on a single addition), it is unacceptable. About macro idempotence, as you said, consistent caching will make these macros look like they are idempotent.
@nuntius: I did some experiments with code like yours. The way I can compile and run code with Lisp is pretty cool! But there is something I need to know. Suppose I place such a code in its own package. When I load its file, I will be able to keep calling the function and successive instatiations will be cached because the fboundp function will be guarding the code emission. The question is: is the information associated with the mapping between symbols and functions always present at compile-time? That mapping is the compile-time data structure I have been talking about. It obviously need to be present in the interactive environment, but is there a way for me to remove it in non-interactive mode? It seems to me that your code is just like what I want, but I am unsure whether I have removed every trace of compile-time computation from runtime.
Ok, so now I am writing an example of typical usage of templates in C++. Since using canonical algebraic structures would be too verbose, let me make a more straight example. Suppose we want to code an intrusive red-black tree data structure. There will be a (compile-time) structure representing the characteristics of the node of the tree, a compile-time structure representing the the characteristics of the element and the comparison operation and a final structure representing the characteristics of the tree itself.
The node structure would be something like.
Code: Select all
struct example_node {
typedef int element_t; /* The element type */
element_t& getelem() {...} /* getter */
const element_t& getelem() const {...}
example_node* left(const example_node& nd) const {...} /* How to get to the left node */
example_node* right(const example_node& nd) const {...} /* How to get to the right node */
example_node* parent(const example_node& nd) const {...} /* How to get to the parent node */
enum {has_size = true}; /* Tells whether the node can hold a size value */
size_t size; /* Will hold the number of elements in the subtree determined by the node */
size_t getsize(const example_node& nd) const {...}
};
The comparison structure would look like:
Code: Select all
struct int_less_than {
typedef int element_t; /* The type of the elements */
bool less(const element_t& x, const element_t& y) const {return x < y;} /* The ordering */
};
Finally, we would have the tree structure, something like
Code: Select all
struct my_rbtree {
typedef example_node node_t; /* The node to manipulate */
typedef int_less_than order_t; /* The ordering */
enum {left = true}; /* Whether to keep track of the leftmost node for getting the min element in O(1) */
enum {right = false}; /* Same for right node */
};
There is a reasong not to bundle the tree structure with the previous two, and that will be explained now.
The code will have some procedures, one of which will be insert, which will insert an element in the tree. insert will in turn call a procedure named insert_fixup, which will mantain the red-black properties, and that one will call both left_rotate and right_rotate, which will do single rotations.
The big point is that insert strongly depends on the ordering of the elements but insert_fixup and the rotations do not. Thus, separting the structures (which will be fed as template arguments to the procedure) allows us to reuse the compiled code for insert_fixup for a tree that sorts ints in increasing and decreasing order, reducing code bloat.
Another ability of this approach is that it can produce code on the fly. In principle, no important code is generate if I just initialize a tree. But the first time someone in the whole project (tons of source files) invoke insert, it will generate insert_fixup and the rotations. If someone else then call remove, it will generate remove_fixup but not the rotations. Actually g++ will, but the duplicates will be removed in link-time.
The code generated is specialized for that particular kind of node, ordering and tree, and parts of it will be shared when appropriate. In more elaborate structures, the programmer might feel inclined to mantain compile time data structures to run algorithms to decide which code to generate, but no trace of that is left at runtime. The binary is small and clean.
So far, the code generated is the fastest possible from the most general human code. If there are optimizations that were supressed due to the specification being too general, compile-time computation (aka template specialization) can be used to sort that out.
But there are drawbacks. Firstly, C++'s syntax is pretty awkward, but that is tolerable. Sencondly, and most importantly, sometimes the tree will be used so infrequently in the code (in terms of runtime call count) that it might pay to join some incompatible implementations into one for reducing code size at the cost of runtime performance. One way to do this would be passing a function pointer to decide the ordering, just like C's qsort.
The thing that made me rethink C++ as the way for generic programming and made me look for Lisp is simple: the syntax for doing such conversion is totally different from the syntax used to originally code the structure. The difference between the syntax of qsort and STL's sort is noticeable.
One more example. Suppose we want to compute the gcd of two elements of some euclidean domain. One way would be C++:
Code: Select all
template<typename E> typename E::t gcd(const typename E::t& a, const typename E::t& b) {...}
where E must provide the module (%) and the test for null element (== 0) operations.
To back off the information to compile time, one would have to go for Cish
Code: Select all
void gcd(void* result, const void* a, const void* b, bool (*is_zero)(const void*), void (*mod)(void*, const void*, const void*)) {...}
In Lisp, we can only hope for doing something like this:
Code: Select all
; sorry for possible n00b mistakes
(defstruct euclidean-domain zero? mod)
And we could code a normal gcd:
Code: Select all
(defun runtime-gcd (E a b) ...)
; uses (euclidean-domain-zero? E) (euclidean-domain-mod E)
But also, it would be great to put a general:
Code: Select all
(define-euclidean-domain ed-of-integers zerop mod)
which would both make a macro named ed-of-integers and a structure (make-euclidean-domain :zero? zerop :mod mod). Or maybe just one of them based on additional arguments.
Anyway, we could invoke (gcd E a b), which would expand into (runtime-gcd E a b) or (gcd (E) a b) (I am making up the syntax) which would expand into (let ((mangled-name ...)) (if (fboundp) ....).
That is what I am trying to achieve.
Sorry for the length of the post, but it is just something I am looking for for a long time and haven't found it. I need some way to:
#0. Express an algorithm generically over algebraic structures.
#1. Define the structures for runtime or compile-time (or both) with uniform syntax.
#2. Instatiate the algorithms for compile-time/runtime based on my decision with a similar syntax.
#3. Know that the system will instantiate specialized code on demand.
#4. Know that code will be shared as needed.
The approach of gugamilare in his mapcar routine satisfies only #0 and #3. It replicates the implementation all over each call. That is fine for mapcar, but is hazardous for a red-black tree.
So, ok, that is it. I hope I have expressed myself well.
Thanks for helping.