sdc@capshaw.UUCP (Dan Capshaw) (10/16/88)
A friend that does a lot of program development in PASCAL has found that using Abstract Data Types (ADTs) significantly increases his productivity by minimizing his debugging time. He describes an ADT as being a data structure or set of data structures combined with an exclusive set of allowable operations on those structures that are placed into a module. The module is essentially a black box to the main program and to the programmer (if they didn't code the module) that is called when an operation needs to be performed on the ADT. For example, suppose you wanted to create an ADT called FRAC that could be used to perform various operations on a fraction--such as 'put numerator', 'put denominator', 'get numerator', ... 'find fractional equiv. of a real'... etc. FRAC would be used to perform these operations in a standard way without the need for the programmer to worry about how FRAC performs its job. In fact, the module's source code may not even be available to the programmer. One reason my friend doesn't like C is because he doesn't feel ADTs can be used effectively in C. But to me, it seems like he is just describing standard function calls where the interface is defined but how the function performs its job may not be. So...I don't see the advantage of ADTs and how they are superior to the structured programming techniques that I have been using for years. Is anyone out there using ADTs in C? If so, am I missing something here? And finally, if ADTs are not as I have described them, what are they, and how can they be used in C (if in fact they should be used in C)? -- Dan Capshaw | ...!uunet!capshaw!sdc 4664 Panther Lake Rd. W. | 206-275-0158 Bremerton, WA 98312 |
g-rh@XAIT.Xerox.COM (Richard Harter) (10/16/88)
In article <116@capshaw.UUCP> sdc@capshaw.UUCP (Dan Capshaw) writes: >A friend that does a lot of program development in PASCAL has >found that using Abstract Data Types (ADTs) significantly >increases his productivity by minimizing his debugging time... >One reason my friend doesn't like C is because he doesn't feel >ADTs can be used effectively in C. But to me, it seems like he is >just describing standard function calls where the interface is defined >but how the function performs its job may not be. So...I don't see >the advantage of ADTs and how they are superior to the structured >programming techniques that I have been using for years. >Is anyone out there using ADTs in C? If so, am I missing something >here? And finally, if ADTs are not as I have described them, what >are they, and how can they be used in C (if in fact they should be used >in C)? Your friend is full of hooey -- you can do ADT's in C just as readily as you can in P****L. On the other hand an ADT is somewhat more than your description. The point of an abstract data type is that you can create types that are not originally part of the language. A language which supports ADT's lets you, in effect, extend the language by adding types. For a simple example, suppose that you wanted to extend C to add complex variables. You would want to be able to declare things as complex, extract the real and imaginary parts, do arithmetic operations and so. Now in a language which has complex variables you can do all these things without knowing the details of how the compiler handles your code; indeed you can't get at the details. How would you go about setting this up in C? Well, you would create an include file with a typedef for COMPLEX as a struct of a pair of doubles, and define macros for the sundry arithmetic operators. If you wanted a more complicated type, linked lists for example, you might need some functions, so you would create a package. This would consist of an include file that has the public declarations and macros, and an implementation file that has the associated functions and private variables. The advantage of abstract data types (and related concepts) is that you can operate at a higher level of generality -- implementation details can be taken care of once instead of being replicated from instance to instance. The idea is more general than that of a black box function. As to whether it is worthwhile in C or any other LLHLL (lower level high level language) is a matter of the application and your approach to software. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
jfh@rpp386.Dallas.TX.US (The Beach Bum) (10/16/88)
In article <116@capshaw.UUCP> sdc@capshaw.UUCP (Dan Capshaw) writes: >Is anyone out there using ADTs in C? If so, am I missing something >here? And finally, if ADTs are not as I have described them, what >are they, and how can they be used in C (if in fact they should be used >in C)? Yes, on very large and hairy projects they are a must. What you and your friend are probably missing is the need to discipline yourselves to do the hard work and keep the data type abstract. An example of how this might happen is if you have a routine CreateObject(), which creates and initializes the object, but then you use free() to dispose of the item rather than having yet another routine, DestroyObject() which itself may only be a call to free(). You have to not know the details of the implementation, and what details you are permitted to know must be very well documented. This is why documentation is so very important. It defines what you are permitted to use reliably. -- John F. Haugh II +----Make believe quote of the week---- VoiceNet: (214) 250-3311 Data: -6272 | Nancy Reagan on Richard Stallman: InterNet: jfh@rpp386.Dallas.TX.US | "Just say `Gno'" UucpNet : <backbone>!killer!rpp386!jfh +--------------------------------------
carroll@s.cs.uiuc.edu (10/16/88)
I use Abstract Data Types all the time - they really are a bonus.
The key thing to remember is that C is *file* oriented - if you want data
to be shared among a set of functions, without access to the data from
other functions, all of the data sharing functions must be in the same
file. For instance, if we wanted a stack handler as an ADT, we would put
the stack variables in a file ("stack.c"), and make them 'static' -
which for external variables means that they are not visible *outside the
file*. The stack handling routines go inside "stack.c" also, where they
can access the stack variables. Other code treats it as a black box, which
is linked in when needed. One of the main advantages of C++ is that it
more directly supports ADT's in programming.
Alan M. Carroll "How many danger signs did you ignore?
carroll@s.cs.uiuc.edu How many times had you heard it all before?" - AP&EW
CS Grad / U of Ill @ Urbana ...{ucbvax,pur-ee,convex}!s.cs.uiuc.edu!carrollgwyn@smoke.ARPA (Doug Gwyn ) (10/17/88)
In article <116@capshaw.UUCP> sdc@capshaw.UUCP (Dan Capshaw) writes: >Is anyone out there using ADTs in C? Certainly, although we call them "abstract data types". ADT is a trademark of a security firm (American District Telegraph). You can implement abstract data types in almost any programming language. Ada has facilities for forcing you to use them, and C++ has special support for them. The usual access to an abstract data type in a C application is via a header file that defines the data type(s) and declares the functions used to implement it. The functions are implemented in a separate source file with everything except the header-documented access hooks made file-static.
john@frog.UUCP (John Woods) (10/19/88)
In article <116@capshaw.UUCP>, sdc@capshaw.UUCP (Dan Capshaw) writes: > A friend that does a lot of program development in PASCAL has > found that using Abstract Data Types (ADTs) significantly > increases his productivity by minimizing his debugging time... > One reason my friend doesn't like C is because he doesn't feel > ADTs can be used effectively in C... > Is anyone out there using ADTs in C? Almost anyone using the Standard IO library functions are using an Abstract Data Type (excluding the few mutants who JUST HAVE to personally fiddle with _cnt or _ptr). There may be a strong tendancy for C programmers to make sure that the details of their data types are visible (so they can "maximize" efficiency by banging structure elements, for example), yet C is perfectly amenable to data abstraction (with just a hint of programmer discipline). By way of contrast: the CLU language (invented by Liskov (and others?) at MIT) is all about data abstraction, and makes it a natural part of the language; a number of CLU adherents maintain that you cannot do data abstraction without such language support. However, I took the Software Engineering course the year before the CLU compiler was ready, and they taught data abstraction using plain old PL/I, with a few little library tricks to make sure that abstract pointers stayed abstract: they insisted that you tag structures with the name of the abstraction, and that you use their "up" and "down" routines to turn real pointers into opaque pointers and vice versa; an opaque pointer had its address modified so it was invalid and would cause a progam crash if referenced as if it were real. -- John Woods, Charles River Data Systems, Framingham MA, (617) 626-1101 ...!decvax!frog!john, john@frog.UUCP, ...!mit-eddie!jfw, jfw@eddie.mit.edu Goooooood Morning Discovery! -Robin Williams Abracadabra, 'press to MECO', America is back in space!
wald-david@CS.YALE.EDU (david wald) (10/21/88)
In article <116@capshaw.UUCP> sdc@capshaw.UUCP (Dan Capshaw) writes: >A friend that does a lot of program development in PASCAL has found that >using Abstract Data Types (ADTs) significantly increases his >productivity by minimizing his debugging time... > >One reason my friend doesn't like C is because he doesn't feel ADTs can >be used effectively in C. But to me, it seems like he is just >describing standard function calls where the interface is defined but >how the function performs its job may not be. So...I don't see the >advantage of ADTs and how they are superior to the structured >programming techniques that I have been using for years. > >Is anyone out there using ADTs in C? If so, am I missing something >here? And finally, if ADTs are not as I have described them, what are >they, and how can they be used in C (if in fact they should be used in >C)? Yes, you can certainly use ADT's in C. On the other hand, you and/or your friend might want to take a look at C++, which provides fairly decent support for creating new data types and hiding their internal structures. ============================================================================ David Wald wald-david@yale.UUCP waldave@yalevm.bitnet ============================================================================
eric@golux.UUCP (Eric S. Raymond) (10/24/88)
In article <116@capshaw.UUCP> sdc@capshaw.UUCP (Dan Capshaw) writes: >Is anyone out there using ADTs in C? If so, am I missing something here? ADT programming is more a style of problem decomposition than a language- dependent bag of tricks. If you *think* in ADT terms, you can write ADT programs in assembler! -- which is not to deny that good facilities like C++'s make it a lot easier. C wasn't built for ADT programming, but can support it quite nicely. The basic method is to implement each ADT as a separate C module (or, in some cases, a module library) with an associated header file that completely defines the ADT interface. My netnews rewrite is explicitly ADT-structured, all 156,638 code lines of it. I think this qualifies as a real-world project of significant size. Here are some ADT principles I've applied. Minimizing shared global information is important. You need to get into the habit of declaring everything static that doesn't absolutely *need* to be externally visible. And globals that 'float', i.e. are not owned and used for interface presentation by some ADT, are a big no-no. I only have one such in my entire suite, and that's a 1K scratch buffer that I never assume stays un-munged across function-calls. I like to write things so that the information in the ADT interface is packaged in a single visible struct, named the same as the file where that's reasonable; that way every reference to the interface points back at the ADT. Function pointers are important. They give you a way for ADTs to pass around and use each others' capabilities without exposing their internals and without tying the capabilities to fixed names that the linker has to know about. For example, I use a macroexpansion function that takes three arguments; a get-character function, an unget-character function and a result buffer. This way, by having different ADTs pass it different arguments, it can handle macroexpansion of (a) file contents, (b) a tty input stream, or (c) an in- memory buffer. Method tables -- name-indexed arrays of function pointers -- are another useful trick to keep in mind, especially if you're writing anything that looks like a command interpreter (and I claim that almost *any* interactive program can gain from being considered as a special-purpose language interpreter, but that's another soapbox). In NNTP, for example, each NNTP command keyword is dispatched through a method table to a separate ADT-like handler module, almost like an object invocation in Smalltalk. I do similar things to dispatch netnews control messages. But I repeat; ADTness, like "structured programming" is a design attitude, not a collection of rules or coding tricks. If you grok the ADT philosophy in fullness, you can apply it even in very impoverished laanguages. If you don't, even the most zealous application of the above guidelines isn't likely to get you the kind of code coherence and cleanness you want. -- Eric S. Raymond (the mad mastermind of TMN-Netnews) UUCP: ...!{uunet,att,rutgers}!snark!eric = eric@snark.UUCP Post: 22 S. Warren Avenue, Malvern, PA 19355 Phone: (215)-296-5718