Bryan@SU-SIERRA.ARPA (Doug Bryan) (06/06/86)
Could some of you C and/or Algol hackers out there give me an example of an algorithm where subprograms as parameters are needed and generic formal subprograms won't do the trick. In other words, I'm looking for an algorithm where the subprogram, or actual parameter, cannot be determined until run-time. doug -------
jmb@S1-B.ARPA (Jeff Broughton) (06/06/86)
You asked for an example of an algorithm where subprograms as parameters are needed. You correctly identified the issue as being whether or not the identity of the procedure can be known at compile time. My favorite example is that of a terminal interface. A user logs into a computer system and then tells it what type of terminal is to be used. Several systems that I know of implement this kind of runtime binding by having a set of procedure values that implement various functions, e.g. clear_screen, put_line, etc. Initially, the system initializes the variables for a generic terminal. When the user makes his selection, the routines implementing the protocols specific to the terminal type are assigned to the variables, and presto(!), terminal I/O is transformed for another type. Many might argue that this could be accomplished in other ways. The Unix termcap facility is one way; though I would argue that, in effect, they accomplish the result by implementing pointers to interpretive code. Another is to have a global variable which defines the type of the terminal, and have each terminal interface procedure to examine the terminal type variable and dispatch to the corresponding routine. Ignoring issues of efficiency, my objection to the second approach is that it requires the person who writes the terminal library to have full knowledge of all the terminals that are to be supported, or equivalently, that to add a new terminal type to the system, you have to modify the code. This is terrible modularity. The usual counter argument is that for my example the names of all the terminal types and hence the code for all the terminal types must be in the system anyway; the difference is that it is on top of the terminal library rather than below. This is true in most computer systems that we use today. Being an old Multics programmer, however, I am use to the notion of dynamic linking, where I can load a subroutine by name from the file system and call it without every knowing its name at compile time. Fundamentally, what I am arguing is that the notion of "device independence" requires procedure variables. Sure, you can get around them, but you really wish that you didn't have to. By the way, this is really the same argument as in the earlier message about the implementation of key-bindings in EMACS that appeared earlier on Info-Ada. Only the terms have been changed to aid the unfamiliar.
MHJohnson@HI-MULTICS.ARPA (Mark Johnson) (06/07/86)
I'd like to amplify the response of jmb@s1-b.arpa by describing Multics and by describing a graphics library implementation (Template on VAX/VMS). On Multics, the operating system has a mechanism to automatically search several directories to find a procedure AT RUN TIME. This usually makes the first reference to a procedure slow (say .5sec) but makes subsequent references run at full speed. This is a very useful feature for supporting multiple versions of tools (eg KERMIT, test software, & other stuff) and allows the incremental development of software. I know this is a very brief description, but look at Organick's (sp?) book on Multics or the article in Datamation (April issue I think) for more details. On VAX/VMS, there is a concept of `shared libraries'. If you follow some special procedures, the linker and loader will work to allow you to make updates to subroutines in a shared library without relinking all the programs that reference the library. A VMS implementation of Template uses this to create a number of shared libraries, one for each supported device. You run a program (IDENT) to define a logical name that identifies the shared library that supports your graphics device. All of the programs that use those libraries can move from one device to another without recoding or relinking. New devices can be added at will as long as they adhere to the calling standards and are built in the same way as the other shared libraries. In both cases, the operating system supports the concept of `run-time' binding of procedures. In both cases, argument validation (number and type) can be performed if necessary (usually ignored w/ fatal results though). In both cases, the user of the system is given greater flexibility by postponing the actual procedure call binding to run-time. In both cases, you do not need procedure variables to implement this run-time binding, but you do need to understand how the operating system works and you end up with very system specific implementations. --Mark Johnson <MHJohnson @ HI-MULTICS>
anw@nott-cs.UUCP (06/12/86)
In article <12212651166.12.BRYAN@SU-SIERRA.ARPA> Bryan@SU-SIERRA.ARPA.UUCP writes: > Could some of you C and/or Algol hackers out there give me an example of > [...] an algorithm where the subprogram, or actual parameter, cannot be > determined until run-time. I'm not sure whether this is too simple, or perhaps not at all what you had in mind, but many pre-compiled library modules have this property, assuming that by "until run-time" you mean "at compilation time". For example, you might have PROC simpson = (PROC (REAL) REAL f, REAL a, b, eps) REAL: (# code to integrate "f", a real function of a real parameter, from "a" to "b" within tolerance "eps" by using Simpson's rule # SKIP); shoved into a library [and therefore compiled in complete ignorance of what particular functions might appear], after which the user could write in *his* program things like x := simpson (sqrt, 1, 2, 0.00001); y := simpson ((REAL x) REAL: x * exp(x), x, x+1, exp(-x)); z := simpson ((REAL x) REAL: simpson (sin, 0, x, 1e-7), 0, 1, 1e-7); w := simpson ((z>0 | sin | cos), 0, pi, 1); v := simpson (FRED 7, -1, 1, 0.1) where FRED was an OP (INT) PROC (REAL) REAL. It's possible in Algol to write operators and functions that deliver functions or procedures, but unfortunately the scoping rules prevent this being of more than limited use*. Some compilers implement extensions such as partial parametrisation that make it sensible to compose functions as the program proceeds, in which case it is clearly impracticable (in general) for the compiler to list all the functions that "simpson" might be used with. -- Andy Walker * For example, you can't do things like OP (PROC (REAL) REAL f, g) PROC (REAL) REAL COMPOSE = (REAL x) REAL: f (g (x)); PROC (REAL) REAL sincos = sin COMPOSE cos; but OP (PROC (REAL) REAL f, g) PROC (REAL) REAL OR = IF random < 0.5 THEN f ELSE g FI; PROC (REAL) REAL sorc = sin OR cos; is fine. Spot the difference!