ske@pkmab.se (Kristoffer Eriksson) (01/12/91)
In article <1990Dec29.110202.3862@mathrt0.math.chalmers.se>, augustss@cs.chalmers.se (Lennart Augustsson) wrote: >The problem with the counterclaim is that it talks about a completely >different, newly defined type called func (integer), but the original >claim was about another builtin type. > > If I have tons of code that uses functions (ints) >I would have to make massive changes to be able to use that code with >these new type func (bignum). Even worse, I may not have the source code >for all the things I use, e.g. a library function like qsort (abs) would >fail horribly if passed an object of the new type insteaad of the original. Actually, the situation is not quite that bad. For the purpose of passing one of Dan's structure-emulated pseudo functions to an existing function that only knows about normal C functions, all you have to do is write a third (normal) function that knows how to call one of Dan's functions, and pass this third function to the library function (or whatever function it was). As long as you don't need to keep an unlimited number of such functions alive at one and the same time, this method works well. You only need these intermediate functions during the call to the library function, even if you have lots of Dan's pseudo functions around, so they can be ordinary statically allocated C functions, and a practical trick is to make them reconfigurable and set up each just prior to each use. For examples like qsort(), you would only need one of these intermediate functions. There would be a problem if you were using many library functions that needed to be passed multiple functions and possibly store some of them for later use, but there aren't many such functions in the ordinary C libraries, and if you're writing your own function library, you don't need this method since you can easily make them accept Dan's pseudo-functions directly. Thus, I would say that using Dan's method (lacking real first-class functions) is not such a disaster as you make it out, except if you have very special needs. (Maybe that wasn't such an important point in your argument, but you did make a point out of it.) In article <1991Jan5.182428.615@mathrt0.math.chalmers.se>, augustss@cs.chalmers.se (Lennart Augustsson) wrote: > The bounded number of C-functions is the real reason why a >C-function compose (for C-functions) cannot be written in C. Since >composition can give you an unbounded number of different C-functions, >but there is only a bounded number of them available it has to fail. >(This is why Kristoffer Eriksson "solution" cannot be made to work >in the general case.) The supply of memory is bounded, too, yet we seem to manage. Thus I gather that for many purposes a fixed, but dynamically allocatable, supply of functions is sufficient. Since Lennart challenged me by mail to prove that I could write such a function (whether or not this is the variety that he refers to as the "general" case above), and I think this function may be of more general interest, I will append it at the end of this posting. Still, I do grant that this method may not be sufficient or may be impractical for applications consuming big numbers of dynamic functions. After all, the practicall limit on the number of functions is a lot lower than for the supply of memory. We have so far concentrated solely on completely portable implementations of composed functions. But looking at how many other features available in the C programming environment are implemented, we see that many of them are of a kind that can not be expressed solely by C "builtin" features. Many are in fact implemented as assembler routines or system dependant nonportable C functions or operating system calls, for instance malloc, another function for dynamic allocation of resources. The C libraries are a means of providing C extensions, and they need not necessarily be portable. The portable inter- face is in the function call interface of the libraries. Therefore I will also append one implementation of _unlimited_ dynamic composed function creation. This maybe doesn't touch the subject of first class functions in C unless you take the library interface argument seriously, but I think the routines in themselves are interesting and maybe even useful to somebody. The implementation is obviously not portable, but is on the other hand not overly complicated either. It works on my 68000 Unix system, and I also give a modification for MSC on MSDOS. I don't know whether it is possible to make it work on PC-Unixes, but then Intel processors have always been special. I didn't get it to work on SCO Xenix, since the operating system wouldn't allow me to read the code section, but I would regard that as mostly a deficiency (also called "feature") in the operating system rather than in the general idea of the implementation. The implementation depends on there not being too strict boundaries between the code and data sections in the execution model. My impression is that many processors can accept that, although not all. Firstly, my portable but bounded compose() implementation. This requires ANSI C, unless you want to type a lot. To reconfigure the supply of allocatable functions, set NUM_FUN to the new number of functions, add or remove decl_fun()'s to the desired number of functions, and add function names to the initialization of funarray. One could probably make the preprocessor help with parts of this, but I don't want to overdo this, and besides, the preprocessor might overflow. /* composed.c: */ /* -------- Dynamic composition package begins ----- */ /* By Kristoffer Eriksson, ske@pkmab.se, 1991. */ #define decl_fun(num) \ int composed_ ## num(int x) \ { return(descrarray [num].f1( descrarray [num].f2(x) )); } #define NUM_FUN 5 struct fun_descr { int (*f1)(), (*f2)(); }; typedef int (*funptr)(int); static next_fun = 0; struct fun_descr descrarray [NUM_FUN]; /* Create a supply of to-be composed functions to allocate from. */ decl_fun(0); decl_fun(1); decl_fun(2); decl_fun(3); decl_fun(4); /* Array for referencing the functions. */ funptr funarray [] = { composed_0,composed_1,composed_2,composed_3,composed_4 }; funptr compose(funptr fun1, funptr fun2) { if (next_fun >= NUM_FUN) return 0; descrarray [next_fun].f1 = fun1; descrarray [next_fun].f2 = fun2; return(funarray [next_fun++]); } /* Matching function destruction function omitted. The allocation/deallocation * could of course be more sofisticated too, but this is just a demonstration. */ /* -------- Dynamic composition package ends ------- */ Next, my unbounded (except by memory) but non-portable compose() implementation. This does not require ANSI C, except for the fact that I used ANSI-style function declarations. A replacement for one of the functions for use on MSDOS is at the end. This package should port without too much difficulty to systems that satisfy the assumptions that are made about the execution model. Other system are out of luck. In this implementation you deallocate composed functions simply by calling the ordinary free() on them. /* composeu.c: */ /* -------- Unlimited dynamic composition package begins ----- */ /* By Kristoffer Eriksson, ske@pkmab.se, 1991. */ #include <memory.h> #include <malloc.h> typedef int (*funptr)(int); #define PLACE_HOLDER 12345678 /* Change this to a 16-bit value if 16-bit pointers are used. */ /* This value may have to be adjusted in order not to match any instruction sequence in the function template(). */ /* Template function that is copied to make new functions. The place holder * makes it possible to locate the place of the values that the local function * pointers are initialized to in the binary image of the function, in most * ordinary computer architectures. A more serious obstacle may be systems * that refuse to execute out of the data segment or copy from the text segment. * * Sometimes there are special system calls that can be used to turn a memory * area into an executable segment (e.g. execseg() in SCO Xenix), or special * calls to allocate new executable memory, or both. They should be put to use * by compose() in that case. There may also be operating system deficiencies * that make the whole approach impossible. In SCO Xenix, for instance, copying * from the code segment seems to be disallowed, which propably means that to * implement this on Xenix you'ld have to define template() as an array initia- * lized with suitable machine code (you could copy it from the assembly output * of the compiler for the original C version of the function), or you'ld have * to compile template() in a segment of it's own and somehow link it in as a * data segment. I don't know about the other i386 Unix versions. */ int template(int x) { funptr f1 = (funptr)PLACE_HOLDER, f2 = (funptr)PLACE_HOLDER; return(f1(f2(x))); } int after_template(void) {} char *memfind(char *mainstr, char *substr, int mainlen, int sublen) { int i; /* Find a substring in another string. */ if (mainlen <= 0) return(0); if (sublen <= 0) return(mainstr); mainlen -= sublen; while (mainlen-- >= 0) { if (*mainstr == *substr) for (i = 0; mainstr[i] == substr[i]; ) if (++i >= sublen) return(mainstr); ++mainstr; } return(0); } char *insert_funptr(char *area, int len, funptr fun) { funptr search_pattern = (funptr)PLACE_HOLDER; char *where; /* Find the place holder in a copy of the template function, and * insert the desired function pointer there in stead. */ where = memfind(area, (char*)&search_pattern, len, sizeof(search_pattern)); if (where == 0) write(2, "Compose() does not currently work on this machine\n", 50); else memcpy(where, (char *)&fun, sizeof(search_pattern)); return(where); } funptr compose(funptr fun1, funptr fun2) { char *res; char *where; int funsize = (char *)after_template - (char *)template; /* Allocate a fresh copy of the template function. */ if ((res = malloc(funsize)) == 0) return(0); memcpy(res, (char *)template, funsize); /* Insert the two function pointers in the right places. */ where = insert_funptr(res, funsize, fun1); if (where == 0) return(0); where = insert_funptr(where + sizeof(fun1), funsize - (where - res) - sizeof(fun1), fun2); if (where == 0) return(0); return((funptr)res); } /* -------- Unlimited dynamic composition package ends ------- */ /* -------- Replacement insert_funptr() for MSDOS ------------ */ /* Under MSDOS, the vanilla version may work if compiled to a .COM file, * with the same segment used for both code and data. To make an .EXE file, * you have to use the "large" memory model in order for the system to look * in the right segment for the allocated functions, and then you need the * following replacement for insert_funptr, since the function pointer values * are being assigned in 16 bits chunks. (This works for v5.1 at least.) * * With Microsoft C, use for instance the command CL -AL on all modules. */ #ifdef MSDOS char *insert_funptr(char *area, int len, funptr fun) { funptr search_pattern = (funptr)PLACE_HOLDER; char *where; where = memfind(area, (char*)&search_pattern, len, 2); if (where == 0) write(2, "Compose() does not currently work on this machine 1\n", 52); else memcpy(where, (char *)&fun, 2); where = memfind(area, (char*)&search_pattern + 2, len, 2); if (where == 0) write(2, "Compose() does not currently work on this machine 2\n", 52); else memcpy(where, (char *)&fun + 2, 2); return(where); } #endif /* -------- Replacement Insert_funptr() ends ----------------- */ Lastly, I give the test program I got from Lennart (it does what it should, so it would be pointless for me to write one myself). You can compile the test program and the composition packages as separate files that you link together if you like. Set MAXFUNC to the number of composed functions you want to test (the same or less than NUM_FUN if it is the bounded version you test). The program first composes a number of functions and stores them in an array, and then calls them to check the results. /* comptest.c: */ /* -------- Test program begins ------------------------------ */ #include <stdio.h> typedef int (*intintfun)(int); intintfun compose(intintfun, intintfun); #define MAXFUNC 5 #define TESTDATA 42 int id(int x) { return x; } int suc(int x) { return x+1; } main(int argc, char **argv) { intintfun adders[MAXFUNC+1]; int i; adders[0] = id; for(i = 1; i <= MAXFUNC; i++) { adders[i] = compose(adders[i-1], suc); if (adders[i] == 0) { printf("Sorry, ran out of functions at %d\n", i); exit(1); } } for(i = 0; i <= MAXFUNC; i++) if ((*adders[i])(TESTDATA) != TESTDATA+i) { printf("Sorry, adder %d failed\n", i); exit(1); } printf("You may have a working compose!\n"); exit(0); } /* -------- Test program ends -------------------------------- */ I'd still use my original macro implementation whenever it satisfies my needs, though, since it is both portable and needs no reconfiguration. -- Kristoffer Eriksson, Peridot Konsult AB, Hagagatan 6, S-703 40 Oerebro, Sweden Phone: +46 19-13 03 60 ! e-mail: ske@pkmab.se Fax: +46 19-11 51 03 ! or ...!{uunet,mcsun}!sunic.sunet.se!kullmar!pkmab!ske